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 # When the multiplicities are all zero or one, multiset operations 770 # are guaranteed to be equivalent to the corresponding operations 771 # for regular sets. 772 # Given counter multisets such as: 773 # cp = Counter(a=1, b=0, c=1) 774 # cq = Counter(c=1, d=0, e=1) 775 # The corresponding regular sets would be: 776 # sp = {'a', 'c'} 777 # sq = {'c', 'e'} 778 # All of the following relations would hold: 779 # set(cp + cq) == sp | sq 780 # set(cp - cq) == sp - sq 781 # set(cp | cq) == sp | sq 782 # set(cp & cq) == sp & sq 783 # (cp == cq) == (sp == sq) 784 # (cp != cq) == (sp != sq) 785 # (cp <= cq) == (sp <= sq) 786 # (cp < cq) == (sp < sq) 787 # (cp >= cq) == (sp >= sq) 788 # (cp > cq) == (sp > sq) 789 790 def __add__(self, other): 791 '''Add counts from two counters. 792 793 >>> Counter('abbb') + Counter('bcc') 794 Counter({'b': 4, 'c': 2, 'a': 1}) 795 796 ''' 797 if not isinstance(other, Counter): 798 return NotImplemented 799 result = Counter() 800 for elem, count in self.items(): 801 newcount = count + other[elem] 802 if newcount > 0: 803 result[elem] = newcount 804 for elem, count in other.items(): 805 if elem not in self and count > 0: 806 result[elem] = count 807 return result 808 809 def __sub__(self, other): 810 ''' Subtract count, but keep only results with positive counts. 811 812 >>> Counter('abbbc') - Counter('bccd') 813 Counter({'b': 2, 'a': 1}) 814 815 ''' 816 if not isinstance(other, Counter): 817 return NotImplemented 818 result = Counter() 819 for elem, count in self.items(): 820 newcount = count - other[elem] 821 if newcount > 0: 822 result[elem] = newcount 823 for elem, count in other.items(): 824 if elem not in self and count < 0: 825 result[elem] = 0 - count 826 return result 827 828 def __or__(self, other): 829 '''Union is the maximum of value in either of the input counters. 830 831 >>> Counter('abbb') | Counter('bcc') 832 Counter({'b': 3, 'c': 2, 'a': 1}) 833 834 ''' 835 if not isinstance(other, Counter): 836 return NotImplemented 837 result = Counter() 838 for elem, count in self.items(): 839 other_count = other[elem] 840 newcount = other_count if count < other_count else count 841 if newcount > 0: 842 result[elem] = newcount 843 for elem, count in other.items(): 844 if elem not in self and count > 0: 845 result[elem] = count 846 return result 847 848 def __and__(self, other): 849 ''' Intersection is the minimum of corresponding counts. 850 851 >>> Counter('abbb') & Counter('bcc') 852 Counter({'b': 1}) 853 854 ''' 855 if not isinstance(other, Counter): 856 return NotImplemented 857 result = Counter() 858 for elem, count in self.items(): 859 other_count = other[elem] 860 newcount = count if count < other_count else other_count 861 if newcount > 0: 862 result[elem] = newcount 863 return result 864 865 def __pos__(self): 866 'Adds an empty counter, effectively stripping negative and zero counts' 867 result = Counter() 868 for elem, count in self.items(): 869 if count > 0: 870 result[elem] = count 871 return result 872 873 def __neg__(self): 874 '''Subtracts from an empty counter. Strips positive and zero counts, 875 and flips the sign on negative counts. 876 877 ''' 878 result = Counter() 879 for elem, count in self.items(): 880 if count < 0: 881 result[elem] = 0 - count 882 return result 883 884 def _keep_positive(self): 885 '''Internal method to strip elements with a negative or zero count''' 886 nonpositive = [elem for elem, count in self.items() if not count > 0] 887 for elem in nonpositive: 888 del self[elem] 889 return self 890 891 def __iadd__(self, other): 892 '''Inplace add from another counter, keeping only positive counts. 893 894 >>> c = Counter('abbb') 895 >>> c += Counter('bcc') 896 >>> c 897 Counter({'b': 4, 'c': 2, 'a': 1}) 898 899 ''' 900 for elem, count in other.items(): 901 self[elem] += count 902 return self._keep_positive() 903 904 def __isub__(self, other): 905 '''Inplace subtract counter, but keep only results with positive counts. 906 907 >>> c = Counter('abbbc') 908 >>> c -= Counter('bccd') 909 >>> c 910 Counter({'b': 2, 'a': 1}) 911 912 ''' 913 for elem, count in other.items(): 914 self[elem] -= count 915 return self._keep_positive() 916 917 def __ior__(self, other): 918 '''Inplace union is the maximum of value from either counter. 919 920 >>> c = Counter('abbb') 921 >>> c |= Counter('bcc') 922 >>> c 923 Counter({'b': 3, 'c': 2, 'a': 1}) 924 925 ''' 926 for elem, other_count in other.items(): 927 count = self[elem] 928 if other_count > count: 929 self[elem] = other_count 930 return self._keep_positive() 931 932 def __iand__(self, other): 933 '''Inplace intersection is the minimum of corresponding counts. 934 935 >>> c = Counter('abbb') 936 >>> c &= Counter('bcc') 937 >>> c 938 Counter({'b': 1}) 939 940 ''' 941 for elem, count in self.items(): 942 other_count = other[elem] 943 if other_count < count: 944 self[elem] = other_count 945 return self._keep_positive() 946 947 948######################################################################## 949### ChainMap 950######################################################################## 951 952class ChainMap(_collections_abc.MutableMapping): 953 ''' A ChainMap groups multiple dicts (or other mappings) together 954 to create a single, updateable view. 955 956 The underlying mappings are stored in a list. That list is public and can 957 be accessed or updated using the *maps* attribute. There is no other 958 state. 959 960 Lookups search the underlying mappings successively until a key is found. 961 In contrast, writes, updates, and deletions only operate on the first 962 mapping. 963 964 ''' 965 966 def __init__(self, *maps): 967 '''Initialize a ChainMap by setting *maps* to the given mappings. 968 If no mappings are provided, a single empty dictionary is used. 969 970 ''' 971 self.maps = list(maps) or [{}] # always at least one map 972 973 def __missing__(self, key): 974 raise KeyError(key) 975 976 def __getitem__(self, key): 977 for mapping in self.maps: 978 try: 979 return mapping[key] # can't use 'key in mapping' with defaultdict 980 except KeyError: 981 pass 982 return self.__missing__(key) # support subclasses that define __missing__ 983 984 def get(self, key, default=None): 985 return self[key] if key in self else default 986 987 def __len__(self): 988 return len(set().union(*self.maps)) # reuses stored hash values if possible 989 990 def __iter__(self): 991 d = {} 992 for mapping in reversed(self.maps): 993 d.update(dict.fromkeys(mapping)) # reuses stored hash values if possible 994 return iter(d) 995 996 def __contains__(self, key): 997 return any(key in m for m in self.maps) 998 999 def __bool__(self): 1000 return any(self.maps) 1001 1002 @_recursive_repr() 1003 def __repr__(self): 1004 return f'{self.__class__.__name__}({", ".join(map(repr, self.maps))})' 1005 1006 @classmethod 1007 def fromkeys(cls, iterable, *args): 1008 'Create a ChainMap with a single dict created from the iterable.' 1009 return cls(dict.fromkeys(iterable, *args)) 1010 1011 def copy(self): 1012 'New ChainMap or subclass with a new copy of maps[0] and refs to maps[1:]' 1013 return self.__class__(self.maps[0].copy(), *self.maps[1:]) 1014 1015 __copy__ = copy 1016 1017 def new_child(self, m=None, **kwargs): # like Django's Context.push() 1018 '''New ChainMap with a new map followed by all previous maps. 1019 If no map is provided, an empty dict is used. 1020 Keyword arguments update the map or new empty dict. 1021 ''' 1022 if m is None: 1023 m = kwargs 1024 elif kwargs: 1025 m.update(kwargs) 1026 return self.__class__(m, *self.maps) 1027 1028 @property 1029 def parents(self): # like Django's Context.pop() 1030 'New ChainMap from maps[1:].' 1031 return self.__class__(*self.maps[1:]) 1032 1033 def __setitem__(self, key, value): 1034 self.maps[0][key] = value 1035 1036 def __delitem__(self, key): 1037 try: 1038 del self.maps[0][key] 1039 except KeyError: 1040 raise KeyError(f'Key not found in the first mapping: {key!r}') 1041 1042 def popitem(self): 1043 'Remove and return an item pair from maps[0]. Raise KeyError is maps[0] is empty.' 1044 try: 1045 return self.maps[0].popitem() 1046 except KeyError: 1047 raise KeyError('No keys found in the first mapping.') 1048 1049 def pop(self, key, *args): 1050 'Remove *key* from maps[0] and return its value. Raise KeyError if *key* not in maps[0].' 1051 try: 1052 return self.maps[0].pop(key, *args) 1053 except KeyError: 1054 raise KeyError(f'Key not found in the first mapping: {key!r}') 1055 1056 def clear(self): 1057 'Clear maps[0], leaving maps[1:] intact.' 1058 self.maps[0].clear() 1059 1060 def __ior__(self, other): 1061 self.maps[0].update(other) 1062 return self 1063 1064 def __or__(self, other): 1065 if not isinstance(other, _collections_abc.Mapping): 1066 return NotImplemented 1067 m = self.copy() 1068 m.maps[0].update(other) 1069 return m 1070 1071 def __ror__(self, other): 1072 if not isinstance(other, _collections_abc.Mapping): 1073 return NotImplemented 1074 m = dict(other) 1075 for child in reversed(self.maps): 1076 m.update(child) 1077 return self.__class__(m) 1078 1079 1080################################################################################ 1081### UserDict 1082################################################################################ 1083 1084class UserDict(_collections_abc.MutableMapping): 1085 1086 # Start by filling-out the abstract methods 1087 def __init__(self, dict=None, /, **kwargs): 1088 self.data = {} 1089 if dict is not None: 1090 self.update(dict) 1091 if kwargs: 1092 self.update(kwargs) 1093 1094 def __len__(self): 1095 return len(self.data) 1096 1097 def __getitem__(self, key): 1098 if key in self.data: 1099 return self.data[key] 1100 if hasattr(self.__class__, "__missing__"): 1101 return self.__class__.__missing__(self, key) 1102 raise KeyError(key) 1103 1104 def __setitem__(self, key, item): 1105 self.data[key] = item 1106 1107 def __delitem__(self, key): 1108 del self.data[key] 1109 1110 def __iter__(self): 1111 return iter(self.data) 1112 1113 # Modify __contains__ to work correctly when __missing__ is present 1114 def __contains__(self, key): 1115 return key in self.data 1116 1117 # Now, add the methods in dicts but not in MutableMapping 1118 def __repr__(self): 1119 return repr(self.data) 1120 1121 def __or__(self, other): 1122 if isinstance(other, UserDict): 1123 return self.__class__(self.data | other.data) 1124 if isinstance(other, dict): 1125 return self.__class__(self.data | other) 1126 return NotImplemented 1127 1128 def __ror__(self, other): 1129 if isinstance(other, UserDict): 1130 return self.__class__(other.data | self.data) 1131 if isinstance(other, dict): 1132 return self.__class__(other | self.data) 1133 return NotImplemented 1134 1135 def __ior__(self, other): 1136 if isinstance(other, UserDict): 1137 self.data |= other.data 1138 else: 1139 self.data |= other 1140 return self 1141 1142 def __copy__(self): 1143 inst = self.__class__.__new__(self.__class__) 1144 inst.__dict__.update(self.__dict__) 1145 # Create a copy and avoid triggering descriptors 1146 inst.__dict__["data"] = self.__dict__["data"].copy() 1147 return inst 1148 1149 def copy(self): 1150 if self.__class__ is UserDict: 1151 return UserDict(self.data.copy()) 1152 import copy 1153 data = self.data 1154 try: 1155 self.data = {} 1156 c = copy.copy(self) 1157 finally: 1158 self.data = data 1159 c.update(self) 1160 return c 1161 1162 @classmethod 1163 def fromkeys(cls, iterable, value=None): 1164 d = cls() 1165 for key in iterable: 1166 d[key] = value 1167 return d 1168 1169 1170################################################################################ 1171### UserList 1172################################################################################ 1173 1174class UserList(_collections_abc.MutableSequence): 1175 """A more or less complete user-defined wrapper around list objects.""" 1176 1177 def __init__(self, initlist=None): 1178 self.data = [] 1179 if initlist is not None: 1180 # XXX should this accept an arbitrary sequence? 1181 if type(initlist) == type(self.data): 1182 self.data[:] = initlist 1183 elif isinstance(initlist, UserList): 1184 self.data[:] = initlist.data[:] 1185 else: 1186 self.data = list(initlist) 1187 1188 def __repr__(self): 1189 return repr(self.data) 1190 1191 def __lt__(self, other): 1192 return self.data < self.__cast(other) 1193 1194 def __le__(self, other): 1195 return self.data <= self.__cast(other) 1196 1197 def __eq__(self, other): 1198 return self.data == self.__cast(other) 1199 1200 def __gt__(self, other): 1201 return self.data > self.__cast(other) 1202 1203 def __ge__(self, other): 1204 return self.data >= self.__cast(other) 1205 1206 def __cast(self, other): 1207 return other.data if isinstance(other, UserList) else other 1208 1209 def __contains__(self, item): 1210 return item in self.data 1211 1212 def __len__(self): 1213 return len(self.data) 1214 1215 def __getitem__(self, i): 1216 if isinstance(i, slice): 1217 return self.__class__(self.data[i]) 1218 else: 1219 return self.data[i] 1220 1221 def __setitem__(self, i, item): 1222 self.data[i] = item 1223 1224 def __delitem__(self, i): 1225 del self.data[i] 1226 1227 def __add__(self, other): 1228 if isinstance(other, UserList): 1229 return self.__class__(self.data + other.data) 1230 elif isinstance(other, type(self.data)): 1231 return self.__class__(self.data + other) 1232 return self.__class__(self.data + list(other)) 1233 1234 def __radd__(self, other): 1235 if isinstance(other, UserList): 1236 return self.__class__(other.data + self.data) 1237 elif isinstance(other, type(self.data)): 1238 return self.__class__(other + self.data) 1239 return self.__class__(list(other) + self.data) 1240 1241 def __iadd__(self, other): 1242 if isinstance(other, UserList): 1243 self.data += other.data 1244 elif isinstance(other, type(self.data)): 1245 self.data += other 1246 else: 1247 self.data += list(other) 1248 return self 1249 1250 def __mul__(self, n): 1251 return self.__class__(self.data * n) 1252 1253 __rmul__ = __mul__ 1254 1255 def __imul__(self, n): 1256 self.data *= n 1257 return self 1258 1259 def __copy__(self): 1260 inst = self.__class__.__new__(self.__class__) 1261 inst.__dict__.update(self.__dict__) 1262 # Create a copy and avoid triggering descriptors 1263 inst.__dict__["data"] = self.__dict__["data"][:] 1264 return inst 1265 1266 def append(self, item): 1267 self.data.append(item) 1268 1269 def insert(self, i, item): 1270 self.data.insert(i, item) 1271 1272 def pop(self, i=-1): 1273 return self.data.pop(i) 1274 1275 def remove(self, item): 1276 self.data.remove(item) 1277 1278 def clear(self): 1279 self.data.clear() 1280 1281 def copy(self): 1282 return self.__class__(self) 1283 1284 def count(self, item): 1285 return self.data.count(item) 1286 1287 def index(self, item, *args): 1288 return self.data.index(item, *args) 1289 1290 def reverse(self): 1291 self.data.reverse() 1292 1293 def sort(self, /, *args, **kwds): 1294 self.data.sort(*args, **kwds) 1295 1296 def extend(self, other): 1297 if isinstance(other, UserList): 1298 self.data.extend(other.data) 1299 else: 1300 self.data.extend(other) 1301 1302 1303################################################################################ 1304### UserString 1305################################################################################ 1306 1307class UserString(_collections_abc.Sequence): 1308 1309 def __init__(self, seq): 1310 if isinstance(seq, str): 1311 self.data = seq 1312 elif isinstance(seq, UserString): 1313 self.data = seq.data[:] 1314 else: 1315 self.data = str(seq) 1316 1317 def __str__(self): 1318 return str(self.data) 1319 1320 def __repr__(self): 1321 return repr(self.data) 1322 1323 def __int__(self): 1324 return int(self.data) 1325 1326 def __float__(self): 1327 return float(self.data) 1328 1329 def __complex__(self): 1330 return complex(self.data) 1331 1332 def __hash__(self): 1333 return hash(self.data) 1334 1335 def __getnewargs__(self): 1336 return (self.data[:],) 1337 1338 def __eq__(self, string): 1339 if isinstance(string, UserString): 1340 return self.data == string.data 1341 return self.data == string 1342 1343 def __lt__(self, string): 1344 if isinstance(string, UserString): 1345 return self.data < string.data 1346 return self.data < string 1347 1348 def __le__(self, string): 1349 if isinstance(string, UserString): 1350 return self.data <= string.data 1351 return self.data <= string 1352 1353 def __gt__(self, string): 1354 if isinstance(string, UserString): 1355 return self.data > string.data 1356 return self.data > string 1357 1358 def __ge__(self, string): 1359 if isinstance(string, UserString): 1360 return self.data >= string.data 1361 return self.data >= string 1362 1363 def __contains__(self, char): 1364 if isinstance(char, UserString): 1365 char = char.data 1366 return char in self.data 1367 1368 def __len__(self): 1369 return len(self.data) 1370 1371 def __getitem__(self, index): 1372 return self.__class__(self.data[index]) 1373 1374 def __add__(self, other): 1375 if isinstance(other, UserString): 1376 return self.__class__(self.data + other.data) 1377 elif isinstance(other, str): 1378 return self.__class__(self.data + other) 1379 return self.__class__(self.data + str(other)) 1380 1381 def __radd__(self, other): 1382 if isinstance(other, str): 1383 return self.__class__(other + self.data) 1384 return self.__class__(str(other) + self.data) 1385 1386 def __mul__(self, n): 1387 return self.__class__(self.data * n) 1388 1389 __rmul__ = __mul__ 1390 1391 def __mod__(self, args): 1392 return self.__class__(self.data % args) 1393 1394 def __rmod__(self, template): 1395 return self.__class__(str(template) % self) 1396 1397 # the following methods are defined in alphabetical order: 1398 def capitalize(self): 1399 return self.__class__(self.data.capitalize()) 1400 1401 def casefold(self): 1402 return self.__class__(self.data.casefold()) 1403 1404 def center(self, width, *args): 1405 return self.__class__(self.data.center(width, *args)) 1406 1407 def count(self, sub, start=0, end=_sys.maxsize): 1408 if isinstance(sub, UserString): 1409 sub = sub.data 1410 return self.data.count(sub, start, end) 1411 1412 def removeprefix(self, prefix, /): 1413 if isinstance(prefix, UserString): 1414 prefix = prefix.data 1415 return self.__class__(self.data.removeprefix(prefix)) 1416 1417 def removesuffix(self, suffix, /): 1418 if isinstance(suffix, UserString): 1419 suffix = suffix.data 1420 return self.__class__(self.data.removesuffix(suffix)) 1421 1422 def encode(self, encoding='utf-8', errors='strict'): 1423 encoding = 'utf-8' if encoding is None else encoding 1424 errors = 'strict' if errors is None else errors 1425 return self.data.encode(encoding, errors) 1426 1427 def endswith(self, suffix, start=0, end=_sys.maxsize): 1428 return self.data.endswith(suffix, start, end) 1429 1430 def expandtabs(self, tabsize=8): 1431 return self.__class__(self.data.expandtabs(tabsize)) 1432 1433 def find(self, sub, start=0, end=_sys.maxsize): 1434 if isinstance(sub, UserString): 1435 sub = sub.data 1436 return self.data.find(sub, start, end) 1437 1438 def format(self, /, *args, **kwds): 1439 return self.data.format(*args, **kwds) 1440 1441 def format_map(self, mapping): 1442 return self.data.format_map(mapping) 1443 1444 def index(self, sub, start=0, end=_sys.maxsize): 1445 return self.data.index(sub, start, end) 1446 1447 def isalpha(self): 1448 return self.data.isalpha() 1449 1450 def isalnum(self): 1451 return self.data.isalnum() 1452 1453 def isascii(self): 1454 return self.data.isascii() 1455 1456 def isdecimal(self): 1457 return self.data.isdecimal() 1458 1459 def isdigit(self): 1460 return self.data.isdigit() 1461 1462 def isidentifier(self): 1463 return self.data.isidentifier() 1464 1465 def islower(self): 1466 return self.data.islower() 1467 1468 def isnumeric(self): 1469 return self.data.isnumeric() 1470 1471 def isprintable(self): 1472 return self.data.isprintable() 1473 1474 def isspace(self): 1475 return self.data.isspace() 1476 1477 def istitle(self): 1478 return self.data.istitle() 1479 1480 def isupper(self): 1481 return self.data.isupper() 1482 1483 def join(self, seq): 1484 return self.data.join(seq) 1485 1486 def ljust(self, width, *args): 1487 return self.__class__(self.data.ljust(width, *args)) 1488 1489 def lower(self): 1490 return self.__class__(self.data.lower()) 1491 1492 def lstrip(self, chars=None): 1493 return self.__class__(self.data.lstrip(chars)) 1494 1495 maketrans = str.maketrans 1496 1497 def partition(self, sep): 1498 return self.data.partition(sep) 1499 1500 def replace(self, old, new, maxsplit=-1): 1501 if isinstance(old, UserString): 1502 old = old.data 1503 if isinstance(new, UserString): 1504 new = new.data 1505 return self.__class__(self.data.replace(old, new, maxsplit)) 1506 1507 def rfind(self, sub, start=0, end=_sys.maxsize): 1508 if isinstance(sub, UserString): 1509 sub = sub.data 1510 return self.data.rfind(sub, start, end) 1511 1512 def rindex(self, sub, start=0, end=_sys.maxsize): 1513 return self.data.rindex(sub, start, end) 1514 1515 def rjust(self, width, *args): 1516 return self.__class__(self.data.rjust(width, *args)) 1517 1518 def rpartition(self, sep): 1519 return self.data.rpartition(sep) 1520 1521 def rstrip(self, chars=None): 1522 return self.__class__(self.data.rstrip(chars)) 1523 1524 def split(self, sep=None, maxsplit=-1): 1525 return self.data.split(sep, maxsplit) 1526 1527 def rsplit(self, sep=None, maxsplit=-1): 1528 return self.data.rsplit(sep, maxsplit) 1529 1530 def splitlines(self, keepends=False): 1531 return self.data.splitlines(keepends) 1532 1533 def startswith(self, prefix, start=0, end=_sys.maxsize): 1534 return self.data.startswith(prefix, start, end) 1535 1536 def strip(self, chars=None): 1537 return self.__class__(self.data.strip(chars)) 1538 1539 def swapcase(self): 1540 return self.__class__(self.data.swapcase()) 1541 1542 def title(self): 1543 return self.__class__(self.data.title()) 1544 1545 def translate(self, *args): 1546 return self.__class__(self.data.translate(*args)) 1547 1548 def upper(self): 1549 return self.__class__(self.data.upper()) 1550 1551 def zfill(self, width): 1552 return self.__class__(self.data.zfill(width)) 1553