An ordered dictionary for the Python library?

[Mark Summerfield]

On 14 Sep, 12:46, Antoon Pardon <apar... at forel.vub.ac.be> wrote:
> On 2007-09-14, Mark Summerfield <m.n.summerfi... 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.

I'm sure you're right.

> > 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.

I put them in for completeness, although in some contexts I have found
the ability to ask for the n-th item to be v. useful.

> 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.

That is an appealing feature---but I don't want to make any assumption
about keys (they could be ints, id()s, strs, or anything that is
acceptable to a dict.

There's nothing to stop you creating a PEP for your AVL tree---I'd
certainly be glad for one to be in the collections module. I'm not
advocating "only one" ordered data structure, but rather one
particular one---and I certainly hope the collections module will have
several eventually, and that other people will propose PEPs for other
data structures, such as AVL trees, B*Trees, skiplists, etc., since
all have something to offer.

> > 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.

I don't expect my API to satisfy everyone, but by making it as close
to what exists already, i.e., a dict, yet with keys that "happen" to
be ordered (and offering a few extra methods to help users exploit
that if they want), I am hoping this will make it more likely to be
acceptable.