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