Re: Immutable Ropes

On Wed, 16 Mar 2005, Nikolai Weibull wrote:
> * Mathieu Bouchard (Mar 15, 2005 19:50):
> > One related project is my old project called MetaRuby. I presented it
> > at the Europ臺sche Ruby Konferenz 2004 (although I wrote all of the
> > code in 2001).
> Perhaps most importantly, Rope would be a built-in type in Ruby 2.0, at
> least in my virtual world where everything is the way I want it.

It's nice to have such a world, as long as it's connected with reality. In
case Matz doesn't like the ropes (which may very well be the case), I am
trying to help you by suggesting a "plan B".

Plan B's are very important in life =)

Personally I'd very much like a way to replace the implementation of
String to whatever someone may like. Currently, the only "easy" way of
doing it is using MetaRuby, starting with a minimum amount of C, and then
writing more C as long as the default String-methods provided by MetaRuby
feel slow.

> Anyway, I didn't quite understand how your strings work.  I didn't
> follow how your strings are created from other data.  Perhaps
> http://artengine.ca/matju/MetaRuby/ wasn't the right url for this?  

It's the correct URL.

My Arrays/Hashes/Strings are abstract, so you have to provide your own
implementation. However, you only have to do so with a handful of
methods. Whereas the builtin Ruby containers are optimised for speed, by
calling methods directly in their class (effectively bypassing
methodlookup) or by modifying an array of bytes directly, MetaRuby instead
defines everything to minimise the effort of coding an implementation of a
container class.

A few examples are provided, especially the SubArrays and SubStrings,
which are views of a segment of another container; AutoArray (etc) which
is just a dummy container working exactly like Array except slower, but
can be _subclassed_ so that a _few_ lines later you have #undo and #redo
(see UndoableString, UndoQueue).

I haven't had the patience yet for writing a rope-like package, but it
could be done rather easily by someone who knows the algorithms better
than I do. A wrapper for C ropes can be completed by submoduling
("including") the abstract String class.

Personally, the O(log n) element lookup is bugging me a bit, so I'd rather
have a two-level sqrt(n)-tree that does lookup in O(1) and insertion in
O(sqrt n), which is not as fast as O(log n) or O(1) insertion, but is a
damn lot better than O(n) insertion. What do you think? (maybe this
question is rhetorical because you seem to really want to use the original
Boehm ropes implementation)



PS: For the Perl fans, let's say MetaRuby's Abstract Containers is Ruby's
equivalent to Perl's tie(), except much slower and a bit more flexible.

PPS: For the Perl haters, forget what you just read and consider the thing
for its own virtues, and not as a tainted wound coming from evil Perl in
Hieronymous Bosch's hell. (I'm serious.)

_____________________________________________________________________
Mathieu Bouchard -=- Montr饌l QC Canada -=- http://artengine.ca/matju