1ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh__all__ = ['Counter', 'deque', 'defaultdict', 'namedtuple', 'OrderedDict'] 2ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh# For bootstrapping reasons, the collection ABCs are defined in _abcoll.py. 3ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh# They should however be considered an integral part of collections.py. 4ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsiehfrom _abcoll import * 5ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsiehimport _abcoll 6ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh__all__ += _abcoll.__all__ 7ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 8ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsiehfrom _collections import deque, defaultdict 9ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsiehfrom operator import itemgetter as _itemgetter, eq as _eq 10ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsiehfrom keyword import iskeyword as _iskeyword 11ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsiehimport sys as _sys 12ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsiehimport heapq as _heapq 13ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsiehfrom itertools import repeat as _repeat, chain as _chain, starmap as _starmap 14ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsiehfrom itertools import imap as _imap 15ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 16ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsiehtry: 17ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh from thread import get_ident as _get_ident 18ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsiehexcept ImportError: 19ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh from dummy_thread import get_ident as _get_ident 20ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 21ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 22ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh################################################################################ 23ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh### OrderedDict 24ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh################################################################################ 25ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 26ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsiehclass OrderedDict(dict): 27ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 'Dictionary that remembers insertion order' 28ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh # An inherited dict maps keys to values. 29ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh # The inherited dict provides __getitem__, __len__, __contains__, and get. 30ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh # The remaining methods are order-aware. 31ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh # Big-O running times for all methods are the same as regular dictionaries. 32ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 33ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh # The internal self.__map dict maps keys to links in a doubly linked list. 34ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh # The circular doubly linked list starts and ends with a sentinel element. 35ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh # The sentinel element never gets deleted (this simplifies the algorithm). 36ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh # Each link is stored as a list of length three: [PREV, NEXT, KEY]. 37ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 38ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def __init__(self, *args, **kwds): 39ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh '''Initialize an ordered dictionary. The signature is the same as 40ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh regular dictionaries, but keyword arguments are not recommended because 41ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh their insertion order is arbitrary. 42ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 43ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh ''' 44ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh if len(args) > 1: 45ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh raise TypeError('expected at most 1 arguments, got %d' % len(args)) 46ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh try: 47ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh self.__root 48ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh except AttributeError: 49ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh self.__root = root = [] # sentinel node 50ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh root[:] = [root, root, None] 51ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh self.__map = {} 52ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh self.__update(*args, **kwds) 53ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 54ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def __setitem__(self, key, value, dict_setitem=dict.__setitem__): 55ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 'od.__setitem__(i, y) <==> od[i]=y' 56ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh # Setting a new item creates a new link at the end of the linked list, 57ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh # and the inherited dictionary is updated with the new key/value pair. 58ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh if key not in self: 59ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh root = self.__root 60ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh last = root[0] 61ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh last[1] = root[0] = self.__map[key] = [last, root, key] 62ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return dict_setitem(self, key, value) 63ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 64ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def __delitem__(self, key, dict_delitem=dict.__delitem__): 65ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 'od.__delitem__(y) <==> del od[y]' 66ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh # Deleting an existing item uses self.__map to find the link which gets 67ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh # removed by updating the links in the predecessor and successor nodes. 68ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh dict_delitem(self, key) 69ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh link_prev, link_next, _ = self.__map.pop(key) 70ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh link_prev[1] = link_next # update link_prev[NEXT] 71ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh link_next[0] = link_prev # update link_next[PREV] 72ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 73ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def __iter__(self): 74ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 'od.__iter__() <==> iter(od)' 75ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh # Traverse the linked list in order. 76ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh root = self.__root 77ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh curr = root[1] # start at the first node 78ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh while curr is not root: 79ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh yield curr[2] # yield the curr[KEY] 80ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh curr = curr[1] # move to next node 81ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 82ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def __reversed__(self): 83ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 'od.__reversed__() <==> reversed(od)' 84ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh # Traverse the linked list in reverse order. 85ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh root = self.__root 86ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh curr = root[0] # start at the last node 87ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh while curr is not root: 88ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh yield curr[2] # yield the curr[KEY] 89ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh curr = curr[0] # move to previous node 90ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 91ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def clear(self): 92ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 'od.clear() -> None. Remove all items from od.' 93ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh root = self.__root 94ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh root[:] = [root, root, None] 95ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh self.__map.clear() 96ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh dict.clear(self) 97ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 98ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh # -- the following methods do not depend on the internal structure -- 99ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 100ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def keys(self): 101ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 'od.keys() -> list of keys in od' 102ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return list(self) 103ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 104ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def values(self): 105ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 'od.values() -> list of values in od' 106ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return [self[key] for key in self] 107ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 108ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def items(self): 109ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 'od.items() -> list of (key, value) pairs in od' 110ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return [(key, self[key]) for key in self] 111ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 112ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def iterkeys(self): 113ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 'od.iterkeys() -> an iterator over the keys in od' 114ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return iter(self) 115ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 116ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def itervalues(self): 117ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 'od.itervalues -> an iterator over the values in od' 118ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh for k in self: 119ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh yield self[k] 120ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 121ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def iteritems(self): 122ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 'od.iteritems -> an iterator over the (key, value) pairs in od' 123ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh for k in self: 124ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh yield (k, self[k]) 125ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 126ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh update = MutableMapping.update 127ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 128ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh __update = update # let subclasses override update without breaking __init__ 129ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 130ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh __marker = object() 131ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 132ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def pop(self, key, default=__marker): 133ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh '''od.pop(k[,d]) -> v, remove specified key and return the corresponding 134ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh value. If key is not found, d is returned if given, otherwise KeyError 135ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh is raised. 136ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 137ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh ''' 138ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh if key in self: 139ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh result = self[key] 140ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh del self[key] 141ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return result 142ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh if default is self.__marker: 143ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh raise KeyError(key) 144ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return default 145ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 146ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def setdefault(self, key, default=None): 147ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 'od.setdefault(k[,d]) -> od.get(k,d), also set od[k]=d if k not in od' 148ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh if key in self: 149ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return self[key] 150ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh self[key] = default 151ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return default 152ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 153ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def popitem(self, last=True): 154ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh '''od.popitem() -> (k, v), return and remove a (key, value) pair. 155ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh Pairs are returned in LIFO order if last is true or FIFO order if false. 156ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 157ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh ''' 158ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh if not self: 159ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh raise KeyError('dictionary is empty') 160ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh key = next(reversed(self) if last else iter(self)) 161ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh value = self.pop(key) 162ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return key, value 163ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 164ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def __repr__(self, _repr_running={}): 165ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 'od.__repr__() <==> repr(od)' 166ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh call_key = id(self), _get_ident() 167ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh if call_key in _repr_running: 168ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return '...' 169ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh _repr_running[call_key] = 1 170ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh try: 171ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh if not self: 172ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return '%s()' % (self.__class__.__name__,) 173ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return '%s(%r)' % (self.__class__.__name__, self.items()) 174ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh finally: 175ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh del _repr_running[call_key] 176ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 177ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def __reduce__(self): 178ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 'Return state information for pickling' 179ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh items = [[k, self[k]] for k in self] 180ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh inst_dict = vars(self).copy() 181ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh for k in vars(OrderedDict()): 182ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh inst_dict.pop(k, None) 183ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh if inst_dict: 184ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return (self.__class__, (items,), inst_dict) 185ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return self.__class__, (items,) 186ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 187ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def copy(self): 188ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 'od.copy() -> a shallow copy of od' 189ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return self.__class__(self) 190ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 191ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh @classmethod 192ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def fromkeys(cls, iterable, value=None): 193ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh '''OD.fromkeys(S[, v]) -> New ordered dictionary with keys from S. 194ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh If not specified, the value defaults to None. 195ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 196ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh ''' 197ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh self = cls() 198ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh for key in iterable: 199ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh self[key] = value 200ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return self 201ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 202ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def __eq__(self, other): 203ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh '''od.__eq__(y) <==> od==y. Comparison to another OD is order-sensitive 204ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh while comparison to a regular mapping is order-insensitive. 205ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 206ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh ''' 207ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh if isinstance(other, OrderedDict): 208ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return dict.__eq__(self, other) and all(_imap(_eq, self, other)) 209ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return dict.__eq__(self, other) 210ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 211ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def __ne__(self, other): 212ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 'od.__ne__(y) <==> od!=y' 213ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return not self == other 214ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 215ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh # -- the following methods support python 3.x style dictionary views -- 216ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 217ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def viewkeys(self): 218ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh "od.viewkeys() -> a set-like object providing a view on od's keys" 219ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return KeysView(self) 220ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 221ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def viewvalues(self): 222ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh "od.viewvalues() -> an object providing a view on od's values" 223ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return ValuesView(self) 224ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 225ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def viewitems(self): 226ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh "od.viewitems() -> a set-like object providing a view on od's items" 227ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return ItemsView(self) 228ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 229ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 230ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh################################################################################ 231ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh### namedtuple 232ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh################################################################################ 233ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 234ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh_class_template = '''\ 235ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsiehclass {typename}(tuple): 236ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh '{typename}({arg_list})' 237ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 238ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh __slots__ = () 239ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 240ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh _fields = {field_names!r} 241ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 242ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def __new__(_cls, {arg_list}): 243ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 'Create new instance of {typename}({arg_list})' 244ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return _tuple.__new__(_cls, ({arg_list})) 245ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 246ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh @classmethod 247ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def _make(cls, iterable, new=tuple.__new__, len=len): 248ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 'Make a new {typename} object from a sequence or iterable' 249ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh result = new(cls, iterable) 250ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh if len(result) != {num_fields:d}: 251ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh raise TypeError('Expected {num_fields:d} arguments, got %d' % len(result)) 252ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return result 253ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 254ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def __repr__(self): 255ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 'Return a nicely formatted representation string' 256ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return '{typename}({repr_fmt})' % self 257ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 258ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def _asdict(self): 259ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 'Return a new OrderedDict which maps field names to their values' 260ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return OrderedDict(zip(self._fields, self)) 261ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 262ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def _replace(_self, **kwds): 263ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 'Return a new {typename} object replacing specified fields with new values' 264ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh result = _self._make(map(kwds.pop, {field_names!r}, _self)) 265ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh if kwds: 266ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh raise ValueError('Got unexpected field names: %r' % kwds.keys()) 267ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return result 268ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 269ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def __getnewargs__(self): 270ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 'Return self as a plain tuple. Used by copy and pickle.' 271ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return tuple(self) 272ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 273ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh{field_defs} 274ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh''' 275ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 276ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh_repr_template = '{name}=%r' 277ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 278ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh_field_template = '''\ 279ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh {name} = _property(_itemgetter({index:d}), doc='Alias for field number {index:d}') 280ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh''' 281ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 282ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsiehdef namedtuple(typename, field_names, verbose=False, rename=False): 283ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh """Returns a new subclass of tuple with named fields. 284ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 285ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh >>> Point = namedtuple('Point', ['x', 'y']) 286ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh >>> Point.__doc__ # docstring for the new class 287ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 'Point(x, y)' 288ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh >>> p = Point(11, y=22) # instantiate with positional args or keywords 289ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh >>> p[0] + p[1] # indexable like a plain tuple 290ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 33 291ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh >>> x, y = p # unpack like a regular tuple 292ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh >>> x, y 293ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh (11, 22) 294ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh >>> p.x + p.y # fields also accessable by name 295ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 33 296ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh >>> d = p._asdict() # convert to a dictionary 297ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh >>> d['x'] 298ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 11 299ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh >>> Point(**d) # convert from a dictionary 300ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh Point(x=11, y=22) 301ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh >>> p._replace(x=100) # _replace() is like str.replace() but targets named fields 302ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh Point(x=100, y=22) 303ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 304ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh """ 305ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 306ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh # Validate the field names. At the user's option, either generate an error 307ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh # message or automatically replace the field name with a valid name. 308ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh if isinstance(field_names, basestring): 309ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh field_names = field_names.replace(',', ' ').split() 310ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh field_names = map(str, field_names) 311ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh if rename: 312ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh seen = set() 313ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh for index, name in enumerate(field_names): 314ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh if (not all(c.isalnum() or c=='_' for c in name) 315ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh or _iskeyword(name) 316ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh or not name 317ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh or name[0].isdigit() 318ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh or name.startswith('_') 319ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh or name in seen): 320ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh field_names[index] = '_%d' % index 321ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh seen.add(name) 322ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh for name in [typename] + field_names: 323ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh if not all(c.isalnum() or c=='_' for c in name): 324ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh raise ValueError('Type names and field names can only contain ' 325ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 'alphanumeric characters and underscores: %r' % name) 326ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh if _iskeyword(name): 327ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh raise ValueError('Type names and field names cannot be a ' 328ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 'keyword: %r' % name) 329ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh if name[0].isdigit(): 330ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh raise ValueError('Type names and field names cannot start with ' 331ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 'a number: %r' % name) 332ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh seen = set() 333ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh for name in field_names: 334ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh if name.startswith('_') and not rename: 335ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh raise ValueError('Field names cannot start with an underscore: ' 336ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh '%r' % name) 337ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh if name in seen: 338ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh raise ValueError('Encountered duplicate field name: %r' % name) 339ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh seen.add(name) 340ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 341ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh # Fill-in the class template 342ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh class_definition = _class_template.format( 343ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh typename = typename, 344ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh field_names = tuple(field_names), 345ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh num_fields = len(field_names), 346ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh arg_list = repr(tuple(field_names)).replace("'", "")[1:-1], 347ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh repr_fmt = ', '.join(_repr_template.format(name=name) 348ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh for name in field_names), 349ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh field_defs = '\n'.join(_field_template.format(index=index, name=name) 350ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh for index, name in enumerate(field_names)) 351ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh ) 352ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh if verbose: 353ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh print class_definition 354ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 355ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh # Execute the template string in a temporary namespace and support 356ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh # tracing utilities by setting a value for frame.f_globals['__name__'] 357ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh namespace = dict(_itemgetter=_itemgetter, __name__='namedtuple_%s' % typename, 358ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh OrderedDict=OrderedDict, _property=property, _tuple=tuple) 359ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh try: 360ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh exec class_definition in namespace 361ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh except SyntaxError as e: 362ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh raise SyntaxError(e.message + ':\n' + class_definition) 363ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh result = namespace[typename] 364ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 365ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh # For pickling to work, the __module__ variable needs to be set to the frame 366ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh # where the named tuple is created. Bypass this step in enviroments where 367ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh # sys._getframe is not defined (Jython for example) or sys._getframe is not 368ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh # defined for arguments greater than 0 (IronPython). 369ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh try: 370ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh result.__module__ = _sys._getframe(1).f_globals.get('__name__', '__main__') 371ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh except (AttributeError, ValueError): 372ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh pass 373ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 374ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return result 375ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 376ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 377ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh######################################################################## 378ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh### Counter 379ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh######################################################################## 380ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 381ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsiehclass Counter(dict): 382ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh '''Dict subclass for counting hashable items. Sometimes called a bag 383ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh or multiset. Elements are stored as dictionary keys and their counts 384ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh are stored as dictionary values. 385ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 386ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh >>> c = Counter('abcdeabcdabcaba') # count elements from a string 387ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 388ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh >>> c.most_common(3) # three most common elements 389ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh [('a', 5), ('b', 4), ('c', 3)] 390ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh >>> sorted(c) # list all unique elements 391ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh ['a', 'b', 'c', 'd', 'e'] 392ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh >>> ''.join(sorted(c.elements())) # list elements with repetitions 393ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 'aaaaabbbbcccdde' 394ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh >>> sum(c.values()) # total of all counts 395ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 15 396ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 397ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh >>> c['a'] # count of letter 'a' 398ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 5 399ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh >>> for elem in 'shazam': # update counts from an iterable 400ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh ... c[elem] += 1 # by adding 1 to each element's count 401ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh >>> c['a'] # now there are seven 'a' 402ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 7 403ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh >>> del c['b'] # remove all 'b' 404ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh >>> c['b'] # now there are zero 'b' 405ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 0 406ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 407ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh >>> d = Counter('simsalabim') # make another counter 408ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh >>> c.update(d) # add in the second counter 409ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh >>> c['a'] # now there are nine 'a' 410ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 9 411ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 412ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh >>> c.clear() # empty the counter 413ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh >>> c 414ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh Counter() 415ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 416ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh Note: If a count is set to zero or reduced to zero, it will remain 417ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh in the counter until the entry is deleted or the counter is cleared: 418ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 419ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh >>> c = Counter('aaabbc') 420ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh >>> c['b'] -= 2 # reduce the count of 'b' by two 421ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh >>> c.most_common() # 'b' is still in, but its count is zero 422ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh [('a', 3), ('c', 1), ('b', 0)] 423ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 424ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh ''' 425ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh # References: 426ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh # http://en.wikipedia.org/wiki/Multiset 427ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh # http://www.gnu.org/software/smalltalk/manual-base/html_node/Bag.html 428ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh # http://www.demo2s.com/Tutorial/Cpp/0380__set-multiset/Catalog0380__set-multiset.htm 429ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh # http://code.activestate.com/recipes/259174/ 430ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh # Knuth, TAOCP Vol. II section 4.6.3 431ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 432ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def __init__(self, iterable=None, **kwds): 433ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh '''Create a new, empty Counter object. And if given, count elements 434ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh from an input iterable. Or, initialize the count from another mapping 435ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh of elements to their counts. 436ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 437ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh >>> c = Counter() # a new, empty counter 438ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh >>> c = Counter('gallahad') # a new counter from an iterable 439ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh >>> c = Counter({'a': 4, 'b': 2}) # a new counter from a mapping 440ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh >>> c = Counter(a=4, b=2) # a new counter from keyword args 441ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 442ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh ''' 443ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh super(Counter, self).__init__() 444ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh self.update(iterable, **kwds) 445ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 446ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def __missing__(self, key): 447ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 'The count of elements not in the Counter is zero.' 448ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh # Needed so that self[missing_item] does not raise KeyError 449ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return 0 450ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 451ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def most_common(self, n=None): 452ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh '''List the n most common elements and their counts from the most 453ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh common to the least. If n is None, then list all element counts. 454ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 455ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh >>> Counter('abcdeabcdabcaba').most_common(3) 456ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh [('a', 5), ('b', 4), ('c', 3)] 457ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 458ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh ''' 459ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh # Emulate Bag.sortedByCount from Smalltalk 460ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh if n is None: 461ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return sorted(self.iteritems(), key=_itemgetter(1), reverse=True) 462ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return _heapq.nlargest(n, self.iteritems(), key=_itemgetter(1)) 463ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 464ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def elements(self): 465ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh '''Iterator over elements repeating each as many times as its count. 466ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 467ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh >>> c = Counter('ABCABC') 468ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh >>> sorted(c.elements()) 469ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh ['A', 'A', 'B', 'B', 'C', 'C'] 470ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 471ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh # Knuth's example for prime factors of 1836: 2**2 * 3**3 * 17**1 472ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh >>> prime_factors = Counter({2: 2, 3: 3, 17: 1}) 473ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh >>> product = 1 474ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh >>> for factor in prime_factors.elements(): # loop over factors 475ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh ... product *= factor # and multiply them 476ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh >>> product 477ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 1836 478ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 479ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh Note, if an element's count has been set to zero or is a negative 480ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh number, elements() will ignore it. 481ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 482ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh ''' 483ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh # Emulate Bag.do from Smalltalk and Multiset.begin from C++. 484ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return _chain.from_iterable(_starmap(_repeat, self.iteritems())) 485ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 486ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh # Override dict methods where necessary 487ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 488ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh @classmethod 489ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def fromkeys(cls, iterable, v=None): 490ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh # There is no equivalent method for counters because setting v=1 491ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh # means that no element can have a count greater than one. 492ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh raise NotImplementedError( 493ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 'Counter.fromkeys() is undefined. Use Counter(iterable) instead.') 494ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 495ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def update(self, iterable=None, **kwds): 496ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh '''Like dict.update() but add counts instead of replacing them. 497ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 498ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh Source can be an iterable, a dictionary, or another Counter instance. 499ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 500ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh >>> c = Counter('which') 501ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh >>> c.update('witch') # add elements from another iterable 502ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh >>> d = Counter('watch') 503ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh >>> c.update(d) # add elements from another counter 504ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh >>> c['h'] # four 'h' in which, witch, and watch 505ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 4 506ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 507ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh ''' 508ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh # The regular dict.update() operation makes no sense here because the 509ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh # replace behavior results in the some of original untouched counts 510ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh # being mixed-in with all of the other counts for a mismash that 511ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh # doesn't have a straight-forward interpretation in most counting 512ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh # contexts. Instead, we implement straight-addition. Both the inputs 513ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh # and outputs are allowed to contain zero and negative counts. 514ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 515ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh if iterable is not None: 516ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh if isinstance(iterable, Mapping): 517ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh if self: 518ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh self_get = self.get 519ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh for elem, count in iterable.iteritems(): 520ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh self[elem] = self_get(elem, 0) + count 521ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh else: 522ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh super(Counter, self).update(iterable) # fast path when counter is empty 523ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh else: 524ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh self_get = self.get 525ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh for elem in iterable: 526ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh self[elem] = self_get(elem, 0) + 1 527ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh if kwds: 528ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh self.update(kwds) 529ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 530ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def subtract(self, iterable=None, **kwds): 531ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh '''Like dict.update() but subtracts counts instead of replacing them. 532ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh Counts can be reduced below zero. Both the inputs and outputs are 533ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh allowed to contain zero and negative counts. 534ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 535ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh Source can be an iterable, a dictionary, or another Counter instance. 536ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 537ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh >>> c = Counter('which') 538ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh >>> c.subtract('witch') # subtract elements from another iterable 539ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh >>> c.subtract(Counter('watch')) # subtract elements from another counter 540ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh >>> c['h'] # 2 in which, minus 1 in witch, minus 1 in watch 541ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 0 542ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh >>> c['w'] # 1 in which, minus 1 in witch, minus 1 in watch 543ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh -1 544ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 545ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh ''' 546ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh if iterable is not None: 547ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh self_get = self.get 548ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh if isinstance(iterable, Mapping): 549ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh for elem, count in iterable.items(): 550ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh self[elem] = self_get(elem, 0) - count 551ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh else: 552ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh for elem in iterable: 553ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh self[elem] = self_get(elem, 0) - 1 554ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh if kwds: 555ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh self.subtract(kwds) 556ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 557ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def copy(self): 558ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 'Return a shallow copy.' 559ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return self.__class__(self) 560ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 561ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def __reduce__(self): 562ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return self.__class__, (dict(self),) 563ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 564ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def __delitem__(self, elem): 565ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 'Like dict.__delitem__() but does not raise KeyError for missing values.' 566ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh if elem in self: 567ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh super(Counter, self).__delitem__(elem) 568ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 569ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def __repr__(self): 570ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh if not self: 571ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return '%s()' % self.__class__.__name__ 572ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh items = ', '.join(map('%r: %r'.__mod__, self.most_common())) 573ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return '%s({%s})' % (self.__class__.__name__, items) 574ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 575ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh # Multiset-style mathematical operations discussed in: 576ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh # Knuth TAOCP Volume II section 4.6.3 exercise 19 577ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh # and at http://en.wikipedia.org/wiki/Multiset 578ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh # 579ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh # Outputs guaranteed to only include positive counts. 580ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh # 581ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh # To strip negative and zero counts, add-in an empty counter: 582ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh # c += Counter() 583ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 584ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def __add__(self, other): 585ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh '''Add counts from two counters. 586ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 587ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh >>> Counter('abbb') + Counter('bcc') 588ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh Counter({'b': 4, 'c': 2, 'a': 1}) 589ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 590ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh ''' 591ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh if not isinstance(other, Counter): 592ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return NotImplemented 593ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh result = Counter() 594ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh for elem, count in self.items(): 595ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh newcount = count + other[elem] 596ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh if newcount > 0: 597ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh result[elem] = newcount 598ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh for elem, count in other.items(): 599ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh if elem not in self and count > 0: 600ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh result[elem] = count 601ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return result 602ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 603ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def __sub__(self, other): 604ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh ''' Subtract count, but keep only results with positive counts. 605ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 606ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh >>> Counter('abbbc') - Counter('bccd') 607ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh Counter({'b': 2, 'a': 1}) 608ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 609ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh ''' 610ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh if not isinstance(other, Counter): 611ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return NotImplemented 612ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh result = Counter() 613ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh for elem, count in self.items(): 614ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh newcount = count - other[elem] 615ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh if newcount > 0: 616ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh result[elem] = newcount 617ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh for elem, count in other.items(): 618ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh if elem not in self and count < 0: 619ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh result[elem] = 0 - count 620ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return result 621ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 622ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def __or__(self, other): 623ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh '''Union is the maximum of value in either of the input counters. 624ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 625ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh >>> Counter('abbb') | Counter('bcc') 626ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh Counter({'b': 3, 'c': 2, 'a': 1}) 627ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 628ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh ''' 629ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh if not isinstance(other, Counter): 630ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return NotImplemented 631ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh result = Counter() 632ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh for elem, count in self.items(): 633ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh other_count = other[elem] 634ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh newcount = other_count if count < other_count else count 635ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh if newcount > 0: 636ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh result[elem] = newcount 637ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh for elem, count in other.items(): 638ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh if elem not in self and count > 0: 639ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh result[elem] = count 640ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return result 641ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 642ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def __and__(self, other): 643ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh ''' Intersection is the minimum of corresponding counts. 644ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 645ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh >>> Counter('abbb') & Counter('bcc') 646ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh Counter({'b': 1}) 647ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 648ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh ''' 649ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh if not isinstance(other, Counter): 650ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return NotImplemented 651ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh result = Counter() 652ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh for elem, count in self.items(): 653ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh other_count = other[elem] 654ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh newcount = count if count < other_count else other_count 655ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh if newcount > 0: 656ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh result[elem] = newcount 657ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return result 658ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 659ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 660ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsiehif __name__ == '__main__': 661ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh # verify that instances can be pickled 662ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh from cPickle import loads, dumps 663ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh Point = namedtuple('Point', 'x, y', True) 664ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh p = Point(x=10, y=20) 665ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh assert p == loads(dumps(p)) 666ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 667ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh # test and demonstrate ability to override methods 668ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh class Point(namedtuple('Point', 'x y')): 669ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh __slots__ = () 670ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh @property 671ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def hypot(self): 672ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return (self.x ** 2 + self.y ** 2) ** 0.5 673ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def __str__(self): 674ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return 'Point: x=%6.3f y=%6.3f hypot=%6.3f' % (self.x, self.y, self.hypot) 675ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 676ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh for p in Point(3, 4), Point(14, 5/7.): 677ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh print p 678ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 679ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh class Point(namedtuple('Point', 'x y')): 680ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 'Point class with optimized _make() and _replace() without error-checking' 681ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh __slots__ = () 682ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh _make = classmethod(tuple.__new__) 683ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def _replace(self, _map=map, **kwds): 684ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return self._make(_map(kwds.get, ('x', 'y'), self)) 685ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 686ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh print Point(11, 22)._replace(x=100) 687ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 688ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh Point3D = namedtuple('Point3D', Point._fields + ('z',)) 689ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh print Point3D.__doc__ 690ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 691ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh import doctest 692ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh TestResults = namedtuple('TestResults', 'failed attempted') 693ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh print TestResults(*doctest.testmod()) 694