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