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, it):
 290         for value in (self - it):
 291             self.discard(value)
 292         return self
 293
 294     def __ixor__(self, it):
 295         if not isinstance(it, Set):
 296             it = self._from_iterable(it)
 297         for value in it:
 298             if value in self:
 299                 self.discard(value)
 300             else:
 301                 self.add(value)
 302         return self
 303
 304     def __isub__(self, it):
 305         for value in it:
 306             self.discard(value)
 307         return self
 308
 309 MutableSet.register(set)
 310
 311
 312 ### MAPPINGS ###
 313
 314
 315 class Mapping(Sized, Iterable, Container):
 316
 317     @abstractmethod
 318     def __getitem__(self, key):
 319         raise KeyError
 320
 321     def get(self, key, default=None):
 322         try:
 323             return self[key]
 324         except KeyError:
 325             return default
 326
 327     def __contains__(self, key):
 328         try:
 329             self[key]
 330         except KeyError:
 331             return False
 332         else:
 333             return True
 334
 335     def iterkeys(self):
 336         return iter(self)
 337
 338     def itervalues(self):
 339         for key in self:
 340             yield self[key]
 341
 342     def iteritems(self):
 343         for key in self:
 344             yield (key, self[key])
 345
 346     def keys(self):
 347         return list(self)
 348
 349     def items(self):
 350         return [(key, self[key]) for key in self]
 351
 352     def values(self):
 353         return [self[key] for key in self]
 354
 355     # Mappings are not hashable by default, but subclasses can change this
 356     __hash__ = None
 357
 358     def __eq__(self, other):
 359         return isinstance(other, Mapping) and \
 360                dict(self.items()) == dict(other.items())
 361
 362     def __ne__(self, other):
 363         return not (self == other)
 364
 365 class MappingView(Sized):
 366
 367     def __init__(self, mapping):
 368         self._mapping = mapping
 369
 370     def __len__(self):
 371         return len(self._mapping)
 372
 373     def __repr__(self):
 374         return '{0.__class__.__name__}({0._mapping!r})'.format(self)
 375
 376
 377 class KeysView(MappingView, Set):
 378
 379     def __contains__(self, key):
 380         return key in self._mapping
 381
 382     def __iter__(self):
 383         for key in self._mapping:
 384             yield key
 385
 386
 387 class ItemsView(MappingView, Set):
 388
 389     def __contains__(self, item):
 390         key, value = item
 391         try:
 392             v = self._mapping[key]
 393         except KeyError:
 394             return False
 395         else:
 396             return v == value
 397
 398     def __iter__(self):
 399         for key in self._mapping:
 400             yield (key, self._mapping[key])
 401
 402
 403 class ValuesView(MappingView):
 404
 405     def __contains__(self, value):
 406         for key in self._mapping:
 407             if value == self._mapping[key]:
 408                 return True
 409         return False
 410
 411     def __iter__(self):
 412         for key in self._mapping:
 413             yield self._mapping[key]
 414
 415
 416 class MutableMapping(Mapping):
 417
 418     @abstractmethod
 419     def __setitem__(self, key, value):
 420         raise KeyError
 421
 422     @abstractmethod
 423     def __delitem__(self, key):
 424         raise KeyError
 425
 426     __marker = object()
 427
 428     def pop(self, key, default=__marker):
 429         try:
 430             value = self[key]
 431         except KeyError:
 432             if default is self.__marker:
 433                 raise
 434             return default
 435         else:
 436             del self[key]
 437             return value
 438
 439     def popitem(self):
 440         try:
 441             key = next(iter(self))
 442         except StopIteration:
 443             raise KeyError
 444         value = self[key]
 445         del self[key]
 446         return key, value
 447
 448     def clear(self):
 449         try:
 450             while True:
 451                 self.popitem()
 452         except KeyError:
 453             pass
 454
 455     def update(self, other=(), **kwds):
 456         if isinstance(other, Mapping):
 457             for key in other:
 458                 self[key] = other[key]
 459         elif hasattr(other, "keys"):
 460             for key in other.keys():
 461                 self[key] = other[key]
 462         else:
 463             for key, value in other:
 464                 self[key] = value
 465         for key, value in kwds.items():
 466             self[key] = value
 467
 468     def setdefault(self, key, default=None):
 469         try:
 470             return self[key]
 471         except KeyError:
 472             self[key] = default
 473         return default
 474
 475 MutableMapping.register(dict)
 476
 477
 478 ### SEQUENCES ###
 479
 480
 481 class Sequence(Sized, Iterable, Container):
 482     """All the operations on a read-only sequence.
 483
 484     Concrete subclasses must override __new__ or __init__,
 485     __getitem__, and __len__.
 486     """
 487
 488     @abstractmethod
 489     def __getitem__(self, index):
 490         raise IndexError
 491
 492     def __iter__(self):
 493         i = 0
 494         try:
 495             while True:
 496                 v = self[i]
 497                 yield v
 498                 i += 1
 499         except IndexError:
 500             return
 501
 502     def __contains__(self, value):
 503         for v in self:
 504             if v == value:
 505                 return True
 506         return False
 507
 508     def __reversed__(self):
 509         for i in reversed(range(len(self))):
 510             yield self[i]
 511
 512     def index(self, value):
 513         for i, v in enumerate(self):
 514             if v == value:
 515                 return i
 516         raise ValueError
 517
 518     def count(self, value):
 519         return sum(1 for v in self if v == value)
 520
 521 Sequence.register(tuple)
 522 Sequence.register(basestring)
 523 Sequence.register(buffer)
 524 Sequence.register(xrange)
 525
 526
 527 class MutableSequence(Sequence):
 528
 529     @abstractmethod
 530     def __setitem__(self, index, value):
 531         raise IndexError
 532
 533     @abstractmethod
 534     def __delitem__(self, index):
 535         raise IndexError
 536
 537     @abstractmethod
 538     def insert(self, index, value):
 539         raise IndexError
 540
 541     def append(self, value):
 542         self.insert(len(self), value)
 543
 544     def reverse(self):
 545         n = len(self)
 546         for i in range(n//2):
 547             self[i], self[n-i-1] = self[n-i-1], self[i]
 548
 549     def extend(self, values):
 550         for v in values:
 551             self.append(v)
 552
 553     def pop(self, index=-1):
 554         v = self[index]
 555         del self[index]
 556         return v
 557
 558     def remove(self, value):
 559         del self[self.index(value)]
 560
 561     def __iadd__(self, values):
 562         self.extend(values)
 563         return self
 564
 565 MutableSequence.register(list)