[Sugar-devel] I'm looking for a tree...

[Benjamin M. Schwartz]

I've had amazing difficulty communicating what I'm looking for here.

Those closest thing is

http://en.wikipedia.org/wiki/Rope_(computer_science)

A rope is a binary tree that _imposes_ an ordering on its leaves that has
nothing whatsoever to do with their values (the values are essentially
opaque).  This is very unusual; almost all standard tree structures
_derive_ an ordering _from_ the values.

Unfortunately, all implementations of Ropes that I have seen so far are
designed only to store Chars, whereas I need to store arbitrary python
objects.  I'd like to avoid coding such a beast myself, but I may have no
choice.  It would help if someone could identify Ropes as a specialization
of a more general type of tree, but I have not seen any claims of this kind.

The only property I'm looking for that Ropes don't intrinsically satisfy
is "Reverse lookup".  That is to say, I would like to be able to hold a
pointer to a particular object in the tree, and at some later time, walk
back up the tree from that pointer to work out the object's current index.
 It does seem like that should be doable with a Rope, especially if we
move to the special case in which the leaves are "arrays of length 1".

--Ben

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 198 bytes
Desc: OpenPGP digital signature
Url : http://lists.sugarlabs.org/archive/sugar-devel/attachments/20090608/ce66c463/attachment.pgp