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

[Benjamin M. Schwartz]

Lucian Branescu wrote:
> Would an ordered dictionary otherwise be all right, or am I
> misunderstanding your requirements? There are other implementations,
> like http://www.xs4all.nl/~anthon/Python/ordereddict/

No, an ordered dictionary is not enough.  All these ordered dictionaries
are ordered either by time or by sorting the keys.  Neither will work for
me.  The problem is simple: if I insert something at position 5, I need
the object currently at position 5 to move to position 6, and the object
currently at position 6 to move to position 7, etc.

To accomplish this in an time-ordered odict, I would have to remove all
keys subsequent to the insertion point, make the insertion, and then
re-insert those keys.  That's O(n).

To accomplish this in a sorted-order odict, I would have to generate a new
key that causes my insertion to occur at the right location.  If there are
repeated insertions at the same location, generating such keys becomes an
O(n) operation.  To see this, suppose I am repeatedly inserting at the
second position.  Initially, the keys are (0,1).  The first insertion has
to pick a key between 0 and 1, e.g. 0.5.  The second insertion has to pick
a key between 0 and 0.5: e.g. 0.25.  The number of bits required to store
these keys to sufficient precision increases by one bit on each insertion.
 This means that the length of the keys is O(n), so every comparison is O(n).

--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/20090607/bd5abafa/attachment.pgp