Debian Codegraph @

Lib/collections/__init__.py

raw
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__ = [
18 'ChainMap',
19 'Counter',
20 'OrderedDict',
21 'UserDict',
22 'UserList',
23 'UserString',
24 'defaultdict',
25 'deque',
26 'namedtuple',
27 ]
28
29 import _collections_abc
30 import sys as _sys
31
32 _sys.modules['collections.abc'] = _collections_abc
33 abc = _collections_abc
34
35 from itertools import chain as _chain
36 from itertools import repeat as _repeat
37 from itertools import starmap as _starmap
38 from keyword import iskeyword as _iskeyword
39 from operator import eq as _eq
40 from operator import itemgetter as _itemgetter
41 from reprlib import recursive_repr as _recursive_repr
42 from _weakref import proxy as _proxy
43
44 try:
45 from _collections import deque
46 except ImportError:
47 pass
48 else:
49 _collections_abc.MutableSequence.register(deque)
50
51 try:
52 # Expose _deque_iterator to support pickling deque iterators
53 from _collections import _deque_iterator # noqa: F401
54 except ImportError:
55 pass
56
57 try:
58 from _collections import defaultdict
59 except ImportError:
60 pass
61
62 heapq = None # Lazily imported
63
64
65 ################################################################################
66 ### OrderedDict
67 ################################################################################
68
69 class _OrderedDictKeysView(_collections_abc.KeysView):
70
71 def __reversed__(self):
72 yield from reversed(self._mapping)
73
74 class _OrderedDictItemsView(_collections_abc.ItemsView):
75
76 def __reversed__(self):
77 for key in reversed(self._mapping):
78 yield (key, self._mapping[key])
79
80 class _OrderedDictValuesView(_collections_abc.ValuesView):
81
82 def __reversed__(self):
83 for key in reversed(self._mapping):
84 yield self._mapping[key]
85
86 class _Link(object):
87 __slots__ = 'prev', 'next', 'key', '__weakref__'
88
89 class OrderedDict(dict):
90 'Dictionary that remembers insertion order'
91 # An inherited dict maps keys to values.
92 # The inherited dict provides __getitem__, __len__, __contains__, and get.
93 # The remaining methods are order-aware.
94 # Big-O running times for all methods are the same as regular dictionaries.
95
96 # The internal self.__map dict maps keys to links in a doubly linked list.
97 # The circular doubly linked list starts and ends with a sentinel element.
98 # The sentinel element never gets deleted (this simplifies the algorithm).
99 # The sentinel is in self.__hardroot with a weakref proxy in self.__root.
100 # The prev links are weakref proxies (to prevent circular references).
101 # Individual links are kept alive by the hard reference in self.__map.
102 # Those hard references disappear when a key is deleted from an OrderedDict.
103
104 def __new__(cls, /, *args, **kwds):
105 "Create the ordered dict object and set up the underlying structures."
106 self = dict.__new__(cls)
107 self.__hardroot = _Link()
108 self.__root = root = _proxy(self.__hardroot)
109 root.prev = root.next = root
110 self.__map = {}
111 return self
112
113 def __init__(self, other=(), /, **kwds):
114 '''Initialize an ordered dictionary. The signature is the same as
115 regular dictionaries. Keyword argument order is preserved.
116 '''
117 self.__update(other, **kwds)
118
119 def __setitem__(self, key, value,
120 dict_setitem=dict.__setitem__, proxy=_proxy, Link=_Link):
121 'od.__setitem__(i, y) <==> od[i]=y'
122 # Setting a new item creates a new link at the end of the linked list,
123 # and the inherited dictionary is updated with the new key/value pair.
124 if key not in self:
125 self.__map[key] = link = Link()
126 root = self.__root
127 last = root.prev
128 link.prev, link.next, link.key = last, root, key
129 last.next = link
130 root.prev = proxy(link)
131 dict_setitem(self, key, value)
132
133 def __delitem__(self, key, dict_delitem=dict.__delitem__):
134 'od.__delitem__(y) <==> del od[y]'
135 # Deleting an existing item uses self.__map to find the link which gets
136 # removed by updating the links in the predecessor and successor nodes.
137 dict_delitem(self, key)
138 link = self.__map.pop(key)
139 link_prev = link.prev
140 link_next = link.next
141 link_prev.next = link_next
142 link_next.prev = link_prev
143 link.prev = None
144 link.next = None
145
146 def __iter__(self):
147 'od.__iter__() <==> iter(od)'
148 # Traverse the linked list in order.
149 root = self.__root
150 curr = root.next
151 while curr is not root:
152 yield curr.key
153 curr = curr.next
154
155 def __reversed__(self):
156 'od.__reversed__() <==> reversed(od)'
157 # Traverse the linked list in reverse order.
158 root = self.__root
159 curr = root.prev
160 while curr is not root:
161 yield curr.key
162 curr = curr.prev
163
164 def clear(self):
165 'od.clear() -> None. Remove all items from od.'
166 root = self.__root
167 root.prev = root.next = root
168 self.__map.clear()
169 dict.clear(self)
170
171 def popitem(self, last=True):
172 '''Remove and return a (key, value) pair from the dictionary.
173
174 Pairs are returned in LIFO order if last is true or FIFO order if false.
175 '''
176 if not self:
177 raise KeyError('dictionary is empty')
178 root = self.__root
179 if last:
180 link = root.prev
181 link_prev = link.prev
182 link_prev.next = root
183 root.prev = link_prev
184 else:
185 link = root.next
186 link_next = link.next
187 root.next = link_next
188 link_next.prev = root
189 key = link.key
190 del self.__map[key]
191 value = dict.pop(self, key)
192 return key, value
193
194 def move_to_end(self, key, last=True):
195 '''Move an existing element to the end (or beginning if last is false).
196
197 Raise KeyError if the element does not exist.
198 '''
199 link = self.__map[key]
200 link_prev = link.prev
201 link_next = link.next
202 soft_link = link_next.prev
203 link_prev.next = link_next
204 link_next.prev = link_prev
205 root = self.__root
206 if last:
207 last = root.prev
208 link.prev = last
209 link.next = root
210 root.prev = soft_link
211 last.next = link
212 else:
213 first = root.next
214 link.prev = root
215 link.next = first
216 first.prev = soft_link
217 root.next = link
218
219 def __sizeof__(self):
220 sizeof = _sys.getsizeof
221 n = len(self) + 1 # number of links including root
222 size = sizeof(self.__dict__) # instance dictionary
223 size += sizeof(self.__map) * 2 # internal dict and inherited dict
224 size += sizeof(self.__hardroot) * n # link objects
225 size += sizeof(self.__root) * n # proxy objects
226 return size
227
228 update = __update = _collections_abc.MutableMapping.update
229
230 def keys(self):
231 "D.keys() -> a set-like object providing a view on D's keys"
232 return _OrderedDictKeysView(self)
233
234 def items(self):
235 "D.items() -> a set-like object providing a view on D's items"
236 return _OrderedDictItemsView(self)
237
238 def values(self):
239 "D.values() -> an object providing a view on D's values"
240 return _OrderedDictValuesView(self)
241
242 __ne__ = _collections_abc.MutableMapping.__ne__
243
244 __marker = object()
245
246 def pop(self, key, default=__marker):
247 '''od.pop(k[,d]) -> v, remove specified key and return the corresponding
248 value. If key is not found, d is returned if given, otherwise KeyError
249 is raised.
250
251 '''
252 marker = self.__marker
253 result = dict.pop(self, key, marker)
254 if result is not marker:
255 # The same as in __delitem__().
256 link = self.__map.pop(key)
257 link_prev = link.prev
258 link_next = link.next
259 link_prev.next = link_next
260 link_next.prev = link_prev
261 link.prev = None
262 link.next = None
263 return result
264 if default is marker:
265 raise KeyError(key)
266 return default
267
268 def setdefault(self, key, default=None):
269 '''Insert key with a value of default if key is not in the dictionary.
270
271 Return the value for key if key is in the dictionary, else default.
272 '''
273 if key in self:
274 return self[key]
275 self[key] = default
276 return default
277
278 @_recursive_repr()
279 def __repr__(self):
280 'od.__repr__() <==> repr(od)'
281 if not self:
282 return '%s()' % (self.__class__.__name__,)
283 return '%s(%r)' % (self.__class__.__name__, dict(self.items()))
284
285 def __reduce__(self):
286 'Return state information for pickling'
287 state = self.__getstate__()
288 if state:
289 if isinstance(state, tuple):
290 state, slots = state
291 else:
292 slots = {}
293 state = state.copy()
294 slots = slots.copy()
295 for k in vars(OrderedDict()):
296 state.pop(k, None)
297 slots.pop(k, None)
298 if slots:
299 state = state, slots
300 else:
301 state = state or None
302 return self.__class__, (), state, None, iter(self.items())
303
304 def copy(self):
305 'od.copy() -> a shallow copy of od'
306 return self.__class__(self)
307
308 @classmethod
309 def fromkeys(cls, iterable, value=None):
310 '''Create a new ordered dictionary with keys from iterable and values set to value.
311 '''
312 self = cls()
313 for key in iterable:
314 self[key] = value
315 return self
316
317 def __eq__(self, other):
318 '''od.__eq__(y) <==> od==y. Comparison to another OD is order-sensitive
319 while comparison to a regular mapping is order-insensitive.
320
321 '''
322 if isinstance(other, OrderedDict):
323 return dict.__eq__(self, other) and all(map(_eq, self, other))
324 return dict.__eq__(self, other)
325
326 def __ior__(self, other):
327 self.update(other)
328 return self
329
330 def __or__(self, other):
331 if not isinstance(other, dict):
332 return NotImplemented
333 new = self.__class__(self)
334 new.update(other)
335 return new
336
337 def __ror__(self, other):
338 if not isinstance(other, dict):
339 return NotImplemented
340 new = self.__class__(other)
341 new.update(self)
342 return new
343
344
345 try:
346 from _collections import OrderedDict
347 except ImportError:
348 # Leave the pure Python version in place.
349 pass
350
351
352 ################################################################################
353 ### namedtuple
354 ################################################################################
355
356 try:
357 from _collections import _tuplegetter
358 except ImportError:
359 _tuplegetter = lambda index, doc: property(_itemgetter(index), doc=doc)
360
361 def namedtuple(typename, field_names, *, rename=False, defaults=None, module=None):
362 """Returns a new subclass of tuple with named fields.
363
364 >>> Point = namedtuple('Point', ['x', 'y'])
365 >>> Point.__doc__ # docstring for the new class
366 'Point(x, y)'
367 >>> p = Point(11, y=22) # instantiate with positional args or keywords
368 >>> p[0] + p[1] # indexable like a plain tuple
369 33
370 >>> x, y = p # unpack like a regular tuple
371 >>> x, y
372 (11, 22)
373 >>> p.x + p.y # fields also accessible by name
374 33
375 >>> d = p._asdict() # convert to a dictionary
376 >>> d['x']
377 11
378 >>> Point(**d) # convert from a dictionary
379 Point(x=11, y=22)
380 >>> p._replace(x=100) # _replace() is like str.replace() but targets named fields
381 Point(x=100, y=22)
382
383 """
384
385 # Validate the field names. At the user's option, either generate an error
386 # message or automatically replace the field name with a valid name.
387 if isinstance(field_names, str):
388 field_names = field_names.replace(',', ' ').split()
389 field_names = list(map(str, field_names))
390 typename = _sys.intern(str(typename))
391
392 if rename:
393 seen = set()
394 for index, name in enumerate(field_names):
395 if (not name.isidentifier()
396 or _iskeyword(name)
397 or name.startswith('_')
398 or name in seen):
399 field_names[index] = f'_{index}'
400 seen.add(name)
401
402 for name in [typename] + field_names:
403 if type(name) is not str:
404 raise TypeError('Type names and field names must be strings')
405 if not name.isidentifier():
406 raise ValueError('Type names and field names must be valid '
407 f'identifiers: {name!r}')
408 if _iskeyword(name):
409 raise ValueError('Type names and field names cannot be a '
410 f'keyword: {name!r}')
411
412 seen = set()
413 for name in field_names:
414 if name.startswith('_') and not rename:
415 raise ValueError('Field names cannot start with an underscore: '
416 f'{name!r}')
417 if name in seen:
418 raise ValueError(f'Encountered duplicate field name: {name!r}')
419 seen.add(name)
420
421 field_defaults = {}
422 if defaults is not None:
423 defaults = tuple(defaults)
424 if len(defaults) > len(field_names):
425 raise TypeError('Got more default values than field names')
426 field_defaults = dict(reversed(list(zip(reversed(field_names),
427 reversed(defaults)))))
428
429 # Variables used in the methods and docstrings
430 field_names = tuple(map(_sys.intern, field_names))
431 num_fields = len(field_names)
432 arg_list = ', '.join(field_names)
433 if num_fields == 1:
434 arg_list += ','
435 repr_fmt = '(' + ', '.join(f'{name}=%r' for name in field_names) + ')'
436 tuple_new = tuple.__new__
437 _dict, _tuple, _len, _map, _zip = dict, tuple, len, map, zip
438
439 # Create all the named tuple methods to be added to the class namespace
440
441 namespace = {
442 '_tuple_new': tuple_new,
443 '__builtins__': {},
444 '__name__': f'namedtuple_{typename}',
445 }
446 code = f'lambda _cls, {arg_list}: _tuple_new(_cls, ({arg_list}))'
447 __new__ = eval(code, namespace)
448 __new__.__name__ = '__new__'
449 __new__.__doc__ = f'Create new instance of {typename}({arg_list})'
450 if defaults is not None:
451 __new__.__defaults__ = defaults
452
453 @classmethod
454 def _make(cls, iterable):
455 result = tuple_new(cls, iterable)
456 if _len(result) != num_fields:
457 raise TypeError(f'Expected {num_fields} arguments, got {len(result)}')
458 return result
459
460 _make.__func__.__doc__ = (f'Make a new {typename} object from a sequence '
461 'or iterable')
462
463 def _replace(self, /, **kwds):
464 result = self._make(_map(kwds.pop, field_names, self))
465 if kwds:
466 raise TypeError(f'Got unexpected field names: {list(kwds)!r}')
467 return result
468
469 _replace.__doc__ = (f'Return a new {typename} object replacing specified '
470 'fields with new values')
471
472 def __repr__(self):
473 'Return a nicely formatted representation string'
474 return self.__class__.__name__ + repr_fmt % self
475
476 def _asdict(self):
477 'Return a new dict which maps field names to their values.'
478 return _dict(_zip(self._fields, self))
479
480 def __getnewargs__(self):
481 'Return self as a plain tuple. Used by copy and pickle.'
482 return _tuple(self)
483
484 # Modify function metadata to help with introspection and debugging
485 for method in (
486 __new__,
487 _make.__func__,
488 _replace,
489 __repr__,
490 _asdict,
491 __getnewargs__,
492 ):
493 method.__qualname__ = f'{typename}.{method.__name__}'
494
495 # Build-up the class namespace dictionary
496 # and use type() to build the result class
497 class_namespace = {
498 '__doc__': f'{typename}({arg_list})',
499 '__slots__': (),
500 '_fields': field_names,
501 '_field_defaults': field_defaults,
502 '__new__': __new__,
503 '_make': _make,
504 '__replace__': _replace,
505 '_replace': _replace,
506 '__repr__': __repr__,
507 '_asdict': _asdict,
508 '__getnewargs__': __getnewargs__,
509 '__match_args__': field_names,
510 }
511 for index, name in enumerate(field_names):
512 doc = _sys.intern(f'Alias for field number {index}')
513 class_namespace[name] = _tuplegetter(index, doc)
514
515 result = type(typename, (tuple,), class_namespace)
516
517 # For pickling to work, the __module__ variable needs to be set to the frame
518 # where the named tuple is created. Bypass this step in environments where
519 # sys._getframe is not defined (Jython for example) or sys._getframe is not
520 # defined for arguments greater than 0 (IronPython), or where the user has
521 # specified a particular module.
522 if module is None:
523 try:
524 module = _sys._getframemodulename(1) or '__main__'
525 except AttributeError:
526 try:
527 module = _sys._getframe(1).f_globals.get('__name__', '__main__')
528 except (AttributeError, ValueError):
529 pass
530 if module is not None:
531 result.__module__ = module
532
533 return result
534
535
536 ########################################################################
537 ### Counter
538 ########################################################################
539
540 def _count_elements(mapping, iterable):
541 'Tally elements from the iterable.'
542 mapping_get = mapping.get
543 for elem in iterable:
544 mapping[elem] = mapping_get(elem, 0) + 1
545
546 try: # Load C helper function if available
547 from _collections import _count_elements
548 except ImportError:
549 pass
550
551 class Counter(dict):
552 '''Dict subclass for counting hashable items. Sometimes called a bag
553 or multiset. Elements are stored as dictionary keys and their counts
554 are stored as dictionary values.
555
556 >>> c = Counter('abcdeabcdabcaba') # count elements from a string
557
558 >>> c.most_common(3) # three most common elements
559 [('a', 5), ('b', 4), ('c', 3)]
560 >>> sorted(c) # list all unique elements
561 ['a', 'b', 'c', 'd', 'e']
562 >>> ''.join(sorted(c.elements())) # list elements with repetitions
563 'aaaaabbbbcccdde'
564 >>> sum(c.values()) # total of all counts
565 15
566
567 >>> c['a'] # count of letter 'a'
568 5
569 >>> for elem in 'shazam': # update counts from an iterable
570 ... c[elem] += 1 # by adding 1 to each element's count
571 >>> c['a'] # now there are seven 'a'
572 7
573 >>> del c['b'] # remove all 'b'
574 >>> c['b'] # now there are zero 'b'
575 0
576
577 >>> d = Counter('simsalabim') # make another counter
578 >>> c.update(d) # add in the second counter
579 >>> c['a'] # now there are nine 'a'
580 9
581
582 >>> c.clear() # empty the counter
583 >>> c
584 Counter()
585
586 Note: If a count is set to zero or reduced to zero, it will remain
587 in the counter until the entry is deleted or the counter is cleared:
588
589 >>> c = Counter('aaabbc')
590 >>> c['b'] -= 2 # reduce the count of 'b' by two
591 >>> c.most_common() # 'b' is still in, but its count is zero
592 [('a', 3), ('c', 1), ('b', 0)]
593
594 '''
595 # References:
596 # http://en.wikipedia.org/wiki/Multiset
597 # http://www.gnu.org/software/smalltalk/manual-base/html_node/Bag.html
598 # http://www.java2s.com/Tutorial/Cpp/0380__set-multiset/Catalog0380__set-multiset.htm
599 # http://code.activestate.com/recipes/259174/
600 # Knuth, TAOCP Vol. II section 4.6.3
601
602 def __init__(self, iterable=None, /, **kwds):
603 '''Create a new, empty Counter object. And if given, count elements
604 from an input iterable. Or, initialize the count from another mapping
605 of elements to their counts.
606
607 >>> c = Counter() # a new, empty counter
608 >>> c = Counter('gallahad') # a new counter from an iterable
609 >>> c = Counter({'a': 4, 'b': 2}) # a new counter from a mapping
610 >>> c = Counter(a=4, b=2) # a new counter from keyword args
611
612 '''
613 super().__init__()
614 self.update(iterable, **kwds)
615
616 def __missing__(self, key):
617 'The count of elements not in the Counter is zero.'
618 # Needed so that self[missing_item] does not raise KeyError
619 return 0
620
621 def total(self):
622 'Sum of the counts'
623 return sum(self.values())
624
625 def most_common(self, n=None):
626 '''List the n most common elements and their counts from the most
627 common to the least. If n is None, then list all element counts.
628
629 >>> Counter('abracadabra').most_common(3)
630 [('a', 5), ('b', 2), ('r', 2)]
631
632 '''
633 # Emulate Bag.sortedByCount from Smalltalk
634 if n is None:
635 return sorted(self.items(), key=_itemgetter(1), reverse=True)
636
637 # Lazy import to speedup Python startup time
638 global heapq
639 if heapq is None:
640 import heapq
641
642 return heapq.nlargest(n, self.items(), key=_itemgetter(1))
643
644 def elements(self):
645 '''Iterator over elements repeating each as many times as its count.
646
647 >>> c = Counter('ABCABC')
648 >>> sorted(c.elements())
649 ['A', 'A', 'B', 'B', 'C', 'C']
650
651 Knuth's example for prime factors of 1836: 2**2 * 3**3 * 17**1
652
653 >>> import math
654 >>> prime_factors = Counter({2: 2, 3: 3, 17: 1})
655 >>> math.prod(prime_factors.elements())
656 1836
657
658 Note, if an element's count has been set to zero or is a negative
659 number, elements() will ignore it.
660
661 '''
662 # Emulate Bag.do from Smalltalk and Multiset.begin from C++.
663 return _chain.from_iterable(_starmap(_repeat, self.items()))
664
665 # Override dict methods where necessary
666
667 @classmethod
668 def fromkeys(cls, iterable, v=None):
669 # There is no equivalent method for counters because the semantics
670 # would be ambiguous in cases such as Counter.fromkeys('aaabbc', v=2).
671 # Initializing counters to zero values isn't necessary because zero
672 # is already the default value for counter lookups. Initializing
673 # to one is easily accomplished with Counter(set(iterable)). For
674 # more exotic cases, create a dictionary first using a dictionary
675 # comprehension or dict.fromkeys().
676 raise NotImplementedError(
677 'Counter.fromkeys() is undefined. Use Counter(iterable) instead.')
678
679 def update(self, iterable=None, /, **kwds):
680 '''Like dict.update() but add counts instead of replacing them.
681
682 Source can be an iterable, a dictionary, or another Counter instance.
683
684 >>> c = Counter('which')
685 >>> c.update('witch') # add elements from another iterable
686 >>> d = Counter('watch')
687 >>> c.update(d) # add elements from another counter
688 >>> c['h'] # four 'h' in which, witch, and watch
689 4
690
691 '''
692 # The regular dict.update() operation makes no sense here because the
693 # replace behavior results in some of the original untouched counts
694 # being mixed-in with all of the other counts for a mismash that
695 # doesn't have a straight-forward interpretation in most counting
696 # contexts. Instead, we implement straight-addition. Both the inputs
697 # and outputs are allowed to contain zero and negative counts.
698
699 if iterable is not None:
700 if isinstance(iterable, _collections_abc.Mapping):
701 if self:
702 self_get = self.get
703 for elem, count in iterable.items():
704 self[elem] = count + self_get(elem, 0)
705 else:
706 # fast path when counter is empty
707 super().update(iterable)
708 else:
709 _count_elements(self, iterable)
710 if kwds:
711 self.update(kwds)
712
713 def subtract(self, iterable=None, /, **kwds):
714 '''Like dict.update() but subtracts counts instead of replacing them.
715 Counts can be reduced below zero. Both the inputs and outputs are
716 allowed to contain zero and negative counts.
717
718 Source can be an iterable, a dictionary, or another Counter instance.
719
720 >>> c = Counter('which')
721 >>> c.subtract('witch') # subtract elements from another iterable
722 >>> c.subtract(Counter('watch')) # subtract elements from another counter
723 >>> c['h'] # 2 in which, minus 1 in witch, minus 1 in watch
724 0
725 >>> c['w'] # 1 in which, minus 1 in witch, minus 1 in watch
726 -1
727
728 '''
729 if iterable is not None:
730 self_get = self.get
731 if isinstance(iterable, _collections_abc.Mapping):
732 for elem, count in iterable.items():
733 self[elem] = self_get(elem, 0) - count
734 else:
735 for elem in iterable:
736 self[elem] = self_get(elem, 0) - 1
737 if kwds:
738 self.subtract(kwds)
739
740 def copy(self):
741 'Return a shallow copy.'
742 return self.__class__(self)
743
744 def __reduce__(self):
745 return self.__class__, (dict(self),)
746
747 def __delitem__(self, elem):
748 'Like dict.__delitem__() but does not raise KeyError for missing values.'
749 if elem in self:
750 super().__delitem__(elem)
751
752 def __repr__(self):
753 if not self:
754 return f'{self.__class__.__name__}()'
755 try:
756 # dict() preserves the ordering returned by most_common()
757 d = dict(self.most_common())
758 except TypeError:
759 # handle case where values are not orderable
760 d = dict(self)
761 return f'{self.__class__.__name__}({d!r})'
762
763 # Multiset-style mathematical operations discussed in:
764 # Knuth TAOCP Volume II section 4.6.3 exercise 19
765 # and at http://en.wikipedia.org/wiki/Multiset
766 #
767 # Outputs guaranteed to only include positive counts.
768 #
769 # To strip negative and zero counts, add-in an empty counter:
770 # c += Counter()
771 #
772 # Results are ordered according to when an element is first
773 # encountered in the left operand and then by the order
774 # encountered in the right operand.
775 #
776 # When the multiplicities are all zero or one, multiset operations
777 # are guaranteed to be equivalent to the corresponding operations
778 # for regular sets.
779 # Given counter multisets such as:
780 # cp = Counter(a=1, b=0, c=1)
781 # cq = Counter(c=1, d=0, e=1)
782 # The corresponding regular sets would be:
783 # sp = {'a', 'c'}
784 # sq = {'c', 'e'}
785 # All of the following relations would hold:
786 # set(cp + cq) == sp | sq
787 # set(cp - cq) == sp - sq
788 # set(cp | cq) == sp | sq
789 # set(cp & cq) == sp & sq
790 # (cp == cq) == (sp == sq)
791 # (cp != cq) == (sp != sq)
792 # (cp <= cq) == (sp <= sq)
793 # (cp < cq) == (sp < sq)
794 # (cp >= cq) == (sp >= sq)
795 # (cp > cq) == (sp > sq)
796
797 def __eq__(self, other):
798 'True if all counts agree. Missing counts are treated as zero.'
799 if not isinstance(other, Counter):
800 return NotImplemented
801 return all(self[e] == other[e] for c in (self, other) for e in c)
802
803 def __ne__(self, other):
804 'True if any counts disagree. Missing counts are treated as zero.'
805 if not isinstance(other, Counter):
806 return NotImplemented
807 return not self == other
808
809 def __le__(self, other):
810 'True if all counts in self are a subset of those in other.'
811 if not isinstance(other, Counter):
812 return NotImplemented
813 return all(self[e] <= other[e] for c in (self, other) for e in c)
814
815 def __lt__(self, other):
816 'True if all counts in self are a proper subset of those in other.'
817 if not isinstance(other, Counter):
818 return NotImplemented
819 return self <= other and self != other
820
821 def __ge__(self, other):
822 'True if all counts in self are a superset of those in other.'
823 if not isinstance(other, Counter):
824 return NotImplemented
825 return all(self[e] >= other[e] for c in (self, other) for e in c)
826
827 def __gt__(self, other):
828 'True if all counts in self are a proper superset of those in other.'
829 if not isinstance(other, Counter):
830 return NotImplemented
831 return self >= other and self != other
832
833 def __add__(self, other):
834 '''Add counts from two counters.
835
836 >>> Counter('abbb') + Counter('bcc')
837 Counter({'b': 4, 'c': 2, 'a': 1})
838
839 '''
840 if not isinstance(other, Counter):
841 return NotImplemented
842 result = Counter()
843 for elem, count in self.items():
844 newcount = count + other[elem]
845 if newcount > 0:
846 result[elem] = newcount
847 for elem, count in other.items():
848 if elem not in self and count > 0:
849 result[elem] = count
850 return result
851
852 def __sub__(self, other):
853 ''' Subtract count, but keep only results with positive counts.
854
855 >>> Counter('abbbc') - Counter('bccd')
856 Counter({'b': 2, 'a': 1})
857
858 '''
859 if not isinstance(other, Counter):
860 return NotImplemented
861 result = Counter()
862 for elem, count in self.items():
863 newcount = count - other[elem]
864 if newcount > 0:
865 result[elem] = newcount
866 for elem, count in other.items():
867 if elem not in self and count < 0:
868 result[elem] = 0 - count
869 return result
870
871 def __or__(self, other):
872 '''Union is the maximum of value in either of the input counters.
873
874 >>> Counter('abbb') | Counter('bcc')
875 Counter({'b': 3, 'c': 2, 'a': 1})
876
877 '''
878 if not isinstance(other, Counter):
879 return NotImplemented
880 result = Counter()
881 for elem, count in self.items():
882 other_count = other[elem]
883 newcount = other_count if count < other_count else count
884 if newcount > 0:
885 result[elem] = newcount
886 for elem, count in other.items():
887 if elem not in self and count > 0:
888 result[elem] = count
889 return result
890
891 def __and__(self, other):
892 ''' Intersection is the minimum of corresponding counts.
893
894 >>> Counter('abbb') & Counter('bcc')
895 Counter({'b': 1})
896
897 '''
898 if not isinstance(other, Counter):
899 return NotImplemented
900 result = Counter()
901 for elem, count in self.items():
902 other_count = other[elem]
903 newcount = count if count < other_count else other_count
904 if newcount > 0:
905 result[elem] = newcount
906 return result
907
908 def __pos__(self):
909 'Adds an empty counter, effectively stripping negative and zero counts'
910 result = Counter()
911 for elem, count in self.items():
912 if count > 0:
913 result[elem] = count
914 return result
915
916 def __neg__(self):
917 '''Subtracts from an empty counter. Strips positive and zero counts,
918 and flips the sign on negative counts.
919
920 '''
921 result = Counter()
922 for elem, count in self.items():
923 if count < 0:
924 result[elem] = 0 - count
925 return result
926
927 def _keep_positive(self):
928 '''Internal method to strip elements with a negative or zero count'''
929 nonpositive = [elem for elem, count in self.items() if not count > 0]
930 for elem in nonpositive:
931 del self[elem]
932 return self
933
934 def __iadd__(self, other):
935 '''Inplace add from another counter, keeping only positive counts.
936
937 >>> c = Counter('abbb')
938 >>> c += Counter('bcc')
939 >>> c
940 Counter({'b': 4, 'c': 2, 'a': 1})
941
942 '''
943 for elem, count in other.items():
944 self[elem] += count
945 return self._keep_positive()
946
947 def __isub__(self, other):
948 '''Inplace subtract counter, but keep only results with positive counts.
949
950 >>> c = Counter('abbbc')
951 >>> c -= Counter('bccd')
952 >>> c
953 Counter({'b': 2, 'a': 1})
954
955 '''
956 for elem, count in other.items():
957 self[elem] -= count
958 return self._keep_positive()
959
960 def __ior__(self, other):
961 '''Inplace union is the maximum of value from either counter.
962
963 >>> c = Counter('abbb')
964 >>> c |= Counter('bcc')
965 >>> c
966 Counter({'b': 3, 'c': 2, 'a': 1})
967
968 '''
969 for elem, other_count in other.items():
970 count = self[elem]
971 if other_count > count:
972 self[elem] = other_count
973 return self._keep_positive()
974
975 def __iand__(self, other):
976 '''Inplace intersection is the minimum of corresponding counts.
977
978 >>> c = Counter('abbb')
979 >>> c &= Counter('bcc')
980 >>> c
981 Counter({'b': 1})
982
983 '''
984 for elem, count in self.items():
985 other_count = other[elem]
986 if other_count < count:
987 self[elem] = other_count
988 return self._keep_positive()
989
990
991 ########################################################################
992 ### ChainMap
993 ########################################################################
994
995 class ChainMap(_collections_abc.MutableMapping):
996 ''' A ChainMap groups multiple dicts (or other mappings) together
997 to create a single, updateable view.
998
999 The underlying mappings are stored in a list. That list is public and can
1000 be accessed or updated using the *maps* attribute. There is no other
1001 state.
1002
1003 Lookups search the underlying mappings successively until a key is found.
1004 In contrast, writes, updates, and deletions only operate on the first
1005 mapping.
1006
1007 '''
1008
1009 def __init__(self, *maps):
1010 '''Initialize a ChainMap by setting *maps* to the given mappings.
1011 If no mappings are provided, a single empty dictionary is used.
1012
1013 '''
1014 self.maps = list(maps) or [{}] # always at least one map
1015
1016 def __missing__(self, key):
1017 raise KeyError(key)
1018
1019 def __getitem__(self, key):
1020 for mapping in self.maps:
1021 try:
1022 return mapping[key] # can't use 'key in mapping' with defaultdict
1023 except KeyError:
1024 pass
1025 return self.__missing__(key) # support subclasses that define __missing__
1026
1027 def get(self, key, default=None):
1028 return self[key] if key in self else default # needs to make use of __contains__
1029
1030 def __len__(self):
1031 return len(set().union(*self.maps)) # reuses stored hash values if possible
1032
1033 def __iter__(self):
1034 d = {}
1035 for mapping in map(dict.fromkeys, reversed(self.maps)):
1036 d |= mapping # reuses stored hash values if possible
1037 return iter(d)
1038
1039 def __contains__(self, key):
1040 for mapping in self.maps:
1041 if key in mapping:
1042 return True
1043 return False
1044
1045 def __bool__(self):
1046 return any(self.maps)
1047
1048 @_recursive_repr()
1049 def __repr__(self):
1050 return f'{self.__class__.__name__}({", ".join(map(repr, self.maps))})'
1051
1052 @classmethod
1053 def fromkeys(cls, iterable, value=None, /):
1054 'Create a new ChainMap with keys from iterable and values set to value.'
1055 return cls(dict.fromkeys(iterable, value))
1056
1057 def copy(self):
1058 'New ChainMap or subclass with a new copy of maps[0] and refs to maps[1:]'
1059 return self.__class__(self.maps[0].copy(), *self.maps[1:])
1060
1061 __copy__ = copy
1062
1063 def new_child(self, m=None, **kwargs): # like Django's Context.push()
1064 '''New ChainMap with a new map followed by all previous maps.
1065 If no map is provided, an empty dict is used.
1066 Keyword arguments update the map or new empty dict.
1067 '''
1068 if m is None:
1069 m = kwargs
1070 elif kwargs:
1071 m.update(kwargs)
1072 return self.__class__(m, *self.maps)
1073
1074 @property
1075 def parents(self): # like Django's Context.pop()
1076 'New ChainMap from maps[1:].'
1077 return self.__class__(*self.maps[1:])
1078
1079 def __setitem__(self, key, value):
1080 self.maps[0][key] = value
1081
1082 def __delitem__(self, key):
1083 try:
1084 del self.maps[0][key]
1085 except KeyError:
1086 raise KeyError(f'Key not found in the first mapping: {key!r}')
1087
1088 def popitem(self):
1089 'Remove and return an item pair from maps[0]. Raise KeyError is maps[0] is empty.'
1090 try:
1091 return self.maps[0].popitem()
1092 except KeyError:
1093 raise KeyError('No keys found in the first mapping.')
1094
1095 def pop(self, key, *args):
1096 'Remove *key* from maps[0] and return its value. Raise KeyError if *key* not in maps[0].'
1097 try:
1098 return self.maps[0].pop(key, *args)
1099 except KeyError:
1100 raise KeyError(f'Key not found in the first mapping: {key!r}')
1101
1102 def clear(self):
1103 'Clear maps[0], leaving maps[1:] intact.'
1104 self.maps[0].clear()
1105
1106 def __ior__(self, other):
1107 self.maps[0].update(other)
1108 return self
1109
1110 def __or__(self, other):
1111 if not isinstance(other, _collections_abc.Mapping):
1112 return NotImplemented
1113 m = self.copy()
1114 m.maps[0].update(other)
1115 return m
1116
1117 def __ror__(self, other):
1118 if not isinstance(other, _collections_abc.Mapping):
1119 return NotImplemented
1120 m = dict(other)
1121 for child in reversed(self.maps):
1122 m.update(child)
1123 return self.__class__(m)
1124
1125
1126 ################################################################################
1127 ### UserDict
1128 ################################################################################
1129
1130 class UserDict(_collections_abc.MutableMapping):
1131
1132 # Start by filling-out the abstract methods
1133 def __init__(self, dict=None, /, **kwargs):
1134 self.data = {}
1135 if dict is not None:
1136 self.update(dict)
1137 if kwargs:
1138 self.update(kwargs)
1139
1140 def __len__(self):
1141 return len(self.data)
1142
1143 def __getitem__(self, key):
1144 if key in self.data:
1145 return self.data[key]
1146 if hasattr(self.__class__, "__missing__"):
1147 return self.__class__.__missing__(self, key)
1148 raise KeyError(key)
1149
1150 def __setitem__(self, key, item):
1151 self.data[key] = item
1152
1153 def __delitem__(self, key):
1154 del self.data[key]
1155
1156 def __iter__(self):
1157 return iter(self.data)
1158
1159 # Modify __contains__ and get() to work like dict
1160 # does when __missing__ is present.
1161 def __contains__(self, key):
1162 return key in self.data
1163
1164 def get(self, key, default=None):
1165 if key in self:
1166 return self[key]
1167 return default
1168
1169
1170 # Now, add the methods in dicts but not in MutableMapping
1171 def __repr__(self):
1172 return repr(self.data)
1173
1174 def __or__(self, other):
1175 if isinstance(other, UserDict):
1176 return self.__class__(self.data | other.data)
1177 if isinstance(other, dict):
1178 return self.__class__(self.data | other)
1179 return NotImplemented
1180
1181 def __ror__(self, other):
1182 if isinstance(other, UserDict):
1183 return self.__class__(other.data | self.data)
1184 if isinstance(other, dict):
1185 return self.__class__(other | self.data)
1186 return NotImplemented
1187
1188 def __ior__(self, other):
1189 if isinstance(other, UserDict):
1190 self.data |= other.data
1191 else:
1192 self.data |= other
1193 return self
1194
1195 def __copy__(self):
1196 inst = self.__class__.__new__(self.__class__)
1197 inst.__dict__.update(self.__dict__)
1198 # Create a copy and avoid triggering descriptors
1199 inst.__dict__["data"] = self.__dict__["data"].copy()
1200 return inst
1201
1202 def copy(self):
1203 if self.__class__ is UserDict:
1204 return UserDict(self.data.copy())
1205 import copy
1206 data = self.data
1207 try:
1208 self.data = {}
1209 c = copy.copy(self)
1210 finally:
1211 self.data = data
1212 c.update(self)
1213 return c
1214
1215 @classmethod
1216 def fromkeys(cls, iterable, value=None):
1217 d = cls()
1218 for key in iterable:
1219 d[key] = value
1220 return d
1221
1222
1223 ################################################################################
1224 ### UserList
1225 ################################################################################
1226
1227 class UserList(_collections_abc.MutableSequence):
1228 """A more or less complete user-defined wrapper around list objects."""
1229
1230 def __init__(self, initlist=None):
1231 self.data = []
1232 if initlist is not None:
1233 # XXX should this accept an arbitrary sequence?
1234 if type(initlist) == type(self.data):
1235 self.data[:] = initlist
1236 elif isinstance(initlist, UserList):
1237 self.data[:] = initlist.data[:]
1238 else:
1239 self.data = list(initlist)
1240
1241 def __repr__(self):
1242 return repr(self.data)
1243
1244 def __lt__(self, other):
1245 return self.data < self.__cast(other)
1246
1247 def __le__(self, other):
1248 return self.data <= self.__cast(other)
1249
1250 def __eq__(self, other):
1251 return self.data == self.__cast(other)
1252
1253 def __gt__(self, other):
1254 return self.data > self.__cast(other)
1255
1256 def __ge__(self, other):
1257 return self.data >= self.__cast(other)
1258
1259 def __cast(self, other):
1260 return other.data if isinstance(other, UserList) else other
1261
1262 def __contains__(self, item):
1263 return item in self.data
1264
1265 def __len__(self):
1266 return len(self.data)
1267
1268 def __getitem__(self, i):
1269 if isinstance(i, slice):
1270 return self.__class__(self.data[i])
1271 else:
1272 return self.data[i]
1273
1274 def __setitem__(self, i, item):
1275 self.data[i] = item
1276
1277 def __delitem__(self, i):
1278 del self.data[i]
1279
1280 def __add__(self, other):
1281 if isinstance(other, UserList):
1282 return self.__class__(self.data + other.data)
1283 elif isinstance(other, type(self.data)):
1284 return self.__class__(self.data + other)
1285 return self.__class__(self.data + list(other))
1286
1287 def __radd__(self, other):
1288 if isinstance(other, UserList):
1289 return self.__class__(other.data + self.data)
1290 elif isinstance(other, type(self.data)):
1291 return self.__class__(other + self.data)
1292 return self.__class__(list(other) + self.data)
1293
1294 def __iadd__(self, other):
1295 if isinstance(other, UserList):
1296 self.data += other.data
1297 elif isinstance(other, type(self.data)):
1298 self.data += other
1299 else:
1300 self.data += list(other)
1301 return self
1302
1303 def __mul__(self, n):
1304 return self.__class__(self.data * n)
1305
1306 __rmul__ = __mul__
1307
1308 def __imul__(self, n):
1309 self.data *= n
1310 return self
1311
1312 def __copy__(self):
1313 inst = self.__class__.__new__(self.__class__)
1314 inst.__dict__.update(self.__dict__)
1315 # Create a copy and avoid triggering descriptors
1316 inst.__dict__["data"] = self.__dict__["data"][:]
1317 return inst
1318
1319 def append(self, item):
1320 self.data.append(item)
1321
1322 def insert(self, i, item):
1323 self.data.insert(i, item)
1324
1325 def pop(self, i=-1):
1326 return self.data.pop(i)
1327
1328 def remove(self, item):
1329 self.data.remove(item)
1330
1331 def clear(self):
1332 self.data.clear()
1333
1334 def copy(self):
1335 return self.__class__(self)
1336
1337 def count(self, item):
1338 return self.data.count(item)
1339
1340 def index(self, item, *args):
1341 return self.data.index(item, *args)
1342
1343 def reverse(self):
1344 self.data.reverse()
1345
1346 def sort(self, /, *args, **kwds):
1347 self.data.sort(*args, **kwds)
1348
1349 def extend(self, other):
1350 if isinstance(other, UserList):
1351 self.data.extend(other.data)
1352 else:
1353 self.data.extend(other)
1354
1355
1356 ################################################################################
1357 ### UserString
1358 ################################################################################
1359
1360 class UserString(_collections_abc.Sequence):
1361
1362 def __init__(self, seq):
1363 if isinstance(seq, str):
1364 self.data = seq
1365 elif isinstance(seq, UserString):
1366 self.data = seq.data[:]
1367 else:
1368 self.data = str(seq)
1369
1370 def __str__(self):
1371 return str(self.data)
1372
1373 def __repr__(self):
1374 return repr(self.data)
1375
1376 def __int__(self):
1377 return int(self.data)
1378
1379 def __float__(self):
1380 return float(self.data)
1381
1382 def __complex__(self):
1383 return complex(self.data)
1384
1385 def __hash__(self):
1386 return hash(self.data)
1387
1388 def __getnewargs__(self):
1389 return (self.data[:],)
1390
1391 def __eq__(self, string):
1392 if isinstance(string, UserString):
1393 return self.data == string.data
1394 return self.data == string
1395
1396 def __lt__(self, string):
1397 if isinstance(string, UserString):
1398 return self.data < string.data
1399 return self.data < string
1400
1401 def __le__(self, string):
1402 if isinstance(string, UserString):
1403 return self.data <= string.data
1404 return self.data <= string
1405
1406 def __gt__(self, string):
1407 if isinstance(string, UserString):
1408 return self.data > string.data
1409 return self.data > string
1410
1411 def __ge__(self, string):
1412 if isinstance(string, UserString):
1413 return self.data >= string.data
1414 return self.data >= string
1415
1416 def __contains__(self, char):
1417 if isinstance(char, UserString):
1418 char = char.data
1419 return char in self.data
1420
1421 def __len__(self):
1422 return len(self.data)
1423
1424 def __getitem__(self, index):
1425 return self.__class__(self.data[index])
1426
1427 def __add__(self, other):
1428 if isinstance(other, UserString):
1429 return self.__class__(self.data + other.data)
1430 elif isinstance(other, str):
1431 return self.__class__(self.data + other)
1432 return self.__class__(self.data + str(other))
1433
1434 def __radd__(self, other):
1435 if isinstance(other, str):
1436 return self.__class__(other + self.data)
1437 return self.__class__(str(other) + self.data)
1438
1439 def __mul__(self, n):
1440 return self.__class__(self.data * n)
1441
1442 __rmul__ = __mul__
1443
1444 def __mod__(self, args):
1445 return self.__class__(self.data % args)
1446
1447 def __rmod__(self, template):
1448 return self.__class__(str(template) % self)
1449
1450 # the following methods are defined in alphabetical order:
1451 def capitalize(self):
1452 return self.__class__(self.data.capitalize())
1453
1454 def casefold(self):
1455 return self.__class__(self.data.casefold())
1456
1457 def center(self, width, *args):
1458 return self.__class__(self.data.center(width, *args))
1459
1460 def count(self, sub, start=0, end=_sys.maxsize):
1461 if isinstance(sub, UserString):
1462 sub = sub.data
1463 return self.data.count(sub, start, end)
1464
1465 def removeprefix(self, prefix, /):
1466 if isinstance(prefix, UserString):
1467 prefix = prefix.data
1468 return self.__class__(self.data.removeprefix(prefix))
1469
1470 def removesuffix(self, suffix, /):
1471 if isinstance(suffix, UserString):
1472 suffix = suffix.data
1473 return self.__class__(self.data.removesuffix(suffix))
1474
1475 def encode(self, encoding='utf-8', errors='strict'):
1476 encoding = 'utf-8' if encoding is None else encoding
1477 errors = 'strict' if errors is None else errors
1478 return self.data.encode(encoding, errors)
1479
1480 def endswith(self, suffix, start=0, end=_sys.maxsize):
1481 return self.data.endswith(suffix, start, end)
1482
1483 def expandtabs(self, tabsize=8):
1484 return self.__class__(self.data.expandtabs(tabsize))
1485
1486 def find(self, sub, start=0, end=_sys.maxsize):
1487 if isinstance(sub, UserString):
1488 sub = sub.data
1489 return self.data.find(sub, start, end)
1490
1491 def format(self, /, *args, **kwds):
1492 return self.data.format(*args, **kwds)
1493
1494 def format_map(self, mapping):
1495 return self.data.format_map(mapping)
1496
1497 def index(self, sub, start=0, end=_sys.maxsize):
1498 if isinstance(sub, UserString):
1499 sub = sub.data
1500 return self.data.index(sub, start, end)
1501
1502 def isalpha(self):
1503 return self.data.isalpha()
1504
1505 def isalnum(self):
1506 return self.data.isalnum()
1507
1508 def isascii(self):
1509 return self.data.isascii()
1510
1511 def isdecimal(self):
1512 return self.data.isdecimal()
1513
1514 def isdigit(self):
1515 return self.data.isdigit()
1516
1517 def isidentifier(self):
1518 return self.data.isidentifier()
1519
1520 def islower(self):
1521 return self.data.islower()
1522
1523 def isnumeric(self):
1524 return self.data.isnumeric()
1525
1526 def isprintable(self):
1527 return self.data.isprintable()
1528
1529 def isspace(self):
1530 return self.data.isspace()
1531
1532 def istitle(self):
1533 return self.data.istitle()
1534
1535 def isupper(self):
1536 return self.data.isupper()
1537
1538 def join(self, seq):
1539 return self.data.join(seq)
1540
1541 def ljust(self, width, *args):
1542 return self.__class__(self.data.ljust(width, *args))
1543
1544 def lower(self):
1545 return self.__class__(self.data.lower())
1546
1547 def lstrip(self, chars=None):
1548 return self.__class__(self.data.lstrip(chars))
1549
1550 maketrans = str.maketrans
1551
1552 def partition(self, sep):
1553 return self.data.partition(sep)
1554
1555 def replace(self, old, new, maxsplit=-1):
1556 if isinstance(old, UserString):
1557 old = old.data
1558 if isinstance(new, UserString):
1559 new = new.data
1560 return self.__class__(self.data.replace(old, new, maxsplit))
1561
1562 def rfind(self, sub, start=0, end=_sys.maxsize):
1563 if isinstance(sub, UserString):
1564 sub = sub.data
1565 return self.data.rfind(sub, start, end)
1566
1567 def rindex(self, sub, start=0, end=_sys.maxsize):
1568 if isinstance(sub, UserString):
1569 sub = sub.data
1570 return self.data.rindex(sub, start, end)
1571
1572 def rjust(self, width, *args):
1573 return self.__class__(self.data.rjust(width, *args))
1574
1575 def rpartition(self, sep):
1576 return self.data.rpartition(sep)
1577
1578 def rstrip(self, chars=None):
1579 return self.__class__(self.data.rstrip(chars))
1580
1581 def split(self, sep=None, maxsplit=-1):
1582 return self.data.split(sep, maxsplit)
1583
1584 def rsplit(self, sep=None, maxsplit=-1):
1585 return self.data.rsplit(sep, maxsplit)
1586
1587 def splitlines(self, keepends=False):
1588 return self.data.splitlines(keepends)
1589
1590 def startswith(self, prefix, start=0, end=_sys.maxsize):
1591 return self.data.startswith(prefix, start, end)
1592
1593 def strip(self, chars=None):
1594 return self.__class__(self.data.strip(chars))
1595
1596 def swapcase(self):
1597 return self.__class__(self.data.swapcase())
1598
1599 def title(self):
1600 return self.__class__(self.data.title())
1601
1602 def translate(self, *args):
1603 return self.__class__(self.data.translate(*args))
1604
1605 def upper(self):
1606 return self.__class__(self.data.upper())
1607
1608 def zfill(self, width):
1609 return self.__class__(self.data.zfill(width))