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