10a8c90248264a8b26970b4473770bcc3df8515fJosh Gao__all__ = ['Counter', 'deque', 'defaultdict', 'namedtuple', 'OrderedDict'] 20a8c90248264a8b26970b4473770bcc3df8515fJosh Gao# For bootstrapping reasons, the collection ABCs are defined in _abcoll.py. 30a8c90248264a8b26970b4473770bcc3df8515fJosh Gao# They should however be considered an integral part of collections.py. 40a8c90248264a8b26970b4473770bcc3df8515fJosh Gaofrom _abcoll import * 50a8c90248264a8b26970b4473770bcc3df8515fJosh Gaoimport _abcoll 60a8c90248264a8b26970b4473770bcc3df8515fJosh Gao__all__ += _abcoll.__all__ 70a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 80a8c90248264a8b26970b4473770bcc3df8515fJosh Gaofrom _collections import deque, defaultdict 90a8c90248264a8b26970b4473770bcc3df8515fJosh Gaofrom operator import itemgetter as _itemgetter, eq as _eq 100a8c90248264a8b26970b4473770bcc3df8515fJosh Gaofrom keyword import iskeyword as _iskeyword 110a8c90248264a8b26970b4473770bcc3df8515fJosh Gaoimport sys as _sys 120a8c90248264a8b26970b4473770bcc3df8515fJosh Gaoimport heapq as _heapq 130a8c90248264a8b26970b4473770bcc3df8515fJosh Gaofrom itertools import repeat as _repeat, chain as _chain, starmap as _starmap 140a8c90248264a8b26970b4473770bcc3df8515fJosh Gaofrom itertools import imap as _imap 150a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 160a8c90248264a8b26970b4473770bcc3df8515fJosh Gaotry: 170a8c90248264a8b26970b4473770bcc3df8515fJosh Gao from thread import get_ident as _get_ident 180a8c90248264a8b26970b4473770bcc3df8515fJosh Gaoexcept ImportError: 190a8c90248264a8b26970b4473770bcc3df8515fJosh Gao from dummy_thread import get_ident as _get_ident 200a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 210a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 220a8c90248264a8b26970b4473770bcc3df8515fJosh Gao################################################################################ 230a8c90248264a8b26970b4473770bcc3df8515fJosh Gao### OrderedDict 240a8c90248264a8b26970b4473770bcc3df8515fJosh Gao################################################################################ 250a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 260a8c90248264a8b26970b4473770bcc3df8515fJosh Gaoclass OrderedDict(dict): 270a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 'Dictionary that remembers insertion order' 280a8c90248264a8b26970b4473770bcc3df8515fJosh Gao # An inherited dict maps keys to values. 290a8c90248264a8b26970b4473770bcc3df8515fJosh Gao # The inherited dict provides __getitem__, __len__, __contains__, and get. 300a8c90248264a8b26970b4473770bcc3df8515fJosh Gao # The remaining methods are order-aware. 310a8c90248264a8b26970b4473770bcc3df8515fJosh Gao # Big-O running times for all methods are the same as regular dictionaries. 320a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 330a8c90248264a8b26970b4473770bcc3df8515fJosh Gao # The internal self.__map dict maps keys to links in a doubly linked list. 340a8c90248264a8b26970b4473770bcc3df8515fJosh Gao # The circular doubly linked list starts and ends with a sentinel element. 350a8c90248264a8b26970b4473770bcc3df8515fJosh Gao # The sentinel element never gets deleted (this simplifies the algorithm). 360a8c90248264a8b26970b4473770bcc3df8515fJosh Gao # Each link is stored as a list of length three: [PREV, NEXT, KEY]. 370a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 380a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def __init__(self, *args, **kwds): 390a8c90248264a8b26970b4473770bcc3df8515fJosh Gao '''Initialize an ordered dictionary. The signature is the same as 400a8c90248264a8b26970b4473770bcc3df8515fJosh Gao regular dictionaries, but keyword arguments are not recommended because 410a8c90248264a8b26970b4473770bcc3df8515fJosh Gao their insertion order is arbitrary. 420a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 430a8c90248264a8b26970b4473770bcc3df8515fJosh Gao ''' 440a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if len(args) > 1: 450a8c90248264a8b26970b4473770bcc3df8515fJosh Gao raise TypeError('expected at most 1 arguments, got %d' % len(args)) 460a8c90248264a8b26970b4473770bcc3df8515fJosh Gao try: 470a8c90248264a8b26970b4473770bcc3df8515fJosh Gao self.__root 480a8c90248264a8b26970b4473770bcc3df8515fJosh Gao except AttributeError: 490a8c90248264a8b26970b4473770bcc3df8515fJosh Gao self.__root = root = [] # sentinel node 500a8c90248264a8b26970b4473770bcc3df8515fJosh Gao root[:] = [root, root, None] 510a8c90248264a8b26970b4473770bcc3df8515fJosh Gao self.__map = {} 520a8c90248264a8b26970b4473770bcc3df8515fJosh Gao self.__update(*args, **kwds) 530a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 540a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def __setitem__(self, key, value, dict_setitem=dict.__setitem__): 550a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 'od.__setitem__(i, y) <==> od[i]=y' 560a8c90248264a8b26970b4473770bcc3df8515fJosh Gao # Setting a new item creates a new link at the end of the linked list, 570a8c90248264a8b26970b4473770bcc3df8515fJosh Gao # and the inherited dictionary is updated with the new key/value pair. 580a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if key not in self: 590a8c90248264a8b26970b4473770bcc3df8515fJosh Gao root = self.__root 600a8c90248264a8b26970b4473770bcc3df8515fJosh Gao last = root[0] 610a8c90248264a8b26970b4473770bcc3df8515fJosh Gao last[1] = root[0] = self.__map[key] = [last, root, key] 620a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return dict_setitem(self, key, value) 630a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 640a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def __delitem__(self, key, dict_delitem=dict.__delitem__): 650a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 'od.__delitem__(y) <==> del od[y]' 660a8c90248264a8b26970b4473770bcc3df8515fJosh Gao # Deleting an existing item uses self.__map to find the link which gets 670a8c90248264a8b26970b4473770bcc3df8515fJosh Gao # removed by updating the links in the predecessor and successor nodes. 680a8c90248264a8b26970b4473770bcc3df8515fJosh Gao dict_delitem(self, key) 690a8c90248264a8b26970b4473770bcc3df8515fJosh Gao link_prev, link_next, _ = self.__map.pop(key) 700a8c90248264a8b26970b4473770bcc3df8515fJosh Gao link_prev[1] = link_next # update link_prev[NEXT] 710a8c90248264a8b26970b4473770bcc3df8515fJosh Gao link_next[0] = link_prev # update link_next[PREV] 720a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 730a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def __iter__(self): 740a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 'od.__iter__() <==> iter(od)' 750a8c90248264a8b26970b4473770bcc3df8515fJosh Gao # Traverse the linked list in order. 760a8c90248264a8b26970b4473770bcc3df8515fJosh Gao root = self.__root 770a8c90248264a8b26970b4473770bcc3df8515fJosh Gao curr = root[1] # start at the first node 780a8c90248264a8b26970b4473770bcc3df8515fJosh Gao while curr is not root: 790a8c90248264a8b26970b4473770bcc3df8515fJosh Gao yield curr[2] # yield the curr[KEY] 800a8c90248264a8b26970b4473770bcc3df8515fJosh Gao curr = curr[1] # move to next node 810a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 820a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def __reversed__(self): 830a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 'od.__reversed__() <==> reversed(od)' 840a8c90248264a8b26970b4473770bcc3df8515fJosh Gao # Traverse the linked list in reverse order. 850a8c90248264a8b26970b4473770bcc3df8515fJosh Gao root = self.__root 860a8c90248264a8b26970b4473770bcc3df8515fJosh Gao curr = root[0] # start at the last node 870a8c90248264a8b26970b4473770bcc3df8515fJosh Gao while curr is not root: 880a8c90248264a8b26970b4473770bcc3df8515fJosh Gao yield curr[2] # yield the curr[KEY] 890a8c90248264a8b26970b4473770bcc3df8515fJosh Gao curr = curr[0] # move to previous node 900a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 910a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def clear(self): 920a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 'od.clear() -> None. Remove all items from od.' 930a8c90248264a8b26970b4473770bcc3df8515fJosh Gao root = self.__root 940a8c90248264a8b26970b4473770bcc3df8515fJosh Gao root[:] = [root, root, None] 950a8c90248264a8b26970b4473770bcc3df8515fJosh Gao self.__map.clear() 960a8c90248264a8b26970b4473770bcc3df8515fJosh Gao dict.clear(self) 970a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 980a8c90248264a8b26970b4473770bcc3df8515fJosh Gao # -- the following methods do not depend on the internal structure -- 990a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 1000a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def keys(self): 1010a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 'od.keys() -> list of keys in od' 1020a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return list(self) 1030a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 1040a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def values(self): 1050a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 'od.values() -> list of values in od' 1060a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return [self[key] for key in self] 1070a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 1080a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def items(self): 1090a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 'od.items() -> list of (key, value) pairs in od' 1100a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return [(key, self[key]) for key in self] 1110a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 1120a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def iterkeys(self): 1130a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 'od.iterkeys() -> an iterator over the keys in od' 1140a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return iter(self) 1150a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 1160a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def itervalues(self): 1170a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 'od.itervalues -> an iterator over the values in od' 1180a8c90248264a8b26970b4473770bcc3df8515fJosh Gao for k in self: 1190a8c90248264a8b26970b4473770bcc3df8515fJosh Gao yield self[k] 1200a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 1210a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def iteritems(self): 1220a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 'od.iteritems -> an iterator over the (key, value) pairs in od' 1230a8c90248264a8b26970b4473770bcc3df8515fJosh Gao for k in self: 1240a8c90248264a8b26970b4473770bcc3df8515fJosh Gao yield (k, self[k]) 1250a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 1260a8c90248264a8b26970b4473770bcc3df8515fJosh Gao update = MutableMapping.update 1270a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 1280a8c90248264a8b26970b4473770bcc3df8515fJosh Gao __update = update # let subclasses override update without breaking __init__ 1290a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 1300a8c90248264a8b26970b4473770bcc3df8515fJosh Gao __marker = object() 1310a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 1320a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def pop(self, key, default=__marker): 1330a8c90248264a8b26970b4473770bcc3df8515fJosh Gao '''od.pop(k[,d]) -> v, remove specified key and return the corresponding 1340a8c90248264a8b26970b4473770bcc3df8515fJosh Gao value. If key is not found, d is returned if given, otherwise KeyError 1350a8c90248264a8b26970b4473770bcc3df8515fJosh Gao is raised. 1360a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 1370a8c90248264a8b26970b4473770bcc3df8515fJosh Gao ''' 1380a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if key in self: 1390a8c90248264a8b26970b4473770bcc3df8515fJosh Gao result = self[key] 1400a8c90248264a8b26970b4473770bcc3df8515fJosh Gao del self[key] 1410a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return result 1420a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if default is self.__marker: 1430a8c90248264a8b26970b4473770bcc3df8515fJosh Gao raise KeyError(key) 1440a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return default 1450a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 1460a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def setdefault(self, key, default=None): 1470a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 'od.setdefault(k[,d]) -> od.get(k,d), also set od[k]=d if k not in od' 1480a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if key in self: 1490a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return self[key] 1500a8c90248264a8b26970b4473770bcc3df8515fJosh Gao self[key] = default 1510a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return default 1520a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 1530a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def popitem(self, last=True): 1540a8c90248264a8b26970b4473770bcc3df8515fJosh Gao '''od.popitem() -> (k, v), return and remove a (key, value) pair. 1550a8c90248264a8b26970b4473770bcc3df8515fJosh Gao Pairs are returned in LIFO order if last is true or FIFO order if false. 1560a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 1570a8c90248264a8b26970b4473770bcc3df8515fJosh Gao ''' 1580a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if not self: 1590a8c90248264a8b26970b4473770bcc3df8515fJosh Gao raise KeyError('dictionary is empty') 1600a8c90248264a8b26970b4473770bcc3df8515fJosh Gao key = next(reversed(self) if last else iter(self)) 1610a8c90248264a8b26970b4473770bcc3df8515fJosh Gao value = self.pop(key) 1620a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return key, value 1630a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 1640a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def __repr__(self, _repr_running={}): 1650a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 'od.__repr__() <==> repr(od)' 1660a8c90248264a8b26970b4473770bcc3df8515fJosh Gao call_key = id(self), _get_ident() 1670a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if call_key in _repr_running: 1680a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return '...' 1690a8c90248264a8b26970b4473770bcc3df8515fJosh Gao _repr_running[call_key] = 1 1700a8c90248264a8b26970b4473770bcc3df8515fJosh Gao try: 1710a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if not self: 1720a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return '%s()' % (self.__class__.__name__,) 1730a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return '%s(%r)' % (self.__class__.__name__, self.items()) 1740a8c90248264a8b26970b4473770bcc3df8515fJosh Gao finally: 1750a8c90248264a8b26970b4473770bcc3df8515fJosh Gao del _repr_running[call_key] 1760a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 1770a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def __reduce__(self): 1780a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 'Return state information for pickling' 1790a8c90248264a8b26970b4473770bcc3df8515fJosh Gao items = [[k, self[k]] for k in self] 1800a8c90248264a8b26970b4473770bcc3df8515fJosh Gao inst_dict = vars(self).copy() 1810a8c90248264a8b26970b4473770bcc3df8515fJosh Gao for k in vars(OrderedDict()): 1820a8c90248264a8b26970b4473770bcc3df8515fJosh Gao inst_dict.pop(k, None) 1830a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if inst_dict: 1840a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return (self.__class__, (items,), inst_dict) 1850a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return self.__class__, (items,) 1860a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 1870a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def copy(self): 1880a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 'od.copy() -> a shallow copy of od' 1890a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return self.__class__(self) 1900a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 1910a8c90248264a8b26970b4473770bcc3df8515fJosh Gao @classmethod 1920a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def fromkeys(cls, iterable, value=None): 1930a8c90248264a8b26970b4473770bcc3df8515fJosh Gao '''OD.fromkeys(S[, v]) -> New ordered dictionary with keys from S. 1940a8c90248264a8b26970b4473770bcc3df8515fJosh Gao If not specified, the value defaults to None. 1950a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 1960a8c90248264a8b26970b4473770bcc3df8515fJosh Gao ''' 1970a8c90248264a8b26970b4473770bcc3df8515fJosh Gao self = cls() 1980a8c90248264a8b26970b4473770bcc3df8515fJosh Gao for key in iterable: 1990a8c90248264a8b26970b4473770bcc3df8515fJosh Gao self[key] = value 2000a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return self 2010a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 2020a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def __eq__(self, other): 2030a8c90248264a8b26970b4473770bcc3df8515fJosh Gao '''od.__eq__(y) <==> od==y. Comparison to another OD is order-sensitive 2040a8c90248264a8b26970b4473770bcc3df8515fJosh Gao while comparison to a regular mapping is order-insensitive. 2050a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 2060a8c90248264a8b26970b4473770bcc3df8515fJosh Gao ''' 2070a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if isinstance(other, OrderedDict): 2080a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return dict.__eq__(self, other) and all(_imap(_eq, self, other)) 2090a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return dict.__eq__(self, other) 2100a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 2110a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def __ne__(self, other): 2120a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 'od.__ne__(y) <==> od!=y' 2130a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return not self == other 2140a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 2150a8c90248264a8b26970b4473770bcc3df8515fJosh Gao # -- the following methods support python 3.x style dictionary views -- 2160a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 2170a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def viewkeys(self): 2180a8c90248264a8b26970b4473770bcc3df8515fJosh Gao "od.viewkeys() -> a set-like object providing a view on od's keys" 2190a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return KeysView(self) 2200a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 2210a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def viewvalues(self): 2220a8c90248264a8b26970b4473770bcc3df8515fJosh Gao "od.viewvalues() -> an object providing a view on od's values" 2230a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return ValuesView(self) 2240a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 2250a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def viewitems(self): 2260a8c90248264a8b26970b4473770bcc3df8515fJosh Gao "od.viewitems() -> a set-like object providing a view on od's items" 2270a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return ItemsView(self) 2280a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 2290a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 2300a8c90248264a8b26970b4473770bcc3df8515fJosh Gao################################################################################ 2310a8c90248264a8b26970b4473770bcc3df8515fJosh Gao### namedtuple 2320a8c90248264a8b26970b4473770bcc3df8515fJosh Gao################################################################################ 2330a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 2340a8c90248264a8b26970b4473770bcc3df8515fJosh Gao_class_template = '''\ 2350a8c90248264a8b26970b4473770bcc3df8515fJosh Gaoclass {typename}(tuple): 2360a8c90248264a8b26970b4473770bcc3df8515fJosh Gao '{typename}({arg_list})' 2370a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 2380a8c90248264a8b26970b4473770bcc3df8515fJosh Gao __slots__ = () 2390a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 2400a8c90248264a8b26970b4473770bcc3df8515fJosh Gao _fields = {field_names!r} 2410a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 2420a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def __new__(_cls, {arg_list}): 2430a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 'Create new instance of {typename}({arg_list})' 2440a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return _tuple.__new__(_cls, ({arg_list})) 2450a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 2460a8c90248264a8b26970b4473770bcc3df8515fJosh Gao @classmethod 2470a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def _make(cls, iterable, new=tuple.__new__, len=len): 2480a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 'Make a new {typename} object from a sequence or iterable' 2490a8c90248264a8b26970b4473770bcc3df8515fJosh Gao result = new(cls, iterable) 2500a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if len(result) != {num_fields:d}: 2510a8c90248264a8b26970b4473770bcc3df8515fJosh Gao raise TypeError('Expected {num_fields:d} arguments, got %d' % len(result)) 2520a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return result 2530a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 2540a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def __repr__(self): 2550a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 'Return a nicely formatted representation string' 2560a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return '{typename}({repr_fmt})' % self 2570a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 2580a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def _asdict(self): 2590a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 'Return a new OrderedDict which maps field names to their values' 2600a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return OrderedDict(zip(self._fields, self)) 2610a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 2620a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def _replace(_self, **kwds): 2630a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 'Return a new {typename} object replacing specified fields with new values' 2640a8c90248264a8b26970b4473770bcc3df8515fJosh Gao result = _self._make(map(kwds.pop, {field_names!r}, _self)) 2650a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if kwds: 2660a8c90248264a8b26970b4473770bcc3df8515fJosh Gao raise ValueError('Got unexpected field names: %r' % kwds.keys()) 2670a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return result 2680a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 2690a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def __getnewargs__(self): 2700a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 'Return self as a plain tuple. Used by copy and pickle.' 2710a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return tuple(self) 2720a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 2730a8c90248264a8b26970b4473770bcc3df8515fJosh Gao{field_defs} 2740a8c90248264a8b26970b4473770bcc3df8515fJosh Gao''' 2750a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 2760a8c90248264a8b26970b4473770bcc3df8515fJosh Gao_repr_template = '{name}=%r' 2770a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 2780a8c90248264a8b26970b4473770bcc3df8515fJosh Gao_field_template = '''\ 2790a8c90248264a8b26970b4473770bcc3df8515fJosh Gao {name} = _property(_itemgetter({index:d}), doc='Alias for field number {index:d}') 2800a8c90248264a8b26970b4473770bcc3df8515fJosh Gao''' 2810a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 2820a8c90248264a8b26970b4473770bcc3df8515fJosh Gaodef namedtuple(typename, field_names, verbose=False, rename=False): 2830a8c90248264a8b26970b4473770bcc3df8515fJosh Gao """Returns a new subclass of tuple with named fields. 2840a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 2850a8c90248264a8b26970b4473770bcc3df8515fJosh Gao >>> Point = namedtuple('Point', ['x', 'y']) 2860a8c90248264a8b26970b4473770bcc3df8515fJosh Gao >>> Point.__doc__ # docstring for the new class 2870a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 'Point(x, y)' 2880a8c90248264a8b26970b4473770bcc3df8515fJosh Gao >>> p = Point(11, y=22) # instantiate with positional args or keywords 2890a8c90248264a8b26970b4473770bcc3df8515fJosh Gao >>> p[0] + p[1] # indexable like a plain tuple 2900a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 33 2910a8c90248264a8b26970b4473770bcc3df8515fJosh Gao >>> x, y = p # unpack like a regular tuple 2920a8c90248264a8b26970b4473770bcc3df8515fJosh Gao >>> x, y 2930a8c90248264a8b26970b4473770bcc3df8515fJosh Gao (11, 22) 2940a8c90248264a8b26970b4473770bcc3df8515fJosh Gao >>> p.x + p.y # fields also accessable by name 2950a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 33 2960a8c90248264a8b26970b4473770bcc3df8515fJosh Gao >>> d = p._asdict() # convert to a dictionary 2970a8c90248264a8b26970b4473770bcc3df8515fJosh Gao >>> d['x'] 2980a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 11 2990a8c90248264a8b26970b4473770bcc3df8515fJosh Gao >>> Point(**d) # convert from a dictionary 3000a8c90248264a8b26970b4473770bcc3df8515fJosh Gao Point(x=11, y=22) 3010a8c90248264a8b26970b4473770bcc3df8515fJosh Gao >>> p._replace(x=100) # _replace() is like str.replace() but targets named fields 3020a8c90248264a8b26970b4473770bcc3df8515fJosh Gao Point(x=100, y=22) 3030a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 3040a8c90248264a8b26970b4473770bcc3df8515fJosh Gao """ 3050a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 3060a8c90248264a8b26970b4473770bcc3df8515fJosh Gao # Validate the field names. At the user's option, either generate an error 3070a8c90248264a8b26970b4473770bcc3df8515fJosh Gao # message or automatically replace the field name with a valid name. 3080a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if isinstance(field_names, basestring): 3090a8c90248264a8b26970b4473770bcc3df8515fJosh Gao field_names = field_names.replace(',', ' ').split() 3100a8c90248264a8b26970b4473770bcc3df8515fJosh Gao field_names = map(str, field_names) 3110a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if rename: 3120a8c90248264a8b26970b4473770bcc3df8515fJosh Gao seen = set() 3130a8c90248264a8b26970b4473770bcc3df8515fJosh Gao for index, name in enumerate(field_names): 3140a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if (not all(c.isalnum() or c=='_' for c in name) 3150a8c90248264a8b26970b4473770bcc3df8515fJosh Gao or _iskeyword(name) 3160a8c90248264a8b26970b4473770bcc3df8515fJosh Gao or not name 3170a8c90248264a8b26970b4473770bcc3df8515fJosh Gao or name[0].isdigit() 3180a8c90248264a8b26970b4473770bcc3df8515fJosh Gao or name.startswith('_') 3190a8c90248264a8b26970b4473770bcc3df8515fJosh Gao or name in seen): 3200a8c90248264a8b26970b4473770bcc3df8515fJosh Gao field_names[index] = '_%d' % index 3210a8c90248264a8b26970b4473770bcc3df8515fJosh Gao seen.add(name) 3220a8c90248264a8b26970b4473770bcc3df8515fJosh Gao for name in [typename] + field_names: 3230a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if not all(c.isalnum() or c=='_' for c in name): 3240a8c90248264a8b26970b4473770bcc3df8515fJosh Gao raise ValueError('Type names and field names can only contain ' 3250a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 'alphanumeric characters and underscores: %r' % name) 3260a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if _iskeyword(name): 3270a8c90248264a8b26970b4473770bcc3df8515fJosh Gao raise ValueError('Type names and field names cannot be a ' 3280a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 'keyword: %r' % name) 3290a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if name[0].isdigit(): 3300a8c90248264a8b26970b4473770bcc3df8515fJosh Gao raise ValueError('Type names and field names cannot start with ' 3310a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 'a number: %r' % name) 3320a8c90248264a8b26970b4473770bcc3df8515fJosh Gao seen = set() 3330a8c90248264a8b26970b4473770bcc3df8515fJosh Gao for name in field_names: 3340a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if name.startswith('_') and not rename: 3350a8c90248264a8b26970b4473770bcc3df8515fJosh Gao raise ValueError('Field names cannot start with an underscore: ' 3360a8c90248264a8b26970b4473770bcc3df8515fJosh Gao '%r' % name) 3370a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if name in seen: 3380a8c90248264a8b26970b4473770bcc3df8515fJosh Gao raise ValueError('Encountered duplicate field name: %r' % name) 3390a8c90248264a8b26970b4473770bcc3df8515fJosh Gao seen.add(name) 3400a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 3410a8c90248264a8b26970b4473770bcc3df8515fJosh Gao # Fill-in the class template 3420a8c90248264a8b26970b4473770bcc3df8515fJosh Gao class_definition = _class_template.format( 3430a8c90248264a8b26970b4473770bcc3df8515fJosh Gao typename = typename, 3440a8c90248264a8b26970b4473770bcc3df8515fJosh Gao field_names = tuple(field_names), 3450a8c90248264a8b26970b4473770bcc3df8515fJosh Gao num_fields = len(field_names), 3460a8c90248264a8b26970b4473770bcc3df8515fJosh Gao arg_list = repr(tuple(field_names)).replace("'", "")[1:-1], 3470a8c90248264a8b26970b4473770bcc3df8515fJosh Gao repr_fmt = ', '.join(_repr_template.format(name=name) 3480a8c90248264a8b26970b4473770bcc3df8515fJosh Gao for name in field_names), 3490a8c90248264a8b26970b4473770bcc3df8515fJosh Gao field_defs = '\n'.join(_field_template.format(index=index, name=name) 3500a8c90248264a8b26970b4473770bcc3df8515fJosh Gao for index, name in enumerate(field_names)) 3510a8c90248264a8b26970b4473770bcc3df8515fJosh Gao ) 3520a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if verbose: 3530a8c90248264a8b26970b4473770bcc3df8515fJosh Gao print class_definition 3540a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 3550a8c90248264a8b26970b4473770bcc3df8515fJosh Gao # Execute the template string in a temporary namespace and support 3560a8c90248264a8b26970b4473770bcc3df8515fJosh Gao # tracing utilities by setting a value for frame.f_globals['__name__'] 3570a8c90248264a8b26970b4473770bcc3df8515fJosh Gao namespace = dict(_itemgetter=_itemgetter, __name__='namedtuple_%s' % typename, 3580a8c90248264a8b26970b4473770bcc3df8515fJosh Gao OrderedDict=OrderedDict, _property=property, _tuple=tuple) 3590a8c90248264a8b26970b4473770bcc3df8515fJosh Gao try: 3600a8c90248264a8b26970b4473770bcc3df8515fJosh Gao exec class_definition in namespace 3610a8c90248264a8b26970b4473770bcc3df8515fJosh Gao except SyntaxError as e: 3620a8c90248264a8b26970b4473770bcc3df8515fJosh Gao raise SyntaxError(e.message + ':\n' + class_definition) 3630a8c90248264a8b26970b4473770bcc3df8515fJosh Gao result = namespace[typename] 3640a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 3650a8c90248264a8b26970b4473770bcc3df8515fJosh Gao # For pickling to work, the __module__ variable needs to be set to the frame 3660a8c90248264a8b26970b4473770bcc3df8515fJosh Gao # where the named tuple is created. Bypass this step in enviroments where 3670a8c90248264a8b26970b4473770bcc3df8515fJosh Gao # sys._getframe is not defined (Jython for example) or sys._getframe is not 3680a8c90248264a8b26970b4473770bcc3df8515fJosh Gao # defined for arguments greater than 0 (IronPython). 3690a8c90248264a8b26970b4473770bcc3df8515fJosh Gao try: 3700a8c90248264a8b26970b4473770bcc3df8515fJosh Gao result.__module__ = _sys._getframe(1).f_globals.get('__name__', '__main__') 3710a8c90248264a8b26970b4473770bcc3df8515fJosh Gao except (AttributeError, ValueError): 3720a8c90248264a8b26970b4473770bcc3df8515fJosh Gao pass 3730a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 3740a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return result 3750a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 3760a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 3770a8c90248264a8b26970b4473770bcc3df8515fJosh Gao######################################################################## 3780a8c90248264a8b26970b4473770bcc3df8515fJosh Gao### Counter 3790a8c90248264a8b26970b4473770bcc3df8515fJosh Gao######################################################################## 3800a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 3810a8c90248264a8b26970b4473770bcc3df8515fJosh Gaoclass Counter(dict): 3820a8c90248264a8b26970b4473770bcc3df8515fJosh Gao '''Dict subclass for counting hashable items. Sometimes called a bag 3830a8c90248264a8b26970b4473770bcc3df8515fJosh Gao or multiset. Elements are stored as dictionary keys and their counts 3840a8c90248264a8b26970b4473770bcc3df8515fJosh Gao are stored as dictionary values. 3850a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 3860a8c90248264a8b26970b4473770bcc3df8515fJosh Gao >>> c = Counter('abcdeabcdabcaba') # count elements from a string 3870a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 3880a8c90248264a8b26970b4473770bcc3df8515fJosh Gao >>> c.most_common(3) # three most common elements 3890a8c90248264a8b26970b4473770bcc3df8515fJosh Gao [('a', 5), ('b', 4), ('c', 3)] 3900a8c90248264a8b26970b4473770bcc3df8515fJosh Gao >>> sorted(c) # list all unique elements 3910a8c90248264a8b26970b4473770bcc3df8515fJosh Gao ['a', 'b', 'c', 'd', 'e'] 3920a8c90248264a8b26970b4473770bcc3df8515fJosh Gao >>> ''.join(sorted(c.elements())) # list elements with repetitions 3930a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 'aaaaabbbbcccdde' 3940a8c90248264a8b26970b4473770bcc3df8515fJosh Gao >>> sum(c.values()) # total of all counts 3950a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 15 3960a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 3970a8c90248264a8b26970b4473770bcc3df8515fJosh Gao >>> c['a'] # count of letter 'a' 3980a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 5 3990a8c90248264a8b26970b4473770bcc3df8515fJosh Gao >>> for elem in 'shazam': # update counts from an iterable 4000a8c90248264a8b26970b4473770bcc3df8515fJosh Gao ... c[elem] += 1 # by adding 1 to each element's count 4010a8c90248264a8b26970b4473770bcc3df8515fJosh Gao >>> c['a'] # now there are seven 'a' 4020a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 7 4030a8c90248264a8b26970b4473770bcc3df8515fJosh Gao >>> del c['b'] # remove all 'b' 4040a8c90248264a8b26970b4473770bcc3df8515fJosh Gao >>> c['b'] # now there are zero 'b' 4050a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 0 4060a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 4070a8c90248264a8b26970b4473770bcc3df8515fJosh Gao >>> d = Counter('simsalabim') # make another counter 4080a8c90248264a8b26970b4473770bcc3df8515fJosh Gao >>> c.update(d) # add in the second counter 4090a8c90248264a8b26970b4473770bcc3df8515fJosh Gao >>> c['a'] # now there are nine 'a' 4100a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 9 4110a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 4120a8c90248264a8b26970b4473770bcc3df8515fJosh Gao >>> c.clear() # empty the counter 4130a8c90248264a8b26970b4473770bcc3df8515fJosh Gao >>> c 4140a8c90248264a8b26970b4473770bcc3df8515fJosh Gao Counter() 4150a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 4160a8c90248264a8b26970b4473770bcc3df8515fJosh Gao Note: If a count is set to zero or reduced to zero, it will remain 4170a8c90248264a8b26970b4473770bcc3df8515fJosh Gao in the counter until the entry is deleted or the counter is cleared: 4180a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 4190a8c90248264a8b26970b4473770bcc3df8515fJosh Gao >>> c = Counter('aaabbc') 4200a8c90248264a8b26970b4473770bcc3df8515fJosh Gao >>> c['b'] -= 2 # reduce the count of 'b' by two 4210a8c90248264a8b26970b4473770bcc3df8515fJosh Gao >>> c.most_common() # 'b' is still in, but its count is zero 4220a8c90248264a8b26970b4473770bcc3df8515fJosh Gao [('a', 3), ('c', 1), ('b', 0)] 4230a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 4240a8c90248264a8b26970b4473770bcc3df8515fJosh Gao ''' 4250a8c90248264a8b26970b4473770bcc3df8515fJosh Gao # References: 4260a8c90248264a8b26970b4473770bcc3df8515fJosh Gao # http://en.wikipedia.org/wiki/Multiset 4270a8c90248264a8b26970b4473770bcc3df8515fJosh Gao # http://www.gnu.org/software/smalltalk/manual-base/html_node/Bag.html 4280a8c90248264a8b26970b4473770bcc3df8515fJosh Gao # http://www.demo2s.com/Tutorial/Cpp/0380__set-multiset/Catalog0380__set-multiset.htm 4290a8c90248264a8b26970b4473770bcc3df8515fJosh Gao # http://code.activestate.com/recipes/259174/ 4300a8c90248264a8b26970b4473770bcc3df8515fJosh Gao # Knuth, TAOCP Vol. II section 4.6.3 4310a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 4320a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def __init__(self, iterable=None, **kwds): 4330a8c90248264a8b26970b4473770bcc3df8515fJosh Gao '''Create a new, empty Counter object. And if given, count elements 4340a8c90248264a8b26970b4473770bcc3df8515fJosh Gao from an input iterable. Or, initialize the count from another mapping 4350a8c90248264a8b26970b4473770bcc3df8515fJosh Gao of elements to their counts. 4360a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 4370a8c90248264a8b26970b4473770bcc3df8515fJosh Gao >>> c = Counter() # a new, empty counter 4380a8c90248264a8b26970b4473770bcc3df8515fJosh Gao >>> c = Counter('gallahad') # a new counter from an iterable 4390a8c90248264a8b26970b4473770bcc3df8515fJosh Gao >>> c = Counter({'a': 4, 'b': 2}) # a new counter from a mapping 4400a8c90248264a8b26970b4473770bcc3df8515fJosh Gao >>> c = Counter(a=4, b=2) # a new counter from keyword args 4410a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 4420a8c90248264a8b26970b4473770bcc3df8515fJosh Gao ''' 4430a8c90248264a8b26970b4473770bcc3df8515fJosh Gao super(Counter, self).__init__() 4440a8c90248264a8b26970b4473770bcc3df8515fJosh Gao self.update(iterable, **kwds) 4450a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 4460a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def __missing__(self, key): 4470a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 'The count of elements not in the Counter is zero.' 4480a8c90248264a8b26970b4473770bcc3df8515fJosh Gao # Needed so that self[missing_item] does not raise KeyError 4490a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return 0 4500a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 4510a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def most_common(self, n=None): 4520a8c90248264a8b26970b4473770bcc3df8515fJosh Gao '''List the n most common elements and their counts from the most 4530a8c90248264a8b26970b4473770bcc3df8515fJosh Gao common to the least. If n is None, then list all element counts. 4540a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 4550a8c90248264a8b26970b4473770bcc3df8515fJosh Gao >>> Counter('abcdeabcdabcaba').most_common(3) 4560a8c90248264a8b26970b4473770bcc3df8515fJosh Gao [('a', 5), ('b', 4), ('c', 3)] 4570a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 4580a8c90248264a8b26970b4473770bcc3df8515fJosh Gao ''' 4590a8c90248264a8b26970b4473770bcc3df8515fJosh Gao # Emulate Bag.sortedByCount from Smalltalk 4600a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if n is None: 4610a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return sorted(self.iteritems(), key=_itemgetter(1), reverse=True) 4620a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return _heapq.nlargest(n, self.iteritems(), key=_itemgetter(1)) 4630a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 4640a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def elements(self): 4650a8c90248264a8b26970b4473770bcc3df8515fJosh Gao '''Iterator over elements repeating each as many times as its count. 4660a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 4670a8c90248264a8b26970b4473770bcc3df8515fJosh Gao >>> c = Counter('ABCABC') 4680a8c90248264a8b26970b4473770bcc3df8515fJosh Gao >>> sorted(c.elements()) 4690a8c90248264a8b26970b4473770bcc3df8515fJosh Gao ['A', 'A', 'B', 'B', 'C', 'C'] 4700a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 4710a8c90248264a8b26970b4473770bcc3df8515fJosh Gao # Knuth's example for prime factors of 1836: 2**2 * 3**3 * 17**1 4720a8c90248264a8b26970b4473770bcc3df8515fJosh Gao >>> prime_factors = Counter({2: 2, 3: 3, 17: 1}) 4730a8c90248264a8b26970b4473770bcc3df8515fJosh Gao >>> product = 1 4740a8c90248264a8b26970b4473770bcc3df8515fJosh Gao >>> for factor in prime_factors.elements(): # loop over factors 4750a8c90248264a8b26970b4473770bcc3df8515fJosh Gao ... product *= factor # and multiply them 4760a8c90248264a8b26970b4473770bcc3df8515fJosh Gao >>> product 4770a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 1836 4780a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 4790a8c90248264a8b26970b4473770bcc3df8515fJosh Gao Note, if an element's count has been set to zero or is a negative 4800a8c90248264a8b26970b4473770bcc3df8515fJosh Gao number, elements() will ignore it. 4810a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 4820a8c90248264a8b26970b4473770bcc3df8515fJosh Gao ''' 4830a8c90248264a8b26970b4473770bcc3df8515fJosh Gao # Emulate Bag.do from Smalltalk and Multiset.begin from C++. 4840a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return _chain.from_iterable(_starmap(_repeat, self.iteritems())) 4850a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 4860a8c90248264a8b26970b4473770bcc3df8515fJosh Gao # Override dict methods where necessary 4870a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 4880a8c90248264a8b26970b4473770bcc3df8515fJosh Gao @classmethod 4890a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def fromkeys(cls, iterable, v=None): 4900a8c90248264a8b26970b4473770bcc3df8515fJosh Gao # There is no equivalent method for counters because setting v=1 4910a8c90248264a8b26970b4473770bcc3df8515fJosh Gao # means that no element can have a count greater than one. 4920a8c90248264a8b26970b4473770bcc3df8515fJosh Gao raise NotImplementedError( 4930a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 'Counter.fromkeys() is undefined. Use Counter(iterable) instead.') 4940a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 4950a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def update(self, iterable=None, **kwds): 4960a8c90248264a8b26970b4473770bcc3df8515fJosh Gao '''Like dict.update() but add counts instead of replacing them. 4970a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 4980a8c90248264a8b26970b4473770bcc3df8515fJosh Gao Source can be an iterable, a dictionary, or another Counter instance. 4990a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 5000a8c90248264a8b26970b4473770bcc3df8515fJosh Gao >>> c = Counter('which') 5010a8c90248264a8b26970b4473770bcc3df8515fJosh Gao >>> c.update('witch') # add elements from another iterable 5020a8c90248264a8b26970b4473770bcc3df8515fJosh Gao >>> d = Counter('watch') 5030a8c90248264a8b26970b4473770bcc3df8515fJosh Gao >>> c.update(d) # add elements from another counter 5040a8c90248264a8b26970b4473770bcc3df8515fJosh Gao >>> c['h'] # four 'h' in which, witch, and watch 5050a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 4 5060a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 5070a8c90248264a8b26970b4473770bcc3df8515fJosh Gao ''' 5080a8c90248264a8b26970b4473770bcc3df8515fJosh Gao # The regular dict.update() operation makes no sense here because the 5090a8c90248264a8b26970b4473770bcc3df8515fJosh Gao # replace behavior results in the some of original untouched counts 5100a8c90248264a8b26970b4473770bcc3df8515fJosh Gao # being mixed-in with all of the other counts for a mismash that 5110a8c90248264a8b26970b4473770bcc3df8515fJosh Gao # doesn't have a straight-forward interpretation in most counting 5120a8c90248264a8b26970b4473770bcc3df8515fJosh Gao # contexts. Instead, we implement straight-addition. Both the inputs 5130a8c90248264a8b26970b4473770bcc3df8515fJosh Gao # and outputs are allowed to contain zero and negative counts. 5140a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 5150a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if iterable is not None: 5160a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if isinstance(iterable, Mapping): 5170a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if self: 5180a8c90248264a8b26970b4473770bcc3df8515fJosh Gao self_get = self.get 5190a8c90248264a8b26970b4473770bcc3df8515fJosh Gao for elem, count in iterable.iteritems(): 5200a8c90248264a8b26970b4473770bcc3df8515fJosh Gao self[elem] = self_get(elem, 0) + count 5210a8c90248264a8b26970b4473770bcc3df8515fJosh Gao else: 5220a8c90248264a8b26970b4473770bcc3df8515fJosh Gao super(Counter, self).update(iterable) # fast path when counter is empty 5230a8c90248264a8b26970b4473770bcc3df8515fJosh Gao else: 5240a8c90248264a8b26970b4473770bcc3df8515fJosh Gao self_get = self.get 5250a8c90248264a8b26970b4473770bcc3df8515fJosh Gao for elem in iterable: 5260a8c90248264a8b26970b4473770bcc3df8515fJosh Gao self[elem] = self_get(elem, 0) + 1 5270a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if kwds: 5280a8c90248264a8b26970b4473770bcc3df8515fJosh Gao self.update(kwds) 5290a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 5300a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def subtract(self, iterable=None, **kwds): 5310a8c90248264a8b26970b4473770bcc3df8515fJosh Gao '''Like dict.update() but subtracts counts instead of replacing them. 5320a8c90248264a8b26970b4473770bcc3df8515fJosh Gao Counts can be reduced below zero. Both the inputs and outputs are 5330a8c90248264a8b26970b4473770bcc3df8515fJosh Gao allowed to contain zero and negative counts. 5340a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 5350a8c90248264a8b26970b4473770bcc3df8515fJosh Gao Source can be an iterable, a dictionary, or another Counter instance. 5360a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 5370a8c90248264a8b26970b4473770bcc3df8515fJosh Gao >>> c = Counter('which') 5380a8c90248264a8b26970b4473770bcc3df8515fJosh Gao >>> c.subtract('witch') # subtract elements from another iterable 5390a8c90248264a8b26970b4473770bcc3df8515fJosh Gao >>> c.subtract(Counter('watch')) # subtract elements from another counter 5400a8c90248264a8b26970b4473770bcc3df8515fJosh Gao >>> c['h'] # 2 in which, minus 1 in witch, minus 1 in watch 5410a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 0 5420a8c90248264a8b26970b4473770bcc3df8515fJosh Gao >>> c['w'] # 1 in which, minus 1 in witch, minus 1 in watch 5430a8c90248264a8b26970b4473770bcc3df8515fJosh Gao -1 5440a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 5450a8c90248264a8b26970b4473770bcc3df8515fJosh Gao ''' 5460a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if iterable is not None: 5470a8c90248264a8b26970b4473770bcc3df8515fJosh Gao self_get = self.get 5480a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if isinstance(iterable, Mapping): 5490a8c90248264a8b26970b4473770bcc3df8515fJosh Gao for elem, count in iterable.items(): 5500a8c90248264a8b26970b4473770bcc3df8515fJosh Gao self[elem] = self_get(elem, 0) - count 5510a8c90248264a8b26970b4473770bcc3df8515fJosh Gao else: 5520a8c90248264a8b26970b4473770bcc3df8515fJosh Gao for elem in iterable: 5530a8c90248264a8b26970b4473770bcc3df8515fJosh Gao self[elem] = self_get(elem, 0) - 1 5540a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if kwds: 5550a8c90248264a8b26970b4473770bcc3df8515fJosh Gao self.subtract(kwds) 5560a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 5570a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def copy(self): 5580a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 'Return a shallow copy.' 5590a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return self.__class__(self) 5600a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 5610a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def __reduce__(self): 5620a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return self.__class__, (dict(self),) 5630a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 5640a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def __delitem__(self, elem): 5650a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 'Like dict.__delitem__() but does not raise KeyError for missing values.' 5660a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if elem in self: 5670a8c90248264a8b26970b4473770bcc3df8515fJosh Gao super(Counter, self).__delitem__(elem) 5680a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 5690a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def __repr__(self): 5700a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if not self: 5710a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return '%s()' % self.__class__.__name__ 5720a8c90248264a8b26970b4473770bcc3df8515fJosh Gao items = ', '.join(map('%r: %r'.__mod__, self.most_common())) 5730a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return '%s({%s})' % (self.__class__.__name__, items) 5740a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 5750a8c90248264a8b26970b4473770bcc3df8515fJosh Gao # Multiset-style mathematical operations discussed in: 5760a8c90248264a8b26970b4473770bcc3df8515fJosh Gao # Knuth TAOCP Volume II section 4.6.3 exercise 19 5770a8c90248264a8b26970b4473770bcc3df8515fJosh Gao # and at http://en.wikipedia.org/wiki/Multiset 5780a8c90248264a8b26970b4473770bcc3df8515fJosh Gao # 5790a8c90248264a8b26970b4473770bcc3df8515fJosh Gao # Outputs guaranteed to only include positive counts. 5800a8c90248264a8b26970b4473770bcc3df8515fJosh Gao # 5810a8c90248264a8b26970b4473770bcc3df8515fJosh Gao # To strip negative and zero counts, add-in an empty counter: 5820a8c90248264a8b26970b4473770bcc3df8515fJosh Gao # c += Counter() 5830a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 5840a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def __add__(self, other): 5850a8c90248264a8b26970b4473770bcc3df8515fJosh Gao '''Add counts from two counters. 5860a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 5870a8c90248264a8b26970b4473770bcc3df8515fJosh Gao >>> Counter('abbb') + Counter('bcc') 5880a8c90248264a8b26970b4473770bcc3df8515fJosh Gao Counter({'b': 4, 'c': 2, 'a': 1}) 5890a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 5900a8c90248264a8b26970b4473770bcc3df8515fJosh Gao ''' 5910a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if not isinstance(other, Counter): 5920a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return NotImplemented 5930a8c90248264a8b26970b4473770bcc3df8515fJosh Gao result = Counter() 5940a8c90248264a8b26970b4473770bcc3df8515fJosh Gao for elem, count in self.items(): 5950a8c90248264a8b26970b4473770bcc3df8515fJosh Gao newcount = count + other[elem] 5960a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if newcount > 0: 5970a8c90248264a8b26970b4473770bcc3df8515fJosh Gao result[elem] = newcount 5980a8c90248264a8b26970b4473770bcc3df8515fJosh Gao for elem, count in other.items(): 5990a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if elem not in self and count > 0: 6000a8c90248264a8b26970b4473770bcc3df8515fJosh Gao result[elem] = count 6010a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return result 6020a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 6030a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def __sub__(self, other): 6040a8c90248264a8b26970b4473770bcc3df8515fJosh Gao ''' Subtract count, but keep only results with positive counts. 6050a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 6060a8c90248264a8b26970b4473770bcc3df8515fJosh Gao >>> Counter('abbbc') - Counter('bccd') 6070a8c90248264a8b26970b4473770bcc3df8515fJosh Gao Counter({'b': 2, 'a': 1}) 6080a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 6090a8c90248264a8b26970b4473770bcc3df8515fJosh Gao ''' 6100a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if not isinstance(other, Counter): 6110a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return NotImplemented 6120a8c90248264a8b26970b4473770bcc3df8515fJosh Gao result = Counter() 6130a8c90248264a8b26970b4473770bcc3df8515fJosh Gao for elem, count in self.items(): 6140a8c90248264a8b26970b4473770bcc3df8515fJosh Gao newcount = count - other[elem] 6150a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if newcount > 0: 6160a8c90248264a8b26970b4473770bcc3df8515fJosh Gao result[elem] = newcount 6170a8c90248264a8b26970b4473770bcc3df8515fJosh Gao for elem, count in other.items(): 6180a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if elem not in self and count < 0: 6190a8c90248264a8b26970b4473770bcc3df8515fJosh Gao result[elem] = 0 - count 6200a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return result 6210a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 6220a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def __or__(self, other): 6230a8c90248264a8b26970b4473770bcc3df8515fJosh Gao '''Union is the maximum of value in either of the input counters. 6240a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 6250a8c90248264a8b26970b4473770bcc3df8515fJosh Gao >>> Counter('abbb') | Counter('bcc') 6260a8c90248264a8b26970b4473770bcc3df8515fJosh Gao Counter({'b': 3, 'c': 2, 'a': 1}) 6270a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 6280a8c90248264a8b26970b4473770bcc3df8515fJosh Gao ''' 6290a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if not isinstance(other, Counter): 6300a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return NotImplemented 6310a8c90248264a8b26970b4473770bcc3df8515fJosh Gao result = Counter() 6320a8c90248264a8b26970b4473770bcc3df8515fJosh Gao for elem, count in self.items(): 6330a8c90248264a8b26970b4473770bcc3df8515fJosh Gao other_count = other[elem] 6340a8c90248264a8b26970b4473770bcc3df8515fJosh Gao newcount = other_count if count < other_count else count 6350a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if newcount > 0: 6360a8c90248264a8b26970b4473770bcc3df8515fJosh Gao result[elem] = newcount 6370a8c90248264a8b26970b4473770bcc3df8515fJosh Gao for elem, count in other.items(): 6380a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if elem not in self and count > 0: 6390a8c90248264a8b26970b4473770bcc3df8515fJosh Gao result[elem] = count 6400a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return result 6410a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 6420a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def __and__(self, other): 6430a8c90248264a8b26970b4473770bcc3df8515fJosh Gao ''' Intersection is the minimum of corresponding counts. 6440a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 6450a8c90248264a8b26970b4473770bcc3df8515fJosh Gao >>> Counter('abbb') & Counter('bcc') 6460a8c90248264a8b26970b4473770bcc3df8515fJosh Gao Counter({'b': 1}) 6470a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 6480a8c90248264a8b26970b4473770bcc3df8515fJosh Gao ''' 6490a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if not isinstance(other, Counter): 6500a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return NotImplemented 6510a8c90248264a8b26970b4473770bcc3df8515fJosh Gao result = Counter() 6520a8c90248264a8b26970b4473770bcc3df8515fJosh Gao for elem, count in self.items(): 6530a8c90248264a8b26970b4473770bcc3df8515fJosh Gao other_count = other[elem] 6540a8c90248264a8b26970b4473770bcc3df8515fJosh Gao newcount = count if count < other_count else other_count 6550a8c90248264a8b26970b4473770bcc3df8515fJosh Gao if newcount > 0: 6560a8c90248264a8b26970b4473770bcc3df8515fJosh Gao result[elem] = newcount 6570a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return result 6580a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 6590a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 6600a8c90248264a8b26970b4473770bcc3df8515fJosh Gaoif __name__ == '__main__': 6610a8c90248264a8b26970b4473770bcc3df8515fJosh Gao # verify that instances can be pickled 6620a8c90248264a8b26970b4473770bcc3df8515fJosh Gao from cPickle import loads, dumps 6630a8c90248264a8b26970b4473770bcc3df8515fJosh Gao Point = namedtuple('Point', 'x, y', True) 6640a8c90248264a8b26970b4473770bcc3df8515fJosh Gao p = Point(x=10, y=20) 6650a8c90248264a8b26970b4473770bcc3df8515fJosh Gao assert p == loads(dumps(p)) 6660a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 6670a8c90248264a8b26970b4473770bcc3df8515fJosh Gao # test and demonstrate ability to override methods 6680a8c90248264a8b26970b4473770bcc3df8515fJosh Gao class Point(namedtuple('Point', 'x y')): 6690a8c90248264a8b26970b4473770bcc3df8515fJosh Gao __slots__ = () 6700a8c90248264a8b26970b4473770bcc3df8515fJosh Gao @property 6710a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def hypot(self): 6720a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return (self.x ** 2 + self.y ** 2) ** 0.5 6730a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def __str__(self): 6740a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return 'Point: x=%6.3f y=%6.3f hypot=%6.3f' % (self.x, self.y, self.hypot) 6750a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 6760a8c90248264a8b26970b4473770bcc3df8515fJosh Gao for p in Point(3, 4), Point(14, 5/7.): 6770a8c90248264a8b26970b4473770bcc3df8515fJosh Gao print p 6780a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 6790a8c90248264a8b26970b4473770bcc3df8515fJosh Gao class Point(namedtuple('Point', 'x y')): 6800a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 'Point class with optimized _make() and _replace() without error-checking' 6810a8c90248264a8b26970b4473770bcc3df8515fJosh Gao __slots__ = () 6820a8c90248264a8b26970b4473770bcc3df8515fJosh Gao _make = classmethod(tuple.__new__) 6830a8c90248264a8b26970b4473770bcc3df8515fJosh Gao def _replace(self, _map=map, **kwds): 6840a8c90248264a8b26970b4473770bcc3df8515fJosh Gao return self._make(_map(kwds.get, ('x', 'y'), self)) 6850a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 6860a8c90248264a8b26970b4473770bcc3df8515fJosh Gao print Point(11, 22)._replace(x=100) 6870a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 6880a8c90248264a8b26970b4473770bcc3df8515fJosh Gao Point3D = namedtuple('Point3D', Point._fields + ('z',)) 6890a8c90248264a8b26970b4473770bcc3df8515fJosh Gao print Point3D.__doc__ 6900a8c90248264a8b26970b4473770bcc3df8515fJosh Gao 6910a8c90248264a8b26970b4473770bcc3df8515fJosh Gao import doctest 6920a8c90248264a8b26970b4473770bcc3df8515fJosh Gao TestResults = namedtuple('TestResults', 'failed attempted') 6930a8c90248264a8b26970b4473770bcc3df8515fJosh Gao print TestResults(*doctest.testmod()) 694