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 if not v:
229 return
230 self_insert = self._insert
231 values = super().setdefault(k, [])
232 for subv in v:
233 self_insert(k, subv)
234 values.extend(v)
236 def get(self, k, default=None):
237 """Return the value for key *k* if present in the dictionary, else
238 *default*. If *default* is not given, ``None`` is returned.
239 This method never raises a :exc:`KeyError`.
241 To get all values under a key, use :meth:`OrderedMultiDict.getlist`.
242 """
243 return super().get(k, [default])[-1]
245 def getlist(self, k, default=_MISSING):
246 """Get all values for key *k* as a list, if *k* is in the
247 dictionary, else *default*. The list returned is a copy and
248 can be safely mutated. If *default* is not given, an empty
249 :class:`list` is returned.
250 """
251 try:
252 return super().__getitem__(k)[:]
253 except KeyError:
254 if default is _MISSING:
255 return []
256 return default
258 def clear(self):
259 "Empty the dictionary."
260 super().clear()
261 self._clear_ll()
263 def setdefault(self, k, default=_MISSING):
264 """If key *k* is in the dictionary, return its value. If not, insert
265 *k* with a value of *default* and return *default*. *default*
266 defaults to ``None``. See :meth:`dict.setdefault` for more
267 information.
268 """
269 if not super().__contains__(k):
270 self[k] = None if default is _MISSING else default
271 return self[k]
273 def copy(self):
274 "Return a shallow copy of the dictionary."
275 return self.__class__(self.iteritems(multi=True))
277 @classmethod
278 def fromkeys(cls, keys, default=None):
279 """Create a dictionary from a list of keys, with all the values
280 set to *default*, or ``None`` if *default* is not set.
281 """
282 return cls([(k, default) for k in keys])
284 def update(self, E, **F):
285 """Add items from a dictionary or iterable (and/or keyword arguments),
286 overwriting values under an existing key. See
287 :meth:`dict.update` for more details.
288 """
289 # E and F are throwback names to the dict() __doc__
290 if E is self:
291 return
292 self_add = self.add
293 if isinstance(E, OrderedMultiDict):
294 for k in E:
295 if k in self:
296 del self[k]
297 for k, v in E.iteritems(multi=True):
298 self_add(k, v)
299 elif callable(getattr(E, 'keys', None)):
300 for k in E.keys():
301 self[k] = E[k]
302 else:
303 seen = set()
304 seen_add = seen.add
305 for k, v in E:
306 if k not in seen and k in self:
307 del self[k]
308 seen_add(k)
309 self_add(k, v)
310 for k in F:
311 self[k] = F[k]
312 return
314 def update_extend(self, E, **F):
315 """Add items from a dictionary, iterable, and/or keyword
316 arguments without overwriting existing items present in the
317 dictionary. Like :meth:`update`, but adds to existing keys
318 instead of overwriting them.
319 """
320 if E is self:
321 iterator = iter(E.items())
322 elif isinstance(E, OrderedMultiDict):
323 iterator = E.iteritems(multi=True)
324 elif hasattr(E, 'keys'):
325 iterator = ((k, E[k]) for k in E.keys())
326 else:
327 iterator = E
329 self_add = self.add
330 for k, v in iterator:
331 self_add(k, v)
333 def __setitem__(self, k, v):
334 if super().__contains__(k):
335 self._remove_all(k)
336 self._insert(k, v)
337 super().__setitem__(k, [v])
339 def __getitem__(self, k):
340 return super().__getitem__(k)[-1]
342 def __delitem__(self, k):
343 super().__delitem__(k)
344 self._remove_all(k)
346 def __eq__(self, other):
347 if self is other:
348 return True
349 try:
350 if len(other) != len(self):
351 return False
352 except TypeError:
353 return False
354 if isinstance(other, OrderedMultiDict):
355 selfi = self.iteritems(multi=True)
356 otheri = other.iteritems(multi=True)
357 zipped_items = zip_longest(selfi, otheri, fillvalue=(None, None))
358 for (selfk, selfv), (otherk, otherv) in zipped_items:
359 if selfk != otherk or selfv != otherv:
360 return False
361 if not(next(selfi, _MISSING) is _MISSING
362 and next(otheri, _MISSING) is _MISSING):
363 # leftovers (TODO: watch for StopIteration?)
364 return False
365 return True
366 elif hasattr(other, 'keys'):
367 for selfk in self:
368 try:
369 if other[selfk] != self[selfk]:
370 return False
371 except KeyError:
372 return False
373 return True
374 return False
376 def __ne__(self, other):
377 return not (self == other)
379 def __ior__(self, other):
380 self.update(other)
381 return self
383 def pop(self, k, default=_MISSING):
384 """Remove all values under key *k*, returning the most-recently
385 inserted value. Raises :exc:`KeyError` if the key is not
386 present and no *default* is provided.
387 """
388 try:
389 return self.popall(k)[-1]
390 except KeyError:
391 if default is _MISSING:
392 raise KeyError(k)
393 return default
395 def popall(self, k, default=_MISSING):
396 """Remove all values under key *k*, returning them in the form of
397 a list. Raises :exc:`KeyError` if the key is not present and no
398 *default* is provided.
399 """
400 super_self = super()
401 if super_self.__contains__(k):
402 self._remove_all(k)
403 if default is _MISSING:
404 return super_self.pop(k)
405 return super_self.pop(k, default)
407 def poplast(self, k=_MISSING, default=_MISSING):
408 """Remove and return the most-recently inserted value under the key
409 *k*, or the most-recently inserted key if *k* is not
410 provided. If no values remain under *k*, it will be removed
411 from the OMD. Raises :exc:`KeyError` if *k* is not present in
412 the dictionary, or the dictionary is empty.
413 """
414 if k is _MISSING:
415 if self:
416 k = self.root[PREV][KEY]
417 else:
418 if default is _MISSING:
419 raise KeyError('empty %r' % type(self))
420 return default
421 try:
422 self._remove(k)
423 except KeyError:
424 if default is _MISSING:
425 raise KeyError(k)
426 return default
427 values = super().__getitem__(k)
428 v = values.pop()
429 if not values:
430 super().__delitem__(k)
431 return v
433 def _remove(self, k):
434 values = self._map[k]
435 cell = values.pop()
436 cell[PREV][NEXT], cell[NEXT][PREV] = cell[NEXT], cell[PREV]
437 if not values:
438 del self._map[k]
440 def _remove_all(self, k):
441 values = self._map[k]
442 while values:
443 cell = values.pop()
444 cell[PREV][NEXT], cell[NEXT][PREV] = cell[NEXT], cell[PREV]
445 del self._map[k]
447 def iteritems(self, multi=False):
448 """Iterate over the OMD's items in insertion order. By default,
449 yields only the most-recently inserted value for each key. Set
450 *multi* to ``True`` to get all inserted items.
451 """
452 root = self.root
453 curr = root[NEXT]
454 if multi:
455 while curr is not root:
456 yield curr[KEY], curr[VALUE]
457 curr = curr[NEXT]
458 else:
459 for key in self.iterkeys():
460 yield key, self[key]
462 def iterkeys(self, multi=False):
463 """Iterate over the OMD's keys in insertion order. By default, yields
464 each key once, according to the most recent insertion. Set
465 *multi* to ``True`` to get all keys, including duplicates, in
466 insertion order.
467 """
468 root = self.root
469 curr = root[NEXT]
470 if multi:
471 while curr is not root:
472 yield curr[KEY]
473 curr = curr[NEXT]
474 else:
475 yielded = set()
476 yielded_add = yielded.add
477 while curr is not root:
478 k = curr[KEY]
479 if k not in yielded:
480 yielded_add(k)
481 yield k
482 curr = curr[NEXT]
484 def itervalues(self, multi=False):
485 """Iterate over the OMD's values in insertion order. By default,
486 yields the most-recently inserted value per unique key. Set
487 *multi* to ``True`` to get all values according to insertion
488 order.
489 """
490 for k, v in self.iteritems(multi=multi):
491 yield v
493 def todict(self, multi=False):
494 """Gets a basic :class:`dict` of the items in this dictionary. Keys
495 are the same as the OMD, values are the most recently inserted
496 values for each key.
498 Setting the *multi* arg to ``True`` is yields the same
499 result as calling :class:`dict` on the OMD, except that all the
500 value lists are copies that can be safely mutated.
501 """
502 if multi:
503 return {k: self.getlist(k) for k in self}
504 return {k: self[k] for k in self}
506 def sorted(self, key=None, reverse=False):
507 """Similar to the built-in :func:`sorted`, except this method returns
508 a new :class:`OrderedMultiDict` sorted by the provided key
509 function, optionally reversed.
511 Args:
512 key (callable): A callable to determine the sort key of
513 each element. The callable should expect an **item**
514 (key-value pair tuple).
515 reverse (bool): Set to ``True`` to reverse the ordering.
517 >>> omd = OrderedMultiDict(zip(range(3), range(3)))
518 >>> omd.sorted(reverse=True)
519 OrderedMultiDict([(2, 2), (1, 1), (0, 0)])
521 Note that the key function receives an **item** (key-value
522 tuple), so the recommended signature looks like:
524 >>> omd = OrderedMultiDict(zip('hello', 'world'))
525 >>> omd.sorted(key=lambda i: i[1]) # i[0] is the key, i[1] is the val
526 OrderedMultiDict([('o', 'd'), ('l', 'l'), ('e', 'o'), ('l', 'r'), ('h', 'w')])
527 """
528 cls = self.__class__
529 return cls(sorted(self.iteritems(multi=True), key=key, reverse=reverse))
531 def sortedvalues(self, key=None, reverse=False):
532 """Returns a copy of the :class:`OrderedMultiDict` with the same keys
533 in the same order as the original OMD, but the values within
534 each keyspace have been sorted according to *key* and
535 *reverse*.
537 Args:
538 key (callable): A single-argument callable to determine
539 the sort key of each element. The callable should expect
540 an **item** (key-value pair tuple).
541 reverse (bool): Set to ``True`` to reverse the ordering.
543 >>> omd = OrderedMultiDict()
544 >>> omd.addlist('even', [6, 2])
545 >>> omd.addlist('odd', [1, 5])
546 >>> omd.add('even', 4)
547 >>> omd.add('odd', 3)
548 >>> somd = omd.sortedvalues()
549 >>> somd.getlist('even')
550 [2, 4, 6]
551 >>> somd.keys(multi=True) == omd.keys(multi=True)
552 True
553 >>> omd == somd
554 False
555 >>> somd
556 OrderedMultiDict([('even', 2), ('even', 4), ('odd', 1), ('odd', 3), ('even', 6), ('odd', 5)])
558 As demonstrated above, contents and key order are
559 retained. Only value order changes.
560 """
561 try:
562 superself_iteritems = super().iteritems()
563 except AttributeError:
564 superself_iteritems = super().items()
565 # (not reverse) because they pop off in reverse order for reinsertion
566 sorted_val_map = {k: sorted(v, key=key, reverse=(not reverse))
567 for k, v in superself_iteritems}
568 ret = self.__class__()
569 for k in self.iterkeys(multi=True):
570 ret.add(k, sorted_val_map[k].pop())
571 return ret
573 def inverted(self):
574 """Returns a new :class:`OrderedMultiDict` with values and keys
575 swapped, like creating dictionary transposition or reverse
576 index. Insertion order is retained and all keys and values
577 are represented in the output.
579 >>> omd = OMD([(0, 2), (1, 2)])
580 >>> omd.inverted().getlist(2)
581 [0, 1]
583 Inverting twice yields a copy of the original:
585 >>> omd.inverted().inverted()
586 OrderedMultiDict([(0, 2), (1, 2)])
587 """
588 return self.__class__((v, k) for k, v in self.iteritems(multi=True))
590 def counts(self):
591 """Returns a mapping from key to number of values inserted under that
592 key. Like :py:class:`collections.Counter`, but returns a new
593 :class:`OrderedMultiDict`.
594 """
595 # Returns an OMD because Counter/OrderedDict may not be
596 # available, and neither Counter nor dict maintain order.
597 super_getitem = super().__getitem__
598 return self.__class__((k, len(super_getitem(k))) for k in self)
600 def keys(self, multi=False):
601 """Returns a list containing the output of :meth:`iterkeys`. See
602 that method's docs for more details.
603 """
604 return list(self.iterkeys(multi=multi))
606 def values(self, multi=False):
607 """Returns a list containing the output of :meth:`itervalues`. See
608 that method's docs for more details.
609 """
610 return list(self.itervalues(multi=multi))
612 def items(self, multi=False):
613 """Returns a list containing the output of :meth:`iteritems`. See
614 that method's docs for more details.
615 """
616 return list(self.iteritems(multi=multi))
618 def __iter__(self):
619 return self.iterkeys()
621 def __reversed__(self):
622 root = self.root
623 curr = root[PREV]
624 lengths = {}
625 lengths_sd = lengths.setdefault
626 get_values = super().__getitem__
627 while curr is not root:
628 k = curr[KEY]
629 vals = get_values(k)
630 if lengths_sd(k, 1) == len(vals):
631 yield k
632 lengths[k] += 1
633 curr = curr[PREV]
635 def __repr__(self):
636 cn = self.__class__.__name__
637 kvs = ', '.join([repr((k, v)) for k, v in self.iteritems(multi=True)])
638 return f'{cn}([{kvs}])'
640 def viewkeys(self):
641 "OMD.viewkeys() -> a set-like object providing a view on OMD's keys"
642 return KeysView(self)
644 def viewvalues(self):
645 "OMD.viewvalues() -> an object providing a view on OMD's values"
646 return ValuesView(self)
648 def viewitems(self):
649 "OMD.viewitems() -> a set-like object providing a view on OMD's items"
650 return ItemsView(self)
653# A couple of convenient aliases
654OMD = OrderedMultiDict
655MultiDict = OrderedMultiDict
658class FastIterOrderedMultiDict(OrderedMultiDict):
659 """An OrderedMultiDict backed by a skip list. Iteration over keys
660 is faster and uses constant memory but adding duplicate key-value
661 pairs is slower. Brainchild of Mark Williams.
662 """
663 def _clear_ll(self):
664 # TODO: always reset objects? (i.e., no else block below)
665 try:
666 _map = self._map
667 except AttributeError:
668 _map = self._map = {}
669 self.root = []
670 _map.clear()
671 self.root[:] = [self.root, self.root,
672 None, None,
673 self.root, self.root]
675 def _insert(self, k, v):
676 root = self.root
677 empty = []
678 cells = self._map.setdefault(k, empty)
679 last = root[PREV]
681 if cells is empty:
682 cell = [last, root,
683 k, v,
684 last, root]
685 # was the last one skipped?
686 if last[SPREV][SNEXT] is root:
687 last[SPREV][SNEXT] = cell
688 last[NEXT] = last[SNEXT] = root[PREV] = root[SPREV] = cell
689 cells.append(cell)
690 else:
691 # if the previous was skipped, go back to the cell that
692 # skipped it
693 sprev = last[SPREV] if (last[SPREV][SNEXT] is not last) else last
694 cell = [last, root,
695 k, v,
696 sprev, root]
697 # skip me
698 last[SNEXT] = root
699 last[NEXT] = root[PREV] = root[SPREV] = cell
700 cells.append(cell)
702 def _remove(self, k):
703 cells = self._map[k]
704 cell = cells.pop()
705 if not cells:
706 del self._map[k]
707 cell[PREV][SNEXT] = cell[SNEXT]
709 if cell[PREV][SPREV][SNEXT] is cell:
710 cell[PREV][SPREV][SNEXT] = cell[NEXT]
711 elif cell[SNEXT] is cell[NEXT]:
712 cell[SPREV][SNEXT], cell[SNEXT][SPREV] = cell[SNEXT], cell[SPREV]
714 cell[PREV][NEXT], cell[NEXT][PREV] = cell[NEXT], cell[PREV]
716 def _remove_all(self, k):
717 cells = self._map.pop(k)
718 while cells:
719 cell = cells.pop()
720 if cell[PREV][SPREV][SNEXT] is cell:
721 cell[PREV][SPREV][SNEXT] = cell[NEXT]
722 elif cell[SNEXT] is cell[NEXT]:
723 cell[SPREV][SNEXT], cell[SNEXT][SPREV] = cell[SNEXT], cell[SPREV]
725 cell[PREV][NEXT], cell[NEXT][PREV] = cell[NEXT], cell[PREV]
726 cell[PREV][SNEXT] = cell[SNEXT]
728 def iteritems(self, multi=False):
729 next_link = NEXT if multi else SNEXT
730 root = self.root
731 curr = root[next_link]
732 while curr is not root:
733 yield curr[KEY], curr[VALUE]
734 curr = curr[next_link]
736 def iterkeys(self, multi=False):
737 next_link = NEXT if multi else SNEXT
738 root = self.root
739 curr = root[next_link]
740 while curr is not root:
741 yield curr[KEY]
742 curr = curr[next_link]
744 def __reversed__(self):
745 root = self.root
746 curr = root[PREV]
747 while curr is not root:
748 if curr[SPREV][SNEXT] is not curr:
749 curr = curr[SPREV]
750 if curr is root:
751 break
752 yield curr[KEY]
753 curr = curr[PREV]
756_OTO_INV_MARKER = object()
757_OTO_UNIQUE_MARKER = object()
760class OneToOne(dict):
761 """Implements a one-to-one mapping dictionary. In addition to
762 inheriting from and behaving exactly like the builtin
763 :class:`dict`, all values are automatically added as keys on a
764 reverse mapping, available as the `inv` attribute. This
765 arrangement keeps key and value namespaces distinct.
767 Basic operations are intuitive:
769 >>> oto = OneToOne({'a': 1, 'b': 2})
770 >>> print(oto['a'])
771 1
772 >>> print(oto.inv[1])
773 a
774 >>> len(oto)
775 2
777 Overwrites happens in both directions:
779 >>> oto.inv[1] = 'c'
780 >>> print(oto.get('a'))
781 None
782 >>> len(oto)
783 2
785 For a very similar project, with even more one-to-one
786 functionality, check out `bidict <https://github.com/jab/bidict>`_.
787 """
788 __slots__ = ('inv',)
790 def __init__(self, *a, **kw):
791 raise_on_dupe = False
792 if a:
793 if a[0] is _OTO_INV_MARKER:
794 self.inv = a[1]
795 dict.__init__(self, [(v, k) for k, v in self.inv.items()])
796 return
797 elif a[0] is _OTO_UNIQUE_MARKER:
798 a, raise_on_dupe = a[1:], True
800 dict.__init__(self, *a, **kw)
801 self.inv = self.__class__(_OTO_INV_MARKER, self)
803 if len(self) == len(self.inv):
804 # if lengths match, that means everything's unique
805 return
807 if not raise_on_dupe:
808 dict.clear(self)
809 dict.update(self, [(v, k) for k, v in self.inv.items()])
810 return
812 # generate an error message if the values aren't 1:1
814 val_multidict = {}
815 for k, v in self.items():
816 val_multidict.setdefault(v, []).append(k)
818 dupes = {v: k_list for v, k_list in
819 val_multidict.items() if len(k_list) > 1}
821 raise ValueError('expected unique values, got multiple keys for'
822 ' the following values: %r' % dupes)
824 @classmethod
825 def unique(cls, *a, **kw):
826 """This alternate constructor for OneToOne will raise an exception
827 when input values overlap. For instance:
829 >>> OneToOne.unique({'a': 1, 'b': 1})
830 Traceback (most recent call last):
831 ...
832 ValueError: expected unique values, got multiple keys for the following values: ...
834 This even works across inputs:
836 >>> a_dict = {'a': 2}
837 >>> OneToOne.unique(a_dict, b=2)
838 Traceback (most recent call last):
839 ...
840 ValueError: expected unique values, got multiple keys for the following values: ...
841 """
842 return cls(_OTO_UNIQUE_MARKER, *a, **kw)
844 def __setitem__(self, key, val):
845 hash(val) # ensure val is a valid key
846 if key in self:
847 dict.__delitem__(self.inv, self[key])
848 if val in self.inv:
849 del self.inv[val]
850 dict.__setitem__(self, key, val)
851 dict.__setitem__(self.inv, val, key)
853 def __delitem__(self, key):
854 dict.__delitem__(self.inv, self[key])
855 dict.__delitem__(self, key)
857 def clear(self):
858 dict.clear(self)
859 dict.clear(self.inv)
861 def copy(self):
862 return self.__class__(self)
864 def pop(self, key, default=_MISSING):
865 if key in self:
866 dict.__delitem__(self.inv, self[key])
867 return dict.pop(self, key)
868 if default is not _MISSING:
869 return default
870 raise KeyError()
872 def popitem(self):
873 key, val = dict.popitem(self)
874 dict.__delitem__(self.inv, val)
875 return key, val
877 def setdefault(self, key, default=None):
878 if key not in self:
879 self[key] = default
880 return self[key]
882 def update(self, dict_or_iterable, **kw):
883 keys_vals = []
884 if isinstance(dict_or_iterable, dict):
885 for val in dict_or_iterable.values():
886 hash(val)
887 keys_vals = list(dict_or_iterable.items())
888 else:
889 for key, val in dict_or_iterable:
890 hash(key)
891 hash(val)
892 keys_vals = list(dict_or_iterable)
893 for val in kw.values():
894 hash(val)
895 keys_vals.extend(kw.items())
896 for key, val in keys_vals:
897 self[key] = val
899 def __repr__(self):
900 cn = self.__class__.__name__
901 dict_repr = dict.__repr__(self)
902 return f"{cn}({dict_repr})"
905# marker for the secret handshake used internally to set up the invert ManyToMany
906_PAIRING = object()
909class ManyToMany:
910 """
911 a dict-like entity that represents a many-to-many relationship
912 between two groups of objects
914 behaves like a dict-of-tuples; also has .inv which is kept
915 up to date which is a dict-of-tuples in the other direction
917 also, can be used as a directed graph among hashable python objects
918 """
919 def __init__(self, items=None):
920 self.data = {}
921 if type(items) is tuple and items and items[0] is _PAIRING:
922 self.inv = items[1]
923 else:
924 self.inv = self.__class__((_PAIRING, self))
925 if items:
926 self.update(items)
927 return
929 def get(self, key, default=frozenset()):
930 try:
931 return self[key]
932 except KeyError:
933 return default
935 def __getitem__(self, key):
936 return frozenset(self.data[key])
938 def __setitem__(self, key, vals):
939 vals = set(vals)
940 if key in self:
941 to_remove = self.data[key] - vals
942 vals -= self.data[key]
943 for val in to_remove:
944 self.remove(key, val)
945 for val in vals:
946 self.add(key, val)
948 def __delitem__(self, key):
949 for val in self.data.pop(key):
950 self.inv.data[val].remove(key)
951 if not self.inv.data[val]:
952 del self.inv.data[val]
954 def update(self, iterable):
955 """given an iterable of (key, val), add them all"""
956 if type(iterable) is type(self):
957 other = iterable
958 for k in other.data:
959 if k not in self.data:
960 self.data[k] = other.data[k]
961 else:
962 self.data[k].update(other.data[k])
963 for k in other.inv.data:
964 if k not in self.inv.data:
965 self.inv.data[k] = other.inv.data[k]
966 else:
967 self.inv.data[k].update(other.inv.data[k])
968 elif callable(getattr(iterable, 'keys', None)):
969 for k in iterable.keys():
970 self.add(k, iterable[k])
971 else:
972 for key, val in iterable:
973 self.add(key, val)
974 return
976 def add(self, key, val):
977 if key not in self.data:
978 self.data[key] = set()
979 self.data[key].add(val)
980 if val not in self.inv.data:
981 self.inv.data[val] = set()
982 self.inv.data[val].add(key)
984 def remove(self, key, val):
985 self.data[key].remove(val)
986 if not self.data[key]:
987 del self.data[key]
988 self.inv.data[val].remove(key)
989 if not self.inv.data[val]:
990 del self.inv.data[val]
992 def replace(self, key, newkey):
993 """
994 replace instances of key by newkey
995 """
996 if key not in self.data:
997 return
998 self.data[newkey] = fwdset = self.data.pop(key)
999 for val in fwdset:
1000 revset = self.inv.data[val]
1001 revset.remove(key)
1002 revset.add(newkey)
1004 def iteritems(self):
1005 for key in self.data:
1006 for val in self.data[key]:
1007 yield key, val
1009 def keys(self):
1010 return self.data.keys()
1012 def __contains__(self, key):
1013 return key in self.data
1015 def __iter__(self):
1016 return self.data.__iter__()
1018 def __len__(self):
1019 return self.data.__len__()
1021 def __eq__(self, other):
1022 return type(self) == type(other) and self.data == other.data
1024 def __repr__(self):
1025 cn = self.__class__.__name__
1026 return f'{cn}({list(self.iteritems())!r})'
1029def subdict(d, keep=None, drop=None):
1030 """Compute the "subdictionary" of a dict, *d*.
1032 A subdict is to a dict what a subset is a to set. If *A* is a
1033 subdict of *B*, that means that all keys of *A* are present in
1034 *B*.
1036 Returns a new dict with any keys in *drop* removed, and any keys
1037 in *keep* still present, provided they were in the original
1038 dict. *keep* defaults to all keys, *drop* defaults to empty, so
1039 without one of these arguments, calling this function is
1040 equivalent to calling ``dict()``.
1042 >>> from pprint import pprint as pp
1043 >>> pp(subdict({'a': 1, 'b': 2}))
1044 {'a': 1, 'b': 2}
1045 >>> subdict({'a': 1, 'b': 2, 'c': 3}, drop=['b', 'c'])
1046 {'a': 1}
1047 >>> pp(subdict({'a': 1, 'b': 2, 'c': 3}, keep=['a', 'c']))
1048 {'a': 1, 'c': 3}
1050 """
1051 if keep is None:
1052 keep = d.keys()
1053 if drop is None:
1054 drop = []
1056 keys = set(keep) - set(drop)
1058 return type(d)([(k, v) for k, v in d.items() if k in keys])
1061class FrozenHashError(TypeError):
1062 pass
1065class FrozenDict(dict):
1066 """An immutable dict subtype that is hashable and can itself be used
1067 as a :class:`dict` key or :class:`set` entry. What
1068 :class:`frozenset` is to :class:`set`, FrozenDict is to
1069 :class:`dict`.
1071 There was once an attempt to introduce such a type to the standard
1072 library, but it was rejected: `PEP 416 <https://www.python.org/dev/peps/pep-0416/>`_.
1074 Because FrozenDict is a :class:`dict` subtype, it automatically
1075 works everywhere a dict would, including JSON serialization.
1077 """
1078 __slots__ = ('_hash',)
1080 def updated(self, *a, **kw):
1081 """Make a copy and add items from a dictionary or iterable (and/or
1082 keyword arguments), overwriting values under an existing
1083 key. See :meth:`dict.update` for more details.
1084 """
1085 data = dict(self)
1086 data.update(*a, **kw)
1087 return type(self)(data)
1089 @classmethod
1090 def fromkeys(cls, keys, value=None):
1091 # one of the lesser known and used/useful dict methods
1092 return cls(dict.fromkeys(keys, value))
1094 def __repr__(self):
1095 cn = self.__class__.__name__
1096 return f'{cn}({dict.__repr__(self)})'
1098 def __reduce_ex__(self, protocol):
1099 return type(self), (dict(self),)
1101 def __hash__(self):
1102 try:
1103 ret = self._hash
1104 except AttributeError:
1105 try:
1106 ret = self._hash = hash(frozenset(self.items()))
1107 except Exception as e:
1108 ret = self._hash = FrozenHashError(e)
1110 if ret.__class__ is FrozenHashError:
1111 raise ret
1113 return ret
1115 def __copy__(self):
1116 return self # immutable types don't copy, see tuple's behavior
1118 # block everything else
1119 def _raise_frozen_typeerror(self, *a, **kw):
1120 "raises a TypeError, because FrozenDicts are immutable"
1121 raise TypeError('%s object is immutable' % self.__class__.__name__)
1123 __ior__ = __setitem__ = __delitem__ = update = _raise_frozen_typeerror
1124 setdefault = pop = popitem = clear = _raise_frozen_typeerror
1126 del _raise_frozen_typeerror
1129# end dictutils.py