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 # Suppress 'OrderedDict.update: Method has no argument':
170 # pylint: disable=E0211
171 def update(*args, **kwds):
172 '''od.update(E, **F) -> None. Update od from dict/iterable E and F.
174 If E is a dict instance, does: for k in E: od[k] = E[k]
175 If E has a .keys() method, does: for k in E.keys(): od[k] = E[k]
176 Or if E is an iterable of items, does: for k, v in E: od[k] = v
177 In either case, this is followed by: for k, v in F.items(): od[k] = v
181 raise TypeError('update() takes at most 2 positional '
182 'arguments (%d given)' % (len(args),))
184 raise TypeError('update() takes at least 1 argument (0 given)')
186 # Make progressively weaker assumptions about "other"
190 if isinstance(other, dict):
192 self[key] = other[key]
193 elif hasattr(other, 'keys'):
194 for key in other.keys():
195 self[key] = other[key]
197 for key, value in other:
199 for key, value in kwds.items():
202 __update = update # let subclasses override update without breaking __init__
206 def pop(self, key, default=__marker):
207 '''od.pop(k[,d]) -> v, remove specified key and return the corresponding value.
208 If key is not found, d is returned if given, otherwise KeyError is raised.
215 if default is self.__marker:
219 def setdefault(self, key, default=None):
220 'od.setdefault(k[,d]) -> od.get(k,d), also set od[k]=d if k not in od'
226 def __repr__(self, _repr_running={}):
227 'od.__repr__() <==> repr(od)'
228 call_key = id(self), _get_ident()
229 if call_key in _repr_running:
231 _repr_running[call_key] = 1
234 return '%s()' % (self.__class__.__name__,)
235 return '%s(%r)' % (self.__class__.__name__, self.items())
237 del _repr_running[call_key]
239 def __reduce__(self):
240 'Return state information for pickling'
241 items = [[k, self[k]] for k in self]
242 inst_dict = vars(self).copy()
243 for k in vars(OrderedDict()):
244 inst_dict.pop(k, None)
246 return (self.__class__, (items,), inst_dict)
247 return self.__class__, (items,)
250 'od.copy() -> a shallow copy of od'
251 return self.__class__(self)
254 def fromkeys(cls, iterable, value=None):
255 '''OD.fromkeys(S[, v]) -> New ordered dictionary with keys from S
256 and values equal to v (which defaults to None).
264 def __eq__(self, other):
265 '''od.__eq__(y) <==> od==y. Comparison to another OD is order-sensitive
266 while comparison to a regular mapping is order-insensitive.
269 if isinstance(other, OrderedDict):
270 return len(self)==len(other) and self.items() == other.items()
271 return dict.__eq__(self, other)
273 def __ne__(self, other):
274 return not self == other
276 # -- the following methods are only used in Python 2.7 --
279 "od.viewkeys() -> a set-like object providing a view on od's keys"
280 return KeysView(self)
282 def viewvalues(self):
283 "od.viewvalues() -> an object providing a view on od's values"
284 return ValuesView(self)
287 "od.viewitems() -> a set-like object providing a view on od's items"
288 return ItemsView(self)