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