1# Backport of OrderedDict() class that runs on Python 2.4, 2.5, 2.6, 2.7 and pypy. 2# Passes Python2.7's test suite and incorporates all the latest updates. 3# Copyright 2009 Raymond Hettinger 4# http://code.activestate.com/recipes/576693/ 5"Ordered dictionary" 6 7try: 8 from thread import get_ident as _get_ident 9except ImportError: 10 from dummy_thread import get_ident as _get_ident 11 12try: 13 from _abcoll import KeysView, ValuesView, ItemsView 14except ImportError: 15 pass 16 17 18class OrderedDict(dict): 19 'Dictionary that remembers insertion order' 20 # An inherited dict maps keys to values. 21 # The inherited dict provides __getitem__, __len__, __contains__, and get. 22 # The remaining methods are order-aware. 23 # Big-O running times for all methods are the same as for regular dictionaries. 24 25 # The internal self.__map dictionary maps keys to links in a doubly linked list. 26 # The circular doubly linked list starts and ends with a sentinel element. 27 # The sentinel element never gets deleted (this simplifies the algorithm). 28 # Each link is stored as a list of length three: [PREV, NEXT, KEY]. 29 30 def __init__(self, *args, **kwds): 31 '''Initialize an ordered dictionary. Signature is the same as for 32 regular dictionaries, but keyword arguments are not recommended 33 because their insertion order is arbitrary. 34 35 ''' 36 if len(args) > 1: 37 raise TypeError('expected at most 1 arguments, got %d' % len(args)) 38 try: 39 self.__root 40 except AttributeError: 41 self.__root = root = [] # sentinel node 42 root[:] = [root, root, None] 43 self.__map = {} 44 self.__update(*args, **kwds) 45 46 def __setitem__(self, key, value, dict_setitem=dict.__setitem__): 47 'od.__setitem__(i, y) <==> od[i]=y' 48 # Setting a new item creates a new link which goes at the end of the linked 49 # list, and the inherited dictionary is updated with the new key/value pair. 50 if key not in self: 51 root = self.__root 52 last = root[0] 53 last[1] = root[0] = self.__map[key] = [last, root, key] 54 dict_setitem(self, key, value) 55 56 def __delitem__(self, key, dict_delitem=dict.__delitem__): 57 'od.__delitem__(y) <==> del od[y]' 58 # Deleting an existing item uses self.__map to find the link which is 59 # then removed by updating the links in the predecessor and successor nodes. 60 dict_delitem(self, key) 61 link_prev, link_next, key = self.__map.pop(key) 62 link_prev[1] = link_next 63 link_next[0] = link_prev 64 65 def __iter__(self): 66 'od.__iter__() <==> iter(od)' 67 root = self.__root 68 curr = root[1] 69 while curr is not root: 70 yield curr[2] 71 curr = curr[1] 72 73 def __reversed__(self): 74 'od.__reversed__() <==> reversed(od)' 75 root = self.__root 76 curr = root[0] 77 while curr is not root: 78 yield curr[2] 79 curr = curr[0] 80 81 def clear(self): 82 'od.clear() -> None. Remove all items from od.' 83 try: 84 for node in self.__map.itervalues(): 85 del node[:] 86 root = self.__root 87 root[:] = [root, root, None] 88 self.__map.clear() 89 except AttributeError: 90 pass 91 dict.clear(self) 92 93 def popitem(self, last=True): 94 '''od.popitem() -> (k, v), return and remove a (key, value) pair. 95 Pairs are returned in LIFO order if last is true or FIFO order if false. 96 97 ''' 98 if not self: 99 raise KeyError('dictionary is empty') 100 root = self.__root 101 if last: 102 link = root[0] 103 link_prev = link[0] 104 link_prev[1] = root 105 root[0] = link_prev 106 else: 107 link = root[1] 108 link_next = link[1] 109 root[1] = link_next 110 link_next[0] = root 111 key = link[2] 112 del self.__map[key] 113 value = dict.pop(self, key) 114 return key, value 115 116 # -- the following methods do not depend on the internal structure -- 117 118 def keys(self): 119 'od.keys() -> list of keys in od' 120 return list(self) 121 122 def values(self): 123 'od.values() -> list of values in od' 124 return [self[key] for key in self] 125 126 def items(self): 127 'od.items() -> list of (key, value) pairs in od' 128 return [(key, self[key]) for key in self] 129 130 def iterkeys(self): 131 'od.iterkeys() -> an iterator over the keys in od' 132 return iter(self) 133 134 def itervalues(self): 135 'od.itervalues -> an iterator over the values in od' 136 for k in self: 137 yield self[k] 138 139 def iteritems(self): 140 'od.iteritems -> an iterator over the (key, value) items in od' 141 for k in self: 142 yield (k, self[k]) 143 144 def update(*args, **kwds): 145 '''od.update(E, **F) -> None. Update od from dict/iterable E and F. 146 147 If E is a dict instance, does: for k in E: od[k] = E[k] 148 If E has a .keys() method, does: for k in E.keys(): od[k] = E[k] 149 Or if E is an iterable of items, does: for k, v in E: od[k] = v 150 In either case, this is followed by: for k, v in F.items(): od[k] = v 151 152 ''' 153 if len(args) > 2: 154 raise TypeError('update() takes at most 2 positional ' 155 'arguments (%d given)' % (len(args),)) 156 elif not args: 157 raise TypeError('update() takes at least 1 argument (0 given)') 158 self = args[0] 159 # Make progressively weaker assumptions about "other" 160 other = () 161 if len(args) == 2: 162 other = args[1] 163 if isinstance(other, dict): 164 for key in other: 165 self[key] = other[key] 166 elif hasattr(other, 'keys'): 167 for key in other.keys(): 168 self[key] = other[key] 169 else: 170 for key, value in other: 171 self[key] = value 172 for key, value in kwds.items(): 173 self[key] = value 174 175 __update = update # let subclasses override update without breaking __init__ 176 177 __marker = object() 178 179 def pop(self, key, default=__marker): 180 '''od.pop(k[,d]) -> v, remove specified key and return the corresponding value. 181 If key is not found, d is returned if given, otherwise KeyError is raised. 182 183 ''' 184 if key in self: 185 result = self[key] 186 del self[key] 187 return result 188 if default is self.__marker: 189 raise KeyError(key) 190 return default 191 192 def setdefault(self, key, default=None): 193 'od.setdefault(k[,d]) -> od.get(k,d), also set od[k]=d if k not in od' 194 if key in self: 195 return self[key] 196 self[key] = default 197 return default 198 199 def __repr__(self, _repr_running={}): 200 'od.__repr__() <==> repr(od)' 201 call_key = id(self), _get_ident() 202 if call_key in _repr_running: 203 return '...' 204 _repr_running[call_key] = 1 205 try: 206 if not self: 207 return '%s()' % (self.__class__.__name__,) 208 return '%s(%r)' % (self.__class__.__name__, self.items()) 209 finally: 210 del _repr_running[call_key] 211 212 def __reduce__(self): 213 'Return state information for pickling' 214 items = [[k, self[k]] for k in self] 215 inst_dict = vars(self).copy() 216 for k in vars(OrderedDict()): 217 inst_dict.pop(k, None) 218 if inst_dict: 219 return (self.__class__, (items,), inst_dict) 220 return self.__class__, (items,) 221 222 def copy(self): 223 'od.copy() -> a shallow copy of od' 224 return self.__class__(self) 225 226 @classmethod 227 def fromkeys(cls, iterable, value=None): 228 '''OD.fromkeys(S[, v]) -> New ordered dictionary with keys from S 229 and values equal to v (which defaults to None). 230 231 ''' 232 d = cls() 233 for key in iterable: 234 d[key] = value 235 return d 236 237 def __eq__(self, other): 238 '''od.__eq__(y) <==> od==y. Comparison to another OD is order-sensitive 239 while comparison to a regular mapping is order-insensitive. 240 241 ''' 242 if isinstance(other, OrderedDict): 243 return len(self)==len(other) and self.items() == other.items() 244 return dict.__eq__(self, other) 245 246 def __ne__(self, other): 247 return not self == other 248 249 # -- the following methods are only used in Python 2.7 -- 250 251 def viewkeys(self): 252 "od.viewkeys() -> a set-like object providing a view on od's keys" 253 return KeysView(self) 254 255 def viewvalues(self): 256 "od.viewvalues() -> an object providing a view on od's values" 257 return ValuesView(self) 258 259 def viewitems(self): 260 "od.viewitems() -> a set-like object providing a view on od's items" 261 return ItemsView(self) 262