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