Lib/_abcoll.py

   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
  13 __all__ = ["Hashable", "Iterable", "Iterator",
  14            "Sized", "Container", "Callable",
  15            "Set", "MutableSet",
  16            "Mapping", "MutableMapping",
  17            "MappingView", "KeysView", "ItemsView", "ValuesView",
  18            "Sequence", "MutableSequence",
  19            ]
  20
  21 ### ONE-TRICK PONIES ###
  22
  23 class Hashable:
  24     __metaclass__ = ABCMeta
  25
  26     @abstractmethod
  27     def __hash__(self):
  28         return 0
  29
  30     @classmethod
  31     def __subclasshook__(cls, C):
  32         if cls is Hashable:
  33             for B in C.__mro__:
  34                 if "__hash__" in B.__dict__:
  35                     if B.__dict__["__hash__"]:
  36                         return True
  37                     break
  38         return NotImplemented
  39
  40
  41 class Iterable:
  42     __metaclass__ = ABCMeta
  43
  44     @abstractmethod
  45     def __iter__(self):
  46         while False:
  47             yield None
  48
  49     @classmethod
  50     def __subclasshook__(cls, C):
  51         if cls is Iterable:
  52             if any("__iter__" in B.__dict__ for B in C.__mro__):
  53                 return True
  54         return NotImplemented
  55
  56 Iterable.register(str)
  57
  58
  59 class Iterator:
  60     __metaclass__ = ABCMeta
  61
  62     @abstractmethod
  63     def __next__(self):
  64         raise StopIteration
  65
  66     def __iter__(self):
  67         return self
  68
  69     @classmethod
  70     def __subclasshook__(cls, C):
  71         if cls is Iterator:
  72             if any("next" in B.__dict__ for B in C.__mro__):
  73                 return True
  74         return NotImplemented
  75
  76
  77 class Sized:
  78     __metaclass__ = ABCMeta
  79
  80     @abstractmethod
  81     def __len__(self):
  82         return 0
  83
  84     @classmethod
  85     def __subclasshook__(cls, C):
  86         if cls is Sized:
  87             if any("__len__" in B.__dict__ for B in C.__mro__):
  88                 return True
  89         return NotImplemented
  90
  91
  92 class Container:
  93     __metaclass__ = ABCMeta
  94
  95     @abstractmethod
  96     def __contains__(self, x):
  97         return False
  98
  99     @classmethod
 100     def __subclasshook__(cls, C):
 101         if cls is Container:
 102             if any("__contains__" in B.__dict__ for B in C.__mro__):
 103                 return True
 104         return NotImplemented
 105
 106
 107 class Callable:
 108     __metaclass__ = ABCMeta
 109
 110     @abstractmethod
 111     def __contains__(self, x):
 112         return False
 113
 114     @classmethod
 115     def __subclasshook__(cls, C):
 116         if cls is Callable:
 117             if any("__call__" in B.__dict__ for B in C.__mro__):
 118                 return True
 119         return NotImplemented
 120
 121
 122 ### SETS ###
 123
 124
 125 class Set:
 126     __metaclass__ = ABCMeta
 127
 128     """A set is a finite, iterable container.
 129
 130     This class provides concrete generic implementations of all
 131     methods except for __contains__, __iter__ and __len__.
 132
 133     To override the comparisons (presumably for speed, as the
 134     semantics are fixed), all you have to do is redefine __le__ and
 135     then the other operations will automatically follow suit.
 136     """
 137
 138     @abstractmethod
 139     def __contains__(self, value):
 140         return False
 141
 142     @abstractmethod
 143     def __iter__(self):
 144         while False:
 145             yield None
 146
 147     @abstractmethod
 148     def __len__(self):
 149         return 0
 150
 151     def __le__(self, other):
 152         if not isinstance(other, Set):
 153             return NotImplemented
 154         if len(self) > len(other):
 155             return False
 156         for elem in self:
 157             if elem not in other:
 158                 return False
 159         return True
 160
 161     def __lt__(self, other):
 162         if not isinstance(other, Set):
 163             return NotImplemented
 164         return len(self) < len(other) and self.__le__(other)
 165
 166     def __eq__(self, other):
 167         if not isinstance(other, Set):
 168             return NotImplemented
 169         return len(self) == len(other) and self.__le__(other)
 170
 171     @classmethod
 172     def _from_iterable(cls, it):
 173         return frozenset(it)
 174
 175     def __and__(self, other):
 176         if not isinstance(other, Iterable):
 177             return NotImplemented
 178         return self._from_iterable(value for value in other if value in self)
 179
 180     def __or__(self, other):
 181         if not isinstance(other, Iterable):
 182             return NotImplemented
 183         return self._from_iterable(itertools.chain(self, other))
 184
 185     def __sub__(self, other):
 186         if not isinstance(other, Set):
 187             if not isinstance(other, Iterable):
 188                 return NotImplemented
 189             other = self._from_iterable(other)
 190         return self._from_iterable(value for value in self
 191                                    if value not in other)
 192
 193     def __xor__(self, other):
 194         if not isinstance(other, Set):
 195             if not isinstance(other, Iterable):
 196                 return NotImplemented
 197             other = self._from_iterable(other)
 198         return (self - other) | (other - self)
 199
 200     def _hash(self):
 201         """Compute the hash value of a set.
 202
 203         Note that we don't define __hash__: not all sets are hashable.
 204         But if you define a hashable set type, its __hash__ should
 205         call this function.
 206
 207         This must be compatible __eq__.
 208
 209         All sets ought to compare equal if they contain the same
 210         elements, regardless of how they are implemented, and
 211         regardless of the order of the elements; so there's not much
 212         freedom for __eq__ or __hash__.  We match the algorithm used
 213         by the built-in frozenset type.
 214         """
 215         MAX = sys.maxint
 216         MASK = 2 * MAX + 1
 217         n = len(self)
 218         h = 1927868237 * (n + 1)
 219         h &= MASK
 220         for x in self:
 221             hx = hash(x)
 222             h ^= (hx ^ (hx << 16) ^ 89869747)  * 3644798167
 223             h &= MASK
 224         h = h * 69069 + 907133923
 225         h &= MASK
 226         if h > MAX:
 227             h -= MASK + 1
 228         if h == -1:
 229             h = 590923713
 230         return h
 231
 232 Set.register(frozenset)
 233
 234
 235 class MutableSet(Set):
 236
 237     @abstractmethod
 238     def add(self, value):
 239         """Return True if it was added, False if already there."""
 240         raise NotImplementedError
 241
 242     @abstractmethod
 243     def discard(self, value):
 244         """Return True if it was deleted, False if not there."""
 245         raise NotImplementedError
 246
 247     def pop(self):
 248         """Return the popped value.  Raise KeyError if empty."""
 249         it = iter(self)
 250         try:
 251             value = it.__next__()
 252         except StopIteration:
 253             raise KeyError
 254         self.discard(value)
 255         return value
 256
 257     def toggle(self, value):
 258         """Return True if it was added, False if deleted."""
 259         # XXX This implementation is not thread-safe
 260         if value in self:
 261             self.discard(value)
 262             return False
 263         else:
 264             self.add(value)
 265             return True
 266
 267     def clear(self):
 268         """This is slow (creates N new iterators!) but effective."""
 269         try:
 270             while True:
 271                 self.pop()
 272         except KeyError:
 273             pass
 274
 275     def __ior__(self, it):
 276         for value in it:
 277             self.add(value)
 278         return self
 279
 280     def __iand__(self, c):
 281         for value in self:
 282             if value not in c:
 283                 self.discard(value)
 284         return self
 285
 286     def __ixor__(self, it):
 287         # This calls toggle(), so if that is overridded, we call the override
 288         for value in it:
 289             self.toggle(it)
 290         return self
 291
 292     def __isub__(self, it):
 293         for value in it:
 294             self.discard(value)
 295         return self
 296
 297 MutableSet.register(set)
 298
 299
 300 ### MAPPINGS ###
 301
 302
 303 class Mapping:
 304     __metaclass__ = ABCMeta
 305
 306     @abstractmethod
 307     def __getitem__(self, key):
 308         raise KeyError
 309
 310     def get(self, key, default=None):
 311         try:
 312             return self[key]
 313         except KeyError:
 314             return default
 315
 316     def __contains__(self, key):
 317         try:
 318             self[key]
 319         except KeyError:
 320             return False
 321         else:
 322             return True
 323
 324     @abstractmethod
 325     def __len__(self):
 326         return 0
 327
 328     @abstractmethod
 329     def __iter__(self):
 330         while False:
 331             yield None
 332
 333     def keys(self):
 334         return KeysView(self)
 335
 336     def items(self):
 337         return ItemsView(self)
 338
 339     def values(self):
 340         return ValuesView(self)
 341
 342
 343 class MappingView:
 344     __metaclass__ = ABCMeta
 345
 346     def __init__(self, mapping):
 347         self._mapping = mapping
 348
 349     def __len__(self):
 350         return len(self._mapping)
 351
 352
 353 class KeysView(MappingView, Set):
 354
 355     def __contains__(self, key):
 356         return key in self._mapping
 357
 358     def __iter__(self):
 359         for key in self._mapping:
 360             yield key
 361
 362 KeysView.register(type({}.keys()))
 363
 364
 365 class ItemsView(MappingView, Set):
 366
 367     def __contains__(self, item):
 368         key, value = item
 369         try:
 370             v = self._mapping[key]
 371         except KeyError:
 372             return False
 373         else:
 374             return v == value
 375
 376     def __iter__(self):
 377         for key in self._mapping:
 378             yield (key, self._mapping[key])
 379
 380 ItemsView.register(type({}.items()))
 381
 382
 383 class ValuesView(MappingView):
 384
 385     def __contains__(self, value):
 386         for key in self._mapping:
 387             if value == self._mapping[key]:
 388                 return True
 389         return False
 390
 391     def __iter__(self):
 392         for key in self._mapping:
 393             yield self._mapping[key]
 394
 395 ValuesView.register(type({}.values()))
 396
 397
 398 class MutableMapping(Mapping):
 399
 400     @abstractmethod
 401     def __setitem__(self, key, value):
 402         raise KeyError
 403
 404     @abstractmethod
 405     def __delitem__(self, key):
 406         raise KeyError
 407
 408     __marker = object()
 409
 410     def pop(self, key, default=__marker):
 411         try:
 412             value = self[key]
 413         except KeyError:
 414             if default is self.__marker:
 415                 raise
 416             return default
 417         else:
 418             del self[key]
 419             return value
 420
 421     def popitem(self):
 422         try:
 423             key = next(iter(self))
 424         except StopIteration:
 425             raise KeyError
 426         value = self[key]
 427         del self[key]
 428         return key, value
 429
 430     def clear(self):
 431         try:
 432             while True:
 433                 self.popitem()
 434         except KeyError:
 435             pass
 436
 437     def update(self, other=(), **kwds):
 438         if isinstance(other, Mapping):
 439             for key in other:
 440                 self[key] = other[key]
 441         elif hasattr(other, "keys"):
 442             for key in other.keys():
 443                 self[key] = other[key]
 444         else:
 445             for key, value in other:
 446                 self[key] = value
 447         for key, value in kwds.items():
 448             self[key] = value
 449
 450 MutableMapping.register(dict)
 451
 452
 453 ### SEQUENCES ###
 454
 455
 456 class Sequence:
 457     __metaclass__ = ABCMeta
 458
 459     """All the operations on a read-only sequence.
 460
 461     Concrete subclasses must override __new__ or __init__,
 462     __getitem__, and __len__.
 463     """
 464
 465     @abstractmethod
 466     def __getitem__(self, index):
 467         raise IndexError
 468
 469     @abstractmethod
 470     def __len__(self):
 471         return 0
 472
 473     def __iter__(self):
 474         i = 0
 475         while True:
 476             try:
 477                 v = self[i]
 478             except IndexError:
 479                 break
 480             yield v
 481             i += 1
 482
 483     def __contains__(self, value):
 484         for v in self:
 485             if v == value:
 486                 return True
 487         return False
 488
 489     def __reversed__(self):
 490         for i in reversed(range(len(self))):
 491             yield self[i]
 492
 493     def index(self, value):
 494         for i, v in enumerate(self):
 495             if v == value:
 496                 return i
 497         raise ValueError
 498
 499     def count(self, value):
 500         return sum(1 for v in self if v == value)
 501
 502 Sequence.register(tuple)
 503 Sequence.register(basestring)
 504 Sequence.register(buffer)
 505
 506
 507 class MutableSequence(Sequence):
 508
 509     @abstractmethod
 510     def __setitem__(self, index, value):
 511         raise IndexError
 512
 513     @abstractmethod
 514     def __delitem__(self, index):
 515         raise IndexError
 516
 517     @abstractmethod
 518     def insert(self, index, value):
 519         raise IndexError
 520
 521     def append(self, value):
 522         self.insert(len(self), value)
 523
 524     def reverse(self):
 525         n = len(self)
 526         for i in range(n//2):
 527             self[i], self[n-i-1] = self[n-i-1], self[i]
 528
 529     def extend(self, values):
 530         for v in values:
 531             self.append(v)
 532
 533     def pop(self, index=-1):
 534         v = self[index]
 535         del self[index]
 536         return v
 537
 538     def remove(self, value):
 539         del self[self.index(value)]
 540
 541     def __iadd__(self, values):
 542         self.extend(values)
 543
 544 MutableSequence.register(list)