hooke/compat/odict.py

   1 # -*- coding: utf-8 -*-
   2
   3 # An ordered dictionary implementation.  OrderedDict entered the
   4 # Python Standard Library in Python 2.7 and 3.1.  See `PEP 372`_ for
   5 # details.  Code_ by Armin Ronacher and the PEP 273 authors.
   6 #
   7 # .. _PEP 372: http://www.python.org/dev/peps/pep-0372/
   8 # .. _Code: http://dev.pocoo.org/hg/sandbox/raw-file/tip/odict.py
   9
  10 """
  11     odict
  12     ~~~~~
  13
  14     This module is an example implementation of an ordered dict for the
  15     collections module.  It's not written for performance (it actually
  16     performs pretty bad) but to show how the API works.
  17
  18
  19     Questions and Answers
  20     =====================
  21
  22     Why would anyone need ordered dicts?
  23
  24         Dicts in python are unordered which means that the order of items when
  25         iterating over dicts is undefined.  As a matter of fact it is most of
  26         the time useless and differs from implementation to implementation.
  27
  28         Many developers stumble upon that problem sooner or later when
  29         comparing the output of doctests which often does not match the order
  30         the developer thought it would.
  31
  32         Also XML systems such as Genshi have their problems with unordered
  33         dicts as the input and output ordering of tag attributes is often
  34         mixed up because the ordering is lost when converting the data into
  35         a dict.  Switching to lists is often not possible because the
  36         complexity of a lookup is too high.
  37
  38         Another very common case is metaprogramming.  The default namespace
  39         of a class in python is a dict.  With Python 3 it becomes possible
  40         to replace it with a different object which could be an ordered dict.
  41         Django is already doing something similar with a hack that assigns
  42         numbers to some descriptors initialized in the class body of a
  43         specific subclass to restore the ordering after class creation.
  44
  45         When porting code from programming languages such as PHP and Ruby
  46         where the item-order in a dict is guaranteed it's also a great help
  47         to have an equivalent data structure in Python to ease the transition.
  48
  49     Where are new keys added?
  50
  51         At the end.  This behavior is consistent with Ruby 1.9 Hashmaps
  52         and PHP Arrays.  It also matches what common ordered dict
  53         implementations do currently.
  54
  55     What happens if an existing key is reassigned?
  56
  57         The key is *not* moved.  This is consitent with existing
  58         implementations and can be changed by a subclass very easily::
  59
  60             class movingodict(odict):
  61                 def __setitem__(self, key, value):
  62                     self.pop(key, None)
  63                     odict.__setitem__(self, key, value)
  64
  65         Moving keys to the end of a ordered dict on reassignment is not
  66         very useful for most applications.
  67
  68     Does it mean the dict keys are sorted by a sort expression?
  69
  70         That's not the case.  The odict only guarantees that there is an order
  71         and that newly inserted keys are inserted at the end of the dict.  If
  72         you want to sort it you can do so, but newly added keys are again added
  73         at the end of the dict.
  74
  75     I initializes the odict with a dict literal but the keys are not
  76     ordered like they should!
  77
  78         Dict literals in Python generate dict objects and as such the order of
  79         their items is not guaranteed.  Before they are passed to the odict
  80         constructor they are already unordered.
  81
  82     What happens if keys appear multiple times in the list passed to the
  83     constructor?
  84
  85         The same as for the dict.  The latter item overrides the former.  This
  86         has the side-effect that the position of the first key is used because
  87         the key is actually overwritten:
  88
  89         >>> odict([('a', 1), ('b', 2), ('a', 3)])
  90         odict.odict([('a', 3), ('b', 2)])
  91
  92         This behavor is consistent with existing implementation in Python
  93         and the PHP array and the hashmap in Ruby 1.9.
  94
  95     This odict doesn't scale!
  96
  97         Yes it doesn't.  The delitem operation is O(n).  This is file is a
  98         mockup of a real odict that could be implemented for collections
  99         based on an linked list.
 100
 101     Why is there no .insert()?
 102
 103         There are few situations where you really want to insert a key at
 104         an specified index.  To now make the API too complex the proposed
 105         solution for this situation is creating a list of items, manipulating
 106         that and converting it back into an odict:
 107
 108         >>> d = odict([('a', 42), ('b', 23), ('c', 19)])
 109         >>> l = d.items()
 110         >>> l.insert(1, ('x', 0))
 111         >>> odict(l)
 112         odict.odict([('a', 42), ('x', 0), ('b', 23), ('c', 19)])
 113
 114     :copyright: (c) 2008 by Armin Ronacher and PEP 273 authors.
 115     :license: modified BSD license.
 116 """
 117 from itertools import izip, imap
 118 from copy import deepcopy
 119
 120 missing = object()
 121
 122
 123 class odict(dict):
 124     """
 125     Ordered dict example implementation.
 126
 127     This is the proposed interface for a an ordered dict as proposed on the
 128     Python mailinglist (proposal_).
 129
 130     It's a dict subclass and provides some list functions.  The implementation
 131     of this class is inspired by the implementation of Babel but incorporates
 132     some ideas from the `ordereddict`_ and Django's ordered dict.
 133
 134     The constructor and `update()` both accept iterables of tuples as well as
 135     mappings:
 136
 137     >>> d = odict([('a', 'b'), ('c', 'd')])
 138     >>> d.update({'foo': 'bar'})
 139     >>> d
 140     odict.odict([('a', 'b'), ('c', 'd'), ('foo', 'bar')])
 141
 142     Keep in mind that when updating from dict-literals the order is not
 143     preserved as these dicts are unsorted!
 144
 145     You can copy an odict like a dict by using the constructor, `copy.copy`
 146     or the `copy` method and make deep copies with `copy.deepcopy`:
 147
 148     >>> from copy import copy, deepcopy
 149     >>> copy(d)
 150     odict.odict([('a', 'b'), ('c', 'd'), ('foo', 'bar')])
 151     >>> d.copy()
 152     odict.odict([('a', 'b'), ('c', 'd'), ('foo', 'bar')])
 153     >>> odict(d)
 154     odict.odict([('a', 'b'), ('c', 'd'), ('foo', 'bar')])
 155     >>> d['spam'] = []
 156     >>> d2 = deepcopy(d)
 157     >>> d2['spam'].append('eggs')
 158     >>> d
 159     odict.odict([('a', 'b'), ('c', 'd'), ('foo', 'bar'), ('spam', [])])
 160     >>> d2
 161     odict.odict([('a', 'b'), ('c', 'd'), ('foo', 'bar'), ('spam', ['eggs'])])
 162
 163     All iteration methods as well as `keys`, `values` and `items` return
 164     the values ordered by the the time the key-value pair is inserted:
 165
 166     >>> d.keys()
 167     ['a', 'c', 'foo', 'spam']
 168     >>> d.values()
 169     ['b', 'd', 'bar', []]
 170     >>> d.items()
 171     [('a', 'b'), ('c', 'd'), ('foo', 'bar'), ('spam', [])]
 172     >>> list(d.iterkeys())
 173     ['a', 'c', 'foo', 'spam']
 174     >>> list(d.itervalues())
 175     ['b', 'd', 'bar', []]
 176     >>> list(d.iteritems())
 177     [('a', 'b'), ('c', 'd'), ('foo', 'bar'), ('spam', [])]
 178
 179     Index based lookup is supported too by `byindex` which returns the
 180     key/value pair for an index:
 181
 182     >>> d.byindex(2)
 183     ('foo', 'bar')
 184
 185     You can reverse the odict as well:
 186
 187     >>> d.reverse()
 188     >>> d
 189     odict.odict([('spam', []), ('foo', 'bar'), ('c', 'd'), ('a', 'b')])
 190
 191     And sort it like a list:
 192
 193     >>> d.sort(key=lambda x: x[0].lower())
 194     >>> d
 195     odict.odict([('a', 'b'), ('c', 'd'), ('foo', 'bar'), ('spam', [])])
 196
 197     .. _proposal: http://thread.gmane.org/gmane.comp.python.devel/95316
 198     .. _ordereddict: http://www.xs4all.nl/~anthon/Python/ordereddict/
 199     """
 200
 201     def __init__(self, *args, **kwargs):
 202         dict.__init__(self)
 203         self._keys = []
 204         self.update(*args, **kwargs)
 205
 206     def __delitem__(self, key):
 207         dict.__delitem__(self, key)
 208         self._keys.remove(key)
 209
 210     def __setitem__(self, key, item):
 211         if key not in self:
 212             self._keys.append(key)
 213         dict.__setitem__(self, key, item)
 214
 215     def __deepcopy__(self, memo=None):
 216         if memo is None:
 217             memo = {}
 218         d = memo.get(id(self), missing)
 219         if d is not missing:
 220             return d
 221         memo[id(self)] = d = self.__class__()
 222         dict.__init__(d, deepcopy(self.items(), memo))
 223         d._keys = self._keys[:]
 224         return d
 225
 226     def __getstate__(self):
 227         return {'items': dict(self), 'keys': self._keys}
 228
 229     def __setstate__(self, d):
 230         self._keys = d['keys']
 231         dict.update(d['items'])
 232
 233     def __reversed__(self):
 234         return reversed(self._keys)
 235
 236     def __eq__(self, other):
 237         if isinstance(other, odict):
 238             if not dict.__eq__(self, other):
 239                 return False
 240             return self.items() == other.items()
 241         return dict.__eq__(self, other)
 242
 243     def __ne__(self, other):
 244         return not self.__eq__(other)
 245
 246     def __cmp__(self, other):
 247         if isinstance(other, odict):
 248             return cmp(self.items(), other.items())
 249         elif isinstance(other, dict):
 250             return dict.__cmp__(self, other)
 251         return NotImplemented
 252
 253     @classmethod
 254     def fromkeys(cls, iterable, default=None):
 255         return cls((key, default) for key in iterable)
 256
 257     def clear(self):
 258         del self._keys[:]
 259         dict.clear(self)
 260
 261     def copy(self):
 262         return self.__class__(self)
 263
 264     def items(self):
 265         return zip(self._keys, self.values())
 266
 267     def iteritems(self):
 268         return izip(self._keys, self.itervalues())
 269
 270     def keys(self):
 271         return self._keys[:]
 272
 273     def iterkeys(self):
 274         return iter(self._keys)
 275
 276     def pop(self, key, default=missing):
 277         if default is missing:
 278             return dict.pop(self, key)
 279         elif key not in self:
 280             return default
 281         self._keys.remove(key)
 282         return dict.pop(self, key, default)
 283
 284     def popitem(self, key):
 285         self._keys.remove(key)
 286         return dict.popitem(key)
 287
 288     def setdefault(self, key, default=None):
 289         if key not in self:
 290             self._keys.append(key)
 291         dict.setdefault(self, key, default)
 292
 293     def update(self, *args, **kwargs):
 294         sources = []
 295         if len(args) == 1:
 296             if hasattr(args[0], 'iteritems'):
 297                 sources.append(args[0].iteritems())
 298             else:
 299                 sources.append(iter(args[0]))
 300         elif args:
 301             raise TypeError('expected at most one positional argument')
 302         if kwargs:
 303             sources.append(kwargs.iteritems())
 304         for iterable in sources:
 305             for key, val in iterable:
 306                 self[key] = val
 307
 308     def values(self):
 309         return map(self.get, self._keys)
 310
 311     def itervalues(self):
 312         return imap(self.get, self._keys)
 313
 314     def index(self, item):
 315         return self._keys.index(item)
 316
 317     def byindex(self, item):
 318         key = self._keys[item]
 319         return (key, dict.__getitem__(self, key))
 320
 321     def reverse(self):
 322         self._keys.reverse()
 323
 324     def sort(self, *args, **kwargs):
 325         self._keys.sort(*args, **kwargs)
 326
 327     def __repr__(self):
 328         return 'odict.odict(%r)' % self.items()
 329
 330     __copy__ = copy
 331     __iter__ = iterkeys
 332
 333
 334 if __name__ == '__main__':
 335     import doctest
 336     doctest.testmod()