![]()
1 '''This module implements specialized container datatypes providing
2 alternatives to Python's general purpose built-in containers, dict,
3 list, set, and tuple.
4
5 * namedtuple factory function for creating tuple subclasses with named fields
6 * deque list-like container with fast appends and pops on either end
7 * ChainMap dict-like class for creating a single view of multiple mappings
8 * Counter dict subclass for counting hashable objects
9 * OrderedDict dict subclass that remembers the order entries were added
10 * defaultdict dict subclass that calls a factory function to supply missing values
11 * UserDict wrapper around dictionary objects for easier dict subclassing
12 * UserList wrapper around list objects for easier list subclassing
13 * UserString wrapper around string objects for easier string subclassing
14
15 '''
16
17 __all__ = ['deque', 'defaultdict', 'namedtuple', 'UserDict', 'UserList',
18 'UserString', 'Counter', 'OrderedDict', 'ChainMap']
19
20 # For backwards compatibility, continue to make the collections ABCs
21 # available through the collections module.
22 from _collections_abc import *
23 import _collections_abc
24 __all__ += _collections_abc.__all__
25
26 from operator import itemgetter as _itemgetter, eq as _eq
27 from keyword import iskeyword as _iskeyword
28 import sys as _sys
29 import heapq as _heapq
30 from _weakref import proxy as _proxy
31 from itertools import repeat as _repeat, chain as _chain, starmap as _starmap
32 from reprlib import recursive_repr as _recursive_repr
33
34 try:
35 from _collections import deque
36 except ImportError:
37 pass
38 else:
39 MutableSequence.register(deque)
40
41 try:
42 from _collections import defaultdict
43 except ImportError:
44 pass
45
46
47 ################################################################################
48 ### OrderedDict
49 ################################################################################
50
51 class _OrderedDictKeysView(KeysView):
52
53 def __reversed__(self):
54 yield from reversed(self._mapping)
55
56 class _OrderedDictItemsView(ItemsView):
57
58 def __reversed__(self):
59 for key in reversed(self._mapping):
60 yield (key, self._mapping[key])
61
62 class _OrderedDictValuesView(ValuesView):
63
64 def __reversed__(self):
65 for key in reversed(self._mapping):
66 yield self._mapping[key]
67
68 class _Link(object):
69 __slots__ = 'prev', 'next', 'key', '__weakref__'
70
71 class OrderedDict(dict):
72 'Dictionary that remembers insertion order'
73 # An inherited dict maps keys to values.
74 # The inherited dict provides __getitem__, __len__, __contains__, and get.
75 # The remaining methods are order-aware.
76 # Big-O running times for all methods are the same as regular dictionaries.
77
78 # The internal self.__map dict maps keys to links in a doubly linked list.
79 # The circular doubly linked list starts and ends with a sentinel element.
80 # The sentinel element never gets deleted (this simplifies the algorithm).
81 # The sentinel is in self.__hardroot with a weakref proxy in self.__root.
82 # The prev links are weakref proxies (to prevent circular references).
83 # Individual links are kept alive by the hard reference in self.__map.
84 # Those hard references disappear when a key is deleted from an OrderedDict.
85
86 def __init__(*args, **kwds):
87 '''Initialize an ordered dictionary. The signature is the same as
88 regular dictionaries. Keyword argument order is preserved.
89 '''
90 if not args:
91 raise TypeError("descriptor '__init__' of 'OrderedDict' object "
92 "needs an argument")
93 self, *args = args
94 if len(args) > 1:
95 raise TypeError('expected at most 1 arguments, got %d' % len(args))
96 try:
97 self.__root
98 except AttributeError:
99 self.__hardroot = _Link()
100 self.__root = root = _proxy(self.__hardroot)
101 root.prev = root.next = root
102 self.__map = {}
103 self.__update(*args, **kwds)
104
105 def __setitem__(self, key, value,
106 dict_setitem=dict.__setitem__, proxy=_proxy, Link=_Link):
107 'od.__setitem__(i, y) <==> od[i]=y'
108 # Setting a new item creates a new link at the end of the linked list,
109 # and the inherited dictionary is updated with the new key/value pair.
110 if key not in self:
111 self.__map[key] = link = Link()
112 root = self.__root
113 last = root.prev
114 link.prev, link.next, link.key = last, root, key
115 last.next = link
116 root.prev = proxy(link)
117 dict_setitem(self, key, value)
118
119 def __delitem__(self, key, dict_delitem=dict.__delitem__):
120 'od.__delitem__(y) <==> del od[y]'
121 # Deleting an existing item uses self.__map to find the link which gets
122 # removed by updating the links in the predecessor and successor nodes.
123 dict_delitem(self, key)
124 link = self.__map.pop(key)
125 link_prev = link.prev
126 link_next = link.next
127 link_prev.next = link_next
128 link_next.prev = link_prev
129 link.prev = None
130 link.next = None
131
132 def __iter__(self):
133 'od.__iter__() <==> iter(od)'
134 # Traverse the linked list in order.
135 root = self.__root
136 curr = root.next
137 while curr is not root:
138 yield curr.key
139 curr = curr.next
140
141 def __reversed__(self):
142 'od.__reversed__() <==> reversed(od)'
143 # Traverse the linked list in reverse order.
144 root = self.__root
145 curr = root.prev
146 while curr is not root:
147 yield curr.key
148 curr = curr.prev
149
150 def clear(self):
151 'od.clear() -> None. Remove all items from od.'
152 root = self.__root
153 root.prev = root.next = root
154 self.__map.clear()
155 dict.clear(self)
156
157 def popitem(self, last=True):
158 '''Remove and return a (key, value) pair from the dictionary.
159
160 Pairs are returned in LIFO order if last is true or FIFO order if false.
161 '''
162 if not self:
163 raise KeyError('dictionary is empty')
164 root = self.__root
165 if last:
166 link = root.prev
167 link_prev = link.prev
168 link_prev.next = root
169 root.prev = link_prev
170 else:
171 link = root.next
172 link_next = link.next
173 root.next = link_next
174 link_next.prev = root
175 key = link.key
176 del self.__map[key]
177 value = dict.pop(self, key)
178 return key, value
179
180 def move_to_end(self, key, last=True):
181 '''Move an existing element to the end (or beginning if last==False).
182
183 Raises KeyError if the element does not exist.
184 When last=True, acts like a fast version of self[key]=self.pop(key).
185
186 '''
187 link = self.__map[key]
188 link_prev = link.prev
189 link_next = link.next
190 soft_link = link_next.prev
191 link_prev.next = link_next
192 link_next.prev = link_prev
193 root = self.__root
194 if last:
195 last = root.prev
196 link.prev = last
197 link.next = root
198 root.prev = soft_link
199 last.next = link
200 else:
201 first = root.next
202 link.prev = root
203 link.next = first
204 first.prev = soft_link
205 root.next = link
206
207 def __sizeof__(self):
208 sizeof = _sys.getsizeof
209 n = len(self) + 1 # number of links including root
210 size = sizeof(self.__dict__) # instance dictionary
211 size += sizeof(self.__map) * 2 # internal dict and inherited dict
212 size += sizeof(self.__hardroot) * n # link objects
213 size += sizeof(self.__root) * n # proxy objects
214 return size
215
216 update = __update = MutableMapping.update
217
218 def keys(self):
219 "D.keys() -> a set-like object providing a view on D's keys"
220 return _OrderedDictKeysView(self)
221
222 def items(self):
223 "D.items() -> a set-like object providing a view on D's items"
224 return _OrderedDictItemsView(self)
225
226 def values(self):
227 "D.values() -> an object providing a view on D's values"
228 return _OrderedDictValuesView(self)
229
230 __ne__ = MutableMapping.__ne__
231
232 __marker = object()
233
234 def pop(self, key, default=__marker):
235 '''od.pop(k[,d]) -> v, remove specified key and return the corresponding
236 value. If key is not found, d is returned if given, otherwise KeyError
237 is raised.
238
239 '''
240 if key in self:
241 result = self[key]
242 del self[key]
243 return result
244 if default is self.__marker:
245 raise KeyError(key)
246 return default
247
248 def setdefault(self, key, default=None):
249 'od.setdefault(k[,d]) -> od.get(k,d), also set od[k]=d if k not in od'
250 if key in self:
251 return self[key]
252 self[key] = default
253 return default
254
255 @_recursive_repr()
256 def __repr__(self):
257 'od.__repr__() <==> repr(od)'
258 if not self:
259 return '%s()' % (self.__class__.__name__,)
260 return '%s(%r)' % (self.__class__.__name__, list(self.items()))
261
262 def __reduce__(self):
263 'Return state information for pickling'
264 inst_dict = vars(self).copy()
265 for k in vars(OrderedDict()):
266 inst_dict.pop(k, None)
267 return self.__class__, (), inst_dict or None, None, iter(self.items())
268
269 def copy(self):
270 'od.copy() -> a shallow copy of od'
271 return self.__class__(self)
272
273 @classmethod
274 def fromkeys(cls, iterable, value=None):
275 '''OD.fromkeys(S[, v]) -> New ordered dictionary with keys from S.
276 If not specified, the value defaults to None.
277
278 '''
279 self = cls()
280 for key in iterable:
281 self[key] = value
282 return self
283
284 def __eq__(self, other):
285 '''od.__eq__(y) <==> od==y. Comparison to another OD is order-sensitive
286 while comparison to a regular mapping is order-insensitive.
287
288 '''
289 if isinstance(other, OrderedDict):
290 return dict.__eq__(self, other) and all(map(_eq, self, other))
291 return dict.__eq__(self, other)
292
293
294 try:
295 from _collections import OrderedDict
296 except ImportError:
297 # Leave the pure Python version in place.
298 pass
299
300
301 ################################################################################
302 ### namedtuple
303 ################################################################################
304
305 _class_template = """
306 from builtins import property as _property, tuple as _tuple
307 from operator import itemgetter as _itemgetter
308 from collections import OrderedDict
309
310 class {typename}(tuple):
311 '{typename}({arg_list})'
312
313 __slots__ = ()
314
315 _fields = {field_names!r}
316
317 def __new__(_cls, {arg_list}):
318 'Create new instance of {typename}({arg_list})'
319 return _tuple.__new__(_cls, ({arg_list}))
320
321 @classmethod
322 def _make(cls, iterable, new=tuple.__new__, len=len):
323 'Make a new {typename} object from a sequence or iterable'
324 result = new(cls, iterable)
325 if len(result) != {num_fields:d}:
326 raise TypeError('Expected {num_fields:d} arguments, got %d' % len(result))
327 return result
328
329 def _replace(_self, **kwds):
330 'Return a new {typename} object replacing specified fields with new values'
331 result = _self._make(map(kwds.pop, {field_names!r}, _self))
332 if kwds:
333 raise ValueError('Got unexpected field names: %r' % list(kwds))
334 return result
335
336 def __repr__(self):
337 'Return a nicely formatted representation string'
338 return self.__class__.__name__ + '({repr_fmt})' % self
339
340 def _asdict(self):
341 'Return a new OrderedDict which maps field names to their values.'
342 return OrderedDict(zip(self._fields, self))
343
344 def __getnewargs__(self):
345 'Return self as a plain tuple. Used by copy and pickle.'
346 return tuple(self)
347
348 {field_defs}
349 """
350
351 _repr_template = '{name}=%r'
352
353 _field_template = '''
354 {name} = _property(_itemgetter({index:d}), doc='Alias for field number {index:d}')
355 '''
356
357 def namedtuple(typename, field_names, *, verbose=False, rename=False, module=None):
358 """Returns a new subclass of tuple with named fields.
359
360 >>> Point = namedtuple('Point', ['x', 'y'])
361 >>> Point.__doc__ # docstring for the new class
362 'Point(x, y)'
363 >>> p = Point(11, y=22) # instantiate with positional args or keywords
364 >>> p[0] + p[1] # indexable like a plain tuple
365 33
366 >>> x, y = p # unpack like a regular tuple
367 >>> x, y
368 (11, 22)
369 >>> p.x + p.y # fields also accessible by name
370 33
371 >>> d = p._asdict() # convert to a dictionary
372 >>> d['x']
373 11
374 >>> Point(**d) # convert from a dictionary
375 Point(x=11, y=22)
376 >>> p._replace(x=100) # _replace() is like str.replace() but targets named fields
377 Point(x=100, y=22)
378
379 """
380
381 # Validate the field names. At the user's option, either generate an error
382 # message or automatically replace the field name with a valid name.
383 if isinstance(field_names, str):
384 field_names = field_names.replace(',', ' ').split()
385 field_names = list(map(str, field_names))
386 typename = str(typename)
387 if rename:
388 seen = set()
389 for index, name in enumerate(field_names):
390 if (not name.isidentifier()
391 or _iskeyword(name)
392 or name.startswith('_')
393 or name in seen):
394 field_names[index] = '_%d' % index
395 seen.add(name)
396 for name in [typename] + field_names:
397 if type(name) is not str:
398 raise TypeError('Type names and field names must be strings')
399 if not name.isidentifier():
400 raise ValueError('Type names and field names must be valid '
401 'identifiers: %r' % name)
402 if _iskeyword(name):
403 raise ValueError('Type names and field names cannot be a '
404 'keyword: %r' % name)
405 seen = set()
406 for name in field_names:
407 if name.startswith('_') and not rename:
408 raise ValueError('Field names cannot start with an underscore: '
409 '%r' % name)
410 if name in seen:
411 raise ValueError('Encountered duplicate field name: %r' % name)
412 seen.add(name)
413
414 # Fill-in the class template
415 class_definition = _class_template.format(
416 typename = typename,
417 field_names = tuple(field_names),
418 num_fields = len(field_names),
419 arg_list = repr(tuple(field_names)).replace("'", "")[1:-1],
420 repr_fmt = ', '.join(_repr_template.format(name=name)
421 for name in field_names),
422 field_defs = '
'.join(_field_template.format(index=index, name=name)
423 for index, name in enumerate(field_names))
424 )
425
426 # Execute the template string in a temporary namespace and support
427 # tracing utilities by setting a value for frame.f_globals['__name__']
428 namespace = dict(__name__='namedtuple_%s' % typename)
429 exec(class_definition, namespace)
430 result = namespace[typename]
431 result._source = class_definition
432 if verbose:
433 print(result._source)
434
435 # For pickling to work, the __module__ variable needs to be set to the frame
436 # where the named tuple is created. Bypass this step in environments where
437 # sys._getframe is not defined (Jython for example) or sys._getframe is not
438 # defined for arguments greater than 0 (IronPython), or where the user has
439 # specified a particular module.
440 if module is None:
441 try:
442 module = _sys._getframe(1).f_globals.get('__name__', '__main__')
443 except (AttributeError, ValueError):
444 pass
445 if module is not None:
446 result.__module__ = module
447
448 return result
449
450
451 ########################################################################
452 ### Counter
453 ########################################################################
454
455 def _count_elements(mapping, iterable):
456 'Tally elements from the iterable.'
457 mapping_get = mapping.get
458 for elem in iterable:
459 mapping[elem] = mapping_get(elem, 0) + 1
460
461 try: # Load C helper function if available
462 from _collections import _count_elements
463 except ImportError:
464 pass
465
466 class Counter(dict):
467 '''Dict subclass for counting hashable items. Sometimes called a bag
468 or multiset. Elements are stored as dictionary keys and their counts
469 are stored as dictionary values.
470
471 >>> c = Counter('abcdeabcdabcaba') # count elements from a string
472
473 >>> c.most_common(3) # three most common elements
474 [('a', 5), ('b', 4), ('c', 3)]
475 >>> sorted(c) # list all unique elements
476 ['a', 'b', 'c', 'd', 'e']
477 >>> ''.join(sorted(c.elements())) # list elements with repetitions
478 'aaaaabbbbcccdde'
479 >>> sum(c.values()) # total of all counts
480 15
481
482 >>> c['a'] # count of letter 'a'
483 5
484 >>> for elem in 'shazam': # update counts from an iterable
485 ... c[elem] += 1 # by adding 1 to each element's count
486 >>> c['a'] # now there are seven 'a'
487 7
488 >>> del c['b'] # remove all 'b'
489 >>> c['b'] # now there are zero 'b'
490 0
491
492 >>> d = Counter('simsalabim') # make another counter
493 >>> c.update(d) # add in the second counter
494 >>> c['a'] # now there are nine 'a'
495 9
496
497 >>> c.clear() # empty the counter
498 >>> c
499 Counter()
500
501 Note: If a count is set to zero or reduced to zero, it will remain
502 in the counter until the entry is deleted or the counter is cleared:
503
504 >>> c = Counter('aaabbc')
505 >>> c['b'] -= 2 # reduce the count of 'b' by two
506 >>> c.most_common() # 'b' is still in, but its count is zero
507 [('a', 3), ('c', 1), ('b', 0)]
508
509 '''
510 # References:
511 # http://en.wikipedia.org/wiki/Multiset
512 # http://www.gnu.org/software/smalltalk/manual-base/html_node/Bag.html
513 # http://www.demo2s.com/Tutorial/Cpp/0380__set-multiset/Catalog0380__set-multiset.htm
514 # http://code.activestate.com/recipes/259174/
515 # Knuth, TAOCP Vol. II section 4.6.3
516
517 def __init__(*args, **kwds):
518 '''Create a new, empty Counter object. And if given, count elements
519 from an input iterable. Or, initialize the count from another mapping
520 of elements to their counts.
521
522 >>> c = Counter() # a new, empty counter
523 >>> c = Counter('gallahad') # a new counter from an iterable
524 >>> c = Counter({'a': 4, 'b': 2}) # a new counter from a mapping
525 >>> c = Counter(a=4, b=2) # a new counter from keyword args
526
527 '''
528 if not args:
529 raise TypeError("descriptor '__init__' of 'Counter' object "
530 "needs an argument")
531 self, *args = args
532 if len(args) > 1:
533 raise TypeError('expected at most 1 arguments, got %d' % len(args))
534 super(Counter, self).__init__()
535 self.update(*args, **kwds)
536
537 def __missing__(self, key):
538 'The count of elements not in the Counter is zero.'
539 # Needed so that self[missing_item] does not raise KeyError
540 return 0
541
542 def most_common(self, n=None):
543 '''List the n most common elements and their counts from the most
544 common to the least. If n is None, then list all element counts.
545
546 >>> Counter('abcdeabcdabcaba').most_common(3)
547 [('a', 5), ('b', 4), ('c', 3)]
548
549 '''
550 # Emulate Bag.sortedByCount from Smalltalk
551 if n is None:
552 return sorted(self.items(), key=_itemgetter(1), reverse=True)
553 return _heapq.nlargest(n, self.items(), key=_itemgetter(1))
554
555 def elements(self):
556 '''Iterator over elements repeating each as many times as its count.
557
558 >>> c = Counter('ABCABC')
559 >>> sorted(c.elements())
560 ['A', 'A', 'B', 'B', 'C', 'C']
561
562 # Knuth's example for prime factors of 1836: 2**2 * 3**3 * 17**1
563 >>> prime_factors = Counter({2: 2, 3: 3, 17: 1})
564 >>> product = 1
565 >>> for factor in prime_factors.elements(): # loop over factors
566 ... product *= factor # and multiply them
567 >>> product
568 1836
569
570 Note, if an element's count has been set to zero or is a negative
571 number, elements() will ignore it.
572
573 '''
574 # Emulate Bag.do from Smalltalk and Multiset.begin from C++.
575 return _chain.from_iterable(_starmap(_repeat, self.items()))
576
577 # Override dict methods where necessary
578
579 @classmethod
580 def fromkeys(cls, iterable, v=None):
581 # There is no equivalent method for counters because setting v=1
582 # means that no element can have a count greater than one.
583 raise NotImplementedError(
584 'Counter.fromkeys() is undefined. Use Counter(iterable) instead.')
585
586 def update(*args, **kwds):
587 '''Like dict.update() but add counts instead of replacing them.
588
589 Source can be an iterable, a dictionary, or another Counter instance.
590
591 >>> c = Counter('which')
592 >>> c.update('witch') # add elements from another iterable
593 >>> d = Counter('watch')
594 >>> c.update(d) # add elements from another counter
595 >>> c['h'] # four 'h' in which, witch, and watch
596 4
597
598 '''
599 # The regular dict.update() operation makes no sense here because the
600 # replace behavior results in the some of original untouched counts
601 # being mixed-in with all of the other counts for a mismash that
602 # doesn't have a straight-forward interpretation in most counting
603 # contexts. Instead, we implement straight-addition. Both the inputs
604 # and outputs are allowed to contain zero and negative counts.
605
606 if not args:
607 raise TypeError("descriptor 'update' of 'Counter' object "
608 "needs an argument")
609 self, *args = args
610 if len(args) > 1:
611 raise TypeError('expected at most 1 arguments, got %d' % len(args))
612 iterable = args[0] if args else None
613 if iterable is not None:
614 if isinstance(iterable, Mapping):
615 if self:
616 self_get = self.get
617 for elem, count in iterable.items():
618 self[elem] = count + self_get(elem, 0)
619 else:
620 super(Counter, self).update(iterable) # fast path when counter is empty
621 else:
622 _count_elements(self, iterable)
623 if kwds:
624 self.update(kwds)
625
626 def subtract(*args, **kwds):
627 '''Like dict.update() but subtracts counts instead of replacing them.
628 Counts can be reduced below zero. Both the inputs and outputs are
629 allowed to contain zero and negative counts.
630
631 Source can be an iterable, a dictionary, or another Counter instance.
632
633 >>> c = Counter('which')
634 >>> c.subtract('witch') # subtract elements from another iterable
635 >>> c.subtract(Counter('watch')) # subtract elements from another counter
636 >>> c['h'] # 2 in which, minus 1 in witch, minus 1 in watch
637 0
638 >>> c['w'] # 1 in which, minus 1 in witch, minus 1 in watch
639 -1
640
641 '''
642 if not args:
643 raise TypeError("descriptor 'subtract' of 'Counter' object "
644 "needs an argument")
645 self, *args = args
646 if len(args) > 1:
647 raise TypeError('expected at most 1 arguments, got %d' % len(args))
648 iterable = args[0] if args else None
649 if iterable is not None:
650 self_get = self.get
651 if isinstance(iterable, Mapping):
652 for elem, count in iterable.items():
653 self[elem] = self_get(elem, 0) - count
654 else:
655 for elem in iterable:
656 self[elem] = self_get(elem, 0) - 1
657 if kwds:
658 self.subtract(kwds)
659
660 def copy(self):
661 'Return a shallow copy.'
662 return self.__class__(self)
663
664 def __reduce__(self):
665 return self.__class__, (dict(self),)
666
667 def __delitem__(self, elem):
668 'Like dict.__delitem__() but does not raise KeyError for missing values.'
669 if elem in self:
670 super().__delitem__(elem)
671
672 def __repr__(self):
673 if not self:
674 return '%s()' % self.__class__.__name__
675 try:
676 items = ', '.join(map('%r: %r'.__mod__, self.most_common()))
677 return '%s({%s})' % (self.__class__.__name__, items)
678 except TypeError:
679 # handle case where values are not orderable
680 return '{0}({1!r})'.format(self.__class__.__name__, dict(self))
681
682 # Multiset-style mathematical operations discussed in:
683 # Knuth TAOCP Volume II section 4.6.3 exercise 19
684 # and at http://en.wikipedia.org/wiki/Multiset
685 #
686 # Outputs guaranteed to only include positive counts.
687 #
688 # To strip negative and zero counts, add-in an empty counter:
689 # c += Counter()
690
691 def __add__(self, other):
692 '''Add counts from two counters.
693
694 >>> Counter('abbb') + Counter('bcc')
695 Counter({'b': 4, 'c': 2, 'a': 1})
696
697 '''
698 if not isinstance(other, Counter):
699 return NotImplemented
700 result = Counter()
701 for elem, count in self.items():
702 newcount = count + other[elem]
703 if newcount > 0:
704 result[elem] = newcount
705 for elem, count in other.items():
706 if elem not in self and count > 0:
707 result[elem] = count
708 return result
709
710 def __sub__(self, other):
711 ''' Subtract count, but keep only results with positive counts.
712
713 >>> Counter('abbbc') - Counter('bccd')
714 Counter({'b': 2, 'a': 1})
715
716 '''
717 if not isinstance(other, Counter):
718 return NotImplemented
719 result = Counter()
720 for elem, count in self.items():
721 newcount = count - other[elem]
722 if newcount > 0:
723 result[elem] = newcount
724 for elem, count in other.items():
725 if elem not in self and count < 0:
726 result[elem] = 0 - count
727 return result
728
729 def __or__(self, other):
730 '''Union is the maximum of value in either of the input counters.
731
732 >>> Counter('abbb') | Counter('bcc')
733 Counter({'b': 3, 'c': 2, 'a': 1})
734
735 '''
736 if not isinstance(other, Counter):
737 return NotImplemented
738 result = Counter()
739 for elem, count in self.items():
740 other_count = other[elem]
741 newcount = other_count if count < other_count else count
742 if newcount > 0:
743 result[elem] = newcount
744 for elem, count in other.items():
745 if elem not in self and count > 0:
746 result[elem] = count
747 return result
748
749 def __and__(self, other):
750 ''' Intersection is the minimum of corresponding counts.
751
752 >>> Counter('abbb') & Counter('bcc')
753 Counter({'b': 1})
754
755 '''
756 if not isinstance(other, Counter):
757 return NotImplemented
758 result = Counter()
759 for elem, count in self.items():
760 other_count = other[elem]
761 newcount = count if count < other_count else other_count
762 if newcount > 0:
763 result[elem] = newcount
764 return result
765
766 def __pos__(self):
767 'Adds an empty counter, effectively stripping negative and zero counts'
768 result = Counter()
769 for elem, count in self.items():
770 if count > 0:
771 result[elem] = count
772 return result
773
774 def __neg__(self):
775 '''Subtracts from an empty counter. Strips positive and zero counts,
776 and flips the sign on negative counts.
777
778 '''
779 result = Counter()
780 for elem, count in self.items():
781 if count < 0:
782 result[elem] = 0 - count
783 return result
784
785 def _keep_positive(self):
786 '''Internal method to strip elements with a negative or zero count'''
787 nonpositive = [elem for elem, count in self.items() if not count > 0]
788 for elem in nonpositive:
789 del self[elem]
790 return self
791
792 def __iadd__(self, other):
793 '''Inplace add from another counter, keeping only positive counts.
794
795 >>> c = Counter('abbb')
796 >>> c += Counter('bcc')
797 >>> c
798 Counter({'b': 4, 'c': 2, 'a': 1})
799
800 '''
801 for elem, count in other.items():
802 self[elem] += count
803 return self._keep_positive()
804
805 def __isub__(self, other):
806 '''Inplace subtract counter, but keep only results with positive counts.
807
808 >>> c = Counter('abbbc')
809 >>> c -= Counter('bccd')
810 >>> c
811 Counter({'b': 2, 'a': 1})
812
813 '''
814 for elem, count in other.items():
815 self[elem] -= count
816 return self._keep_positive()
817
818 def __ior__(self, other):
819 '''Inplace union is the maximum of value from either counter.
820
821 >>> c = Counter('abbb')
822 >>> c |= Counter('bcc')
823 >>> c
824 Counter({'b': 3, 'c': 2, 'a': 1})
825
826 '''
827 for elem, other_count in other.items():
828 count = self[elem]
829 if other_count > count:
830 self[elem] = other_count
831 return self._keep_positive()
832
833 def __iand__(self, other):
834 '''Inplace intersection is the minimum of corresponding counts.
835
836 >>> c = Counter('abbb')
837 >>> c &= Counter('bcc')
838 >>> c
839 Counter({'b': 1})
840
841 '''
842 for elem, count in self.items():
843 other_count = other[elem]
844 if other_count < count:
845 self[elem] = other_count
846 return self._keep_positive()
847
848
849 ########################################################################
850 ### ChainMap
851 ########################################################################
852
853 class ChainMap(MutableMapping):
854 ''' A ChainMap groups multiple dicts (or other mappings) together
855 to create a single, updateable view.
856
857 The underlying mappings are stored in a list. That list is public and can
858 be accessed or updated using the *maps* attribute. There is no other
859 state.
860
861 Lookups search the underlying mappings successively until a key is found.
862 In contrast, writes, updates, and deletions only operate on the first
863 mapping.
864
865 '''
866
867 def __init__(self, *maps):
868 '''Initialize a ChainMap by setting *maps* to the given mappings.
869 If no mappings are provided, a single empty dictionary is used.
870
871 '''
872 self.maps = list(maps) or [{}] # always at least one map
873
874 def __missing__(self, key):
875 raise KeyError(key)
876
877 def __getitem__(self, key):
878 for mapping in self.maps:
879 try:
880 return mapping[key] # can't use 'key in mapping' with defaultdict
881 except KeyError:
882 pass
883 return self.__missing__(key) # support subclasses that define __missing__
884
885 def get(self, key, default=None):
886 return self[key] if key in self else default
887
888 def __len__(self):
889 return len(set().union(*self.maps)) # reuses stored hash values if possible
890
891 def __iter__(self):
892 return iter(set().union(*self.maps))
893
894 def __contains__(self, key):
895 return any(key in m for m in self.maps)
896
897 def __bool__(self):
898 return any(self.maps)
899
900 @_recursive_repr()
901 def __repr__(self):
902 return '{0.__class__.__name__}({1})'.format(
903 self, ', '.join(map(repr, self.maps)))
904
905 @classmethod
906 def fromkeys(cls, iterable, *args):
907 'Create a ChainMap with a single dict created from the iterable.'
908 return cls(dict.fromkeys(iterable, *args))
909
910 def copy(self):
911 'New ChainMap or subclass with a new copy of maps[0] and refs to maps[1:]'
912 return self.__class__(self.maps[0].copy(), *self.maps[1:])
913
914 __copy__ = copy
915
916 def new_child(self, m=None): # like Django's Context.push()
917 '''New ChainMap with a new map followed by all previous maps.
918 If no map is provided, an empty dict is used.
919 '''
920 if m is None:
921 m = {}
922 return self.__class__(m, *self.maps)
923
924 @property
925 def parents(self): # like Django's Context.pop()
926 'New ChainMap from maps[1:].'
927 return self.__class__(*self.maps[1:])
928
929 def __setitem__(self, key, value):
930 self.maps[0][key] = value
931
932 def __delitem__(self, key):
933 try:
934 del self.maps[0][key]
935 except KeyError:
936 raise KeyError('Key not found in the first mapping: {!r}'.format(key))
937
938 def popitem(self):
939 'Remove and return an item pair from maps[0]. Raise KeyError is maps[0] is empty.'
940 try:
941 return self.maps[0].popitem()
942 except KeyError:
943 raise KeyError('No keys found in the first mapping.')
944
945 def pop(self, key, *args):
946 'Remove *key* from maps[0] and return its value. Raise KeyError if *key* not in maps[0].'
947 try:
948 return self.maps[0].pop(key, *args)
949 except KeyError:
950 raise KeyError('Key not found in the first mapping: {!r}'.format(key))
951
952 def clear(self):
953 'Clear maps[0], leaving maps[1:] intact.'
954 self.maps[0].clear()
955
956
957 ################################################################################
958 ### UserDict
959 ################################################################################
960
961 class UserDict(MutableMapping):
962
963 # Start by filling-out the abstract methods
964 def __init__(*args, **kwargs):
965 if not args:
966 raise TypeError("descriptor '__init__' of 'UserDict' object "
967 "needs an argument")
968 self, *args = args
969 if len(args) > 1:
970 raise TypeError('expected at most 1 arguments, got %d' % len(args))
971 if args:
972 dict = args[0]
973 elif 'dict' in kwargs:
974 dict = kwargs.pop('dict')
975 import warnings
976 warnings.warn("Passing 'dict' as keyword argument is deprecated",
977 DeprecationWarning, stacklevel=2)
978 else:
979 dict = None
980 self.data = {}
981 if dict is not None:
982 self.update(dict)
983 if len(kwargs):
984 self.update(kwargs)
985 def __len__(self): return len(self.data)
986 def __getitem__(self, key):
987 if key in self.data:
988 return self.data[key]
989 if hasattr(self.__class__, "__missing__"):
990 return self.__class__.__missing__(self, key)
991 raise KeyError(key)
992 def __setitem__(self, key, item): self.data[key] = item
993 def __delitem__(self, key): del self.data[key]
994 def __iter__(self):
995 return iter(self.data)
996
997 # Modify __contains__ to work correctly when __missing__ is present
998 def __contains__(self, key):
999 return key in self.data
1000
1001 # Now, add the methods in dicts but not in MutableMapping
1002 def __repr__(self): return repr(self.data)
1003 def copy(self):
1004 if self.__class__ is UserDict:
1005 return UserDict(self.data.copy())
1006 import copy
1007 data = self.data
1008 try:
1009 self.data = {}
1010 c = copy.copy(self)
1011 finally:
1012 self.data = data
1013 c.update(self)
1014 return c
1015 @classmethod
1016 def fromkeys(cls, iterable, value=None):
1017 d = cls()
1018 for key in iterable:
1019 d[key] = value
1020 return d
1021
1022
1023
1024 ################################################################################
1025 ### UserList
1026 ################################################################################
1027
1028 class UserList(MutableSequence):
1029 """A more or less complete user-defined wrapper around list objects."""
1030 def __init__(self, initlist=None):
1031 self.data = []
1032 if initlist is not None:
1033 # XXX should this accept an arbitrary sequence?
1034 if type(initlist) == type(self.data):
1035 self.data[:] = initlist
1036 elif isinstance(initlist, UserList):
1037 self.data[:] = initlist.data[:]
1038 else:
1039 self.data = list(initlist)
1040 def __repr__(self): return repr(self.data)
1041 def __lt__(self, other): return self.data < self.__cast(other)
1042 def __le__(self, other): return self.data <= self.__cast(other)
1043 def __eq__(self, other): return self.data == self.__cast(other)
1044 def __gt__(self, other): return self.data > self.__cast(other)
1045 def __ge__(self, other): return self.data >= self.__cast(other)
1046 def __cast(self, other):
1047 return other.data if isinstance(other, UserList) else other
1048 def __contains__(self, item): return item in self.data
1049 def __len__(self): return len(self.data)
1050 def __getitem__(self, i): return self.data[i]
1051 def __setitem__(self, i, item): self.data[i] = item
1052 def __delitem__(self, i): del self.data[i]
1053 def __add__(self, other):
1054 if isinstance(other, UserList):
1055 return self.__class__(self.data + other.data)
1056 elif isinstance(other, type(self.data)):
1057 return self.__class__(self.data + other)
1058 return self.__class__(self.data + list(other))
1059 def __radd__(self, other):
1060 if isinstance(other, UserList):
1061 return self.__class__(other.data + self.data)
1062 elif isinstance(other, type(self.data)):
1063 return self.__class__(other + self.data)
1064 return self.__class__(list(other) + self.data)
1065 def __iadd__(self, other):
1066 if isinstance(other, UserList):
1067 self.data += other.data
1068 elif isinstance(other, type(self.data)):
1069 self.data += other
1070 else:
1071 self.data += list(other)
1072 return self
1073 def __mul__(self, n):
1074 return self.__class__(self.data*n)
1075 __rmul__ = __mul__
1076 def __imul__(self, n):
1077 self.data *= n
1078 return self
1079 def append(self, item): self.data.append(item)
1080 def insert(self, i, item): self.data.insert(i, item)
1081 def pop(self, i=-1): return self.data.pop(i)
1082 def remove(self, item): self.data.remove(item)
1083 def clear(self): self.data.clear()
1084 def copy(self): return self.__class__(self)
1085 def count(self, item): return self.data.count(item)
1086 def index(self, item, *args): return self.data.index(item, *args)
1087 def reverse(self): self.data.reverse()
1088 def sort(self, *args, **kwds): self.data.sort(*args, **kwds)
1089 def extend(self, other):
1090 if isinstance(other, UserList):
1091 self.data.extend(other.data)
1092 else:
1093 self.data.extend(other)
1094
1095
1096
1097 ################################################################################
1098 ### UserString
1099 ################################################################################
1100
1101 class UserString(Sequence):
1102 def __init__(self, seq):
1103 if isinstance(seq, str):
1104 self.data = seq
1105 elif isinstance(seq, UserString):
1106 self.data = seq.data[:]
1107 else:
1108 self.data = str(seq)
1109 def __str__(self): return str(self.data)
1110 def __repr__(self): return repr(self.data)
1111 def __int__(self): return int(self.data)
1112 def __float__(self): return float(self.data)
1113 def __complex__(self): return complex(self.data)
1114 def __hash__(self): return hash(self.data)
1115 def __getnewargs__(self):
1116 return (self.data[:],)
1117
1118 def __eq__(self, string):
1119 if isinstance(string, UserString):
1120 return self.data == string.data
1121 return self.data == string
1122 def __lt__(self, string):
1123 if isinstance(string, UserString):
1124 return self.data < string.data
1125 return self.data < string
1126 def __le__(self, string):
1127 if isinstance(string, UserString):
1128 return self.data <= string.data
1129 return self.data <= string
1130 def __gt__(self, string):
1131 if isinstance(string, UserString):
1132 return self.data > string.data
1133 return self.data > string
1134 def __ge__(self, string):
1135 if isinstance(string, UserString):
1136 return self.data >= string.data
1137 return self.data >= string
1138
1139 def __contains__(self, char):
1140 if isinstance(char, UserString):
1141 char = char.data
1142 return char in self.data
1143
1144 def __len__(self): return len(self.data)
1145 def __getitem__(self, index): return self.__class__(self.data[index])
1146 def __add__(self, other):
1147 if isinstance(other, UserString):
1148 return self.__class__(self.data + other.data)
1149 elif isinstance(other, str):
1150 return self.__class__(self.data + other)
1151 return self.__class__(self.data + str(other))
1152 def __radd__(self, other):
1153 if isinstance(other, str):
1154 return self.__class__(other + self.data)
1155 return self.__class__(str(other) + self.data)
1156 def __mul__(self, n):
1157 return self.__class__(self.data*n)
1158 __rmul__ = __mul__
1159 def __mod__(self, args):
1160 return self.__class__(self.data % args)
1161 def __rmod__(self, format):
1162 return self.__class__(format % args)
1163
1164 # the following methods are defined in alphabetical order:
1165 def capitalize(self): return self.__class__(self.data.capitalize())
1166 def casefold(self):
1167 return self.__class__(self.data.casefold())
1168 def center(self, width, *args):
1169 return self.__class__(self.data.center(width, *args))
1170 def count(self, sub, start=0, end=_sys.maxsize):
1171 if isinstance(sub, UserString):
1172 sub = sub.data
1173 return self.data.count(sub, start, end)
1174 def encode(self, encoding=None, errors=None): # XXX improve this?
1175 if encoding:
1176 if errors:
1177 return self.__class__(self.data.encode(encoding, errors))
1178 return self.__class__(self.data.encode(encoding))
1179 return self.__class__(self.data.encode())
1180 def endswith(self, suffix, start=0, end=_sys.maxsize):
1181 return self.data.endswith(suffix, start, end)
1182 def expandtabs(self, tabsize=8):
1183 return self.__class__(self.data.expandtabs(tabsize))
1184 def find(self, sub, start=0, end=_sys.maxsize):
1185 if isinstance(sub, UserString):
1186 sub = sub.data
1187 return self.data.find(sub, start, end)
1188 def format(self, *args, **kwds):
1189 return self.data.format(*args, **kwds)
1190 def format_map(self, mapping):
1191 return self.data.format_map(mapping)
1192 def index(self, sub, start=0, end=_sys.maxsize):
1193 return self.data.index(sub, start, end)
1194 def isalpha(self): return self.data.isalpha()
1195 def isalnum(self): return self.data.isalnum()
1196 def isdecimal(self): return self.data.isdecimal()
1197 def isdigit(self): return self.data.isdigit()
1198 def isidentifier(self): return self.data.isidentifier()
1199 def islower(self): return self.data.islower()
1200 def isnumeric(self): return self.data.isnumeric()
1201 def isprintable(self): return self.data.isprintable()
1202 def isspace(self): return self.data.isspace()
1203 def istitle(self): return self.data.istitle()
1204 def isupper(self): return self.data.isupper()
1205 def join(self, seq): return self.data.join(seq)
1206 def ljust(self, width, *args):
1207 return self.__class__(self.data.ljust(width, *args))
1208 def lower(self): return self.__class__(self.data.lower())
1209 def lstrip(self, chars=None): return self.__class__(self.data.lstrip(chars))
1210 maketrans = str.maketrans
1211 def partition(self, sep):
1212 return self.data.partition(sep)
1213 def replace(self, old, new, maxsplit=-1):
1214 if isinstance(old, UserString):
1215 old = old.data
1216 if isinstance(new, UserString):
1217 new = new.data
1218 return self.__class__(self.data.replace(old, new, maxsplit))
1219 def rfind(self, sub, start=0, end=_sys.maxsize):
1220 if isinstance(sub, UserString):
1221 sub = sub.data
1222 return self.data.rfind(sub, start, end)
1223 def rindex(self, sub, start=0, end=_sys.maxsize):
1224 return self.data.rindex(sub, start, end)
1225 def rjust(self, width, *args):
1226 return self.__class__(self.data.rjust(width, *args))
1227 def rpartition(self, sep):
1228 return self.data.rpartition(sep)
1229 def rstrip(self, chars=None):
1230 return self.__class__(self.data.rstrip(chars))
1231 def split(self, sep=None, maxsplit=-1):
1232 return self.data.split(sep, maxsplit)
1233 def rsplit(self, sep=None, maxsplit=-1):
1234 return self.data.rsplit(sep, maxsplit)
1235 def splitlines(self, keepends=False): return self.data.splitlines(keepends)
1236 def startswith(self, prefix, start=0, end=_sys.maxsize):
1237 return self.data.startswith(prefix, start, end)
1238 def strip(self, chars=None): return self.__class__(self.data.strip(chars))
1239 def swapcase(self): return self.__class__(self.data.swapcase())
1240 def title(self): return self.__class__(self.data.title())
1241 def translate(self, *args):
1242 return self.__class__(self.data.translate(*args))
1243 def upper(self): return self.__class__(self.data.upper())
1244 def zfill(self, width): return self.__class__(self.data.zfill(width))
