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 raise StopIteration 78 79 def __iter__(self): 80 return self 81 82 @classmethod 83 def __subclasshook__(cls, C): 84 if cls is Iterator: 85 if _hasattr(C, "next") and _hasattr(C, "__iter__"): 86 return True 87 return NotImplemented 88 89 90 class Sized: 91 __metaclass__ = ABCMeta 92 93 @abstractmethod 94 def __len__(self): 95 return 0 96 97 @classmethod 98 def __subclasshook__(cls, C): 99 if cls is Sized: 100 if _hasattr(C, "__len__"): 101 return True 102 return NotImplemented 103 104 105 class Container: 106 __metaclass__ = ABCMeta 107 108 @abstractmethod 109 def __contains__(self, x): 110 return False 111 112 @classmethod 113 def __subclasshook__(cls, C): 114 if cls is Container: 115 if _hasattr(C, "__contains__"): 116 return True 117 return NotImplemented 118 119 120 class Callable: 121 __metaclass__ = ABCMeta 122 123 @abstractmethod 124 def __call__(self, *args, **kwds): 125 return False 126 127 @classmethod 128 def __subclasshook__(cls, C): 129 if cls is Callable: 130 if _hasattr(C, "__call__"): 131 return True 132 return NotImplemented 133 134 135 ### SETS ### 136 137 138 class Set(Sized, Iterable, Container): 139 """A set is a finite, iterable container. 140 141 This class provides concrete generic implementations of all 142 methods except for __contains__, __iter__ and __len__. 143 144 To override the comparisons (presumably for speed, as the 145 semantics are fixed), all you have to do is redefine __le__ and 146 then the other operations will automatically follow suit. 147 """ 148 149 def __le__(self, other): 150 if not isinstance(other, Set): 151 return NotImplemented 152 if len(self) > len(other): 153 return False 154 for elem in self: 155 if elem not in other: 156 return False 157 return True 158 159 def __lt__(self, other): 160 if not isinstance(other, Set): 161 return NotImplemented 162 return len(self) < len(other) and self.__le__(other) 163 164 def __gt__(self, other): 165 if not isinstance(other, Set): 166 return NotImplemented 167 return other < self 168 169 def __ge__(self, other): 170 if not isinstance(other, Set): 171 return NotImplemented 172 return other <= self 173 174 def __eq__(self, other): 175 if not isinstance(other, Set): 176 return NotImplemented 177 return len(self) == len(other) and self.__le__(other) 178 179 def __ne__(self, other): 180 return not (self == other) 181 182 @classmethod 183 def _from_iterable(cls, it): 184 '''Construct an instance of the class from any iterable input. 185 186 Must override this method if the class constructor signature 187 does not accept an iterable for an input. 188 ''' 189 return cls(it) 190 191 def __and__(self, other): 192 if not isinstance(other, Iterable): 193 return NotImplemented 194 return self._from_iterable(value for value in other if value in self) 195 196 def isdisjoint(self, other): 197 for value in other: 198 if value in self: 199 return False 200 return True 201 202 def __or__(self, other): 203 if not isinstance(other, Iterable): 204 return NotImplemented 205 chain = (e for s in (self, other) for e in s) 206 return self._from_iterable(chain) 207 208 def __sub__(self, other): 209 if not isinstance(other, Set): 210 if not isinstance(other, Iterable): 211 return NotImplemented 212 other = self._from_iterable(other) 213 return self._from_iterable(value for value in self 214 if value not in other) 215 216 def __xor__(self, other): 217 if not isinstance(other, Set): 218 if not isinstance(other, Iterable): 219 return NotImplemented 220 other = self._from_iterable(other) 221 return (self - other) | (other - self) 222 223 # Sets are not hashable by default, but subclasses can change this 224 __hash__ = None 225 226 def _hash(self): 227 """Compute the hash value of a set. 228 229 Note that we don't define __hash__: not all sets are hashable. 230 But if you define a hashable set type, its __hash__ should 231 call this function. 232 233 This must be compatible __eq__. 234 235 All sets ought to compare equal if they contain the same 236 elements, regardless of how they are implemented, and 237 regardless of the order of the elements; so there's not much 238 freedom for __eq__ or __hash__. We match the algorithm used 239 by the built-in frozenset type. 240 """ 241 MAX = sys.maxint 242 MASK = 2 * MAX + 1 243 n = len(self) 244 h = 1927868237 * (n + 1) 245 h &= MASK 246 for x in self: 247 hx = hash(x) 248 h ^= (hx ^ (hx << 16) ^ 89869747) * 3644798167 249 h &= MASK 250 h = h * 69069 + 907133923 251 h &= MASK 252 if h > MAX: 253 h -= MASK + 1 254 if h == -1: 255 h = 590923713 256 return h 257 258 Set.register(frozenset) 259 260 261 class MutableSet(Set): 262 263 @abstractmethod 264 def add(self, value): 265 """Add an element.""" 266 raise NotImplementedError 267 268 @abstractmethod 269 def discard(self, value): 270 """Remove an element. Do not raise an exception if absent.""" 271 raise NotImplementedError 272 273 def remove(self, value): 274 """Remove an element. If not a member, raise a KeyError.""" 275 if value not in self: 276 raise KeyError(value) 277 self.discard(value) 278 279 def pop(self): 280 """Return the popped value. Raise KeyError if empty.""" 281 it = iter(self) 282 try: 283 value = next(it) 284 except StopIteration: 285 raise KeyError 286 self.discard(value) 287 return value 288 289 def clear(self): 290 """This is slow (creates N new iterators!) but effective.""" 291 try: 292 while True: 293 self.pop() 294 except KeyError: 295 pass 296 297 def __ior__(self, it): 298 for value in it: 299 self.add(value) 300 return self 301 302 def __iand__(self, it): 303 for value in (self - it): 304 self.discard(value) 305 return self 306 307 def __ixor__(self, it): 308 if it is self: 309 self.clear() 310 else: 311 if not isinstance(it, Set): 312 it = self._from_iterable(it) 313 for value in it: 314 if value in self: 315 self.discard(value) 316 else: 317 self.add(value) 318 return self 319 320 def __isub__(self, it): 321 if it is self: 322 self.clear() 323 else: 324 for value in it: 325 self.discard(value) 326 return self 327 328 MutableSet.register(set) 329 330 331 ### MAPPINGS ### 332 333 334 class Mapping(Sized, Iterable, Container): 335 336 @abstractmethod 337 def __getitem__(self, key): 338 raise KeyError 339 340 def get(self, key, default=None): 341 try: 342 return self[key] 343 except KeyError: 344 return default 345 346 def __contains__(self, key): 347 try: 348 self[key] 349 except KeyError: 350 return False 351 else: 352 return True 353 354 def iterkeys(self): 355 return iter(self) 356 357 def itervalues(self): 358 for key in self: 359 yield self[key] 360 361 def iteritems(self): 362 for key in self: 363 yield (key, self[key]) 364 365 def keys(self): 366 return list(self) 367 368 def items(self): 369 return [(key, self[key]) for key in self] 370 371 def values(self): 372 return [self[key] for key in self] 373 374 # Mappings are not hashable by default, but subclasses can change this 375 __hash__ = None 376 377 def __eq__(self, other): 378 if not isinstance(other, Mapping): 379 return NotImplemented 380 return dict(self.items()) == dict(other.items()) 381 382 def __ne__(self, other): 383 return not (self == other) 384 385 class MappingView(Sized): 386 387 def __init__(self, mapping): 388 self._mapping = mapping 389 390 def __len__(self): 391 return len(self._mapping) 392 393 def __repr__(self): 394 return '{0.__class__.__name__}({0._mapping!r})'.format(self) 395 396 397 class KeysView(MappingView, Set): 398 399 @classmethod 400 def _from_iterable(self, it): 401 return set(it) 402 403 def __contains__(self, key): 404 return key in self._mapping 405 406 def __iter__(self): 407 for key in self._mapping: 408 yield key 409 410 411 class ItemsView(MappingView, Set): 412 413 @classmethod 414 def _from_iterable(self, it): 415 return set(it) 416 417 def __contains__(self, item): 418 key, value = item 419 try: 420 v = self._mapping[key] 421 except KeyError: 422 return False 423 else: 424 return v == value 425 426 def __iter__(self): 427 for key in self._mapping: 428 yield (key, self._mapping[key]) 429 430 431 class ValuesView(MappingView): 432 433 def __contains__(self, value): 434 for key in self._mapping: 435 if value == self._mapping[key]: 436 return True 437 return False 438 439 def __iter__(self): 440 for key in self._mapping: 441 yield self._mapping[key] 442 443 444 class MutableMapping(Mapping): 445 446 @abstractmethod 447 def __setitem__(self, key, value): 448 raise KeyError 449 450 @abstractmethod 451 def __delitem__(self, key): 452 raise KeyError 453 454 __marker = object() 455 456 def pop(self, key, default=__marker): 457 try: 458 value = self[key] 459 except KeyError: 460 if default is self.__marker: 461 raise 462 return default 463 else: 464 del self[key] 465 return value 466 467 def popitem(self): 468 try: 469 key = next(iter(self)) 470 except StopIteration: 471 raise KeyError 472 value = self[key] 473 del self[key] 474 return key, value 475 476 def clear(self): 477 try: 478 while True: 479 self.popitem() 480 except KeyError: 481 pass 482 483 def update(*args, **kwds): 484 if len(args) > 2: 485 raise TypeError("update() takes at most 2 positional " 486 "arguments ({} given)".format(len(args))) 487 elif not args: 488 raise TypeError("update() takes at least 1 argument (0 given)") 489 self = args[0] 490 other = args[1] if len(args) >= 2 else () 491 492 if isinstance(other, Mapping): 493 for key in other: 494 self[key] = other[key] 495 elif hasattr(other, "keys"): 496 for key in other.keys(): 497 self[key] = other[key] 498 else: 499 for key, value in other: 500 self[key] = value 501 for key, value in kwds.items(): 502 self[key] = value 503 504 def setdefault(self, key, default=None): 505 try: 506 return self[key] 507 except KeyError: 508 self[key] = default 509 return default 510 511 MutableMapping.register(dict) 512 513 514 ### SEQUENCES ### 515 516 517 class Sequence(Sized, Iterable, Container): 518 """All the operations on a read-only sequence. 519 520 Concrete subclasses must override __new__ or __init__, 521 __getitem__, and __len__. 522 """ 523 524 @abstractmethod 525 def __getitem__(self, index): 526 raise IndexError 527 528 def __iter__(self): 529 i = 0 530 try: 531 while True: 532 v = self[i] 533 yield v 534 i += 1 535 except IndexError: 536 return 537 538 def __contains__(self, value): 539 for v in self: 540 if v == value: 541 return True 542 return False 543 544 def __reversed__(self): 545 for i in reversed(range(len(self))): 546 yield self[i] 547 548 def index(self, value): 549 for i, v in enumerate(self): 550 if v == value: 551 return i 552 raise ValueError 553 554 def count(self, value): 555 return sum(1 for v in self if v == value) 556 557 Sequence.register(tuple) 558 Sequence.register(basestring) 559 Sequence.register(buffer) 560 Sequence.register(xrange) 561 562 563 class MutableSequence(Sequence): 564 565 @abstractmethod 566 def __setitem__(self, index, value): 567 raise IndexError 568 569 @abstractmethod 570 def __delitem__(self, index): 571 raise IndexError 572 573 @abstractmethod 574 def insert(self, index, value): 575 raise IndexError 576 577 def append(self, value): 578 self.insert(len(self), value) 579 580 def reverse(self): 581 n = len(self) 582 for i in range(n//2): 583 self[i], self[n-i-1] = self[n-i-1], self[i] 584 585 def extend(self, values): 586 for v in values: 587 self.append(v) 588 589 def pop(self, index=-1): 590 v = self[index] 591 del self[index] 592 return v 593 594 def remove(self, value): 595 del self[self.index(value)] 596 597 def __iadd__(self, values): 598 self.extend(values) 599 return self 600 601 MutableSequence.register(list) 602
