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