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 6 DON'T USE THIS MODULE DIRECTLY! The classes here should be imported 7 via collections; they are defined here only to alleviate certain 8 bootstrapping issues. Unit tests are in test_collections. 9 """ 10 11 from abc import ABCMeta, abstractmethod 12 import 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 24 def _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 32 class 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 55 class 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 70 Iterable.register(str) 71 72 73 class 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 91 class 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 106 class 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 121 class 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 139 class 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 279 Set.register(frozenset) 280 281 282 class 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 359 MutableSet.register(set) 360 361 362 ### MAPPINGS ### 363 364 365 class 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 431 class 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 443 class 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 456 457 class ItemsView(MappingView, Set): 458 459 @classmethod 460 def _from_iterable(self, it): 461 return set(it) 462 463 def __contains__(self, item): 464 key, value = item 465 try: 466 v = self._mapping[key] 467 except KeyError: 468 return False 469 else: 470 return v == value 471 472 def __iter__(self): 473 for key in self._mapping: 474 yield (key, self._mapping[key]) 475 476 477 class ValuesView(MappingView): 478 479 def __contains__(self, value): 480 for key in self._mapping: 481 if value == self._mapping[key]: 482 return True 483 return False 484 485 def __iter__(self): 486 for key in self._mapping: 487 yield self._mapping[key] 488 489 490 class MutableMapping(Mapping): 491 492 """A MutableMapping is a generic container for associating 493 key/value pairs. 494 495 This class provides concrete generic implementations of all 496 methods except for __getitem__, __setitem__, __delitem__, 497 __iter__, and __len__. 498 499 """ 500 501 @abstractmethod 502 def __setitem__(self, key, value): 503 raise KeyError 504 505 @abstractmethod 506 def __delitem__(self, key): 507 raise KeyError 508 509 __marker = object() 510 511 def pop(self, key, default=__marker): 512 '''D.pop(k[,d]) -> v, remove specified key and return the corresponding value. 513 If key is not found, d is returned if given, otherwise KeyError is raised. 514 ''' 515 try: 516 value = self[key] 517 except KeyError: 518 if default is self.__marker: 519 raise 520 return default 521 else: 522 del self[key] 523 return value 524 525 def popitem(self): 526 '''D.popitem() -> (k, v), remove and return some (key, value) pair 527 as a 2-tuple; but raise KeyError if D is empty. 528 ''' 529 try: 530 key = next(iter(self)) 531 except StopIteration: 532 raise KeyError 533 value = self[key] 534 del self[key] 535 return key, value 536 537 def clear(self): 538 'D.clear() -> None. Remove all items from D.' 539 try: 540 while True: 541 self.popitem() 542 except KeyError: 543 pass 544 545 def update(*args, **kwds): 546 ''' D.update([E, ]**F) -> None. Update D from mapping/iterable E and F. 547 If E present and has a .keys() method, does: for k in E: D[k] = E[k] 548 If E present and lacks .keys() method, does: for (k, v) in E: D[k] = v 549 In either case, this is followed by: for k, v in F.items(): D[k] = v 550 ''' 551 if not args: 552 raise TypeError("descriptor 'update' of 'MutableMapping' object " 553 "needs an argument") 554 self = args[0] 555 args = args[1:] 556 if len(args) > 1: 557 raise TypeError('update expected at most 1 arguments, got %d' % 558 len(args)) 559 if args: 560 other = args[0] 561 if isinstance(other, Mapping): 562 for key in other: 563 self[key] = other[key] 564 elif hasattr(other, "keys"): 565 for key in other.keys(): 566 self[key] = other[key] 567 else: 568 for key, value in other: 569 self[key] = value 570 for key, value in kwds.items(): 571 self[key] = value 572 573 def setdefault(self, key, default=None): 574 'D.setdefault(k[,d]) -> D.get(k,d), also set D[k]=d if k not in D' 575 try: 576 return self[key] 577 except KeyError: 578 self[key] = default 579 return default 580 581 MutableMapping.register(dict) 582 583 584 ### SEQUENCES ### 585 586 587 class Sequence(Sized, Iterable, Container): 588 """All the operations on a read-only sequence. 589 590 Concrete subclasses must override __new__ or __init__, 591 __getitem__, and __len__. 592 """ 593 594 @abstractmethod 595 def __getitem__(self, index): 596 raise IndexError 597 598 def __iter__(self): 599 i = 0 600 try: 601 while True: 602 v = self[i] 603 yield v 604 i += 1 605 except IndexError: 606 return 607 608 def __contains__(self, value): 609 for v in self: 610 if v == value: 611 return True 612 return False 613 614 def __reversed__(self): 615 for i in reversed(range(len(self))): 616 yield self[i] 617 618 def index(self, value): 619 '''S.index(value) -> integer -- return first index of value. 620 Raises ValueError if the value is not present. 621 ''' 622 for i, v in enumerate(self): 623 if v == value: 624 return i 625 raise ValueError 626 627 def count(self, value): 628 'S.count(value) -> integer -- return number of occurrences of value' 629 return sum(1 for v in self if v == value) 630 631 Sequence.register(tuple) 632 Sequence.register(basestring) 633 Sequence.register(buffer) 634 Sequence.register(xrange) 635 636 637 class MutableSequence(Sequence): 638 639 """All the operations on a read-only sequence. 640 641 Concrete subclasses must provide __new__ or __init__, 642 __getitem__, __setitem__, __delitem__, __len__, and insert(). 643 644 """ 645 646 @abstractmethod 647 def __setitem__(self, index, value): 648 raise IndexError 649 650 @abstractmethod 651 def __delitem__(self, index): 652 raise IndexError 653 654 @abstractmethod 655 def insert(self, index, value): 656 'S.insert(index, object) -- insert object before index' 657 raise IndexError 658 659 def append(self, value): 660 'S.append(object) -- append object to the end of the sequence' 661 self.insert(len(self), value) 662 663 def reverse(self): 664 'S.reverse() -- reverse *IN PLACE*' 665 n = len(self) 666 for i in range(n//2): 667 self[i], self[n-i-1] = self[n-i-1], self[i] 668 669 def extend(self, values): 670 'S.extend(iterable) -- extend sequence by appending elements from the iterable' 671 for v in values: 672 self.append(v) 673 674 def pop(self, index=-1): 675 '''S.pop([index]) -> item -- remove and return item at index (default last). 676 Raise IndexError if list is empty or index is out of range. 677 ''' 678 v = self[index] 679 del self[index] 680 return v 681 682 def remove(self, value): 683 '''S.remove(value) -- remove first occurrence of value. 684 Raise ValueError if the value is not present. 685 ''' 686 del self[self.index(value)] 687 688 def __iadd__(self, values): 689 self.extend(values) 690 return self 691 692 MutableSequence.register(list) 693
