Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.11/site-packages/boltons/dictutils.py: 21%
Shortcuts on this page
r m x toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
1# Copyright (c) 2013, Mahmoud Hashemi
2#
3# Redistribution and use in source and binary forms, with or without
4# modification, are permitted provided that the following conditions are
5# met:
6#
7# * Redistributions of source code must retain the above copyright
8# notice, this list of conditions and the following disclaimer.
9#
10# * Redistributions in binary form must reproduce the above
11# copyright notice, this list of conditions and the following
12# disclaimer in the documentation and/or other materials provided
13# with the distribution.
14#
15# * The names of the contributors may not be used to endorse or
16# promote products derived from this software without specific
17# prior written permission.
18#
19# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
20# "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
21# LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
22# A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
23# OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
24# SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
25# LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
26# DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
27# THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
28# (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
29# OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31"""Python has a very powerful mapping type at its core: the :class:`dict`
32type. While versatile and featureful, the :class:`dict` prioritizes
33simplicity and performance. As a result, it does not retain the order
34of item insertion [1]_, nor does it store multiple values per key. It
35is a fast, unordered 1:1 mapping.
37The :class:`OrderedMultiDict` contrasts to the built-in :class:`dict`,
38as a relatively maximalist, ordered 1:n subtype of
39:class:`dict`. Virtually every feature of :class:`dict` has been
40retooled to be intuitive in the face of this added
41complexity. Additional methods have been added, such as
42:class:`collections.Counter`-like functionality.
44A prime advantage of the :class:`OrderedMultiDict` (OMD) is its
45non-destructive nature. Data can be added to an :class:`OMD` without being
46rearranged or overwritten. The property can allow the developer to
47work more freely with the data, as well as make more assumptions about
48where input data will end up in the output, all without any extra
49work.
51One great example of this is the :meth:`OMD.inverted()` method, which
52returns a new OMD with the values as keys and the keys as values. All
53the data and the respective order is still represented in the inverted
54form, all from an operation which would be outright wrong and reckless
55with a built-in :class:`dict` or :class:`collections.OrderedDict`.
57The OMD has been performance tuned to be suitable for a wide range of
58usages, including as a basic unordered MultiDict. Special
59thanks to `Mark Williams`_ for all his help.
61.. [1] As of 2015, `basic dicts on PyPy are ordered
62 <http://morepypy.blogspot.com/2015/01/faster-more-memory-efficient-and-more.html>`_,
63 and as of December 2017, `basic dicts in CPython 3 are now ordered
64 <https://mail.python.org/pipermail/python-dev/2017-December/151283.html>`_, as
65 well.
66.. _Mark Williams: https://github.com/markrwilliams
68"""
70from collections.abc import KeysView, ValuesView, ItemsView
71from itertools import zip_longest
73try:
74 from .typeutils import make_sentinel
75 _MISSING = make_sentinel(var_name='_MISSING')
76except ImportError:
77 _MISSING = object()
80PREV, NEXT, KEY, VALUE, SPREV, SNEXT = range(6)
83__all__ = ['MultiDict', 'OMD', 'OrderedMultiDict', 'OneToOne', 'ManyToMany', 'subdict', 'FrozenDict']
86class OrderedMultiDict(dict):
87 """A MultiDict is a dictionary that can have multiple values per key
88 and the OrderedMultiDict (OMD) is a MultiDict that retains
89 original insertion order. Common use cases include:
91 * handling query strings parsed from URLs
92 * inverting a dictionary to create a reverse index (values to keys)
93 * stacking data from multiple dictionaries in a non-destructive way
95 The OrderedMultiDict constructor is identical to the built-in
96 :class:`dict`, and overall the API constitutes an intuitive
97 superset of the built-in type:
99 >>> omd = OrderedMultiDict()
100 >>> omd['a'] = 1
101 >>> omd['b'] = 2
102 >>> omd.add('a', 3)
103 >>> omd.get('a')
104 3
105 >>> omd.getlist('a')
106 [1, 3]
108 Some non-:class:`dict`-like behaviors also make an appearance,
109 such as support for :func:`reversed`:
111 >>> list(reversed(omd))
112 ['b', 'a']
114 Note that unlike some other MultiDicts, this OMD gives precedence
115 to the most recent value added. ``omd['a']`` refers to ``3``, not
116 ``1``.
118 >>> omd
119 OrderedMultiDict([('a', 1), ('b', 2), ('a', 3)])
120 >>> omd.poplast('a')
121 3
122 >>> omd
123 OrderedMultiDict([('a', 1), ('b', 2)])
124 >>> omd.pop('a')
125 1
126 >>> omd
127 OrderedMultiDict([('b', 2)])
129 If you want a safe-to-modify or flat dictionary, use
130 :meth:`OrderedMultiDict.todict()`.
132 >>> from pprint import pprint as pp # preserve printed ordering
133 >>> omd = OrderedMultiDict([('a', 1), ('b', 2), ('a', 3)])
134 >>> pp(omd.todict())
135 {'a': 3, 'b': 2}
136 >>> pp(omd.todict(multi=True))
137 {'a': [1, 3], 'b': [2]}
139 With ``multi=False``, items appear with the keys in to original
140 insertion order, alongside the most-recently inserted value for
141 that key.
143 >>> OrderedMultiDict([('a', 1), ('b', 2), ('a', 3)]).items(multi=False)
144 [('a', 3), ('b', 2)]
146 .. warning::
148 ``dict(omd)`` changed behavior `in Python 3.7
149 <https://bugs.python.org/issue34320>`_ due to changes made to
150 support the transition from :class:`collections.OrderedDict` to
151 the built-in dictionary being ordered. Before 3.7, the result
152 would be a new dictionary, with values that were lists, similar
153 to ``omd.todict(multi=True)`` (but only shallow-copy; the lists
154 were direct references to OMD internal structures). From 3.7
155 onward, the values became singular, like
156 ``omd.todict(multi=False)``. For reliable cross-version
157 behavior, just use :meth:`~OrderedMultiDict.todict()`.
159 """
160 def __new__(cls, *a, **kw):
161 ret = super().__new__(cls)
162 ret._clear_ll()
163 return ret
165 def __init__(self, *args, **kwargs):
166 if len(args) > 1:
167 raise TypeError('%s expected at most 1 argument, got %s'
168 % (self.__class__.__name__, len(args)))
169 super().__init__()
171 if args:
172 self.update_extend(args[0])
173 if kwargs:
174 self.update(kwargs)
176 def __getstate__(self):
177 return list(self.iteritems(multi=True))
179 def __setstate__(self, state):
180 self.clear()
181 self.update_extend(state)
183 def __reduce__(self):
184 # The default dict-subclass reduce includes a dictitems iterator
185 # whose entries are reapplied via __setitem__ after __setstate__,
186 # collapsing each key's multiple values down to a single value.
187 # __getstate__/__setstate__ already round-trip the full (multi) state,
188 # so omit dictitems by returning a plain (callable, args, state) tuple.
189 return (self.__class__, (), self.__getstate__())
191 def _clear_ll(self):
192 try:
193 _map = self._map
194 except AttributeError:
195 _map = self._map = {}
196 self.root = []
197 _map.clear()
198 self.root[:] = [self.root, self.root, None]
200 def _insert(self, k, v):
201 root = self.root
202 cells = self._map.setdefault(k, [])
203 last = root[PREV]
204 cell = [last, root, k, v]
205 last[NEXT] = root[PREV] = cell
206 cells.append(cell)
208 def add(self, k, v):
209 """Add a single value *v* under a key *k*. Existing values under *k*
210 are preserved.
211 """
212 values = super().setdefault(k, [])
213 self._insert(k, v)
214 values.append(v)
216 def addlist(self, k, v):
217 """Add an iterable of values underneath a specific key, preserving
218 any values already under that key.
220 >>> omd = OrderedMultiDict([('a', -1)])
221 >>> omd.addlist('a', range(3))
222 >>> omd
223 OrderedMultiDict([('a', -1), ('a', 0), ('a', 1), ('a', 2)])
225 Called ``addlist`` for consistency with :meth:`getlist`, but
226 tuples and other sequences and iterables work.
227 """
228 # materialize first: the values are traversed twice below, and a
229 # one-shot iterator would be empty by the second pass
230 v = list(v)
231 if not v:
232 return
233 self_insert = self._insert
234 values = super().setdefault(k, [])
235 for subv in v:
236 self_insert(k, subv)
237 values.extend(v)
239 def get(self, k, default=None):
240 """Return the value for key *k* if present in the dictionary, else
241 *default*. If *default* is not given, ``None`` is returned.
242 This method never raises a :exc:`KeyError`.
244 To get all values under a key, use :meth:`OrderedMultiDict.getlist`.
245 """
246 return super().get(k, [default])[-1]
248 def getlist(self, k, default=_MISSING):
249 """Get all values for key *k* as a list, if *k* is in the
250 dictionary, else *default*. The list returned is a copy and
251 can be safely mutated. If *default* is not given, an empty
252 :class:`list` is returned.
253 """
254 try:
255 return super().__getitem__(k)[:]
256 except KeyError:
257 if default is _MISSING:
258 return []
259 return default
261 def clear(self):
262 "Empty the dictionary."
263 super().clear()
264 self._clear_ll()
266 def setdefault(self, k, default=_MISSING):
267 """If key *k* is in the dictionary, return its value. If not, insert
268 *k* with a value of *default* and return *default*. *default*
269 defaults to ``None``. See :meth:`dict.setdefault` for more
270 information.
271 """
272 if not super().__contains__(k):
273 self[k] = None if default is _MISSING else default
274 return self[k]
276 def copy(self):
277 "Return a shallow copy of the dictionary."
278 return self.__class__(self.iteritems(multi=True))
280 @classmethod
281 def fromkeys(cls, keys, default=None):
282 """Create a dictionary from a list of keys, with all the values
283 set to *default*, or ``None`` if *default* is not set.
284 """
285 return cls([(k, default) for k in keys])
287 def update(self, E, **F):
288 """Add items from a dictionary or iterable (and/or keyword arguments),
289 overwriting values under an existing key. See
290 :meth:`dict.update` for more details.
291 """
292 # E and F are throwback names to the dict() __doc__
293 if E is self:
294 return
295 self_add = self.add
296 if isinstance(E, OrderedMultiDict):
297 for k in E:
298 if k in self:
299 del self[k]
300 for k, v in E.iteritems(multi=True):
301 self_add(k, v)
302 elif callable(getattr(E, 'keys', None)):
303 for k in E.keys():
304 self[k] = E[k]
305 else:
306 seen = set()
307 seen_add = seen.add
308 for k, v in E:
309 if k not in seen and k in self:
310 del self[k]
311 seen_add(k)
312 self_add(k, v)
313 for k in F:
314 self[k] = F[k]
315 return
317 def update_extend(self, E, **F):
318 """Add items from a dictionary, iterable, and/or keyword
319 arguments without overwriting existing items present in the
320 dictionary. Like :meth:`update`, but adds to existing keys
321 instead of overwriting them.
322 """
323 if E is self:
324 iterator = iter(E.items())
325 elif isinstance(E, OrderedMultiDict):
326 iterator = E.iteritems(multi=True)
327 elif hasattr(E, 'keys'):
328 iterator = ((k, E[k]) for k in E.keys())
329 else:
330 iterator = E
332 self_add = self.add
333 for k, v in iterator:
334 self_add(k, v)
336 def __setitem__(self, k, v):
337 if super().__contains__(k):
338 self._remove_all(k)
339 self._insert(k, v)
340 super().__setitem__(k, [v])
342 def __getitem__(self, k):
343 return super().__getitem__(k)[-1]
345 def __delitem__(self, k):
346 super().__delitem__(k)
347 self._remove_all(k)
349 def __eq__(self, other):
350 if self is other:
351 return True
352 try:
353 if len(other) != len(self):
354 return False
355 except TypeError:
356 return False
357 if isinstance(other, OrderedMultiDict):
358 selfi = self.iteritems(multi=True)
359 otheri = other.iteritems(multi=True)
360 zipped_items = zip_longest(selfi, otheri, fillvalue=(None, None))
361 for (selfk, selfv), (otherk, otherv) in zipped_items:
362 if selfk != otherk or selfv != otherv:
363 return False
364 if not(next(selfi, _MISSING) is _MISSING
365 and next(otheri, _MISSING) is _MISSING):
366 # leftovers (TODO: watch for StopIteration?)
367 return False
368 return True
369 elif hasattr(other, 'keys'):
370 for selfk in self:
371 try:
372 if other[selfk] != self[selfk]:
373 return False
374 except KeyError:
375 return False
376 return True
377 return False
379 def __ne__(self, other):
380 return not (self == other)
382 def __ior__(self, other):
383 self.update(other)
384 return self
386 def pop(self, k, default=_MISSING):
387 """Remove all values under key *k*, returning the most-recently
388 inserted value. Raises :exc:`KeyError` if the key is not
389 present and no *default* is provided.
390 """
391 try:
392 return self.popall(k)[-1]
393 except KeyError:
394 if default is _MISSING:
395 raise KeyError(k)
396 return default
398 def popall(self, k, default=_MISSING):
399 """Remove all values under key *k*, returning them in the form of
400 a list. Raises :exc:`KeyError` if the key is not present and no
401 *default* is provided.
402 """
403 super_self = super()
404 if super_self.__contains__(k):
405 self._remove_all(k)
406 if default is _MISSING:
407 return super_self.pop(k)
408 return super_self.pop(k, default)
410 def poplast(self, k=_MISSING, default=_MISSING):
411 """Remove and return the most-recently inserted value under the key
412 *k*, or the most-recently inserted key if *k* is not
413 provided. If no values remain under *k*, it will be removed
414 from the OMD. Raises :exc:`KeyError` if *k* is not present in
415 the dictionary, or the dictionary is empty.
416 """
417 if k is _MISSING:
418 if self:
419 k = self.root[PREV][KEY]
420 else:
421 if default is _MISSING:
422 raise KeyError('empty %r' % type(self))
423 return default
424 try:
425 self._remove(k)
426 except KeyError:
427 if default is _MISSING:
428 raise KeyError(k)
429 return default
430 values = super().__getitem__(k)
431 v = values.pop()
432 if not values:
433 super().__delitem__(k)
434 return v
436 def _remove(self, k):
437 values = self._map[k]
438 cell = values.pop()
439 cell[PREV][NEXT], cell[NEXT][PREV] = cell[NEXT], cell[PREV]
440 if not values:
441 del self._map[k]
443 def _remove_all(self, k):
444 values = self._map[k]
445 while values:
446 cell = values.pop()
447 cell[PREV][NEXT], cell[NEXT][PREV] = cell[NEXT], cell[PREV]
448 del self._map[k]
450 def iteritems(self, multi=False):
451 """Iterate over the OMD's items in insertion order. By default,
452 yields only the most-recently inserted value for each key. Set
453 *multi* to ``True`` to get all inserted items.
454 """
455 root = self.root
456 curr = root[NEXT]
457 if multi:
458 while curr is not root:
459 yield curr[KEY], curr[VALUE]
460 curr = curr[NEXT]
461 else:
462 for key in self.iterkeys():
463 yield key, self[key]
465 def iterkeys(self, multi=False):
466 """Iterate over the OMD's keys in insertion order. By default, yields
467 each key once, according to the most recent insertion. Set
468 *multi* to ``True`` to get all keys, including duplicates, in
469 insertion order.
470 """
471 root = self.root
472 curr = root[NEXT]
473 if multi:
474 while curr is not root:
475 yield curr[KEY]
476 curr = curr[NEXT]
477 else:
478 yielded = set()
479 yielded_add = yielded.add
480 while curr is not root:
481 k = curr[KEY]
482 if k not in yielded:
483 yielded_add(k)
484 yield k
485 curr = curr[NEXT]
487 def itervalues(self, multi=False):
488 """Iterate over the OMD's values in insertion order. By default,
489 yields the most-recently inserted value per unique key. Set
490 *multi* to ``True`` to get all values according to insertion
491 order.
492 """
493 for k, v in self.iteritems(multi=multi):
494 yield v
496 def todict(self, multi=False):
497 """Gets a basic :class:`dict` of the items in this dictionary. Keys
498 are the same as the OMD, values are the most recently inserted
499 values for each key.
501 Setting the *multi* arg to ``True`` is yields the same
502 result as calling :class:`dict` on the OMD, except that all the
503 value lists are copies that can be safely mutated.
504 """
505 if multi:
506 return {k: self.getlist(k) for k in self}
507 return {k: self[k] for k in self}
509 def sorted(self, key=None, reverse=False):
510 """Similar to the built-in :func:`sorted`, except this method returns
511 a new :class:`OrderedMultiDict` sorted by the provided key
512 function, optionally reversed.
514 Args:
515 key (callable): A callable to determine the sort key of
516 each element. The callable should expect an **item**
517 (key-value pair tuple).
518 reverse (bool): Set to ``True`` to reverse the ordering.
520 >>> omd = OrderedMultiDict(zip(range(3), range(3)))
521 >>> omd.sorted(reverse=True)
522 OrderedMultiDict([(2, 2), (1, 1), (0, 0)])
524 Note that the key function receives an **item** (key-value
525 tuple), so the recommended signature looks like:
527 >>> omd = OrderedMultiDict(zip('hello', 'world'))
528 >>> omd.sorted(key=lambda i: i[1]) # i[0] is the key, i[1] is the val
529 OrderedMultiDict([('o', 'd'), ('l', 'l'), ('e', 'o'), ('l', 'r'), ('h', 'w')])
530 """
531 cls = self.__class__
532 return cls(sorted(self.iteritems(multi=True), key=key, reverse=reverse))
534 def sortedvalues(self, key=None, reverse=False):
535 """Returns a copy of the :class:`OrderedMultiDict` with the same keys
536 in the same order as the original OMD, but the values within
537 each keyspace have been sorted according to *key* and
538 *reverse*.
540 Args:
541 key (callable): A single-argument callable to determine
542 the sort key of each element. The callable should expect
543 an **item** (key-value pair tuple).
544 reverse (bool): Set to ``True`` to reverse the ordering.
546 >>> omd = OrderedMultiDict()
547 >>> omd.addlist('even', [6, 2])
548 >>> omd.addlist('odd', [1, 5])
549 >>> omd.add('even', 4)
550 >>> omd.add('odd', 3)
551 >>> somd = omd.sortedvalues()
552 >>> somd.getlist('even')
553 [2, 4, 6]
554 >>> somd.keys(multi=True) == omd.keys(multi=True)
555 True
556 >>> omd == somd
557 False
558 >>> somd
559 OrderedMultiDict([('even', 2), ('even', 4), ('odd', 1), ('odd', 3), ('even', 6), ('odd', 5)])
561 As demonstrated above, contents and key order are
562 retained. Only value order changes.
563 """
564 try:
565 superself_iteritems = super().iteritems()
566 except AttributeError:
567 superself_iteritems = super().items()
568 # (not reverse) because they pop off in reverse order for reinsertion
569 sorted_val_map = {k: sorted(v, key=key, reverse=(not reverse))
570 for k, v in superself_iteritems}
571 ret = self.__class__()
572 for k in self.iterkeys(multi=True):
573 ret.add(k, sorted_val_map[k].pop())
574 return ret
576 def inverted(self):
577 """Returns a new :class:`OrderedMultiDict` with values and keys
578 swapped, like creating dictionary transposition or reverse
579 index. Insertion order is retained and all keys and values
580 are represented in the output.
582 >>> omd = OMD([(0, 2), (1, 2)])
583 >>> omd.inverted().getlist(2)
584 [0, 1]
586 Inverting twice yields a copy of the original:
588 >>> omd.inverted().inverted()
589 OrderedMultiDict([(0, 2), (1, 2)])
590 """
591 return self.__class__((v, k) for k, v in self.iteritems(multi=True))
593 def counts(self):
594 """Returns a mapping from key to number of values inserted under that
595 key. Like :py:class:`collections.Counter`, but returns a new
596 :class:`OrderedMultiDict`.
597 """
598 # Returns an OMD because Counter/OrderedDict may not be
599 # available, and neither Counter nor dict maintain order.
600 super_getitem = super().__getitem__
601 return self.__class__((k, len(super_getitem(k))) for k in self)
603 def keys(self, multi=False):
604 """Returns a list containing the output of :meth:`iterkeys`. See
605 that method's docs for more details.
606 """
607 return list(self.iterkeys(multi=multi))
609 def values(self, multi=False):
610 """Returns a list containing the output of :meth:`itervalues`. See
611 that method's docs for more details.
612 """
613 return list(self.itervalues(multi=multi))
615 def items(self, multi=False):
616 """Returns a list containing the output of :meth:`iteritems`. See
617 that method's docs for more details.
618 """
619 return list(self.iteritems(multi=multi))
621 def __iter__(self):
622 return self.iterkeys()
624 def __reversed__(self):
625 root = self.root
626 curr = root[PREV]
627 lengths = {}
628 lengths_sd = lengths.setdefault
629 get_values = super().__getitem__
630 while curr is not root:
631 k = curr[KEY]
632 vals = get_values(k)
633 if lengths_sd(k, 1) == len(vals):
634 yield k
635 lengths[k] += 1
636 curr = curr[PREV]
638 def __repr__(self):
639 cn = self.__class__.__name__
640 kvs = ', '.join([repr((k, v)) for k, v in self.iteritems(multi=True)])
641 return f'{cn}([{kvs}])'
643 def viewkeys(self):
644 "OMD.viewkeys() -> a set-like object providing a view on OMD's keys"
645 return KeysView(self)
647 def viewvalues(self):
648 "OMD.viewvalues() -> an object providing a view on OMD's values"
649 return ValuesView(self)
651 def viewitems(self):
652 "OMD.viewitems() -> a set-like object providing a view on OMD's items"
653 return ItemsView(self)
656# A couple of convenient aliases
657OMD = OrderedMultiDict
658MultiDict = OrderedMultiDict
661class FastIterOrderedMultiDict(OrderedMultiDict):
662 """An OrderedMultiDict backed by a skip list. Iteration over keys
663 is faster and uses constant memory but adding duplicate key-value
664 pairs is slower. Brainchild of Mark Williams.
665 """
666 def _clear_ll(self):
667 # TODO: always reset objects? (i.e., no else block below)
668 try:
669 _map = self._map
670 except AttributeError:
671 _map = self._map = {}
672 self.root = []
673 _map.clear()
674 self.root[:] = [self.root, self.root,
675 None, None,
676 self.root, self.root]
678 def _insert(self, k, v):
679 root = self.root
680 empty = []
681 cells = self._map.setdefault(k, empty)
682 last = root[PREV]
684 if cells is empty:
685 cell = [last, root,
686 k, v,
687 last, root]
688 # was the last one skipped?
689 if last[SPREV][SNEXT] is root:
690 last[SPREV][SNEXT] = cell
691 last[NEXT] = last[SNEXT] = root[PREV] = root[SPREV] = cell
692 cells.append(cell)
693 else:
694 # if the previous was skipped, go back to the cell that
695 # skipped it
696 sprev = last[SPREV] if (last[SPREV][SNEXT] is not last) else last
697 cell = [last, root,
698 k, v,
699 sprev, root]
700 # skip me
701 last[SNEXT] = root
702 last[NEXT] = root[PREV] = root[SPREV] = cell
703 cells.append(cell)
705 def _remove(self, k):
706 cells = self._map[k]
707 cell = cells.pop()
708 if not cells:
709 del self._map[k]
710 cell[PREV][SNEXT] = cell[SNEXT]
712 if cell[PREV][SPREV][SNEXT] is cell:
713 cell[PREV][SPREV][SNEXT] = cell[NEXT]
714 elif cell[SNEXT] is cell[NEXT]:
715 cell[SPREV][SNEXT], cell[SNEXT][SPREV] = cell[SNEXT], cell[SPREV]
717 cell[PREV][NEXT], cell[NEXT][PREV] = cell[NEXT], cell[PREV]
719 def _remove_all(self, k):
720 cells = self._map.pop(k)
721 while cells:
722 cell = cells.pop()
723 if cell[PREV][SPREV][SNEXT] is cell:
724 cell[PREV][SPREV][SNEXT] = cell[NEXT]
725 elif cell[SNEXT] is cell[NEXT]:
726 cell[SPREV][SNEXT], cell[SNEXT][SPREV] = cell[SNEXT], cell[SPREV]
728 cell[PREV][NEXT], cell[NEXT][PREV] = cell[NEXT], cell[PREV]
729 cell[PREV][SNEXT] = cell[SNEXT]
731 def iteritems(self, multi=False):
732 next_link = NEXT if multi else SNEXT
733 root = self.root
734 curr = root[next_link]
735 while curr is not root:
736 yield curr[KEY], curr[VALUE]
737 curr = curr[next_link]
739 def iterkeys(self, multi=False):
740 next_link = NEXT if multi else SNEXT
741 root = self.root
742 curr = root[next_link]
743 while curr is not root:
744 yield curr[KEY]
745 curr = curr[next_link]
747 def __reversed__(self):
748 root = self.root
749 curr = root[PREV]
750 while curr is not root:
751 if curr[SPREV][SNEXT] is not curr:
752 curr = curr[SPREV]
753 if curr is root:
754 break
755 yield curr[KEY]
756 curr = curr[PREV]
759_OTO_INV_MARKER = object()
760_OTO_UNIQUE_MARKER = object()
763class OneToOne(dict):
764 """Implements a one-to-one mapping dictionary. In addition to
765 inheriting from and behaving exactly like the builtin
766 :class:`dict`, all values are automatically added as keys on a
767 reverse mapping, available as the `inv` attribute. This
768 arrangement keeps key and value namespaces distinct.
770 Basic operations are intuitive:
772 >>> oto = OneToOne({'a': 1, 'b': 2})
773 >>> print(oto['a'])
774 1
775 >>> print(oto.inv[1])
776 a
777 >>> len(oto)
778 2
780 Overwrites happens in both directions:
782 >>> oto.inv[1] = 'c'
783 >>> print(oto.get('a'))
784 None
785 >>> len(oto)
786 2
788 For a very similar project, with even more one-to-one
789 functionality, check out `bidict <https://github.com/jab/bidict>`_.
790 """
791 __slots__ = ('inv',)
793 def __init__(self, *a, **kw):
794 raise_on_dupe = False
795 if a:
796 if a[0] is _OTO_INV_MARKER:
797 self.inv = a[1]
798 dict.__init__(self, [(v, k) for k, v in self.inv.items()])
799 return
800 elif a[0] is _OTO_UNIQUE_MARKER:
801 a, raise_on_dupe = a[1:], True
803 dict.__init__(self, *a, **kw)
804 self.inv = self.__class__(_OTO_INV_MARKER, self)
806 if len(self) == len(self.inv):
807 # if lengths match, that means everything's unique
808 return
810 if not raise_on_dupe:
811 dict.clear(self)
812 dict.update(self, [(v, k) for k, v in self.inv.items()])
813 return
815 # generate an error message if the values aren't 1:1
817 val_multidict = {}
818 for k, v in self.items():
819 val_multidict.setdefault(v, []).append(k)
821 dupes = {v: k_list for v, k_list in
822 val_multidict.items() if len(k_list) > 1}
824 raise ValueError('expected unique values, got multiple keys for'
825 ' the following values: %r' % dupes)
827 @classmethod
828 def unique(cls, *a, **kw):
829 """This alternate constructor for OneToOne will raise an exception
830 when input values overlap. For instance:
832 >>> OneToOne.unique({'a': 1, 'b': 1})
833 Traceback (most recent call last):
834 ...
835 ValueError: expected unique values, got multiple keys for the following values: ...
837 This even works across inputs:
839 >>> a_dict = {'a': 2}
840 >>> OneToOne.unique(a_dict, b=2)
841 Traceback (most recent call last):
842 ...
843 ValueError: expected unique values, got multiple keys for the following values: ...
844 """
845 return cls(_OTO_UNIQUE_MARKER, *a, **kw)
847 def __setitem__(self, key, val):
848 hash(val) # ensure val is a valid key
849 if key in self:
850 dict.__delitem__(self.inv, self[key])
851 if val in self.inv:
852 del self.inv[val]
853 dict.__setitem__(self, key, val)
854 dict.__setitem__(self.inv, val, key)
856 def __delitem__(self, key):
857 dict.__delitem__(self.inv, self[key])
858 dict.__delitem__(self, key)
860 def clear(self):
861 dict.clear(self)
862 dict.clear(self.inv)
864 def copy(self):
865 return self.__class__(self)
867 def pop(self, key, default=_MISSING):
868 if key in self:
869 dict.__delitem__(self.inv, self[key])
870 return dict.pop(self, key)
871 if default is not _MISSING:
872 return default
873 raise KeyError()
875 def popitem(self):
876 key, val = dict.popitem(self)
877 dict.__delitem__(self.inv, val)
878 return key, val
880 def setdefault(self, key, default=None):
881 if key not in self:
882 self[key] = default
883 return self[key]
885 def update(self, dict_or_iterable, **kw):
886 keys_vals = []
887 if isinstance(dict_or_iterable, dict):
888 for val in dict_or_iterable.values():
889 hash(val)
890 keys_vals = list(dict_or_iterable.items())
891 else:
892 for key, val in dict_or_iterable:
893 hash(key)
894 hash(val)
895 keys_vals = list(dict_or_iterable)
896 for val in kw.values():
897 hash(val)
898 keys_vals.extend(kw.items())
899 for key, val in keys_vals:
900 self[key] = val
902 def __repr__(self):
903 cn = self.__class__.__name__
904 dict_repr = dict.__repr__(self)
905 return f"{cn}({dict_repr})"
908# marker for the secret handshake used internally to set up the invert ManyToMany
909_PAIRING = object()
912class ManyToMany:
913 """
914 a dict-like entity that represents a many-to-many relationship
915 between two groups of objects
917 behaves like a dict-of-tuples; also has .inv which is kept
918 up to date which is a dict-of-tuples in the other direction
920 also, can be used as a directed graph among hashable python objects
921 """
922 def __init__(self, items=None):
923 self.data = {}
924 if type(items) is tuple and items and items[0] is _PAIRING:
925 self.inv = items[1]
926 else:
927 self.inv = self.__class__((_PAIRING, self))
928 if items:
929 self.update(items)
930 return
932 def get(self, key, default=frozenset()):
933 try:
934 return self[key]
935 except KeyError:
936 return default
938 def __getitem__(self, key):
939 return frozenset(self.data[key])
941 def __setitem__(self, key, vals):
942 vals = set(vals)
943 if key in self:
944 to_remove = self.data[key] - vals
945 vals -= self.data[key]
946 for val in to_remove:
947 self.remove(key, val)
948 for val in vals:
949 self.add(key, val)
951 def __delitem__(self, key):
952 for val in self.data.pop(key):
953 self.inv.data[val].remove(key)
954 if not self.inv.data[val]:
955 del self.inv.data[val]
957 def update(self, iterable):
958 """given an iterable of (key, val), add them all"""
959 if type(iterable) is type(self):
960 other = iterable
961 for k in other.data:
962 if k not in self.data:
963 self.data[k] = other.data[k]
964 else:
965 self.data[k].update(other.data[k])
966 for k in other.inv.data:
967 if k not in self.inv.data:
968 self.inv.data[k] = other.inv.data[k]
969 else:
970 self.inv.data[k].update(other.inv.data[k])
971 elif callable(getattr(iterable, 'keys', None)):
972 for k in iterable.keys():
973 self.add(k, iterable[k])
974 else:
975 for key, val in iterable:
976 self.add(key, val)
977 return
979 def add(self, key, val):
980 if key not in self.data:
981 self.data[key] = set()
982 self.data[key].add(val)
983 if val not in self.inv.data:
984 self.inv.data[val] = set()
985 self.inv.data[val].add(key)
987 def remove(self, key, val):
988 self.data[key].remove(val)
989 if not self.data[key]:
990 del self.data[key]
991 self.inv.data[val].remove(key)
992 if not self.inv.data[val]:
993 del self.inv.data[val]
995 def replace(self, key, newkey):
996 """
997 replace instances of key by newkey
998 """
999 if key not in self.data:
1000 return
1001 self.data[newkey] = fwdset = self.data.pop(key)
1002 for val in fwdset:
1003 revset = self.inv.data[val]
1004 revset.remove(key)
1005 revset.add(newkey)
1007 def iteritems(self):
1008 for key in self.data:
1009 for val in self.data[key]:
1010 yield key, val
1012 def keys(self):
1013 return self.data.keys()
1015 def __contains__(self, key):
1016 return key in self.data
1018 def __iter__(self):
1019 return self.data.__iter__()
1021 def __len__(self):
1022 return self.data.__len__()
1024 def __eq__(self, other):
1025 return type(self) == type(other) and self.data == other.data
1027 def __repr__(self):
1028 cn = self.__class__.__name__
1029 return f'{cn}({list(self.iteritems())!r})'
1032def subdict(d, keep=None, drop=None):
1033 """Compute the "subdictionary" of a dict, *d*.
1035 A subdict is to a dict what a subset is a to set. If *A* is a
1036 subdict of *B*, that means that all keys of *A* are present in
1037 *B*.
1039 Returns a new dict with any keys in *drop* removed, and any keys
1040 in *keep* still present, provided they were in the original
1041 dict. *keep* defaults to all keys, *drop* defaults to empty, so
1042 without one of these arguments, calling this function is
1043 equivalent to calling ``dict()``.
1045 >>> from pprint import pprint as pp
1046 >>> pp(subdict({'a': 1, 'b': 2}))
1047 {'a': 1, 'b': 2}
1048 >>> subdict({'a': 1, 'b': 2, 'c': 3}, drop=['b', 'c'])
1049 {'a': 1}
1050 >>> pp(subdict({'a': 1, 'b': 2, 'c': 3}, keep=['a', 'c']))
1051 {'a': 1, 'c': 3}
1053 """
1054 if keep is None:
1055 keep = d.keys()
1056 if drop is None:
1057 drop = []
1059 keys = set(keep) - set(drop)
1061 return type(d)([(k, v) for k, v in d.items() if k in keys])
1064class FrozenHashError(TypeError):
1065 pass
1068class FrozenDict(dict):
1069 """An immutable dict subtype that is hashable and can itself be used
1070 as a :class:`dict` key or :class:`set` entry. What
1071 :class:`frozenset` is to :class:`set`, FrozenDict is to
1072 :class:`dict`.
1074 There was once an attempt to introduce such a type to the standard
1075 library, but it was rejected: `PEP 416 <https://www.python.org/dev/peps/pep-0416/>`_.
1077 Because FrozenDict is a :class:`dict` subtype, it automatically
1078 works everywhere a dict would, including JSON serialization.
1080 """
1081 __slots__ = ('_hash',)
1083 def updated(self, *a, **kw):
1084 """Make a copy and add items from a dictionary or iterable (and/or
1085 keyword arguments), overwriting values under an existing
1086 key. See :meth:`dict.update` for more details.
1087 """
1088 data = dict(self)
1089 data.update(*a, **kw)
1090 return type(self)(data)
1092 @classmethod
1093 def fromkeys(cls, keys, value=None):
1094 # one of the lesser known and used/useful dict methods
1095 return cls(dict.fromkeys(keys, value))
1097 def __repr__(self):
1098 cn = self.__class__.__name__
1099 return f'{cn}({dict.__repr__(self)})'
1101 def __reduce_ex__(self, protocol):
1102 return type(self), (dict(self),)
1104 def __hash__(self):
1105 try:
1106 ret = self._hash
1107 except AttributeError:
1108 try:
1109 ret = self._hash = hash(frozenset(self.items()))
1110 except Exception as e:
1111 ret = self._hash = FrozenHashError(e)
1113 if ret.__class__ is FrozenHashError:
1114 raise ret
1116 return ret
1118 def __copy__(self):
1119 return self # immutable types don't copy, see tuple's behavior
1121 # block everything else
1122 def _raise_frozen_typeerror(self, *a, **kw):
1123 "raises a TypeError, because FrozenDicts are immutable"
1124 raise TypeError('%s object is immutable' % self.__class__.__name__)
1126 __ior__ = __setitem__ = __delitem__ = update = _raise_frozen_typeerror
1127 setdefault = pop = popitem = clear = _raise_frozen_typeerror
1129 del _raise_frozen_typeerror
1132# end dictutils.py