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