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