From: Eric Mahurin <eric.mahurin@...>
Date: 2007-10-31T15:53:12+09:00
Subject: Re: [QUIZ] Editing Text (#145)

On 10/26/07, Ruby Quiz <james@grayproductions.net> wrote:
>         http://en.wikipedia.org/wiki/Gap_buffer

Here is a strange solution of mine.

I start by partially implementing a string class that works equally
well on the front and the back (double ended queue string).  My
array.c patch from a couple years ago did something like this, but the
data structure below is a bit more memory efficient since it can share
a single "gap" and recirculates unused space better.  Basically, the
implementation below is a circular buffer that reallocates when it is
full.  It would be great if the standard String and Array were
symmetrical like this.  It would increase the ways to use simple
strings and arrays.

Next I use this double ended queue string to implement something like
a gap buffer.  You can think of the gap as being at the ends of of
this double-ended string.  Text before the cursor is at the end of the
string and text before the cursor is at the beginning.

The performance is O(n), but not nearly as fast as some a simple
solution (5X slower).  If String was symmetical, I would use that and
it would be a different story.

If I have time, I may try this DQString in a linked-list data-structure...

dqstring.rb:


# characters can be in either of these ranges:
#     gapped : @begin...length, 0...@end
#     contiguous : @begin...@end
# inheriting String only for memory efficiency
# inherited methods won't necessarily make sense

class DQString < String
    def initialize(data="")
        @begin = 0
        @end = data.length
        super(data)
    end
    def inspect
        "#<DQString: begin=#{@begin}, end=#{@end}, #{super}>"
    end
    def length
        if (len = @end-@begin)>=0
            len
        else
            super+len
        end
    end
    def << (ch)
        if @end==size
            if @begin>1
                # use the front, making a gap in the middle
                self[0] = ch
                @end = 1
                self
            else
                @end += 1
                # let ruby realloc when needed
                super(ch)
            end
        else
            self[@end] = ch
            @end += 1
            if @end==@begin
                # double the size when the gap becomes empty
                @begin += size
                self.replace(self+self)
            else
                self
            end
        end
    end
    def >> (ch)
        if @begin.zero?
            @begin = size-1
            if @end<@begin
                # use the back, making a gap in the middle
                self
            else
                # double the size to make room at the front
                @end += size
                self.replace(self+self)
            end
        else
            @begin -= 1
            if @begin==@end
                # double the size when the gap becomes empty
                @begin += size
                self.replace(self+self)
            else
                self
            end
        end
    ensure
        self[@begin] = ch
    end
    def pop
        if @end==@begin
            nil
        else
            @end -= 1
            ch = self[@end]
            if (len = @end-@begin)>=0
                # remove excess trailing space if too much
                self.slice!(-len,len) if size-@end>(len<<1)
            elsif @end.zero?
                len = (@end=size)-@begin
                if @begin>(len<<1)
                    # remove excess leading space
                    self.slice!(0, len)
                    @begin -= len
                    @end -= len
                end
            end
            ch
        end
    end
    def shift
        if @begin==@end
            nil
        else
            ch = self[@begin]
            @begin += 1
            if (len = @end-@begin)>=0
                if @begin>(len<<1)
                    # remove excess leading space
                    self.slice!(0, len)
                    @begin -= len
                    @end -= len
                end
            elsif @begin==size
                # remove excess trailing space if too much
                self.slice!(-@end,@end) if (@end<<1)+len<0
                @begin = 0
            end
            ch
        end
    end
end


dqcursor.rb:


require 'dqstring'

class DQCursor
    def initialize
        @data = DQString.new
        @nafter = 0
    end
    def insert_before(ch)
        @data << ch
    end
    def insert_after(ch)
        @nafter += 1
        @data >> ch
    end
    def delete_before
        @data.length>@nafter and @data.pop
    end
    def delete_after
        @nafter.nonzero? and (@nafter-=1; @data.shift)
    end
    def left
        @data.length>@nafter and (@nafter+=1; @data >> @data.pop)
    end
    def right
        @nafter.nonzero? and (@nafter-=1; @data << @data.shift)
    end
    def up
        nbefore = @data.length-@nafter
        while nbefore.nonzero?
            nbefore -= 1
            @data >> (ch=@data.pop)
            return(true) if ch==?\n
        end
    ensure
        @nafter=@data.length-nbefore
    end
    def down
        while @nafter.nonzero?
            @nafter -= 1
            @data << (ch=@data.shift)
            return(true) if ch==?\n
        end
    end
end