# \[SUMMARY\] Editing Text (#145)

**URL:** <https://rubytalk.org/t/summary-editing-text-145/42014>\
**Category:** ruby-talk\
**Created:** [8 November 2007 14:02 UTC](https://rubytalk.org/t/summary-editing-text-145/42014 "2007-11-08T14:02:24Z")\
**Posts on this page:** 2\
**Page:** 1

<div class="post-metadata">

**Author:** ![James\_Edward\_Gray\_II](https://avatars.discourse-cdn.com/v4/letter/j/ea5d25/32.png) [@James\_Edward\_Gray\_II](https://rubytalk.org/u/James_Edward_Gray_II)\
**Post date:** [8 November 2007 14:02 UTC](https://rubytalk.org/t/summary-editing-text-145/42014/1 "2007-11-08T14:02:24Z")

</div>

Implementing an efficient data structure for this problem can be tricky. A  
couple of the solutions turned out to have a higher complexity than it first  
appeared. That doesn't mean they aren't valuable to examine though.

Let's have a look at Holger's code below. It's an implementation of the  
quiz-recommended gap buffer data structure. It's a very clean implementation of  
the idea that helped me understand what a gap buffer really is. Here's the  
constructor:

&nbsp;&nbsp;class GapBuffer  
&nbsp;&nbsp;&nbsp;&nbsp;def initialize(data="", i=0)  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;@data = data  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;@gap\_start = i  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;@gap\_len = 0  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;@GAP = " "\*64  
&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;  
&nbsp;&nbsp;&nbsp;&nbsp;# ...

The actual content of our text editing session will be kept in @data. However,  
that data may contain some extra material called a "gap," which will begin at  
the index @gap\_start and be @gap\_len characters long. @GAP is just a constant  
used to insert new gaps when that last one is exhausted.

How this interacts in usage is well shown by the insert methods:

&nbsp;&nbsp;&nbsp;&nbsp;# ...  
&nbsp;&nbsp;  
&nbsp;&nbsp;&nbsp;&nbsp;def insert\_before(ch)  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if @gap\_len.zero?  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;@data[@gap\_start, 0] = @GAP  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;@gap\_len = @GAP.length  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;@data[@gap\_start] = ch  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;@gap\_start += 1  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;@gap\_len -= 1  
&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;  
&nbsp;&nbsp;&nbsp;&nbsp;def insert\_after(ch)  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if @gap\_len.zero?  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;@data[@gap\_start, 0] = @GAP  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;@gap\_len = @GAP.length  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;@data[@gap\_start+@gap\_len-1] = ch  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;@gap\_len -= 1  
&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;  
&nbsp;&nbsp;&nbsp;&nbsp;# ...

The idea for both of these methods is simple. To add content, we place it in  
either end of the gap, shrinking the space available there. To insert a  
character before the caret we must add the character to the beginning of the  
gap, bump the gap start index beyond the new character, and decrease our count  
of available space in the gap. Adding after the caret just means placing the  
character at the end and decreasing the length counter.

The if statement at the beginning of both of these methods watches for the gap  
to be exhausted. When we run out of space, a new gap is inserted and our length  
counter is reset.

Deleting characters is just the opposite operation:

&nbsp;&nbsp;&nbsp;&nbsp;# ...  
&nbsp;&nbsp;  
&nbsp;&nbsp;&nbsp;&nbsp;def delete\_before  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return if @gap\_start.zero?  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;@gap\_start -= 1  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;@gap\_len += 1  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;@data[@gap\_start]  
&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;  
&nbsp;&nbsp;&nbsp;&nbsp;def delete\_after  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return if @gap\_start+@gap\_len \>= @data.length  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;@gap\_len += 1  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;@data[@gap\_start+@gap\_len-1]  
&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;  
&nbsp;&nbsp;&nbsp;&nbsp;# ...

To remove something all we really have to do is to manipulate our index and/or  
length to put the discarded character back into the gap. Once there, later  
operations can overwrite it normally.

Note that the last lines of these methods return the "deleted" character and the  
first lines skip the operations when there are no characters beyond the gap.

Now the harder operations of a gap buffer are moving the caret. We'll start  
with left() and right(), which are the easier moves:

&nbsp;&nbsp;&nbsp;&nbsp;# ...  
&nbsp;&nbsp;&nbsp;&nbsp;  
&nbsp;&nbsp;&nbsp;&nbsp;def left  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return if @gap\_start.zero?  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;@data[@gap\_start+@gap\_len-1] = @data[@gap\_start-1]  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;@gap\_start -= 1  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;@data[@gap\_start]  
&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;  
&nbsp;&nbsp;&nbsp;&nbsp;def right  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return if @gap\_start+@gap\_len\>=@data.length  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;@data[@gap\_start] = @data[@gap\_start + @gap\_len]  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;@gap\_start += 1  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;@data[@gap\_start - 1]  
&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;&nbsp;&nbsp;  
&nbsp;&nbsp;&nbsp;&nbsp;# ...

Moving the caret to either side means transferring a character from one end of  
the buffer to the other. Then we can just expand the gap to include the moved  
character's previous location, so future editing operations will swallow in up.  
For example, given the following data:

&nbsp;&nbsp;The gap buffer[], or our caret, is shown here with brackets.

A move to the left() is gives us:

&nbsp;&nbsp;The gap buffe[r]r, or our caret, is shown here with brackets.

The moved character is on the right of the buffer while the original is inside.  
Characters inside the buffer don't really exist in the content so we don't have  
any duplication here.

Now for the hard moves:

&nbsp;&nbsp;&nbsp;&nbsp;# ...  
&nbsp;&nbsp;&nbsp;&nbsp;  
&nbsp;&nbsp;&nbsp;&nbsp;def up  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;col = column  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;cursor = @gap\_start-col  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return if cursor.zero?  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;cursor\_line = @data.rindex(?\n, cursor-2)  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;cursor\_line = 0 if cursor\_line.nil?  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;cursor\_line += col+1  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if cursor\_line \> cursor-1  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;cursor\_line = cursor-1  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;left while @gap\_start \> cursor\_line  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;true  
&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;  
&nbsp;&nbsp;&nbsp;&nbsp;def down  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;col = column  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;cursor = @data.index(?\n, @gap\_start + @gap\_len)  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return if cursor.nil?  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;cursor\_line = cursor+1+col  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;cursor = @data.index(?\n, cursor+1)  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;cursor = @data.length if cursor.nil?  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;cursor\_line = cursor if cursor\_line \> cursor  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;right while @gap\_start + @gap\_len \< cursor\_line  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;true  
&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;&nbsp;&nbsp;  
&nbsp;&nbsp;&nbsp;&nbsp;# ...

While this looks like a lot of code, the procedure is simple.

The column() helper method, which we will see shortly, figures out where we are  
in the current line. For the down() method, that's really all we need to mark  
our current location. When moving up() though, we want to reach the line before  
ours, or somewhere between one and two newlines back. To make that easier, up()  
first backs up by the column count to start the search from the beginning of the  
line.

Then we have a terrific use index()/rindex() with the optional minimum index  
parameter to find the next newline past the end of the gap buffer. When that  
search fails, the caret is moved to the beginning or end of the data which must  
be the last line we needed to cross. Having found the desired line, the current  
column is added on, and trimmed to match the data if it exceeds the line.

Together, these operations give us a where we are and where we need to get to.  
The actual move is performed with repeated calls to left()/right(), one for each  
character we need to travel.

Here are a couple of location methods, one of which we just saw in use:

&nbsp;&nbsp;&nbsp;&nbsp;# ...  
&nbsp;&nbsp;&nbsp;&nbsp;  
&nbsp;&nbsp;&nbsp;&nbsp;def position  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;@gap\_start  
&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;  
&nbsp;&nbsp;&nbsp;&nbsp;def column  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;lbreak = @data.rindex(?\n, @gap\_start-1)  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;lbreak.nil? ? @gap\_start : (@gap\_start-(lbreak+1))  
&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;&nbsp;&nbsp;  
&nbsp;&nbsp;&nbsp;&nbsp;# ...

As you can see, position() is just an alias for @gap\_start. The column() method  
though is just more clever use of the rindex() method. It really works just  
like we saw in up(), save that it doesn't need to skip over a newline.

The last operation supported by this solution is to stringify the data:

&nbsp;&nbsp;&nbsp;&nbsp;# ...  
&nbsp;&nbsp;&nbsp;&nbsp;  
&nbsp;&nbsp;&nbsp;&nbsp;def to\_s  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return @data[0, @gap\_start] +  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;@data[@gap\_start+@gap\_len, @data.length-@gap\_start-@gap\_len]  
&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;end

The actual data is just the concatenation of what's on both sides of the gap.  
The code above assembles that with simple indexing.

Holger had hoped the solution was O(n), but unfortunately it turns out to be  
O(n\*\*2). Eric explains why this is and provides tips for how to get it to O(n)  
in this email:

&nbsp;&nbsp;[http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-talk/277308](http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-talk/277308)

While the code does need the mentioned changes to reduce its complexity, I still  
felt it was a very clean implementation of the gap buffer and quite easy to  
follow. This should make fixing it up a snap.

My thanks to those who did manage to find the time for the quiz. It was a  
tricky problem to do well and all of the solutions showed off neat approaches.

Tomorrow we will do some vehicle counting, programmer style...

---

<div class="post-metadata">

**Author:** ![Eric\_Mahurin](https://avatars.discourse-cdn.com/v4/letter/e/b4bc9f/32.png) [@Eric\_Mahurin](https://rubytalk.org/u/Eric_Mahurin)\
**Post date:** [8 November 2007 17:40 UTC](https://rubytalk.org/t/summary-editing-text-145/42014/2 "2007-11-08T17:40:01Z")

</div>

> Implementing an efficient data structure for this problem can be  
> tricky. A  
> couple of the solutions turned out to have a higher complexity than it  
> first  
> appeared. That doesn't mean they aren't valuable to examine though.

I thought we had a good mix of data structures in the solutions. Anybody  
with an interest in data structures should take a look. Here are the data  
structures (or features) I saw in the solutions :

\* conventional gap buffer  
\* "double-ended" gap buffer (one using Array and another String)  
\* deferred gap movement until editing operations  
\* linked list of lines (strings)  
\* circular buffer  
\* linked list of buffers (gap and file)

I thought all of them were very good solutions. Other possibilities were  
also mentioned.

Let's have a look at Holger's code below.

...

&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;def insert\_before(ch)

> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if @gap\_len.zero?  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;@data[@gap\_start, 0] = @GAP  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;@gap\_len = @GAP.length  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;@data[@gap\_start] = ch  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;@gap\_start += 1  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;@gap\_len -= 1  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end
> 
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;def insert\_after(ch)  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if @gap\_len.zero?  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;@data[@gap\_start, 0] = @GAP  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;@gap\_len = @GAP.length  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;@data[@gap\_start+@gap\_len-1] = ch  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;@gap\_len -= 1  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end

...

Holger had hoped the solution was O(n), but unfortunately it turns out to be

> O(n\*\*2). Eric explains why this is and provides tips for how to get it to  
> O(n)  
> in this email:
> 
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;[http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-talk/277308](http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-talk/277308)
> 
> While the code does need the mentioned changes to reduce its complexity, I  
> still  
> felt it was a very clean implementation of the gap buffer and quite easy  
> to  
> follow. This should make fixing it up a snap.

BTW, the simple way to make Holger's code O(n) is to replace this line (in  
both inserts):

@data[@gap\_start, 0] = @GAP

with this:

@data[@gap\_start , 0] = @data

This makes the gap (garbage data) the same size as the real data. This  
amortizes the O(n) gap increase across O(n) operations, so that on average  
each insert is still O(1). The gap just needs to be increased to a size  
relative to the size of the real data. This is the same way the  
reallocating arrays/strings (like ruby's C-level Array/String  
implementations) are done so that operations at the end (where the "gap" is)  
are amortized O(1).

Eric

> **···**
>
> On 11/8/07, Ruby Quiz \<james@grayproductions.net\> wrote: