1'''This module implements specialized container datatypes providing 2alternatives to Python's general purpose built-in containers, dict, 3list, set, and tuple. 4 5* namedtuple factory function for creating tuple subclasses with named fields 6* deque list-like container with fast appends and pops on either end 7* ChainMap dict-like class for creating a single view of multiple mappings 8* Counter dict subclass for counting hashable objects 9* OrderedDict dict subclass that remembers the order entries were added 10* defaultdict dict subclass that calls a factory function to supply missing values 11* UserDict wrapper around dictionary objects for easier dict subclassing 12* UserList wrapper around list objects for easier list subclassing 13* UserString wrapper around string objects for easier string subclassing 14 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_abc 30import heapq as _heapq 31import sys as _sys 32 33from itertools import chain as _chain 34from itertools import repeat as _repeat 35from itertools import starmap as _starmap 36from keyword import iskeyword as _iskeyword 37from operator import eq as _eq 38from operator import itemgetter as _itemgetter 39from reprlib import recursive_repr as _recursive_repr 40from _weakref import proxy as _proxy 41 42try: 43 from _collections import deque 44except ImportError: 45 pass 46else: 47 _collections_abc.MutableSequence.register(deque) 48 49try: 50 from _collections import defaultdict 51except ImportError: 52 pass 53 54 55def __getattr__(name): 56 # For backwards compatibility, continue to make the collections ABCs 57 # through Python 3.6 available through the collections module. 58 # Note, no new collections ABCs were added in Python 3.7 59 if name in _collections_abc.__all__: 60 obj = getattr(_collections_abc, name) 61 import warnings 62 warnings.warn("Using or importing the ABCs from 'collections' instead " 63 "of from 'collections.abc' is deprecated since Python 3.3, " 64 "and in 3.10 it will stop working", 65 DeprecationWarning, stacklevel=2) 66 globals()[name] = obj 67 return obj 68 raise AttributeError(f'module {__name__!r} has no attribute {name!r}') 69 70 71################################################################################ 72### OrderedDict 73################################################################################ 74 75class _OrderedDictKeysView(_collections_abc.KeysView): 76 77 def __reversed__(self): 78 yield from reversed(self._mapping) 79 80class _OrderedDictItemsView(_collections_abc.ItemsView): 81 82 def __reversed__(self): 83 for key in reversed(self._mapping): 84 yield (key, self._mapping[key]) 85 86class _OrderedDictValuesView(_collections_abc.ValuesView): 87 88 def __reversed__(self): 89 for key in reversed(self._mapping): 90 yield self._mapping[key] 91 92class _Link(object): 93 __slots__ = 'prev', 'next', 'key', '__weakref__' 94 95class OrderedDict(dict): 96 'Dictionary that remembers insertion order' 97 # An inherited dict maps keys to values. 98 # The inherited dict provides __getitem__, __len__, __contains__, and get. 99 # The remaining methods are order-aware. 100 # Big-O running times for all methods are the same as regular dictionaries. 101 102 # The internal self.__map dict maps keys to links in a doubly linked list. 103 # The circular doubly linked list starts and ends with a sentinel element. 104 # The sentinel element never gets deleted (this simplifies the algorithm). 105 # The sentinel is in self.__hardroot with a weakref proxy in self.__root. 106 # The prev links are weakref proxies (to prevent circular references). 107 # Individual links are kept alive by the hard reference in self.__map. 108 # Those hard references disappear when a key is deleted from an OrderedDict. 109 110 def __init__(self, other=(), /, **kwds): 111 '''Initialize an ordered dictionary. The signature is the same as 112 regular dictionaries. Keyword argument order is preserved. 113 ''' 114 try: 115 self.__root 116 except AttributeError: 117 self.__hardroot = _Link() 118 self.__root = root = _proxy(self.__hardroot) 119 root.prev = root.next = root 120 self.__map = {} 121 self.__update(other, **kwds) 122 123 def __setitem__(self, key, value, 124 dict_setitem=dict.__setitem__, proxy=_proxy, Link=_Link): 125 'od.__setitem__(i, y) <==> od[i]=y' 126 # Setting a new item creates a new link at the end of the linked list, 127 # and the inherited dictionary is updated with the new key/value pair. 128 if key not in self: 129 self.__map[key] = link = Link() 130 root = self.__root 131 last = root.prev 132 link.prev, link.next, link.key = last, root, key 133 last.next = link 134 root.prev = proxy(link) 135 dict_setitem(self, key, value) 136 137 def __delitem__(self, key, dict_delitem=dict.__delitem__): 138 'od.__delitem__(y) <==> del od[y]' 139 # Deleting an existing item uses self.__map to find the link which gets 140 # removed by updating the links in the predecessor and successor nodes. 141 dict_delitem(self, key) 142 link = self.__map.pop(key) 143 link_prev = link.prev 144 link_next = link.next 145 link_prev.next = link_next 146 link_next.prev = link_prev 147 link.prev = None 148 link.next = None 149 150 def __iter__(self): 151 'od.__iter__() <==> iter(od)' 152 # Traverse the linked list in order. 153 root = self.__root 154 curr = root.next 155 while curr is not root: 156 yield curr.key 157 curr = curr.next 158 159 def __reversed__(self): 160 'od.__reversed__() <==> reversed(od)' 161 # Traverse the linked list in reverse order. 162 root = self.__root 163 curr = root.prev 164 while curr is not root: 165 yield curr.key 166 curr = curr.prev 167 168 def clear(self): 169 'od.clear() -> None. Remove all items from od.' 170 root = self.__root 171 root.prev = root.next = root 172 self.__map.clear() 173 dict.clear(self) 174 175 def popitem(self, last=True): 176 '''Remove and return a (key, value) pair from the dictionary. 177 178 Pairs are returned in LIFO order if last is true or FIFO order if false. 179 ''' 180 if not self: 181 raise KeyError('dictionary is empty') 182 root = self.__root 183 if last: 184 link = root.prev 185 link_prev = link.prev 186 link_prev.next = root 187 root.prev = link_prev 188 else: 189 link = root.next 190 link_next = link.next 191 root.next = link_next 192 link_next.prev = root 193 key = link.key 194 del self.__map[key] 195 value = dict.pop(self, key) 196 return key, value 197 198 def move_to_end(self, key, last=True): 199 '''Move an existing element to the end (or beginning if last is false). 200 201 Raise KeyError if the element does not exist. 202 ''' 203 link = self.__map[key] 204 link_prev = link.prev 205 link_next = link.next 206 soft_link = link_next.prev 207 link_prev.next = link_next 208 link_next.prev = link_prev 209 root = self.__root 210 if last: 211 last = root.prev 212 link.prev = last 213 link.next = root 214 root.prev = soft_link 215 last.next = link 216 else: 217 first = root.next 218 link.prev = root 219 link.next = first 220 first.prev = soft_link 221 root.next = link 222 223 def __sizeof__(self): 224 sizeof = _sys.getsizeof 225 n = len(self) + 1 # number of links including root 226 size = sizeof(self.__dict__) # instance dictionary 227 size += sizeof(self.__map) * 2 # internal dict and inherited dict 228 size += sizeof(self.__hardroot) * n # link objects 229 size += sizeof(self.__root) * n # proxy objects 230 return size 231 232 update = __update = _collections_abc.MutableMapping.update 233 234 def keys(self): 235 "D.keys() -> a set-like object providing a view on D's keys" 236 return _OrderedDictKeysView(self) 237 238 def items(self): 239 "D.items() -> a set-like object providing a view on D's items" 240 return _OrderedDictItemsView(self) 241 242 def values(self): 243 "D.values() -> an object providing a view on D's values" 244 return _OrderedDictValuesView(self) 245 246 __ne__ = _collections_abc.MutableMapping.__ne__ 247 248 __marker = object() 249 250 def pop(self, key, default=__marker): 251 '''od.pop(k[,d]) -> v, remove specified key and return the corresponding 252 value. If key is not found, d is returned if given, otherwise KeyError 253 is raised. 254 255 ''' 256 if key in self: 257 result = self[key] 258 del self[key] 259 return result 260 if default is self.__marker: 261 raise KeyError(key) 262 return default 263 264 def setdefault(self, key, default=None): 265 '''Insert key with a value of default if key is not in the dictionary. 266 267 Return the value for key if key is in the dictionary, else default. 268 ''' 269 if key in self: 270 return self[key] 271 self[key] = default 272 return default 273 274 @_recursive_repr() 275 def __repr__(self): 276 'od.__repr__() <==> repr(od)' 277 if not self: 278 return '%s()' % (self.__class__.__name__,) 279 return '%s(%r)' % (self.__class__.__name__, list(self.items())) 280 281 def __reduce__(self): 282 'Return state information for pickling' 283 inst_dict = vars(self).copy() 284 for k in vars(OrderedDict()): 285 inst_dict.pop(k, None) 286 return self.__class__, (), inst_dict or None, None, iter(self.items()) 287 288 def copy(self): 289 'od.copy() -> a shallow copy of od' 290 return self.__class__(self) 291 292 @classmethod 293 def fromkeys(cls, iterable, value=None): 294 '''Create a new ordered dictionary with keys from iterable and values set to value. 295 ''' 296 self = cls() 297 for key in iterable: 298 self[key] = value 299 return self 300 301 def __eq__(self, other): 302 '''od.__eq__(y) <==> od==y. Comparison to another OD is order-sensitive 303 while comparison to a regular mapping is order-insensitive. 304 305 ''' 306 if isinstance(other, OrderedDict): 307 return dict.__eq__(self, other) and all(map(_eq, self, other)) 308 return dict.__eq__(self, other) 309 310 def __ior__(self, other): 311 self.update(other) 312 return self 313 314 def __or__(self, other): 315 if not isinstance(other, dict): 316 return NotImplemented 317 new = self.__class__(self) 318 new.update(other) 319 return new 320 321 def __ror__(self, other): 322 if not isinstance(other, dict): 323 return NotImplemented 324 new = self.__class__(other) 325 new.update(self) 326 return new 327 328 329try: 330 from _collections import OrderedDict 331except ImportError: 332 # Leave the pure Python version in place. 333 pass 334 335 336################################################################################ 337### namedtuple 338################################################################################ 339 340try: 341 from _collections import _tuplegetter 342except ImportError: 343 _tuplegetter = lambda index, doc: property(_itemgetter(index), doc=doc) 344 345def namedtuple(typename, field_names, *, rename=False, defaults=None, module=None): 346 """Returns a new subclass of tuple with named fields. 347 348 >>> Point = namedtuple('Point', ['x', 'y']) 349 >>> Point.__doc__ # docstring for the new class 350 'Point(x, y)' 351 >>> p = Point(11, y=22) # instantiate with positional args or keywords 352 >>> p[0] + p[1] # indexable like a plain tuple 353 33 354 >>> x, y = p # unpack like a regular tuple 355 >>> x, y 356 (11, 22) 357 >>> p.x + p.y # fields also accessible by name 358 33 359 >>> d = p._asdict() # convert to a dictionary 360 >>> d['x'] 361 11 362 >>> Point(**d) # convert from a dictionary 363 Point(x=11, y=22) 364 >>> p._replace(x=100) # _replace() is like str.replace() but targets named fields 365 Point(x=100, y=22) 366 367 """ 368 369 # Validate the field names. At the user's option, either generate an error 370 # message or automatically replace the field name with a valid name. 371 if isinstance(field_names, str): 372 field_names = field_names.replace(',', ' ').split() 373 field_names = list(map(str, field_names)) 374 typename = _sys.intern(str(typename)) 375 376 if rename: 377 seen = set() 378 for index, name in enumerate(field_names): 379 if (not name.isidentifier() 380 or _iskeyword(name) 381 or name.startswith('_') 382 or name in seen): 383 field_names[index] = f'_{index}' 384 seen.add(name) 385 386 for name in [typename] + field_names: 387 if type(name) is not str: 388 raise TypeError('Type names and field names must be strings') 389 if not name.isidentifier(): 390 raise ValueError('Type names and field names must be valid ' 391 f'identifiers: {name!r}') 392 if _iskeyword(name): 393 raise ValueError('Type names and field names cannot be a ' 394 f'keyword: {name!r}') 395 396 seen = set() 397 for name in field_names: 398 if name.startswith('_') and not rename: 399 raise ValueError('Field names cannot start with an underscore: ' 400 f'{name!r}') 401 if name in seen: 402 raise ValueError(f'Encountered duplicate field name: {name!r}') 403 seen.add(name) 404 405 field_defaults = {} 406 if defaults is not None: 407 defaults = tuple(defaults) 408 if len(defaults) > len(field_names): 409 raise TypeError('Got more default values than field names') 410 field_defaults = dict(reversed(list(zip(reversed(field_names), 411 reversed(defaults))))) 412 413 # Variables used in the methods and docstrings 414 field_names = tuple(map(_sys.intern, field_names)) 415 num_fields = len(field_names) 416 arg_list = ', '.join(field_names) 417 if num_fields == 1: 418 arg_list += ',' 419 repr_fmt = '(' + ', '.join(f'{name}=%r' for name in field_names) + ')' 420 tuple_new = tuple.__new__ 421 _dict, _tuple, _len, _map, _zip = dict, tuple, len, map, zip 422 423 # Create all the named tuple methods to be added to the class namespace 424 425 namespace = { 426 '_tuple_new': tuple_new, 427 '__builtins__': None, 428 '__name__': f'namedtuple_{typename}', 429 } 430 code = f'lambda _cls, {arg_list}: _tuple_new(_cls, ({arg_list}))' 431 __new__ = eval(code, namespace) 432 __new__.__name__ = '__new__' 433 __new__.__doc__ = f'Create new instance of {typename}({arg_list})' 434 if defaults is not None: 435 __new__.__defaults__ = defaults 436 437 @classmethod 438 def _make(cls, iterable): 439 result = tuple_new(cls, iterable) 440 if _len(result) != num_fields: 441 raise TypeError(f'Expected {num_fields} arguments, got {len(result)}') 442 return result 443 444 _make.__func__.__doc__ = (f'Make a new {typename} object from a sequence ' 445 'or iterable') 446 447 def _replace(self, /, **kwds): 448 result = self._make(_map(kwds.pop, field_names, self)) 449 if kwds: 450 raise ValueError(f'Got unexpected field names: {list(kwds)!r}') 451 return result 452 453 _replace.__doc__ = (f'Return a new {typename} object replacing specified ' 454 'fields with new values') 455 456 def __repr__(self): 457 'Return a nicely formatted representation string' 458 return self.__class__.__name__ + repr_fmt % self 459 460 def _asdict(self): 461 'Return a new dict which maps field names to their values.' 462 return _dict(_zip(self._fields, self)) 463 464 def __getnewargs__(self): 465 'Return self as a plain tuple. Used by copy and pickle.' 466 return _tuple(self) 467 468 # Modify function metadata to help with introspection and debugging 469 for method in ( 470 __new__, 471 _make.__func__, 472 _replace, 473 __repr__, 474 _asdict, 475 __getnewargs__, 476 ): 477 method.__qualname__ = f'{typename}.{method.__name__}' 478 479 # Build-up the class namespace dictionary 480 # and use type() to build the result class 481 class_namespace = { 482 '__doc__': f'{typename}({arg_list})', 483 '__slots__': (), 484 '_fields': field_names, 485 '_field_defaults': field_defaults, 486 '__new__': __new__, 487 '_make': _make, 488 '_replace': _replace, 489 '__repr__': __repr__, 490 '_asdict': _asdict, 491 '__getnewargs__': __getnewargs__, 492 } 493 for index, name in enumerate(field_names): 494 doc = _sys.intern(f'Alias for field number {index}') 495 class_namespace[name] = _tuplegetter(index, doc) 496 497 result = type(typename, (tuple,), class_namespace) 498 499 # For pickling to work, the __module__ variable needs to be set to the frame 500 # where the named tuple is created. Bypass this step in environments where 501 # sys._getframe is not defined (Jython for example) or sys._getframe is not 502 # defined for arguments greater than 0 (IronPython), or where the user has 503 # specified a particular module. 504 if module is None: 505 try: 506 module = _sys._getframe(1).f_globals.get('__name__', '__main__') 507 except (AttributeError, ValueError): 508 pass 509 if module is not None: 510 result.__module__ = module 511 512 return result 513 514 515######################################################################## 516### Counter 517######################################################################## 518 519def _count_elements(mapping, iterable): 520 'Tally elements from the iterable.' 521 mapping_get = mapping.get 522 for elem in iterable: 523 mapping[elem] = mapping_get(elem, 0) + 1 524 525try: # Load C helper function if available 526 from _collections import _count_elements 527except ImportError: 528 pass 529 530class Counter(dict): 531 '''Dict subclass for counting hashable items. Sometimes called a bag 532 or multiset. Elements are stored as dictionary keys and their counts 533 are stored as dictionary values. 534 535 >>> c = Counter('abcdeabcdabcaba') # count elements from a string 536 537 >>> c.most_common(3) # three most common elements 538 [('a', 5), ('b', 4), ('c', 3)] 539 >>> sorted(c) # list all unique elements 540 ['a', 'b', 'c', 'd', 'e'] 541 >>> ''.join(sorted(c.elements())) # list elements with repetitions 542 'aaaaabbbbcccdde' 543 >>> sum(c.values()) # total of all counts 544 15 545 546 >>> c['a'] # count of letter 'a' 547 5 548 >>> for elem in 'shazam': # update counts from an iterable 549 ... c[elem] += 1 # by adding 1 to each element's count 550 >>> c['a'] # now there are seven 'a' 551 7 552 >>> del c['b'] # remove all 'b' 553 >>> c['b'] # now there are zero 'b' 554 0 555 556 >>> d = Counter('simsalabim') # make another counter 557 >>> c.update(d) # add in the second counter 558 >>> c['a'] # now there are nine 'a' 559 9 560 561 >>> c.clear() # empty the counter 562 >>> c 563 Counter() 564 565 Note: If a count is set to zero or reduced to zero, it will remain 566 in the counter until the entry is deleted or the counter is cleared: 567 568 >>> c = Counter('aaabbc') 569 >>> c['b'] -= 2 # reduce the count of 'b' by two 570 >>> c.most_common() # 'b' is still in, but its count is zero 571 [('a', 3), ('c', 1), ('b', 0)] 572 573 ''' 574 # References: 575 # http://en.wikipedia.org/wiki/Multiset 576 # http://www.gnu.org/software/smalltalk/manual-base/html_node/Bag.html 577 # http://www.demo2s.com/Tutorial/Cpp/0380__set-multiset/Catalog0380__set-multiset.htm 578 # http://code.activestate.com/recipes/259174/ 579 # Knuth, TAOCP Vol. II section 4.6.3 580 581 def __init__(self, iterable=None, /, **kwds): 582 '''Create a new, empty Counter object. And if given, count elements 583 from an input iterable. Or, initialize the count from another mapping 584 of elements to their counts. 585 586 >>> c = Counter() # a new, empty counter 587 >>> c = Counter('gallahad') # a new counter from an iterable 588 >>> c = Counter({'a': 4, 'b': 2}) # a new counter from a mapping 589 >>> c = Counter(a=4, b=2) # a new counter from keyword args 590 591 ''' 592 super().__init__() 593 self.update(iterable, **kwds) 594 595 def __missing__(self, key): 596 'The count of elements not in the Counter is zero.' 597 # Needed so that self[missing_item] does not raise KeyError 598 return 0 599 600 def most_common(self, n=None): 601 '''List the n most common elements and their counts from the most 602 common to the least. If n is None, then list all element counts. 603 604 >>> Counter('abracadabra').most_common(3) 605 [('a', 5), ('b', 2), ('r', 2)] 606 607 ''' 608 # Emulate Bag.sortedByCount from Smalltalk 609 if n is None: 610 return sorted(self.items(), key=_itemgetter(1), reverse=True) 611 return _heapq.nlargest(n, self.items(), key=_itemgetter(1)) 612 613 def elements(self): 614 '''Iterator over elements repeating each as many times as its count. 615 616 >>> c = Counter('ABCABC') 617 >>> sorted(c.elements()) 618 ['A', 'A', 'B', 'B', 'C', 'C'] 619 620 # Knuth's example for prime factors of 1836: 2**2 * 3**3 * 17**1 621 >>> prime_factors = Counter({2: 2, 3: 3, 17: 1}) 622 >>> product = 1 623 >>> for factor in prime_factors.elements(): # loop over factors 624 ... product *= factor # and multiply them 625 >>> product 626 1836 627 628 Note, if an element's count has been set to zero or is a negative 629 number, elements() will ignore it. 630 631 ''' 632 # Emulate Bag.do from Smalltalk and Multiset.begin from C++. 633 return _chain.from_iterable(_starmap(_repeat, self.items())) 634 635 # Override dict methods where necessary 636 637 @classmethod 638 def fromkeys(cls, iterable, v=None): 639 # There is no equivalent method for counters because the semantics 640 # would be ambiguous in cases such as Counter.fromkeys('aaabbc', v=2). 641 # Initializing counters to zero values isn't necessary because zero 642 # is already the default value for counter lookups. Initializing 643 # to one is easily accomplished with Counter(set(iterable)). For 644 # more exotic cases, create a dictionary first using a dictionary 645 # comprehension or dict.fromkeys(). 646 raise NotImplementedError( 647 'Counter.fromkeys() is undefined. Use Counter(iterable) instead.') 648 649 def update(self, iterable=None, /, **kwds): 650 '''Like dict.update() but add counts instead of replacing them. 651 652 Source can be an iterable, a dictionary, or another Counter instance. 653 654 >>> c = Counter('which') 655 >>> c.update('witch') # add elements from another iterable 656 >>> d = Counter('watch') 657 >>> c.update(d) # add elements from another counter 658 >>> c['h'] # four 'h' in which, witch, and watch 659 4 660 661 ''' 662 # The regular dict.update() operation makes no sense here because the 663 # replace behavior results in the some of original untouched counts 664 # being mixed-in with all of the other counts for a mismash that 665 # doesn't have a straight-forward interpretation in most counting 666 # contexts. Instead, we implement straight-addition. Both the inputs 667 # and outputs are allowed to contain zero and negative counts. 668 669 if iterable is not None: 670 if isinstance(iterable, _collections_abc.Mapping): 671 if self: 672 self_get = self.get 673 for elem, count in iterable.items(): 674 self[elem] = count + self_get(elem, 0) 675 else: 676 # fast path when counter is empty 677 super().update(iterable) 678 else: 679 _count_elements(self, iterable) 680 if kwds: 681 self.update(kwds) 682 683 def subtract(self, iterable=None, /, **kwds): 684 '''Like dict.update() but subtracts counts instead of replacing them. 685 Counts can be reduced below zero. Both the inputs and outputs are 686 allowed to contain zero and negative counts. 687 688 Source can be an iterable, a dictionary, or another Counter instance. 689 690 >>> c = Counter('which') 691 >>> c.subtract('witch') # subtract elements from another iterable 692 >>> c.subtract(Counter('watch')) # subtract elements from another counter 693 >>> c['h'] # 2 in which, minus 1 in witch, minus 1 in watch 694 0 695 >>> c['w'] # 1 in which, minus 1 in witch, minus 1 in watch 696 -1 697 698 ''' 699 if iterable is not None: 700 self_get = self.get 701 if isinstance(iterable, _collections_abc.Mapping): 702 for elem, count in iterable.items(): 703 self[elem] = self_get(elem, 0) - count 704 else: 705 for elem in iterable: 706 self[elem] = self_get(elem, 0) - 1 707 if kwds: 708 self.subtract(kwds) 709 710 def copy(self): 711 'Return a shallow copy.' 712 return self.__class__(self) 713 714 def __reduce__(self): 715 return self.__class__, (dict(self),) 716 717 def __delitem__(self, elem): 718 'Like dict.__delitem__() but does not raise KeyError for missing values.' 719 if elem in self: 720 super().__delitem__(elem) 721 722 def __repr__(self): 723 if not self: 724 return f'{self.__class__.__name__}()' 725 try: 726 # dict() preserves the ordering returned by most_common() 727 d = dict(self.most_common()) 728 except TypeError: 729 # handle case where values are not orderable 730 d = dict(self) 731 return f'{self.__class__.__name__}({d!r})' 732 733 # Multiset-style mathematical operations discussed in: 734 # Knuth TAOCP Volume II section 4.6.3 exercise 19 735 # and at http://en.wikipedia.org/wiki/Multiset 736 # 737 # Outputs guaranteed to only include positive counts. 738 # 739 # To strip negative and zero counts, add-in an empty counter: 740 # c += Counter() 741 # 742 # Rich comparison operators for multiset subset and superset tests 743 # are deliberately omitted due to semantic conflicts with the 744 # existing inherited dict equality method. Subset and superset 745 # semantics ignore zero counts and require that p≤q ∧ p≥q → p=q; 746 # however, that would not be the case for p=Counter(a=1, b=0) 747 # and q=Counter(a=1) where the dictionaries are not equal. 748 749 def __add__(self, other): 750 '''Add counts from two counters. 751 752 >>> Counter('abbb') + Counter('bcc') 753 Counter({'b': 4, 'c': 2, 'a': 1}) 754 755 ''' 756 if not isinstance(other, Counter): 757 return NotImplemented 758 result = Counter() 759 for elem, count in self.items(): 760 newcount = count + other[elem] 761 if newcount > 0: 762 result[elem] = newcount 763 for elem, count in other.items(): 764 if elem not in self and count > 0: 765 result[elem] = count 766 return result 767 768 def __sub__(self, other): 769 ''' Subtract count, but keep only results with positive counts. 770 771 >>> Counter('abbbc') - Counter('bccd') 772 Counter({'b': 2, 'a': 1}) 773 774 ''' 775 if not isinstance(other, Counter): 776 return NotImplemented 777 result = Counter() 778 for elem, count in self.items(): 779 newcount = count - other[elem] 780 if newcount > 0: 781 result[elem] = newcount 782 for elem, count in other.items(): 783 if elem not in self and count < 0: 784 result[elem] = 0 - count 785 return result 786 787 def __or__(self, other): 788 '''Union is the maximum of value in either of the input counters. 789 790 >>> Counter('abbb') | Counter('bcc') 791 Counter({'b': 3, 'c': 2, 'a': 1}) 792 793 ''' 794 if not isinstance(other, Counter): 795 return NotImplemented 796 result = Counter() 797 for elem, count in self.items(): 798 other_count = other[elem] 799 newcount = other_count if count < other_count else count 800 if newcount > 0: 801 result[elem] = newcount 802 for elem, count in other.items(): 803 if elem not in self and count > 0: 804 result[elem] = count 805 return result 806 807 def __and__(self, other): 808 ''' Intersection is the minimum of corresponding counts. 809 810 >>> Counter('abbb') & Counter('bcc') 811 Counter({'b': 1}) 812 813 ''' 814 if not isinstance(other, Counter): 815 return NotImplemented 816 result = Counter() 817 for elem, count in self.items(): 818 other_count = other[elem] 819 newcount = count if count < other_count else other_count 820 if newcount > 0: 821 result[elem] = newcount 822 return result 823 824 def __pos__(self): 825 'Adds an empty counter, effectively stripping negative and zero counts' 826 result = Counter() 827 for elem, count in self.items(): 828 if count > 0: 829 result[elem] = count 830 return result 831 832 def __neg__(self): 833 '''Subtracts from an empty counter. Strips positive and zero counts, 834 and flips the sign on negative counts. 835 836 ''' 837 result = Counter() 838 for elem, count in self.items(): 839 if count < 0: 840 result[elem] = 0 - count 841 return result 842 843 def _keep_positive(self): 844 '''Internal method to strip elements with a negative or zero count''' 845 nonpositive = [elem for elem, count in self.items() if not count > 0] 846 for elem in nonpositive: 847 del self[elem] 848 return self 849 850 def __iadd__(self, other): 851 '''Inplace add from another counter, keeping only positive counts. 852 853 >>> c = Counter('abbb') 854 >>> c += Counter('bcc') 855 >>> c 856 Counter({'b': 4, 'c': 2, 'a': 1}) 857 858 ''' 859 for elem, count in other.items(): 860 self[elem] += count 861 return self._keep_positive() 862 863 def __isub__(self, other): 864 '''Inplace subtract counter, but keep only results with positive counts. 865 866 >>> c = Counter('abbbc') 867 >>> c -= Counter('bccd') 868 >>> c 869 Counter({'b': 2, 'a': 1}) 870 871 ''' 872 for elem, count in other.items(): 873 self[elem] -= count 874 return self._keep_positive() 875 876 def __ior__(self, other): 877 '''Inplace union is the maximum of value from either counter. 878 879 >>> c = Counter('abbb') 880 >>> c |= Counter('bcc') 881 >>> c 882 Counter({'b': 3, 'c': 2, 'a': 1}) 883 884 ''' 885 for elem, other_count in other.items(): 886 count = self[elem] 887 if other_count > count: 888 self[elem] = other_count 889 return self._keep_positive() 890 891 def __iand__(self, other): 892 '''Inplace intersection is the minimum of corresponding counts. 893 894 >>> c = Counter('abbb') 895 >>> c &= Counter('bcc') 896 >>> c 897 Counter({'b': 1}) 898 899 ''' 900 for elem, count in self.items(): 901 other_count = other[elem] 902 if other_count < count: 903 self[elem] = other_count 904 return self._keep_positive() 905 906 907######################################################################## 908### ChainMap 909######################################################################## 910 911class ChainMap(_collections_abc.MutableMapping): 912 ''' A ChainMap groups multiple dicts (or other mappings) together 913 to create a single, updateable view. 914 915 The underlying mappings are stored in a list. That list is public and can 916 be accessed or updated using the *maps* attribute. There is no other 917 state. 918 919 Lookups search the underlying mappings successively until a key is found. 920 In contrast, writes, updates, and deletions only operate on the first 921 mapping. 922 923 ''' 924 925 def __init__(self, *maps): 926 '''Initialize a ChainMap by setting *maps* to the given mappings. 927 If no mappings are provided, a single empty dictionary is used. 928 929 ''' 930 self.maps = list(maps) or [{}] # always at least one map 931 932 def __missing__(self, key): 933 raise KeyError(key) 934 935 def __getitem__(self, key): 936 for mapping in self.maps: 937 try: 938 return mapping[key] # can't use 'key in mapping' with defaultdict 939 except KeyError: 940 pass 941 return self.__missing__(key) # support subclasses that define __missing__ 942 943 def get(self, key, default=None): 944 return self[key] if key in self else default 945 946 def __len__(self): 947 return len(set().union(*self.maps)) # reuses stored hash values if possible 948 949 def __iter__(self): 950 d = {} 951 for mapping in reversed(self.maps): 952 d.update(dict.fromkeys(mapping)) # reuses stored hash values if possible 953 return iter(d) 954 955 def __contains__(self, key): 956 return any(key in m for m in self.maps) 957 958 def __bool__(self): 959 return any(self.maps) 960 961 @_recursive_repr() 962 def __repr__(self): 963 return f'{self.__class__.__name__}({", ".join(map(repr, self.maps))})' 964 965 @classmethod 966 def fromkeys(cls, iterable, *args): 967 'Create a ChainMap with a single dict created from the iterable.' 968 return cls(dict.fromkeys(iterable, *args)) 969 970 def copy(self): 971 'New ChainMap or subclass with a new copy of maps[0] and refs to maps[1:]' 972 return self.__class__(self.maps[0].copy(), *self.maps[1:]) 973 974 __copy__ = copy 975 976 def new_child(self, m=None): # like Django's Context.push() 977 '''New ChainMap with a new map followed by all previous maps. 978 If no map is provided, an empty dict is used. 979 ''' 980 if m is None: 981 m = {} 982 return self.__class__(m, *self.maps) 983 984 @property 985 def parents(self): # like Django's Context.pop() 986 'New ChainMap from maps[1:].' 987 return self.__class__(*self.maps[1:]) 988 989 def __setitem__(self, key, value): 990 self.maps[0][key] = value 991 992 def __delitem__(self, key): 993 try: 994 del self.maps[0][key] 995 except KeyError: 996 raise KeyError(f'Key not found in the first mapping: {key!r}') 997 998 def popitem(self): 999 'Remove and return an item pair from maps[0]. Raise KeyError is maps[0] is empty.' 1000 try: 1001 return self.maps[0].popitem() 1002 except KeyError: 1003 raise KeyError('No keys found in the first mapping.') 1004 1005 def pop(self, key, *args): 1006 'Remove *key* from maps[0] and return its value. Raise KeyError if *key* not in maps[0].' 1007 try: 1008 return self.maps[0].pop(key, *args) 1009 except KeyError: 1010 raise KeyError(f'Key not found in the first mapping: {key!r}') 1011 1012 def clear(self): 1013 'Clear maps[0], leaving maps[1:] intact.' 1014 self.maps[0].clear() 1015 1016 def __ior__(self, other): 1017 self.maps[0].update(other) 1018 return self 1019 1020 def __or__(self, other): 1021 if not isinstance(other, _collections_abc.Mapping): 1022 return NotImplemented 1023 m = self.copy() 1024 m.maps[0].update(other) 1025 return m 1026 1027 def __ror__(self, other): 1028 if not isinstance(other, _collections_abc.Mapping): 1029 return NotImplemented 1030 m = dict(other) 1031 for child in reversed(self.maps): 1032 m.update(child) 1033 return self.__class__(m) 1034 1035 1036################################################################################ 1037### UserDict 1038################################################################################ 1039 1040class UserDict(_collections_abc.MutableMapping): 1041 1042 # Start by filling-out the abstract methods 1043 def __init__(self, dict=None, /, **kwargs): 1044 self.data = {} 1045 if dict is not None: 1046 self.update(dict) 1047 if kwargs: 1048 self.update(kwargs) 1049 1050 def __len__(self): 1051 return len(self.data) 1052 1053 def __getitem__(self, key): 1054 if key in self.data: 1055 return self.data[key] 1056 if hasattr(self.__class__, "__missing__"): 1057 return self.__class__.__missing__(self, key) 1058 raise KeyError(key) 1059 1060 def __setitem__(self, key, item): 1061 self.data[key] = item 1062 1063 def __delitem__(self, key): 1064 del self.data[key] 1065 1066 def __iter__(self): 1067 return iter(self.data) 1068 1069 # Modify __contains__ to work correctly when __missing__ is present 1070 def __contains__(self, key): 1071 return key in self.data 1072 1073 # Now, add the methods in dicts but not in MutableMapping 1074 def __repr__(self): 1075 return repr(self.data) 1076 1077 def __or__(self, other): 1078 if isinstance(other, UserDict): 1079 return self.__class__(self.data | other.data) 1080 if isinstance(other, dict): 1081 return self.__class__(self.data | other) 1082 return NotImplemented 1083 1084 def __ror__(self, other): 1085 if isinstance(other, UserDict): 1086 return self.__class__(other.data | self.data) 1087 if isinstance(other, dict): 1088 return self.__class__(other | self.data) 1089 return NotImplemented 1090 1091 def __ior__(self, other): 1092 if isinstance(other, UserDict): 1093 self.data |= other.data 1094 else: 1095 self.data |= other 1096 return self 1097 1098 def __copy__(self): 1099 inst = self.__class__.__new__(self.__class__) 1100 inst.__dict__.update(self.__dict__) 1101 # Create a copy and avoid triggering descriptors 1102 inst.__dict__["data"] = self.__dict__["data"].copy() 1103 return inst 1104 1105 def copy(self): 1106 if self.__class__ is UserDict: 1107 return UserDict(self.data.copy()) 1108 import copy 1109 data = self.data 1110 try: 1111 self.data = {} 1112 c = copy.copy(self) 1113 finally: 1114 self.data = data 1115 c.update(self) 1116 return c 1117 1118 @classmethod 1119 def fromkeys(cls, iterable, value=None): 1120 d = cls() 1121 for key in iterable: 1122 d[key] = value 1123 return d 1124 1125 1126################################################################################ 1127### UserList 1128################################################################################ 1129 1130class UserList(_collections_abc.MutableSequence): 1131 """A more or less complete user-defined wrapper around list objects.""" 1132 1133 def __init__(self, initlist=None): 1134 self.data = [] 1135 if initlist is not None: 1136 # XXX should this accept an arbitrary sequence? 1137 if type(initlist) == type(self.data): 1138 self.data[:] = initlist 1139 elif isinstance(initlist, UserList): 1140 self.data[:] = initlist.data[:] 1141 else: 1142 self.data = list(initlist) 1143 1144 def __repr__(self): 1145 return repr(self.data) 1146 1147 def __lt__(self, other): 1148 return self.data < self.__cast(other) 1149 1150 def __le__(self, other): 1151 return self.data <= self.__cast(other) 1152 1153 def __eq__(self, other): 1154 return self.data == self.__cast(other) 1155 1156 def __gt__(self, other): 1157 return self.data > self.__cast(other) 1158 1159 def __ge__(self, other): 1160 return self.data >= self.__cast(other) 1161 1162 def __cast(self, other): 1163 return other.data if isinstance(other, UserList) else other 1164 1165 def __contains__(self, item): 1166 return item in self.data 1167 1168 def __len__(self): 1169 return len(self.data) 1170 1171 def __getitem__(self, i): 1172 if isinstance(i, slice): 1173 return self.__class__(self.data[i]) 1174 else: 1175 return self.data[i] 1176 1177 def __setitem__(self, i, item): 1178 self.data[i] = item 1179 1180 def __delitem__(self, i): 1181 del self.data[i] 1182 1183 def __add__(self, other): 1184 if isinstance(other, UserList): 1185 return self.__class__(self.data + other.data) 1186 elif isinstance(other, type(self.data)): 1187 return self.__class__(self.data + other) 1188 return self.__class__(self.data + list(other)) 1189 1190 def __radd__(self, other): 1191 if isinstance(other, UserList): 1192 return self.__class__(other.data + self.data) 1193 elif isinstance(other, type(self.data)): 1194 return self.__class__(other + self.data) 1195 return self.__class__(list(other) + self.data) 1196 1197 def __iadd__(self, other): 1198 if isinstance(other, UserList): 1199 self.data += other.data 1200 elif isinstance(other, type(self.data)): 1201 self.data += other 1202 else: 1203 self.data += list(other) 1204 return self 1205 1206 def __mul__(self, n): 1207 return self.__class__(self.data * n) 1208 1209 __rmul__ = __mul__ 1210 1211 def __imul__(self, n): 1212 self.data *= n 1213 return self 1214 1215 def __copy__(self): 1216 inst = self.__class__.__new__(self.__class__) 1217 inst.__dict__.update(self.__dict__) 1218 # Create a copy and avoid triggering descriptors 1219 inst.__dict__["data"] = self.__dict__["data"][:] 1220 return inst 1221 1222 def append(self, item): 1223 self.data.append(item) 1224 1225 def insert(self, i, item): 1226 self.data.insert(i, item) 1227 1228 def pop(self, i=-1): 1229 return self.data.pop(i) 1230 1231 def remove(self, item): 1232 self.data.remove(item) 1233 1234 def clear(self): 1235 self.data.clear() 1236 1237 def copy(self): 1238 return self.__class__(self) 1239 1240 def count(self, item): 1241 return self.data.count(item) 1242 1243 def index(self, item, *args): 1244 return self.data.index(item, *args) 1245 1246 def reverse(self): 1247 self.data.reverse() 1248 1249 def sort(self, /, *args, **kwds): 1250 self.data.sort(*args, **kwds) 1251 1252 def extend(self, other): 1253 if isinstance(other, UserList): 1254 self.data.extend(other.data) 1255 else: 1256 self.data.extend(other) 1257 1258 1259################################################################################ 1260### UserString 1261################################################################################ 1262 1263class UserString(_collections_abc.Sequence): 1264 1265 def __init__(self, seq): 1266 if isinstance(seq, str): 1267 self.data = seq 1268 elif isinstance(seq, UserString): 1269 self.data = seq.data[:] 1270 else: 1271 self.data = str(seq) 1272 1273 def __str__(self): 1274 return str(self.data) 1275 1276 def __repr__(self): 1277 return repr(self.data) 1278 1279 def __int__(self): 1280 return int(self.data) 1281 1282 def __float__(self): 1283 return float(self.data) 1284 1285 def __complex__(self): 1286 return complex(self.data) 1287 1288 def __hash__(self): 1289 return hash(self.data) 1290 1291 def __getnewargs__(self): 1292 return (self.data[:],) 1293 1294 def __eq__(self, string): 1295 if isinstance(string, UserString): 1296 return self.data == string.data 1297 return self.data == string 1298 1299 def __lt__(self, string): 1300 if isinstance(string, UserString): 1301 return self.data < string.data 1302 return self.data < string 1303 1304 def __le__(self, string): 1305 if isinstance(string, UserString): 1306 return self.data <= string.data 1307 return self.data <= string 1308 1309 def __gt__(self, string): 1310 if isinstance(string, UserString): 1311 return self.data > string.data 1312 return self.data > string 1313 1314 def __ge__(self, string): 1315 if isinstance(string, UserString): 1316 return self.data >= string.data 1317 return self.data >= string 1318 1319 def __contains__(self, char): 1320 if isinstance(char, UserString): 1321 char = char.data 1322 return char in self.data 1323 1324 def __len__(self): 1325 return len(self.data) 1326 1327 def __getitem__(self, index): 1328 return self.__class__(self.data[index]) 1329 1330 def __add__(self, other): 1331 if isinstance(other, UserString): 1332 return self.__class__(self.data + other.data) 1333 elif isinstance(other, str): 1334 return self.__class__(self.data + other) 1335 return self.__class__(self.data + str(other)) 1336 1337 def __radd__(self, other): 1338 if isinstance(other, str): 1339 return self.__class__(other + self.data) 1340 return self.__class__(str(other) + self.data) 1341 1342 def __mul__(self, n): 1343 return self.__class__(self.data * n) 1344 1345 __rmul__ = __mul__ 1346 1347 def __mod__(self, args): 1348 return self.__class__(self.data % args) 1349 1350 def __rmod__(self, template): 1351 return self.__class__(str(template) % self) 1352 1353 # the following methods are defined in alphabetical order: 1354 def capitalize(self): 1355 return self.__class__(self.data.capitalize()) 1356 1357 def casefold(self): 1358 return self.__class__(self.data.casefold()) 1359 1360 def center(self, width, *args): 1361 return self.__class__(self.data.center(width, *args)) 1362 1363 def count(self, sub, start=0, end=_sys.maxsize): 1364 if isinstance(sub, UserString): 1365 sub = sub.data 1366 return self.data.count(sub, start, end) 1367 1368 def removeprefix(self, prefix, /): 1369 if isinstance(prefix, UserString): 1370 prefix = prefix.data 1371 return self.__class__(self.data.removeprefix(prefix)) 1372 1373 def removesuffix(self, suffix, /): 1374 if isinstance(suffix, UserString): 1375 suffix = suffix.data 1376 return self.__class__(self.data.removesuffix(suffix)) 1377 1378 def encode(self, encoding='utf-8', errors='strict'): 1379 encoding = 'utf-8' if encoding is None else encoding 1380 errors = 'strict' if errors is None else errors 1381 return self.data.encode(encoding, errors) 1382 1383 def endswith(self, suffix, start=0, end=_sys.maxsize): 1384 return self.data.endswith(suffix, start, end) 1385 1386 def expandtabs(self, tabsize=8): 1387 return self.__class__(self.data.expandtabs(tabsize)) 1388 1389 def find(self, sub, start=0, end=_sys.maxsize): 1390 if isinstance(sub, UserString): 1391 sub = sub.data 1392 return self.data.find(sub, start, end) 1393 1394 def format(self, /, *args, **kwds): 1395 return self.data.format(*args, **kwds) 1396 1397 def format_map(self, mapping): 1398 return self.data.format_map(mapping) 1399 1400 def index(self, sub, start=0, end=_sys.maxsize): 1401 return self.data.index(sub, start, end) 1402 1403 def isalpha(self): 1404 return self.data.isalpha() 1405 1406 def isalnum(self): 1407 return self.data.isalnum() 1408 1409 def isascii(self): 1410 return self.data.isascii() 1411 1412 def isdecimal(self): 1413 return self.data.isdecimal() 1414 1415 def isdigit(self): 1416 return self.data.isdigit() 1417 1418 def isidentifier(self): 1419 return self.data.isidentifier() 1420 1421 def islower(self): 1422 return self.data.islower() 1423 1424 def isnumeric(self): 1425 return self.data.isnumeric() 1426 1427 def isprintable(self): 1428 return self.data.isprintable() 1429 1430 def isspace(self): 1431 return self.data.isspace() 1432 1433 def istitle(self): 1434 return self.data.istitle() 1435 1436 def isupper(self): 1437 return self.data.isupper() 1438 1439 def join(self, seq): 1440 return self.data.join(seq) 1441 1442 def ljust(self, width, *args): 1443 return self.__class__(self.data.ljust(width, *args)) 1444 1445 def lower(self): 1446 return self.__class__(self.data.lower()) 1447 1448 def lstrip(self, chars=None): 1449 return self.__class__(self.data.lstrip(chars)) 1450 1451 maketrans = str.maketrans 1452 1453 def partition(self, sep): 1454 return self.data.partition(sep) 1455 1456 def replace(self, old, new, maxsplit=-1): 1457 if isinstance(old, UserString): 1458 old = old.data 1459 if isinstance(new, UserString): 1460 new = new.data 1461 return self.__class__(self.data.replace(old, new, maxsplit)) 1462 1463 def rfind(self, sub, start=0, end=_sys.maxsize): 1464 if isinstance(sub, UserString): 1465 sub = sub.data 1466 return self.data.rfind(sub, start, end) 1467 1468 def rindex(self, sub, start=0, end=_sys.maxsize): 1469 return self.data.rindex(sub, start, end) 1470 1471 def rjust(self, width, *args): 1472 return self.__class__(self.data.rjust(width, *args)) 1473 1474 def rpartition(self, sep): 1475 return self.data.rpartition(sep) 1476 1477 def rstrip(self, chars=None): 1478 return self.__class__(self.data.rstrip(chars)) 1479 1480 def split(self, sep=None, maxsplit=-1): 1481 return self.data.split(sep, maxsplit) 1482 1483 def rsplit(self, sep=None, maxsplit=-1): 1484 return self.data.rsplit(sep, maxsplit) 1485 1486 def splitlines(self, keepends=False): 1487 return self.data.splitlines(keepends) 1488 1489 def startswith(self, prefix, start=0, end=_sys.maxsize): 1490 return self.data.startswith(prefix, start, end) 1491 1492 def strip(self, chars=None): 1493 return self.__class__(self.data.strip(chars)) 1494 1495 def swapcase(self): 1496 return self.__class__(self.data.swapcase()) 1497 1498 def title(self): 1499 return self.__class__(self.data.title()) 1500 1501 def translate(self, *args): 1502 return self.__class__(self.data.translate(*args)) 1503 1504 def upper(self): 1505 return self.__class__(self.data.upper()) 1506 1507 def zfill(self, width): 1508 return self.__class__(self.data.zfill(width)) 1509