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         if not isinstance(other, Mapping):
 380             return NotImplemented
 381         return dict(self.items()) == dict(other.items())
 382
 383     def __ne__(self, other):
 384         return not (self == other)
 385
 386
 387 class MappingView(Sized):
 388
 389     def __init__(self, mapping):
 390         self._mapping = mapping
 391
 392     def __len__(self):
 393         return len(self._mapping)
 394
 395     def __repr__(self):
 396         return '{0.__class__.__name__}({0._mapping!r})'.format(self)
 397
 398
 399 class KeysView(MappingView, Set):
 400
 401     def __contains__(self, key):
 402         return key in self._mapping
 403
 404     def __iter__(self):
 405         for key in self._mapping:
 406             yield key
 407
 408 KeysView.register(dict_keys)
 409
 410
 411 class ItemsView(MappingView, Set):
 412
 413     def __contains__(self, item):
 414         key, value = item
 415         try:
 416             v = self._mapping[key]
 417         except KeyError:
 418             return False
 419         else:
 420             return v == value
 421
 422     def __iter__(self):
 423         for key in self._mapping:
 424             yield (key, self._mapping[key])
 425
 426 ItemsView.register(dict_items)
 427
 428
 429 class ValuesView(MappingView):
 430
 431     def __contains__(self, value):
 432         for key in self._mapping:
 433             if value == self._mapping[key]:
 434                 return True
 435         return False
 436
 437     def __iter__(self):
 438         for key in self._mapping:
 439             yield self._mapping[key]
 440
 441 ValuesView.register(dict_values)
 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
 519     """All the operations on a read-only sequence.
 520
 521     Concrete subclasses must override __new__ or __init__,
 522     __getitem__, and __len__.
 523     """
 524
 525     @abstractmethod
 526     def __getitem__(self, index):
 527         raise IndexError
 528
 529     def __iter__(self):
 530         i = 0
 531         try:
 532             while True:
 533                 v = self[i]
 534                 yield v
 535                 i += 1
 536         except IndexError:
 537             return
 538
 539     def __contains__(self, value):
 540         for v in self:
 541             if v == value:
 542                 return True
 543         return False
 544
 545     def __reversed__(self):
 546         for i in reversed(range(len(self))):
 547             yield self[i]
 548
 549     def index(self, value):
 550         for i, v in enumerate(self):
 551             if v == value:
 552                 return i
 553         raise ValueError
 554
 555     def count(self, value):
 556         return sum(1 for v in self if v == value)
 557
 558 Sequence.register(tuple)
 559 Sequence.register(str)
 560 Sequence.register(range)
 561
 562
 563 class ByteString(Sequence):
 564
 565     """This unifies bytes and bytearray.
 566
 567     XXX Should add all their methods.
 568     """
 569
 570 ByteString.register(bytes)
 571 ByteString.register(bytearray)
 572
 573
 574 class MutableSequence(Sequence):
 575
 576     @abstractmethod
 577     def __setitem__(self, index, value):
 578         raise IndexError
 579
 580     @abstractmethod
 581     def __delitem__(self, index):
 582         raise IndexError
 583
 584     @abstractmethod
 585     def insert(self, index, value):
 586         raise IndexError
 587
 588     def append(self, value):
 589         self.insert(len(self), value)
 590
 591     def reverse(self):
 592         n = len(self)
 593         for i in range(n//2):
 594             self[i], self[n-i-1] = self[n-i-1], self[i]
 595
 596     def extend(self, values):
 597         for v in values:
 598             self.append(v)
 599
 600     def pop(self, index=-1):
 601         v = self[index]
 602         del self[index]
 603         return v
 604
 605     def remove(self, value):
 606         del self[self.index(value)]
 607
 608     def __iadd__(self, values):
 609         self.extend(values)
 610         return self
 611
 612 MutableSequence.register(list)
 613 MutableSequence.register(bytearray)  # Multiply inheriting, see ByteString