ยปCore Development>Code coverage>Lib/collections/__init__.py

Python code coverage for Lib/collections/__init__.py

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