On 10/26/07, Ruby Quiz <james / grayproductions.net> wrote:
> The task is to implement data structures for efficiently editing text. One
> common data structure is a gap buffer:
>
>         http://en.wikipedia.org/wiki/Gap_buffer
>
> Other options to consider include: ropes (see quiz #137), linked lists, simple
> strings, or a multi-level combination of data structures (i.e. for lines vs.
> characters in a line). There are many data structures that may work efficiently
> with simple editing operations, but not all of those data structures will work
> well for more complex functionality.

Here is another solution :

http://rubyquiz.com/hosted_solutions/145/eric/linked.rb

http://rubyquiz.com/hosted_solutions/145/eric/edit_test2.rb

In addition to the minimal functionality, I implemented a method that
inserts a file in the text (#read).   But, it doesn't read the entire
file into memory (it actually only needs to hold one character of the
file at a time).   Only edits to the file are held in memory.

I implemented this by using a linked list of text buffers.  Each
buffer is a gap buffer or a slice of an IO (begin/end positions).
Although the gap buffer I implemented (using two strings) is simple
and fast in ruby, it isn't as memory efficient as a normal gap buffer
since each string effectively has a gap (where a normal gap buffer has
one shared gap between before/after text).

I changed the API for this implementation.  All of the methods also
take a lambda/proc that is called when switching from one buffer to
another (updating the current cursor object).  Another possibility
which keeps the original API is to add a wrapper class to do this, but
it won't be nearly as efficient because of the extra layer (the
performance cost of the linked list is almost zero using the new API).
 I also added some testing of file "read"s and
moving/inserting/deleting through files.  SplitGapCursor can actually
be used with the old or new benchmarks (just don't link it to another
buffer).  Here are some results (total measures the same as before and
ftotal measures operations on file text) :

SplitGapCursor: 4000x100
insert_before     0.360000   0.000000    0.360000 (  0.359155)
left              0.630000   0.000000   0.630000 (  0.632066)
right             0.620000   0.000000   0.620000 (  0.623372)
up                 0.480000   0.000000   0.480000 (  0.470801)
down              0.480000   0.000000   0.480000 (  0.478180)
insert_after      0.340000   0.000000   0.340000 (  0.343666)
delete_before     0.500000   0.000000   0.500000 (  0.496911)
delete_after      0.500000   0.000000   0.500000 (  0.501599)
read              0.000000   0.000000   0.000000 (  0.000031)
up                 0.480000   0.000000   0.480000 (  0.475890)
read              0.000000   0.000000   0.000000 (  0.000025)
delete_before     0.970000   0.000000   0.970000 (  0.971401)
right             0.510000   0.000000   0.510000 (  0.502776)
left              0.560000   0.000000   0.560000 (  0.559028)
down              0.550000   0.000000   0.550000 (  0.552482)
up                 0.520000   0.000000   0.520000 (  0.516446)
delete_after      0.920000   0.000000   0.920000 (  0.920615)
total             3.910000   0.000000   3.910000 (  3.905750)
ftotal             4.030000   0.000000   4.030000 (  4.022773)

Notice the read time (0).  But, I used StringIO instead of a real file
for testing.