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 5# 6# This should be deleted once Py2.7 is available on all bots, see 7# http://crbug.com/241769. 8# 9# Copyright (c) 2009 Raymond Hettinger. 10# 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: 17# 18# The above copyright notice and this permission notice shall be included in 19# all copies or substantial portions of the Software. 20# 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 27# THE SOFTWARE. 28 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. 31 32try: 33 from thread import get_ident as _get_ident 34except ImportError: 35 from dummy_thread import get_ident as _get_ident 36 37try: 38 from _abcoll import KeysView, ValuesView, ItemsView 39except ImportError: 40 pass 41 42 43class 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. 49 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]. 54 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. 59 60 ''' 61 if len(args) > 1: 62 raise TypeError('expected at most 1 arguments, got %d' % len(args)) 63 try: 64 self.__root 65 except AttributeError: 66 self.__root = root = [] # sentinel node 67 root[:] = [root, root, None] 68 self.__map = {} 69 self.__update(*args, **kwds) 70 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. 75 if key not in self: 76 root = self.__root 77 last = root[0] 78 last[1] = root[0] = self.__map[key] = [last, root, key] 79 dict_setitem(self, key, value) 80 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 89 90 def __iter__(self): 91 'od.__iter__() <==> iter(od)' 92 root = self.__root 93 curr = root[1] 94 while curr is not root: 95 yield curr[2] 96 curr = curr[1] 97 98 def __reversed__(self): 99 'od.__reversed__() <==> reversed(od)' 100 root = self.__root 101 curr = root[0] 102 while curr is not root: 103 yield curr[2] 104 curr = curr[0] 105 106 def clear(self): 107 'od.clear() -> None. Remove all items from od.' 108 try: 109 for node in self.__map.itervalues(): 110 del node[:] 111 root = self.__root 112 root[:] = [root, root, None] 113 self.__map.clear() 114 except AttributeError: 115 pass 116 dict.clear(self) 117 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. 121 122 ''' 123 if not self: 124 raise KeyError('dictionary is empty') 125 root = self.__root 126 if last: 127 link = root[0] 128 link_prev = link[0] 129 link_prev[1] = root 130 root[0] = link_prev 131 else: 132 link = root[1] 133 link_next = link[1] 134 root[1] = link_next 135 link_next[0] = root 136 key = link[2] 137 del self.__map[key] 138 value = dict.pop(self, key) 139 return key, value 140 141 # -- the following methods do not depend on the internal structure -- 142 143 def keys(self): 144 'od.keys() -> list of keys in od' 145 return list(self) 146 147 def values(self): 148 'od.values() -> list of values in od' 149 return [self[key] for key in self] 150 151 def items(self): 152 'od.items() -> list of (key, value) pairs in od' 153 return [(key, self[key]) for key in self] 154 155 def iterkeys(self): 156 'od.iterkeys() -> an iterator over the keys in od' 157 return iter(self) 158 159 def itervalues(self): 160 'od.itervalues -> an iterator over the values in od' 161 for k in self: 162 yield self[k] 163 164 def iteritems(self): 165 'od.iteritems -> an iterator over the (key, value) items in od' 166 for k in self: 167 yield (k, self[k]) 168 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. 173 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 178 179 ''' 180 if len(args) > 2: 181 raise TypeError('update() takes at most 2 positional ' 182 'arguments (%d given)' % (len(args),)) 183 elif not args: 184 raise TypeError('update() takes at least 1 argument (0 given)') 185 self = args[0] 186 # Make progressively weaker assumptions about "other" 187 other = () 188 if len(args) == 2: 189 other = args[1] 190 if isinstance(other, dict): 191 for key in other: 192 self[key] = other[key] 193 elif hasattr(other, 'keys'): 194 for key in other.keys(): 195 self[key] = other[key] 196 else: 197 for key, value in other: 198 self[key] = value 199 for key, value in kwds.items(): 200 self[key] = value 201 202 __update = update # let subclasses override update without breaking __init__ 203 204 __marker = object() 205 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. 209 210 ''' 211 if key in self: 212 result = self[key] 213 del self[key] 214 return result 215 if default is self.__marker: 216 raise KeyError(key) 217 return default 218 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' 221 if key in self: 222 return self[key] 223 self[key] = default 224 return default 225 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: 230 return '...' 231 _repr_running[call_key] = 1 232 try: 233 if not self: 234 return '%s()' % (self.__class__.__name__,) 235 return '%s(%r)' % (self.__class__.__name__, self.items()) 236 finally: 237 del _repr_running[call_key] 238 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) 245 if inst_dict: 246 return (self.__class__, (items,), inst_dict) 247 return self.__class__, (items,) 248 249 def copy(self): 250 'od.copy() -> a shallow copy of od' 251 return self.__class__(self) 252 253 @classmethod 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). 257 258 ''' 259 d = cls() 260 for key in iterable: 261 d[key] = value 262 return d 263 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. 267 268 ''' 269 if isinstance(other, OrderedDict): 270 return len(self)==len(other) and self.items() == other.items() 271 return dict.__eq__(self, other) 272 273 def __ne__(self, other): 274 return not self == other 275 276 # -- the following methods are only used in Python 2.7 -- 277 278 def viewkeys(self): 279 "od.viewkeys() -> a set-like object providing a view on od's keys" 280 return KeysView(self) 281 282 def viewvalues(self): 283 "od.viewvalues() -> an object providing a view on od's values" 284 return ValuesView(self) 285 286 def viewitems(self): 287 "od.viewitems() -> a set-like object providing a view on od's items" 288 return ItemsView(self) 289 290