A sorted map type.

[Alex Martelli]

"Mark Pilgrim" <f8dy at diveintopython.org> wrote in message
news:B6FD065A.56BE%f8dy at diveintopython.org...
> in article slrn9dbfe5.qmh.apardon at trout.vub.ac.be, apardon at trout.vub.ac.be
> at apardon at trout.vub.ac.be wrote on 4/12/01 10:33 AM:
>
> > Is there a module that provides a sorted map.
> >
> > What I need is a map type that allow you to visit
> > all members in key order. Also the possibility
> > to look for the next in line after a search
> > would be nice. Is there a module that already
    ...
> separate list). Sorting (key,value) pairs (items) is simplest, but not
> fastest."
>     http://www.activestate.com/ASPN/Python/Cookbook/Recipe/52306
>
> Article and associated code by Alex Martelli, which, if you're new around
> here, means it's definitive.

Nope, not necessarily definitive -- that would be so if the timbot or effbot
had authored it; I'm the _fallible_ one of the three bots, the one with the
HumanFoibles module activated.

Anyway, that recipe does not provide optimal code if your typical usage
pattern alternates too frequently between inserting/deleting an element
and 'visiting all members in key order'; it focuses on the more typical
usage pattern where bursts of modifications happen for a while, then
bursts of visits, and back again.  It re-sorts each time a 'visit' happens
after 1 or more (potential) modifications, so if you have M occurrences
of modify-then-revisit of the N items, runtime is O(M*NlogN).  And it
gives no help with "look for the next in line after a search" -- the search
runs at dictionary-speed (call it O(1):-), but then you'd have to turn
to standard module bisect for the 'next' part (again, a re-sort...).

Wrapping nice layers around a hash table for a job that should be
done with a tree has its limits -- at some point, not having the data
structure that WANTS to be there to underly your code leads you
smack into a wall.  I think it might be worthwhile looking for a real
AVL tree implementation for Python.  Sam Rushing has one, and I
think it's worth exploring; see his summary page of links at
http://www.nightmare.com/software.html, and specifically his
AVL module (ftp://www.nightmare.com/squirl/python-ext/avl/,
but I'm having some problem getting to the ftp site right now).


Alex