An ordered dictionary for the Python library?

[Antoon Pardon]

On 2007-09-14, Mark Summerfield <m.n.summerfield at googlemail.com> wrote:
>> > 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.

If you don't have a use case, I advise you to drop them. As far as I
understand people's sentiments, including a feature without a use case
illustrating its usefullness will decrease your chances.

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

The feature doesn't depend on any assumption. if your keys are integers
you can iterate over all keys between 121 and 8264. Iterating over all
keys that start with an 'n' just depends on the fact that all such
strings lie between the strings 'n' and 'o'.

However not all keys acceptable to a dict, will be acceptable to
a SortedDict. Some types are hashable but not completly comparable.
Those objects will not be usable as a key in a SortedDict although
they can be used as a key in an normal 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.

I'm not interrested in writing a PEP. My impression from asking around
is that is too much work for too little chance to get it accepted.
That is more a personal evaluation of how I value my time and how much I
would prefer it to have my module included than about the PEP process
in itself.

If someone would like to use my avl module as a starting point for a PEP,
I may consider allowing that, but writing the PEP myself is going to
take too much time from other projects.

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

I wish you all the luck you can get. Maybe if you succeed I'll change
my mind about writing a PEP myself.

However I think your chances will increase if you write your module
and have it available in the cheese shop. If people start using your
module regularly, your chances of it being included in the standard
library will increase greatly.

-- 
Antoon Pardon

-- 
Antoon Pardon