An ordered dictionary for the Python library?

[Antoon Pardon]

On 2007-09-14, Mark Summerfield <m.n.summerfield at googlemail.com> wrote:
> On 14 Sep, 10:49, Antoon Pardon <apar... at forel.vub.ac.be> wrote:
>> > # some time later
>> > d["e"] = 15
>> > # later still
>> > d["b"] = 70
>> > d.keys() # returns ['a', 'b', 'e', 'm', 'x']
>> > d.values() # returns [1, 70, 15, 4, 20]
>>
>> which seems to be exactly what my avltree module mentioned earlier
>> provides.
>>
>> >>> from avltree import Tree
>> >>> d=Tree(a=1, x=20, b=35, m=4)
>> >>> d["e"] = 15
>> >>> d["b"] = 70
>> >>> d.keys()
>>
>> ['a', 'b', 'e', 'm', 'x']>>> d.values()
>>
>> [1, 70, 15, 4, 20]
>
> Antoon,
>
> Your AVL tree looks impressive (although it has five times the lines
> of my ordereddict), but it does not appear to support dict.update()'s
> API (which was extended in 2.4), so you can't do: avl.update({'g':
> 20}, a=9, b=22).

It is true that I didn't follow up the API difference made to dict
since I wrote the module, but I think these are rather minor.
I don't think it would take a lot of work to correct these.

> Also, it does not provide the key(), value(), and item() methods that
> the API I proposed can support (because in an ordereddict, index
> positions make sense).

At the time I wrote my module I never had a need for these. Do you have
a use case or is it a consideration of completeness that makes you want
these? Maybe I can take a look in how to implement this, but at this
moment it doesn't sound that usefull to me.

On the other hand your API doesn't seem to allow for iterating over only
a part of the keys. Supposing all keys are strings, I can easily iterate
over all keys that start with an 'n' or with any arbitrary prefix.
That IMO seems more usefull.

> If there was consensus on an API and you, me, and others had different
> implementations, we could always come up with some tests to compare
> their relative performance, and put the fastest one(s) forward in a
> PEP. (I don't care if my own code is used or not, it is the
> functionality in Python's standard library that I want, whoever's code
> it is.)

Good luck on finding that consensus. If you really want this I fear you
will have to start writing that PEP before a consensus is reached and
hope to find a proposal that will be acceptable to the majority and
especially the BDFL.

-- 
Antoon Pardon