'ChainMap',

'Counter',

'OrderedDict',

'UserDict',

'UserList',

'UserString',

'defaultdict',

'deque',

'namedtuple',

def __reversed__(self):

for key in reversed(self._mapping):

def __reversed__(self):

for key in reversed(self._mapping):

'Dictionary that remembers insertion order'

# An inherited dict maps keys to values.

# The inherited dict provides __getitem__, __len__, __contains__, and get.

# The remaining methods are order-aware.

# Big-O running times for all methods are the same as regular dictionaries.

# The internal self.__map dict maps keys to links in a doubly linked list.

# The circular doubly linked list starts and ends with a sentinel element.

# The sentinel element never gets deleted (this simplifies the algorithm).

# The sentinel is in self.__hardroot with a weakref proxy in self.__root.

# The prev links are weakref proxies (to prevent circular references).

# Individual links are kept alive by the hard reference in self.__map.

# Those hard references disappear when a key is deleted from an OrderedDict.

def __new__(cls, /, *args, **kwds):

"Create the ordered dict object and set up the underlying structures."

self = dict.__new__(cls)

self.__hardroot = _Link()

self.__root = root = _proxy(self.__hardroot)

root.prev = root.next = root

self.__map = {}

return self

def __init__(self, other=(), /, **kwds):

'''Initialize an ordered dictionary. The signature is the same as

self.__update(other, **kwds)

def __setitem__(self, key, value,

dict_setitem=dict.__setitem__, proxy=_proxy, Link=_Link):

'od.__setitem__(i, y) <==> od[i]=y'

# Setting a new item creates a new link at the end of the linked list,

# and the inherited dictionary is updated with the new key/value pair.

if key not in self:

self.__map[key] = link = Link()

root = self.__root

last = root.prev

link.prev, link.next, link.key = last, root, key

last.next = link

root.prev = proxy(link)

dict_setitem(self, key, value)

def __delitem__(self, key, dict_delitem=dict.__delitem__):

'od.__delitem__(y) <==> del od[y]'

# Deleting an existing item uses self.__map to find the link which gets

# removed by updating the links in the predecessor and successor nodes.

dict_delitem(self, key)

link = self.__map.pop(key)

link_prev = link.prev

link_next = link.next

link_prev.next = link_next

link_next.prev = link_prev

link.prev = None

link.next = None

def __iter__(self):

'od.__iter__() <==> iter(od)'

# Traverse the linked list in order.

root = self.__root

curr = root.next

while curr is not root:

yield curr.key

curr = curr.next

def __reversed__(self):

'od.__reversed__() <==> reversed(od)'

# Traverse the linked list in reverse order.

root = self.__root

curr = root.prev

while curr is not root:

yield curr.key

curr = curr.prev

def clear(self):

'od.clear() -> None. Remove all items from od.'

root = self.__root

root.prev = root.next = root

self.__map.clear()

dict.clear(self)

def popitem(self, last=True):

'''Remove and return a (key, value) pair from the dictionary.

if not self:

raise KeyError('dictionary is empty')

root = self.__root

if last:

link = root.prev

link_prev = link.prev

link_prev.next = root

root.prev = link_prev

else:

link = root.next

link_next = link.next

root.next = link_next

link_next.prev = root

key = link.key

del self.__map[key]

value = dict.pop(self, key)

return key, value

def move_to_end(self, key, last=True):

'''Move an existing element to the end (or beginning if last is false).

link = self.__map[key]

link_prev = link.prev

link_next = link.next

soft_link = link_next.prev

link_prev.next = link_next

link_next.prev = link_prev

root = self.__root

if last:

last = root.prev

link.prev = last

link.next = root

root.prev = soft_link

last.next = link

else:

first = root.next

link.prev = root

link.next = first

first.prev = soft_link

root.next = link

def __sizeof__(self):

sizeof = _sys.getsizeof

n = len(self) + 1 # number of links including root

size = sizeof(self.__dict__) # instance dictionary

size += sizeof(self.__map) * 2 # internal dict and inherited dict

size += sizeof(self.__hardroot) * n # link objects

size += sizeof(self.__root) * n # proxy objects

return size

update = __update = _collections_abc.MutableMapping.update

def keys(self):

"D.keys() -> a set-like object providing a view on D's keys"

return _OrderedDictKeysView(self)

def items(self):

"D.items() -> a set-like object providing a view on D's items"

return _OrderedDictItemsView(self)

def values(self):

"D.values() -> an object providing a view on D's values"

return _OrderedDictValuesView(self)

__ne__ = _collections_abc.MutableMapping.__ne__

__marker = object()

def pop(self, key, default=__marker):

'''od.pop(k[,d]) -> v, remove specified key and return the corresponding

marker = self.__marker

result = dict.pop(self, key, marker)

if result is not marker:

# The same as in __delitem__().

link = self.__map.pop(key)

link_prev = link.prev

link_next = link.next

link_prev.next = link_next

link_next.prev = link_prev

link.prev = None

link.next = None

return result

if default is marker:

raise KeyError(key)

return default

def setdefault(self, key, default=None):

'''Insert key with a value of default if key is not in the dictionary.

if key in self:

return self[key]

self[key] = default

return default

@_recursive_repr()

def __repr__(self):

'od.__repr__() <==> repr(od)'

if not self:

return '%s()' % (self.__class__.__name__,)

return '%s(%r)' % (self.__class__.__name__, dict(self.items()))

def __reduce__(self):

'Return state information for pickling'

state = self.__getstate__()

if state:

if isinstance(state, tuple):

state, slots = state

else:

slots = {}

state = state.copy()

slots = slots.copy()

for k in vars(OrderedDict()):

state.pop(k, None)

slots.pop(k, None)

if slots:

state = state, slots

else:

state = state or None

return self.__class__, (), state, None, iter(self.items())

def copy(self):

'od.copy() -> a shallow copy of od'

return self.__class__(self)

@classmethod

def fromkeys(cls, iterable, value=None):

'''Create a new ordered dictionary with keys from iterable and values set to value.

self = cls()

for key in iterable:

self[key] = value

return self

def __eq__(self, other):

'''od.__eq__(y) <==> od==y. Comparison to another OD is order-sensitive

if isinstance(other, OrderedDict):

return dict.__eq__(self, other) and all(map(_eq, self, other))

return dict.__eq__(self, other)

def __ior__(self, other):

self.update(other)

return self

def __or__(self, other):

if not isinstance(other, (dict, frozendict)):

return NotImplemented

new = self.__class__(self)

new.update(other)

return new

def __ror__(self, other):

if not isinstance(other, (dict, frozendict)):

return NotImplemented

new = self.__class__(other)

new.update(self)

"""Returns a new subclass of tuple with named fields.

# Validate the field names. At the user's option, either generate an error

# message or automatically replace the field name with a valid name.

if isinstance(field_names, str):

field_names = field_names.replace(',', ' ').split()

field_names = list(map(str, field_names))

typename = _sys.intern(str(typename))

if rename:

seen = set()

for index, name in enumerate(field_names):

if (not name.isidentifier()

or _iskeyword(name)

or name.startswith('_')

or name in seen):

field_names[index] = f'_{index}'

seen.add(name)

for name in [typename] + field_names:

if type(name) is not str:

raise TypeError('Type names and field names must be strings')

if not name.isidentifier():

raise ValueError('Type names and field names must be valid '

f'identifiers: {name!r}')

if _iskeyword(name):

raise ValueError('Type names and field names cannot be a '

f'keyword: {name!r}')

seen = set()

for name in field_names:

if name.startswith('_') and not rename:

raise ValueError('Field names cannot start with an underscore: '

f'{name!r}')

if name in seen:

raise ValueError(f'Encountered duplicate field name: {name!r}')

seen.add(name)

field_defaults = {}

if defaults is not None:

defaults = tuple(defaults)

if len(defaults) > len(field_names):

raise TypeError('Got more default values than field names')

field_defaults = dict(reversed(list(zip(reversed(field_names),

reversed(defaults)))))

# Variables used in the methods and docstrings

field_names = tuple(map(_sys.intern, field_names))

num_fields = len(field_names)

arg_list = ', '.join(field_names)

if num_fields == 1:

arg_list += ','

repr_fmt = '(' + ', '.join(f'{name}=%r' for name in field_names) + ')'

tuple_new = tuple.__new__

_dict, _tuple, _len, _map, _zip = dict, tuple, len, map, zip

# Create all the named tuple methods to be added to the class namespace

namespace = {

'_tuple_new': tuple_new,

'__builtins__': {},

'__name__': f'namedtuple_{typename}',

}

code = f'lambda _cls, {arg_list}: _tuple_new(_cls, ({arg_list}))'

__new__ = eval(code, namespace)

__new__.__name__ = '__new__'

__new__.__doc__ = f'Create new instance of {typename}({arg_list})'

if defaults is not None:

__new__.__defaults__ = defaults

@classmethod

def _make(cls, iterable):

result = tuple_new(cls, iterable)

if _len(result) != num_fields:

raise TypeError(f'Expected {num_fields} arguments, got {len(result)}')

return result

_make.__func__.__doc__ = (f'Make a new {typename} object from a sequence '

'or iterable')

def _replace(self, /, **kwds):

result = self._make(_map(kwds.pop, field_names, self))

if kwds:

raise TypeError(f'Got unexpected field names: {list(kwds)!r}')

return result

_replace.__doc__ = (f'Return a new {typename} object replacing specified '

'fields with new values')

def __repr__(self):

'Return a nicely formatted representation string'

return self.__class__.__name__ + repr_fmt % self

def _asdict(self):

'Return a new dict which maps field names to their values.'

return _dict(_zip(self._fields, self))

def __getnewargs__(self):

'Return self as a plain tuple. Used by copy and pickle.'

return _tuple(self)

# Modify function metadata to help with introspection and debugging

for method in (

__new__,

_make.__func__,

_replace,

__repr__,

_asdict,

__getnewargs__,

):

method.__qualname__ = f'{typename}.{method.__name__}'

# Build-up the class namespace dictionary

# and use type() to build the result class

class_namespace = {

'__doc__': f'{typename}({arg_list})',

'__slots__': (),

'_fields': field_names,

'_field_defaults': field_defaults,

'__new__': __new__,

'_make': _make,

'__replace__': _replace,

'_replace': _replace,

'__repr__': __repr__,

'_asdict': _asdict,

'__getnewargs__': __getnewargs__,

'__match_args__': field_names,

}

for index, name in enumerate(field_names):

doc = _sys.intern(f'Alias for field number {index}')

class_namespace[name] = _tuplegetter(index, doc)

result = type(typename, (tuple,), class_namespace)

# For pickling to work, the __module__ variable needs to be set to the frame

# where the named tuple is created. Bypass this step in environments where

# sys._getframe is not defined (Jython for example) or sys._getframe is not

# defined for arguments greater than 0 (IronPython), or where the user has

# specified a particular module.

if module is None:

try:

module = _sys._getframemodulename(1) or '__main__'

except AttributeError:

try:

module = _sys._getframe(1).f_globals.get('__name__', '__main__')

except (AttributeError, ValueError):

pass

if module is not None:

result.__module__ = module

'Tally elements from the iterable.'

mapping_get = mapping.get

for elem in iterable:

'''Dict subclass for counting hashable items. Sometimes called a bag

# References:

# http://en.wikipedia.org/wiki/Multiset

# http://www.gnu.org/software/smalltalk/manual-base/html_node/Bag.html

# http://www.java2s.com/Tutorial/Cpp/0380__set-multiset/Catalog0380__set-multiset.htm

# http://code.activestate.com/recipes/259174/

# Knuth, TAOCP Vol. II section 4.6.3

def __init__(self, iterable=None, /, **kwds):

'''Create a new, empty Counter object. And if given, count elements

super().__init__()

self.update(iterable, **kwds)

def __missing__(self, key):

'The count of elements not in the Counter is zero.'

# Needed so that self[missing_item] does not raise KeyError

return 0

def total(self):

'Sum of the counts'

return sum(self.values())

def most_common(self, n=None):

'''List the n most common elements and their counts from the most

# Emulate Bag.sortedByCount from Smalltalk

if n is None:

return sorted(self.items(), key=_itemgetter(1), reverse=True)

return _nlargest(n, self.items(), key=_itemgetter(1))

def elements(self):

'''Iterator over elements repeating each as many times as its count.

# Emulate Bag.do from Smalltalk and Multiset.begin from C++.

return _chain.from_iterable(_starmap(_repeat, self.items()))

# Override dict methods where necessary

@classmethod

def fromkeys(cls, iterable, v=None):

# There is no equivalent method for counters because the semantics

# would be ambiguous in cases such as Counter.fromkeys('aaabbc', v=2).

# Initializing counters to zero values isn't necessary because zero

# is already the default value for counter lookups. Initializing

# to one is easily accomplished with Counter(set(iterable)). For

# more exotic cases, create a dictionary first using a dictionary

# comprehension or dict.fromkeys().

raise NotImplementedError(

'Counter.fromkeys() is undefined. Use Counter(iterable) instead.')

def update(self, iterable=None, /, **kwds):

'''Like dict.update() but add counts instead of replacing them.

# The regular dict.update() operation makes no sense here because the

# replace behavior results in some of the original untouched counts

# being mixed-in with all of the other counts for a mismash that

# doesn't have a straight-forward interpretation in most counting

# contexts. Instead, we implement straight-addition. Both the inputs

# and outputs are allowed to contain zero and negative counts.

if iterable is not None:

if isinstance(iterable, _collections_abc.Mapping):

if self:

self_get = self.get

for elem, count in iterable.items():

self[elem] = count + self_get(elem, 0)

else:

# fast path when counter is empty

super().update(iterable)

else:

_count_elements(self, iterable)

if kwds:

self.update(kwds)

def subtract(self, iterable=None, /, **kwds):

'''Like dict.update() but subtracts counts instead of replacing them.

if iterable is not None:

self_get = self.get

if isinstance(iterable, _collections_abc.Mapping):

for elem, count in iterable.items():

self[elem] = self_get(elem, 0) - count

else:

for elem in iterable:

self[elem] = self_get(elem, 0) - 1

if kwds:

self.subtract(kwds)

def copy(self):

'Return a shallow copy.'

return self.__class__(self)

def __reduce__(self):

return self.__class__, (dict(self),)

def __delitem__(self, elem):

'Like dict.__delitem__() but does not raise KeyError for missing values.'

if elem in self:

super().__delitem__(elem)

def __repr__(self):

if not self:

return f'{self.__class__.__name__}()'

try:

# dict() preserves the ordering returned by most_common()

d = dict(self.most_common())

except TypeError:

# handle case where values are not orderable

d = dict(self)

return f'{self.__class__.__name__}({d!r})'

# Multiset-style mathematical operations discussed in:

# Knuth TAOCP Volume II section 4.6.3 exercise 19

# and at http://en.wikipedia.org/wiki/Multiset

#

# Outputs guaranteed to only include positive counts.

#

# To strip negative and zero counts, add-in an empty counter:

# c += Counter()

#

# Results are ordered according to when an element is first

# encountered in the left operand and then by the order

# encountered in the right operand.

#

# When the multiplicities are all zero or one, multiset operations

# are guaranteed to be equivalent to the corresponding operations

# for regular sets.

#

# Given counter multisets such as:

# cp = Counter(a=1, b=0, c=1)

# cq = Counter(c=1, d=0, e=1)

#

# The corresponding regular sets would be:

# sp = {'a', 'c'}

# sq = {'c', 'e'}

#

# All of the following relations would hold:

# (cp == cq) == (sp == sq)

# (cp != cq) == (sp != sq)

# (cp <= cq) == (sp <= sq)

# (cp < cq) == (sp < sq)

# (cp >= cq) == (sp >= sq)

# (cp > cq) == (sp > sq)

# set(cp + cq) == sp | sq

# set(cp - cq) == sp - sq

# set(cp | cq) == sp | sq

# set(cp & cq) == sp & sq

# set(cp ^ cq) == sp ^ sq

def __eq__(self, other):

'True if all counts agree. Missing counts are treated as zero.'

if not isinstance(other, Counter):

return NotImplemented

return all(self[e] == other[e] for c in (self, other) for e in c)

def __ne__(self, other):

'True if any counts disagree. Missing counts are treated as zero.'

if not isinstance(other, Counter):

return NotImplemented

return not self == other

def __le__(self, other):

'True if all counts in self are a subset of those in other.'

if not isinstance(other, Counter):

return NotImplemented

return all(self[e] <= other[e] for c in (self, other) for e in c)

def __lt__(self, other):

'True if all counts in self are a proper subset of those in other.'

if not isinstance(other, Counter):

return NotImplemented

return self <= other and self != other

def __ge__(self, other):

'True if all counts in self are a superset of those in other.'

if not isinstance(other, Counter):

return NotImplemented

return all(self[e] >= other[e] for c in (self, other) for e in c)

def __gt__(self, other):

'True if all counts in self are a proper superset of those in other.'

if not isinstance(other, Counter):

return NotImplemented

return self >= other and self != other

def __add__(self, other):

'''Add counts from two counters.

if not isinstance(other, Counter):

return NotImplemented

result = Counter()

for elem, count in self.items():

newcount = count + other[elem]

if newcount > 0:

result[elem] = newcount

for elem, count in other.items():

if elem not in self and count > 0:

result[elem] = count

return result

def __sub__(self, other):

''' Subtract count, but keep only results with positive counts.

if not isinstance(other, Counter):

return NotImplemented

result = Counter()

for elem, count in self.items():

newcount = count - other[elem]

if newcount > 0:

result[elem] = newcount

for elem, count in other.items():

if elem not in self and count < 0:

result[elem] = 0 - count

return result

def __or__(self, other):

'''Union is the maximum of value in either of the input counters.

if not isinstance(other, Counter):

return NotImplemented

result = Counter()

for elem, count in self.items():

other_count = other[elem]

newcount = other_count if count < other_count else count

if newcount > 0:

result[elem] = newcount

for elem, count in other.items():

if elem not in self and count > 0:

result[elem] = count

return result

def __and__(self, other):

''' Intersection is the minimum of corresponding counts.

if not isinstance(other, Counter):

return NotImplemented

result = Counter()

for elem, count in self.items():

other_count = other[elem]

newcount = count if count < other_count else other_count

if newcount > 0:

result[elem] = newcount

return result

def __xor__(self, other):

'''Symmetric difference. Absolute value of count differences.

if not isinstance(other, Counter):

return NotImplemented

result = Counter()

for elem, count in self.items():

newcount = abs(count - other[elem])

if newcount:

result[elem] = newcount

for elem, count in other.items():

if elem not in self and count:

result[elem] = abs(count)

return result

def __pos__(self):

'Adds an empty counter, effectively stripping negative and zero counts'

result = Counter()

for elem, count in self.items():

if count > 0:

result[elem] = count

return result

def __neg__(self):

'''Subtracts from an empty counter. Strips positive and zero counts,

result = Counter()

for elem, count in self.items():

if count < 0:

result[elem] = 0 - count

return result

def _keep_positive(self):

'''Internal method to strip elements with a negative or zero count'''

nonpositive = [elem for elem, count in self.items() if not count > 0]

for elem in nonpositive:

del self[elem]

return self

def __iadd__(self, other):

'''Inplace add from another counter, keeping only positive counts.

for elem, count in other.items():

self[elem] += count

return self._keep_positive()

def __isub__(self, other):

'''Inplace subtract counter, but keep only results with positive counts.

for elem, count in other.items():

self[elem] -= count

return self._keep_positive()

def __ior__(self, other):

'''Inplace union is the maximum of value from either counter.

for elem, other_count in other.items():

count = self[elem]

if other_count > count: