1 # http://code.activestate.com/recipes/576693/ (r9)
\r
2 # Created by Raymond Hettinger on Wed, 18 Mar 2009 (MIT)
\r
4 # Backport of OrderedDict() class that runs on Python 2.4, 2.5, 2.6, 2.7
\r
6 # Passes Python2.7's test suite and incorporates all the latest updates.
\r
10 from thread import get_ident as _get_ident
\r
12 from dummy_thread import get_ident as _get_ident
\r
15 from _abcoll import KeysView, ValuesView, ItemsView
\r
20 class OrderedDict(dict):
\r
21 'Dictionary that remembers insertion order'
\r
22 # An inherited dict maps keys to values.
\r
23 # The inherited dict provides __getitem__, __len__, __contains__, and get.
\r
24 # The remaining methods are order-aware.
\r
25 # Big-O running times for all methods are the same as for regular dictionaries.
\r
27 # The internal self.__map dictionary maps keys to links in a doubly linked list.
\r
28 # The circular doubly linked list starts and ends with a sentinel element.
\r
29 # The sentinel element never gets deleted (this simplifies the algorithm).
\r
30 # Each link is stored as a list of length three: [PREV, NEXT, KEY].
\r
32 def __init__(self, *args, **kwds):
\r
33 '''Initialize an ordered dictionary. Signature is the same as for
\r
34 regular dictionaries, but keyword arguments are not recommended
\r
35 because their insertion order is arbitrary.
\r
39 raise TypeError('expected at most 1 arguments, got %d' % len(args))
\r
42 except AttributeError:
\r
43 self.__root = root = [] # sentinel node
\r
44 root[:] = [root, root, None]
\r
46 self.__update(*args, **kwds)
\r
48 def __setitem__(self, key, value, dict_setitem=dict.__setitem__):
\r
49 'od.__setitem__(i, y) <==> od[i]=y'
\r
50 # Setting a new item creates a new link which goes at the end of the linked
\r
51 # list, and the inherited dictionary is updated with the new key/value pair.
\r
55 last[1] = root[0] = self.__map[key] = [last, root, key]
\r
56 dict_setitem(self, key, value)
\r
58 def __delitem__(self, key, dict_delitem=dict.__delitem__):
\r
59 'od.__delitem__(y) <==> del od[y]'
\r
60 # Deleting an existing item uses self.__map to find the link which is
\r
61 # then removed by updating the links in the predecessor and successor nodes.
\r
62 dict_delitem(self, key)
\r
63 link_prev, link_next, key = self.__map.pop(key)
\r
64 link_prev[1] = link_next
\r
65 link_next[0] = link_prev
\r
68 'od.__iter__() <==> iter(od)'
\r
71 while curr is not root:
\r
75 def __reversed__(self):
\r
76 'od.__reversed__() <==> reversed(od)'
\r
79 while curr is not root:
\r
84 'od.clear() -> None. Remove all items from od.'
\r
86 for node in self.__map.itervalues():
\r
89 root[:] = [root, root, None]
\r
91 except AttributeError:
\r
95 def popitem(self, last=True):
\r
96 '''od.popitem() -> (k, v), return and remove a (key, value) pair.
\r
97 Pairs are returned in LIFO order if last is true or FIFO order if false.
\r
101 raise KeyError('dictionary is empty')
\r
105 link_prev = link[0]
\r
106 link_prev[1] = root
\r
107 root[0] = link_prev
\r
110 link_next = link[1]
\r
111 root[1] = link_next
\r
112 link_next[0] = root
\r
114 del self.__map[key]
\r
115 value = dict.pop(self, key)
\r
118 # -- the following methods do not depend on the internal structure --
\r
121 'od.keys() -> list of keys in od'
\r
125 'od.values() -> list of values in od'
\r
126 return [self[key] for key in self]
\r
129 'od.items() -> list of (key, value) pairs in od'
\r
130 return [(key, self[key]) for key in self]
\r
132 def iterkeys(self):
\r
133 'od.iterkeys() -> an iterator over the keys in od'
\r
136 def itervalues(self):
\r
137 'od.itervalues -> an iterator over the values in od'
\r
141 def iteritems(self):
\r
142 'od.iteritems -> an iterator over the (key, value) items in od'
\r
146 def update(*args, **kwds):
\r
147 '''od.update(E, **F) -> None. Update od from dict/iterable E and F.
\r
149 If E is a dict instance, does: for k in E: od[k] = E[k]
\r
150 If E has a .keys() method, does: for k in E.keys(): od[k] = E[k]
\r
151 Or if E is an iterable of items, does: for k, v in E: od[k] = v
\r
152 In either case, this is followed by: for k, v in F.items(): od[k] = v
\r
156 raise TypeError('update() takes at most 2 positional '
\r
157 'arguments (%d given)' % (len(args),))
\r
159 raise TypeError('update() takes at least 1 argument (0 given)')
\r
161 # Make progressively weaker assumptions about "other"
\r
165 if isinstance(other, dict):
\r
167 self[key] = other[key]
\r
168 elif hasattr(other, 'keys'):
\r
169 for key in other.keys():
\r
170 self[key] = other[key]
\r
172 for key, value in other:
\r
174 for key, value in kwds.items():
\r
177 __update = update # let subclasses override update without breaking __init__
\r
179 __marker = object()
\r
181 def pop(self, key, default=__marker):
\r
182 '''od.pop(k[,d]) -> v, remove specified key and return the corresponding value.
\r
183 If key is not found, d is returned if given, otherwise KeyError is raised.
\r
190 if default is self.__marker:
\r
191 raise KeyError(key)
\r
194 def setdefault(self, key, default=None):
\r
195 'od.setdefault(k[,d]) -> od.get(k,d), also set od[k]=d if k not in od'
\r
198 self[key] = default
\r
201 def __repr__(self, _repr_running={}):
\r
202 'od.__repr__() <==> repr(od)'
\r
203 call_key = id(self), _get_ident()
\r
204 if call_key in _repr_running:
\r
206 _repr_running[call_key] = 1
\r
209 return '%s()' % (self.__class__.__name__,)
\r
210 return '%s(%r)' % (self.__class__.__name__, self.items())
\r
212 del _repr_running[call_key]
\r
214 def __reduce__(self):
\r
215 'Return state information for pickling'
\r
216 items = [[k, self[k]] for k in self]
\r
217 inst_dict = vars(self).copy()
\r
218 for k in vars(OrderedDict()):
\r
219 inst_dict.pop(k, None)
\r
221 return (self.__class__, (items,), inst_dict)
\r
222 return self.__class__, (items,)
\r
225 'od.copy() -> a shallow copy of od'
\r
226 return self.__class__(self)
\r
229 def fromkeys(cls, iterable, value=None):
\r
230 '''OD.fromkeys(S[, v]) -> New ordered dictionary with keys from S
\r
231 and values equal to v (which defaults to None).
\r
235 for key in iterable:
\r
239 def __eq__(self, other):
\r
240 '''od.__eq__(y) <==> od==y. Comparison to another OD is order-sensitive
\r
241 while comparison to a regular mapping is order-insensitive.
\r
244 if isinstance(other, OrderedDict):
\r
245 return len(self)==len(other) and self.items() == other.items()
\r
246 return dict.__eq__(self, other)
\r
248 def __ne__(self, other):
\r
249 return not self == other
\r
251 # -- the following methods are only used in Python 2.7 --
\r
253 def viewkeys(self):
\r
254 "od.viewkeys() -> a set-like object providing a view on od's keys"
\r
255 return KeysView(self)
\r
257 def viewvalues(self):
\r
258 "od.viewvalues() -> an object providing a view on od's values"
\r
259 return ValuesView(self)
\r
261 def viewitems(self):
\r
262 "od.viewitems() -> a set-like object providing a view on od's items"
\r
263 return ItemsView(self)
\r