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     def _hash(self):
 211         """Compute the hash value of a set.
 212
 213         Note that we don't define __hash__: not all sets are hashable.
 214         But if you define a hashable set type, its __hash__ should
 215         call this function.
 216
 217         This must be compatible __eq__.
 218
 219         All sets ought to compare equal if they contain the same
 220         elements, regardless of how they are implemented, and
 221         regardless of the order of the elements; so there's not much
 222         freedom for __eq__ or __hash__.  We match the algorithm used
 223         by the built-in frozenset type.
 224         """
 225         MAX = sys.maxint
 226         MASK = 2 * MAX + 1
 227         n = len(self)
 228         h = 1927868237 * (n + 1)
 229         h &= MASK
 230         for x in self:
 231             hx = hash(x)
 232             h ^= (hx ^ (hx << 16) ^ 89869747)  * 3644798167
 233             h &= MASK
 234         h = h * 69069 + 907133923
 235         h &= MASK
 236         if h > MAX:
 237             h -= MASK + 1
 238         if h == -1:
 239             h = 590923713
 240         return h
 241
 242 Set.register(frozenset)
 243
 244
 245 class MutableSet(Set):
 246
 247     @abstractmethod
 248     def add(self, value):
 249         """Return True if it was added, False if already there."""
 250         raise NotImplementedError
 251
 252     @abstractmethod
 253     def discard(self, value):
 254         """Return True if it was deleted, False if not there."""
 255         raise NotImplementedError
 256
 257     def remove(self, value):
 258         """Remove an element. If not a member, raise a KeyError."""
 259         if value not in self:
 260             raise KeyError(value)
 261         self.discard(value)
 262
 263     def pop(self):
 264         """Return the popped value.  Raise KeyError if empty."""
 265         it = iter(self)
 266         try:
 267             value = it.__next__()
 268         except StopIteration:
 269             raise KeyError
 270         self.discard(value)
 271         return value
 272
 273     def clear(self):
 274         """This is slow (creates N new iterators!) but effective."""
 275         try:
 276             while True:
 277                 self.pop()
 278         except KeyError:
 279             pass
 280
 281     def __ior__(self, it):
 282         for value in it:
 283             self.add(value)
 284         return self
 285
 286     def __iand__(self, c):
 287         for value in self:
 288             if value not in c:
 289                 self.discard(value)
 290         return self
 291
 292     def __ixor__(self, it):
 293         if not isinstance(it, Set):
 294             it = self._from_iterable(it)
 295         for value in it:
 296             if value in self:
 297                 self.discard(value)
 298             else:
 299                 self.add(value)
 300         return self
 301
 302     def __isub__(self, it):
 303         for value in it:
 304             self.discard(value)
 305         return self
 306
 307 MutableSet.register(set)
 308
 309
 310 ### MAPPINGS ###
 311
 312
 313 class Mapping(Sized, Iterable, Container):
 314
 315     @abstractmethod
 316     def __getitem__(self, key):
 317         raise KeyError
 318
 319     def get(self, key, default=None):
 320         try:
 321             return self[key]
 322         except KeyError:
 323             return default
 324
 325     def __contains__(self, key):
 326         try:
 327             self[key]
 328         except KeyError:
 329             return False
 330         else:
 331             return True
 332
 333     def iterkeys(self):
 334         return iter(self)
 335
 336     def itervalues(self):
 337         for key in self:
 338             yield self[key]
 339
 340     def iteritems(self):
 341         for key in self:
 342             yield (key, self[key])
 343
 344     def keys(self):
 345         return list(self)
 346
 347     def items(self):
 348         return [(key, self[key]) for key in self]
 349
 350     def values(self):
 351         return [self[key] for key in self]
 352
 353     def __eq__(self, other):
 354         return isinstance(other, Mapping) and \
 355                dict(self.items()) == dict(other.items())
 356
 357     def __ne__(self, other):
 358         return not (self == other)
 359
 360 class MappingView(Sized):
 361
 362     def __init__(self, mapping):
 363         self._mapping = mapping
 364
 365     def __len__(self):
 366         return len(self._mapping)
 367
 368
 369 class KeysView(MappingView, Set):
 370
 371     def __contains__(self, key):
 372         return key in self._mapping
 373
 374     def __iter__(self):
 375         for key in self._mapping:
 376             yield key
 377
 378
 379 class ItemsView(MappingView, Set):
 380
 381     def __contains__(self, item):
 382         key, value = item
 383         try:
 384             v = self._mapping[key]
 385         except KeyError:
 386             return False
 387         else:
 388             return v == value
 389
 390     def __iter__(self):
 391         for key in self._mapping:
 392             yield (key, self._mapping[key])
 393
 394
 395 class ValuesView(MappingView):
 396
 397     def __contains__(self, value):
 398         for key in self._mapping:
 399             if value == self._mapping[key]:
 400                 return True
 401         return False
 402
 403     def __iter__(self):
 404         for key in self._mapping:
 405             yield self._mapping[key]
 406
 407
 408 class MutableMapping(Mapping):
 409
 410     @abstractmethod
 411     def __setitem__(self, key, value):
 412         raise KeyError
 413
 414     @abstractmethod
 415     def __delitem__(self, key):
 416         raise KeyError
 417
 418     __marker = object()
 419
 420     def pop(self, key, default=__marker):
 421         try:
 422             value = self[key]
 423         except KeyError:
 424             if default is self.__marker:
 425                 raise
 426             return default
 427         else:
 428             del self[key]
 429             return value
 430
 431     def popitem(self):
 432         try:
 433             key = next(iter(self))
 434         except StopIteration:
 435             raise KeyError
 436         value = self[key]
 437         del self[key]
 438         return key, value
 439
 440     def clear(self):
 441         try:
 442             while True:
 443                 self.popitem()
 444         except KeyError:
 445             pass
 446
 447     def update(self, other=(), **kwds):
 448         if isinstance(other, Mapping):
 449             for key in other:
 450                 self[key] = other[key]
 451         elif hasattr(other, "keys"):
 452             for key in other.keys():
 453                 self[key] = other[key]
 454         else:
 455             for key, value in other:
 456                 self[key] = value
 457         for key, value in kwds.items():
 458             self[key] = value
 459
 460     def setdefault(self, key, default=None):
 461         try:
 462             return self[key]
 463         except KeyError:
 464             self[key] = default
 465         return default
 466
 467 MutableMapping.register(dict)
 468
 469
 470 ### SEQUENCES ###
 471
 472
 473 class Sequence(Sized, Iterable, Container):
 474     """All the operations on a read-only sequence.
 475
 476     Concrete subclasses must override __new__ or __init__,
 477     __getitem__, and __len__.
 478     """
 479
 480     @abstractmethod
 481     def __getitem__(self, index):
 482         raise IndexError
 483
 484     def __iter__(self):
 485         i = 0
 486         try:
 487             while True:
 488                 v = self[i]
 489                 yield v
 490                 i += 1
 491         except IndexError:
 492             return
 493
 494     def __contains__(self, value):
 495         for v in self:
 496             if v == value:
 497                 return True
 498         return False
 499
 500     def __reversed__(self):
 501         for i in reversed(range(len(self))):
 502             yield self[i]
 503
 504     def index(self, value):
 505         for i, v in enumerate(self):
 506             if v == value:
 507                 return i
 508         raise ValueError
 509
 510     def count(self, value):
 511         return sum(1 for v in self if v == value)
 512
 513 Sequence.register(tuple)
 514 Sequence.register(basestring)
 515 Sequence.register(buffer)
 516
 517
 518 class MutableSequence(Sequence):
 519
 520     @abstractmethod
 521     def __setitem__(self, index, value):
 522         raise IndexError
 523
 524     @abstractmethod
 525     def __delitem__(self, index):
 526         raise IndexError
 527
 528     @abstractmethod
 529     def insert(self, index, value):
 530         raise IndexError
 531
 532     def append(self, value):
 533         self.insert(len(self), value)
 534
 535     def reverse(self):
 536         n = len(self)
 537         for i in range(n//2):
 538             self[i], self[n-i-1] = self[n-i-1], self[i]
 539
 540     def extend(self, values):
 541         for v in values:
 542             self.append(v)
 543
 544     def pop(self, index=-1):
 545         v = self[index]
 546         del self[index]
 547         return v
 548
 549     def remove(self, value):
 550         del self[self.index(value)]
 551
 552     def __iadd__(self, values):
 553         self.extend(values)
 554
 555 MutableSequence.register(list)