cpython-lru_cache-weakref: Lib/collections.py annotate

annotate Lib/collections.py @ 79675:c0a2294de787 2.7

Issue #16199: Backport 2to3 typo fix from 3.2.

author	Chris Jerdonek <chris.jerdonek@gmail.com>
date	Thu, 11 Oct 2012 16:15:46 -0700
parents	272e7dcffd30
children	6fe34156782b

rev	line source
51962 4a4da968de2a Backport PEP 372: OrderedDict() Raymond Hettinger <python@rcn.com> parents: 51499 diff changeset	1 __all__ = ['Counter', 'deque', 'defaultdict', 'namedtuple', 'OrderedDict']
44330 4a6c06a77deb Add more namedtuple() test cases. Neaten the code and comments. Raymond Hettinger <python@rcn.com> parents: 44303 diff changeset	2 # For bootstrapping reasons, the collection ABCs are defined in _abcoll.py.
4a6c06a77deb Add more namedtuple() test cases. Neaten the code and comments. Raymond Hettinger <python@rcn.com> parents: 44303 diff changeset	3 # They should however be considered an integral part of collections.py.
4a6c06a77deb Add more namedtuple() test cases. Neaten the code and comments. Raymond Hettinger <python@rcn.com> parents: 44303 diff changeset	4 from _abcoll import *
4a6c06a77deb Add more namedtuple() test cases. Neaten the code and comments. Raymond Hettinger <python@rcn.com> parents: 44303 diff changeset	5 import _abcoll
4a6c06a77deb Add more namedtuple() test cases. Neaten the code and comments. Raymond Hettinger <python@rcn.com> parents: 44303 diff changeset	6 __all__ += _abcoll.__all__
40989 4087c0ec733b Prepare collections module for pure python code entries. Raymond Hettinger <python@rcn.com> parents: diff changeset	7
4087c0ec733b Prepare collections module for pure python code entries. Raymond Hettinger <python@rcn.com> parents: diff changeset	8 from _collections import deque, defaultdict
69537 ad89231ee568 Remove unused imports Raymond Hettinger <python@rcn.com> parents: 69536 diff changeset	9 from operator import itemgetter as _itemgetter
43579 046edaa1566a More docs, error messages, and tests Raymond Hettinger <python@rcn.com> parents: 43578 diff changeset	10 from keyword import iskeyword as _iskeyword
40992 b46c6d27625e Add collections.NamedTuple Raymond Hettinger <python@rcn.com> parents: 40989 diff changeset	11 import sys as _sys
50753 5934612d5070 Issue 1696199: Add collections.Counter(). Raymond Hettinger <python@rcn.com> parents: 49301 diff changeset	12 import heapq as _heapq
69537 ad89231ee568 Remove unused imports Raymond Hettinger <python@rcn.com> parents: 69536 diff changeset	13 from itertools import repeat as _repeat, chain as _chain, starmap as _starmap
ad89231ee568 Remove unused imports Raymond Hettinger <python@rcn.com> parents: 69536 diff changeset	14
64727 a60deecac242 Issue 9826: OrderedDict.__repr__ did not play well with self-referencing dicts. Raymond Hettinger <python@rcn.com> parents: 64661 diff changeset	15 try:
69531 fa277cbd66bb Cleanups to remove dependencies and add docstrings. Raymond Hettinger <python@rcn.com> parents: 69495 diff changeset	16 from thread import get_ident as _get_ident
66103 b4938c34b803 Backport part of r86217: Fix issues when building without threads Amaury Forgeot d'Arc <amauryfa@gmail.com> parents: 64727 diff changeset	17 except ImportError:
69531 fa277cbd66bb Cleanups to remove dependencies and add docstrings. Raymond Hettinger <python@rcn.com> parents: 69495 diff changeset	18 from dummy_thread import get_ident as _get_ident
64727 a60deecac242 Issue 9826: OrderedDict.__repr__ did not play well with self-referencing dicts. Raymond Hettinger <python@rcn.com> parents: 64661 diff changeset	19
51962 4a4da968de2a Backport PEP 372: OrderedDict() Raymond Hettinger <python@rcn.com> parents: 51499 diff changeset	20
4a4da968de2a Backport PEP 372: OrderedDict() Raymond Hettinger <python@rcn.com> parents: 51499 diff changeset	21 ################################################################################
4a4da968de2a Backport PEP 372: OrderedDict() Raymond Hettinger <python@rcn.com> parents: 51499 diff changeset	22 ### OrderedDict
4a4da968de2a Backport PEP 372: OrderedDict() Raymond Hettinger <python@rcn.com> parents: 51499 diff changeset	23 ################################################################################
4a4da968de2a Backport PEP 372: OrderedDict() Raymond Hettinger <python@rcn.com> parents: 51499 diff changeset	24
67253 a9aa5e4eb8c3 Raymond-Hettingers-MacBook-Pro:py27 raymondhettinger$ cat svn-commit.tmp Raymond Hettinger <python@rcn.com> parents: 66103 diff changeset	25 class OrderedDict(dict):
52229 290c7513e125 * Add implementation notes. Raymond Hettinger <python@rcn.com> parents: 52227 diff changeset	26 'Dictionary that remembers insertion order'
52277 119e3fc6cdf3 Add more comments. Improve variable names. Raymond Hettinger <python@rcn.com> parents: 52231 diff changeset	27 # An inherited dict maps keys to values.
52229 290c7513e125 * Add implementation notes. Raymond Hettinger <python@rcn.com> parents: 52227 diff changeset	28 # The inherited dict provides __getitem__, __len__, __contains__, and get.
290c7513e125 * Add implementation notes. Raymond Hettinger <python@rcn.com> parents: 52227 diff changeset	29 # The remaining methods are order-aware.
69539 45f26582250b Remove unused branch in the clear() method. Minor comment edits. Raymond Hettinger <python@rcn.com> parents: 69538 diff changeset	30 # Big-O running times for all methods are the same as regular dictionaries.
52277 119e3fc6cdf3 Add more comments. Improve variable names. Raymond Hettinger <python@rcn.com> parents: 52231 diff changeset	31
69539 45f26582250b Remove unused branch in the clear() method. Minor comment edits. Raymond Hettinger <python@rcn.com> parents: 69538 diff changeset	32 # The internal self.__map dict maps keys to links in a doubly linked list.
52277 119e3fc6cdf3 Add more comments. Improve variable names. Raymond Hettinger <python@rcn.com> parents: 52231 diff changeset	33 # The circular doubly linked list starts and ends with a sentinel element.
119e3fc6cdf3 Add more comments. Improve variable names. Raymond Hettinger <python@rcn.com> parents: 52231 diff changeset	34 # The sentinel element never gets deleted (this simplifies the algorithm).
59486 1f5da55ee7d7 Have links in OrderedDicts be native Python lists instead Raymond Hettinger <python@rcn.com> parents: 59485 diff changeset	35 # Each link is stored as a list of length three: [PREV, NEXT, KEY].
51962 4a4da968de2a Backport PEP 372: OrderedDict() Raymond Hettinger <python@rcn.com> parents: 51499 diff changeset	36
4a4da968de2a Backport PEP 372: OrderedDict() Raymond Hettinger <python@rcn.com> parents: 51499 diff changeset	37 def __init__(self, args, *kwds):
69540 c64c41974d1f Other minor clean-ups. Raymond Hettinger <python@rcn.com> parents: 69539 diff changeset	38 '''Initialize an ordered dictionary. The signature is the same as
c64c41974d1f Other minor clean-ups. Raymond Hettinger <python@rcn.com> parents: 69539 diff changeset	39 regular dictionaries, but keyword arguments are not recommended because
c64c41974d1f Other minor clean-ups. Raymond Hettinger <python@rcn.com> parents: 69539 diff changeset	40 their insertion order is arbitrary.
52982 df0ed9eb79c3 Add docstrings. Raymond Hettinger <python@rcn.com> parents: 52800 diff changeset	41
df0ed9eb79c3 Add docstrings. Raymond Hettinger <python@rcn.com> parents: 52800 diff changeset	42 '''
51962 4a4da968de2a Backport PEP 372: OrderedDict() Raymond Hettinger <python@rcn.com> parents: 51499 diff changeset	43 if len(args) > 1:
4a4da968de2a Backport PEP 372: OrderedDict() Raymond Hettinger <python@rcn.com> parents: 51499 diff changeset	44 raise TypeError('expected at most 1 arguments, got %d' % len(args))
51973 982502826f78 Make the underlying data structure more private. Raymond Hettinger <python@rcn.com> parents: 51963 diff changeset	45 try:
52277 119e3fc6cdf3 Add more comments. Improve variable names. Raymond Hettinger <python@rcn.com> parents: 52231 diff changeset	46 self.__root
51973 982502826f78 Make the underlying data structure more private. Raymond Hettinger <python@rcn.com> parents: 51963 diff changeset	47 except AttributeError:
69535 a3d5149bdd70 Minor code simplification. Raymond Hettinger <python@rcn.com> parents: 69531 diff changeset	48 self.__root = root = [] # sentinel node
a3d5149bdd70 Minor code simplification. Raymond Hettinger <python@rcn.com> parents: 69531 diff changeset	49 root[:] = [root, root, None]
52336 f5d670fcdbe9 Separate initialization from clearing. Raymond Hettinger <python@rcn.com> parents: 52286 diff changeset	50 self.__map = {}
67253 a9aa5e4eb8c3 Raymond-Hettingers-MacBook-Pro:py27 raymondhettinger$ cat svn-commit.tmp Raymond Hettinger <python@rcn.com> parents: 66103 diff changeset	51 self.__update(args, *kwds)
51962 4a4da968de2a Backport PEP 372: OrderedDict() Raymond Hettinger <python@rcn.com> parents: 51499 diff changeset	52
60215 5ebca6228903 Factor-out constant expressions Raymond Hettinger <python@rcn.com> parents: 60214 diff changeset	53 def __setitem__(self, key, value, PREV=0, NEXT=1, dict_setitem=dict.__setitem__):
52982 df0ed9eb79c3 Add docstrings. Raymond Hettinger <python@rcn.com> parents: 52800 diff changeset	54 'od.__setitem__(i, y) <==> od[i]=y'
69539 45f26582250b Remove unused branch in the clear() method. Minor comment edits. Raymond Hettinger <python@rcn.com> parents: 69538 diff changeset	55 # Setting a new item creates a new link at the end of the linked list,
45f26582250b Remove unused branch in the clear() method. Minor comment edits. Raymond Hettinger <python@rcn.com> parents: 69538 diff changeset	56 # and the inherited dictionary is updated with the new key/value pair.
51962 4a4da968de2a Backport PEP 372: OrderedDict() Raymond Hettinger <python@rcn.com> parents: 51499 diff changeset	57 if key not in self:
52277 119e3fc6cdf3 Add more comments. Improve variable names. Raymond Hettinger <python@rcn.com> parents: 52231 diff changeset	58 root = self.__root
59486 1f5da55ee7d7 Have links in OrderedDicts be native Python lists instead Raymond Hettinger <python@rcn.com> parents: 59485 diff changeset	59 last = root[PREV]
1f5da55ee7d7 Have links in OrderedDicts be native Python lists instead Raymond Hettinger <python@rcn.com> parents: 59485 diff changeset	60 last[NEXT] = root[PREV] = self.__map[key] = [last, root, key]
60215 5ebca6228903 Factor-out constant expressions Raymond Hettinger <python@rcn.com> parents: 60214 diff changeset	61 dict_setitem(self, key, value)
51962 4a4da968de2a Backport PEP 372: OrderedDict() Raymond Hettinger <python@rcn.com> parents: 51499 diff changeset	62
60215 5ebca6228903 Factor-out constant expressions Raymond Hettinger <python@rcn.com> parents: 60214 diff changeset	63 def __delitem__(self, key, PREV=0, NEXT=1, dict_delitem=dict.__delitem__):
52982 df0ed9eb79c3 Add docstrings. Raymond Hettinger <python@rcn.com> parents: 52800 diff changeset	64 'od.__delitem__(y) <==> del od[y]'
69539 45f26582250b Remove unused branch in the clear() method. Minor comment edits. Raymond Hettinger <python@rcn.com> parents: 69538 diff changeset	65 # Deleting an existing item uses self.__map to find the link which gets
45f26582250b Remove unused branch in the clear() method. Minor comment edits. Raymond Hettinger <python@rcn.com> parents: 69538 diff changeset	66 # removed by updating the links in the predecessor and successor nodes.
60215 5ebca6228903 Factor-out constant expressions Raymond Hettinger <python@rcn.com> parents: 60214 diff changeset	67 dict_delitem(self, key)
69536 d6729016eedc Minor code simplification. Raymond Hettinger <python@rcn.com> parents: 69535 diff changeset	68 link_prev, link_next, key = self.__map.pop(key)
60201 4ed04a39c0a9 Clear cyclical references in list based OrderedDict. Raymond Hettinger <python@rcn.com> parents: 59488 diff changeset	69 link_prev[NEXT] = link_next
4ed04a39c0a9 Clear cyclical references in list based OrderedDict. Raymond Hettinger <python@rcn.com> parents: 59488 diff changeset	70 link_next[PREV] = link_prev
51962 4a4da968de2a Backport PEP 372: OrderedDict() Raymond Hettinger <python@rcn.com> parents: 51499 diff changeset	71
69540 c64c41974d1f Other minor clean-ups. Raymond Hettinger <python@rcn.com> parents: 69539 diff changeset	72 def __iter__(self):
52982 df0ed9eb79c3 Add docstrings. Raymond Hettinger <python@rcn.com> parents: 52800 diff changeset	73 'od.__iter__() <==> iter(od)'
52277 119e3fc6cdf3 Add more comments. Improve variable names. Raymond Hettinger <python@rcn.com> parents: 52231 diff changeset	74 # Traverse the linked list in order.
69540 c64c41974d1f Other minor clean-ups. Raymond Hettinger <python@rcn.com> parents: 69539 diff changeset	75 NEXT, KEY = 1, 2
52277 119e3fc6cdf3 Add more comments. Improve variable names. Raymond Hettinger <python@rcn.com> parents: 52231 diff changeset	76 root = self.__root
59486 1f5da55ee7d7 Have links in OrderedDicts be native Python lists instead Raymond Hettinger <python@rcn.com> parents: 59485 diff changeset	77 curr = root[NEXT]
52277 119e3fc6cdf3 Add more comments. Improve variable names. Raymond Hettinger <python@rcn.com> parents: 52231 diff changeset	78 while curr is not root:
59486 1f5da55ee7d7 Have links in OrderedDicts be native Python lists instead Raymond Hettinger <python@rcn.com> parents: 59485 diff changeset	79 yield curr[KEY]
1f5da55ee7d7 Have links in OrderedDicts be native Python lists instead Raymond Hettinger <python@rcn.com> parents: 59485 diff changeset	80 curr = curr[NEXT]
51962 4a4da968de2a Backport PEP 372: OrderedDict() Raymond Hettinger <python@rcn.com> parents: 51499 diff changeset	81
69540 c64c41974d1f Other minor clean-ups. Raymond Hettinger <python@rcn.com> parents: 69539 diff changeset	82 def __reversed__(self):
52982 df0ed9eb79c3 Add docstrings. Raymond Hettinger <python@rcn.com> parents: 52800 diff changeset	83 'od.__reversed__() <==> reversed(od)'
52277 119e3fc6cdf3 Add more comments. Improve variable names. Raymond Hettinger <python@rcn.com> parents: 52231 diff changeset	84 # Traverse the linked list in reverse order.
69540 c64c41974d1f Other minor clean-ups. Raymond Hettinger <python@rcn.com> parents: 69539 diff changeset	85 PREV, KEY = 0, 2
52277 119e3fc6cdf3 Add more comments. Improve variable names. Raymond Hettinger <python@rcn.com> parents: 52231 diff changeset	86 root = self.__root
59486 1f5da55ee7d7 Have links in OrderedDicts be native Python lists instead Raymond Hettinger <python@rcn.com> parents: 59485 diff changeset	87 curr = root[PREV]
52277 119e3fc6cdf3 Add more comments. Improve variable names. Raymond Hettinger <python@rcn.com> parents: 52231 diff changeset	88 while curr is not root:
59486 1f5da55ee7d7 Have links in OrderedDicts be native Python lists instead Raymond Hettinger <python@rcn.com> parents: 59485 diff changeset	89 yield curr[KEY]
1f5da55ee7d7 Have links in OrderedDicts be native Python lists instead Raymond Hettinger <python@rcn.com> parents: 59485 diff changeset	90 curr = curr[PREV]
51962 4a4da968de2a Backport PEP 372: OrderedDict() Raymond Hettinger <python@rcn.com> parents: 51499 diff changeset	91
60201 4ed04a39c0a9 Clear cyclical references in list based OrderedDict. Raymond Hettinger <python@rcn.com> parents: 59488 diff changeset	92 def clear(self):
4ed04a39c0a9 Clear cyclical references in list based OrderedDict. Raymond Hettinger <python@rcn.com> parents: 59488 diff changeset	93 'od.clear() -> None. Remove all items from od.'
69539 45f26582250b Remove unused branch in the clear() method. Minor comment edits. Raymond Hettinger <python@rcn.com> parents: 69538 diff changeset	94 for node in self.__map.itervalues():
45f26582250b Remove unused branch in the clear() method. Minor comment edits. Raymond Hettinger <python@rcn.com> parents: 69538 diff changeset	95 del node[:]
45f26582250b Remove unused branch in the clear() method. Minor comment edits. Raymond Hettinger <python@rcn.com> parents: 69538 diff changeset	96 root = self.__root
45f26582250b Remove unused branch in the clear() method. Minor comment edits. Raymond Hettinger <python@rcn.com> parents: 69538 diff changeset	97 root[:] = [root, root, None]
45f26582250b Remove unused branch in the clear() method. Minor comment edits. Raymond Hettinger <python@rcn.com> parents: 69538 diff changeset	98 self.__map.clear()
60214 fdd0137432f8 Improve clear() method. Keeps key/value refcnts >= 1 until final dict.clear() so that decrefs to zero won't trigger arbitrary code . Also runs a bit faster. Raymond Hettinger <python@rcn.com> parents: 60201 diff changeset	99 dict.clear(self)
60201 4ed04a39c0a9 Clear cyclical references in list based OrderedDict. Raymond Hettinger <python@rcn.com> parents: 59488 diff changeset	100
69531 fa277cbd66bb Cleanups to remove dependencies and add docstrings. Raymond Hettinger <python@rcn.com> parents: 69495 diff changeset	101 # -- the following methods do not depend on the internal structure --
fa277cbd66bb Cleanups to remove dependencies and add docstrings. Raymond Hettinger <python@rcn.com> parents: 69495 diff changeset	102
fa277cbd66bb Cleanups to remove dependencies and add docstrings. Raymond Hettinger <python@rcn.com> parents: 69495 diff changeset	103 def keys(self):
fa277cbd66bb Cleanups to remove dependencies and add docstrings. Raymond Hettinger <python@rcn.com> parents: 69495 diff changeset	104 'od.keys() -> list of keys in od'
fa277cbd66bb Cleanups to remove dependencies and add docstrings. Raymond Hettinger <python@rcn.com> parents: 69495 diff changeset	105 return list(self)
fa277cbd66bb Cleanups to remove dependencies and add docstrings. Raymond Hettinger <python@rcn.com> parents: 69495 diff changeset	106
fa277cbd66bb Cleanups to remove dependencies and add docstrings. Raymond Hettinger <python@rcn.com> parents: 69495 diff changeset	107 def values(self):
fa277cbd66bb Cleanups to remove dependencies and add docstrings. Raymond Hettinger <python@rcn.com> parents: 69495 diff changeset	108 'od.values() -> list of values in od'
fa277cbd66bb Cleanups to remove dependencies and add docstrings. Raymond Hettinger <python@rcn.com> parents: 69495 diff changeset	109 return [self[key] for key in self]
fa277cbd66bb Cleanups to remove dependencies and add docstrings. Raymond Hettinger <python@rcn.com> parents: 69495 diff changeset	110
fa277cbd66bb Cleanups to remove dependencies and add docstrings. Raymond Hettinger <python@rcn.com> parents: 69495 diff changeset	111 def items(self):
fa277cbd66bb Cleanups to remove dependencies and add docstrings. Raymond Hettinger <python@rcn.com> parents: 69495 diff changeset	112 'od.items() -> list of (key, value) pairs in od'
fa277cbd66bb Cleanups to remove dependencies and add docstrings. Raymond Hettinger <python@rcn.com> parents: 69495 diff changeset	113 return [(key, self[key]) for key in self]
fa277cbd66bb Cleanups to remove dependencies and add docstrings. Raymond Hettinger <python@rcn.com> parents: 69495 diff changeset	114
fa277cbd66bb Cleanups to remove dependencies and add docstrings. Raymond Hettinger <python@rcn.com> parents: 69495 diff changeset	115 def iterkeys(self):
fa277cbd66bb Cleanups to remove dependencies and add docstrings. Raymond Hettinger <python@rcn.com> parents: 69495 diff changeset	116 'od.iterkeys() -> an iterator over the keys in od'
fa277cbd66bb Cleanups to remove dependencies and add docstrings. Raymond Hettinger <python@rcn.com> parents: 69495 diff changeset	117 return iter(self)
fa277cbd66bb Cleanups to remove dependencies and add docstrings. Raymond Hettinger <python@rcn.com> parents: 69495 diff changeset	118
fa277cbd66bb Cleanups to remove dependencies and add docstrings. Raymond Hettinger <python@rcn.com> parents: 69495 diff changeset	119 def itervalues(self):
fa277cbd66bb Cleanups to remove dependencies and add docstrings. Raymond Hettinger <python@rcn.com> parents: 69495 diff changeset	120 'od.itervalues -> an iterator over the values in od'
fa277cbd66bb Cleanups to remove dependencies and add docstrings. Raymond Hettinger <python@rcn.com> parents: 69495 diff changeset	121 for k in self:
fa277cbd66bb Cleanups to remove dependencies and add docstrings. Raymond Hettinger <python@rcn.com> parents: 69495 diff changeset	122 yield self[k]
fa277cbd66bb Cleanups to remove dependencies and add docstrings. Raymond Hettinger <python@rcn.com> parents: 69495 diff changeset	123
fa277cbd66bb Cleanups to remove dependencies and add docstrings. Raymond Hettinger <python@rcn.com> parents: 69495 diff changeset	124 def iteritems(self):
69540 c64c41974d1f Other minor clean-ups. Raymond Hettinger <python@rcn.com> parents: 69539 diff changeset	125 'od.iteritems -> an iterator over the (key, value) pairs in od'
69531 fa277cbd66bb Cleanups to remove dependencies and add docstrings. Raymond Hettinger <python@rcn.com> parents: 69495 diff changeset	126 for k in self:
fa277cbd66bb Cleanups to remove dependencies and add docstrings. Raymond Hettinger <python@rcn.com> parents: 69495 diff changeset	127 yield (k, self[k])
fa277cbd66bb Cleanups to remove dependencies and add docstrings. Raymond Hettinger <python@rcn.com> parents: 69495 diff changeset	128
fa277cbd66bb Cleanups to remove dependencies and add docstrings. Raymond Hettinger <python@rcn.com> parents: 69495 diff changeset	129 update = MutableMapping.update
fa277cbd66bb Cleanups to remove dependencies and add docstrings. Raymond Hettinger <python@rcn.com> parents: 69495 diff changeset	130
69539 45f26582250b Remove unused branch in the clear() method. Minor comment edits. Raymond Hettinger <python@rcn.com> parents: 69538 diff changeset	131 __update = update # let subclasses override update without breaking __init__
51962 4a4da968de2a Backport PEP 372: OrderedDict() Raymond Hettinger <python@rcn.com> parents: 51499 diff changeset	132
67253 a9aa5e4eb8c3 Raymond-Hettingers-MacBook-Pro:py27 raymondhettinger$ cat svn-commit.tmp Raymond Hettinger <python@rcn.com> parents: 66103 diff changeset	133 __marker = object()
a9aa5e4eb8c3 Raymond-Hettingers-MacBook-Pro:py27 raymondhettinger$ cat svn-commit.tmp Raymond Hettinger <python@rcn.com> parents: 66103 diff changeset	134
a9aa5e4eb8c3 Raymond-Hettingers-MacBook-Pro:py27 raymondhettinger$ cat svn-commit.tmp Raymond Hettinger <python@rcn.com> parents: 66103 diff changeset	135 def pop(self, key, default=__marker):
69540 c64c41974d1f Other minor clean-ups. Raymond Hettinger <python@rcn.com> parents: 69539 diff changeset	136 '''od.pop(k[,d]) -> v, remove specified key and return the corresponding
c64c41974d1f Other minor clean-ups. Raymond Hettinger <python@rcn.com> parents: 69539 diff changeset	137 value. If key is not found, d is returned if given, otherwise KeyError
c64c41974d1f Other minor clean-ups. Raymond Hettinger <python@rcn.com> parents: 69539 diff changeset	138 is raised.
c64c41974d1f Other minor clean-ups. Raymond Hettinger <python@rcn.com> parents: 69539 diff changeset	139
c64c41974d1f Other minor clean-ups. Raymond Hettinger <python@rcn.com> parents: 69539 diff changeset	140 '''
67253 a9aa5e4eb8c3 Raymond-Hettingers-MacBook-Pro:py27 raymondhettinger$ cat svn-commit.tmp Raymond Hettinger <python@rcn.com> parents: 66103 diff changeset	141 if key in self:
a9aa5e4eb8c3 Raymond-Hettingers-MacBook-Pro:py27 raymondhettinger$ cat svn-commit.tmp Raymond Hettinger <python@rcn.com> parents: 66103 diff changeset	142 result = self[key]
a9aa5e4eb8c3 Raymond-Hettingers-MacBook-Pro:py27 raymondhettinger$ cat svn-commit.tmp Raymond Hettinger <python@rcn.com> parents: 66103 diff changeset	143 del self[key]
a9aa5e4eb8c3 Raymond-Hettingers-MacBook-Pro:py27 raymondhettinger$ cat svn-commit.tmp Raymond Hettinger <python@rcn.com> parents: 66103 diff changeset	144 return result
a9aa5e4eb8c3 Raymond-Hettingers-MacBook-Pro:py27 raymondhettinger$ cat svn-commit.tmp Raymond Hettinger <python@rcn.com> parents: 66103 diff changeset	145 if default is self.__marker:
a9aa5e4eb8c3 Raymond-Hettingers-MacBook-Pro:py27 raymondhettinger$ cat svn-commit.tmp Raymond Hettinger <python@rcn.com> parents: 66103 diff changeset	146 raise KeyError(key)
a9aa5e4eb8c3 Raymond-Hettingers-MacBook-Pro:py27 raymondhettinger$ cat svn-commit.tmp Raymond Hettinger <python@rcn.com> parents: 66103 diff changeset	147 return default
a9aa5e4eb8c3 Raymond-Hettingers-MacBook-Pro:py27 raymondhettinger$ cat svn-commit.tmp Raymond Hettinger <python@rcn.com> parents: 66103 diff changeset	148
a9aa5e4eb8c3 Raymond-Hettingers-MacBook-Pro:py27 raymondhettinger$ cat svn-commit.tmp Raymond Hettinger <python@rcn.com> parents: 66103 diff changeset	149 def setdefault(self, key, default=None):
a9aa5e4eb8c3 Raymond-Hettingers-MacBook-Pro:py27 raymondhettinger$ cat svn-commit.tmp Raymond Hettinger <python@rcn.com> parents: 66103 diff changeset	150 'od.setdefault(k[,d]) -> od.get(k,d), also set od[k]=d if k not in od'
a9aa5e4eb8c3 Raymond-Hettingers-MacBook-Pro:py27 raymondhettinger$ cat svn-commit.tmp Raymond Hettinger <python@rcn.com> parents: 66103 diff changeset	151 if key in self:
a9aa5e4eb8c3 Raymond-Hettingers-MacBook-Pro:py27 raymondhettinger$ cat svn-commit.tmp Raymond Hettinger <python@rcn.com> parents: 66103 diff changeset	152 return self[key]
a9aa5e4eb8c3 Raymond-Hettingers-MacBook-Pro:py27 raymondhettinger$ cat svn-commit.tmp Raymond Hettinger <python@rcn.com> parents: 66103 diff changeset	153 self[key] = default
a9aa5e4eb8c3 Raymond-Hettingers-MacBook-Pro:py27 raymondhettinger$ cat svn-commit.tmp Raymond Hettinger <python@rcn.com> parents: 66103 diff changeset	154 return default
a9aa5e4eb8c3 Raymond-Hettingers-MacBook-Pro:py27 raymondhettinger$ cat svn-commit.tmp Raymond Hettinger <python@rcn.com> parents: 66103 diff changeset	155
52229 290c7513e125 * Add implementation notes. Raymond Hettinger <python@rcn.com> parents: 52227 diff changeset	156 def popitem(self, last=True):
52982 df0ed9eb79c3 Add docstrings. Raymond Hettinger <python@rcn.com> parents: 52800 diff changeset	157 '''od.popitem() -> (k, v), return and remove a (key, value) pair.
df0ed9eb79c3 Add docstrings. Raymond Hettinger <python@rcn.com> parents: 52800 diff changeset	158 Pairs are returned in LIFO order if last is true or FIFO order if false.
df0ed9eb79c3 Add docstrings. Raymond Hettinger <python@rcn.com> parents: 52800 diff changeset	159
df0ed9eb79c3 Add docstrings. Raymond Hettinger <python@rcn.com> parents: 52800 diff changeset	160 '''
52229 290c7513e125 * Add implementation notes. Raymond Hettinger <python@rcn.com> parents: 52227 diff changeset	161 if not self:
290c7513e125 * Add implementation notes. Raymond Hettinger <python@rcn.com> parents: 52227 diff changeset	162 raise KeyError('dictionary is empty')
52985 7b8962f65918 Minor factoring. Raymond Hettinger <python@rcn.com> parents: 52982 diff changeset	163 key = next(reversed(self) if last else iter(self))
52229 290c7513e125 * Add implementation notes. Raymond Hettinger <python@rcn.com> parents: 52227 diff changeset	164 value = self.pop(key)
290c7513e125 * Add implementation notes. Raymond Hettinger <python@rcn.com> parents: 52227 diff changeset	165 return key, value
290c7513e125 * Add implementation notes. Raymond Hettinger <python@rcn.com> parents: 52227 diff changeset	166
69531 fa277cbd66bb Cleanups to remove dependencies and add docstrings. Raymond Hettinger <python@rcn.com> parents: 69495 diff changeset	167 def __repr__(self, _repr_running={}):
52982 df0ed9eb79c3 Add docstrings. Raymond Hettinger <python@rcn.com> parents: 52800 diff changeset	168 'od.__repr__() <==> repr(od)'
69531 fa277cbd66bb Cleanups to remove dependencies and add docstrings. Raymond Hettinger <python@rcn.com> parents: 69495 diff changeset	169 call_key = id(self), _get_ident()
fa277cbd66bb Cleanups to remove dependencies and add docstrings. Raymond Hettinger <python@rcn.com> parents: 69495 diff changeset	170 if call_key in _repr_running:
fa277cbd66bb Cleanups to remove dependencies and add docstrings. Raymond Hettinger <python@rcn.com> parents: 69495 diff changeset	171 return '...'
fa277cbd66bb Cleanups to remove dependencies and add docstrings. Raymond Hettinger <python@rcn.com> parents: 69495 diff changeset	172 _repr_running[call_key] = 1
fa277cbd66bb Cleanups to remove dependencies and add docstrings. Raymond Hettinger <python@rcn.com> parents: 69495 diff changeset	173 try:
fa277cbd66bb Cleanups to remove dependencies and add docstrings. Raymond Hettinger <python@rcn.com> parents: 69495 diff changeset	174 if not self:
fa277cbd66bb Cleanups to remove dependencies and add docstrings. Raymond Hettinger <python@rcn.com> parents: 69495 diff changeset	175 return '%s()' % (self.__class__.__name__,)
fa277cbd66bb Cleanups to remove dependencies and add docstrings. Raymond Hettinger <python@rcn.com> parents: 69495 diff changeset	176 return '%s(%r)' % (self.__class__.__name__, self.items())
fa277cbd66bb Cleanups to remove dependencies and add docstrings. Raymond Hettinger <python@rcn.com> parents: 69495 diff changeset	177 finally:
fa277cbd66bb Cleanups to remove dependencies and add docstrings. Raymond Hettinger <python@rcn.com> parents: 69495 diff changeset	178 del _repr_running[call_key]
51962 4a4da968de2a Backport PEP 372: OrderedDict() Raymond Hettinger <python@rcn.com> parents: 51499 diff changeset	179
69495 4a1530e9df7f Minor text rearrangement. Raymond Hettinger <python@rcn.com> parents: 69459 diff changeset	180 def __reduce__(self):
4a1530e9df7f Minor text rearrangement. Raymond Hettinger <python@rcn.com> parents: 69459 diff changeset	181 'Return state information for pickling'
4a1530e9df7f Minor text rearrangement. Raymond Hettinger <python@rcn.com> parents: 69459 diff changeset	182 items = [[k, self[k]] for k in self]
4a1530e9df7f Minor text rearrangement. Raymond Hettinger <python@rcn.com> parents: 69459 diff changeset	183 inst_dict = vars(self).copy()
4a1530e9df7f Minor text rearrangement. Raymond Hettinger <python@rcn.com> parents: 69459 diff changeset	184 for k in vars(OrderedDict()):
4a1530e9df7f Minor text rearrangement. Raymond Hettinger <python@rcn.com> parents: 69459 diff changeset	185 inst_dict.pop(k, None)
4a1530e9df7f Minor text rearrangement. Raymond Hettinger <python@rcn.com> parents: 69459 diff changeset	186 if inst_dict:
4a1530e9df7f Minor text rearrangement. Raymond Hettinger <python@rcn.com> parents: 69459 diff changeset	187 return (self.__class__, (items,), inst_dict)
4a1530e9df7f Minor text rearrangement. Raymond Hettinger <python@rcn.com> parents: 69459 diff changeset	188 return self.__class__, (items,)
4a1530e9df7f Minor text rearrangement. Raymond Hettinger <python@rcn.com> parents: 69459 diff changeset	189
51962 4a4da968de2a Backport PEP 372: OrderedDict() Raymond Hettinger <python@rcn.com> parents: 51499 diff changeset	190 def copy(self):
52982 df0ed9eb79c3 Add docstrings. Raymond Hettinger <python@rcn.com> parents: 52800 diff changeset	191 'od.copy() -> a shallow copy of od'
51962 4a4da968de2a Backport PEP 372: OrderedDict() Raymond Hettinger <python@rcn.com> parents: 51499 diff changeset	192 return self.__class__(self)
4a4da968de2a Backport PEP 372: OrderedDict() Raymond Hettinger <python@rcn.com> parents: 51499 diff changeset	193
4a4da968de2a Backport PEP 372: OrderedDict() Raymond Hettinger <python@rcn.com> parents: 51499 diff changeset	194 @classmethod
4a4da968de2a Backport PEP 372: OrderedDict() Raymond Hettinger <python@rcn.com> parents: 51499 diff changeset	195 def fromkeys(cls, iterable, value=None):
69540 c64c41974d1f Other minor clean-ups. Raymond Hettinger <python@rcn.com> parents: 69539 diff changeset	196 '''OD.fromkeys(S[, v]) -> New ordered dictionary with keys from S.
c64c41974d1f Other minor clean-ups. Raymond Hettinger <python@rcn.com> parents: 69539 diff changeset	197 If not specified, the value defaults to None.
52982 df0ed9eb79c3 Add docstrings. Raymond Hettinger <python@rcn.com> parents: 52800 diff changeset	198
df0ed9eb79c3 Add docstrings. Raymond Hettinger <python@rcn.com> parents: 52800 diff changeset	199 '''
69539 45f26582250b Remove unused branch in the clear() method. Minor comment edits. Raymond Hettinger <python@rcn.com> parents: 69538 diff changeset	200 self = cls()
51962 4a4da968de2a Backport PEP 372: OrderedDict() Raymond Hettinger <python@rcn.com> parents: 51499 diff changeset	201 for key in iterable:
69539 45f26582250b Remove unused branch in the clear() method. Minor comment edits. Raymond Hettinger <python@rcn.com> parents: 69538 diff changeset	202 self[key] = value
45f26582250b Remove unused branch in the clear() method. Minor comment edits. Raymond Hettinger <python@rcn.com> parents: 69538 diff changeset	203 return self
51962 4a4da968de2a Backport PEP 372: OrderedDict() Raymond Hettinger <python@rcn.com> parents: 51499 diff changeset	204
4a4da968de2a Backport PEP 372: OrderedDict() Raymond Hettinger <python@rcn.com> parents: 51499 diff changeset	205 def __eq__(self, other):
52982 df0ed9eb79c3 Add docstrings. Raymond Hettinger <python@rcn.com> parents: 52800 diff changeset	206 '''od.__eq__(y) <==> od==y. Comparison to another OD is order-sensitive
df0ed9eb79c3 Add docstrings. Raymond Hettinger <python@rcn.com> parents: 52800 diff changeset	207 while comparison to a regular mapping is order-insensitive.
df0ed9eb79c3 Add docstrings. Raymond Hettinger <python@rcn.com> parents: 52800 diff changeset	208
df0ed9eb79c3 Add docstrings. Raymond Hettinger <python@rcn.com> parents: 52800 diff changeset	209 '''
51962 4a4da968de2a Backport PEP 372: OrderedDict() Raymond Hettinger <python@rcn.com> parents: 51499 diff changeset	210 if isinstance(other, OrderedDict):
69531 fa277cbd66bb Cleanups to remove dependencies and add docstrings. Raymond Hettinger <python@rcn.com> parents: 69495 diff changeset	211 return len(self)==len(other) and self.items() == other.items()
51962 4a4da968de2a Backport PEP 372: OrderedDict() Raymond Hettinger <python@rcn.com> parents: 51499 diff changeset	212 return dict.__eq__(self, other)
4a4da968de2a Backport PEP 372: OrderedDict() Raymond Hettinger <python@rcn.com> parents: 51499 diff changeset	213
69531 fa277cbd66bb Cleanups to remove dependencies and add docstrings. Raymond Hettinger <python@rcn.com> parents: 69495 diff changeset	214 def __ne__(self, other):
fa277cbd66bb Cleanups to remove dependencies and add docstrings. Raymond Hettinger <python@rcn.com> parents: 69495 diff changeset	215 'od.__ne__(y) <==> od!=y'
fa277cbd66bb Cleanups to remove dependencies and add docstrings. Raymond Hettinger <python@rcn.com> parents: 69495 diff changeset	216 return not self == other
fa277cbd66bb Cleanups to remove dependencies and add docstrings. Raymond Hettinger <python@rcn.com> parents: 69495 diff changeset	217
69536 d6729016eedc Minor code simplification. Raymond Hettinger <python@rcn.com> parents: 69535 diff changeset	218 # -- the following methods support python 3.x style dictionary views --
d6729016eedc Minor code simplification. Raymond Hettinger <python@rcn.com> parents: 69535 diff changeset	219
d6729016eedc Minor code simplification. Raymond Hettinger <python@rcn.com> parents: 69535 diff changeset	220 def viewkeys(self):
d6729016eedc Minor code simplification. Raymond Hettinger <python@rcn.com> parents: 69535 diff changeset	221 "od.viewkeys() -> a set-like object providing a view on od's keys"
d6729016eedc Minor code simplification. Raymond Hettinger <python@rcn.com> parents: 69535 diff changeset	222 return KeysView(self)
d6729016eedc Minor code simplification. Raymond Hettinger <python@rcn.com> parents: 69535 diff changeset	223
d6729016eedc Minor code simplification. Raymond Hettinger <python@rcn.com> parents: 69535 diff changeset	224 def viewvalues(self):
d6729016eedc Minor code simplification. Raymond Hettinger <python@rcn.com> parents: 69535 diff changeset	225 "od.viewvalues() -> an object providing a view on od's values"
d6729016eedc Minor code simplification. Raymond Hettinger <python@rcn.com> parents: 69535 diff changeset	226 return ValuesView(self)
d6729016eedc Minor code simplification. Raymond Hettinger <python@rcn.com> parents: 69535 diff changeset	227
d6729016eedc Minor code simplification. Raymond Hettinger <python@rcn.com> parents: 69535 diff changeset	228 def viewitems(self):
d6729016eedc Minor code simplification. Raymond Hettinger <python@rcn.com> parents: 69535 diff changeset	229 "od.viewitems() -> a set-like object providing a view on od's items"
d6729016eedc Minor code simplification. Raymond Hettinger <python@rcn.com> parents: 69535 diff changeset	230 return ItemsView(self)
d6729016eedc Minor code simplification. Raymond Hettinger <python@rcn.com> parents: 69535 diff changeset	231
50753 5934612d5070 Issue 1696199: Add collections.Counter(). Raymond Hettinger <python@rcn.com> parents: 49301 diff changeset	232
50924 8d66b82a10a3 Make merging easier by formattng comment blocks the same in Py3.1 Raymond Hettinger <python@rcn.com> parents: 50923 diff changeset	233 ################################################################################
8d66b82a10a3 Make merging easier by formattng comment blocks the same in Py3.1 Raymond Hettinger <python@rcn.com> parents: 50923 diff changeset	234 ### namedtuple
8d66b82a10a3 Make merging easier by formattng comment blocks the same in Py3.1 Raymond Hettinger <python@rcn.com> parents: 50923 diff changeset	235 ################################################################################
40992 b46c6d27625e Add collections.NamedTuple Raymond Hettinger <python@rcn.com> parents: 40989 diff changeset	236
77389 aca1a271c4fc Code cleanups Raymond Hettinger <python@rcn.com> parents: 70608 diff changeset	237 _class_template = '''\
aca1a271c4fc Code cleanups Raymond Hettinger <python@rcn.com> parents: 70608 diff changeset	238 class {typename}(tuple):
aca1a271c4fc Code cleanups Raymond Hettinger <python@rcn.com> parents: 70608 diff changeset	239 '{typename}({arg_list})'
aca1a271c4fc Code cleanups Raymond Hettinger <python@rcn.com> parents: 70608 diff changeset	240
aca1a271c4fc Code cleanups Raymond Hettinger <python@rcn.com> parents: 70608 diff changeset	241 __slots__ = ()
aca1a271c4fc Code cleanups Raymond Hettinger <python@rcn.com> parents: 70608 diff changeset	242
aca1a271c4fc Code cleanups Raymond Hettinger <python@rcn.com> parents: 70608 diff changeset	243 _fields = {field_names!r}
aca1a271c4fc Code cleanups Raymond Hettinger <python@rcn.com> parents: 70608 diff changeset	244
aca1a271c4fc Code cleanups Raymond Hettinger <python@rcn.com> parents: 70608 diff changeset	245 def __new__(_cls, {arg_list}):
aca1a271c4fc Code cleanups Raymond Hettinger <python@rcn.com> parents: 70608 diff changeset	246 'Create new instance of {typename}({arg_list})'
aca1a271c4fc Code cleanups Raymond Hettinger <python@rcn.com> parents: 70608 diff changeset	247 return _tuple.__new__(_cls, ({arg_list}))
aca1a271c4fc Code cleanups Raymond Hettinger <python@rcn.com> parents: 70608 diff changeset	248
aca1a271c4fc Code cleanups Raymond Hettinger <python@rcn.com> parents: 70608 diff changeset	249 @classmethod
aca1a271c4fc Code cleanups Raymond Hettinger <python@rcn.com> parents: 70608 diff changeset	250 def _make(cls, iterable, new=tuple.__new__, len=len):
aca1a271c4fc Code cleanups Raymond Hettinger <python@rcn.com> parents: 70608 diff changeset	251 'Make a new {typename} object from a sequence or iterable'
aca1a271c4fc Code cleanups Raymond Hettinger <python@rcn.com> parents: 70608 diff changeset	252 result = new(cls, iterable)
aca1a271c4fc Code cleanups Raymond Hettinger <python@rcn.com> parents: 70608 diff changeset	253 if len(result) != {num_fields:d}:
aca1a271c4fc Code cleanups Raymond Hettinger <python@rcn.com> parents: 70608 diff changeset	254 raise TypeError('Expected {num_fields:d} arguments, got %d' % len(result))
aca1a271c4fc Code cleanups Raymond Hettinger <python@rcn.com> parents: 70608 diff changeset	255 return result
aca1a271c4fc Code cleanups Raymond Hettinger <python@rcn.com> parents: 70608 diff changeset	256
aca1a271c4fc Code cleanups Raymond Hettinger <python@rcn.com> parents: 70608 diff changeset	257 def __repr__(self):
aca1a271c4fc Code cleanups Raymond Hettinger <python@rcn.com> parents: 70608 diff changeset	258 'Return a nicely formatted representation string'
aca1a271c4fc Code cleanups Raymond Hettinger <python@rcn.com> parents: 70608 diff changeset	259 return '{typename}({repr_fmt})' % self
aca1a271c4fc Code cleanups Raymond Hettinger <python@rcn.com> parents: 70608 diff changeset	260
aca1a271c4fc Code cleanups Raymond Hettinger <python@rcn.com> parents: 70608 diff changeset	261 def _asdict(self):
aca1a271c4fc Code cleanups Raymond Hettinger <python@rcn.com> parents: 70608 diff changeset	262 'Return a new OrderedDict which maps field names to their values'
aca1a271c4fc Code cleanups Raymond Hettinger <python@rcn.com> parents: 70608 diff changeset	263 return OrderedDict(zip(self._fields, self))
aca1a271c4fc Code cleanups Raymond Hettinger <python@rcn.com> parents: 70608 diff changeset	264
aca1a271c4fc Code cleanups Raymond Hettinger <python@rcn.com> parents: 70608 diff changeset	265 __dict__ = property(_asdict)
aca1a271c4fc Code cleanups Raymond Hettinger <python@rcn.com> parents: 70608 diff changeset	266
aca1a271c4fc Code cleanups Raymond Hettinger <python@rcn.com> parents: 70608 diff changeset	267 def _replace(_self, **kwds):
aca1a271c4fc Code cleanups Raymond Hettinger <python@rcn.com> parents: 70608 diff changeset	268 'Return a new {typename} object replacing specified fields with new values'
aca1a271c4fc Code cleanups Raymond Hettinger <python@rcn.com> parents: 70608 diff changeset	269 result = _self._make(map(kwds.pop, {field_names!r}, _self))
aca1a271c4fc Code cleanups Raymond Hettinger <python@rcn.com> parents: 70608 diff changeset	270 if kwds:
aca1a271c4fc Code cleanups Raymond Hettinger <python@rcn.com> parents: 70608 diff changeset	271 raise ValueError('Got unexpected field names: %r' % kwds.keys())
aca1a271c4fc Code cleanups Raymond Hettinger <python@rcn.com> parents: 70608 diff changeset	272 return result
aca1a271c4fc Code cleanups Raymond Hettinger <python@rcn.com> parents: 70608 diff changeset	273
aca1a271c4fc Code cleanups Raymond Hettinger <python@rcn.com> parents: 70608 diff changeset	274 def __getnewargs__(self):
aca1a271c4fc Code cleanups Raymond Hettinger <python@rcn.com> parents: 70608 diff changeset	275 'Return self as a plain tuple. Used by copy and pickle.'
aca1a271c4fc Code cleanups Raymond Hettinger <python@rcn.com> parents: 70608 diff changeset	276 return tuple(self)
aca1a271c4fc Code cleanups Raymond Hettinger <python@rcn.com> parents: 70608 diff changeset	277
aca1a271c4fc Code cleanups Raymond Hettinger <python@rcn.com> parents: 70608 diff changeset	278 {field_defs}
aca1a271c4fc Code cleanups Raymond Hettinger <python@rcn.com> parents: 70608 diff changeset	279 '''
aca1a271c4fc Code cleanups Raymond Hettinger <python@rcn.com> parents: 70608 diff changeset	280
aca1a271c4fc Code cleanups Raymond Hettinger <python@rcn.com> parents: 70608 diff changeset	281 _repr_template = '{name}=%r'
aca1a271c4fc Code cleanups Raymond Hettinger <python@rcn.com> parents: 70608 diff changeset	282
aca1a271c4fc Code cleanups Raymond Hettinger <python@rcn.com> parents: 70608 diff changeset	283 _field_template = '''\
aca1a271c4fc Code cleanups Raymond Hettinger <python@rcn.com> parents: 70608 diff changeset	284 {name} = _property(_itemgetter({index:d}), doc='Alias for field number {index:d}')
aca1a271c4fc Code cleanups Raymond Hettinger <python@rcn.com> parents: 70608 diff changeset	285 '''
aca1a271c4fc Code cleanups Raymond Hettinger <python@rcn.com> parents: 70608 diff changeset	286
51499 beef8818a66c Issue 1818: collections.namedtuple() to support automatic renaming of invalid fieldnames. Raymond Hettinger <python@rcn.com> parents: 51110 diff changeset	287 def namedtuple(typename, field_names, verbose=False, rename=False):
40992 b46c6d27625e Add collections.NamedTuple Raymond Hettinger <python@rcn.com> parents: 40989 diff changeset	288 """Returns a new subclass of tuple with named fields.
b46c6d27625e Add collections.NamedTuple Raymond Hettinger <python@rcn.com> parents: 40989 diff changeset	289
77389 aca1a271c4fc Code cleanups Raymond Hettinger <python@rcn.com> parents: 70608 diff changeset	290 >>> Point = namedtuple('Point', ['x', 'y'])
43377 2e7dd201ea1d Sync-up named tuples with the latest version of the ASPN recipe. Raymond Hettinger <python@rcn.com> parents: 41801 diff changeset	291 >>> Point.__doc__ # docstring for the new class
40992 b46c6d27625e Add collections.NamedTuple Raymond Hettinger <python@rcn.com> parents: 40989 diff changeset	292 'Point(x, y)'
43377 2e7dd201ea1d Sync-up named tuples with the latest version of the ASPN recipe. Raymond Hettinger <python@rcn.com> parents: 41801 diff changeset	293 >>> p = Point(11, y=22) # instantiate with positional args or keywords
44343 f8d0faffce88 Simplify and speedup _asdict() for named tuples. Raymond Hettinger <python@rcn.com> parents: 44330 diff changeset	294 >>> p[0] + p[1] # indexable like a plain tuple
40992 b46c6d27625e Add collections.NamedTuple Raymond Hettinger <python@rcn.com> parents: 40989 diff changeset	295 33
44330 4a6c06a77deb Add more namedtuple() test cases. Neaten the code and comments. Raymond Hettinger <python@rcn.com> parents: 44303 diff changeset	296 >>> x, y = p # unpack like a regular tuple
40992 b46c6d27625e Add collections.NamedTuple Raymond Hettinger <python@rcn.com> parents: 40989 diff changeset	297 >>> x, y
b46c6d27625e Add collections.NamedTuple Raymond Hettinger <python@rcn.com> parents: 40989 diff changeset	298 (11, 22)
43377 2e7dd201ea1d Sync-up named tuples with the latest version of the ASPN recipe. Raymond Hettinger <python@rcn.com> parents: 41801 diff changeset	299 >>> p.x + p.y # fields also accessable by name
40992 b46c6d27625e Add collections.NamedTuple Raymond Hettinger <python@rcn.com> parents: 40989 diff changeset	300 33
44294 294b1a79f201 Cleaner method naming convention Raymond Hettinger <python@rcn.com> parents: 44290 diff changeset	301 >>> d = p._asdict() # convert to a dictionary
43466 73f49656420b Add __asdict__() to NamedTuple and refine the docs. Raymond Hettinger <python@rcn.com> parents: 43388 diff changeset	302 >>> d['x']
73f49656420b Add __asdict__() to NamedTuple and refine the docs. Raymond Hettinger <python@rcn.com> parents: 43388 diff changeset	303 11
73f49656420b Add __asdict__() to NamedTuple and refine the docs. Raymond Hettinger <python@rcn.com> parents: 43388 diff changeset	304 >>> Point(**d) # convert from a dictionary
40992 b46c6d27625e Add collections.NamedTuple Raymond Hettinger <python@rcn.com> parents: 40989 diff changeset	305 Point(x=11, y=22)
44294 294b1a79f201 Cleaner method naming convention Raymond Hettinger <python@rcn.com> parents: 44290 diff changeset	306 >>> p._replace(x=100) # _replace() is like str.replace() but targets named fields
43377 2e7dd201ea1d Sync-up named tuples with the latest version of the ASPN recipe. Raymond Hettinger <python@rcn.com> parents: 41801 diff changeset	307 Point(x=100, y=22)
40992 b46c6d27625e Add collections.NamedTuple Raymond Hettinger <python@rcn.com> parents: 40989 diff changeset	308
b46c6d27625e Add collections.NamedTuple Raymond Hettinger <python@rcn.com> parents: 40989 diff changeset	309 """
b46c6d27625e Add collections.NamedTuple Raymond Hettinger <python@rcn.com> parents: 40989 diff changeset	310
77394 b15d5b2c9051 Wrap fat lines and improve some variable names. Raymond Hettinger <python@rcn.com> parents: 77389 diff changeset	311 # Validate the field names. At the user's option, either generate an error
b15d5b2c9051 Wrap fat lines and improve some variable names. Raymond Hettinger <python@rcn.com> parents: 77389 diff changeset	312 # message or automatically replace the field name with a valid name.
43494 4db5dab7f235 Add comments to NamedTuple code. Raymond Hettinger <python@rcn.com> parents: 43466 diff changeset	313 if isinstance(field_names, basestring):
77394 b15d5b2c9051 Wrap fat lines and improve some variable names. Raymond Hettinger <python@rcn.com> parents: 77389 diff changeset	314 field_names = field_names.replace(',', ' ').split()
b15d5b2c9051 Wrap fat lines and improve some variable names. Raymond Hettinger <python@rcn.com> parents: 77389 diff changeset	315 field_names = map(str, field_names)
51499 beef8818a66c Issue 1818: collections.namedtuple() to support automatic renaming of invalid fieldnames. Raymond Hettinger <python@rcn.com> parents: 51110 diff changeset	316 if rename:
beef8818a66c Issue 1818: collections.namedtuple() to support automatic renaming of invalid fieldnames. Raymond Hettinger <python@rcn.com> parents: 51110 diff changeset	317 seen = set()
77394 b15d5b2c9051 Wrap fat lines and improve some variable names. Raymond Hettinger <python@rcn.com> parents: 77389 diff changeset	318 for index, name in enumerate(field_names):
77389 aca1a271c4fc Code cleanups Raymond Hettinger <python@rcn.com> parents: 70608 diff changeset	319 if (not all(c.isalnum() or c=='_' for c in name)
aca1a271c4fc Code cleanups Raymond Hettinger <python@rcn.com> parents: 70608 diff changeset	320 or _iskeyword(name)
aca1a271c4fc Code cleanups Raymond Hettinger <python@rcn.com> parents: 70608 diff changeset	321 or not name
aca1a271c4fc Code cleanups Raymond Hettinger <python@rcn.com> parents: 70608 diff changeset	322 or name[0].isdigit()
aca1a271c4fc Code cleanups Raymond Hettinger <python@rcn.com> parents: 70608 diff changeset	323 or name.startswith('_')
51499 beef8818a66c Issue 1818: collections.namedtuple() to support automatic renaming of invalid fieldnames. Raymond Hettinger <python@rcn.com> parents: 51110 diff changeset	324 or name in seen):
77394 b15d5b2c9051 Wrap fat lines and improve some variable names. Raymond Hettinger <python@rcn.com> parents: 77389 diff changeset	325 field_names[index] = '_%d' % index
51499 beef8818a66c Issue 1818: collections.namedtuple() to support automatic renaming of invalid fieldnames. Raymond Hettinger <python@rcn.com> parents: 51110 diff changeset	326 seen.add(name)
77394 b15d5b2c9051 Wrap fat lines and improve some variable names. Raymond Hettinger <python@rcn.com> parents: 77389 diff changeset	327 for name in [typename] + field_names:
44178 9340698ae421 Error checking was too aggressive (reported by Chris Tismer) Raymond Hettinger <python@rcn.com> parents: 43958 diff changeset	328 if not all(c.isalnum() or c=='_' for c in name):
77394 b15d5b2c9051 Wrap fat lines and improve some variable names. Raymond Hettinger <python@rcn.com> parents: 77389 diff changeset	329 raise ValueError('Type names and field names can only contain '
b15d5b2c9051 Wrap fat lines and improve some variable names. Raymond Hettinger <python@rcn.com> parents: 77389 diff changeset	330 'alphanumeric characters and underscores: %r' % name)
43579 046edaa1566a More docs, error messages, and tests Raymond Hettinger <python@rcn.com> parents: 43578 diff changeset	331 if _iskeyword(name):
77394 b15d5b2c9051 Wrap fat lines and improve some variable names. Raymond Hettinger <python@rcn.com> parents: 77389 diff changeset	332 raise ValueError('Type names and field names cannot be a '
b15d5b2c9051 Wrap fat lines and improve some variable names. Raymond Hettinger <python@rcn.com> parents: 77389 diff changeset	333 'keyword: %r' % name)
43578 4060047b3f1d Improve error messages Raymond Hettinger <python@rcn.com> parents: 43502 diff changeset	334 if name[0].isdigit():
77394 b15d5b2c9051 Wrap fat lines and improve some variable names. Raymond Hettinger <python@rcn.com> parents: 77389 diff changeset	335 raise ValueError('Type names and field names cannot start with '
b15d5b2c9051 Wrap fat lines and improve some variable names. Raymond Hettinger <python@rcn.com> parents: 77389 diff changeset	336 'a number: %r' % name)
77389 aca1a271c4fc Code cleanups Raymond Hettinger <python@rcn.com> parents: 70608 diff changeset	337 seen = set()
43502 ebf2a5cf13fb Make the error messages more specific Raymond Hettinger <python@rcn.com> parents: 43500 diff changeset	338 for name in field_names:
51499 beef8818a66c Issue 1818: collections.namedtuple() to support automatic renaming of invalid fieldnames. Raymond Hettinger <python@rcn.com> parents: 51110 diff changeset	339 if name.startswith('_') and not rename:
77395 272e7dcffd30 Minor formatting fix=up Raymond Hettinger <python@rcn.com> parents: 77394 diff changeset	340 raise ValueError('Field names cannot start with an underscore: '
77394 b15d5b2c9051 Wrap fat lines and improve some variable names. Raymond Hettinger <python@rcn.com> parents: 77389 diff changeset	341 '%r' % name)
77389 aca1a271c4fc Code cleanups Raymond Hettinger <python@rcn.com> parents: 70608 diff changeset	342 if name in seen:
43578 4060047b3f1d Improve error messages Raymond Hettinger <python@rcn.com> parents: 43502 diff changeset	343 raise ValueError('Encountered duplicate field name: %r' % name)
77389 aca1a271c4fc Code cleanups Raymond Hettinger <python@rcn.com> parents: 70608 diff changeset	344 seen.add(name)
43494 4db5dab7f235 Add comments to NamedTuple code. Raymond Hettinger <python@rcn.com> parents: 43466 diff changeset	345
77389 aca1a271c4fc Code cleanups Raymond Hettinger <python@rcn.com> parents: 70608 diff changeset	346 # Fill-in the class template
aca1a271c4fc Code cleanups Raymond Hettinger <python@rcn.com> parents: 70608 diff changeset	347 class_definition = _class_template.format(
aca1a271c4fc Code cleanups Raymond Hettinger <python@rcn.com> parents: 70608 diff changeset	348 typename = typename,
aca1a271c4fc Code cleanups Raymond Hettinger <python@rcn.com> parents: 70608 diff changeset	349 field_names = tuple(field_names),
aca1a271c4fc Code cleanups Raymond Hettinger <python@rcn.com> parents: 70608 diff changeset	350 num_fields = len(field_names),
aca1a271c4fc Code cleanups Raymond Hettinger <python@rcn.com> parents: 70608 diff changeset	351 arg_list = repr(tuple(field_names)).replace("'", "")[1:-1],
77394 b15d5b2c9051 Wrap fat lines and improve some variable names. Raymond Hettinger <python@rcn.com> parents: 77389 diff changeset	352 repr_fmt = ', '.join(_repr_template.format(name=name)
b15d5b2c9051 Wrap fat lines and improve some variable names. Raymond Hettinger <python@rcn.com> parents: 77389 diff changeset	353 for name in field_names),
77389 aca1a271c4fc Code cleanups Raymond Hettinger <python@rcn.com> parents: 70608 diff changeset	354 field_defs = '\n'.join(_field_template.format(index=index, name=name)
aca1a271c4fc Code cleanups Raymond Hettinger <python@rcn.com> parents: 70608 diff changeset	355 for index, name in enumerate(field_names))
aca1a271c4fc Code cleanups Raymond Hettinger <python@rcn.com> parents: 70608 diff changeset	356 )
43388 2fdff0b5beb6 Handle corner cased on 0-tuples and 1-tuples. Add verbose option so people can see how it works. Raymond Hettinger <python@rcn.com> parents: 43377 diff changeset	357 if verbose:
77389 aca1a271c4fc Code cleanups Raymond Hettinger <python@rcn.com> parents: 70608 diff changeset	358 print class_definition
43494 4db5dab7f235 Add comments to NamedTuple code. Raymond Hettinger <python@rcn.com> parents: 43466 diff changeset	359
77394 b15d5b2c9051 Wrap fat lines and improve some variable names. Raymond Hettinger <python@rcn.com> parents: 77389 diff changeset	360 # Execute the template string in a temporary namespace and support
b15d5b2c9051 Wrap fat lines and improve some variable names. Raymond Hettinger <python@rcn.com> parents: 77389 diff changeset	361 # tracing utilities by setting a value for frame.f_globals['__name__']
54365 3f79ecab5e52 Fix field name conflicts for named tuples. Raymond Hettinger <python@rcn.com> parents: 51113 diff changeset	362 namespace = dict(_itemgetter=_itemgetter, __name__='namedtuple_%s' % typename,
54366 23a373c8ec1b Fix field name conflicts for named tuples. Raymond Hettinger <python@rcn.com> parents: 53760 diff changeset	363 OrderedDict=OrderedDict, _property=property, _tuple=tuple)
43494 4db5dab7f235 Add comments to NamedTuple code. Raymond Hettinger <python@rcn.com> parents: 43466 diff changeset	364 try:
77389 aca1a271c4fc Code cleanups Raymond Hettinger <python@rcn.com> parents: 70608 diff changeset	365 exec class_definition in namespace
aca1a271c4fc Code cleanups Raymond Hettinger <python@rcn.com> parents: 70608 diff changeset	366 except SyntaxError as e:
77394 b15d5b2c9051 Wrap fat lines and improve some variable names. Raymond Hettinger <python@rcn.com> parents: 77389 diff changeset	367 raise SyntaxError(e.message + ':\n' + class_definition)
43496 91904f3e7be1 Better variable names Raymond Hettinger <python@rcn.com> parents: 43494 diff changeset	368 result = namespace[typename]
43494 4db5dab7f235 Add comments to NamedTuple code. Raymond Hettinger <python@rcn.com> parents: 43466 diff changeset	369
4db5dab7f235 Add comments to NamedTuple code. Raymond Hettinger <python@rcn.com> parents: 43466 diff changeset	370 # For pickling to work, the __module__ variable needs to be set to the frame
4db5dab7f235 Add comments to NamedTuple code. Raymond Hettinger <python@rcn.com> parents: 43466 diff changeset	371 # where the named tuple is created. Bypass this step in enviroments where
53760 639a79fa6a23 using sys._getframe(x), where x > 0 doesnt' work on IronPython Benjamin Peterson <benjamin@python.org> parents: 52985 diff changeset	372 # sys._getframe is not defined (Jython for example) or sys._getframe is not
639a79fa6a23 using sys._getframe(x), where x > 0 doesnt' work on IronPython Benjamin Peterson <benjamin@python.org> parents: 52985 diff changeset	373 # defined for arguments greater than 0 (IronPython).
639a79fa6a23 using sys._getframe(x), where x > 0 doesnt' work on IronPython Benjamin Peterson <benjamin@python.org> parents: 52985 diff changeset	374 try:
51113 e718d29874d7 Issue 5021: doctest.testfile should set __name__ Raymond Hettinger <python@rcn.com> parents: 49301 diff changeset	375 result.__module__ = _sys._getframe(1).f_globals.get('__name__', '__main__')
53760 639a79fa6a23 using sys._getframe(x), where x > 0 doesnt' work on IronPython Benjamin Peterson <benjamin@python.org> parents: 52985 diff changeset	376 except (AttributeError, ValueError):
639a79fa6a23 using sys._getframe(x), where x > 0 doesnt' work on IronPython Benjamin Peterson <benjamin@python.org> parents: 52985 diff changeset	377 pass
43494 4db5dab7f235 Add comments to NamedTuple code. Raymond Hettinger <python@rcn.com> parents: 43466 diff changeset	378
41774 4a3a63769d34 Improvements to NamedTuple's implementation, tests, and documentation Raymond Hettinger <python@rcn.com> parents: 40992 diff changeset	379 return result
40992 b46c6d27625e Add collections.NamedTuple Raymond Hettinger <python@rcn.com> parents: 40989 diff changeset	380
41774 4a3a63769d34 Improvements to NamedTuple's implementation, tests, and documentation Raymond Hettinger <python@rcn.com> parents: 40992 diff changeset	381
50753 5934612d5070 Issue 1696199: Add collections.Counter(). Raymond Hettinger <python@rcn.com> parents: 49301 diff changeset	382 ########################################################################
50924 8d66b82a10a3 Make merging easier by formattng comment blocks the same in Py3.1 Raymond Hettinger <python@rcn.com> parents: 50923 diff changeset	383 ### Counter
8d66b82a10a3 Make merging easier by formattng comment blocks the same in Py3.1 Raymond Hettinger <python@rcn.com> parents: 50923 diff changeset	384 ########################################################################
40992 b46c6d27625e Add collections.NamedTuple Raymond Hettinger <python@rcn.com> parents: 40989 diff changeset	385
50753 5934612d5070 Issue 1696199: Add collections.Counter(). Raymond Hettinger <python@rcn.com> parents: 49301 diff changeset	386 class Counter(dict):
5934612d5070 Issue 1696199: Add collections.Counter(). Raymond Hettinger <python@rcn.com> parents: 49301 diff changeset	387 '''Dict subclass for counting hashable items. Sometimes called a bag
5934612d5070 Issue 1696199: Add collections.Counter(). Raymond Hettinger <python@rcn.com> parents: 49301 diff changeset	388 or multiset. Elements are stored as dictionary keys and their counts
5934612d5070 Issue 1696199: Add collections.Counter(). Raymond Hettinger <python@rcn.com> parents: 49301 diff changeset	389 are stored as dictionary values.
40992 b46c6d27625e Add collections.NamedTuple Raymond Hettinger <python@rcn.com> parents: 40989 diff changeset	390
67291 c898dd215ba0 Backport r87672 and r87615, improving tests, using super() instead of direct parent references, and using __reduce__ method for pickling. Raymond Hettinger <python@rcn.com> parents: 67253 diff changeset	391 >>> c = Counter('abcdeabcdabcaba') # count elements from a string
50753 5934612d5070 Issue 1696199: Add collections.Counter(). Raymond Hettinger <python@rcn.com> parents: 49301 diff changeset	392
5934612d5070 Issue 1696199: Add collections.Counter(). Raymond Hettinger <python@rcn.com> parents: 49301 diff changeset	393 >>> c.most_common(3) # three most common elements
67291 c898dd215ba0 Backport r87672 and r87615, improving tests, using super() instead of direct parent references, and using __reduce__ method for pickling. Raymond Hettinger <python@rcn.com> parents: 67253 diff changeset	394 [('a', 5), ('b', 4), ('c', 3)]
50753 5934612d5070 Issue 1696199: Add collections.Counter(). Raymond Hettinger <python@rcn.com> parents: 49301 diff changeset	395 >>> sorted(c) # list all unique elements
67291 c898dd215ba0 Backport r87672 and r87615, improving tests, using super() instead of direct parent references, and using __reduce__ method for pickling. Raymond Hettinger <python@rcn.com> parents: 67253 diff changeset	396 ['a', 'b', 'c', 'd', 'e']
50753 5934612d5070 Issue 1696199: Add collections.Counter(). Raymond Hettinger <python@rcn.com> parents: 49301 diff changeset	397 >>> ''.join(sorted(c.elements())) # list elements with repetitions
67291 c898dd215ba0 Backport r87672 and r87615, improving tests, using super() instead of direct parent references, and using __reduce__ method for pickling. Raymond Hettinger <python@rcn.com> parents: 67253 diff changeset	398 'aaaaabbbbcccdde'
50753 5934612d5070 Issue 1696199: Add collections.Counter(). Raymond Hettinger <python@rcn.com> parents: 49301 diff changeset	399 >>> sum(c.values()) # total of all counts
67291 c898dd215ba0 Backport r87672 and r87615, improving tests, using super() instead of direct parent references, and using __reduce__ method for pickling. Raymond Hettinger <python@rcn.com> parents: 67253 diff changeset	400 15
50753 5934612d5070 Issue 1696199: Add collections.Counter(). Raymond Hettinger <python@rcn.com> parents: 49301 diff changeset	401
5934612d5070 Issue 1696199: Add collections.Counter(). Raymond Hettinger <python@rcn.com> parents: 49301 diff changeset	402 >>> c['a'] # count of letter 'a'
5934612d5070 Issue 1696199: Add collections.Counter(). Raymond Hettinger <python@rcn.com> parents: 49301 diff changeset	403 5
5934612d5070 Issue 1696199: Add collections.Counter(). Raymond Hettinger <python@rcn.com> parents: 49301 diff changeset	404 >>> for elem in 'shazam': # update counts from an iterable
5934612d5070 Issue 1696199: Add collections.Counter(). Raymond Hettinger <python@rcn.com> parents: 49301 diff changeset	405 ... c[elem] += 1 # by adding 1 to each element's count
5934612d5070 Issue 1696199: Add collections.Counter(). Raymond Hettinger <python@rcn.com> parents: 49301 diff changeset	406 >>> c['a'] # now there are seven 'a'
5934612d5070 Issue 1696199: Add collections.Counter(). Raymond Hettinger <python@rcn.com> parents: 49301 diff changeset	407 7
67291 c898dd215ba0 Backport r87672 and r87615, improving tests, using super() instead of direct parent references, and using __reduce__ method for pickling. Raymond Hettinger <python@rcn.com> parents: 67253 diff changeset	408 >>> del c['b'] # remove all 'b'
c898dd215ba0 Backport r87672 and r87615, improving tests, using super() instead of direct parent references, and using __reduce__ method for pickling. Raymond Hettinger <python@rcn.com> parents: 67253 diff changeset	409 >>> c['b'] # now there are zero 'b'
50753 5934612d5070 Issue 1696199: Add collections.Counter(). Raymond Hettinger <python@rcn.com> parents: 49301 diff changeset	410 0
5934612d5070 Issue 1696199: Add collections.Counter(). Raymond Hettinger <python@rcn.com> parents: 49301 diff changeset	411
5934612d5070 Issue 1696199: Add collections.Counter(). Raymond Hettinger <python@rcn.com> parents: 49301 diff changeset	412 >>> d = Counter('simsalabim') # make another counter
5934612d5070 Issue 1696199: Add collections.Counter(). Raymond Hettinger <python@rcn.com> parents: 49301 diff changeset	413 >>> c.update(d) # add in the second counter
5934612d5070 Issue 1696199: Add collections.Counter(). Raymond Hettinger <python@rcn.com> parents: 49301 diff changeset	414 >>> c['a'] # now there are nine 'a'
5934612d5070 Issue 1696199: Add collections.Counter(). Raymond Hettinger <python@rcn.com> parents: 49301 diff changeset	415 9
5934612d5070 Issue 1696199: Add collections.Counter(). Raymond Hettinger <python@rcn.com> parents: 49301 diff changeset	416
5934612d5070 Issue 1696199: Add collections.Counter(). Raymond Hettinger <python@rcn.com> parents: 49301 diff changeset	417 >>> c.clear() # empty the counter
5934612d5070 Issue 1696199: Add collections.Counter(). Raymond Hettinger <python@rcn.com> parents: 49301 diff changeset	418 >>> c
5934612d5070 Issue 1696199: Add collections.Counter(). Raymond Hettinger <python@rcn.com> parents: 49301 diff changeset	419 Counter()
5934612d5070 Issue 1696199: Add collections.Counter(). Raymond Hettinger <python@rcn.com> parents: 49301 diff changeset	420
5934612d5070 Issue 1696199: Add collections.Counter(). Raymond Hettinger <python@rcn.com> parents: 49301 diff changeset	421 Note: If a count is set to zero or reduced to zero, it will remain
5934612d5070 Issue 1696199: Add collections.Counter(). Raymond Hettinger <python@rcn.com> parents: 49301 diff changeset	422 in the counter until the entry is deleted or the counter is cleared:
5934612d5070 Issue 1696199: Add collections.Counter(). Raymond Hettinger <python@rcn.com> parents: 49301 diff changeset	423
5934612d5070 Issue 1696199: Add collections.Counter(). Raymond Hettinger <python@rcn.com> parents: 49301 diff changeset	424 >>> c = Counter('aaabbc')
5934612d5070 Issue 1696199: Add collections.Counter(). Raymond Hettinger <python@rcn.com> parents: 49301 diff changeset	425 >>> c['b'] -= 2 # reduce the count of 'b' by two
5934612d5070 Issue 1696199: Add collections.Counter(). Raymond Hettinger <python@rcn.com> parents: 49301 diff changeset	426 >>> c.most_common() # 'b' is still in, but its count is zero
5934612d5070 Issue 1696199: Add collections.Counter(). Raymond Hettinger <python@rcn.com> parents: 49301 diff changeset	427 [('a', 3), ('c', 1), ('b', 0)]
5934612d5070 Issue 1696199: Add collections.Counter(). Raymond Hettinger <python@rcn.com> parents: 49301 diff changeset	428
5934612d5070 Issue 1696199: Add collections.Counter(). Raymond Hettinger <python@rcn.com> parents: 49301 diff changeset	429 '''
5934612d5070 Issue 1696199: Add collections.Counter(). Raymond Hettinger <python@rcn.com> parents: 49301 diff changeset	430 # References:
5934612d5070 Issue 1696199: Add collections.Counter(). Raymond Hettinger <python@rcn.com> parents: 49301 diff changeset	431 # http://en.wikipedia.org/wiki/Multiset
5934612d5070 Issue 1696199: Add collections.Counter(). Raymond Hettinger <python@rcn.com> parents: 49301 diff changeset	432 # http://www.gnu.org/software/smalltalk/manual-base/html_node/Bag.html
5934612d5070 Issue 1696199: Add collections.Counter(). Raymond Hettinger <python@rcn.com> parents: 49301 diff changeset	433 # http://www.demo2s.com/Tutorial/Cpp/0380__set-multiset/Catalog0380__set-multiset.htm
5934612d5070 Issue 1696199: Add collections.Counter(). Raymond Hettinger <python@rcn.com> parents: 49301 diff changeset	434 # http://code.activestate.com/recipes/259174/
5934612d5070 Issue 1696199: Add collections.Counter(). Raymond Hettinger <python@rcn.com> parents: 49301 diff changeset	435 # Knuth, TAOCP Vol. II section 4.6.3
5934612d5070 Issue 1696199: Add collections.Counter(). Raymond Hettinger <python@rcn.com> parents: 49301 diff changeset	436
50920 191b7b3ddf4f Build-outs for Counter() class: Raymond Hettinger <python@rcn.com> parents: 50761 diff changeset	437 def __init__(self, iterable=None, **kwds):
50753 5934612d5070 Issue 1696199: Add collections.Counter(). Raymond Hettinger <python@rcn.com> parents: 49301 diff changeset	438 '''Create a new, empty Counter object. And if given, count elements
50756 f45997d9ac55 Simplify Counter() API. Replace items keyword argument Raymond Hettinger <python@rcn.com> parents: 50753 diff changeset	439 from an input iterable. Or, initialize the count from another mapping
f45997d9ac55 Simplify Counter() API. Replace items keyword argument Raymond Hettinger <python@rcn.com> parents: 50753 diff changeset	440 of elements to their counts.
50753 5934612d5070 Issue 1696199: Add collections.Counter(). Raymond Hettinger <python@rcn.com> parents: 49301 diff changeset	441
50756 f45997d9ac55 Simplify Counter() API. Replace items keyword argument Raymond Hettinger <python@rcn.com> parents: 50753 diff changeset	442 >>> c = Counter() # a new, empty counter
50760 e301141e91b1 Fixup and simplify docstrings and doctests. Raymond Hettinger <python@rcn.com> parents: 50756 diff changeset	443 >>> c = Counter('gallahad') # a new counter from an iterable
50756 f45997d9ac55 Simplify Counter() API. Replace items keyword argument Raymond Hettinger <python@rcn.com> parents: 50753 diff changeset	444 >>> c = Counter({'a': 4, 'b': 2}) # a new counter from a mapping
50920 191b7b3ddf4f Build-outs for Counter() class: Raymond Hettinger <python@rcn.com> parents: 50761 diff changeset	445 >>> c = Counter(a=4, b=2) # a new counter from keyword args
50753 5934612d5070 Issue 1696199: Add collections.Counter(). Raymond Hettinger <python@rcn.com> parents: 49301 diff changeset	446
5934612d5070 Issue 1696199: Add collections.Counter(). Raymond Hettinger <python@rcn.com> parents: 49301 diff changeset	447 '''
67291 c898dd215ba0 Backport r87672 and r87615, improving tests, using super() instead of direct parent references, and using __reduce__ method for pickling. Raymond Hettinger <python@rcn.com> parents: 67253 diff changeset	448 super(Counter, self).__init__()
50920 191b7b3ddf4f Build-outs for Counter() class: Raymond Hettinger <python@rcn.com> parents: 50761 diff changeset	449 self.update(iterable, **kwds)
50753 5934612d5070 Issue 1696199: Add collections.Counter(). Raymond Hettinger <python@rcn.com> parents: 49301 diff changeset	450
5934612d5070 Issue 1696199: Add collections.Counter(). Raymond Hettinger <python@rcn.com> parents: 49301 diff changeset	451 def __missing__(self, key):
5934612d5070 Issue 1696199: Add collections.Counter(). Raymond Hettinger <python@rcn.com> parents: 49301 diff changeset	452 'The count of elements not in the Counter is zero.'
5934612d5070 Issue 1696199: Add collections.Counter(). Raymond Hettinger <python@rcn.com> parents: 49301 diff changeset	453 # Needed so that self[missing_item] does not raise KeyError
5934612d5070 Issue 1696199: Add collections.Counter(). Raymond Hettinger <python@rcn.com> parents: 49301 diff changeset	454 return 0
5934612d5070 Issue 1696199: Add collections.Counter(). Raymond Hettinger <python@rcn.com> parents: 49301 diff changeset	455
5934612d5070 Issue 1696199: Add collections.Counter(). Raymond Hettinger <python@rcn.com> parents: 49301 diff changeset	456 def most_common(self, n=None):
5934612d5070 Issue 1696199: Add collections.Counter(). Raymond Hettinger <python@rcn.com> parents: 49301 diff changeset	457 '''List the n most common elements and their counts from the most
5934612d5070 Issue 1696199: Add collections.Counter(). Raymond Hettinger <python@rcn.com> parents: 49301 diff changeset	458 common to the least. If n is None, then list all element counts.
5934612d5070 Issue 1696199: Add collections.Counter(). Raymond Hettinger <python@rcn.com> parents: 49301 diff changeset	459
67291 c898dd215ba0 Backport r87672 and r87615, improving tests, using super() instead of direct parent references, and using __reduce__ method for pickling. Raymond Hettinger <python@rcn.com> parents: 67253 diff changeset	460 >>> Counter('abcdeabcdabcaba').most_common(3)
c898dd215ba0 Backport r87672 and r87615, improving tests, using super() instead of direct parent references, and using __reduce__ method for pickling. Raymond Hettinger <python@rcn.com> parents: 67253 diff changeset	461 [('a', 5), ('b', 4), ('c', 3)]
50753 5934612d5070 Issue 1696199: Add collections.Counter(). Raymond Hettinger <python@rcn.com> parents: 49301 diff changeset	462
5934612d5070 Issue 1696199: Add collections.Counter(). Raymond Hettinger <python@rcn.com> parents: 49301 diff changeset	463 '''
5934612d5070 Issue 1696199: Add collections.Counter(). Raymond Hettinger <python@rcn.com> parents: 49301 diff changeset	464 # Emulate Bag.sortedByCount from Smalltalk
5934612d5070 Issue 1696199: Add collections.Counter(). Raymond Hettinger <python@rcn.com> parents: 49301 diff changeset	465 if n is None:
5934612d5070 Issue 1696199: Add collections.Counter(). Raymond Hettinger <python@rcn.com> parents: 49301 diff changeset	466 return sorted(self.iteritems(), key=_itemgetter(1), reverse=True)
5934612d5070 Issue 1696199: Add collections.Counter(). Raymond Hettinger <python@rcn.com> parents: 49301 diff changeset	467 return _heapq.nlargest(n, self.iteritems(), key=_itemgetter(1))
5934612d5070 Issue 1696199: Add collections.Counter(). Raymond Hettinger <python@rcn.com> parents: 49301 diff changeset	468
5934612d5070 Issue 1696199: Add collections.Counter(). Raymond Hettinger <python@rcn.com> parents: 49301 diff changeset	469 def elements(self):
5934612d5070 Issue 1696199: Add collections.Counter(). Raymond Hettinger <python@rcn.com> parents: 49301 diff changeset	470 '''Iterator over elements repeating each as many times as its count.
5934612d5070 Issue 1696199: Add collections.Counter(). Raymond Hettinger <python@rcn.com> parents: 49301 diff changeset	471
5934612d5070 Issue 1696199: Add collections.Counter(). Raymond Hettinger <python@rcn.com> parents: 49301 diff changeset	472 >>> c = Counter('ABCABC')
5934612d5070 Issue 1696199: Add collections.Counter(). Raymond Hettinger <python@rcn.com> parents: 49301 diff changeset	473 >>> sorted(c.elements())
5934612d5070 Issue 1696199: Add collections.Counter(). Raymond Hettinger <python@rcn.com> parents: 49301 diff changeset	474 ['A', 'A', 'B', 'B', 'C', 'C']
5934612d5070 Issue 1696199: Add collections.Counter(). Raymond Hettinger <python@rcn.com> parents: 49301 diff changeset	475
50760 e301141e91b1 Fixup and simplify docstrings and doctests. Raymond Hettinger <python@rcn.com> parents: 50756 diff changeset	476 # Knuth's example for prime factors of 1836: 2*2 3*3 17**1
e301141e91b1 Fixup and simplify docstrings and doctests. Raymond Hettinger <python@rcn.com> parents: 50756 diff changeset	477 >>> prime_factors = Counter({2: 2, 3: 3, 17: 1})
e301141e91b1 Fixup and simplify docstrings and doctests. Raymond Hettinger <python@rcn.com> parents: 50756 diff changeset	478 >>> product = 1
e301141e91b1 Fixup and simplify docstrings and doctests. Raymond Hettinger <python@rcn.com> parents: 50756 diff changeset	479 >>> for factor in prime_factors.elements(): # loop over factors
e301141e91b1 Fixup and simplify docstrings and doctests. Raymond Hettinger <python@rcn.com> parents: 50756 diff changeset	480 ... product *= factor # and multiply them
e301141e91b1 Fixup and simplify docstrings and doctests. Raymond Hettinger <python@rcn.com> parents: 50756 diff changeset	481 >>> product
50753 5934612d5070 Issue 1696199: Add collections.Counter(). Raymond Hettinger <python@rcn.com> parents: 49301 diff changeset	482 1836
5934612d5070 Issue 1696199: Add collections.Counter(). Raymond Hettinger <python@rcn.com> parents: 49301 diff changeset	483
50760 e301141e91b1 Fixup and simplify docstrings and doctests. Raymond Hettinger <python@rcn.com> parents: 50756 diff changeset	484 Note, if an element's count has been set to zero or is a negative
e301141e91b1 Fixup and simplify docstrings and doctests. Raymond Hettinger <python@rcn.com> parents: 50756 diff changeset	485 number, elements() will ignore it.
50753 5934612d5070 Issue 1696199: Add collections.Counter(). Raymond Hettinger <python@rcn.com> parents: 49301 diff changeset	486
5934612d5070 Issue 1696199: Add collections.Counter(). Raymond Hettinger <python@rcn.com> parents: 49301 diff changeset	487 '''
5934612d5070 Issue 1696199: Add collections.Counter(). Raymond Hettinger <python@rcn.com> parents: 49301 diff changeset	488 # Emulate Bag.do from Smalltalk and Multiset.begin from C++.
50761 e5f996cda321 Speed-up __repr__. Eliminate duplicate tests. Use a from-irmport. Raymond Hettinger <python@rcn.com> parents: 50760 diff changeset	489 return _chain.from_iterable(_starmap(_repeat, self.iteritems()))
50753 5934612d5070 Issue 1696199: Add collections.Counter(). Raymond Hettinger <python@rcn.com> parents: 49301 diff changeset	490
5934612d5070 Issue 1696199: Add collections.Counter(). Raymond Hettinger <python@rcn.com> parents: 49301 diff changeset	491 # Override dict methods where necessary
5934612d5070 Issue 1696199: Add collections.Counter(). Raymond Hettinger <python@rcn.com> parents: 49301 diff changeset	492
5934612d5070 Issue 1696199: Add collections.Counter(). Raymond Hettinger <python@rcn.com> parents: 49301 diff changeset	493 @classmethod
5934612d5070 Issue 1696199: Add collections.Counter(). Raymond Hettinger <python@rcn.com> parents: 49301 diff changeset	494 def fromkeys(cls, iterable, v=None):
5934612d5070 Issue 1696199: Add collections.Counter(). Raymond Hettinger <python@rcn.com> parents: 49301 diff changeset	495 # There is no equivalent method for counters because setting v=1
5934612d5070 Issue 1696199: Add collections.Counter(). Raymond Hettinger <python@rcn.com> parents: 49301 diff changeset	496 # means that no element can have a count greater than one.
5934612d5070 Issue 1696199: Add collections.Counter(). Raymond Hettinger <python@rcn.com> parents: 49301 diff changeset	497 raise NotImplementedError(
5934612d5070 Issue 1696199: Add collections.Counter(). Raymond Hettinger <python@rcn.com> parents: 49301 diff changeset	498 'Counter.fromkeys() is undefined. Use Counter(iterable) instead.')
5934612d5070 Issue 1696199: Add collections.Counter(). Raymond Hettinger <python@rcn.com> parents: 49301 diff changeset	499
50920 191b7b3ddf4f Build-outs for Counter() class: Raymond Hettinger <python@rcn.com> parents: 50761 diff changeset	500 def update(self, iterable=None, **kwds):
50753 5934612d5070 Issue 1696199: Add collections.Counter(). Raymond Hettinger <python@rcn.com> parents: 49301 diff changeset	501 '''Like dict.update() but add counts instead of replacing them.
5934612d5070 Issue 1696199: Add collections.Counter(). Raymond Hettinger <python@rcn.com> parents: 49301 diff changeset	502
50760 e301141e91b1 Fixup and simplify docstrings and doctests. Raymond Hettinger <python@rcn.com> parents: 50756 diff changeset	503 Source can be an iterable, a dictionary, or another Counter instance.
50753 5934612d5070 Issue 1696199: Add collections.Counter(). Raymond Hettinger <python@rcn.com> parents: 49301 diff changeset	504
5934612d5070 Issue 1696199: Add collections.Counter(). Raymond Hettinger <python@rcn.com> parents: 49301 diff changeset	505 >>> c = Counter('which')
50760 e301141e91b1 Fixup and simplify docstrings and doctests. Raymond Hettinger <python@rcn.com> parents: 50756 diff changeset	506 >>> c.update('witch') # add elements from another iterable
e301141e91b1 Fixup and simplify docstrings and doctests. Raymond Hettinger <python@rcn.com> parents: 50756 diff changeset	507 >>> d = Counter('watch')
e301141e91b1 Fixup and simplify docstrings and doctests. Raymond Hettinger <python@rcn.com> parents: 50756 diff changeset	508 >>> c.update(d) # add elements from another counter
e301141e91b1 Fixup and simplify docstrings and doctests. Raymond Hettinger <python@rcn.com> parents: 50756 diff changeset	509 >>> c['h'] # four 'h' in which, witch, and watch
50756 f45997d9ac55 Simplify Counter() API. Replace items keyword argument Raymond Hettinger <python@rcn.com> parents: 50753 diff changeset	510 4
50753 5934612d5070 Issue 1696199: Add collections.Counter(). Raymond Hettinger <python@rcn.com> parents: 49301 diff changeset	511
5934612d5070 Issue 1696199: Add collections.Counter(). Raymond Hettinger <python@rcn.com> parents: 49301 diff changeset	512 '''
5934612d5070 Issue 1696199: Add collections.Counter(). Raymond Hettinger <python@rcn.com> parents: 49301 diff changeset	513 # The regular dict.update() operation makes no sense here because the
5934612d5070 Issue 1696199: Add collections.Counter(). Raymond Hettinger <python@rcn.com> parents: 49301 diff changeset	514 # replace behavior results in the some of original untouched counts
5934612d5070 Issue 1696199: Add collections.Counter(). Raymond Hettinger <python@rcn.com> parents: 49301 diff changeset	515 # being mixed-in with all of the other counts for a mismash that
5934612d5070 Issue 1696199: Add collections.Counter(). Raymond Hettinger <python@rcn.com> parents: 49301 diff changeset	516 # doesn't have a straight-forward interpretation in most counting
50920 191b7b3ddf4f Build-outs for Counter() class: Raymond Hettinger <python@rcn.com> parents: 50761 diff changeset	517 # contexts. Instead, we implement straight-addition. Both the inputs
191b7b3ddf4f Build-outs for Counter() class: Raymond Hettinger <python@rcn.com> parents: 50761 diff changeset	518 # and outputs are allowed to contain zero and negative counts.
50756 f45997d9ac55 Simplify Counter() API. Replace items keyword argument Raymond Hettinger <python@rcn.com> parents: 50753 diff changeset	519
f45997d9ac55 Simplify Counter() API. Replace items keyword argument Raymond Hettinger <python@rcn.com> parents: 50753 diff changeset	520 if iterable is not None:
f45997d9ac55 Simplify Counter() API. Replace items keyword argument Raymond Hettinger <python@rcn.com> parents: 50753 diff changeset	521 if isinstance(iterable, Mapping):
50972 3f13c65aec05 Update comments and add an optimized path for Counter.update(). Raymond Hettinger <python@rcn.com> parents: 50964 diff changeset	522 if self:
54986 d2b1f5ef2ae3 Issue 6370: Performance issue with collections.Counter(). Raymond Hettinger <python@rcn.com> parents: 54725 diff changeset	523 self_get = self.get
50972 3f13c65aec05 Update comments and add an optimized path for Counter.update(). Raymond Hettinger <python@rcn.com> parents: 50964 diff changeset	524 for elem, count in iterable.iteritems():
54986 d2b1f5ef2ae3 Issue 6370: Performance issue with collections.Counter(). Raymond Hettinger <python@rcn.com> parents: 54725 diff changeset	525 self[elem] = self_get(elem, 0) + count
50972 3f13c65aec05 Update comments and add an optimized path for Counter.update(). Raymond Hettinger <python@rcn.com> parents: 50964 diff changeset	526 else:
67291 c898dd215ba0 Backport r87672 and r87615, improving tests, using super() instead of direct parent references, and using __reduce__ method for pickling. Raymond Hettinger <python@rcn.com> parents: 67253 diff changeset	527 super(Counter, self).update(iterable) # fast path when counter is empty
50756 f45997d9ac55 Simplify Counter() API. Replace items keyword argument Raymond Hettinger <python@rcn.com> parents: 50753 diff changeset	528 else:
54986 d2b1f5ef2ae3 Issue 6370: Performance issue with collections.Counter(). Raymond Hettinger <python@rcn.com> parents: 54725 diff changeset	529 self_get = self.get
50756 f45997d9ac55 Simplify Counter() API. Replace items keyword argument Raymond Hettinger <python@rcn.com> parents: 50753 diff changeset	530 for elem in iterable:
54986 d2b1f5ef2ae3 Issue 6370: Performance issue with collections.Counter(). Raymond Hettinger <python@rcn.com> parents: 54725 diff changeset	531 self[elem] = self_get(elem, 0) + 1
50920 191b7b3ddf4f Build-outs for Counter() class: Raymond Hettinger <python@rcn.com> parents: 50761 diff changeset	532 if kwds:
191b7b3ddf4f Build-outs for Counter() class: Raymond Hettinger <python@rcn.com> parents: 50761 diff changeset	533 self.update(kwds)
50753 5934612d5070 Issue 1696199: Add collections.Counter(). Raymond Hettinger <python@rcn.com> parents: 49301 diff changeset	534
60224 da7b0006a799 Add subtract() method to collections.Counter() objects. Raymond Hettinger <python@rcn.com> parents: 60215 diff changeset	535 def subtract(self, iterable=None, **kwds):
da7b0006a799 Add subtract() method to collections.Counter() objects. Raymond Hettinger <python@rcn.com> parents: 60215 diff changeset	536 '''Like dict.update() but subtracts counts instead of replacing them.
da7b0006a799 Add subtract() method to collections.Counter() objects. Raymond Hettinger <python@rcn.com> parents: 60215 diff changeset	537 Counts can be reduced below zero. Both the inputs and outputs are
da7b0006a799 Add subtract() method to collections.Counter() objects. Raymond Hettinger <python@rcn.com> parents: 60215 diff changeset	538 allowed to contain zero and negative counts.
da7b0006a799 Add subtract() method to collections.Counter() objects. Raymond Hettinger <python@rcn.com> parents: 60215 diff changeset	539
da7b0006a799 Add subtract() method to collections.Counter() objects. Raymond Hettinger <python@rcn.com> parents: 60215 diff changeset	540 Source can be an iterable, a dictionary, or another Counter instance.
da7b0006a799 Add subtract() method to collections.Counter() objects. Raymond Hettinger <python@rcn.com> parents: 60215 diff changeset	541
da7b0006a799 Add subtract() method to collections.Counter() objects. Raymond Hettinger <python@rcn.com> parents: 60215 diff changeset	542 >>> c = Counter('which')
da7b0006a799 Add subtract() method to collections.Counter() objects. Raymond Hettinger <python@rcn.com> parents: 60215 diff changeset	543 >>> c.subtract('witch') # subtract elements from another iterable
da7b0006a799 Add subtract() method to collections.Counter() objects. Raymond Hettinger <python@rcn.com> parents: 60215 diff changeset	544 >>> c.subtract(Counter('watch')) # subtract elements from another counter
da7b0006a799 Add subtract() method to collections.Counter() objects. Raymond Hettinger <python@rcn.com> parents: 60215 diff changeset	545 >>> c['h'] # 2 in which, minus 1 in witch, minus 1 in watch
da7b0006a799 Add subtract() method to collections.Counter() objects. Raymond Hettinger <python@rcn.com> parents: 60215 diff changeset	546 0
da7b0006a799 Add subtract() method to collections.Counter() objects. Raymond Hettinger <python@rcn.com> parents: 60215 diff changeset	547 >>> c['w'] # 1 in which, minus 1 in witch, minus 1 in watch
da7b0006a799 Add subtract() method to collections.Counter() objects. Raymond Hettinger <python@rcn.com> parents: 60215 diff changeset	548 -1
da7b0006a799 Add subtract() method to collections.Counter() objects. Raymond Hettinger <python@rcn.com> parents: 60215 diff changeset	549
da7b0006a799 Add subtract() method to collections.Counter() objects. Raymond Hettinger <python@rcn.com> parents: 60215 diff changeset	550 '''
da7b0006a799 Add subtract() method to collections.Counter() objects. Raymond Hettinger <python@rcn.com> parents: 60215 diff changeset	551 if iterable is not None:
60510 b4a155e4d312 Minor factoring Raymond Hettinger <python@rcn.com> parents: 60224 diff changeset	552 self_get = self.get
60224 da7b0006a799 Add subtract() method to collections.Counter() objects. Raymond Hettinger <python@rcn.com> parents: 60215 diff changeset	553 if isinstance(iterable, Mapping):
da7b0006a799 Add subtract() method to collections.Counter() objects. Raymond Hettinger <python@rcn.com> parents: 60215 diff changeset	554 for elem, count in iterable.items():
da7b0006a799 Add subtract() method to collections.Counter() objects. Raymond Hettinger <python@rcn.com> parents: 60215 diff changeset	555 self[elem] = self_get(elem, 0) - count
da7b0006a799 Add subtract() method to collections.Counter() objects. Raymond Hettinger <python@rcn.com> parents: 60215 diff changeset	556 else:
da7b0006a799 Add subtract() method to collections.Counter() objects. Raymond Hettinger <python@rcn.com> parents: 60215 diff changeset	557 for elem in iterable:
da7b0006a799 Add subtract() method to collections.Counter() objects. Raymond Hettinger <python@rcn.com> parents: 60215 diff changeset	558 self[elem] = self_get(elem, 0) - 1
da7b0006a799 Add subtract() method to collections.Counter() objects. Raymond Hettinger <python@rcn.com> parents: 60215 diff changeset	559 if kwds:
da7b0006a799 Add subtract() method to collections.Counter() objects. Raymond Hettinger <python@rcn.com> parents: 60215 diff changeset	560 self.subtract(kwds)
da7b0006a799 Add subtract() method to collections.Counter() objects. Raymond Hettinger <python@rcn.com> parents: 60215 diff changeset	561
50753 5934612d5070 Issue 1696199: Add collections.Counter(). Raymond Hettinger <python@rcn.com> parents: 49301 diff changeset	562 def copy(self):
69378 30d6bc10e862 Fix minor subclassing issue with collections.Counter Raymond Hettinger <python@rcn.com> parents: 68256 diff changeset	563 'Return a shallow copy.'
30d6bc10e862 Fix minor subclassing issue with collections.Counter Raymond Hettinger <python@rcn.com> parents: 68256 diff changeset	564 return self.__class__(self)
50753 5934612d5070 Issue 1696199: Add collections.Counter(). Raymond Hettinger <python@rcn.com> parents: 49301 diff changeset	565
67291 c898dd215ba0 Backport r87672 and r87615, improving tests, using super() instead of direct parent references, and using __reduce__ method for pickling. Raymond Hettinger <python@rcn.com> parents: 67253 diff changeset	566 def __reduce__(self):
c898dd215ba0 Backport r87672 and r87615, improving tests, using super() instead of direct parent references, and using __reduce__ method for pickling. Raymond Hettinger <python@rcn.com> parents: 67253 diff changeset	567 return self.__class__, (dict(self),)
c898dd215ba0 Backport r87672 and r87615, improving tests, using super() instead of direct parent references, and using __reduce__ method for pickling. Raymond Hettinger <python@rcn.com> parents: 67253 diff changeset	568
50920 191b7b3ddf4f Build-outs for Counter() class: Raymond Hettinger <python@rcn.com> parents: 50761 diff changeset	569 def __delitem__(self, elem):
191b7b3ddf4f Build-outs for Counter() class: Raymond Hettinger <python@rcn.com> parents: 50761 diff changeset	570 'Like dict.__delitem__() but does not raise KeyError for missing values.'
191b7b3ddf4f Build-outs for Counter() class: Raymond Hettinger <python@rcn.com> parents: 50761 diff changeset	571 if elem in self:
67291 c898dd215ba0 Backport r87672 and r87615, improving tests, using super() instead of direct parent references, and using __reduce__ method for pickling. Raymond Hettinger <python@rcn.com> parents: 67253 diff changeset	572 super(Counter, self).__delitem__(elem)
50920 191b7b3ddf4f Build-outs for Counter() class: Raymond Hettinger <python@rcn.com> parents: 50761 diff changeset	573
50753 5934612d5070 Issue 1696199: Add collections.Counter(). Raymond Hettinger <python@rcn.com> parents: 49301 diff changeset	574 def __repr__(self):
5934612d5070 Issue 1696199: Add collections.Counter(). Raymond Hettinger <python@rcn.com> parents: 49301 diff changeset	575 if not self:
5934612d5070 Issue 1696199: Add collections.Counter(). Raymond Hettinger <python@rcn.com> parents: 49301 diff changeset	576 return '%s()' % self.__class__.__name__
50761 e5f996cda321 Speed-up __repr__. Eliminate duplicate tests. Use a from-irmport. Raymond Hettinger <python@rcn.com> parents: 50760 diff changeset	577 items = ', '.join(map('%r: %r'.__mod__, self.most_common()))
50756 f45997d9ac55 Simplify Counter() API. Replace items keyword argument Raymond Hettinger <python@rcn.com> parents: 50753 diff changeset	578 return '%s({%s})' % (self.__class__.__name__, items)
40992 b46c6d27625e Add collections.NamedTuple Raymond Hettinger <python@rcn.com> parents: 40989 diff changeset	579
50920 191b7b3ddf4f Build-outs for Counter() class: Raymond Hettinger <python@rcn.com> parents: 50761 diff changeset	580 # Multiset-style mathematical operations discussed in:
191b7b3ddf4f Build-outs for Counter() class: Raymond Hettinger <python@rcn.com> parents: 50761 diff changeset	581 # Knuth TAOCP Volume II section 4.6.3 exercise 19
191b7b3ddf4f Build-outs for Counter() class: Raymond Hettinger <python@rcn.com> parents: 50761 diff changeset	582 # and at http://en.wikipedia.org/wiki/Multiset
191b7b3ddf4f Build-outs for Counter() class: Raymond Hettinger <python@rcn.com> parents: 50761 diff changeset	583 #
191b7b3ddf4f Build-outs for Counter() class: Raymond Hettinger <python@rcn.com> parents: 50761 diff changeset	584 # Outputs guaranteed to only include positive counts.
191b7b3ddf4f Build-outs for Counter() class: Raymond Hettinger <python@rcn.com> parents: 50761 diff changeset	585 #
191b7b3ddf4f Build-outs for Counter() class: Raymond Hettinger <python@rcn.com> parents: 50761 diff changeset	586 # To strip negative and zero counts, add-in an empty counter:
191b7b3ddf4f Build-outs for Counter() class: Raymond Hettinger <python@rcn.com> parents: 50761 diff changeset	587 # c += Counter()
191b7b3ddf4f Build-outs for Counter() class: Raymond Hettinger <python@rcn.com> parents: 50761 diff changeset	588
191b7b3ddf4f Build-outs for Counter() class: Raymond Hettinger <python@rcn.com> parents: 50761 diff changeset	589 def __add__(self, other):
191b7b3ddf4f Build-outs for Counter() class: Raymond Hettinger <python@rcn.com> parents: 50761 diff changeset	590 '''Add counts from two counters.
191b7b3ddf4f Build-outs for Counter() class: Raymond Hettinger <python@rcn.com> parents: 50761 diff changeset	591
191b7b3ddf4f Build-outs for Counter() class: Raymond Hettinger <python@rcn.com> parents: 50761 diff changeset	592 >>> Counter('abbb') + Counter('bcc')
191b7b3ddf4f Build-outs for Counter() class: Raymond Hettinger <python@rcn.com> parents: 50761 diff changeset	593 Counter({'b': 4, 'c': 2, 'a': 1})
191b7b3ddf4f Build-outs for Counter() class: Raymond Hettinger <python@rcn.com> parents: 50761 diff changeset	594
191b7b3ddf4f Build-outs for Counter() class: Raymond Hettinger <python@rcn.com> parents: 50761 diff changeset	595 '''
191b7b3ddf4f Build-outs for Counter() class: Raymond Hettinger <python@rcn.com> parents: 50761 diff changeset	596 if not isinstance(other, Counter):
191b7b3ddf4f Build-outs for Counter() class: Raymond Hettinger <python@rcn.com> parents: 50761 diff changeset	597 return NotImplemented
191b7b3ddf4f Build-outs for Counter() class: Raymond Hettinger <python@rcn.com> parents: 50761 diff changeset	598 result = Counter()
69416 0c7ea87f676a Rework multiset methods to use less memory and to make fewer calls to __hash__. Raymond Hettinger <python@rcn.com> parents: 69378 diff changeset	599 for elem, count in self.items():
0c7ea87f676a Rework multiset methods to use less memory and to make fewer calls to __hash__. Raymond Hettinger <python@rcn.com> parents: 69378 diff changeset	600 newcount = count + other[elem]
50920 191b7b3ddf4f Build-outs for Counter() class: Raymond Hettinger <python@rcn.com> parents: 50761 diff changeset	601 if newcount > 0:
191b7b3ddf4f Build-outs for Counter() class: Raymond Hettinger <python@rcn.com> parents: 50761 diff changeset	602 result[elem] = newcount
69416 0c7ea87f676a Rework multiset methods to use less memory and to make fewer calls to __hash__. Raymond Hettinger <python@rcn.com> parents: 69378 diff changeset	603 for elem, count in other.items():
0c7ea87f676a Rework multiset methods to use less memory and to make fewer calls to __hash__. Raymond Hettinger <python@rcn.com> parents: 69378 diff changeset	604 if elem not in self and count > 0:
0c7ea87f676a Rework multiset methods to use less memory and to make fewer calls to __hash__. Raymond Hettinger <python@rcn.com> parents: 69378 diff changeset	605 result[elem] = count
50920 191b7b3ddf4f Build-outs for Counter() class: Raymond Hettinger <python@rcn.com> parents: 50761 diff changeset	606 return result
191b7b3ddf4f Build-outs for Counter() class: Raymond Hettinger <python@rcn.com> parents: 50761 diff changeset	607
191b7b3ddf4f Build-outs for Counter() class: Raymond Hettinger <python@rcn.com> parents: 50761 diff changeset	608 def __sub__(self, other):
191b7b3ddf4f Build-outs for Counter() class: Raymond Hettinger <python@rcn.com> parents: 50761 diff changeset	609 ''' Subtract count, but keep only results with positive counts.
191b7b3ddf4f Build-outs for Counter() class: Raymond Hettinger <python@rcn.com> parents: 50761 diff changeset	610
191b7b3ddf4f Build-outs for Counter() class: Raymond Hettinger <python@rcn.com> parents: 50761 diff changeset	611 >>> Counter('abbbc') - Counter('bccd')
191b7b3ddf4f Build-outs for Counter() class: Raymond Hettinger <python@rcn.com> parents: 50761 diff changeset	612 Counter({'b': 2, 'a': 1})
191b7b3ddf4f Build-outs for Counter() class: Raymond Hettinger <python@rcn.com> parents: 50761 diff changeset	613
191b7b3ddf4f Build-outs for Counter() class: Raymond Hettinger <python@rcn.com> parents: 50761 diff changeset	614 '''
191b7b3ddf4f Build-outs for Counter() class: Raymond Hettinger <python@rcn.com> parents: 50761 diff changeset	615 if not isinstance(other, Counter):
191b7b3ddf4f Build-outs for Counter() class: Raymond Hettinger <python@rcn.com> parents: 50761 diff changeset	616 return NotImplemented
191b7b3ddf4f Build-outs for Counter() class: Raymond Hettinger <python@rcn.com> parents: 50761 diff changeset	617 result = Counter()
69416 0c7ea87f676a Rework multiset methods to use less memory and to make fewer calls to __hash__. Raymond Hettinger <python@rcn.com> parents: 69378 diff changeset	618 for elem, count in self.items():
0c7ea87f676a Rework multiset methods to use less memory and to make fewer calls to __hash__. Raymond Hettinger <python@rcn.com> parents: 69378 diff changeset	619 newcount = count - other[elem]
50920 191b7b3ddf4f Build-outs for Counter() class: Raymond Hettinger <python@rcn.com> parents: 50761 diff changeset	620 if newcount > 0:
191b7b3ddf4f Build-outs for Counter() class: Raymond Hettinger <python@rcn.com> parents: 50761 diff changeset	621 result[elem] = newcount
69416 0c7ea87f676a Rework multiset methods to use less memory and to make fewer calls to __hash__. Raymond Hettinger <python@rcn.com> parents: 69378 diff changeset	622 for elem, count in other.items():
0c7ea87f676a Rework multiset methods to use less memory and to make fewer calls to __hash__. Raymond Hettinger <python@rcn.com> parents: 69378 diff changeset	623 if elem not in self and count < 0:
0c7ea87f676a Rework multiset methods to use less memory and to make fewer calls to __hash__. Raymond Hettinger <python@rcn.com> parents: 69378 diff changeset	624 result[elem] = 0 - count
50920 191b7b3ddf4f Build-outs for Counter() class: Raymond Hettinger <python@rcn.com> parents: 50761 diff changeset	625 return result
191b7b3ddf4f Build-outs for Counter() class: Raymond Hettinger <python@rcn.com> parents: 50761 diff changeset	626
191b7b3ddf4f Build-outs for Counter() class: Raymond Hettinger <python@rcn.com> parents: 50761 diff changeset	627 def __or__(self, other):
191b7b3ddf4f Build-outs for Counter() class: Raymond Hettinger <python@rcn.com> parents: 50761 diff changeset	628 '''Union is the maximum of value in either of the input counters.
191b7b3ddf4f Build-outs for Counter() class: Raymond Hettinger <python@rcn.com> parents: 50761 diff changeset	629
191b7b3ddf4f Build-outs for Counter() class: Raymond Hettinger <python@rcn.com> parents: 50761 diff changeset	630 >>> Counter('abbb') \| Counter('bcc')
191b7b3ddf4f Build-outs for Counter() class: Raymond Hettinger <python@rcn.com> parents: 50761 diff changeset	631 Counter({'b': 3, 'c': 2, 'a': 1})
191b7b3ddf4f Build-outs for Counter() class: Raymond Hettinger <python@rcn.com> parents: 50761 diff changeset	632
191b7b3ddf4f Build-outs for Counter() class: Raymond Hettinger <python@rcn.com> parents: 50761 diff changeset	633 '''
191b7b3ddf4f Build-outs for Counter() class: Raymond Hettinger <python@rcn.com> parents: 50761 diff changeset	634 if not isinstance(other, Counter):
191b7b3ddf4f Build-outs for Counter() class: Raymond Hettinger <python@rcn.com> parents: 50761 diff changeset	635 return NotImplemented
191b7b3ddf4f Build-outs for Counter() class: Raymond Hettinger <python@rcn.com> parents: 50761 diff changeset	636 result = Counter()
69416 0c7ea87f676a Rework multiset methods to use less memory and to make fewer calls to __hash__. Raymond Hettinger <python@rcn.com> parents: 69378 diff changeset	637 for elem, count in self.items():
0c7ea87f676a Rework multiset methods to use less memory and to make fewer calls to __hash__. Raymond Hettinger <python@rcn.com> parents: 69378 diff changeset	638 other_count = other[elem]
0c7ea87f676a Rework multiset methods to use less memory and to make fewer calls to __hash__. Raymond Hettinger <python@rcn.com> parents: 69378 diff changeset	639 newcount = other_count if count < other_count else count
50920 191b7b3ddf4f Build-outs for Counter() class: Raymond Hettinger <python@rcn.com> parents: 50761 diff changeset	640 if newcount > 0:
191b7b3ddf4f Build-outs for Counter() class: Raymond Hettinger <python@rcn.com> parents: 50761 diff changeset	641 result[elem] = newcount
69416 0c7ea87f676a Rework multiset methods to use less memory and to make fewer calls to __hash__. Raymond Hettinger <python@rcn.com> parents: 69378 diff changeset	642 for elem, count in other.items():
0c7ea87f676a Rework multiset methods to use less memory and to make fewer calls to __hash__. Raymond Hettinger <python@rcn.com> parents: 69378 diff changeset	643 if elem not in self and count > 0:
0c7ea87f676a Rework multiset methods to use less memory and to make fewer calls to __hash__. Raymond Hettinger <python@rcn.com> parents: 69378 diff changeset	644 result[elem] = count
50920 191b7b3ddf4f Build-outs for Counter() class: Raymond Hettinger <python@rcn.com> parents: 50761 diff changeset	645 return result
191b7b3ddf4f Build-outs for Counter() class: Raymond Hettinger <python@rcn.com> parents: 50761 diff changeset	646
191b7b3ddf4f Build-outs for Counter() class: Raymond Hettinger <python@rcn.com> parents: 50761 diff changeset	647 def __and__(self, other):
191b7b3ddf4f Build-outs for Counter() class: Raymond Hettinger <python@rcn.com> parents: 50761 diff changeset	648 ''' Intersection is the minimum of corresponding counts.
191b7b3ddf4f Build-outs for Counter() class: Raymond Hettinger <python@rcn.com> parents: 50761 diff changeset	649
191b7b3ddf4f Build-outs for Counter() class: Raymond Hettinger <python@rcn.com> parents: 50761 diff changeset	650 >>> Counter('abbb') & Counter('bcc')
191b7b3ddf4f Build-outs for Counter() class: Raymond Hettinger <python@rcn.com> parents: 50761 diff changeset	651 Counter({'b': 1})
191b7b3ddf4f Build-outs for Counter() class: Raymond Hettinger <python@rcn.com> parents: 50761 diff changeset	652
191b7b3ddf4f Build-outs for Counter() class: Raymond Hettinger <python@rcn.com> parents: 50761 diff changeset	653 '''
191b7b3ddf4f Build-outs for Counter() class: Raymond Hettinger <python@rcn.com> parents: 50761 diff changeset	654 if not isinstance(other, Counter):
191b7b3ddf4f Build-outs for Counter() class: Raymond Hettinger <python@rcn.com> parents: 50761 diff changeset	655 return NotImplemented
191b7b3ddf4f Build-outs for Counter() class: Raymond Hettinger <python@rcn.com> parents: 50761 diff changeset	656 result = Counter()
69416 0c7ea87f676a Rework multiset methods to use less memory and to make fewer calls to __hash__. Raymond Hettinger <python@rcn.com> parents: 69378 diff changeset	657 for elem, count in self.items():
0c7ea87f676a Rework multiset methods to use less memory and to make fewer calls to __hash__. Raymond Hettinger <python@rcn.com> parents: 69378 diff changeset	658 other_count = other[elem]
0c7ea87f676a Rework multiset methods to use less memory and to make fewer calls to __hash__. Raymond Hettinger <python@rcn.com> parents: 69378 diff changeset	659 newcount = count if count < other_count else other_count
50920 191b7b3ddf4f Build-outs for Counter() class: Raymond Hettinger <python@rcn.com> parents: 50761 diff changeset	660 if newcount > 0:
191b7b3ddf4f Build-outs for Counter() class: Raymond Hettinger <python@rcn.com> parents: 50761 diff changeset	661 result[elem] = newcount
191b7b3ddf4f Build-outs for Counter() class: Raymond Hettinger <python@rcn.com> parents: 50761 diff changeset	662 return result
40992 b46c6d27625e Add collections.NamedTuple Raymond Hettinger <python@rcn.com> parents: 40989 diff changeset	663
b46c6d27625e Add collections.NamedTuple Raymond Hettinger <python@rcn.com> parents: 40989 diff changeset	664
b46c6d27625e Add collections.NamedTuple Raymond Hettinger <python@rcn.com> parents: 40989 diff changeset	665 if __name__ == '__main__':
43377 2e7dd201ea1d Sync-up named tuples with the latest version of the ASPN recipe. Raymond Hettinger <python@rcn.com> parents: 41801 diff changeset	666 # verify that instances can be pickled
40992 b46c6d27625e Add collections.NamedTuple Raymond Hettinger <python@rcn.com> parents: 40989 diff changeset	667 from cPickle import loads, dumps
43654 a0983f55c957 Shorter name for namedtuple() Raymond Hettinger <python@rcn.com> parents: 43579 diff changeset	668 Point = namedtuple('Point', 'x, y', True)
40992 b46c6d27625e Add collections.NamedTuple Raymond Hettinger <python@rcn.com> parents: 40989 diff changeset	669 p = Point(x=10, y=20)
b46c6d27625e Add collections.NamedTuple Raymond Hettinger <python@rcn.com> parents: 40989 diff changeset	670 assert p == loads(dumps(p))
b46c6d27625e Add collections.NamedTuple Raymond Hettinger <python@rcn.com> parents: 40989 diff changeset	671
43856 98795738b4c2 Accept Issac Morland's suggestion for __replace__ to allow multiple replacements Raymond Hettinger <python@rcn.com> parents: 43852 diff changeset	672 # test and demonstrate ability to override methods
44549 a8697afbf17e Add subclassing example to docs for named tuples. Raymond Hettinger <python@rcn.com> parents: 44546 diff changeset	673 class Point(namedtuple('Point', 'x y')):
44622 c3113914e66e Examples for named tuple subclassing should include __slots__ Raymond Hettinger <python@rcn.com> parents: 44590 diff changeset	674 __slots__ = ()
44549 a8697afbf17e Add subclassing example to docs for named tuples. Raymond Hettinger <python@rcn.com> parents: 44546 diff changeset	675 @property
a8697afbf17e Add subclassing example to docs for named tuples. Raymond Hettinger <python@rcn.com> parents: 44546 diff changeset	676 def hypot(self):
a8697afbf17e Add subclassing example to docs for named tuples. Raymond Hettinger <python@rcn.com> parents: 44546 diff changeset	677 return (self.x 2 + self.y 2) ** 0.5
44582 c75d360ab87b Cleanup named tuple subclassing example. Raymond Hettinger <python@rcn.com> parents: 44552 diff changeset	678 def __str__(self):
44625 69f495082412 Neaten-up the named tuple docs Raymond Hettinger <python@rcn.com> parents: 44623 diff changeset	679 return 'Point: x=%6.3f y=%6.3f hypot=%6.3f' % (self.x, self.y, self.hypot)
44549 a8697afbf17e Add subclassing example to docs for named tuples. Raymond Hettinger <python@rcn.com> parents: 44546 diff changeset	680
44622 c3113914e66e Examples for named tuple subclassing should include __slots__ Raymond Hettinger <python@rcn.com> parents: 44590 diff changeset	681 for p in Point(3, 4), Point(14, 5/7.):
44582 c75d360ab87b Cleanup named tuple subclassing example. Raymond Hettinger <python@rcn.com> parents: 44552 diff changeset	682 print p
43856 98795738b4c2 Accept Issac Morland's suggestion for __replace__ to allow multiple replacements Raymond Hettinger <python@rcn.com> parents: 43852 diff changeset	683
44552 b6ea52993cae Add another named tuple subclassing example. Raymond Hettinger <python@rcn.com> parents: 44550 diff changeset	684 class Point(namedtuple('Point', 'x y')):
b6ea52993cae Add another named tuple subclassing example. Raymond Hettinger <python@rcn.com> parents: 44550 diff changeset	685 'Point class with optimized _make() and _replace() without error-checking'
44622 c3113914e66e Examples for named tuple subclassing should include __slots__ Raymond Hettinger <python@rcn.com> parents: 44590 diff changeset	686 __slots__ = ()
44552 b6ea52993cae Add another named tuple subclassing example. Raymond Hettinger <python@rcn.com> parents: 44550 diff changeset	687 _make = classmethod(tuple.__new__)
b6ea52993cae Add another named tuple subclassing example. Raymond Hettinger <python@rcn.com> parents: 44550 diff changeset	688 def _replace(self, _map=map, **kwds):
44585 42cf59ccce66 Use get() instead of pop() for the optimized version of _replace(). Raymond Hettinger <python@rcn.com> parents: 44582 diff changeset	689 return self._make(_map(kwds.get, ('x', 'y'), self))
44552 b6ea52993cae Add another named tuple subclassing example. Raymond Hettinger <python@rcn.com> parents: 44550 diff changeset	690
b6ea52993cae Add another named tuple subclassing example. Raymond Hettinger <python@rcn.com> parents: 44550 diff changeset	691 print Point(11, 22)._replace(x=100)
b6ea52993cae Add another named tuple subclassing example. Raymond Hettinger <python@rcn.com> parents: 44550 diff changeset	692
44623 dbafcd827979 Clarify how to add a field to a named tuple. Raymond Hettinger <python@rcn.com> parents: 44622 diff changeset	693 Point3D = namedtuple('Point3D', Point._fields + ('z',))
dbafcd827979 Clarify how to add a field to a named tuple. Raymond Hettinger <python@rcn.com> parents: 44622 diff changeset	694 print Point3D.__doc__
dbafcd827979 Clarify how to add a field to a named tuple. Raymond Hettinger <python@rcn.com> parents: 44622 diff changeset	695
40992 b46c6d27625e Add collections.NamedTuple Raymond Hettinger <python@rcn.com> parents: 40989 diff changeset	696 import doctest
43654 a0983f55c957 Shorter name for namedtuple() Raymond Hettinger <python@rcn.com> parents: 43579 diff changeset	697 TestResults = namedtuple('TestResults', 'failed attempted')
40992 b46c6d27625e Add collections.NamedTuple Raymond Hettinger <python@rcn.com> parents: 40989 diff changeset	698 print TestResults(*doctest.testmod())

Mercurial > cpython-lru_cache-weakref

annotate Lib/collections.py @ 79675:c0a2294de787 2.7