Ordered dicts

[bearophileHUGS at lycos.com]

Steve Holden:

I forgot a detail: in the Python version of Odict I use element
deletion is O(n). You need a second dict to improve that (or a duble
linked list of hashing operations, see below).

> FYI there was a *long* discussion around the need for Speed sprint about
> implementing ordered dicts. As the discussion started by your thread has
> started to reveal, everyone has just-ever-so-slightly-different
> requirements. IIRC the goal was dropped because it wasn't possible to
> agree on a specification.

I received a similar answer about graphs too. But this time I think the
semantic of an ordered dict is simple and clear enough, so I belive a
generally acceptable solution may be found still.
An implementation with double linked lists allows amortized O(1) for
all the usual dict metods, deletions too. Maybe firstkey()  lastkey()
methods can be added too, that return the first and last key of the
odict.
The following is a simple example, note that this is a "wrong"
implementation, because you can't scan the keys in the ordered way (you
can scan the values in a ordered way). I presume in a C implementation
you can find the key of a given value. If this isn't possibile without
creating a chain of hashing operations, then I too drop off from this
odict idea :-)

class Odict(dict):
  def __init__(self):
    dict.__init__(self)
    self.lh = None # list header
    self.lt = None # list tail

  def __getitem__(self, key):
    return dict.__getitem__(self, key)[1]

  def __setitem__(self, key, val):
    if key in self:
      dict.__getitem__(self, key)[1] = val
    else:
      new = [self.lt, val, None]
      dict.__setitem__(self, key, new)
      if self.lt: self.lt[2] = new
      self.lt = new
      if not self.lh: self.lh = new

  def __delitem__(self, k):
    if k in self:
      pred,_,succ= dict.__getitem__(self,k)
      if pred: pred[2] = succ
      else: self.lh = succ
      if succ: succ[0] = pred
      else: self.lt = pred
      dict.__delitem__(self, k)
    else: raise KeyError, k

Bye,
bearophile