sorteddict PEP proposal [started off as orderedict]

[Antoon Pardon]

On 2007-09-26, Mark Summerfield <m.n.summerfield at googlemail.com> wrote:
> On 26 Sep, 11:27, Hrvoje Niksic <hnik... at xemacs.org> wrote:
>> Mark Summerfield <m.n.summerfi... at googlemail.com> writes:
>> > On 26 Sep, 09:51, Hrvoje Niksic <hnik... at xemacs.org> wrote:
>> >> Duncan Booth <duncan.bo... at invalid.invalid> writes:
>> >> > I that's the point though: you can't write one implementation
>> >> > that has good performance for all patterns of use
>>
>> >> An implementation of sorted dict using a balanced tree as the
>> >> underlying data structure would give decent performance in all the
>> >> mentioned use cases.  For example, red-black trees search, insert, and
>> >> delete in O(log n) time.
>>
>> > Basically, as implemented, I have to invalidate if there is any
>> > change [...]
>>
>> No argument here, as long as the limitation is understood to be a
>> consequence of the current implementation model.  Seriously proposing
>> a sorteddict that is a mere syntactic sugar over dict dooms the PEP to
>> rejection.
>
> On the Py3K list GvR made it clear that sorteddict wouldn't be in
> Python until an implementation had been in popular use for some
> time... so I will not put forward a PEP for it.
>
>> Major programming language libraries have included sorted mapping and
>> set types for a while now, making the performance and complexity
>> constraints generally well understood.  We should make use of that
>> knowledge when designing sorteddict.
>
> I know! I use Python and C++ and Qt, so what with the STL and Qt's
> containers I'm used to having far more containers to choose from than
> Python offers. I think Python could do with both sorteddict and
> sortedset in the collections module, but to get decent performance
> will require a balanced tree (or a skiplist) implementation, and I
> don't have the time to do that. Apart from Antoon Pardon's AVL tree,
> there's also Chris Gonnerman's RBTree, also pure Python, with a dict
> API and that seems to accept a cmp function, but again, I don't know
> whether it could be adapted to the sorteddict((mapping | sequence |
> nothing), cmp=None, key=None, reverse=None) API that Paul Hankin
> described.

Well you should decide what you want. In a previous exchange one of the
things that was wanted was that you could already seed a tree by using
key word arguments so that you could do the following:

t=Tree(a=15, b=30)

which would be equivallent to:

t=Tree()
t.update(a=15,b=30)

But with the above proposal

t=Tree(cmp=cmp)

is not equivallent to

t=Tree()
t.update(cmp=cmp)

So it seems the API needs some more sorting out.

-- 
Antoon Pardon