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), all you have to do is redefine __le__ and 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 other < self 169 170 def __ge__(self, other): 171 if not isinstance(other, Set): 172 return NotImplemented 173 return other <= self 174 175 def __eq__(self, other): 176 if not isinstance(other, Set): 177 return NotImplemented 178 return len(self) == len(other) and self.__le__(other) 179 180 def __ne__(self, other): 181 return not (self == other) 182 183 @classmethod 184 def _from_iterable(cls, it): 185 '''Construct an instance of the class from any iterable input. 186 187 Must override this method if the class constructor signature 188 does not accept an iterable for an input. 189 ''' 190 return cls(it) 191 192 def __and__(self, other): 193 if not isinstance(other, Iterable): 194 return NotImplemented 195 return self._from_iterable(value for value in other if value in self) 196 197 def isdisjoint(self, other): 198 'Return True if two sets have a null intersection.' 199 for value in other: 200 if value in self: 201 return False 202 return True 203 204 def __or__(self, other): 205 if not isinstance(other, Iterable): 206 return NotImplemented 207 chain = (e for s in (self, other) for e in s) 208 return self._from_iterable(chain) 209 210 def __sub__(self, other): 211 if not isinstance(other, Set): 212 if not isinstance(other, Iterable): 213 return NotImplemented 214 other = self._from_iterable(other) 215 return self._from_iterable(value for value in self 216 if value not in other) 217 218 def __xor__(self, other): 219 if not isinstance(other, Set): 220 if not isinstance(other, Iterable): 221 return NotImplemented 222 other = self._from_iterable(other) 223 return (self - other) | (other - self) 224 225 # Sets are not hashable by default, but subclasses can change this 226 __hash__ = None 227 228 def _hash(self): 229 """Compute the hash value of a set. 230 231 Note that we don't define __hash__: not all sets are hashable. 232 But if you define a hashable set type, its __hash__ should 233 call this function. 234 235 This must be compatible __eq__. 236 237 All sets ought to compare equal if they contain the same 238 elements, regardless of how they are implemented, and 239 regardless of the order of the elements; so there's not much 240 freedom for __eq__ or __hash__. We match the algorithm used 241 by the built-in frozenset type. 242 """ 243 MAX = sys.maxint 244 MASK = 2 * MAX + 1 245 n = len(self) 246 h = 1927868237 * (n + 1) 247 h &= MASK 248 for x in self: 249 hx = hash(x) 250 h ^= (hx ^ (hx << 16) ^ 89869747) * 3644798167 251 h &= MASK 252 h = h * 69069 + 907133923 253 h &= MASK 254 if h > MAX: 255 h -= MASK + 1 256 if h == -1: 257 h = 590923713 258 return h 259 260 Set.register(frozenset) 261 262 263 class MutableSet(Set): 264 """A mutable set is a finite, iterable container. 265 266 This class provides concrete generic implementations of all 267 methods except for __contains__, __iter__, __len__, 268 add(), and discard(). 269 270 To override the comparisons (presumably for speed, as the 271 semantics are fixed), all you have to do is redefine __le__ and 272 then the other operations will automatically follow suit. 273 """ 274 275 @abstractmethod 276 def add(self, value): 277 """Add an element.""" 278 raise NotImplementedError 279 280 @abstractmethod 281 def discard(self, value): 282 """Remove an element. Do not raise an exception if absent.""" 283 raise NotImplementedError 284 285 def remove(self, value): 286 """Remove an element. If not a member, raise a KeyError.""" 287 if value not in self: 288 raise KeyError(value) 289 self.discard(value) 290 291 def pop(self): 292 """Return the popped value. Raise KeyError if empty.""" 293 it = iter(self) 294 try: 295 value = next(it) 296 except StopIteration: 297 raise KeyError 298 self.discard(value) 299 return value 300 301 def clear(self): 302 """This is slow (creates N new iterators!) but effective.""" 303 try: 304 while True: 305 self.pop() 306 except KeyError: 307 pass 308 309 def __ior__(self, it): 310 for value in it: 311 self.add(value) 312 return self 313 314 def __iand__(self, it): 315 for value in (self - it): 316 self.discard(value) 317 return self 318 319 def __ixor__(self, it): 320 if it is self: 321 self.clear() 322 else: 323 if not isinstance(it, Set): 324 it = self._from_iterable(it) 325 for value in it: 326 if value in self: 327 self.discard(value) 328 else: 329 self.add(value) 330 return self 331 332 def __isub__(self, it): 333 if it is self: 334 self.clear() 335 else: 336 for value in it: 337 self.discard(value) 338 return self 339 340 MutableSet.register(set) 341 342 343 ### MAPPINGS ### 344 345 346 class Mapping(Sized, Iterable, Container): 347 348 """A Mapping is a generic container for associating key/value 349 pairs. 350 351 This class provides concrete generic implementations of all 352 methods except for __getitem__, __iter__, and __len__. 353 354 """ 355 356 @abstractmethod 357 def __getitem__(self, key): 358 raise KeyError 359 360 def get(self, key, default=None): 361 'D.get(k[,d]) -> D[k] if k in D, else d. d defaults to None.' 362 try: 363 return self[key] 364 except KeyError: 365 return default 366 367 def __contains__(self, key): 368 try: 369 self[key] 370 except KeyError: 371 return False 372 else: 373 return True 374 375 def iterkeys(self): 376 'D.iterkeys() -> an iterator over the keys of D' 377 return iter(self) 378 379 def itervalues(self): 380 'D.itervalues() -> an iterator over the values of D' 381 for key in self: 382 yield self[key] 383 384 def iteritems(self): 385 'D.iteritems() -> an iterator over the (key, value) items of D' 386 for key in self: 387 yield (key, self[key]) 388 389 def keys(self): 390 "D.keys() -> list of D's keys" 391 return list(self) 392 393 def items(self): 394 "D.items() -> list of D's (key, value) pairs, as 2-tuples" 395 return [(key, self[key]) for key in self] 396 397 def values(self): 398 "D.values() -> list of D's values" 399 return [self[key] for key in self] 400 401 # Mappings are not hashable by default, but subclasses can change this 402 __hash__ = None 403 404 def __eq__(self, other): 405 if not isinstance(other, Mapping): 406 return NotImplemented 407 return dict(self.items()) == dict(other.items()) 408 409 def __ne__(self, other): 410 return not (self == other) 411 412 class MappingView(Sized): 413 414 def __init__(self, mapping): 415 self._mapping = mapping 416 417 def __len__(self): 418 return len(self._mapping) 419 420 def __repr__(self): 421 return '{0.__class__.__name__}({0._mapping!r})'.format(self) 422 423 424 class KeysView(MappingView, Set): 425 426 @classmethod 427 def _from_iterable(self, it): 428 return set(it) 429 430 def __contains__(self, key): 431 return key in self._mapping 432 433 def __iter__(self): 434 for key in self._mapping: 435 yield key 436 437 438 class ItemsView(MappingView, Set): 439 440 @classmethod 441 def _from_iterable(self, it): 442 return set(it) 443 444 def __contains__(self, item): 445 key, value = item 446 try: 447 v = self._mapping[key] 448 except KeyError: 449 return False 450 else: 451 return v == value 452 453 def __iter__(self): 454 for key in self._mapping: 455 yield (key, self._mapping[key]) 456 457 458 class ValuesView(MappingView): 459 460 def __contains__(self, value): 461 for key in self._mapping: 462 if value == self._mapping[key]: 463 return True 464 return False 465 466 def __iter__(self): 467 for key in self._mapping: 468 yield self._mapping[key] 469 470 471 class MutableMapping(Mapping): 472 473 """A MutableMapping is a generic container for associating 474 key/value pairs. 475 476 This class provides concrete generic implementations of all 477 methods except for __getitem__, __setitem__, __delitem__, 478 __iter__, and __len__. 479 480 """ 481 482 @abstractmethod 483 def __setitem__(self, key, value): 484 raise KeyError 485 486 @abstractmethod 487 def __delitem__(self, key): 488 raise KeyError 489 490 __marker = object() 491 492 def pop(self, key, default=__marker): 493 '''D.pop(k[,d]) -> v, remove specified key and return the corresponding value. 494 If key is not found, d is returned if given, otherwise KeyError is raised. 495 ''' 496 try: 497 value = self[key] 498 except KeyError: 499 if default is self.__marker: 500 raise 501 return default 502 else: 503 del self[key] 504 return value 505 506 def popitem(self): 507 '''D.popitem() -> (k, v), remove and return some (key, value) pair 508 as a 2-tuple; but raise KeyError if D is empty. 509 ''' 510 try: 511 key = next(iter(self)) 512 except StopIteration: 513 raise KeyError 514 value = self[key] 515 del self[key] 516 return key, value 517 518 def clear(self): 519 'D.clear() -> None. Remove all items from D.' 520 try: 521 while True: 522 self.popitem() 523 except KeyError: 524 pass 525 526 def update(*args, **kwds): 527 ''' D.update([E, ]**F) -> None. Update D from mapping/iterable E and F. 528 If E present and has a .keys() method, does: for k in E: D[k] = E[k] 529 If E present and lacks .keys() method, does: for (k, v) in E: D[k] = v 530 In either case, this is followed by: for k, v in F.items(): D[k] = v 531 ''' 532 if len(args) > 2: 533 raise TypeError("update() takes at most 2 positional " 534 "arguments ({} given)".format(len(args))) 535 elif not args: 536 raise TypeError("update() takes at least 1 argument (0 given)") 537 self = args[0] 538 other = args[1] if len(args) >= 2 else () 539 540 if isinstance(other, Mapping): 541 for key in other: 542 self[key] = other[key] 543 elif hasattr(other, "keys"): 544 for key in other.keys(): 545 self[key] = other[key] 546 else: 547 for key, value in other: 548 self[key] = value 549 for key, value in kwds.items(): 550 self[key] = value 551 552 def setdefault(self, key, default=None): 553 'D.setdefault(k[,d]) -> D.get(k,d), also set D[k]=d if k not in D' 554 try: 555 return self[key] 556 except KeyError: 557 self[key] = default 558 return default 559 560 MutableMapping.register(dict) 561 562 563 ### SEQUENCES ### 564 565 566 class Sequence(Sized, Iterable, Container): 567 """All the operations on a read-only sequence. 568 569 Concrete subclasses must override __new__ or __init__, 570 __getitem__, and __len__. 571 """ 572 573 @abstractmethod 574 def __getitem__(self, index): 575 raise IndexError 576 577 def __iter__(self): 578 i = 0 579 try: 580 while True: 581 v = self[i] 582 yield v 583 i += 1 584 except IndexError: 585 return 586 587 def __contains__(self, value): 588 for v in self: 589 if v == value: 590 return True 591 return False 592 593 def __reversed__(self): 594 for i in reversed(range(len(self))): 595 yield self[i] 596 597 def index(self, value): 598 '''S.index(value) -> integer -- return first index of value. 599 Raises ValueError if the value is not present. 600 ''' 601 for i, v in enumerate(self): 602 if v == value: 603 return i 604 raise ValueError 605 606 def count(self, value): 607 'S.count(value) -> integer -- return number of occurrences of value' 608 return sum(1 for v in self if v == value) 609 610 Sequence.register(tuple) 611 Sequence.register(basestring) 612 Sequence.register(buffer) 613 Sequence.register(xrange) 614 615 616 class MutableSequence(Sequence): 617 618 """All the operations on a read-only sequence. 619 620 Concrete subclasses must provide __new__ or __init__, 621 __getitem__, __setitem__, __delitem__, __len__, and insert(). 622 623 """ 624 625 @abstractmethod 626 def __setitem__(self, index, value): 627 raise IndexError 628 629 @abstractmethod 630 def __delitem__(self, index): 631 raise IndexError 632 633 @abstractmethod 634 def insert(self, index, value): 635 'S.insert(index, object) -- insert object before index' 636 raise IndexError 637 638 def append(self, value): 639 'S.append(object) -- append object to the end of the sequence' 640 self.insert(len(self), value) 641 642 def reverse(self): 643 'S.reverse() -- reverse *IN PLACE*' 644 n = len(self) 645 for i in range(n//2): 646 self[i], self[n-i-1] = self[n-i-1], self[i] 647 648 def extend(self, values): 649 'S.extend(iterable) -- extend sequence by appending elements from the iterable' 650 for v in values: 651 self.append(v) 652 653 def pop(self, index=-1): 654 '''S.pop([index]) -> item -- remove and return item at index (default last). 655 Raise IndexError if list is empty or index is out of range. 656 ''' 657 v = self[index] 658 del self[index] 659 return v 660 661 def remove(self, value): 662 '''S.remove(value) -- remove first occurrence of value. 663 Raise ValueError if the value is not present. 664 ''' 665 del self[self.index(value)] 666 667 def __iadd__(self, values): 668 self.extend(values) 669 return self 670 671 MutableSequence.register(list) 672
