From: Eric Mahurin <eric.mahurin@...>
Date: 2007-11-09T02:40:01+09:00
Subject: Re: [SUMMARY] Editing Text (#145)

------=_Part_45111_8400975.1194543600249
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit
Content-Disposition: inline

On 11/8/07, Ruby Quiz <james@grayproductions.net> wrote:
>
> 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.


...

          def insert_before(ch)
>             if @gap_len.zero?
>               @data[@gap_start, 0] = @GAP
>               @gap_len = @GAP.length
>             end
>             @data[@gap_start] = ch
>             @gap_start += 1
>             @gap_len -= 1
>           end
>
>           def insert_after(ch)
>             if @gap_len.zero?
>               @data[@gap_start, 0] = @GAP
>               @gap_len = @GAP.length
>             end
>             @data[@gap_start+@gap_len-1] = ch
>             @gap_len -= 1
>           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:
>
>         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

------=_Part_45111_8400975.1194543600249--