_abcoll.py revision 7d518f418b8bb7f155c8e695adbc5b69ac0ed0fd
164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum# Copyright 2007 Google, Inc. All Rights Reserved. 264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum# Licensed to PSF under a Contributor Agreement. 364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum"""Abstract Base Classes (ABCs) for collections, according to PEP 3119. 564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van RossumDON'T USE THIS MODULE DIRECTLY! The classes here should be imported 764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossumvia collections; they are defined here only to alleviate certain 864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossumbootstrapping issues. Unit tests are in test_collections. 964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum""" 1064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 1164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossumfrom abc import ABCMeta, abstractmethod 1264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 1364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum__all__ = ["Hashable", "Iterable", "Iterator", 1464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum "Sized", "Container", "Callable", 1564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum "Set", "MutableSet", 1664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum "Mapping", "MutableMapping", 1764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum "MappingView", "KeysView", "ItemsView", "ValuesView", 1864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum "Sequence", "MutableSequence", 1964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum ] 2064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 2164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum### ONE-TRICK PONIES ### 2264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 2364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossumclass Hashable: 2464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum __metaclass__ = ABCMeta 2564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 2664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum @abstractmethod 2764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __hash__(self): 2864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return 0 2964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 3064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum @classmethod 3164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __subclasshook__(cls, C): 3264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum if cls is Hashable: 3364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum for B in C.__mro__: 3464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum if "__hash__" in B.__dict__: 3564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum if B.__dict__["__hash__"]: 3664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return True 3764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum break 3864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return NotImplemented 3964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 4064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 4164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossumclass Iterable: 4264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum __metaclass__ = ABCMeta 4364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 4464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum @abstractmethod 4564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __iter__(self): 4664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum while False: 4764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum yield None 4864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 4964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum @classmethod 5064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __subclasshook__(cls, C): 5164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum if cls is Iterable: 5264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum if any("__iter__" in B.__dict__ for B in C.__mro__): 5364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return True 5464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return NotImplemented 5564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 5664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van RossumIterable.register(str) 5764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 5864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 5964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossumclass Iterator: 6064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum __metaclass__ = ABCMeta 6164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 6264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum @abstractmethod 6364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __next__(self): 6464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum raise StopIteration 6564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 6664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __iter__(self): 6764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return self 6864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 6964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum @classmethod 7064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __subclasshook__(cls, C): 7164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum if cls is Iterator: 7264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum if any("next" in B.__dict__ for B in C.__mro__): 7364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return True 7464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return NotImplemented 7564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 7664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 7764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossumclass Sized: 7864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum __metaclass__ = ABCMeta 7964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 8064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum @abstractmethod 8164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __len__(self): 8264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return 0 8364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 8464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum @classmethod 8564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __subclasshook__(cls, C): 8664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum if cls is Sized: 8764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum if any("__len__" in B.__dict__ for B in C.__mro__): 8864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return True 8964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return NotImplemented 9064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 9164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 9264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossumclass Container: 9364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum __metaclass__ = ABCMeta 9464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 9564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum @abstractmethod 9664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __contains__(self, x): 9764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return False 9864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 9964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum @classmethod 10064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __subclasshook__(cls, C): 10164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum if cls is Container: 10264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum if any("__contains__" in B.__dict__ for B in C.__mro__): 10364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return True 10464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return NotImplemented 10564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 10664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 10764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossumclass Callable: 10864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum __metaclass__ = ABCMeta 10964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 11064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum @abstractmethod 11164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __contains__(self, x): 11264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return False 11364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 11464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum @classmethod 11564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __subclasshook__(cls, C): 11664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum if cls is Callable: 11764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum if any("__call__" in B.__dict__ for B in C.__mro__): 11864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return True 11964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return NotImplemented 12064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 12164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 12264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum### SETS ### 12364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 12464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 12564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossumclass Set: 12664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum __metaclass__ = ABCMeta 12764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 12864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum """A set is a finite, iterable container. 12964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 13064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum This class provides concrete generic implementations of all 13164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum methods except for __contains__, __iter__ and __len__. 13264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 13364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum To override the comparisons (presumably for speed, as the 13464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum semantics are fixed), all you have to do is redefine __le__ and 13564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum then the other operations will automatically follow suit. 13664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum """ 13764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 13864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum @abstractmethod 13964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __contains__(self, value): 14064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return False 14164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 14264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum @abstractmethod 14364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __iter__(self): 14464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum while False: 14564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum yield None 14664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 14764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum @abstractmethod 14864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __len__(self): 14964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return 0 15064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 15164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __le__(self, other): 15264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum if not isinstance(other, Set): 15364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return NotImplemented 15464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum if len(self) > len(other): 15564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return False 15664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum for elem in self: 15764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum if elem not in other: 15864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return False 15964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return True 16064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 16164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __lt__(self, other): 16264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum if not isinstance(other, Set): 16364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return NotImplemented 16464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return len(self) < len(other) and self.__le__(other) 16564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 16664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __eq__(self, other): 16764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum if not isinstance(other, Set): 16864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return NotImplemented 16964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return len(self) == len(other) and self.__le__(other) 17064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 17164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum @classmethod 17264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def _from_iterable(cls, it): 17364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return frozenset(it) 17464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 17564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __and__(self, other): 17664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum if not isinstance(other, Iterable): 17764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return NotImplemented 17864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return self._from_iterable(value for value in other if value in self) 17964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 180abf3fcf39fb3bff4d347296a083a4c62d515dacdRaymond Hettinger def isdisjoint(self, other): 181abf3fcf39fb3bff4d347296a083a4c62d515dacdRaymond Hettinger for value in other: 182abf3fcf39fb3bff4d347296a083a4c62d515dacdRaymond Hettinger if value in self: 183abf3fcf39fb3bff4d347296a083a4c62d515dacdRaymond Hettinger return False 184abf3fcf39fb3bff4d347296a083a4c62d515dacdRaymond Hettinger return True 185abf3fcf39fb3bff4d347296a083a4c62d515dacdRaymond Hettinger 18664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __or__(self, other): 18764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum if not isinstance(other, Iterable): 18864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return NotImplemented 18964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return self._from_iterable(itertools.chain(self, other)) 19064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 19164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __sub__(self, other): 19264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum if not isinstance(other, Set): 19364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum if not isinstance(other, Iterable): 19464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return NotImplemented 19564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum other = self._from_iterable(other) 19664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return self._from_iterable(value for value in self 19764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum if value not in other) 19864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 19964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __xor__(self, other): 20064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum if not isinstance(other, Set): 20164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum if not isinstance(other, Iterable): 20264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return NotImplemented 20364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum other = self._from_iterable(other) 20464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return (self - other) | (other - self) 20564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 20664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def _hash(self): 20764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum """Compute the hash value of a set. 20864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 20964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum Note that we don't define __hash__: not all sets are hashable. 21064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum But if you define a hashable set type, its __hash__ should 21164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum call this function. 21264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 21364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum This must be compatible __eq__. 21464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 21564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum All sets ought to compare equal if they contain the same 21664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum elements, regardless of how they are implemented, and 21764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum regardless of the order of the elements; so there's not much 21864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum freedom for __eq__ or __hash__. We match the algorithm used 21964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum by the built-in frozenset type. 22064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum """ 22164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum MAX = sys.maxint 22264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum MASK = 2 * MAX + 1 22364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum n = len(self) 22464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum h = 1927868237 * (n + 1) 22564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum h &= MASK 22664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum for x in self: 22764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum hx = hash(x) 22864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum h ^= (hx ^ (hx << 16) ^ 89869747) * 3644798167 22964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum h &= MASK 23064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum h = h * 69069 + 907133923 23164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum h &= MASK 23264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum if h > MAX: 23364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum h -= MASK + 1 23464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum if h == -1: 23564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum h = 590923713 23664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return h 23764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 23864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van RossumSet.register(frozenset) 23964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 24064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 24164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossumclass MutableSet(Set): 24264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 24364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum @abstractmethod 24464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def add(self, value): 24564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum """Return True if it was added, False if already there.""" 24664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum raise NotImplementedError 24764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 24864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum @abstractmethod 24964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def discard(self, value): 25064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum """Return True if it was deleted, False if not there.""" 25164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum raise NotImplementedError 25264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 2537d518f418b8bb7f155c8e695adbc5b69ac0ed0fdRaymond Hettinger def remove(self, value): 2547d518f418b8bb7f155c8e695adbc5b69ac0ed0fdRaymond Hettinger """Remove an element. If not a member, raise a KeyError.""" 2557d518f418b8bb7f155c8e695adbc5b69ac0ed0fdRaymond Hettinger if value not in self: 2567d518f418b8bb7f155c8e695adbc5b69ac0ed0fdRaymond Hettinger raise KeyError(value) 2577d518f418b8bb7f155c8e695adbc5b69ac0ed0fdRaymond Hettinger self.discard(value) 2587d518f418b8bb7f155c8e695adbc5b69ac0ed0fdRaymond Hettinger 25964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def pop(self): 26064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum """Return the popped value. Raise KeyError if empty.""" 26164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum it = iter(self) 26264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum try: 26364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum value = it.__next__() 26464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum except StopIteration: 26564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum raise KeyError 26664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum self.discard(value) 26764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return value 26864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 26964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def toggle(self, value): 27064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum """Return True if it was added, False if deleted.""" 27164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum # XXX This implementation is not thread-safe 27264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum if value in self: 27364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum self.discard(value) 27464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return False 27564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum else: 27664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum self.add(value) 27764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return True 27864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 27964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def clear(self): 28064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum """This is slow (creates N new iterators!) but effective.""" 28164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum try: 28264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum while True: 28364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum self.pop() 28464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum except KeyError: 28564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum pass 28664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 28764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __ior__(self, it): 28864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum for value in it: 28964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum self.add(value) 29064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return self 29164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 29264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __iand__(self, c): 29364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum for value in self: 29464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum if value not in c: 29564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum self.discard(value) 29664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return self 29764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 29864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __ixor__(self, it): 29964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum # This calls toggle(), so if that is overridded, we call the override 30064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum for value in it: 30164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum self.toggle(it) 30264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return self 30364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 30464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __isub__(self, it): 30564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum for value in it: 30664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum self.discard(value) 30764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return self 30864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 30964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van RossumMutableSet.register(set) 31064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 31164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 31264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum### MAPPINGS ### 31364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 31464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 31564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossumclass Mapping: 31664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum __metaclass__ = ABCMeta 31764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 31864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum @abstractmethod 31964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __getitem__(self, key): 32064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum raise KeyError 32164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 32264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def get(self, key, default=None): 32364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum try: 32464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return self[key] 32564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum except KeyError: 32664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return default 32764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 32864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __contains__(self, key): 32964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum try: 33064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum self[key] 33164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum except KeyError: 33264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return False 33364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum else: 33464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return True 33564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 33664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum @abstractmethod 33764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __len__(self): 33864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return 0 33964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 34064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum @abstractmethod 34164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __iter__(self): 34264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum while False: 34364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum yield None 34464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 34564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def keys(self): 34664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return KeysView(self) 34764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 34864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def items(self): 34964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return ItemsView(self) 35064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 35164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def values(self): 35264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return ValuesView(self) 35364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 35464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 35564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossumclass MappingView: 35664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum __metaclass__ = ABCMeta 35764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 35864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __init__(self, mapping): 35964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum self._mapping = mapping 36064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 36164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __len__(self): 36264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return len(self._mapping) 36364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 36464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 36564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossumclass KeysView(MappingView, Set): 36664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 36764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __contains__(self, key): 36864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return key in self._mapping 36964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 37064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __iter__(self): 37164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum for key in self._mapping: 37264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum yield key 37364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 37464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van RossumKeysView.register(type({}.keys())) 37564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 37664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 37764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossumclass ItemsView(MappingView, Set): 37864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 37964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __contains__(self, item): 38064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum key, value = item 38164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum try: 38264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum v = self._mapping[key] 38364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum except KeyError: 38464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return False 38564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum else: 38664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return v == value 38764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 38864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __iter__(self): 38964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum for key in self._mapping: 39064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum yield (key, self._mapping[key]) 39164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 39264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van RossumItemsView.register(type({}.items())) 39364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 39464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 39564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossumclass ValuesView(MappingView): 39664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 39764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __contains__(self, value): 39864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum for key in self._mapping: 39964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum if value == self._mapping[key]: 40064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return True 40164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return False 40264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 40364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __iter__(self): 40464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum for key in self._mapping: 40564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum yield self._mapping[key] 40664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 40764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van RossumValuesView.register(type({}.values())) 40864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 40964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 41064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossumclass MutableMapping(Mapping): 41164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 41264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum @abstractmethod 41364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __setitem__(self, key, value): 41464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum raise KeyError 41564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 41664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum @abstractmethod 41764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __delitem__(self, key): 41864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum raise KeyError 41964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 42064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum __marker = object() 42164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 42264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def pop(self, key, default=__marker): 42364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum try: 42464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum value = self[key] 42564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum except KeyError: 42664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum if default is self.__marker: 42764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum raise 42864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return default 42964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum else: 43064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum del self[key] 43164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return value 43264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 43364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def popitem(self): 43464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum try: 43564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum key = next(iter(self)) 43664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum except StopIteration: 43764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum raise KeyError 43864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum value = self[key] 43964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum del self[key] 44064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return key, value 44164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 44264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def clear(self): 44364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum try: 44464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum while True: 44564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum self.popitem() 44664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum except KeyError: 44764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum pass 44864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 44964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def update(self, other=(), **kwds): 45064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum if isinstance(other, Mapping): 45164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum for key in other: 45264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum self[key] = other[key] 45364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum elif hasattr(other, "keys"): 45464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum for key in other.keys(): 45564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum self[key] = other[key] 45664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum else: 45764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum for key, value in other: 45864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum self[key] = value 45964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum for key, value in kwds.items(): 46064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum self[key] = value 46164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 46264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van RossumMutableMapping.register(dict) 46364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 46464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 46564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum### SEQUENCES ### 46664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 46764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 46864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossumclass Sequence: 46964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum __metaclass__ = ABCMeta 47064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 47164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum """All the operations on a read-only sequence. 47264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 47364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum Concrete subclasses must override __new__ or __init__, 47464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum __getitem__, and __len__. 47564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum """ 47664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 47764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum @abstractmethod 47864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __getitem__(self, index): 47964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum raise IndexError 48064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 48164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum @abstractmethod 48264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __len__(self): 48364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return 0 48464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 48564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __iter__(self): 48664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum i = 0 48764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum while True: 48864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum try: 48964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum v = self[i] 49064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum except IndexError: 49164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum break 49264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum yield v 49364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum i += 1 49464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 49564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __contains__(self, value): 49664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum for v in self: 49764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum if v == value: 49864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return True 49964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return False 50064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 50164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __reversed__(self): 50264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum for i in reversed(range(len(self))): 50364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum yield self[i] 50464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 50564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def index(self, value): 50664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum for i, v in enumerate(self): 50764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum if v == value: 50864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return i 50964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum raise ValueError 51064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 51164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def count(self, value): 51264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return sum(1 for v in self if v == value) 51364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 51464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van RossumSequence.register(tuple) 51564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van RossumSequence.register(basestring) 51664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van RossumSequence.register(buffer) 51764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 51864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 51964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossumclass MutableSequence(Sequence): 52064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 52164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum @abstractmethod 52264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __setitem__(self, index, value): 52364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum raise IndexError 52464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 52564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum @abstractmethod 52664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __delitem__(self, index): 52764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum raise IndexError 52864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 52964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum @abstractmethod 53064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def insert(self, index, value): 53164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum raise IndexError 53264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 53364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def append(self, value): 53464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum self.insert(len(self), value) 53564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 53664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def reverse(self): 53764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum n = len(self) 53864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum for i in range(n//2): 53964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum self[i], self[n-i-1] = self[n-i-1], self[i] 54064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 54164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def extend(self, values): 54264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum for v in values: 54364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum self.append(v) 54464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 54564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def pop(self, index=-1): 54664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum v = self[index] 54764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum del self[index] 54864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return v 54964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 55064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def remove(self, value): 55164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum del self[self.index(value)] 55264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 55364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __iadd__(self, values): 55464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum self.extend(values) 55564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 55664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van RossumMutableSequence.register(list) 557