1 # Unmodified from http://code.activestate.com/recipes/576693/
2 # other than to add MIT license header (as specified on page, but not in code).
3 # Linked from Python documentation here:
4 # http://docs.python.org/2/library/collections.html#collections.OrderedDict
6 # This should be deleted once Py2.7 is available on all bots, see
7 # http://crbug.com/241769.
9 # Copyright (c) 2009 Raymond Hettinger.
11 # Permission is hereby granted, free of charge, to any person obtaining a copy
12 # of this software and associated documentation files (the "Software"), to deal
13 # in the Software without restriction, including without limitation the rights
14 # to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
15 # copies of the Software, and to permit persons to whom the Software is
16 # furnished to do so, subject to the following conditions:
18 # The above copyright notice and this permission notice shall be included in
19 # all copies or substantial portions of the Software.
21 # THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
22 # IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
23 # FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
24 # AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
25 # LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
26 # OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
29 # Backport of OrderedDict() class that runs on Python 2.4, 2.5, 2.6, 2.7 and pypy.
30 # Passes Python2.7's test suite and incorporates all the latest updates.
33 from thread import get_ident as _get_ident
35 from dummy_thread import get_ident as _get_ident
38 from _abcoll import KeysView, ValuesView, ItemsView
43 class OrderedDict(dict):
44 'Dictionary that remembers insertion order'
45 # An inherited dict maps keys to values.
46 # The inherited dict provides __getitem__, __len__, __contains__, and get.
47 # The remaining methods are order-aware.
48 # Big-O running times for all methods are the same as for regular dictionaries.
50 # The internal self.__map dictionary maps keys to links in a doubly linked list.
51 # The circular doubly linked list starts and ends with a sentinel element.
52 # The sentinel element never gets deleted (this simplifies the algorithm).
53 # Each link is stored as a list of length three: [PREV, NEXT, KEY].
55 def __init__(self, *args, **kwds):
56 '''Initialize an ordered dictionary. Signature is the same as for
57 regular dictionaries, but keyword arguments are not recommended
58 because their insertion order is arbitrary.
62 raise TypeError('expected at most 1 arguments, got %d' % len(args))
65 except AttributeError:
66 self.__root = root = [] # sentinel node
67 root[:] = [root, root, None]
69 self.__update(*args, **kwds)
71 def __setitem__(self, key, value, dict_setitem=dict.__setitem__):
72 'od.__setitem__(i, y) <==> od[i]=y'
73 # Setting a new item creates a new link which goes at the end of the linked
74 # list, and the inherited dictionary is updated with the new key/value pair.
78 last[1] = root[0] = self.__map[key] = [last, root, key]
79 dict_setitem(self, key, value)
81 def __delitem__(self, key, dict_delitem=dict.__delitem__):
82 'od.__delitem__(y) <==> del od[y]'
83 # Deleting an existing item uses self.__map to find the link which is
84 # then removed by updating the links in the predecessor and successor nodes.
85 dict_delitem(self, key)
86 link_prev, link_next, key = self.__map.pop(key)
87 link_prev[1] = link_next
88 link_next[0] = link_prev
91 'od.__iter__() <==> iter(od)'
94 while curr is not root:
98 def __reversed__(self):
99 'od.__reversed__() <==> reversed(od)'
102 while curr is not root:
107 'od.clear() -> None. Remove all items from od.'
109 for node in self.__map.itervalues():
112 root[:] = [root, root, None]
114 except AttributeError:
118 def popitem(self, last=True):
119 '''od.popitem() -> (k, v), return and remove a (key, value) pair.
120 Pairs are returned in LIFO order if last is true or FIFO order if false.
124 raise KeyError('dictionary is empty')
138 value = dict.pop(self, key)
141 # -- the following methods do not depend on the internal structure --
144 'od.keys() -> list of keys in od'
148 'od.values() -> list of values in od'
149 return [self[key] for key in self]
152 'od.items() -> list of (key, value) pairs in od'
153 return [(key, self[key]) for key in self]
156 'od.iterkeys() -> an iterator over the keys in od'
159 def itervalues(self):
160 'od.itervalues -> an iterator over the values in od'
165 'od.iteritems -> an iterator over the (key, value) items in od'
169 def update(*args, **kwds):
170 '''od.update(E, **F) -> None. Update od from dict/iterable E and F.
172 If E is a dict instance, does: for k in E: od[k] = E[k]
173 If E has a .keys() method, does: for k in E.keys(): od[k] = E[k]
174 Or if E is an iterable of items, does: for k, v in E: od[k] = v
175 In either case, this is followed by: for k, v in F.items(): od[k] = v
179 raise TypeError('update() takes at most 2 positional '
180 'arguments (%d given)' % (len(args),))
182 raise TypeError('update() takes at least 1 argument (0 given)')
184 # Make progressively weaker assumptions about "other"
188 if isinstance(other, dict):
190 self[key] = other[key]
191 elif hasattr(other, 'keys'):
192 for key in other.keys():
193 self[key] = other[key]
195 for key, value in other:
197 for key, value in kwds.items():
200 __update = update # let subclasses override update without breaking __init__
204 def pop(self, key, default=__marker):
205 '''od.pop(k[,d]) -> v, remove specified key and return the corresponding value.
206 If key is not found, d is returned if given, otherwise KeyError is raised.
213 if default is self.__marker:
217 def setdefault(self, key, default=None):
218 'od.setdefault(k[,d]) -> od.get(k,d), also set od[k]=d if k not in od'
224 def __repr__(self, _repr_running={}):
225 'od.__repr__() <==> repr(od)'
226 call_key = id(self), _get_ident()
227 if call_key in _repr_running:
229 _repr_running[call_key] = 1
232 return '%s()' % (self.__class__.__name__,)
233 return '%s(%r)' % (self.__class__.__name__, self.items())
235 del _repr_running[call_key]
237 def __reduce__(self):
238 'Return state information for pickling'
239 items = [[k, self[k]] for k in self]
240 inst_dict = vars(self).copy()
241 for k in vars(OrderedDict()):
242 inst_dict.pop(k, None)
244 return (self.__class__, (items,), inst_dict)
245 return self.__class__, (items,)
248 'od.copy() -> a shallow copy of od'
249 return self.__class__(self)
252 def fromkeys(cls, iterable, value=None):
253 '''OD.fromkeys(S[, v]) -> New ordered dictionary with keys from S
254 and values equal to v (which defaults to None).
262 def __eq__(self, other):
263 '''od.__eq__(y) <==> od==y. Comparison to another OD is order-sensitive
264 while comparison to a regular mapping is order-insensitive.
267 if isinstance(other, OrderedDict):
268 return len(self)==len(other) and self.items() == other.items()
269 return dict.__eq__(self, other)
271 def __ne__(self, other):
272 return not self == other
274 # -- the following methods are only used in Python 2.7 --
277 "od.viewkeys() -> a set-like object providing a view on od's keys"
278 return KeysView(self)
280 def viewvalues(self):
281 "od.viewvalues() -> an object providing a view on od's values"
282 return ValuesView(self)
285 "od.viewitems() -> a set-like object providing a view on od's items"
286 return ItemsView(self)