1 """Backport of OrderedDict() class
3 Runs on Python 2.4, 2.5, 2.6, 2.7, 3.x and pypy.
5 Passes Python2.7's test suite and incorporates all the latest updates.
6 Copyright 2009 Raymond Hettinger, released under the MIT License.
7 http://code.activestate.com/recipes/576693/
10 from __future__
import absolute_import
, division
, unicode_literals
12 # Python2's "thread" module must be tried first
13 from thread
import get_ident
as _get_ident
15 # Python2 also contains a "threading" module, but it does not
16 # contain get_ident(), so this part would fail if it were done first.
17 # get_ident() become available in the consolidated "threading" module
19 from threading
import get_ident
as _get_ident
22 class OrderedDict(dict):
23 'Dictionary that remembers insertion order'
24 # An inherited dict maps keys to values.
25 # The inherited dict provides __getitem__, __len__, __contains__, and get.
26 # The remaining methods are order-aware.
27 # Big-O running times for all methods are the same as for regular dictionaries.
29 # The internal self.__map dictionary maps keys to links in a doubly linked list.
30 # The circular doubly linked list starts and ends with a sentinel element.
31 # The sentinel element never gets deleted (this simplifies the algorithm).
32 # Each link is stored as a list of length three: [PREV, NEXT, KEY].
34 def __init__(self
, *args
, **kwds
):
35 '''Initialize an ordered dictionary. Signature is the same as for
36 regular dictionaries, but keyword arguments are not recommended
37 because their insertion order is arbitrary.
41 raise TypeError('expected at most 1 arguments, got %d' % len(args
))
44 except AttributeError:
45 self
.__root
= root
= [] # sentinel node
46 root
[:] = [root
, root
, None]
48 self
.__update
(*args
, **kwds
)
50 def __setitem__(self
, key
, value
, dict_setitem
=dict.__setitem
__):
51 'od.__setitem__(i, y) <==> od[i]=y'
52 # Setting a new item creates a new link which goes at the end of the linked
53 # list, and the inherited dictionary is updated with the new key/value pair.
57 last
[1] = root
[0] = self
.__map
[key
] = [last
, root
, key
]
58 dict_setitem(self
, key
, value
)
60 def __delitem__(self
, key
, dict_delitem
=dict.__delitem
__):
61 'od.__delitem__(y) <==> del od[y]'
62 # Deleting an existing item uses self.__map to find the link which is
63 # then removed by updating the links in the predecessor and successor nodes.
64 dict_delitem(self
, key
)
65 link_prev
, link_next
, key
= self
.__map
.pop(key
)
66 link_prev
[1] = link_next
67 link_next
[0] = link_prev
70 'od.__iter__() <==> iter(od)'
73 while curr
is not root
:
77 def __reversed__(self
):
78 'od.__reversed__() <==> reversed(od)'
81 while curr
is not root
:
86 'od.clear() -> None. Remove all items from od.'
88 for node
in self
.__map
.values():
91 root
[:] = [root
, root
, None]
93 except AttributeError:
97 def popitem(self
, last
=True):
98 '''od.popitem() -> (k, v), return and remove a (key, value) pair.
99 Pairs are returned in LIFO order if last is true or FIFO order if false.
103 raise KeyError('dictionary is empty')
117 value
= dict.pop(self
, key
)
120 # -- the following methods do not depend on the internal structure --
123 'od.keys() -> list of keys in od'
127 'od.values() -> list of values in od'
128 return [self
[key
] for key
in self
]
131 'od.items() -> list of (key, value) pairs in od'
132 return [(key
, self
[key
]) for key
in self
]
135 'od.iterkeys() -> an iterator over the keys in od'
138 def itervalues(self
):
139 'od.itervalues -> an iterator over the values in od'
144 'od.iteritems -> an iterator over the (key, value) items in od'
148 def update(*args
, **kwds
):
149 '''od.update(E, **F) -> None. Update od from dict/iterable E and F.
151 If E is a dict instance, does: for k in E: od[k] = E[k]
152 If E has a .keys() method, does: for k in E.keys(): od[k] = E[k]
153 Or if E is an iterable of items, does: for k, v in E: od[k] = v
154 In either case, this is followed by: for k, v in F.items(): od[k] = v
158 raise TypeError('update() takes at most 2 positional '
159 'arguments (%d given)' % (len(args
),))
161 raise TypeError('update() takes at least 1 argument (0 given)')
163 # Make progressively weaker assumptions about "other"
167 if isinstance(other
, dict):
169 self
[key
] = other
[key
]
170 elif hasattr(other
, 'keys'):
171 for key
in other
.keys():
172 self
[key
] = other
[key
]
174 for key
, value
in other
:
176 for key
, value
in kwds
.items():
179 __update
= update
# let subclasses override update without breaking __init__
183 def pop(self
, key
, default
=__marker
):
184 '''od.pop(k[,d]) -> v, remove specified key and return the corresponding value.
185 If key is not found, d is returned if given, otherwise KeyError is raised.
192 if default
is self
.__marker
:
196 def setdefault(self
, key
, default
=None):
197 'od.setdefault(k[,d]) -> od.get(k,d), also set od[k]=d if k not in od'
203 def __repr__(self
, _repr_running
={}):
204 'od.__repr__() <==> repr(od)'
205 call_key
= id(self
), _get_ident()
206 if call_key
in _repr_running
:
208 _repr_running
[call_key
] = 1
211 return '%s()' % (self
.__class
__.__name
__,)
212 return '%s(%r)' % (self
.__class
__.__name
__, self
.items())
214 del _repr_running
[call_key
]
216 def __reduce__(self
):
217 'Return state information for pickling'
218 items
= [[k
, self
[k
]] for k
in self
]
219 inst_dict
= vars(self
).copy()
220 for k
in vars(OrderedDict()):
221 inst_dict
.pop(k
, None)
223 return (self
.__class
__, (items
,), inst_dict
)
224 return self
.__class
__, (items
,)
227 'od.copy() -> a shallow copy of od'
228 return self
.__class
__(self
)
231 def fromkeys(cls
, iterable
, value
=None):
232 '''OD.fromkeys(S[, v]) -> New ordered dictionary with keys from S
233 and values equal to v (which defaults to None).
241 def __eq__(self
, other
):
242 '''od.__eq__(y) <==> od==y. Comparison to another OD is order-sensitive
243 while comparison to a regular mapping is order-insensitive.
246 if isinstance(other
, OrderedDict
):
247 return len(self
)==len(other
) and self
.items() == other
.items()
248 return dict.__eq
__(self
, other
)
250 def __ne__(self
, other
):
251 return not self
== other