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