Mercurial > repos > shellac > guppy_basecaller

comparison env/lib/python3.7/site-packages/boltons/dictutils.py @ 0:26e78fe6e8c4 draft

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