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