From: Eric Mahurin <eric_mahurin@...>
Date: 2005-06-30T06:08:08+09:00
Subject: Re: shift vs. slice!(0) and others

--- Nikolai Weibull
<mailing-lists.ruby-talk@rawuncut.elitemail.org> wrote:

> Eric Mahurin wrote:
> 
> [...]
> 
> > This sure would be nice for easy and high performance
> > implementations of circular and gap buffers.
> 
> Please do explain,
>         nikolai

OK.  I've been thinking about this stuff quite a bit while
working on my cursor package.  Let's start with a gap buffer. 
The traditional approach is to a have an array with the data
before the cursor at the beginning of the array and data after
the cursor at the end of the array.  In the middle is the "gap"
and could be gigabytes of virtual address space if you have
enough control over virtual memory (you don't in Ruby). 
Something like this:

   A  B  C  D  E -------------- F  G  H  I
   0  1  2  3  4 ---the gap--- -4 -3 -2 -1
  ^             ^              ^          ^
begin          before         after      end

All single element operations (move cursor, read, write, and
especially insert/delete) are O(1) operations.  Compare this to
an array/string where insert/delete are O(n).

Another way you could organize the data above would be like
this:
 
    F   G   H   I   A   B   C   D   E
    0   1   2   3   4   5   6   7   8
  ^               ^                   ^
after=0      begin_end             before

In this case, the "gap" is what is outside the array.  If
single all single element operations on the ends of this array
(push, pop, shift, unshift) were O(1), then all our single
element operations at the cursor in this structure would also
be O(1).  The problem is shift/unshift usually aren't.  But
they could be by simply moving the start array pointer around
(shift looks to be O(1)).

Another approach I'm taking now is implementing this gap buffer
by using 2 arrays/strings, where one represents what's before
the cursor and one represents what's after the cursor:

    A   B   C   D   E
    0   1   2   3   4
  ^                   ^
begin               before

    I   H   G   F
    0   1   2   3
  ^               ^
 end            after

I store the "after" array/string in reverse so that all
operations at the cursor occur at the ends of one or both of
these arrays/strings.

I haven't seen either of these approaches before.  Has anybody
else done them?

For implementing a circular buffer, the first two
implementations above can be easily adapted by removing the
begin, end, or begin_end indices and allowing to wrap around or
pass through them.  Implementing a circular buffer using ideas
from the last implementation above is a little trickier, but I
think I have a solution.

This is just a sampling of implementations that my next cursor
release will provide.  There are many more possibilities
(linked-lists, hybrids, trees, etc) that I probably won't get
to yet.



		
__________________________________ 
Yahoo! Mail 
Stay connected, organized, and protected. Take the tour: 
http://tour.mail.yahoo.com/mailtour.html