OLD | NEW |
(Empty) | |
| 1 # Unmodified from http://code.activestate.com/recipes/576693/ |
| 2 # Linked from Python documentation here: |
| 3 # http://docs.python.org/2/library/collections.html#collections.OrderedDict |
| 4 # |
| 5 # This should be deleted once Py2.7 is available on all bots, see |
| 6 # http://crbug.com/241769. |
| 7 |
| 8 # Backport of OrderedDict() class that runs on Python 2.4, 2.5, 2.6, 2.7 and pyp
y. |
| 9 # Passes Python2.7's test suite and incorporates all the latest updates. |
| 10 |
| 11 try: |
| 12 from thread import get_ident as _get_ident |
| 13 except ImportError: |
| 14 from dummy_thread import get_ident as _get_ident |
| 15 |
| 16 try: |
| 17 from _abcoll import KeysView, ValuesView, ItemsView |
| 18 except ImportError: |
| 19 pass |
| 20 |
| 21 |
| 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 dictionari
es. |
| 28 |
| 29 # The internal self.__map dictionary maps keys to links in a doubly linked l
ist. |
| 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]. |
| 33 |
| 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. |
| 38 |
| 39 ''' |
| 40 if len(args) > 1: |
| 41 raise TypeError('expected at most 1 arguments, got %d' % len(args)) |
| 42 try: |
| 43 self.__root |
| 44 except AttributeError: |
| 45 self.__root = root = [] # sentinel node |
| 46 root[:] = [root, root, None] |
| 47 self.__map = {} |
| 48 self.__update(*args, **kwds) |
| 49 |
| 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 lin
ked |
| 53 # list, and the inherited dictionary is updated with the new key/value p
air. |
| 54 if key not in self: |
| 55 root = self.__root |
| 56 last = root[0] |
| 57 last[1] = root[0] = self.__map[key] = [last, root, key] |
| 58 dict_setitem(self, key, value) |
| 59 |
| 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 no
des. |
| 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 |
| 68 |
| 69 def __iter__(self): |
| 70 'od.__iter__() <==> iter(od)' |
| 71 root = self.__root |
| 72 curr = root[1] |
| 73 while curr is not root: |
| 74 yield curr[2] |
| 75 curr = curr[1] |
| 76 |
| 77 def __reversed__(self): |
| 78 'od.__reversed__() <==> reversed(od)' |
| 79 root = self.__root |
| 80 curr = root[0] |
| 81 while curr is not root: |
| 82 yield curr[2] |
| 83 curr = curr[0] |
| 84 |
| 85 def clear(self): |
| 86 'od.clear() -> None. Remove all items from od.' |
| 87 try: |
| 88 for node in self.__map.itervalues(): |
| 89 del node[:] |
| 90 root = self.__root |
| 91 root[:] = [root, root, None] |
| 92 self.__map.clear() |
| 93 except AttributeError: |
| 94 pass |
| 95 dict.clear(self) |
| 96 |
| 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. |
| 100 |
| 101 ''' |
| 102 if not self: |
| 103 raise KeyError('dictionary is empty') |
| 104 root = self.__root |
| 105 if last: |
| 106 link = root[0] |
| 107 link_prev = link[0] |
| 108 link_prev[1] = root |
| 109 root[0] = link_prev |
| 110 else: |
| 111 link = root[1] |
| 112 link_next = link[1] |
| 113 root[1] = link_next |
| 114 link_next[0] = root |
| 115 key = link[2] |
| 116 del self.__map[key] |
| 117 value = dict.pop(self, key) |
| 118 return key, value |
| 119 |
| 120 # -- the following methods do not depend on the internal structure -- |
| 121 |
| 122 def keys(self): |
| 123 'od.keys() -> list of keys in od' |
| 124 return list(self) |
| 125 |
| 126 def values(self): |
| 127 'od.values() -> list of values in od' |
| 128 return [self[key] for key in self] |
| 129 |
| 130 def items(self): |
| 131 'od.items() -> list of (key, value) pairs in od' |
| 132 return [(key, self[key]) for key in self] |
| 133 |
| 134 def iterkeys(self): |
| 135 'od.iterkeys() -> an iterator over the keys in od' |
| 136 return iter(self) |
| 137 |
| 138 def itervalues(self): |
| 139 'od.itervalues -> an iterator over the values in od' |
| 140 for k in self: |
| 141 yield self[k] |
| 142 |
| 143 def iteritems(self): |
| 144 'od.iteritems -> an iterator over the (key, value) items in od' |
| 145 for k in self: |
| 146 yield (k, self[k]) |
| 147 |
| 148 def update(*args, **kwds): |
| 149 '''od.update(E, **F) -> None. Update od from dict/iterable E and F. |
| 150 |
| 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 |
| 155 |
| 156 ''' |
| 157 if len(args) > 2: |
| 158 raise TypeError('update() takes at most 2 positional ' |
| 159 'arguments (%d given)' % (len(args),)) |
| 160 elif not args: |
| 161 raise TypeError('update() takes at least 1 argument (0 given)') |
| 162 self = args[0] |
| 163 # Make progressively weaker assumptions about "other" |
| 164 other = () |
| 165 if len(args) == 2: |
| 166 other = args[1] |
| 167 if isinstance(other, dict): |
| 168 for key in other: |
| 169 self[key] = other[key] |
| 170 elif hasattr(other, 'keys'): |
| 171 for key in other.keys(): |
| 172 self[key] = other[key] |
| 173 else: |
| 174 for key, value in other: |
| 175 self[key] = value |
| 176 for key, value in kwds.items(): |
| 177 self[key] = value |
| 178 |
| 179 __update = update # let subclasses override update without breaking __init_
_ |
| 180 |
| 181 __marker = object() |
| 182 |
| 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 raise
d. |
| 186 |
| 187 ''' |
| 188 if key in self: |
| 189 result = self[key] |
| 190 del self[key] |
| 191 return result |
| 192 if default is self.__marker: |
| 193 raise KeyError(key) |
| 194 return default |
| 195 |
| 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' |
| 198 if key in self: |
| 199 return self[key] |
| 200 self[key] = default |
| 201 return default |
| 202 |
| 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: |
| 207 return '...' |
| 208 _repr_running[call_key] = 1 |
| 209 try: |
| 210 if not self: |
| 211 return '%s()' % (self.__class__.__name__,) |
| 212 return '%s(%r)' % (self.__class__.__name__, self.items()) |
| 213 finally: |
| 214 del _repr_running[call_key] |
| 215 |
| 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) |
| 222 if inst_dict: |
| 223 return (self.__class__, (items,), inst_dict) |
| 224 return self.__class__, (items,) |
| 225 |
| 226 def copy(self): |
| 227 'od.copy() -> a shallow copy of od' |
| 228 return self.__class__(self) |
| 229 |
| 230 @classmethod |
| 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). |
| 234 |
| 235 ''' |
| 236 d = cls() |
| 237 for key in iterable: |
| 238 d[key] = value |
| 239 return d |
| 240 |
| 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. |
| 244 |
| 245 ''' |
| 246 if isinstance(other, OrderedDict): |
| 247 return len(self)==len(other) and self.items() == other.items() |
| 248 return dict.__eq__(self, other) |
| 249 |
| 250 def __ne__(self, other): |
| 251 return not self == other |
| 252 |
| 253 # -- the following methods are only used in Python 2.7 -- |
| 254 |
| 255 def viewkeys(self): |
| 256 "od.viewkeys() -> a set-like object providing a view on od's keys" |
| 257 return KeysView(self) |
| 258 |
| 259 def viewvalues(self): |
| 260 "od.viewvalues() -> an object providing a view on od's values" |
| 261 return ValuesView(self) |
| 262 |
| 263 def viewitems(self): |
| 264 "od.viewitems() -> a set-like object providing a view on od's items" |
| 265 return ItemsView(self) |
| 266 |
OLD | NEW |