logo

oasis-root

Compiled tree of Oasis Linux based on own branch at <https://hacktivis.me/git/oasis/> git clone https://anongit.hacktivis.me/git/oasis-root.git

__init__.py (51228B)


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