research/TCS/odict.py

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