codekingpro/portable-devtools
114k
1'''This module implements specialized container datatypes providing2alternatives to Python's general purpose built-in containers, dict,3list, set, and tuple.4 5* namedtuple factory function for creating tuple subclasses with named fields6* deque list-like container with fast appends and pops on either end7* ChainMap dict-like class for creating a single view of multiple mappings8* Counter dict subclass for counting hashable objects9* OrderedDict dict subclass that remembers the order entries were added10* defaultdict dict subclass that calls a factory function to supply missing values11* UserDict wrapper around dictionary objects for easier dict subclassing12* UserList wrapper around list objects for easier list subclassing13* UserString wrapper around string objects for easier string subclassing14 15'''16 17__all__ = [18 'ChainMap',19 'Counter',20 'OrderedDict',21 'UserDict',22 'UserList',23 'UserString',24 'defaultdict',25 'deque',26 'namedtuple',27]28 29import _collections_abc30import sys as _sys31 32_sys.modules['collections.abc'] = _collections_abc33abc = _collections_abc34 35from itertools import chain as _chain36from itertools import repeat as _repeat37from itertools import starmap as _starmap38from keyword import iskeyword as _iskeyword39from operator import eq as _eq40from operator import itemgetter as _itemgetter41from reprlib import recursive_repr as _recursive_repr42from _weakref import proxy as _proxy43 44try:45 from _collections import deque46except ImportError:47 pass48else:49 _collections_abc.MutableSequence.register(deque)50 51try:52 # Expose _deque_iterator to support pickling deque iterators53 from _collections import _deque_iterator # noqa: F40154except ImportError:55 pass56 57try:58 from _collections import defaultdict59except ImportError:60 pass61 62heapq = None # Lazily imported63 64 65################################################################################66### OrderedDict67################################################################################68 69class _OrderedDictKeysView(_collections_abc.KeysView):70 71 def __reversed__(self):72 yield from reversed(self._mapping)73 74class _OrderedDictItemsView(_collections_abc.ItemsView):75 76 def __reversed__(self):77 for key in reversed(self._mapping):78 yield (key, self._mapping[key])79 80class _OrderedDictValuesView(_collections_abc.ValuesView):81 82 def __reversed__(self):83 for key in reversed(self._mapping):84 yield self._mapping[key]85 86class _Link(object):87 __slots__ = 'prev', 'next', 'key', '__weakref__'88 89class OrderedDict(dict):90 'Dictionary that remembers insertion order'91 # An inherited dict maps keys to values.92 # The inherited dict provides __getitem__, __len__, __contains__, and get.93 # The remaining methods are order-aware.94 # Big-O running times for all methods are the same as regular dictionaries.95 96 # The internal self.__map dict maps keys to links in a doubly linked list.97 # The circular doubly linked list starts and ends with a sentinel element.98 # The sentinel element never gets deleted (this simplifies the algorithm).99 # The sentinel is in self.__hardroot with a weakref proxy in self.__root.100 # The prev links are weakref proxies (to prevent circular references).101 # Individual links are kept alive by the hard reference in self.__map.102 # Those hard references disappear when a key is deleted from an OrderedDict.103 104 def __new__(cls, /, *args, **kwds):105 "Create the ordered dict object and set up the underlying structures."106 self = dict.__new__(cls)107 self.__hardroot = _Link()108 self.__root = root = _proxy(self.__hardroot)109 root.prev = root.next = root110 self.__map = {}111 return self112 113 def __init__(self, other=(), /, **kwds):114 '''Initialize an ordered dictionary. The signature is the same as115 regular dictionaries. Keyword argument order is preserved.116 '''117 self.__update(other, **kwds)118 119 def __setitem__(self, key, value,120 dict_setitem=dict.__setitem__, proxy=_proxy, Link=_Link):121 'od.__setitem__(i, y) <==> od[i]=y'122 # Setting a new item creates a new link at the end of the linked list,123 # and the inherited dictionary is updated with the new key/value pair.124 if key not in self:125 self.__map[key] = link = Link()126 root = self.__root127 last = root.prev128 link.prev, link.next, link.key = last, root, key129 last.next = link130 root.prev = proxy(link)131 dict_setitem(self, key, value)132 133 def __delitem__(self, key, dict_delitem=dict.__delitem__):134 'od.__delitem__(y) <==> del od[y]'135 # Deleting an existing item uses self.__map to find the link which gets136 # removed by updating the links in the predecessor and successor nodes.137 dict_delitem(self, key)138 link = self.__map.pop(key)139 link_prev = link.prev140 link_next = link.next141 link_prev.next = link_next142 link_next.prev = link_prev143 link.prev = None144 link.next = None145 146 def __iter__(self):147 'od.__iter__() <==> iter(od)'148 # Traverse the linked list in order.149 root = self.__root150 curr = root.next151 while curr is not root:152 yield curr.key153 curr = curr.next154 155 def __reversed__(self):156 'od.__reversed__() <==> reversed(od)'157 # Traverse the linked list in reverse order.158 root = self.__root159 curr = root.prev160 while curr is not root:161 yield curr.key162 curr = curr.prev163 164 def clear(self):165 'od.clear() -> None. Remove all items from od.'166 root = self.__root167 root.prev = root.next = root168 self.__map.clear()169 dict.clear(self)170 171 def popitem(self, last=True):172 '''Remove and return a (key, value) pair from the dictionary.173 174 Pairs are returned in LIFO order if last is true or FIFO order if false.175 '''176 if not self:177 raise KeyError('dictionary is empty')178 root = self.__root179 if last:180 link = root.prev181 link_prev = link.prev182 link_prev.next = root183 root.prev = link_prev184 else:185 link = root.next186 link_next = link.next187 root.next = link_next188 link_next.prev = root189 key = link.key190 del self.__map[key]191 value = dict.pop(self, key)192 return key, value193 194 def move_to_end(self, key, last=True):195 '''Move an existing element to the end (or beginning if last is false).196 197 Raise KeyError if the element does not exist.198 '''199 link = self.__map[key]200 link_prev = link.prev201 link_next = link.next202 soft_link = link_next.prev203 link_prev.next = link_next204 link_next.prev = link_prev205 root = self.__root206 if last:207 last = root.prev208 link.prev = last209 link.next = root210 root.prev = soft_link211 last.next = link212 else:213 first = root.next214 link.prev = root215 link.next = first216 first.prev = soft_link217 root.next = link218 219 def __sizeof__(self):220 sizeof = _sys.getsizeof221 n = len(self) + 1 # number of links including root222 size = sizeof(self.__dict__) # instance dictionary223 size += sizeof(self.__map) * 2 # internal dict and inherited dict224 size += sizeof(self.__hardroot) * n # link objects225 size += sizeof(self.__root) * n # proxy objects226 return size227 228 update = __update = _collections_abc.MutableMapping.update229 230 def keys(self):231 "D.keys() -> a set-like object providing a view on D's keys"232 return _OrderedDictKeysView(self)233 234 def items(self):235 "D.items() -> a set-like object providing a view on D's items"236 return _OrderedDictItemsView(self)237 238 def values(self):239 "D.values() -> an object providing a view on D's values"240 return _OrderedDictValuesView(self)241 242 __ne__ = _collections_abc.MutableMapping.__ne__243 244 __marker = object()245 246 def pop(self, key, default=__marker):247 '''od.pop(k[,d]) -> v, remove specified key and return the corresponding248 value. If key is not found, d is returned if given, otherwise KeyError249 is raised.250 251 '''252 marker = self.__marker253 result = dict.pop(self, key, marker)254 if result is not marker:255 # The same as in __delitem__().256 link = self.__map.pop(key)257 link_prev = link.prev258 link_next = link.next259 link_prev.next = link_next260 link_next.prev = link_prev261 link.prev = None262 link.next = None263 return result264 if default is marker:265 raise KeyError(key)266 return default267 268 def setdefault(self, key, default=None):269 '''Insert key with a value of default if key is not in the dictionary.270 271 Return the value for key if key is in the dictionary, else default.272 '''273 if key in self:274 return self[key]275 self[key] = default276 return default277 278 @_recursive_repr()279 def __repr__(self):280 'od.__repr__() <==> repr(od)'281 if not self:282 return '%s()' % (self.__class__.__name__,)283 return '%s(%r)' % (self.__class__.__name__, dict(self.items()))284 285 def __reduce__(self):286 'Return state information for pickling'287 state = self.__getstate__()288 if state:289 if isinstance(state, tuple):290 state, slots = state291 else:292 slots = {}293 state = state.copy()294 slots = slots.copy()295 for k in vars(OrderedDict()):296 state.pop(k, None)297 slots.pop(k, None)298 if slots:299 state = state, slots300 else:301 state = state or None302 return self.__class__, (), state, None, iter(self.items())303 304 def copy(self):305 'od.copy() -> a shallow copy of od'306 return self.__class__(self)307 308 @classmethod309 def fromkeys(cls, iterable, value=None):310 '''Create a new ordered dictionary with keys from iterable and values set to value.311 '''312 self = cls()313 for key in iterable:314 self[key] = value315 return self316 317 def __eq__(self, other):318 '''od.__eq__(y) <==> od==y. Comparison to another OD is order-sensitive319 while comparison to a regular mapping is order-insensitive.320 321 '''322 if isinstance(other, OrderedDict):323 return dict.__eq__(self, other) and all(map(_eq, self, other))324 return dict.__eq__(self, other)325 326 def __ior__(self, other):327 self.update(other)328 return self329 330 def __or__(self, other):331 if not isinstance(other, dict):332 return NotImplemented333 new = self.__class__(self)334 new.update(other)335 return new336 337 def __ror__(self, other):338 if not isinstance(other, dict):339 return NotImplemented340 new = self.__class__(other)341 new.update(self)342 return new343 344 345try:346 from _collections import OrderedDict347except ImportError:348 # Leave the pure Python version in place.349 pass350 351 352################################################################################353### namedtuple354################################################################################355 356try:357 from _collections import _tuplegetter358except ImportError:359 _tuplegetter = lambda index, doc: property(_itemgetter(index), doc=doc)360 361def namedtuple(typename, field_names, *, rename=False, defaults=None, module=None):362 """Returns a new subclass of tuple with named fields.363 364 >>> Point = namedtuple('Point', ['x', 'y'])365 >>> Point.__doc__ # docstring for the new class366 'Point(x, y)'367 >>> p = Point(11, y=22) # instantiate with positional args or keywords368 >>> p[0] + p[1] # indexable like a plain tuple369 33370 >>> x, y = p # unpack like a regular tuple371 >>> x, y372 (11, 22)373 >>> p.x + p.y # fields also accessible by name374 33375 >>> d = p._asdict() # convert to a dictionary376 >>> d['x']377 11378 >>> Point(**d) # convert from a dictionary379 Point(x=11, y=22)380 >>> p._replace(x=100) # _replace() is like str.replace() but targets named fields381 Point(x=100, y=22)382 383 """384 385 # Validate the field names. At the user's option, either generate an error386 # message or automatically replace the field name with a valid name.387 if isinstance(field_names, str):388 field_names = field_names.replace(',', ' ').split()389 field_names = list(map(str, field_names))390 typename = _sys.intern(str(typename))391 392 if rename:393 seen = set()394 for index, name in enumerate(field_names):395 if (not name.isidentifier()396 or _iskeyword(name)397 or name.startswith('_')398 or name in seen):399 field_names[index] = f'_{index}'400 seen.add(name)401 402 for name in [typename] + field_names:403 if type(name) is not str:404 raise TypeError('Type names and field names must be strings')405 if not name.isidentifier():406 raise ValueError('Type names and field names must be valid '407 f'identifiers: {name!r}')408 if _iskeyword(name):409 raise ValueError('Type names and field names cannot be a '410 f'keyword: {name!r}')411 412 seen = set()413 for name in field_names:414 if name.startswith('_') and not rename:415 raise ValueError('Field names cannot start with an underscore: '416 f'{name!r}')417 if name in seen:418 raise ValueError(f'Encountered duplicate field name: {name!r}')419 seen.add(name)420 421 field_defaults = {}422 if defaults is not None:423 defaults = tuple(defaults)424 if len(defaults) > len(field_names):425 raise TypeError('Got more default values than field names')426 field_defaults = dict(reversed(list(zip(reversed(field_names),427 reversed(defaults)))))428 429 # Variables used in the methods and docstrings430 field_names = tuple(map(_sys.intern, field_names))431 num_fields = len(field_names)432 arg_list = ', '.join(field_names)433 if num_fields == 1:434 arg_list += ','435 repr_fmt = '(' + ', '.join(f'{name}=%r' for name in field_names) + ')'436 tuple_new = tuple.__new__437 _dict, _tuple, _len, _map, _zip = dict, tuple, len, map, zip438 439 # Create all the named tuple methods to be added to the class namespace440 441 namespace = {442 '_tuple_new': tuple_new,443 '__builtins__': {},444 '__name__': f'namedtuple_{typename}',445 }446 code = f'lambda _cls, {arg_list}: _tuple_new(_cls, ({arg_list}))'447 __new__ = eval(code, namespace)448 __new__.__name__ = '__new__'449 __new__.__doc__ = f'Create new instance of {typename}({arg_list})'450 if defaults is not None:451 __new__.__defaults__ = defaults452 453 @classmethod454 def _make(cls, iterable):455 result = tuple_new(cls, iterable)456 if _len(result) != num_fields:457 raise TypeError(f'Expected {num_fields} arguments, got {len(result)}')458 return result459 460 _make.__func__.__doc__ = (f'Make a new {typename} object from a sequence '461 'or iterable')462 463 def _replace(self, /, **kwds):464 result = self._make(_map(kwds.pop, field_names, self))465 if kwds:466 raise TypeError(f'Got unexpected field names: {list(kwds)!r}')467 return result468 469 _replace.__doc__ = (f'Return a new {typename} object replacing specified '470 'fields with new values')471 472 def __repr__(self):473 'Return a nicely formatted representation string'474 return self.__class__.__name__ + repr_fmt % self475 476 def _asdict(self):477 'Return a new dict which maps field names to their values.'478 return _dict(_zip(self._fields, self))479 480 def __getnewargs__(self):481 'Return self as a plain tuple. Used by copy and pickle.'482 return _tuple(self)483 484 # Modify function metadata to help with introspection and debugging485 for method in (486 __new__,487 _make.__func__,488 _replace,489 __repr__,490 _asdict,491 __getnewargs__,492 ):493 method.__qualname__ = f'{typename}.{method.__name__}'494 495 # Build-up the class namespace dictionary496 # and use type() to build the result class497 class_namespace = {498 '__doc__': f'{typename}({arg_list})',499 '__slots__': (),500 '_fields': field_names,501 '_field_defaults': field_defaults,502 '__new__': __new__,503 '_make': _make,504 '__replace__': _replace,505 '_replace': _replace,506 '__repr__': __repr__,507 '_asdict': _asdict,508 '__getnewargs__': __getnewargs__,509 '__match_args__': field_names,510 }511 for index, name in enumerate(field_names):512 doc = _sys.intern(f'Alias for field number {index}')513 class_namespace[name] = _tuplegetter(index, doc)514 515 result = type(typename, (tuple,), class_namespace)516 517 # For pickling to work, the __module__ variable needs to be set to the frame518 # where the named tuple is created. Bypass this step in environments where519 # sys._getframe is not defined (Jython for example) or sys._getframe is not520 # defined for arguments greater than 0 (IronPython), or where the user has521 # specified a particular module.522 if module is None:523 try:524 module = _sys._getframemodulename(1) or '__main__'525 except AttributeError:526 try:527 module = _sys._getframe(1).f_globals.get('__name__', '__main__')528 except (AttributeError, ValueError):529 pass530 if module is not None:531 result.__module__ = module532 533 return result534 535 536########################################################################537### Counter538########################################################################539 540def _count_elements(mapping, iterable):541 'Tally elements from the iterable.'542 mapping_get = mapping.get543 for elem in iterable:544 mapping[elem] = mapping_get(elem, 0) + 1545 546try: # Load C helper function if available547 from _collections import _count_elements548except ImportError:549 pass550 551class Counter(dict):552 '''Dict subclass for counting hashable items. Sometimes called a bag553 or multiset. Elements are stored as dictionary keys and their counts554 are stored as dictionary values.555 556 >>> c = Counter('abcdeabcdabcaba') # count elements from a string557 558 >>> c.most_common(3) # three most common elements559 [('a', 5), ('b', 4), ('c', 3)]560 >>> sorted(c) # list all unique elements561 ['a', 'b', 'c', 'd', 'e']562 >>> ''.join(sorted(c.elements())) # list elements with repetitions563 'aaaaabbbbcccdde'564 >>> sum(c.values()) # total of all counts565 15566 567 >>> c['a'] # count of letter 'a'568 5569 >>> for elem in 'shazam': # update counts from an iterable570 ... c[elem] += 1 # by adding 1 to each element's count571 >>> c['a'] # now there are seven 'a'572 7573 >>> del c['b'] # remove all 'b'574 >>> c['b'] # now there are zero 'b'575 0576 577 >>> d = Counter('simsalabim') # make another counter578 >>> c.update(d) # add in the second counter579 >>> c['a'] # now there are nine 'a'580 9581 582 >>> c.clear() # empty the counter583 >>> c584 Counter()585 586 Note: If a count is set to zero or reduced to zero, it will remain587 in the counter until the entry is deleted or the counter is cleared:588 589 >>> c = Counter('aaabbc')590 >>> c['b'] -= 2 # reduce the count of 'b' by two591 >>> c.most_common() # 'b' is still in, but its count is zero592 [('a', 3), ('c', 1), ('b', 0)]593 594 '''595 # References:596 # http://en.wikipedia.org/wiki/Multiset597 # http://www.gnu.org/software/smalltalk/manual-base/html_node/Bag.html598 # http://www.java2s.com/Tutorial/Cpp/0380__set-multiset/Catalog0380__set-multiset.htm599 # http://code.activestate.com/recipes/259174/600 # Knuth, TAOCP Vol. II section 4.6.3601 602 def __init__(self, iterable=None, /, **kwds):603 '''Create a new, empty Counter object. And if given, count elements604 from an input iterable. Or, initialize the count from another mapping605 of elements to their counts.606 607 >>> c = Counter() # a new, empty counter608 >>> c = Counter('gallahad') # a new counter from an iterable609 >>> c = Counter({'a': 4, 'b': 2}) # a new counter from a mapping610 >>> c = Counter(a=4, b=2) # a new counter from keyword args611 612 '''613 super().__init__()614 self.update(iterable, **kwds)615 616 def __missing__(self, key):617 'The count of elements not in the Counter is zero.'618 # Needed so that self[missing_item] does not raise KeyError619 return 0620 621 def total(self):622 'Sum of the counts'623 return sum(self.values())624 625 def most_common(self, n=None):626 '''List the n most common elements and their counts from the most627 common to the least. If n is None, then list all element counts.628 629 >>> Counter('abracadabra').most_common(3)630 [('a', 5), ('b', 2), ('r', 2)]631 632 '''633 # Emulate Bag.sortedByCount from Smalltalk634 if n is None:635 return sorted(self.items(), key=_itemgetter(1), reverse=True)636 637 # Lazy import to speedup Python startup time638 global heapq639 if heapq is None:640 import heapq641 642 return heapq.nlargest(n, self.items(), key=_itemgetter(1))643 644 def elements(self):645 '''Iterator over elements repeating each as many times as its count.646 647 >>> c = Counter('ABCABC')648 >>> sorted(c.elements())649 ['A', 'A', 'B', 'B', 'C', 'C']650 651 Knuth's example for prime factors of 1836: 2**2 * 3**3 * 17**1652 653 >>> import math654 >>> prime_factors = Counter({2: 2, 3: 3, 17: 1})655 >>> math.prod(prime_factors.elements())656 1836657 658 Note, if an element's count has been set to zero or is a negative659 number, elements() will ignore it.660 661 '''662 # Emulate Bag.do from Smalltalk and Multiset.begin from C++.663 return _chain.from_iterable(_starmap(_repeat, self.items()))664 665 # Override dict methods where necessary666 667 @classmethod668 def fromkeys(cls, iterable, v=None):669 # There is no equivalent method for counters because the semantics670 # would be ambiguous in cases such as Counter.fromkeys('aaabbc', v=2).671 # Initializing counters to zero values isn't necessary because zero672 # is already the default value for counter lookups. Initializing673 # to one is easily accomplished with Counter(set(iterable)). For674 # more exotic cases, create a dictionary first using a dictionary675 # comprehension or dict.fromkeys().676 raise NotImplementedError(677 'Counter.fromkeys() is undefined. Use Counter(iterable) instead.')678 679 def update(self, iterable=None, /, **kwds):680 '''Like dict.update() but add counts instead of replacing them.681 682 Source can be an iterable, a dictionary, or another Counter instance.683 684 >>> c = Counter('which')685 >>> c.update('witch') # add elements from another iterable686 >>> d = Counter('watch')687 >>> c.update(d) # add elements from another counter688 >>> c['h'] # four 'h' in which, witch, and watch689 4690 691 '''692 # The regular dict.update() operation makes no sense here because the693 # replace behavior results in some of the original untouched counts694 # being mixed-in with all of the other counts for a mismash that695 # doesn't have a straight-forward interpretation in most counting696 # contexts. Instead, we implement straight-addition. Both the inputs697 # and outputs are allowed to contain zero and negative counts.698 699 if iterable is not None:700 if isinstance(iterable, _collections_abc.Mapping):701 if self:702 self_get = self.get703 for elem, count in iterable.items():704 self[elem] = count + self_get(elem, 0)705 else:706 # fast path when counter is empty707 super().update(iterable)708 else:709 _count_elements(self, iterable)710 if kwds:711 self.update(kwds)712 713 def subtract(self, iterable=None, /, **kwds):714 '''Like dict.update() but subtracts counts instead of replacing them.715 Counts can be reduced below zero. Both the inputs and outputs are716 allowed to contain zero and negative counts.717 718 Source can be an iterable, a dictionary, or another Counter instance.719 720 >>> c = Counter('which')721 >>> c.subtract('witch') # subtract elements from another iterable722 >>> c.subtract(Counter('watch')) # subtract elements from another counter723 >>> c['h'] # 2 in which, minus 1 in witch, minus 1 in watch724 0725 >>> c['w'] # 1 in which, minus 1 in witch, minus 1 in watch726 -1727 728 '''729 if iterable is not None:730 self_get = self.get731 if isinstance(iterable, _collections_abc.Mapping):732 for elem, count in iterable.items():733 self[elem] = self_get(elem, 0) - count734 else:735 for elem in iterable:736 self[elem] = self_get(elem, 0) - 1737 if kwds:738 self.subtract(kwds)739 740 def copy(self):741 'Return a shallow copy.'742 return self.__class__(self)743 744 def __reduce__(self):745 return self.__class__, (dict(self),)746 747 def __delitem__(self, elem):748 'Like dict.__delitem__() but does not raise KeyError for missing values.'749 if elem in self:750 super().__delitem__(elem)751 752 def __repr__(self):753 if not self:754 return f'{self.__class__.__name__}()'755 try:756 # dict() preserves the ordering returned by most_common()757 d = dict(self.most_common())758 except TypeError:759 # handle case where values are not orderable760 d = dict(self)761 return f'{self.__class__.__name__}({d!r})'762 763 # Multiset-style mathematical operations discussed in:764 # Knuth TAOCP Volume II section 4.6.3 exercise 19765 # and at http://en.wikipedia.org/wiki/Multiset766 #767 # Outputs guaranteed to only include positive counts.768 #769 # To strip negative and zero counts, add-in an empty counter:770 # c += Counter()771 #772 # Results are ordered according to when an element is first773 # encountered in the left operand and then by the order774 # encountered in the right operand.775 #776 # When the multiplicities are all zero or one, multiset operations777 # are guaranteed to be equivalent to the corresponding operations778 # for regular sets.779 # Given counter multisets such as:780 # cp = Counter(a=1, b=0, c=1)781 # cq = Counter(c=1, d=0, e=1)782 # The corresponding regular sets would be:783 # sp = {'a', 'c'}784 # sq = {'c', 'e'}785 # All of the following relations would hold:786 # set(cp + cq) == sp | sq787 # set(cp - cq) == sp - sq788 # set(cp | cq) == sp | sq789 # set(cp & cq) == sp & sq790 # (cp == cq) == (sp == sq)791 # (cp != cq) == (sp != sq)792 # (cp <= cq) == (sp <= sq)793 # (cp < cq) == (sp < sq)794 # (cp >= cq) == (sp >= sq)795 # (cp > cq) == (sp > sq)796 797 def __eq__(self, other):798 'True if all counts agree. Missing counts are treated as zero.'799 if not isinstance(other, Counter):800 return NotImplemented801 return all(self[e] == other[e] for c in (self, other) for e in c)802 803 def __ne__(self, other):804 'True if any counts disagree. Missing counts are treated as zero.'805 if not isinstance(other, Counter):806 return NotImplemented807 return not self == other808 809 def __le__(self, other):810 'True if all counts in self are a subset of those in other.'811 if not isinstance(other, Counter):812 return NotImplemented813 return all(self[e] <= other[e] for c in (self, other) for e in c)814 815 def __lt__(self, other):816 'True if all counts in self are a proper subset of those in other.'817 if not isinstance(other, Counter):818 return NotImplemented819 return self <= other and self != other820 821 def __ge__(self, other):822 'True if all counts in self are a superset of those in other.'823 if not isinstance(other, Counter):824 return NotImplemented825 return all(self[e] >= other[e] for c in (self, other) for e in c)826 827 def __gt__(self, other):828 'True if all counts in self are a proper superset of those in other.'829 if not isinstance(other, Counter):830 return NotImplemented831 return self >= other and self != other832 833 def __add__(self, other):834 '''Add counts from two counters.835 836 >>> Counter('abbb') + Counter('bcc')837 Counter({'b': 4, 'c': 2, 'a': 1})838 839 '''840 if not isinstance(other, Counter):841 return NotImplemented842 result = Counter()843 for elem, count in self.items():844 newcount = count + other[elem]845 if newcount > 0:846 result[elem] = newcount847 for elem, count in other.items():848 if elem not in self and count > 0:849 result[elem] = count850 return result851 852 def __sub__(self, other):853 ''' Subtract count, but keep only results with positive counts.854 855 >>> Counter('abbbc') - Counter('bccd')856 Counter({'b': 2, 'a': 1})857 858 '''859 if not isinstance(other, Counter):860 return NotImplemented861 result = Counter()862 for elem, count in self.items():863 newcount = count - other[elem]864 if newcount > 0:865 result[elem] = newcount866 for elem, count in other.items():867 if elem not in self and count < 0:868 result[elem] = 0 - count869 return result870 871 def __or__(self, other):872 '''Union is the maximum of value in either of the input counters.873 874 >>> Counter('abbb') | Counter('bcc')875 Counter({'b': 3, 'c': 2, 'a': 1})876 877 '''878 if not isinstance(other, Counter):879 return NotImplemented880 result = Counter()881 for elem, count in self.items():882 other_count = other[elem]883 newcount = other_count if count < other_count else count884 if newcount > 0:885 result[elem] = newcount886 for elem, count in other.items():887 if elem not in self and count > 0:888 result[elem] = count889 return result890 891 def __and__(self, other):892 ''' Intersection is the minimum of corresponding counts.893 894 >>> Counter('abbb') & Counter('bcc')895 Counter({'b': 1})896 897 '''898 if not isinstance(other, Counter):899 return NotImplemented900 result = Counter()901 for elem, count in self.items():902 other_count = other[elem]903 newcount = count if count < other_count else other_count904 if newcount > 0:905 result[elem] = newcount906 return result907 908 def __pos__(self):909 'Adds an empty counter, effectively stripping negative and zero counts'910 result = Counter()911 for elem, count in self.items():912 if count > 0:913 result[elem] = count914 return result915 916 def __neg__(self):917 '''Subtracts from an empty counter. Strips positive and zero counts,918 and flips the sign on negative counts.919 920 '''921 result = Counter()922 for elem, count in self.items():923 if count < 0:924 result[elem] = 0 - count925 return result926 927 def _keep_positive(self):928 '''Internal method to strip elements with a negative or zero count'''929 nonpositive = [elem for elem, count in self.items() if not count > 0]930 for elem in nonpositive:931 del self[elem]932 return self933 934 def __iadd__(self, other):935 '''Inplace add from another counter, keeping only positive counts.936 937 >>> c = Counter('abbb')938 >>> c += Counter('bcc')939 >>> c940 Counter({'b': 4, 'c': 2, 'a': 1})941 942 '''943 for elem, count in other.items():944 self[elem] += count945 return self._keep_positive()946 947 def __isub__(self, other):948 '''Inplace subtract counter, but keep only results with positive counts.949 950 >>> c = Counter('abbbc')951 >>> c -= Counter('bccd')952 >>> c953 Counter({'b': 2, 'a': 1})954 955 '''956 for elem, count in other.items():957 self[elem] -= count958 return self._keep_positive()959 960 def __ior__(self, other):961 '''Inplace union is the maximum of value from either counter.962 963 >>> c = Counter('abbb')964 >>> c |= Counter('bcc')965 >>> c966 Counter({'b': 3, 'c': 2, 'a': 1})967 968 '''969 for elem, other_count in other.items():970 count = self[elem]971 if other_count > count:972 self[elem] = other_count973 return self._keep_positive()974 975 def __iand__(self, other):976 '''Inplace intersection is the minimum of corresponding counts.977 978 >>> c = Counter('abbb')979 >>> c &= Counter('bcc')980 >>> c981 Counter({'b': 1})982 983 '''984 for elem, count in self.items():985 other_count = other[elem]986 if other_count < count:987 self[elem] = other_count988 return self._keep_positive()989 990 991########################################################################992### ChainMap993########################################################################994 995class ChainMap(_collections_abc.MutableMapping):996 ''' A ChainMap groups multiple dicts (or other mappings) together997 to create a single, updateable view.998 999 The underlying mappings are stored in a list. That list is public and can1000 be accessed or updated using the *maps* attribute. There is no other1001 state.1002 1003 Lookups search the underlying mappings successively until a key is found.1004 In contrast, writes, updates, and deletions only operate on the first1005 mapping.1006 1007 '''1008 1009 def __init__(self, *maps):1010 '''Initialize a ChainMap by setting *maps* to the given mappings.1011 If no mappings are provided, a single empty dictionary is used.1012 1013 '''1014 self.maps = list(maps) or [{}] # always at least one map1015 1016 def __missing__(self, key):1017 raise KeyError(key)1018 1019 def __getitem__(self, key):1020 for mapping in self.maps:1021 try:1022 return mapping[key] # can't use 'key in mapping' with defaultdict1023 except KeyError:1024 pass1025 return self.__missing__(key) # support subclasses that define __missing__1026 1027 def get(self, key, default=None):1028 return self[key] if key in self else default # needs to make use of __contains__1029 1030 def __len__(self):1031 return len(set().union(*self.maps)) # reuses stored hash values if possible1032 1033 def __iter__(self):1034 d = {}1035 for mapping in map(dict.fromkeys, reversed(self.maps)):1036 d |= mapping # reuses stored hash values if possible1037 return iter(d)1038 1039 def __contains__(self, key):1040 for mapping in self.maps:1041 if key in mapping:1042 return True1043 return False1044 1045 def __bool__(self):1046 return any(self.maps)1047 1048 @_recursive_repr()1049 def __repr__(self):1050 return f'{self.__class__.__name__}({", ".join(map(repr, self.maps))})'1051 1052 @classmethod1053 def fromkeys(cls, iterable, value=None, /):1054 'Create a new ChainMap with keys from iterable and values set to value.'1055 return cls(dict.fromkeys(iterable, value))1056 1057 def copy(self):1058 'New ChainMap or subclass with a new copy of maps[0] and refs to maps[1:]'1059 return self.__class__(self.maps[0].copy(), *self.maps[1:])1060 1061 __copy__ = copy1062 1063 def new_child(self, m=None, **kwargs): # like Django's Context.push()1064 '''New ChainMap with a new map followed by all previous maps.1065 If no map is provided, an empty dict is used.1066 Keyword arguments update the map or new empty dict.1067 '''1068 if m is None:1069 m = kwargs1070 elif kwargs:1071 m.update(kwargs)1072 return self.__class__(m, *self.maps)1073 1074 @property1075 def parents(self): # like Django's Context.pop()1076 'New ChainMap from maps[1:].'1077 return self.__class__(*self.maps[1:])1078 1079 def __setitem__(self, key, value):1080 self.maps[0][key] = value1081 1082 def __delitem__(self, key):1083 try:1084 del self.maps[0][key]1085 except KeyError:1086 raise KeyError(f'Key not found in the first mapping: {key!r}')1087 1088 def popitem(self):1089 'Remove and return an item pair from maps[0]. Raise KeyError is maps[0] is empty.'1090 try:1091 return self.maps[0].popitem()1092 except KeyError:1093 raise KeyError('No keys found in the first mapping.')1094 1095 def pop(self, key, *args):1096 'Remove *key* from maps[0] and return its value. Raise KeyError if *key* not in maps[0].'1097 try:1098 return self.maps[0].pop(key, *args)1099 except KeyError:1100 raise KeyError(f'Key not found in the first mapping: {key!r}')1101 1102 def clear(self):1103 'Clear maps[0], leaving maps[1:] intact.'1104 self.maps[0].clear()1105 1106 def __ior__(self, other):1107 self.maps[0].update(other)1108 return self1109 1110 def __or__(self, other):1111 if not isinstance(other, _collections_abc.Mapping):1112 return NotImplemented1113 m = self.copy()1114 m.maps[0].update(other)1115 return m1116 1117 def __ror__(self, other):1118 if not isinstance(other, _collections_abc.Mapping):1119 return NotImplemented1120 m = dict(other)1121 for child in reversed(self.maps):1122 m.update(child)1123 return self.__class__(m)1124 1125 1126################################################################################1127### UserDict1128################################################################################1129 1130class UserDict(_collections_abc.MutableMapping):1131 1132 # Start by filling-out the abstract methods1133 def __init__(self, dict=None, /, **kwargs):1134 self.data = {}1135 if dict is not None:1136 self.update(dict)1137 if kwargs:1138 self.update(kwargs)1139 1140 def __len__(self):1141 return len(self.data)1142 1143 def __getitem__(self, key):1144 if key in self.data:1145 return self.data[key]1146 if hasattr(self.__class__, "__missing__"):1147 return self.__class__.__missing__(self, key)1148 raise KeyError(key)1149 1150 def __setitem__(self, key, item):1151 self.data[key] = item1152 1153 def __delitem__(self, key):1154 del self.data[key]1155 1156 def __iter__(self):1157 return iter(self.data)1158 1159 # Modify __contains__ and get() to work like dict1160 # does when __missing__ is present.1161 def __contains__(self, key):1162 return key in self.data1163 1164 def get(self, key, default=None):1165 if key in self:1166 return self[key]1167 return default1168 1169 1170 # Now, add the methods in dicts but not in MutableMapping1171 def __repr__(self):1172 return repr(self.data)1173 1174 def __or__(self, other):1175 if isinstance(other, UserDict):1176 return self.__class__(self.data | other.data)1177 if isinstance(other, dict):1178 return self.__class__(self.data | other)1179 return NotImplemented1180 1181 def __ror__(self, other):1182 if isinstance(other, UserDict):1183 return self.__class__(other.data | self.data)1184 if isinstance(other, dict):1185 return self.__class__(other | self.data)1186 return NotImplemented1187 1188 def __ior__(self, other):1189 if isinstance(other, UserDict):1190 self.data |= other.data1191 else:1192 self.data |= other1193 return self1194 1195 def __copy__(self):1196 inst = self.__class__.__new__(self.__class__)1197 inst.__dict__.update(self.__dict__)1198 # Create a copy and avoid triggering descriptors1199 inst.__dict__["data"] = self.__dict__["data"].copy()1200 return inst