14adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao__all__ = ['Counter', 'deque', 'defaultdict', 'namedtuple', 'OrderedDict'] 24adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao# For bootstrapping reasons, the collection ABCs are defined in _abcoll.py. 34adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao# They should however be considered an integral part of collections.py. 44adfde8bc82dd39f59e0445588c3e599ada477dJosh Gaofrom _abcoll import * 54adfde8bc82dd39f59e0445588c3e599ada477dJosh Gaoimport _abcoll 64adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao__all__ += _abcoll.__all__ 74adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 84adfde8bc82dd39f59e0445588c3e599ada477dJosh Gaofrom _collections import deque, defaultdict 94adfde8bc82dd39f59e0445588c3e599ada477dJosh Gaofrom operator import itemgetter as _itemgetter, eq as _eq 104adfde8bc82dd39f59e0445588c3e599ada477dJosh Gaofrom keyword import iskeyword as _iskeyword 114adfde8bc82dd39f59e0445588c3e599ada477dJosh Gaoimport sys as _sys 124adfde8bc82dd39f59e0445588c3e599ada477dJosh Gaoimport heapq as _heapq 134adfde8bc82dd39f59e0445588c3e599ada477dJosh Gaofrom itertools import repeat as _repeat, chain as _chain, starmap as _starmap 144adfde8bc82dd39f59e0445588c3e599ada477dJosh Gaofrom itertools import imap as _imap 154adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 164adfde8bc82dd39f59e0445588c3e599ada477dJosh Gaotry: 174adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao from thread import get_ident as _get_ident 184adfde8bc82dd39f59e0445588c3e599ada477dJosh Gaoexcept ImportError: 194adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao from dummy_thread import get_ident as _get_ident 204adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 214adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 224adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao################################################################################ 234adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao### OrderedDict 244adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao################################################################################ 254adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 264adfde8bc82dd39f59e0445588c3e599ada477dJosh Gaoclass OrderedDict(dict): 274adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 'Dictionary that remembers insertion order' 284adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao # An inherited dict maps keys to values. 294adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao # The inherited dict provides __getitem__, __len__, __contains__, and get. 304adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao # The remaining methods are order-aware. 314adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao # Big-O running times for all methods are the same as regular dictionaries. 324adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 334adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao # The internal self.__map dict maps keys to links in a doubly linked list. 344adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao # The circular doubly linked list starts and ends with a sentinel element. 354adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao # The sentinel element never gets deleted (this simplifies the algorithm). 364adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao # Each link is stored as a list of length three: [PREV, NEXT, KEY]. 374adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 384adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao def __init__(self, *args, **kwds): 394adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao '''Initialize an ordered dictionary. The signature is the same as 404adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao regular dictionaries, but keyword arguments are not recommended because 414adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao their insertion order is arbitrary. 424adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 434adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao ''' 444adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao if len(args) > 1: 454adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao raise TypeError('expected at most 1 arguments, got %d' % len(args)) 464adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao try: 474adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.__root 484adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao except AttributeError: 494adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.__root = root = [] # sentinel node 504adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao root[:] = [root, root, None] 514adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.__map = {} 524adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.__update(*args, **kwds) 534adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 544adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao def __setitem__(self, key, value, dict_setitem=dict.__setitem__): 554adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 'od.__setitem__(i, y) <==> od[i]=y' 564adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao # Setting a new item creates a new link at the end of the linked list, 574adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao # and the inherited dictionary is updated with the new key/value pair. 584adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao if key not in self: 594adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao root = self.__root 604adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao last = root[0] 614adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao last[1] = root[0] = self.__map[key] = [last, root, key] 624adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao return dict_setitem(self, key, value) 634adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 644adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao def __delitem__(self, key, dict_delitem=dict.__delitem__): 654adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 'od.__delitem__(y) <==> del od[y]' 664adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao # Deleting an existing item uses self.__map to find the link which gets 674adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao # removed by updating the links in the predecessor and successor nodes. 684adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao dict_delitem(self, key) 694adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao link_prev, link_next, _ = self.__map.pop(key) 704adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao link_prev[1] = link_next # update link_prev[NEXT] 714adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao link_next[0] = link_prev # update link_next[PREV] 724adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 734adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao def __iter__(self): 744adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 'od.__iter__() <==> iter(od)' 754adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao # Traverse the linked list in order. 764adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao root = self.__root 774adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao curr = root[1] # start at the first node 784adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao while curr is not root: 794adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao yield curr[2] # yield the curr[KEY] 804adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao curr = curr[1] # move to next node 814adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 824adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao def __reversed__(self): 834adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 'od.__reversed__() <==> reversed(od)' 844adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao # Traverse the linked list in reverse order. 854adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao root = self.__root 864adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao curr = root[0] # start at the last node 874adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao while curr is not root: 884adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao yield curr[2] # yield the curr[KEY] 894adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao curr = curr[0] # move to previous node 904adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 914adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao def clear(self): 924adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 'od.clear() -> None. Remove all items from od.' 934adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao root = self.__root 944adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao root[:] = [root, root, None] 954adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.__map.clear() 964adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao dict.clear(self) 974adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 984adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao # -- the following methods do not depend on the internal structure -- 994adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 1004adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao def keys(self): 1014adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 'od.keys() -> list of keys in od' 1024adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao return list(self) 1034adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 1044adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao def values(self): 1054adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 'od.values() -> list of values in od' 1064adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao return [self[key] for key in self] 1074adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 1084adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao def items(self): 1094adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 'od.items() -> list of (key, value) pairs in od' 1104adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao return [(key, self[key]) for key in self] 1114adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 1124adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao def iterkeys(self): 1134adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 'od.iterkeys() -> an iterator over the keys in od' 1144adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao return iter(self) 1154adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 1164adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao def itervalues(self): 1174adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 'od.itervalues -> an iterator over the values in od' 1184adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao for k in self: 1194adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao yield self[k] 1204adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 1214adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao def iteritems(self): 1224adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 'od.iteritems -> an iterator over the (key, value) pairs in od' 1234adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao for k in self: 1244adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao yield (k, self[k]) 1254adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 1264adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao update = MutableMapping.update 1274adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 1284adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao __update = update # let subclasses override update without breaking __init__ 1294adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 1304adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao __marker = object() 1314adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 1324adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao def pop(self, key, default=__marker): 1334adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao '''od.pop(k[,d]) -> v, remove specified key and return the corresponding 1344adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao value. If key is not found, d is returned if given, otherwise KeyError 1354adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao is raised. 1364adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 1374adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao ''' 1384adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao if key in self: 1394adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao result = self[key] 1404adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao del self[key] 1414adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao return result 1424adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao if default is self.__marker: 1434adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao raise KeyError(key) 1444adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao return default 1454adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 1464adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao def setdefault(self, key, default=None): 1474adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 'od.setdefault(k[,d]) -> od.get(k,d), also set od[k]=d if k not in od' 1484adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao if key in self: 1494adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao return self[key] 1504adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self[key] = default 1514adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao return default 1524adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 1534adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao def popitem(self, last=True): 1544adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao '''od.popitem() -> (k, v), return and remove a (key, value) pair. 1554adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao Pairs are returned in LIFO order if last is true or FIFO order if false. 1564adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 1574adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao ''' 1584adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao if not self: 1594adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao raise KeyError('dictionary is empty') 1604adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao key = next(reversed(self) if last else iter(self)) 1614adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao value = self.pop(key) 1624adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao return key, value 1634adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 1644adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao def __repr__(self, _repr_running={}): 1654adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 'od.__repr__() <==> repr(od)' 1664adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao call_key = id(self), _get_ident() 1674adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao if call_key in _repr_running: 1684adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao return '...' 1694adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao _repr_running[call_key] = 1 1704adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao try: 1714adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao if not self: 1724adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao return '%s()' % (self.__class__.__name__,) 1734adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao return '%s(%r)' % (self.__class__.__name__, self.items()) 1744adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao finally: 1754adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao del _repr_running[call_key] 1764adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 1774adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao def __reduce__(self): 1784adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 'Return state information for pickling' 1794adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao items = [[k, self[k]] for k in self] 1804adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao inst_dict = vars(self).copy() 1814adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao for k in vars(OrderedDict()): 1824adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao inst_dict.pop(k, None) 1834adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao if inst_dict: 1844adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao return (self.__class__, (items,), inst_dict) 1854adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao return self.__class__, (items,) 1864adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 1874adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao def copy(self): 1884adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 'od.copy() -> a shallow copy of od' 1894adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao return self.__class__(self) 1904adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 1914adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao @classmethod 1924adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao def fromkeys(cls, iterable, value=None): 1934adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao '''OD.fromkeys(S[, v]) -> New ordered dictionary with keys from S. 1944adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao If not specified, the value defaults to None. 1954adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 1964adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao ''' 1974adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self = cls() 1984adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao for key in iterable: 1994adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self[key] = value 2004adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao return self 2014adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 2024adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao def __eq__(self, other): 2034adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao '''od.__eq__(y) <==> od==y. Comparison to another OD is order-sensitive 2044adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao while comparison to a regular mapping is order-insensitive. 2054adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 2064adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao ''' 2074adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao if isinstance(other, OrderedDict): 2084adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao return dict.__eq__(self, other) and all(_imap(_eq, self, other)) 2094adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao return dict.__eq__(self, other) 2104adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 2114adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao def __ne__(self, other): 2124adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 'od.__ne__(y) <==> od!=y' 2134adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao return not self == other 2144adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 2154adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao # -- the following methods support python 3.x style dictionary views -- 2164adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 2174adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao def viewkeys(self): 2184adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao "od.viewkeys() -> a set-like object providing a view on od's keys" 2194adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao return KeysView(self) 2204adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 2214adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao def viewvalues(self): 2224adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao "od.viewvalues() -> an object providing a view on od's values" 2234adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao return ValuesView(self) 2244adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 2254adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao def viewitems(self): 2264adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao "od.viewitems() -> a set-like object providing a view on od's items" 2274adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao return ItemsView(self) 2284adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 2294adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 2304adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao################################################################################ 2314adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao### namedtuple 2324adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao################################################################################ 2334adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 2344adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao_class_template = '''\ 2354adfde8bc82dd39f59e0445588c3e599ada477dJosh Gaoclass {typename}(tuple): 2364adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao '{typename}({arg_list})' 2374adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 2384adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao __slots__ = () 2394adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 2404adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao _fields = {field_names!r} 2414adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 2424adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao def __new__(_cls, {arg_list}): 2434adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 'Create new instance of {typename}({arg_list})' 2444adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao return _tuple.__new__(_cls, ({arg_list})) 2454adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 2464adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao @classmethod 2474adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao def _make(cls, iterable, new=tuple.__new__, len=len): 2484adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 'Make a new {typename} object from a sequence or iterable' 2494adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao result = new(cls, iterable) 2504adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao if len(result) != {num_fields:d}: 2514adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao raise TypeError('Expected {num_fields:d} arguments, got %d' % len(result)) 2524adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao return result 2534adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 2544adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao def __repr__(self): 2554adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 'Return a nicely formatted representation string' 2564adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao return '{typename}({repr_fmt})' % self 2574adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 2584adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao def _asdict(self): 2594adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 'Return a new OrderedDict which maps field names to their values' 2604adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao return OrderedDict(zip(self._fields, self)) 2614adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 2624adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao def _replace(_self, **kwds): 2634adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 'Return a new {typename} object replacing specified fields with new values' 2644adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao result = _self._make(map(kwds.pop, {field_names!r}, _self)) 2654adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao if kwds: 2664adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao raise ValueError('Got unexpected field names: %r' % kwds.keys()) 2674adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao return result 2684adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 2694adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao def __getnewargs__(self): 2704adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 'Return self as a plain tuple. Used by copy and pickle.' 2714adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao return tuple(self) 2724adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 2734adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao{field_defs} 2744adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao''' 2754adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 2764adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao_repr_template = '{name}=%r' 2774adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 2784adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao_field_template = '''\ 2794adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao {name} = _property(_itemgetter({index:d}), doc='Alias for field number {index:d}') 2804adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao''' 2814adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 2824adfde8bc82dd39f59e0445588c3e599ada477dJosh Gaodef namedtuple(typename, field_names, verbose=False, rename=False): 2834adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao """Returns a new subclass of tuple with named fields. 2844adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 2854adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao >>> Point = namedtuple('Point', ['x', 'y']) 2864adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao >>> Point.__doc__ # docstring for the new class 2874adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 'Point(x, y)' 2884adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao >>> p = Point(11, y=22) # instantiate with positional args or keywords 2894adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao >>> p[0] + p[1] # indexable like a plain tuple 2904adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 33 2914adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao >>> x, y = p # unpack like a regular tuple 2924adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao >>> x, y 2934adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao (11, 22) 2944adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao >>> p.x + p.y # fields also accessable by name 2954adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 33 2964adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao >>> d = p._asdict() # convert to a dictionary 2974adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao >>> d['x'] 2984adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 11 2994adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao >>> Point(**d) # convert from a dictionary 3004adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao Point(x=11, y=22) 3014adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao >>> p._replace(x=100) # _replace() is like str.replace() but targets named fields 3024adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao Point(x=100, y=22) 3034adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 3044adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao """ 3054adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 3064adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao # Validate the field names. At the user's option, either generate an error 3074adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao # message or automatically replace the field name with a valid name. 3084adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao if isinstance(field_names, basestring): 3094adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao field_names = field_names.replace(',', ' ').split() 3104adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao field_names = map(str, field_names) 3114adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao if rename: 3124adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao seen = set() 3134adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao for index, name in enumerate(field_names): 3144adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao if (not all(c.isalnum() or c=='_' for c in name) 3154adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao or _iskeyword(name) 3164adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao or not name 3174adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao or name[0].isdigit() 3184adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao or name.startswith('_') 3194adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao or name in seen): 3204adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao field_names[index] = '_%d' % index 3214adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao seen.add(name) 3224adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao for name in [typename] + field_names: 3234adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao if not all(c.isalnum() or c=='_' for c in name): 3244adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao raise ValueError('Type names and field names can only contain ' 3254adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 'alphanumeric characters and underscores: %r' % name) 3264adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao if _iskeyword(name): 3274adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao raise ValueError('Type names and field names cannot be a ' 3284adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 'keyword: %r' % name) 3294adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao if name[0].isdigit(): 3304adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao raise ValueError('Type names and field names cannot start with ' 3314adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 'a number: %r' % name) 3324adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao seen = set() 3334adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao for name in field_names: 3344adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao if name.startswith('_') and not rename: 3354adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao raise ValueError('Field names cannot start with an underscore: ' 3364adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao '%r' % name) 3374adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao if name in seen: 3384adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao raise ValueError('Encountered duplicate field name: %r' % name) 3394adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao seen.add(name) 3404adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 3414adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao # Fill-in the class template 3424adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao class_definition = _class_template.format( 3434adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao typename = typename, 3444adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao field_names = tuple(field_names), 3454adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao num_fields = len(field_names), 3464adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao arg_list = repr(tuple(field_names)).replace("'", "")[1:-1], 3474adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao repr_fmt = ', '.join(_repr_template.format(name=name) 3484adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao for name in field_names), 3494adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao field_defs = '\n'.join(_field_template.format(index=index, name=name) 3504adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao for index, name in enumerate(field_names)) 3514adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao ) 3524adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao if verbose: 3534adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao print class_definition 3544adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 3554adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao # Execute the template string in a temporary namespace and support 3564adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao # tracing utilities by setting a value for frame.f_globals['__name__'] 3574adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao namespace = dict(_itemgetter=_itemgetter, __name__='namedtuple_%s' % typename, 3584adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao OrderedDict=OrderedDict, _property=property, _tuple=tuple) 3594adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao try: 3604adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao exec class_definition in namespace 3614adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao except SyntaxError as e: 3624adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao raise SyntaxError(e.message + ':\n' + class_definition) 3634adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao result = namespace[typename] 3644adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 3654adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao # For pickling to work, the __module__ variable needs to be set to the frame 3664adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao # where the named tuple is created. Bypass this step in enviroments where 3674adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao # sys._getframe is not defined (Jython for example) or sys._getframe is not 3684adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao # defined for arguments greater than 0 (IronPython). 3694adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao try: 3704adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao result.__module__ = _sys._getframe(1).f_globals.get('__name__', '__main__') 3714adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao except (AttributeError, ValueError): 3724adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao pass 3734adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 3744adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao return result 3754adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 3764adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 3774adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao######################################################################## 3784adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao### Counter 3794adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao######################################################################## 3804adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 3814adfde8bc82dd39f59e0445588c3e599ada477dJosh Gaoclass Counter(dict): 3824adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao '''Dict subclass for counting hashable items. Sometimes called a bag 3834adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao or multiset. Elements are stored as dictionary keys and their counts 3844adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao are stored as dictionary values. 3854adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 3864adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao >>> c = Counter('abcdeabcdabcaba') # count elements from a string 3874adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 3884adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao >>> c.most_common(3) # three most common elements 3894adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao [('a', 5), ('b', 4), ('c', 3)] 3904adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao >>> sorted(c) # list all unique elements 3914adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao ['a', 'b', 'c', 'd', 'e'] 3924adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao >>> ''.join(sorted(c.elements())) # list elements with repetitions 3934adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 'aaaaabbbbcccdde' 3944adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao >>> sum(c.values()) # total of all counts 3954adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 15 3964adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 3974adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao >>> c['a'] # count of letter 'a' 3984adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 5 3994adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao >>> for elem in 'shazam': # update counts from an iterable 4004adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao ... c[elem] += 1 # by adding 1 to each element's count 4014adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao >>> c['a'] # now there are seven 'a' 4024adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 7 4034adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao >>> del c['b'] # remove all 'b' 4044adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao >>> c['b'] # now there are zero 'b' 4054adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 0 4064adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 4074adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao >>> d = Counter('simsalabim') # make another counter 4084adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao >>> c.update(d) # add in the second counter 4094adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao >>> c['a'] # now there are nine 'a' 4104adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 9 4114adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 4124adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao >>> c.clear() # empty the counter 4134adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao >>> c 4144adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao Counter() 4154adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 4164adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao Note: If a count is set to zero or reduced to zero, it will remain 4174adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao in the counter until the entry is deleted or the counter is cleared: 4184adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 4194adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao >>> c = Counter('aaabbc') 4204adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao >>> c['b'] -= 2 # reduce the count of 'b' by two 4214adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao >>> c.most_common() # 'b' is still in, but its count is zero 4224adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao [('a', 3), ('c', 1), ('b', 0)] 4234adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 4244adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao ''' 4254adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao # References: 4264adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao # http://en.wikipedia.org/wiki/Multiset 4274adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao # http://www.gnu.org/software/smalltalk/manual-base/html_node/Bag.html 4284adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao # http://www.demo2s.com/Tutorial/Cpp/0380__set-multiset/Catalog0380__set-multiset.htm 4294adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao # http://code.activestate.com/recipes/259174/ 4304adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao # Knuth, TAOCP Vol. II section 4.6.3 4314adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 4324adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao def __init__(self, iterable=None, **kwds): 4334adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao '''Create a new, empty Counter object. And if given, count elements 4344adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao from an input iterable. Or, initialize the count from another mapping 4354adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao of elements to their counts. 4364adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 4374adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao >>> c = Counter() # a new, empty counter 4384adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao >>> c = Counter('gallahad') # a new counter from an iterable 4394adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao >>> c = Counter({'a': 4, 'b': 2}) # a new counter from a mapping 4404adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao >>> c = Counter(a=4, b=2) # a new counter from keyword args 4414adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 4424adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao ''' 4434adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao super(Counter, self).__init__() 4444adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.update(iterable, **kwds) 4454adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 4464adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao def __missing__(self, key): 4474adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 'The count of elements not in the Counter is zero.' 4484adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao # Needed so that self[missing_item] does not raise KeyError 4494adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao return 0 4504adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 4514adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao def most_common(self, n=None): 4524adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao '''List the n most common elements and their counts from the most 4534adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao common to the least. If n is None, then list all element counts. 4544adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 4554adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao >>> Counter('abcdeabcdabcaba').most_common(3) 4564adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao [('a', 5), ('b', 4), ('c', 3)] 4574adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 4584adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao ''' 4594adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao # Emulate Bag.sortedByCount from Smalltalk 4604adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao if n is None: 4614adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao return sorted(self.iteritems(), key=_itemgetter(1), reverse=True) 4624adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao return _heapq.nlargest(n, self.iteritems(), key=_itemgetter(1)) 4634adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 4644adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao def elements(self): 4654adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao '''Iterator over elements repeating each as many times as its count. 4664adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 4674adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao >>> c = Counter('ABCABC') 4684adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao >>> sorted(c.elements()) 4694adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao ['A', 'A', 'B', 'B', 'C', 'C'] 4704adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 4714adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao # Knuth's example for prime factors of 1836: 2**2 * 3**3 * 17**1 4724adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao >>> prime_factors = Counter({2: 2, 3: 3, 17: 1}) 4734adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao >>> product = 1 4744adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao >>> for factor in prime_factors.elements(): # loop over factors 4754adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao ... product *= factor # and multiply them 4764adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao >>> product 4774adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 1836 4784adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 4794adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao Note, if an element's count has been set to zero or is a negative 4804adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao number, elements() will ignore it. 4814adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 4824adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao ''' 4834adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao # Emulate Bag.do from Smalltalk and Multiset.begin from C++. 4844adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao return _chain.from_iterable(_starmap(_repeat, self.iteritems())) 4854adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 4864adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao # Override dict methods where necessary 4874adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 4884adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao @classmethod 4894adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao def fromkeys(cls, iterable, v=None): 4904adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao # There is no equivalent method for counters because setting v=1 4914adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao # means that no element can have a count greater than one. 4924adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao raise NotImplementedError( 4934adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 'Counter.fromkeys() is undefined. Use Counter(iterable) instead.') 4944adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 4954adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao def update(self, iterable=None, **kwds): 4964adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao '''Like dict.update() but add counts instead of replacing them. 4974adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 4984adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao Source can be an iterable, a dictionary, or another Counter instance. 4994adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 5004adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao >>> c = Counter('which') 5014adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao >>> c.update('witch') # add elements from another iterable 5024adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao >>> d = Counter('watch') 5034adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao >>> c.update(d) # add elements from another counter 5044adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao >>> c['h'] # four 'h' in which, witch, and watch 5054adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 4 5064adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 5074adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao ''' 5084adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao # The regular dict.update() operation makes no sense here because the 5094adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao # replace behavior results in the some of original untouched counts 5104adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao # being mixed-in with all of the other counts for a mismash that 5114adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao # doesn't have a straight-forward interpretation in most counting 5124adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao # contexts. Instead, we implement straight-addition. Both the inputs 5134adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao # and outputs are allowed to contain zero and negative counts. 5144adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 5154adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao if iterable is not None: 5164adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao if isinstance(iterable, Mapping): 5174adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao if self: 5184adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self_get = self.get 5194adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao for elem, count in iterable.iteritems(): 5204adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self[elem] = self_get(elem, 0) + count 5214adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao else: 5224adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao super(Counter, self).update(iterable) # fast path when counter is empty 5234adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao else: 5244adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self_get = self.get 5254adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao for elem in iterable: 5264adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self[elem] = self_get(elem, 0) + 1 5274adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao if kwds: 5284adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.update(kwds) 5294adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 5304adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao def subtract(self, iterable=None, **kwds): 5314adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao '''Like dict.update() but subtracts counts instead of replacing them. 5324adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao Counts can be reduced below zero. Both the inputs and outputs are 5334adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao allowed to contain zero and negative counts. 5344adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 5354adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao Source can be an iterable, a dictionary, or another Counter instance. 5364adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 5374adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao >>> c = Counter('which') 5384adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao >>> c.subtract('witch') # subtract elements from another iterable 5394adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao >>> c.subtract(Counter('watch')) # subtract elements from another counter 5404adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao >>> c['h'] # 2 in which, minus 1 in witch, minus 1 in watch 5414adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 0 5424adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao >>> c['w'] # 1 in which, minus 1 in witch, minus 1 in watch 5434adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao -1 5444adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 5454adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao ''' 5464adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao if iterable is not None: 5474adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self_get = self.get 5484adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao if isinstance(iterable, Mapping): 5494adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao for elem, count in iterable.items(): 5504adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self[elem] = self_get(elem, 0) - count 5514adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao else: 5524adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao for elem in iterable: 5534adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self[elem] = self_get(elem, 0) - 1 5544adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao if kwds: 5554adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao self.subtract(kwds) 5564adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 5574adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao def copy(self): 5584adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 'Return a shallow copy.' 5594adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao return self.__class__(self) 5604adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 5614adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao def __reduce__(self): 5624adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao return self.__class__, (dict(self),) 5634adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 5644adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao def __delitem__(self, elem): 5654adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 'Like dict.__delitem__() but does not raise KeyError for missing values.' 5664adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao if elem in self: 5674adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao super(Counter, self).__delitem__(elem) 5684adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 5694adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao def __repr__(self): 5704adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao if not self: 5714adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao return '%s()' % self.__class__.__name__ 5724adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao items = ', '.join(map('%r: %r'.__mod__, self.most_common())) 5734adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao return '%s({%s})' % (self.__class__.__name__, items) 5744adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 5754adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao # Multiset-style mathematical operations discussed in: 5764adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao # Knuth TAOCP Volume II section 4.6.3 exercise 19 5774adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao # and at http://en.wikipedia.org/wiki/Multiset 5784adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao # 5794adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao # Outputs guaranteed to only include positive counts. 5804adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao # 5814adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao # To strip negative and zero counts, add-in an empty counter: 5824adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao # c += Counter() 5834adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 5844adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao def __add__(self, other): 5854adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao '''Add counts from two counters. 5864adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 5874adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao >>> Counter('abbb') + Counter('bcc') 5884adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao Counter({'b': 4, 'c': 2, 'a': 1}) 5894adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 5904adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao ''' 5914adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao if not isinstance(other, Counter): 5924adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao return NotImplemented 5934adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao result = Counter() 5944adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao for elem, count in self.items(): 5954adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao newcount = count + other[elem] 5964adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao if newcount > 0: 5974adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao result[elem] = newcount 5984adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao for elem, count in other.items(): 5994adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao if elem not in self and count > 0: 6004adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao result[elem] = count 6014adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao return result 6024adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 6034adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao def __sub__(self, other): 6044adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao ''' Subtract count, but keep only results with positive counts. 6054adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 6064adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao >>> Counter('abbbc') - Counter('bccd') 6074adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao Counter({'b': 2, 'a': 1}) 6084adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 6094adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao ''' 6104adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao if not isinstance(other, Counter): 6114adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao return NotImplemented 6124adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao result = Counter() 6134adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao for elem, count in self.items(): 6144adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao newcount = count - other[elem] 6154adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao if newcount > 0: 6164adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao result[elem] = newcount 6174adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao for elem, count in other.items(): 6184adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao if elem not in self and count < 0: 6194adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao result[elem] = 0 - count 6204adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao return result 6214adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 6224adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao def __or__(self, other): 6234adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao '''Union is the maximum of value in either of the input counters. 6244adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 6254adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao >>> Counter('abbb') | Counter('bcc') 6264adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao Counter({'b': 3, 'c': 2, 'a': 1}) 6274adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 6284adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao ''' 6294adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao if not isinstance(other, Counter): 6304adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao return NotImplemented 6314adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao result = Counter() 6324adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao for elem, count in self.items(): 6334adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao other_count = other[elem] 6344adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao newcount = other_count if count < other_count else count 6354adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao if newcount > 0: 6364adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao result[elem] = newcount 6374adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao for elem, count in other.items(): 6384adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao if elem not in self and count > 0: 6394adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao result[elem] = count 6404adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao return result 6414adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 6424adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao def __and__(self, other): 6434adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao ''' Intersection is the minimum of corresponding counts. 6444adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 6454adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao >>> Counter('abbb') & Counter('bcc') 6464adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao Counter({'b': 1}) 6474adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 6484adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao ''' 6494adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao if not isinstance(other, Counter): 6504adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao return NotImplemented 6514adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao result = Counter() 6524adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao for elem, count in self.items(): 6534adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao other_count = other[elem] 6544adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao newcount = count if count < other_count else other_count 6554adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao if newcount > 0: 6564adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao result[elem] = newcount 6574adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao return result 6584adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 6594adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 6604adfde8bc82dd39f59e0445588c3e599ada477dJosh Gaoif __name__ == '__main__': 6614adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao # verify that instances can be pickled 6624adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao from cPickle import loads, dumps 6634adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao Point = namedtuple('Point', 'x, y', True) 6644adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao p = Point(x=10, y=20) 6654adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao assert p == loads(dumps(p)) 6664adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 6674adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao # test and demonstrate ability to override methods 6684adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao class Point(namedtuple('Point', 'x y')): 6694adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao __slots__ = () 6704adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao @property 6714adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao def hypot(self): 6724adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao return (self.x ** 2 + self.y ** 2) ** 0.5 6734adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao def __str__(self): 6744adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao return 'Point: x=%6.3f y=%6.3f hypot=%6.3f' % (self.x, self.y, self.hypot) 6754adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 6764adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao for p in Point(3, 4), Point(14, 5/7.): 6774adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao print p 6784adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 6794adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao class Point(namedtuple('Point', 'x y')): 6804adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 'Point class with optimized _make() and _replace() without error-checking' 6814adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao __slots__ = () 6824adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao _make = classmethod(tuple.__new__) 6834adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao def _replace(self, _map=map, **kwds): 6844adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao return self._make(_map(kwds.get, ('x', 'y'), self)) 6854adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 6864adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao print Point(11, 22)._replace(x=100) 6874adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 6884adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao Point3D = namedtuple('Point3D', Point._fields + ('z',)) 6894adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao print Point3D.__doc__ 6904adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao 6914adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao import doctest 6924adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao TestResults = namedtuple('TestResults', 'failed attempted') 6934adfde8bc82dd39f59e0445588c3e599ada477dJosh Gao print TestResults(*doctest.testmod()) 694