1# Copyright 2007 Google, Inc. All Rights Reserved. 2# Licensed to PSF under a Contributor Agreement. 3 4"""Abstract Base Classes (ABCs) for collections, according to PEP 3119. 5 6DON'T USE THIS MODULE DIRECTLY! The classes here should be imported 7via collections; they are defined here only to alleviate certain 8bootstrapping issues. Unit tests are in test_collections. 9""" 10 11from abc import ABCMeta, abstractmethod 12import sys 13 14__all__ = ["Hashable", "Iterable", "Iterator", 15 "Sized", "Container", "Callable", 16 "Set", "MutableSet", 17 "Mapping", "MutableMapping", 18 "MappingView", "KeysView", "ItemsView", "ValuesView", 19 "Sequence", "MutableSequence", 20 ] 21 22### ONE-TRICK PONIES ### 23 24def _hasattr(C, attr): 25 try: 26 return any(attr in B.__dict__ for B in C.__mro__) 27 except AttributeError: 28 # Old-style class 29 return hasattr(C, attr) 30 31 32class Hashable: 33 __metaclass__ = ABCMeta 34 35 @abstractmethod 36 def __hash__(self): 37 return 0 38 39 @classmethod 40 def __subclasshook__(cls, C): 41 if cls is Hashable: 42 try: 43 for B in C.__mro__: 44 if "__hash__" in B.__dict__: 45 if B.__dict__["__hash__"]: 46 return True 47 break 48 except AttributeError: 49 # Old-style class 50 if getattr(C, "__hash__", None): 51 return True 52 return NotImplemented 53 54 55class Iterable: 56 __metaclass__ = ABCMeta 57 58 @abstractmethod 59 def __iter__(self): 60 while False: 61 yield None 62 63 @classmethod 64 def __subclasshook__(cls, C): 65 if cls is Iterable: 66 if _hasattr(C, "__iter__"): 67 return True 68 return NotImplemented 69 70Iterable.register(str) 71 72 73class Iterator(Iterable): 74 75 @abstractmethod 76 def next(self): 77 'Return the next item from the iterator. When exhausted, raise StopIteration' 78 raise StopIteration 79 80 def __iter__(self): 81 return self 82 83 @classmethod 84 def __subclasshook__(cls, C): 85 if cls is Iterator: 86 if _hasattr(C, "next") and _hasattr(C, "__iter__"): 87 return True 88 return NotImplemented 89 90 91class Sized: 92 __metaclass__ = ABCMeta 93 94 @abstractmethod 95 def __len__(self): 96 return 0 97 98 @classmethod 99 def __subclasshook__(cls, C): 100 if cls is Sized: 101 if _hasattr(C, "__len__"): 102 return True 103 return NotImplemented 104 105 106class Container: 107 __metaclass__ = ABCMeta 108 109 @abstractmethod 110 def __contains__(self, x): 111 return False 112 113 @classmethod 114 def __subclasshook__(cls, C): 115 if cls is Container: 116 if _hasattr(C, "__contains__"): 117 return True 118 return NotImplemented 119 120 121class Callable: 122 __metaclass__ = ABCMeta 123 124 @abstractmethod 125 def __call__(self, *args, **kwds): 126 return False 127 128 @classmethod 129 def __subclasshook__(cls, C): 130 if cls is Callable: 131 if _hasattr(C, "__call__"): 132 return True 133 return NotImplemented 134 135 136### SETS ### 137 138 139class Set(Sized, Iterable, Container): 140 """A set is a finite, iterable container. 141 142 This class provides concrete generic implementations of all 143 methods except for __contains__, __iter__ and __len__. 144 145 To override the comparisons (presumably for speed, as the 146 semantics are fixed), redefine __le__ and __ge__, 147 then the other operations will automatically follow suit. 148 """ 149 150 def __le__(self, other): 151 if not isinstance(other, Set): 152 return NotImplemented 153 if len(self) > len(other): 154 return False 155 for elem in self: 156 if elem not in other: 157 return False 158 return True 159 160 def __lt__(self, other): 161 if not isinstance(other, Set): 162 return NotImplemented 163 return len(self) < len(other) and self.__le__(other) 164 165 def __gt__(self, other): 166 if not isinstance(other, Set): 167 return NotImplemented 168 return len(self) > len(other) and self.__ge__(other) 169 170 def __ge__(self, other): 171 if not isinstance(other, Set): 172 return NotImplemented 173 if len(self) < len(other): 174 return False 175 for elem in other: 176 if elem not in self: 177 return False 178 return True 179 180 def __eq__(self, other): 181 if not isinstance(other, Set): 182 return NotImplemented 183 return len(self) == len(other) and self.__le__(other) 184 185 def __ne__(self, other): 186 return not (self == other) 187 188 @classmethod 189 def _from_iterable(cls, it): 190 '''Construct an instance of the class from any iterable input. 191 192 Must override this method if the class constructor signature 193 does not accept an iterable for an input. 194 ''' 195 return cls(it) 196 197 def __and__(self, other): 198 if not isinstance(other, Iterable): 199 return NotImplemented 200 return self._from_iterable(value for value in other if value in self) 201 202 __rand__ = __and__ 203 204 def isdisjoint(self, other): 205 'Return True if two sets have a null intersection.' 206 for value in other: 207 if value in self: 208 return False 209 return True 210 211 def __or__(self, other): 212 if not isinstance(other, Iterable): 213 return NotImplemented 214 chain = (e for s in (self, other) for e in s) 215 return self._from_iterable(chain) 216 217 __ror__ = __or__ 218 219 def __sub__(self, other): 220 if not isinstance(other, Set): 221 if not isinstance(other, Iterable): 222 return NotImplemented 223 other = self._from_iterable(other) 224 return self._from_iterable(value for value in self 225 if value not in other) 226 227 def __rsub__(self, other): 228 if not isinstance(other, Set): 229 if not isinstance(other, Iterable): 230 return NotImplemented 231 other = self._from_iterable(other) 232 return self._from_iterable(value for value in other 233 if value not in self) 234 235 def __xor__(self, other): 236 if not isinstance(other, Set): 237 if not isinstance(other, Iterable): 238 return NotImplemented 239 other = self._from_iterable(other) 240 return (self - other) | (other - self) 241 242 __rxor__ = __xor__ 243 244 # Sets are not hashable by default, but subclasses can change this 245 __hash__ = None 246 247 def _hash(self): 248 """Compute the hash value of a set. 249 250 Note that we don't define __hash__: not all sets are hashable. 251 But if you define a hashable set type, its __hash__ should 252 call this function. 253 254 This must be compatible __eq__. 255 256 All sets ought to compare equal if they contain the same 257 elements, regardless of how they are implemented, and 258 regardless of the order of the elements; so there's not much 259 freedom for __eq__ or __hash__. We match the algorithm used 260 by the built-in frozenset type. 261 """ 262 MAX = sys.maxint 263 MASK = 2 * MAX + 1 264 n = len(self) 265 h = 1927868237 * (n + 1) 266 h &= MASK 267 for x in self: 268 hx = hash(x) 269 h ^= (hx ^ (hx << 16) ^ 89869747) * 3644798167 270 h &= MASK 271 h = h * 69069 + 907133923 272 h &= MASK 273 if h > MAX: 274 h -= MASK + 1 275 if h == -1: 276 h = 590923713 277 return h 278 279Set.register(frozenset) 280 281 282class MutableSet(Set): 283 """A mutable set is a finite, iterable container. 284 285 This class provides concrete generic implementations of all 286 methods except for __contains__, __iter__, __len__, 287 add(), and discard(). 288 289 To override the comparisons (presumably for speed, as the 290 semantics are fixed), all you have to do is redefine __le__ and 291 then the other operations will automatically follow suit. 292 """ 293 294 @abstractmethod 295 def add(self, value): 296 """Add an element.""" 297 raise NotImplementedError 298 299 @abstractmethod 300 def discard(self, value): 301 """Remove an element. Do not raise an exception if absent.""" 302 raise NotImplementedError 303 304 def remove(self, value): 305 """Remove an element. If not a member, raise a KeyError.""" 306 if value not in self: 307 raise KeyError(value) 308 self.discard(value) 309 310 def pop(self): 311 """Return the popped value. Raise KeyError if empty.""" 312 it = iter(self) 313 try: 314 value = next(it) 315 except StopIteration: 316 raise KeyError 317 self.discard(value) 318 return value 319 320 def clear(self): 321 """This is slow (creates N new iterators!) but effective.""" 322 try: 323 while True: 324 self.pop() 325 except KeyError: 326 pass 327 328 def __ior__(self, it): 329 for value in it: 330 self.add(value) 331 return self 332 333 def __iand__(self, it): 334 for value in (self - it): 335 self.discard(value) 336 return self 337 338 def __ixor__(self, it): 339 if it is self: 340 self.clear() 341 else: 342 if not isinstance(it, Set): 343 it = self._from_iterable(it) 344 for value in it: 345 if value in self: 346 self.discard(value) 347 else: 348 self.add(value) 349 return self 350 351 def __isub__(self, it): 352 if it is self: 353 self.clear() 354 else: 355 for value in it: 356 self.discard(value) 357 return self 358 359MutableSet.register(set) 360 361 362### MAPPINGS ### 363 364 365class Mapping(Sized, Iterable, Container): 366 367 """A Mapping is a generic container for associating key/value 368 pairs. 369 370 This class provides concrete generic implementations of all 371 methods except for __getitem__, __iter__, and __len__. 372 373 """ 374 375 @abstractmethod 376 def __getitem__(self, key): 377 raise KeyError 378 379 def get(self, key, default=None): 380 'D.get(k[,d]) -> D[k] if k in D, else d. d defaults to None.' 381 try: 382 return self[key] 383 except KeyError: 384 return default 385 386 def __contains__(self, key): 387 try: 388 self[key] 389 except KeyError: 390 return False 391 else: 392 return True 393 394 def iterkeys(self): 395 'D.iterkeys() -> an iterator over the keys of D' 396 return iter(self) 397 398 def itervalues(self): 399 'D.itervalues() -> an iterator over the values of D' 400 for key in self: 401 yield self[key] 402 403 def iteritems(self): 404 'D.iteritems() -> an iterator over the (key, value) items of D' 405 for key in self: 406 yield (key, self[key]) 407 408 def keys(self): 409 "D.keys() -> list of D's keys" 410 return list(self) 411 412 def items(self): 413 "D.items() -> list of D's (key, value) pairs, as 2-tuples" 414 return [(key, self[key]) for key in self] 415 416 def values(self): 417 "D.values() -> list of D's values" 418 return [self[key] for key in self] 419 420 # Mappings are not hashable by default, but subclasses can change this 421 __hash__ = None 422 423 def __eq__(self, other): 424 if not isinstance(other, Mapping): 425 return NotImplemented 426 return dict(self.items()) == dict(other.items()) 427 428 def __ne__(self, other): 429 return not (self == other) 430 431class MappingView(Sized): 432 433 def __init__(self, mapping): 434 self._mapping = mapping 435 436 def __len__(self): 437 return len(self._mapping) 438 439 def __repr__(self): 440 return '{0.__class__.__name__}({0._mapping!r})'.format(self) 441 442 443class KeysView(MappingView, Set): 444 445 @classmethod 446 def _from_iterable(self, it): 447 return set(it) 448 449 def __contains__(self, key): 450 return key in self._mapping 451 452 def __iter__(self): 453 for key in self._mapping: 454 yield key 455 456KeysView.register(type({}.viewkeys())) 457 458class ItemsView(MappingView, Set): 459 460 @classmethod 461 def _from_iterable(self, it): 462 return set(it) 463 464 def __contains__(self, item): 465 key, value = item 466 try: 467 v = self._mapping[key] 468 except KeyError: 469 return False 470 else: 471 return v == value 472 473 def __iter__(self): 474 for key in self._mapping: 475 yield (key, self._mapping[key]) 476 477ItemsView.register(type({}.viewitems())) 478 479class ValuesView(MappingView): 480 481 def __contains__(self, value): 482 for key in self._mapping: 483 if value == self._mapping[key]: 484 return True 485 return False 486 487 def __iter__(self): 488 for key in self._mapping: 489 yield self._mapping[key] 490 491ValuesView.register(type({}.viewvalues())) 492 493class MutableMapping(Mapping): 494 495 """A MutableMapping is a generic container for associating 496 key/value pairs. 497 498 This class provides concrete generic implementations of all 499 methods except for __getitem__, __setitem__, __delitem__, 500 __iter__, and __len__. 501 502 """ 503 504 @abstractmethod 505 def __setitem__(self, key, value): 506 raise KeyError 507 508 @abstractmethod 509 def __delitem__(self, key): 510 raise KeyError 511 512 __marker = object() 513 514 def pop(self, key, default=__marker): 515 '''D.pop(k[,d]) -> v, remove specified key and return the corresponding value. 516 If key is not found, d is returned if given, otherwise KeyError is raised. 517 ''' 518 try: 519 value = self[key] 520 except KeyError: 521 if default is self.__marker: 522 raise 523 return default 524 else: 525 del self[key] 526 return value 527 528 def popitem(self): 529 '''D.popitem() -> (k, v), remove and return some (key, value) pair 530 as a 2-tuple; but raise KeyError if D is empty. 531 ''' 532 try: 533 key = next(iter(self)) 534 except StopIteration: 535 raise KeyError 536 value = self[key] 537 del self[key] 538 return key, value 539 540 def clear(self): 541 'D.clear() -> None. Remove all items from D.' 542 try: 543 while True: 544 self.popitem() 545 except KeyError: 546 pass 547 548 def update(*args, **kwds): 549 ''' D.update([E, ]**F) -> None. Update D from mapping/iterable E and F. 550 If E present and has a .keys() method, does: for k in E: D[k] = E[k] 551 If E present and lacks .keys() method, does: for (k, v) in E: D[k] = v 552 In either case, this is followed by: for k, v in F.items(): D[k] = v 553 ''' 554 if not args: 555 raise TypeError("descriptor 'update' of 'MutableMapping' object " 556 "needs an argument") 557 self = args[0] 558 args = args[1:] 559 if len(args) > 1: 560 raise TypeError('update expected at most 1 arguments, got %d' % 561 len(args)) 562 if args: 563 other = args[0] 564 if isinstance(other, Mapping): 565 for key in other: 566 self[key] = other[key] 567 elif hasattr(other, "keys"): 568 for key in other.keys(): 569 self[key] = other[key] 570 else: 571 for key, value in other: 572 self[key] = value 573 for key, value in kwds.items(): 574 self[key] = value 575 576 def setdefault(self, key, default=None): 577 'D.setdefault(k[,d]) -> D.get(k,d), also set D[k]=d if k not in D' 578 try: 579 return self[key] 580 except KeyError: 581 self[key] = default 582 return default 583 584MutableMapping.register(dict) 585 586 587### SEQUENCES ### 588 589 590class Sequence(Sized, Iterable, Container): 591 """All the operations on a read-only sequence. 592 593 Concrete subclasses must override __new__ or __init__, 594 __getitem__, and __len__. 595 """ 596 597 @abstractmethod 598 def __getitem__(self, index): 599 raise IndexError 600 601 def __iter__(self): 602 i = 0 603 try: 604 while True: 605 v = self[i] 606 yield v 607 i += 1 608 except IndexError: 609 return 610 611 def __contains__(self, value): 612 for v in self: 613 if v == value: 614 return True 615 return False 616 617 def __reversed__(self): 618 for i in reversed(range(len(self))): 619 yield self[i] 620 621 def index(self, value): 622 '''S.index(value) -> integer -- return first index of value. 623 Raises ValueError if the value is not present. 624 ''' 625 for i, v in enumerate(self): 626 if v == value: 627 return i 628 raise ValueError 629 630 def count(self, value): 631 'S.count(value) -> integer -- return number of occurrences of value' 632 return sum(1 for v in self if v == value) 633 634Sequence.register(tuple) 635Sequence.register(basestring) 636Sequence.register(buffer) 637Sequence.register(xrange) 638 639 640class MutableSequence(Sequence): 641 642 """All the operations on a read-only sequence. 643 644 Concrete subclasses must provide __new__ or __init__, 645 __getitem__, __setitem__, __delitem__, __len__, and insert(). 646 647 """ 648 649 @abstractmethod 650 def __setitem__(self, index, value): 651 raise IndexError 652 653 @abstractmethod 654 def __delitem__(self, index): 655 raise IndexError 656 657 @abstractmethod 658 def insert(self, index, value): 659 'S.insert(index, object) -- insert object before index' 660 raise IndexError 661 662 def append(self, value): 663 'S.append(object) -- append object to the end of the sequence' 664 self.insert(len(self), value) 665 666 def reverse(self): 667 'S.reverse() -- reverse *IN PLACE*' 668 n = len(self) 669 for i in range(n//2): 670 self[i], self[n-i-1] = self[n-i-1], self[i] 671 672 def extend(self, values): 673 'S.extend(iterable) -- extend sequence by appending elements from the iterable' 674 for v in values: 675 self.append(v) 676 677 def pop(self, index=-1): 678 '''S.pop([index]) -> item -- remove and return item at index (default last). 679 Raise IndexError if list is empty or index is out of range. 680 ''' 681 v = self[index] 682 del self[index] 683 return v 684 685 def remove(self, value): 686 '''S.remove(value) -- remove first occurrence of value. 687 Raise ValueError if the value is not present. 688 ''' 689 del self[self.index(value)] 690 691 def __iadd__(self, values): 692 self.extend(values) 693 return self 694 695MutableSequence.register(list) 696