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