14710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm__all__ = ['Counter', 'deque', 'defaultdict', 'namedtuple', 'OrderedDict'] 24710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm# For bootstrapping reasons, the collection ABCs are defined in _abcoll.py. 34710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm# They should however be considered an integral part of collections.py. 44710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmfrom _abcoll import * 54710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmimport _abcoll 64710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm__all__ += _abcoll.__all__ 74710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 84710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmfrom _collections import deque, defaultdict 94710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmfrom operator import itemgetter as _itemgetter 104710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmfrom keyword import iskeyword as _iskeyword 114710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmimport sys as _sys 124710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmimport heapq as _heapq 134710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmfrom itertools import repeat as _repeat, chain as _chain, starmap as _starmap 144710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 154710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmtry: 164710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm from thread import get_ident as _get_ident 174710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmexcept ImportError: 184710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm from dummy_thread import get_ident as _get_ident 194710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 204710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 214710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm################################################################################ 224710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm### OrderedDict 234710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm################################################################################ 244710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 254710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmclass OrderedDict(dict): 264710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 'Dictionary that remembers insertion order' 274710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm # An inherited dict maps keys to values. 284710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm # The inherited dict provides __getitem__, __len__, __contains__, and get. 294710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm # The remaining methods are order-aware. 304710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm # Big-O running times for all methods are the same as regular dictionaries. 314710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 324710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm # The internal self.__map dict maps keys to links in a doubly linked list. 334710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm # The circular doubly linked list starts and ends with a sentinel element. 344710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm # The sentinel element never gets deleted (this simplifies the algorithm). 354710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm # Each link is stored as a list of length three: [PREV, NEXT, KEY]. 364710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 374710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def __init__(self, *args, **kwds): 384710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm '''Initialize an ordered dictionary. The signature is the same as 394710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm regular dictionaries, but keyword arguments are not recommended because 404710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm their insertion order is arbitrary. 414710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 424710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm ''' 434710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if len(args) > 1: 444710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm raise TypeError('expected at most 1 arguments, got %d' % len(args)) 454710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm try: 464710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm self.__root 474710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm except AttributeError: 484710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm self.__root = root = [] # sentinel node 494710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm root[:] = [root, root, None] 504710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm self.__map = {} 514710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm self.__update(*args, **kwds) 524710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 534710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def __setitem__(self, key, value, PREV=0, NEXT=1, dict_setitem=dict.__setitem__): 544710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 'od.__setitem__(i, y) <==> od[i]=y' 554710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm # Setting a new item creates a new link at the end of the linked list, 564710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm # and the inherited dictionary is updated with the new key/value pair. 574710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if key not in self: 584710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm root = self.__root 594710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm last = root[PREV] 604710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm last[NEXT] = root[PREV] = self.__map[key] = [last, root, key] 614710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm dict_setitem(self, key, value) 624710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 634710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def __delitem__(self, key, PREV=0, NEXT=1, dict_delitem=dict.__delitem__): 644710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 'od.__delitem__(y) <==> del od[y]' 654710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm # Deleting an existing item uses self.__map to find the link which gets 664710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm # removed by updating the links in the predecessor and successor nodes. 674710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm dict_delitem(self, key) 684710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm link_prev, link_next, key = self.__map.pop(key) 694710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm link_prev[NEXT] = link_next 704710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm link_next[PREV] = link_prev 714710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 724710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def __iter__(self): 734710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 'od.__iter__() <==> iter(od)' 744710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm # Traverse the linked list in order. 754710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm NEXT, KEY = 1, 2 764710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm root = self.__root 774710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm curr = root[NEXT] 784710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm while curr is not root: 794710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm yield curr[KEY] 804710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm curr = curr[NEXT] 814710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 824710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def __reversed__(self): 834710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 'od.__reversed__() <==> reversed(od)' 844710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm # Traverse the linked list in reverse order. 854710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm PREV, KEY = 0, 2 864710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm root = self.__root 874710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm curr = root[PREV] 884710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm while curr is not root: 894710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm yield curr[KEY] 904710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm curr = curr[PREV] 914710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 924710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def clear(self): 934710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 'od.clear() -> None. Remove all items from od.' 944710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm for node in self.__map.itervalues(): 954710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm del node[:] 964710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm root = self.__root 974710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm root[:] = [root, root, None] 984710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm self.__map.clear() 994710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm dict.clear(self) 1004710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 1014710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm # -- the following methods do not depend on the internal structure -- 1024710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 1034710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def keys(self): 1044710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 'od.keys() -> list of keys in od' 1054710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return list(self) 1064710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 1074710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def values(self): 1084710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 'od.values() -> list of values in od' 1094710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return [self[key] for key in self] 1104710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 1114710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def items(self): 1124710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 'od.items() -> list of (key, value) pairs in od' 1134710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return [(key, self[key]) for key in self] 1144710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 1154710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def iterkeys(self): 1164710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 'od.iterkeys() -> an iterator over the keys in od' 1174710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return iter(self) 1184710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 1194710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def itervalues(self): 1204710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 'od.itervalues -> an iterator over the values in od' 1214710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm for k in self: 1224710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm yield self[k] 1234710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 1244710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def iteritems(self): 1254710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 'od.iteritems -> an iterator over the (key, value) pairs in od' 1264710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm for k in self: 1274710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm yield (k, self[k]) 1284710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 1294710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm update = MutableMapping.update 1304710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 1314710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm __update = update # let subclasses override update without breaking __init__ 1324710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 1334710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm __marker = object() 1344710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 1354710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def pop(self, key, default=__marker): 1364710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm '''od.pop(k[,d]) -> v, remove specified key and return the corresponding 1374710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm value. If key is not found, d is returned if given, otherwise KeyError 1384710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm is raised. 1394710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 1404710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm ''' 1414710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if key in self: 1424710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm result = self[key] 1434710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm del self[key] 1444710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return result 1454710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if default is self.__marker: 1464710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm raise KeyError(key) 1474710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return default 1484710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 1494710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def setdefault(self, key, default=None): 1504710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 'od.setdefault(k[,d]) -> od.get(k,d), also set od[k]=d if k not in od' 1514710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if key in self: 1524710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return self[key] 1534710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm self[key] = default 1544710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return default 1554710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 1564710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def popitem(self, last=True): 1574710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm '''od.popitem() -> (k, v), return and remove a (key, value) pair. 1584710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Pairs are returned in LIFO order if last is true or FIFO order if false. 1594710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 1604710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm ''' 1614710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if not self: 1624710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm raise KeyError('dictionary is empty') 1634710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm key = next(reversed(self) if last else iter(self)) 1644710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm value = self.pop(key) 1654710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return key, value 1664710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 1674710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def __repr__(self, _repr_running={}): 1684710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 'od.__repr__() <==> repr(od)' 1694710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm call_key = id(self), _get_ident() 1704710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if call_key in _repr_running: 1714710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return '...' 1724710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm _repr_running[call_key] = 1 1734710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm try: 1744710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if not self: 1754710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return '%s()' % (self.__class__.__name__,) 1764710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return '%s(%r)' % (self.__class__.__name__, self.items()) 1774710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm finally: 1784710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm del _repr_running[call_key] 1794710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 1804710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def __reduce__(self): 1814710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 'Return state information for pickling' 1824710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm items = [[k, self[k]] for k in self] 1834710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm inst_dict = vars(self).copy() 1844710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm for k in vars(OrderedDict()): 1854710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm inst_dict.pop(k, None) 1864710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if inst_dict: 1874710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return (self.__class__, (items,), inst_dict) 1884710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return self.__class__, (items,) 1894710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 1904710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def copy(self): 1914710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 'od.copy() -> a shallow copy of od' 1924710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return self.__class__(self) 1934710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 1944710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm @classmethod 1954710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def fromkeys(cls, iterable, value=None): 1964710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm '''OD.fromkeys(S[, v]) -> New ordered dictionary with keys from S. 1974710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm If not specified, the value defaults to None. 1984710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 1994710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm ''' 2004710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm self = cls() 2014710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm for key in iterable: 2024710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm self[key] = value 2034710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return self 2044710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 2054710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def __eq__(self, other): 2064710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm '''od.__eq__(y) <==> od==y. Comparison to another OD is order-sensitive 2074710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm while comparison to a regular mapping is order-insensitive. 2084710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 2094710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm ''' 2104710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if isinstance(other, OrderedDict): 2114710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return len(self)==len(other) and self.items() == other.items() 2124710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return dict.__eq__(self, other) 2134710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 2144710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def __ne__(self, other): 2154710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 'od.__ne__(y) <==> od!=y' 2164710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return not self == other 2174710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 2184710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm # -- the following methods support python 3.x style dictionary views -- 2194710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 2204710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def viewkeys(self): 2214710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm "od.viewkeys() -> a set-like object providing a view on od's keys" 2224710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return KeysView(self) 2234710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 2244710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def viewvalues(self): 2254710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm "od.viewvalues() -> an object providing a view on od's values" 2264710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return ValuesView(self) 2274710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 2284710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def viewitems(self): 2294710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm "od.viewitems() -> a set-like object providing a view on od's items" 2304710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return ItemsView(self) 2314710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 2324710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 2334710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm################################################################################ 2344710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm### namedtuple 2354710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm################################################################################ 2364710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 2374710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmdef namedtuple(typename, field_names, verbose=False, rename=False): 2384710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm """Returns a new subclass of tuple with named fields. 2394710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 2404710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm >>> Point = namedtuple('Point', 'x y') 2414710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm >>> Point.__doc__ # docstring for the new class 2424710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 'Point(x, y)' 2434710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm >>> p = Point(11, y=22) # instantiate with positional args or keywords 2444710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm >>> p[0] + p[1] # indexable like a plain tuple 2454710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 33 2464710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm >>> x, y = p # unpack like a regular tuple 2474710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm >>> x, y 2484710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm (11, 22) 2494710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm >>> p.x + p.y # fields also accessable by name 2504710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 33 2514710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm >>> d = p._asdict() # convert to a dictionary 2524710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm >>> d['x'] 2534710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 11 2544710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm >>> Point(**d) # convert from a dictionary 2554710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Point(x=11, y=22) 2564710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm >>> p._replace(x=100) # _replace() is like str.replace() but targets named fields 2574710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Point(x=100, y=22) 2584710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 2594710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm """ 2604710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 2614710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm # Parse and validate the field names. Validation serves two purposes, 2624710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm # generating informative error messages and preventing template injection attacks. 2634710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if isinstance(field_names, basestring): 2644710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm field_names = field_names.replace(',', ' ').split() # names separated by whitespace and/or commas 2654710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm field_names = tuple(map(str, field_names)) 2664710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if rename: 2674710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm names = list(field_names) 2684710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm seen = set() 2694710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm for i, name in enumerate(names): 2704710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if (not all(c.isalnum() or c=='_' for c in name) or _iskeyword(name) 2714710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm or not name or name[0].isdigit() or name.startswith('_') 2724710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm or name in seen): 2734710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm names[i] = '_%d' % i 2744710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm seen.add(name) 2754710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm field_names = tuple(names) 2764710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm for name in (typename,) + field_names: 2774710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if not all(c.isalnum() or c=='_' for c in name): 2784710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm raise ValueError('Type names and field names can only contain alphanumeric characters and underscores: %r' % name) 2794710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if _iskeyword(name): 2804710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm raise ValueError('Type names and field names cannot be a keyword: %r' % name) 2814710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if name[0].isdigit(): 2824710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm raise ValueError('Type names and field names cannot start with a number: %r' % name) 2834710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm seen_names = set() 2844710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm for name in field_names: 2854710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if name.startswith('_') and not rename: 2864710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm raise ValueError('Field names cannot start with an underscore: %r' % name) 2874710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if name in seen_names: 2884710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm raise ValueError('Encountered duplicate field name: %r' % name) 2894710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm seen_names.add(name) 2904710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 2914710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm # Create and fill-in the class template 2924710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm numfields = len(field_names) 2934710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm argtxt = repr(field_names).replace("'", "")[1:-1] # tuple repr without parens or quotes 2944710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm reprtxt = ', '.join('%s=%%r' % name for name in field_names) 2954710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm template = '''class %(typename)s(tuple): 2964710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm '%(typename)s(%(argtxt)s)' \n 2974710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm __slots__ = () \n 2984710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm _fields = %(field_names)r \n 2994710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def __new__(_cls, %(argtxt)s): 3004710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 'Create new instance of %(typename)s(%(argtxt)s)' 3014710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return _tuple.__new__(_cls, (%(argtxt)s)) \n 3024710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm @classmethod 3034710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def _make(cls, iterable, new=tuple.__new__, len=len): 3044710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 'Make a new %(typename)s object from a sequence or iterable' 3054710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm result = new(cls, iterable) 3064710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if len(result) != %(numfields)d: 3074710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm raise TypeError('Expected %(numfields)d arguments, got %%d' %% len(result)) 3084710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return result \n 3094710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def __repr__(self): 3104710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 'Return a nicely formatted representation string' 3114710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return '%(typename)s(%(reprtxt)s)' %% self \n 3124710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def _asdict(self): 3134710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 'Return a new OrderedDict which maps field names to their values' 3144710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return OrderedDict(zip(self._fields, self)) \n 3154710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def _replace(_self, **kwds): 3164710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 'Return a new %(typename)s object replacing specified fields with new values' 3174710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm result = _self._make(map(kwds.pop, %(field_names)r, _self)) 3184710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if kwds: 3194710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm raise ValueError('Got unexpected field names: %%r' %% kwds.keys()) 3204710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return result \n 3214710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def __getnewargs__(self): 3224710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 'Return self as a plain tuple. Used by copy and pickle.' 3234710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return tuple(self) \n\n''' % locals() 3244710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm for i, name in enumerate(field_names): 3254710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm template += " %s = _property(_itemgetter(%d), doc='Alias for field number %d')\n" % (name, i, i) 3264710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if verbose: 3274710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm print template 3284710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 3294710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm # Execute the template string in a temporary namespace and 3304710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm # support tracing utilities by setting a value for frame.f_globals['__name__'] 3314710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm namespace = dict(_itemgetter=_itemgetter, __name__='namedtuple_%s' % typename, 3324710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm OrderedDict=OrderedDict, _property=property, _tuple=tuple) 3334710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm try: 3344710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm exec template in namespace 3354710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm except SyntaxError, e: 3364710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm raise SyntaxError(e.message + ':\n' + template) 3374710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm result = namespace[typename] 3384710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 3394710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm # For pickling to work, the __module__ variable needs to be set to the frame 3404710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm # where the named tuple is created. Bypass this step in enviroments where 3414710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm # sys._getframe is not defined (Jython for example) or sys._getframe is not 3424710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm # defined for arguments greater than 0 (IronPython). 3434710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm try: 3444710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm result.__module__ = _sys._getframe(1).f_globals.get('__name__', '__main__') 3454710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm except (AttributeError, ValueError): 3464710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm pass 3474710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 3484710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return result 3494710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 3504710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 3514710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm######################################################################## 3524710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm### Counter 3534710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm######################################################################## 3544710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 3554710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmclass Counter(dict): 3564710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm '''Dict subclass for counting hashable items. Sometimes called a bag 3574710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm or multiset. Elements are stored as dictionary keys and their counts 3584710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm are stored as dictionary values. 3594710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 3604710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm >>> c = Counter('abcdeabcdabcaba') # count elements from a string 3614710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 3624710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm >>> c.most_common(3) # three most common elements 3634710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm [('a', 5), ('b', 4), ('c', 3)] 3644710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm >>> sorted(c) # list all unique elements 3654710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm ['a', 'b', 'c', 'd', 'e'] 3664710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm >>> ''.join(sorted(c.elements())) # list elements with repetitions 3674710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 'aaaaabbbbcccdde' 3684710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm >>> sum(c.values()) # total of all counts 3694710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 15 3704710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 3714710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm >>> c['a'] # count of letter 'a' 3724710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 5 3734710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm >>> for elem in 'shazam': # update counts from an iterable 3744710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm ... c[elem] += 1 # by adding 1 to each element's count 3754710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm >>> c['a'] # now there are seven 'a' 3764710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 7 3774710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm >>> del c['b'] # remove all 'b' 3784710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm >>> c['b'] # now there are zero 'b' 3794710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 0 3804710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 3814710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm >>> d = Counter('simsalabim') # make another counter 3824710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm >>> c.update(d) # add in the second counter 3834710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm >>> c['a'] # now there are nine 'a' 3844710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 9 3854710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 3864710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm >>> c.clear() # empty the counter 3874710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm >>> c 3884710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Counter() 3894710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 3904710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Note: If a count is set to zero or reduced to zero, it will remain 3914710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm in the counter until the entry is deleted or the counter is cleared: 3924710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 3934710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm >>> c = Counter('aaabbc') 3944710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm >>> c['b'] -= 2 # reduce the count of 'b' by two 3954710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm >>> c.most_common() # 'b' is still in, but its count is zero 3964710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm [('a', 3), ('c', 1), ('b', 0)] 3974710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 3984710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm ''' 3994710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm # References: 4004710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm # http://en.wikipedia.org/wiki/Multiset 4014710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm # http://www.gnu.org/software/smalltalk/manual-base/html_node/Bag.html 4024710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm # http://www.demo2s.com/Tutorial/Cpp/0380__set-multiset/Catalog0380__set-multiset.htm 4034710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm # http://code.activestate.com/recipes/259174/ 4044710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm # Knuth, TAOCP Vol. II section 4.6.3 4054710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 4064710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def __init__(self, iterable=None, **kwds): 4074710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm '''Create a new, empty Counter object. And if given, count elements 4084710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm from an input iterable. Or, initialize the count from another mapping 4094710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm of elements to their counts. 4104710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 4114710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm >>> c = Counter() # a new, empty counter 4124710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm >>> c = Counter('gallahad') # a new counter from an iterable 4134710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm >>> c = Counter({'a': 4, 'b': 2}) # a new counter from a mapping 4144710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm >>> c = Counter(a=4, b=2) # a new counter from keyword args 4154710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 4164710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm ''' 4174710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm super(Counter, self).__init__() 4184710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm self.update(iterable, **kwds) 4194710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 4204710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def __missing__(self, key): 4214710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 'The count of elements not in the Counter is zero.' 4224710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm # Needed so that self[missing_item] does not raise KeyError 4234710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return 0 4244710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 4254710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def most_common(self, n=None): 4264710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm '''List the n most common elements and their counts from the most 4274710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm common to the least. If n is None, then list all element counts. 4284710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 4294710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm >>> Counter('abcdeabcdabcaba').most_common(3) 4304710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm [('a', 5), ('b', 4), ('c', 3)] 4314710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 4324710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm ''' 4334710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm # Emulate Bag.sortedByCount from Smalltalk 4344710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if n is None: 4354710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return sorted(self.iteritems(), key=_itemgetter(1), reverse=True) 4364710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return _heapq.nlargest(n, self.iteritems(), key=_itemgetter(1)) 4374710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 4384710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def elements(self): 4394710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm '''Iterator over elements repeating each as many times as its count. 4404710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 4414710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm >>> c = Counter('ABCABC') 4424710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm >>> sorted(c.elements()) 4434710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm ['A', 'A', 'B', 'B', 'C', 'C'] 4444710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 4454710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm # Knuth's example for prime factors of 1836: 2**2 * 3**3 * 17**1 4464710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm >>> prime_factors = Counter({2: 2, 3: 3, 17: 1}) 4474710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm >>> product = 1 4484710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm >>> for factor in prime_factors.elements(): # loop over factors 4494710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm ... product *= factor # and multiply them 4504710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm >>> product 4514710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 1836 4524710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 4534710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Note, if an element's count has been set to zero or is a negative 4544710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm number, elements() will ignore it. 4554710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 4564710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm ''' 4574710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm # Emulate Bag.do from Smalltalk and Multiset.begin from C++. 4584710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return _chain.from_iterable(_starmap(_repeat, self.iteritems())) 4594710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 4604710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm # Override dict methods where necessary 4614710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 4624710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm @classmethod 4634710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def fromkeys(cls, iterable, v=None): 4644710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm # There is no equivalent method for counters because setting v=1 4654710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm # means that no element can have a count greater than one. 4664710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm raise NotImplementedError( 4674710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 'Counter.fromkeys() is undefined. Use Counter(iterable) instead.') 4684710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 4694710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def update(self, iterable=None, **kwds): 4704710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm '''Like dict.update() but add counts instead of replacing them. 4714710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 4724710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Source can be an iterable, a dictionary, or another Counter instance. 4734710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 4744710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm >>> c = Counter('which') 4754710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm >>> c.update('witch') # add elements from another iterable 4764710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm >>> d = Counter('watch') 4774710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm >>> c.update(d) # add elements from another counter 4784710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm >>> c['h'] # four 'h' in which, witch, and watch 4794710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 4 4804710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 4814710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm ''' 4824710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm # The regular dict.update() operation makes no sense here because the 4834710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm # replace behavior results in the some of original untouched counts 4844710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm # being mixed-in with all of the other counts for a mismash that 4854710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm # doesn't have a straight-forward interpretation in most counting 4864710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm # contexts. Instead, we implement straight-addition. Both the inputs 4874710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm # and outputs are allowed to contain zero and negative counts. 4884710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 4894710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if iterable is not None: 4904710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if isinstance(iterable, Mapping): 4914710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if self: 4924710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm self_get = self.get 4934710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm for elem, count in iterable.iteritems(): 4944710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm self[elem] = self_get(elem, 0) + count 4954710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm else: 4964710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm super(Counter, self).update(iterable) # fast path when counter is empty 4974710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm else: 4984710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm self_get = self.get 4994710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm for elem in iterable: 5004710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm self[elem] = self_get(elem, 0) + 1 5014710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if kwds: 5024710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm self.update(kwds) 5034710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 5044710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def subtract(self, iterable=None, **kwds): 5054710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm '''Like dict.update() but subtracts counts instead of replacing them. 5064710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Counts can be reduced below zero. Both the inputs and outputs are 5074710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm allowed to contain zero and negative counts. 5084710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 5094710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Source can be an iterable, a dictionary, or another Counter instance. 5104710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 5114710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm >>> c = Counter('which') 5124710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm >>> c.subtract('witch') # subtract elements from another iterable 5134710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm >>> c.subtract(Counter('watch')) # subtract elements from another counter 5144710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm >>> c['h'] # 2 in which, minus 1 in witch, minus 1 in watch 5154710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 0 5164710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm >>> c['w'] # 1 in which, minus 1 in witch, minus 1 in watch 5174710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm -1 5184710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 5194710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm ''' 5204710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if iterable is not None: 5214710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm self_get = self.get 5224710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if isinstance(iterable, Mapping): 5234710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm for elem, count in iterable.items(): 5244710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm self[elem] = self_get(elem, 0) - count 5254710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm else: 5264710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm for elem in iterable: 5274710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm self[elem] = self_get(elem, 0) - 1 5284710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if kwds: 5294710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm self.subtract(kwds) 5304710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 5314710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def copy(self): 5324710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 'Return a shallow copy.' 5334710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return self.__class__(self) 5344710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 5354710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def __reduce__(self): 5364710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return self.__class__, (dict(self),) 5374710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 5384710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def __delitem__(self, elem): 5394710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 'Like dict.__delitem__() but does not raise KeyError for missing values.' 5404710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if elem in self: 5414710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm super(Counter, self).__delitem__(elem) 5424710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 5434710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def __repr__(self): 5444710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if not self: 5454710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return '%s()' % self.__class__.__name__ 5464710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm items = ', '.join(map('%r: %r'.__mod__, self.most_common())) 5474710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return '%s({%s})' % (self.__class__.__name__, items) 5484710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 5494710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm # Multiset-style mathematical operations discussed in: 5504710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm # Knuth TAOCP Volume II section 4.6.3 exercise 19 5514710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm # and at http://en.wikipedia.org/wiki/Multiset 5524710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm # 5534710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm # Outputs guaranteed to only include positive counts. 5544710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm # 5554710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm # To strip negative and zero counts, add-in an empty counter: 5564710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm # c += Counter() 5574710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 5584710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def __add__(self, other): 5594710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm '''Add counts from two counters. 5604710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 5614710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm >>> Counter('abbb') + Counter('bcc') 5624710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Counter({'b': 4, 'c': 2, 'a': 1}) 5634710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 5644710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm ''' 5654710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if not isinstance(other, Counter): 5664710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return NotImplemented 5674710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm result = Counter() 5684710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm for elem, count in self.items(): 5694710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm newcount = count + other[elem] 5704710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if newcount > 0: 5714710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm result[elem] = newcount 5724710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm for elem, count in other.items(): 5734710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if elem not in self and count > 0: 5744710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm result[elem] = count 5754710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return result 5764710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 5774710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def __sub__(self, other): 5784710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm ''' Subtract count, but keep only results with positive counts. 5794710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 5804710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm >>> Counter('abbbc') - Counter('bccd') 5814710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Counter({'b': 2, 'a': 1}) 5824710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 5834710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm ''' 5844710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if not isinstance(other, Counter): 5854710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return NotImplemented 5864710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm result = Counter() 5874710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm for elem, count in self.items(): 5884710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm newcount = count - other[elem] 5894710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if newcount > 0: 5904710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm result[elem] = newcount 5914710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm for elem, count in other.items(): 5924710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if elem not in self and count < 0: 5934710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm result[elem] = 0 - count 5944710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return result 5954710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 5964710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def __or__(self, other): 5974710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm '''Union is the maximum of value in either of the input counters. 5984710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 5994710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm >>> Counter('abbb') | Counter('bcc') 6004710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Counter({'b': 3, 'c': 2, 'a': 1}) 6014710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 6024710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm ''' 6034710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if not isinstance(other, Counter): 6044710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return NotImplemented 6054710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm result = Counter() 6064710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm for elem, count in self.items(): 6074710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm other_count = other[elem] 6084710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm newcount = other_count if count < other_count else count 6094710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if newcount > 0: 6104710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm result[elem] = newcount 6114710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm for elem, count in other.items(): 6124710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if elem not in self and count > 0: 6134710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm result[elem] = count 6144710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return result 6154710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 6164710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def __and__(self, other): 6174710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm ''' Intersection is the minimum of corresponding counts. 6184710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 6194710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm >>> Counter('abbb') & Counter('bcc') 6204710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Counter({'b': 1}) 6214710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 6224710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm ''' 6234710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if not isinstance(other, Counter): 6244710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return NotImplemented 6254710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm result = Counter() 6264710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm for elem, count in self.items(): 6274710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm other_count = other[elem] 6284710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm newcount = count if count < other_count else other_count 6294710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm if newcount > 0: 6304710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm result[elem] = newcount 6314710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return result 6324710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 6334710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 6344710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylmif __name__ == '__main__': 6354710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm # verify that instances can be pickled 6364710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm from cPickle import loads, dumps 6374710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Point = namedtuple('Point', 'x, y', True) 6384710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm p = Point(x=10, y=20) 6394710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm assert p == loads(dumps(p)) 6404710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 6414710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm # test and demonstrate ability to override methods 6424710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm class Point(namedtuple('Point', 'x y')): 6434710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm __slots__ = () 6444710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm @property 6454710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def hypot(self): 6464710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return (self.x ** 2 + self.y ** 2) ** 0.5 6474710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def __str__(self): 6484710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return 'Point: x=%6.3f y=%6.3f hypot=%6.3f' % (self.x, self.y, self.hypot) 6494710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 6504710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm for p in Point(3, 4), Point(14, 5/7.): 6514710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm print p 6524710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 6534710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm class Point(namedtuple('Point', 'x y')): 6544710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 'Point class with optimized _make() and _replace() without error-checking' 6554710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm __slots__ = () 6564710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm _make = classmethod(tuple.__new__) 6574710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm def _replace(self, _map=map, **kwds): 6584710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm return self._make(_map(kwds.get, ('x', 'y'), self)) 6594710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 6604710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm print Point(11, 22)._replace(x=100) 6614710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 6624710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm Point3D = namedtuple('Point3D', Point._fields + ('z',)) 6634710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm print Point3D.__doc__ 6644710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm 6654710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm import doctest 6664710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm TestResults = namedtuple('TestResults', 'failed attempted') 6674710c53dcad1ebf3755f3efb9e80ac24bd72a9b2darylm print TestResults(*doctest.testmod()) 668