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