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 not hasattr(self, '_keys'):
 212             self._keys = [] # work around multiprocessing.Queue rebuild
 213         if key not in self:
 214             self._keys.append(key)
 215         dict.__setitem__(self, key, item)
 216
 217     def __deepcopy__(self, memo=None):
 218         if memo is None:
 219             memo = {}
 220         d = memo.get(id(self), missing)
 221         if d is not missing:
 222             return d
 223         memo[id(self)] = d = self.__class__()
 224         dict.__init__(d, deepcopy(self.items(), memo))
 225         d._keys = self._keys[:]
 226         return d
 227
 228     def __getstate__(self):
 229         return {'items': dict(self), 'keys': self._keys}
 230
 231     def __setstate__(self, d):
 232         self._keys = d['keys']
 233         dict.update(d['items'])
 234
 235     def __reversed__(self):
 236         return reversed(self._keys)
 237
 238     def __eq__(self, other):
 239         if isinstance(other, odict):
 240             if not dict.__eq__(self, other):
 241                 return False
 242             return self.items() == other.items()
 243         return dict.__eq__(self, other)
 244
 245     def __ne__(self, other):
 246         return not self.__eq__(other)
 247
 248     def __cmp__(self, other):
 249         if isinstance(other, odict):
 250             return cmp(self.items(), other.items())
 251         elif isinstance(other, dict):
 252             return dict.__cmp__(self, other)
 253         return NotImplemented
 254
 255     @classmethod
 256     def fromkeys(cls, iterable, default=None):
 257         return cls((key, default) for key in iterable)
 258
 259     def clear(self):
 260         del self._keys[:]
 261         dict.clear(self)
 262
 263     def copy(self):
 264         return self.__class__(self)
 265
 266     def items(self):
 267         return zip(self._keys, self.values())
 268
 269     def iteritems(self):
 270         return izip(self._keys, self.itervalues())
 271
 272     def keys(self):
 273         return self._keys[:]
 274
 275     def iterkeys(self):
 276         return iter(self._keys)
 277
 278     def pop(self, key, default=missing):
 279         if default is missing:
 280             return dict.pop(self, key)
 281         elif key not in self:
 282             return default
 283         self._keys.remove(key)
 284         return dict.pop(self, key, default)
 285
 286     def popitem(self, key):
 287         self._keys.remove(key)
 288         return dict.popitem(key)
 289
 290     def setdefault(self, key, default=None):
 291         if key not in self:
 292             self._keys.append(key)
 293         dict.setdefault(self, key, default)
 294
 295     def update(self, *args, **kwargs):
 296         sources = []
 297         if len(args) == 1:
 298             if hasattr(args[0], 'iteritems'):
 299                 sources.append(args[0].iteritems())
 300             else:
 301                 sources.append(iter(args[0]))
 302         elif args:
 303             raise TypeError('expected at most one positional argument')
 304         if kwargs:
 305             sources.append(kwargs.iteritems())
 306         for iterable in sources:
 307             for key, val in iterable:
 308                 self[key] = val
 309
 310     def values(self):
 311         return map(self.get, self._keys)
 312
 313     def itervalues(self):
 314         return imap(self.get, self._keys)
 315
 316     def index(self, item):
 317         return self._keys.index(item)
 318
 319     def byindex(self, item):
 320         key = self._keys[item]
 321         return (key, dict.__getitem__(self, key))
 322
 323     def reverse(self):
 324         self._keys.reverse()
 325
 326     def sort(self, *args, **kwargs):
 327         self._keys.sort(*args, **kwargs)
 328
 329     def __repr__(self):
 330         return 'odict.odict(%r)' % self.items()
 331
 332     __copy__ = copy
 333     __iter__ = iterkeys
 334
 335
 336 if __name__ == '__main__':
 337     import doctest
 338     doctest.testmod()