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         """Add an element."""
 253         raise NotImplementedError
 254
 255     @abstractmethod
 256     def discard(self, value):
 257         """Remove an element.  Do not raise an exception if absent."""
 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 = next(it)
 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     def __repr__(self):
 375         return '{0.__class__.__name__}({0._mapping!r})'.format(self)
 376
 377
 378 class KeysView(MappingView, Set):
 379
 380     def __contains__(self, key):
 381         return key in self._mapping
 382
 383     def __iter__(self):
 384         for key in self._mapping:
 385             yield key
 386
 387
 388 class ItemsView(MappingView, Set):
 389
 390     def __contains__(self, item):
 391         key, value = item
 392         try:
 393             v = self._mapping[key]
 394         except KeyError:
 395             return False
 396         else:
 397             return v == value
 398
 399     def __iter__(self):
 400         for key in self._mapping:
 401             yield (key, self._mapping[key])
 402
 403
 404 class ValuesView(MappingView):
 405
 406     def __contains__(self, value):
 407         for key in self._mapping:
 408             if value == self._mapping[key]:
 409                 return True
 410         return False
 411
 412     def __iter__(self):
 413         for key in self._mapping:
 414             yield self._mapping[key]
 415
 416
 417 class MutableMapping(Mapping):
 418
 419     @abstractmethod
 420     def __setitem__(self, key, value):
 421         raise KeyError
 422
 423     @abstractmethod
 424     def __delitem__(self, key):
 425         raise KeyError
 426
 427     __marker = object()
 428
 429     def pop(self, key, default=__marker):
 430         try:
 431             value = self[key]
 432         except KeyError:
 433             if default is self.__marker:
 434                 raise
 435             return default
 436         else:
 437             del self[key]
 438             return value
 439
 440     def popitem(self):
 441         try:
 442             key = next(iter(self))
 443         except StopIteration:
 444             raise KeyError
 445         value = self[key]
 446         del self[key]
 447         return key, value
 448
 449     def clear(self):
 450         try:
 451             while True:
 452                 self.popitem()
 453         except KeyError:
 454             pass
 455
 456     def update(self, other=(), **kwds):
 457         if isinstance(other, Mapping):
 458             for key in other:
 459                 self[key] = other[key]
 460         elif hasattr(other, "keys"):
 461             for key in other.keys():
 462                 self[key] = other[key]
 463         else:
 464             for key, value in other:
 465                 self[key] = value
 466         for key, value in kwds.items():
 467             self[key] = value
 468
 469     def setdefault(self, key, default=None):
 470         try:
 471             return self[key]
 472         except KeyError:
 473             self[key] = default
 474         return default
 475
 476 MutableMapping.register(dict)
 477
 478
 479 ### SEQUENCES ###
 480
 481
 482 class Sequence(Sized, Iterable, Container):
 483     """All the operations on a read-only sequence.
 484
 485     Concrete subclasses must override __new__ or __init__,
 486     __getitem__, and __len__.
 487     """
 488
 489     @abstractmethod
 490     def __getitem__(self, index):
 491         raise IndexError
 492
 493     def __iter__(self):
 494         i = 0
 495         try:
 496             while True:
 497                 v = self[i]
 498                 yield v
 499                 i += 1
 500         except IndexError:
 501             return
 502
 503     def __contains__(self, value):
 504         for v in self:
 505             if v == value:
 506                 return True
 507         return False
 508
 509     def __reversed__(self):
 510         for i in reversed(range(len(self))):
 511             yield self[i]
 512
 513     def index(self, value):
 514         for i, v in enumerate(self):
 515             if v == value:
 516                 return i
 517         raise ValueError
 518
 519     def count(self, value):
 520         return sum(1 for v in self if v == value)
 521
 522 Sequence.register(tuple)
 523 Sequence.register(basestring)
 524 Sequence.register(buffer)
 525 Sequence.register(xrange)
 526
 527
 528 class MutableSequence(Sequence):
 529
 530     @abstractmethod
 531     def __setitem__(self, index, value):
 532         raise IndexError
 533
 534     @abstractmethod
 535     def __delitem__(self, index):
 536         raise IndexError
 537
 538     @abstractmethod
 539     def insert(self, index, value):
 540         raise IndexError
 541
 542     def append(self, value):
 543         self.insert(len(self), value)
 544
 545     def reverse(self):
 546         n = len(self)
 547         for i in range(n//2):
 548             self[i], self[n-i-1] = self[n-i-1], self[i]
 549
 550     def extend(self, values):
 551         for v in values:
 552             self.append(v)
 553
 554     def pop(self, index=-1):
 555         v = self[index]
 556         del self[index]
 557         return v
 558
 559     def remove(self, value):
 560         del self[self.index(value)]
 561
 562     def __iadd__(self, values):
 563         self.extend(values)
 564
 565 MutableSequence.register(list)