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