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