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

James Zaki james.zaki at gmail.com
Mon Jun 8 11:09:30 EDT 2009


Ben,

Perhaps try communicating the problem you're trying to solve with the data
structure. ie, what you're storing, what would you be looking for when
searching stored objects...

This would yield better advice, and share information within the context of
sugar.


James.


2009/6/8 Benjamin M. Schwartz <bmschwar at fas.harvard.edu>

> I've had amazing difficulty communicating what I'm looking for here.
>
> Those closest thing is
>
> http://en.wikipedia.org/wiki/Rope_(computer_science)<http://en.wikipedia.org/wiki/Rope_%28computer_science%29>
>
> 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
>
>
> _______________________________________________
> Sugar-devel mailing list
> Sugar-devel at lists.sugarlabs.org
> http://lists.sugarlabs.org/listinfo/sugar-devel
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.sugarlabs.org/archive/sugar-devel/attachments/20090608/3d5febac/attachment.htm 


More information about the Sugar-devel mailing list