1 # -*- coding: utf-8 -*-
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.
14 Why would anyone need ordered dicts?
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.
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.
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.
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.
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.
41 Where are new keys added?
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.
47 What happens if an existing key is reassigned?
49 The key is *not* moved. This is consitent with existing
50 implementations and can be changed by a subclass very easily::
52 class movingodict(odict):
53 def __setitem__(self, key, value):
55 odict.__setitem__(self, key, value)
57 Moving keys to the end of a ordered dict on reassignment is not
58 very useful for most applications.
60 Does it mean the dict keys are sorted by a sort expression?
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.
67 I initializes the odict with a dict literal but the keys are not
68 ordered like they should!
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.
74 What happens if keys appear multiple times in the list passed to the
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:
81 >>> odict([('a', 1), ('b', 2), ('a', 3)])
82 odict.odict([('a', 3), ('b', 2)])
84 This behavor is consistent with existing implementation in Python
85 and the PHP array and the hashmap in Ruby 1.9.
87 This odict doesn't scale!
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.
93 Why is there no .insert()?
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:
100 >>> d = odict([('a', 42), ('b', 23), ('c', 19)])
102 >>> l.insert(1, ('x', 0))
104 odict.odict([('a', 42), ('x', 0), ('b', 23), ('c', 19)])
106 :copyright: (c) 2008 by Armin Ronacher and PEP 273 authors.
107 :license: modified BSD license.
109 from itertools import izip, imap
110 from copy import deepcopy
117 Ordered dict example implementation.
119 This is the proposed interface for a an ordered dict as proposed on the
120 Python mailinglist (proposal_).
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.
126 The constructor and `update()` both accept iterables of tuples as well as
129 >>> d = odict([('a', 'b'), ('c', 'd')])
130 >>> d.update({'foo': 'bar'})
132 odict.odict([('a', 'b'), ('c', 'd'), ('foo', 'bar')])
134 Keep in mind that when updating from dict-literals the order is not
135 preserved as these dicts are unsorted!
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`:
140 >>> from copy import copy, deepcopy
142 odict.odict([('a', 'b'), ('c', 'd'), ('foo', 'bar')])
144 odict.odict([('a', 'b'), ('c', 'd'), ('foo', 'bar')])
146 odict.odict([('a', 'b'), ('c', 'd'), ('foo', 'bar')])
149 >>> d2['spam'].append('eggs')
151 odict.odict([('a', 'b'), ('c', 'd'), ('foo', 'bar'), ('spam', [])])
153 odict.odict([('a', 'b'), ('c', 'd'), ('foo', 'bar'), ('spam', ['eggs'])])
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:
159 ['a', 'c', 'foo', 'spam']
161 ['b', 'd', 'bar', []]
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', [])]
171 Index based lookup is supported too by `byindex` which returns the
172 key/value pair for an index:
177 You can reverse the odict as well:
181 odict.odict([('spam', []), ('foo', 'bar'), ('c', 'd'), ('a', 'b')])
183 And sort it like a list:
185 >>> d.sort(key=lambda x: x[0].lower())
187 odict.odict([('a', 'b'), ('c', 'd'), ('foo', 'bar'), ('spam', [])])
189 .. _proposal: http://thread.gmane.org/gmane.comp.python.devel/95316
190 .. _ordereddict: http://www.xs4all.nl/~anthon/Python/ordereddict/
193 def __init__(self, *args, **kwargs):
196 self.update(*args, **kwargs)
198 def __delitem__(self, key):
199 dict.__delitem__(self, key)
200 self._keys.remove(key)
202 def __setitem__(self, key, item):
204 self._keys.append(key)
205 dict.__setitem__(self, key, item)
207 def __deepcopy__(self, memo=None):
210 d = memo.get(id(self), missing)
213 memo[id(self)] = d = self.__class__()
214 dict.__init__(d, deepcopy(self.items(), memo))
215 d._keys = self._keys[:]
218 def __getstate__(self):
219 return {'items': dict(self), 'keys': self._keys}
221 def __setstate__(self, d):
222 self._keys = d['keys']
223 dict.update(d['items'])
225 def __reversed__(self):
226 return reversed(self._keys)
228 def __eq__(self, other):
229 if isinstance(other, odict):
230 if not dict.__eq__(self, other):
232 return self.items() == other.items()
233 return dict.__eq__(self, other)
235 def __ne__(self, other):
236 return not self.__eq__(other)
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
246 def fromkeys(cls, iterable, default=None):
247 return cls((key, default) for key in iterable)
254 return self.__class__(self)
257 return zip(self._keys, self.values())
260 return izip(self._keys, self.itervalues())
266 return iter(self._keys)
268 def pop(self, key, default=missing):
269 if default is missing:
270 return dict.pop(self, key)
271 elif key not in self:
273 self._keys.remove(key)
274 return dict.pop(self, key, default)
276 def popitem(self, key):
277 self._keys.remove(key)
278 return dict.popitem(key)
280 def setdefault(self, key, default=None):
282 self._keys.append(key)
283 dict.setdefault(self, key, default)
285 def update(self, *args, **kwargs):
288 if hasattr(args[0], 'iteritems'):
289 sources.append(args[0].iteritems())
291 sources.append(iter(args[0]))
293 raise TypeError('expected at most one positional argument')
295 sources.append(kwargs.iteritems())
296 for iterable in sources:
297 for key, val in iterable:
301 return map(self.get, self._keys)
303 def itervalues(self):
304 return imap(self.get, self._keys)
306 def index(self, item):
307 return self._keys.index(item)
309 def byindex(self, item):
310 key = self._keys[item]
311 return (key, dict.__getitem__(self, key))
316 def sort(self, *args, **kwargs):
317 self._keys.sort(*args, **kwargs)
320 return 'odict.odict(%r)' % self.items()
326 if __name__ == '__main__':