_abcoll.py revision e973c61238807dcf4ccedc18a99db8f478c422c7
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 clear(self): 27064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum """This is slow (creates N new iterators!) but effective.""" 27164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum try: 27264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum while True: 27364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum self.pop() 27464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum except KeyError: 27564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum pass 27664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 27764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __ior__(self, it): 27864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum for value in it: 27964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum self.add(value) 28064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return self 28164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 28264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __iand__(self, c): 28364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum for value in self: 28464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum if value not in c: 28564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum self.discard(value) 28664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return self 28764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 28864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __ixor__(self, it): 289e67420d72e26d976af2c8cd8603f2dfe158b6d24Raymond Hettinger if not isinstance(it, Set): 290e67420d72e26d976af2c8cd8603f2dfe158b6d24Raymond Hettinger it = self._from_iterable(it) 29164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum for value in it: 292e67420d72e26d976af2c8cd8603f2dfe158b6d24Raymond Hettinger if value in self: 293e67420d72e26d976af2c8cd8603f2dfe158b6d24Raymond Hettinger self.discard(value) 294e67420d72e26d976af2c8cd8603f2dfe158b6d24Raymond Hettinger else: 295e67420d72e26d976af2c8cd8603f2dfe158b6d24Raymond Hettinger self.add(value) 296e973c61238807dcf4ccedc18a99db8f478c422c7Raymond Hettinger return self 29764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 29864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __isub__(self, it): 29964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum for value in it: 30064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum self.discard(value) 30164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return self 30264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 30364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van RossumMutableSet.register(set) 30464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 30564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 30664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum### MAPPINGS ### 30764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 30864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 30964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossumclass Mapping: 31064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum __metaclass__ = ABCMeta 31164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 31264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum @abstractmethod 31364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __getitem__(self, key): 31464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum raise KeyError 31564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 31664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def get(self, key, default=None): 31764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum try: 31864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return self[key] 31964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum except KeyError: 32064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return default 32164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 32264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __contains__(self, key): 32364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum try: 32464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum self[key] 32564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum except KeyError: 32664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return False 32764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum else: 32864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return True 32964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 33064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum @abstractmethod 33164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __len__(self): 33264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return 0 33364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 33464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum @abstractmethod 33564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __iter__(self): 33664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum while False: 33764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum yield None 33864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 33964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def keys(self): 34064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return KeysView(self) 34164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 34264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def items(self): 34364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return ItemsView(self) 34464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 34564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def values(self): 34664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return ValuesView(self) 34764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 34864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 34964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossumclass MappingView: 35064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum __metaclass__ = ABCMeta 35164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 35264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __init__(self, mapping): 35364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum self._mapping = mapping 35464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 35564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __len__(self): 35664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return len(self._mapping) 35764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 35864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 35964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossumclass KeysView(MappingView, Set): 36064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 36164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __contains__(self, key): 36264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return key in self._mapping 36364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 36464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __iter__(self): 36564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum for key in self._mapping: 36664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum yield key 36764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 36864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van RossumKeysView.register(type({}.keys())) 36964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 37064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 37164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossumclass ItemsView(MappingView, Set): 37264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 37364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __contains__(self, item): 37464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum key, value = item 37564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum try: 37664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum v = self._mapping[key] 37764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum except KeyError: 37864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return False 37964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum else: 38064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return v == value 38164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 38264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __iter__(self): 38364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum for key in self._mapping: 38464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum yield (key, self._mapping[key]) 38564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 38664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van RossumItemsView.register(type({}.items())) 38764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 38864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 38964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossumclass ValuesView(MappingView): 39064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 39164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __contains__(self, value): 39264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum for key in self._mapping: 39364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum if value == self._mapping[key]: 39464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return True 39564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return False 39664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 39764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __iter__(self): 39864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum for key in self._mapping: 39964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum yield self._mapping[key] 40064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 40164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van RossumValuesView.register(type({}.values())) 40264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 40364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 40464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossumclass MutableMapping(Mapping): 40564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 40664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum @abstractmethod 40764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __setitem__(self, key, value): 40864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum raise KeyError 40964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 41064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum @abstractmethod 41164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __delitem__(self, key): 41264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum raise KeyError 41364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 41464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum __marker = object() 41564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 41664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def pop(self, key, default=__marker): 41764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum try: 41864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum value = self[key] 41964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum except KeyError: 42064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum if default is self.__marker: 42164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum raise 42264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return default 42364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum else: 42464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum del self[key] 42564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return value 42664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 42764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def popitem(self): 42864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum try: 42964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum key = next(iter(self)) 43064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum except StopIteration: 43164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum raise KeyError 43264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum value = self[key] 43364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum del self[key] 43464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return key, value 43564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 43664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def clear(self): 43764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum try: 43864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum while True: 43964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum self.popitem() 44064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum except KeyError: 44164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum pass 44264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 44364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def update(self, other=(), **kwds): 44464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum if isinstance(other, Mapping): 44564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum for key in other: 44664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum self[key] = other[key] 44764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum elif hasattr(other, "keys"): 44864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum for key in other.keys(): 44964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum self[key] = other[key] 45064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum else: 45164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum for key, value in other: 45264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum self[key] = value 45364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum for key, value in kwds.items(): 45464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum self[key] = value 45564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 45664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van RossumMutableMapping.register(dict) 45764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 45864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 45964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum### SEQUENCES ### 46064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 46164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 46264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossumclass Sequence: 46364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum __metaclass__ = ABCMeta 46464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 46564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum """All the operations on a read-only sequence. 46664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 46764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum Concrete subclasses must override __new__ or __init__, 46864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum __getitem__, and __len__. 46964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum """ 47064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 47164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum @abstractmethod 47264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __getitem__(self, index): 47364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum raise IndexError 47464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 47564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum @abstractmethod 47664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __len__(self): 47764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return 0 47864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 47964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __iter__(self): 48064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum i = 0 48164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum while True: 48264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum try: 48364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum v = self[i] 48464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum except IndexError: 48564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum break 48664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum yield v 48764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum i += 1 48864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 48964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __contains__(self, value): 49064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum for v in self: 49164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum if v == value: 49264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return True 49364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return False 49464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 49564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __reversed__(self): 49664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum for i in reversed(range(len(self))): 49764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum yield self[i] 49864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 49964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def index(self, value): 50064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum for i, v in enumerate(self): 50164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum if v == value: 50264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return i 50364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum raise ValueError 50464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 50564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def count(self, value): 50664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return sum(1 for v in self if v == value) 50764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 50864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van RossumSequence.register(tuple) 50964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van RossumSequence.register(basestring) 51064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van RossumSequence.register(buffer) 51164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 51264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 51364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossumclass MutableSequence(Sequence): 51464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 51564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum @abstractmethod 51664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __setitem__(self, index, value): 51764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum raise IndexError 51864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 51964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum @abstractmethod 52064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __delitem__(self, index): 52164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum raise IndexError 52264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 52364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum @abstractmethod 52464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def insert(self, index, value): 52564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum raise IndexError 52664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 52764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def append(self, value): 52864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum self.insert(len(self), value) 52964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 53064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def reverse(self): 53164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum n = len(self) 53264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum for i in range(n//2): 53364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum self[i], self[n-i-1] = self[n-i-1], self[i] 53464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 53564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def extend(self, values): 53664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum for v in values: 53764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum self.append(v) 53864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 53964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def pop(self, index=-1): 54064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum v = self[index] 54164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum del self[index] 54264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return v 54364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 54464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def remove(self, value): 54564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum del self[self.index(value)] 54664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 54764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __iadd__(self, values): 54864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum self.extend(values) 54964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 55064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van RossumMutableSequence.register(list) 551