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