1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375
|
"""IndexedDict class definition.
.. versionadded:: 1.0.3
"""
from collections.abc import MutableMapping
from ._util import deprecation_warning
from .sentinel import NOT_SET
__all__ = ('IndexedDict', )
# TODO these should be ValueErrors
KEY_AND_INDEX_ERROR = TypeError(
"Specifying both `key` and `index` is not allowed")
KEY_EQ_INDEX_ERROR = TypeError(
"Exactly one of `key` and `index` must be specified")
class IndexedDict(MutableMapping):
"""A Mapping that preserves insertion order and allows access by item index.
The API is an extension of OrderedDict.
"""
def __init__(self, iterable=None, **kwargs):
"""Create an IndexedDict and initialize it like a dict."""
self._dict = {} # key -> (index, value)
self._list = [] # index -> (key, value)
self.update(iterable or [], **kwargs)
def clear(self):
"""Remove all items."""
self._dict = {}
self._list = []
def get(self, key=NOT_SET, index=NOT_SET, default=NOT_SET, d=NOT_SET):
"""Return value with given `key` or `index`.
If no value is found, return `default` (`None` by default).
.. deprecated :: 1.0.3
The `d` parameter has been renamed `default`. `d` will be removed in
some future version.
Args:
key: The key of the value to get
index: The index of the value to get
default: The value to return if `key` is not found or `index` is
out of bounds. If it is NOT_SET, None is returned.
d: DEPRECATED: Old parameter name for `default`
"""
if d is not NOT_SET:
if default is not NOT_SET:
raise ValueError('Specified default and d')
deprecation_warning(
"IndexedDict.pop parameter 'd' has been renamed to 'default'"
)
default = d
if default is NOT_SET:
default = None
if index is NOT_SET and key is not NOT_SET:
try:
index, value = self._dict[key]
except KeyError:
return default
else:
return value
elif index is not NOT_SET and key is NOT_SET:
try:
key, value = self._list[index]
except IndexError:
return default
else:
return value
else:
raise KEY_EQ_INDEX_ERROR
def pop(self, key=NOT_SET, index=NOT_SET, default=NOT_SET, d=NOT_SET):
"""Remove and return value.
Optionally, specify the `key` or `index` of the value to pop.
If `key` is specified and is not found a `KeyError` is raised unless
`default` is specified. Likewise, if `index` is specified that is out of
bounds, an `IndexError` is raised unless `default` is specified.
Both `index` and `key` cannot be specified. If neither is specified,
then the last value is popped.
This is generally O(N) unless removing last item, then O(1).
.. deprecated :: 1.0.3
The `d` parameter has been renamed `default`. `d` will be removed in
some future version.
Args:
key: The key of the value to pop
index: The index of the value to pop
default: The value to return if the key is not found or the index is
out of bounds
d: DEPRECATED: Old parameter name for `default`
"""
if d is not NOT_SET:
if default is not NOT_SET:
raise ValueError('Specified default and d')
deprecation_warning(
"IndexedDict.pop parameter 'd' has been renamed to 'default'"
)
default = d
has_default = default is not NOT_SET
if index is NOT_SET and key is not NOT_SET:
index, value = self._pop_key(key, has_default)
elif key is NOT_SET:
key, index, value = self._pop_index(index, has_default)
else:
raise KEY_AND_INDEX_ERROR
if index is None:
return default
else:
self._fix_indices_after_delete(index)
return value
def _pop_key(self, key, has_default):
"""Remove an element by key."""
try:
index, value = self._dict.pop(key)
except KeyError:
if has_default:
return None, None
else:
raise
key2, value2 = self._list.pop(index)
assert key == key2, f"{key!r} != {key2!r}"
assert value is value2, f"{value} is not {value2}"
return index, value
def _pop_index(self, index, has_default):
"""Remove an element by index, or last element."""
try:
if index is NOT_SET:
index = len(self._list) - 1
key, value = self._list.pop()
else:
key, value = self._list.pop(index)
if index < 0:
index += len(self._list) + 1
except IndexError:
if has_default:
return None, None, None
else:
raise
index2, value2 = self._dict.pop(key)
assert index == index2
assert value is value2
return key, index, value
def fast_pop(self, key=NOT_SET, index=NOT_SET):
"""Pop a specific item quickly by swapping it to the end.
Remove value with given key or index (last item by default) fast
by swapping it to the last place first.
Changes order of the remaining items (item that used to be last goes to
the popped location).
Returns tuple of (poped_value, new_moved_index, moved_key, moved_value).
If key is not found raises KeyError or IndexError.
Runs in O(1).
"""
if index is NOT_SET and key is not NOT_SET:
index, popped_value = self._dict.pop(key)
elif key is NOT_SET:
if index is NOT_SET:
index = len(self._list) - 1
key, popped_value2 = self._list[-1]
else:
key, popped_value2 = self._list[index]
if index < 0:
index += len(self._list)
index2, popped_value = self._dict.pop(key)
assert index == index2
else:
raise KEY_AND_INDEX_ERROR
if key == self._list[-1][0]:
# The item we're removing happens to be the last in the list,
# no swapping needed
_, popped_value2 = self._list.pop()
assert popped_value is popped_value2
return popped_value, len(self._list), key, popped_value
else:
# Swap the last item onto the deleted spot and
# pop the last item from the list
self._list[index] = self._list[-1]
moved_key, moved_value = self._list.pop()
self._dict[moved_key] = (index, moved_value)
return popped_value, index, moved_key, moved_value
def popitem(self, last=NOT_SET, *, key=NOT_SET, index=NOT_SET):
"""Remove and return a (key, value) tuple.
By default, the last item is popped.
Optionally, specify the `key` or `index` of the value to pop.
The `last` parameter is included to match the OrderedDict API. If `last`
is passed then the first or last item is returned based on its
truthiness.
At most one of `index`, `last` and `key` can be specified.
This is generally O(N) unless removing last item, then O(1).
Args:
key: The key of the value to pop
index: The index of the value to pop
last: Whether or not to pip the last item
Raises:
KeyError: If the dictionary is empty or a key is specified that is
not present
IndexError: If `index` is specified and is out of bounds
ValueError: If more than one of `last`, `index` and `key` are
specified
"""
if not self:
raise KeyError('IndexedDict is empty')
if sum(x is not NOT_SET for x in (last, key, index)) > 1:
raise ValueError(
"Cannot specify more than one of key, index and last"
)
if key is not NOT_SET:
index, value = self._pop_key(key=key, has_default=False)
else:
if last is not NOT_SET:
index = -1 if last else 0
if index is NOT_SET:
index = -1
key, index, value = self._pop_index(index, has_default=False)
self._fix_indices_after_delete(starting_index=index)
return key, value
def move_to_end(self, key=NOT_SET, index=NOT_SET, last=True):
"""Move an existing element to the end (or beginning if last==False).
Runs in O(N).
"""
if index is NOT_SET and key is not NOT_SET:
index, value = self._dict[key]
elif index is not NOT_SET and key is NOT_SET:
key, value = self._list[index]
# Normalize index
if index < 0:
index += len(self._list)
else:
raise KEY_EQ_INDEX_ERROR
if last:
index_range = range(len(self._list) - 1, index - 1, -1)
self._dict[key] = (len(self._list) - 1, value)
else:
index_range = range(index + 1)
self._dict[key] = (0, value)
previous = (key, value)
for i in index_range:
self._dict[previous[0]] = i, previous[1]
previous, self._list[i] = self._list[i], previous
def copy(self):
"""Return a shallow copy."""
ret = IndexedDict()
ret._dict = self._dict.copy()
ret._list = list(self._list)
return ret
def index(self, key):
"""Return index of a record with given key.
Runs in O(1).
"""
return self._dict[key][0]
def key(self, index):
"""Return key of a record at given index.
Runs in O(1).
"""
return self._list[index][0]
def __len__(self):
"""Return number of elements stored."""
return len(self._list)
def __repr__(self):
return "{class_name}({data})".format(
class_name=self.__class__.__name__,
data=repr(self._list),
)
def __str__(self):
# When Python 3.5 support is dropped, we can rely on dict order and this
# can be simplified to:
# return "{class_name}({data})".format(
# class_name=self.__class__.__name__,
# data=repr(dict(self)),
# )
data = ', '.join(
'{k!r}: {v!r}'.format(k=k, v=v)
for k, v in self.items()
)
return "{class_name}({{{data}}})".format(
class_name=self.__class__.__name__,
data=data,
)
def __getitem__(self, key):
"""Return value corresponding to given key.
Raises KeyError when the key is not present in the mapping.
Runs in O(1).
"""
return self._dict[key][1]
def __setitem__(self, key, value):
"""Set item with given key to given value.
If the key is already present in the mapping its order is unchanged,
if it is not then it's added to the last place.
Runs in O(1).
"""
if key in self._dict:
index, old_value1 = self._dict[key]
self._list[index] = key, value
else:
index = len(self._list)
self._list.append((key, value))
self._dict[key] = index, value
def __delitem__(self, key):
"""Remove item with given key from the mapping.
Runs in O(n), unless removing last item, then in O(1).
"""
index, value = self._dict.pop(key)
key2, value2 = self._list.pop(index)
assert key == key2
assert value is value2
self._fix_indices_after_delete(index)
def __contains__(self, key):
"""Check if a key is present in the mapping.
Runs in O(1).
"""
return key in self._dict
def __iter__(self):
"""Return iterator over the keys of the mapping in order."""
return (item[0] for item in self._list)
def _fix_indices_after_delete(self, starting_index=0):
for i, (k, v) in enumerate(self._list[starting_index:], starting_index):
self._dict[k] = (i, v)
|