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