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