| 1 | #!/usr/bin/env python2
|
| 2 | """
|
| 3 | collections.py
|
| 4 |
|
| 5 | To avoid other dependencies. Copied OrderedDict from collections.py, and
|
| 6 | MutableMapping from _abcoll.
|
| 7 | """
|
| 8 |
|
| 9 | from typing import Any
|
| 10 |
|
| 11 |
|
| 12 | class OrderedDict(dict):
|
| 13 | 'Dictionary that remembers insertion order'
|
| 14 | # An inherited dict maps keys to values.
|
| 15 | # The inherited dict provides __getitem__, __len__, __contains__, and get.
|
| 16 | # The remaining methods are order-aware.
|
| 17 | # Big-O running times for all methods are the same as regular dictionaries.
|
| 18 |
|
| 19 | # The internal self.__map dict maps keys to links in a doubly linked list.
|
| 20 | # The circular doubly linked list starts and ends with a sentinel element.
|
| 21 | # The sentinel element never gets deleted (this simplifies the algorithm).
|
| 22 | # Each link is stored as a list of length three: [PREV, NEXT, KEY].
|
| 23 |
|
| 24 | def __init__(*args, **kwds):
|
| 25 | # type: (Any, Any) -> None
|
| 26 | '''Initialize an ordered dictionary. The signature is the same as
|
| 27 | regular dictionaries, but keyword arguments are not recommended because
|
| 28 | their insertion order is arbitrary.
|
| 29 |
|
| 30 | '''
|
| 31 |
|
| 32 | if not args:
|
| 33 | raise TypeError("descriptor '__init__' of 'OrderedDict' object "
|
| 34 | "needs an argument")
|
| 35 | self = args[0]
|
| 36 | args = args[1:]
|
| 37 | if len(args) > 1:
|
| 38 | raise TypeError('expected at most 1 arguments, got %d' % len(args))
|
| 39 | try:
|
| 40 | self.__root
|
| 41 | except AttributeError:
|
| 42 | self.__root = root = [] # sentinel node
|
| 43 | root[:] = [root, root, None]
|
| 44 | self.__map = {}
|
| 45 |
|
| 46 | # Oil patch
|
| 47 | #self.__update(*args, **kwds)
|
| 48 | if args:
|
| 49 | raise AssertionError(args)
|
| 50 | if kwds:
|
| 51 | raise AssertionError(kwds)
|
| 52 |
|
| 53 | def __setitem__(self, key, value, dict_setitem=dict.__setitem__):
|
| 54 | 'od.__setitem__(i, y) <==> od[i]=y'
|
| 55 | # Setting a new item creates a new link at the end of the linked list,
|
| 56 | # and the inherited dictionary is updated with the new key/value pair.
|
| 57 | if key not in self:
|
| 58 | root = self.__root
|
| 59 | last = root[0]
|
| 60 | last[1] = root[0] = self.__map[key] = [last, root, key]
|
| 61 | return dict_setitem(self, key, value)
|
| 62 |
|
| 63 | def __delitem__(self, key, dict_delitem=dict.__delitem__):
|
| 64 | 'od.__delitem__(y) <==> del od[y]'
|
| 65 | # Deleting an existing item uses self.__map to find the link which gets
|
| 66 | # removed by updating the links in the predecessor and successor nodes.
|
| 67 | dict_delitem(self, key)
|
| 68 | link_prev, link_next, _ = self.__map.pop(key)
|
| 69 | link_prev[1] = link_next # update link_prev[NEXT]
|
| 70 | link_next[0] = link_prev # update link_next[PREV]
|
| 71 |
|
| 72 | def __iter__(self):
|
| 73 | 'od.__iter__() <==> iter(od)'
|
| 74 | # Traverse the linked list in order.
|
| 75 | root = self.__root
|
| 76 | curr = root[1] # start at the first node
|
| 77 | while curr is not root:
|
| 78 | yield curr[2] # yield the curr[KEY]
|
| 79 | curr = curr[1] # move to next node
|
| 80 |
|
| 81 | def __reversed__(self):
|
| 82 | 'od.__reversed__() <==> reversed(od)'
|
| 83 | # Traverse the linked list in reverse order.
|
| 84 | root = self.__root
|
| 85 | curr = root[0] # start at the last node
|
| 86 | while curr is not root:
|
| 87 | yield curr[2] # yield the curr[KEY]
|
| 88 | curr = curr[0] # move to previous node
|
| 89 |
|
| 90 | def clear(self):
|
| 91 | 'od.clear() -> None. Remove all items from od.'
|
| 92 | root = self.__root
|
| 93 | root[:] = [root, root, None]
|
| 94 | self.__map.clear()
|
| 95 | dict.clear(self)
|
| 96 |
|
| 97 | # -- the following methods do not depend on the internal structure --
|
| 98 |
|
| 99 | def keys(self):
|
| 100 | 'od.keys() -> list of keys in od'
|
| 101 | return list(self)
|
| 102 |
|
| 103 | def values(self):
|
| 104 | 'od.values() -> list of values in od'
|
| 105 | return [self[key] for key in self]
|
| 106 |
|
| 107 | def items(self):
|
| 108 | 'od.items() -> list of (key, value) pairs in od'
|
| 109 | return [(key, self[key]) for key in self]
|
| 110 |
|
| 111 | def iterkeys(self):
|
| 112 | 'od.iterkeys() -> an iterator over the keys in od'
|
| 113 | # PATCH: not used in Oil
|
| 114 | raise AssertionError()
|
| 115 |
|
| 116 | def itervalues(self):
|
| 117 | 'od.itervalues -> an iterator over the values in od'
|
| 118 | # PATCH: not used in Oil
|
| 119 | raise AssertionError()
|
| 120 |
|
| 121 | def iteritems(self):
|
| 122 | 'od.iteritems -> an iterator over the (key, value) pairs in od'
|
| 123 | for k in self:
|
| 124 | yield (k, self[k])
|
| 125 |
|
| 126 | # Oils patch: commented out
|
| 127 | if 0:
|
| 128 | update = MutableMapping.update
|
| 129 |
|
| 130 | __update = update # let subclasses override update without breaking __init__
|
| 131 |
|
| 132 | # Oils patch:
|
| 133 | def update(self, other):
|
| 134 | for k, v in other.iteritems():
|
| 135 | self[k] = v
|
| 136 |
|
| 137 | __marker = object()
|
| 138 |
|
| 139 | def pop(self, key, default=__marker):
|
| 140 | '''od.pop(k[,d]) -> v, remove specified key and return the corresponding
|
| 141 | value. If key is not found, d is returned if given, otherwise KeyError
|
| 142 | is raised.
|
| 143 |
|
| 144 | '''
|
| 145 | if key in self:
|
| 146 | result = self[key]
|
| 147 | del self[key]
|
| 148 | return result
|
| 149 | if default is self.__marker:
|
| 150 | raise KeyError(key)
|
| 151 | return default
|
| 152 |
|
| 153 | def setdefault(self, key, default=None):
|
| 154 | 'od.setdefault(k[,d]) -> od.get(k,d), also set od[k]=d if k not in od'
|
| 155 | # PATCH: not used in Oil
|
| 156 | raise AssertionError()
|
| 157 |
|
| 158 | def popitem(self, last=True):
|
| 159 | '''od.popitem() -> (k, v), return and remove a (key, value) pair.
|
| 160 | Pairs are returned in LIFO order if last is true or FIFO order if false.
|
| 161 |
|
| 162 | '''
|
| 163 | # PATCH: not used in Oil
|
| 164 | raise AssertionError()
|
| 165 |
|
| 166 | def __repr__(self, _repr_running={}):
|
| 167 | 'od.__repr__() <==> repr(od)'
|
| 168 | #call_key = id(self), _get_ident()
|
| 169 |
|
| 170 | # Oil patch: we don't have threads
|
| 171 | call_key = id(self)
|
| 172 |
|
| 173 | if call_key in _repr_running:
|
| 174 | return '...'
|
| 175 | _repr_running[call_key] = 1
|
| 176 | try:
|
| 177 | # Oil patch: use <> as a subtle indicator of OrderedDict
|
| 178 | parts = ['<']
|
| 179 | for i, key in enumerate(self):
|
| 180 | if i != 0:
|
| 181 | parts.append(', ')
|
| 182 | parts.append('%r: ' % key)
|
| 183 | parts.append('%r' % self[key])
|
| 184 | parts.append('>')
|
| 185 | return ''.join(parts)
|
| 186 |
|
| 187 | finally:
|
| 188 | del _repr_running[call_key]
|
| 189 |
|
| 190 | def copy(self):
|
| 191 | 'od.copy() -> a shallow copy of od'
|
| 192 | # PATCH: not used in Oil
|
| 193 | raise AssertionError()
|
| 194 |
|
| 195 | @classmethod
|
| 196 | def fromkeys(cls, iterable, value=None):
|
| 197 | '''OD.fromkeys(S[, v]) -> New ordered dictionary with keys from S.
|
| 198 | If not specified, the value defaults to None.
|
| 199 |
|
| 200 | '''
|
| 201 | # PATCH: not used in Oil
|
| 202 | raise AssertionError()
|
| 203 |
|
| 204 | def __eq__(self, other):
|
| 205 | '''od.__eq__(y) <==> od==y. Comparison to another OD is order-sensitive
|
| 206 | while comparison to a regular mapping is order-insensitive.
|
| 207 |
|
| 208 | '''
|
| 209 | # removed _imap code
|
| 210 | raise AssertionError('not supported')
|
| 211 |
|
| 212 | def __ne__(self, other):
|
| 213 | 'od.__ne__(y) <==> od!=y'
|
| 214 | return not self == other
|