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