Re: O(1) performance for insertions/deletions at the front of an Array/String

--- Mathieu Bouchard <[e-mail]> wrote:

> On Sat, 2 Jul 2005, Eric Mahurin wrote:
> 
> > Not exactly what I was thinking.  I was thinking that when
> you
> > try to unshift and you have no free space available to the
> > left, you'd reallocate to a new area growing by a certain
> > percentage - just like you do when you run out of space on
> the
> > right.
> 
> Oh. Yeah, that's exactly what i meant, sorry for the
> confusion.

I thought what you described earlier was to move the data to
the right by a percentage lower than the amount you allocate on
to the right of the array/string.  You'd only need to
reallocate if you didn't have enough space to the right to
steal from.  I have to think about it a little of the
performance vs. memory usage of the above vs. this one.

> > OT a little ... regarding insertion/deletion do you think
> we can also
> > make a few methods in String vs Array a little more
> consistent:
> 
> Part of Matz's plan for Ruby 2 is to make String and Array
> less consistent
> with each other.

What is the reason behind this?  I don't get it.  Do you have a
link to the reasoning?

One example of the usefulness of having them similar is my
rubyforge project "cursor" (extensive external iterator API). 
My base class assumes that buffers use << and [] (could be
Array/String).  Many of my derived classes use other common
methods ([]=, slice!, size) in addition to apply to both Array
and String:

Cursor::Indexed - simple iterator over an Array/String
Cursor::Split - use 2 to make all ops at the end (i.e. <<)
Cursor::Gap - gap buffer (like in a text editor)
Cursor::Shifting - leave the cursor at the beginning/end
Cursor::Circular::Indexed - wraparound Array/String
Cursor::Circular::Split - circular buffer using multiple
buffers
Cursor::Circular::Gap - gap can wraparound
Cursor::Circular::Shifting - Cursor::Shifting with no begin/end

If insertions/deletions at the front of an Array/String were
made O(1), I'd probably get rid of *::Gap and *::Split (like
the Array2 I gave earlier) because *::Shifting would probably
be better than those 2.

If Array/String were too different, I'd have to double these
classes to get the functionality that I can get now.  There are
many other places that I use these commonalities.  I use
duck-typing quite a bit to have methods/classes handle both
Array and String.

BTW, I don't have all of the above implemented yet.  And I may
have other implementations that may use the commonality of
Array/String (i.e. linked list of fixed sized buffers).



		
____________________________________________________ 
Yahoo! Sports 
Rekindle the Rivalries. Sign up for Fantasy Football 
http://football.fantasysports.yahoo.com