From: Philip Gatt <gattster@...>
Date: 2007-10-30T03:49:35+09:00
Subject: Re: [QUIZ] Editing Text (#145)

Now that you've submitted a reference implementation, it looks much  
more interesting to try to optimize. I bet you'll get a better  
response now.

On Oct 29, 2007, at 6:36 AM, Eric Mahurin wrote:

> On 10/26/07, Ruby Quiz <james@grayproductions.net> wrote:
>> A simple string to represent text buffer isn't efficient
>> enough because inserting (i.e. typing) and deleting (backspace) in  
>> the middle
>> would result in moving all of the text to the end for each operation.
>
> Here is an inefficient string-based solution:
>
> class StringCaret
>     # cursor/caret is between char i-1 and i
>     def initialize(data="", i=0)
>         @data = data
>         @i = i
>     end
>     def insert_before(ch)
>         @data[@i,0] = ("" << ch)
>         @i += 1
>     end
>     def insert_after(ch)
>         @data[@i,0] = ("" << ch)
>     end
>     def delete_before
>         @i.nonzero? and @data.slice!(@i-=1)
>     end
>     def delete_after
>         @data.slice!(@i)
>     end
>     def left
>         @i.nonzero? and @i-=1
>     end
>     def right
>         @i<@data.length and @i+=1
>     end
>     def up
>         while @i.nonzero?
>             @i -= 1
>             break(true) if @data[@i]==?\n
>         end
>     end
>     def down
>         while @i<@data.length
>             break(@i+=1) if @data[@i]==?\n
>             @i += 1
>         end
>     end
> end
>
>
> The benchmark results look like this on my machine:
>
>> ruby -r string.rb test.rb 2 StringCaret.new 1000 100  
>> StringCaret.new 2000 100
> StringCaret.new: 1000x100
> ...
> total             7.800000   0.030000   7.830000 (  7.851117)
> StringCaret.new: 2000x100
> ...
> total            26.810000   0.100000  26.910000 ( 27.015445)
>
> The run-time almost quadrupled when the data-size doubled, so this  
> is O(n**2).
>
> An O(n) solution with this minimal functionality is doable in about
> the same number of lines as above.  But, you have to use another data
> structure...
>
> Eric
>