_abcoll.py revision 2e827bfdfea7b940517f90af78c986aec9159d2c
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 59c2bc0d17e83ad88b829a669cc9ee7194b9e46593Raymond Hettingerclass Iterator(Iterable): 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 125c2bc0d17e83ad88b829a669cc9ee7194b9e46593Raymond Hettingerclass Set(Sized, Iterable, Container): 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 def __le__(self, other): 13964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum if not isinstance(other, Set): 14064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return NotImplemented 14164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum if len(self) > len(other): 14264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return False 14364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum for elem in self: 14464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum if elem not in other: 14564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return False 14664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return True 14764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 14864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __lt__(self, other): 14964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum if not isinstance(other, Set): 15064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return NotImplemented 15164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return len(self) < len(other) and self.__le__(other) 15264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 153d53f1c4d41e863c8a7f0653ea7af04dc0b4faa84Raymond Hettinger def __gt__(self, other): 154d53f1c4d41e863c8a7f0653ea7af04dc0b4faa84Raymond Hettinger if not isinstance(other, Set): 155d53f1c4d41e863c8a7f0653ea7af04dc0b4faa84Raymond Hettinger return NotImplemented 156d53f1c4d41e863c8a7f0653ea7af04dc0b4faa84Raymond Hettinger return other < self 157d53f1c4d41e863c8a7f0653ea7af04dc0b4faa84Raymond Hettinger 158d53f1c4d41e863c8a7f0653ea7af04dc0b4faa84Raymond Hettinger def __ge__(self, other): 159d53f1c4d41e863c8a7f0653ea7af04dc0b4faa84Raymond Hettinger if not isinstance(other, Set): 160d53f1c4d41e863c8a7f0653ea7af04dc0b4faa84Raymond Hettinger return NotImplemented 161d53f1c4d41e863c8a7f0653ea7af04dc0b4faa84Raymond Hettinger return other <= self 162d53f1c4d41e863c8a7f0653ea7af04dc0b4faa84Raymond Hettinger 16364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __eq__(self, other): 16464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum if not isinstance(other, Set): 16564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return NotImplemented 16664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return len(self) == len(other) and self.__le__(other) 16764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 168d53f1c4d41e863c8a7f0653ea7af04dc0b4faa84Raymond Hettinger def __ne__(self, other): 169d53f1c4d41e863c8a7f0653ea7af04dc0b4faa84Raymond Hettinger return not (self == other) 170d53f1c4d41e863c8a7f0653ea7af04dc0b4faa84Raymond Hettinger 17164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum @classmethod 17264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def _from_iterable(cls, it): 173017b6a3ad2be5c0e3309fb016234397211d6ffa7Raymond Hettinger '''Construct an instance of the class from any iterable input. 174017b6a3ad2be5c0e3309fb016234397211d6ffa7Raymond Hettinger 175017b6a3ad2be5c0e3309fb016234397211d6ffa7Raymond Hettinger Must override this method if the class constructor signature 1762e827bfdfea7b940517f90af78c986aec9159d2cRaymond Hettinger does not accept an iterable for an input. 177017b6a3ad2be5c0e3309fb016234397211d6ffa7Raymond Hettinger ''' 1782e827bfdfea7b940517f90af78c986aec9159d2cRaymond Hettinger return cls(it) 17964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 18064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __and__(self, other): 18164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum if not isinstance(other, Iterable): 18264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return NotImplemented 18364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return self._from_iterable(value for value in other if value in self) 18464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 185abf3fcf39fb3bff4d347296a083a4c62d515dacdRaymond Hettinger def isdisjoint(self, other): 186abf3fcf39fb3bff4d347296a083a4c62d515dacdRaymond Hettinger for value in other: 187abf3fcf39fb3bff4d347296a083a4c62d515dacdRaymond Hettinger if value in self: 188abf3fcf39fb3bff4d347296a083a4c62d515dacdRaymond Hettinger return False 189abf3fcf39fb3bff4d347296a083a4c62d515dacdRaymond Hettinger return True 190abf3fcf39fb3bff4d347296a083a4c62d515dacdRaymond Hettinger 19164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __or__(self, other): 19264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum if not isinstance(other, Iterable): 19364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return NotImplemented 19464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return self._from_iterable(itertools.chain(self, other)) 19564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 19664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __sub__(self, other): 19764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum if not isinstance(other, Set): 19864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum if not isinstance(other, Iterable): 19964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return NotImplemented 20064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum other = self._from_iterable(other) 20164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return self._from_iterable(value for value in self 20264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum if value not in other) 20364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 20464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __xor__(self, other): 20564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum if not isinstance(other, Set): 20664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum if not isinstance(other, Iterable): 20764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return NotImplemented 20864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum other = self._from_iterable(other) 20964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return (self - other) | (other - self) 21064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 21164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def _hash(self): 21264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum """Compute the hash value of a set. 21364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 21464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum Note that we don't define __hash__: not all sets are hashable. 21564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum But if you define a hashable set type, its __hash__ should 21664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum call this function. 21764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 21864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum This must be compatible __eq__. 21964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 22064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum All sets ought to compare equal if they contain the same 22164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum elements, regardless of how they are implemented, and 22264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum regardless of the order of the elements; so there's not much 22364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum freedom for __eq__ or __hash__. We match the algorithm used 22464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum by the built-in frozenset type. 22564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum """ 22664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum MAX = sys.maxint 22764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum MASK = 2 * MAX + 1 22864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum n = len(self) 22964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum h = 1927868237 * (n + 1) 23064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum h &= MASK 23164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum for x in self: 23264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum hx = hash(x) 23364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum h ^= (hx ^ (hx << 16) ^ 89869747) * 3644798167 23464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum h &= MASK 23564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum h = h * 69069 + 907133923 23664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum h &= MASK 23764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum if h > MAX: 23864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum h -= MASK + 1 23964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum if h == -1: 24064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum h = 590923713 24164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return h 24264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 24364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van RossumSet.register(frozenset) 24464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 24564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 24664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossumclass MutableSet(Set): 24764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 24864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum @abstractmethod 24964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def add(self, value): 25064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum """Return True if it was added, False if already there.""" 25164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum raise NotImplementedError 25264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 25364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum @abstractmethod 25464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def discard(self, value): 25564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum """Return True if it was deleted, False if not there.""" 25664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum raise NotImplementedError 25764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 2587d518f418b8bb7f155c8e695adbc5b69ac0ed0fdRaymond Hettinger def remove(self, value): 2597d518f418b8bb7f155c8e695adbc5b69ac0ed0fdRaymond Hettinger """Remove an element. If not a member, raise a KeyError.""" 2607d518f418b8bb7f155c8e695adbc5b69ac0ed0fdRaymond Hettinger if value not in self: 2617d518f418b8bb7f155c8e695adbc5b69ac0ed0fdRaymond Hettinger raise KeyError(value) 2627d518f418b8bb7f155c8e695adbc5b69ac0ed0fdRaymond Hettinger self.discard(value) 2637d518f418b8bb7f155c8e695adbc5b69ac0ed0fdRaymond Hettinger 26464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def pop(self): 26564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum """Return the popped value. Raise KeyError if empty.""" 26664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum it = iter(self) 26764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum try: 26864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum value = it.__next__() 26964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum except StopIteration: 27064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum raise KeyError 27164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum self.discard(value) 27264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return value 27364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 27464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def clear(self): 27564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum """This is slow (creates N new iterators!) but effective.""" 27664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum try: 27764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum while True: 27864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum self.pop() 27964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum except KeyError: 28064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum pass 28164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 28264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __ior__(self, it): 28364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum for value in it: 28464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum self.add(value) 28564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return self 28664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 28764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __iand__(self, c): 28864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum for value in self: 28964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum if value not in c: 29064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum self.discard(value) 29164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return self 29264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 29364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __ixor__(self, it): 294e67420d72e26d976af2c8cd8603f2dfe158b6d24Raymond Hettinger if not isinstance(it, Set): 295e67420d72e26d976af2c8cd8603f2dfe158b6d24Raymond Hettinger it = self._from_iterable(it) 29664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum for value in it: 297e67420d72e26d976af2c8cd8603f2dfe158b6d24Raymond Hettinger if value in self: 298e67420d72e26d976af2c8cd8603f2dfe158b6d24Raymond Hettinger self.discard(value) 299e67420d72e26d976af2c8cd8603f2dfe158b6d24Raymond Hettinger else: 300e67420d72e26d976af2c8cd8603f2dfe158b6d24Raymond Hettinger self.add(value) 301e973c61238807dcf4ccedc18a99db8f478c422c7Raymond Hettinger return self 30264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 30364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __isub__(self, it): 30464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum for value in it: 30564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum self.discard(value) 30664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return self 30764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 30864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van RossumMutableSet.register(set) 30964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 31064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 31164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum### MAPPINGS ### 31264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 31364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 314c2bc0d17e83ad88b829a669cc9ee7194b9e46593Raymond Hettingerclass Mapping(Sized, Iterable, Container): 31564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum __metaclass__ = ABCMeta 31664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 31764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum @abstractmethod 31864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __getitem__(self, key): 31964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum raise KeyError 32064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 32164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def get(self, key, default=None): 32264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum try: 32364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return self[key] 32464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum except KeyError: 32564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return default 32664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 32764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __contains__(self, key): 32864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum try: 32964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum self[key] 33064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum except KeyError: 33164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return False 33264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum else: 33364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return True 33464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 33564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def keys(self): 33664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return KeysView(self) 33764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 33864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def items(self): 33964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return ItemsView(self) 34064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 34164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def values(self): 34264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return ValuesView(self) 34364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 34445eda6469124855d349666184c6f92058a9e08f0Raymond Hettinger def __eq__(self, other): 34545eda6469124855d349666184c6f92058a9e08f0Raymond Hettinger return isinstance(other, Mapping) and \ 34645eda6469124855d349666184c6f92058a9e08f0Raymond Hettinger dict(self.items()) == dict(other.items()) 34745eda6469124855d349666184c6f92058a9e08f0Raymond Hettinger 34845eda6469124855d349666184c6f92058a9e08f0Raymond Hettinger def __ne__(self, other): 34945eda6469124855d349666184c6f92058a9e08f0Raymond Hettinger return not (self == other) 35064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 351c2bc0d17e83ad88b829a669cc9ee7194b9e46593Raymond Hettingerclass MappingView(Sized): 35264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum __metaclass__ = ABCMeta 35364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 35464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __init__(self, mapping): 35564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum self._mapping = mapping 35664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 35764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __len__(self): 35864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return len(self._mapping) 35964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 36064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 36164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossumclass KeysView(MappingView, Set): 36264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 36364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __contains__(self, key): 36464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return key in self._mapping 36564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 36664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __iter__(self): 36764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum for key in self._mapping: 36864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum yield key 36964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 37064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van RossumKeysView.register(type({}.keys())) 37164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 37264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 37364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossumclass ItemsView(MappingView, Set): 37464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 37564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __contains__(self, item): 37664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum key, value = item 37764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum try: 37864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum v = self._mapping[key] 37964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum except KeyError: 38064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return False 38164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum else: 38264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return v == value 38364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 38464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __iter__(self): 38564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum for key in self._mapping: 38664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum yield (key, self._mapping[key]) 38764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 38864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van RossumItemsView.register(type({}.items())) 38964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 39064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 39164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossumclass ValuesView(MappingView): 39264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 39364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __contains__(self, value): 39464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum for key in self._mapping: 39564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum if value == self._mapping[key]: 39664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return True 39764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return False 39864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 39964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __iter__(self): 40064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum for key in self._mapping: 40164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum yield self._mapping[key] 40264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 40364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van RossumValuesView.register(type({}.values())) 40464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 40564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 40664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossumclass MutableMapping(Mapping): 40764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 40864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum @abstractmethod 40964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __setitem__(self, key, value): 41064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum raise KeyError 41164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 41264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum @abstractmethod 41364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __delitem__(self, key): 41464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum raise KeyError 41564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 41664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum __marker = object() 41764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 41864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def pop(self, key, default=__marker): 41964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum try: 42064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum value = self[key] 42164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum except KeyError: 42264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum if default is self.__marker: 42364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum raise 42464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return default 42564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum else: 42664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum del self[key] 42764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return value 42864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 42964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def popitem(self): 43064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum try: 43164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum key = next(iter(self)) 43264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum except StopIteration: 43364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum raise KeyError 43464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum value = self[key] 43564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum del self[key] 43664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return key, value 43764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 43864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def clear(self): 43964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum try: 44064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum while True: 44164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum self.popitem() 44264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum except KeyError: 44364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum pass 44464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 44564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def update(self, other=(), **kwds): 44664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum if isinstance(other, Mapping): 44764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum for key in other: 44864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum self[key] = other[key] 44964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum elif hasattr(other, "keys"): 45064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum for key in other.keys(): 45164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum self[key] = other[key] 45264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum else: 45364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum for key, value in other: 45464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum self[key] = value 45564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum for key, value in kwds.items(): 45664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum self[key] = value 45764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 45845eda6469124855d349666184c6f92058a9e08f0Raymond Hettinger def setdefault(self, key, default=None): 45945eda6469124855d349666184c6f92058a9e08f0Raymond Hettinger try: 46045eda6469124855d349666184c6f92058a9e08f0Raymond Hettinger return self[key] 46145eda6469124855d349666184c6f92058a9e08f0Raymond Hettinger except KeyError: 46245eda6469124855d349666184c6f92058a9e08f0Raymond Hettinger self[key] = default 46345eda6469124855d349666184c6f92058a9e08f0Raymond Hettinger return default 46445eda6469124855d349666184c6f92058a9e08f0Raymond Hettinger 46564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van RossumMutableMapping.register(dict) 46664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 46764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 46864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum### SEQUENCES ### 46964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 47064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 471c2bc0d17e83ad88b829a669cc9ee7194b9e46593Raymond Hettingerclass Sequence(Sized, Iterable, Container): 47264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum __metaclass__ = ABCMeta 47364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 47464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum """All the operations on a read-only sequence. 47564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 47664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum Concrete subclasses must override __new__ or __init__, 47764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum __getitem__, and __len__. 47864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum """ 47964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 48064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum @abstractmethod 48164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __getitem__(self, index): 48264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum raise IndexError 48364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 48464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __iter__(self): 48564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum i = 0 48618a1ffcda373fad5f60c187217d7c2125bccf005Raymond Hettinger try: 48718a1ffcda373fad5f60c187217d7c2125bccf005Raymond Hettinger while True: 48864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum v = self[i] 48918a1ffcda373fad5f60c187217d7c2125bccf005Raymond Hettinger yield v 49018a1ffcda373fad5f60c187217d7c2125bccf005Raymond Hettinger i += 1 49118a1ffcda373fad5f60c187217d7c2125bccf005Raymond Hettinger except IndexError: 49218a1ffcda373fad5f60c187217d7c2125bccf005Raymond Hettinger return 49364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 49464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __contains__(self, value): 49564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum for v in self: 49664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum if v == value: 49764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return True 49864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return False 49964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 50064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __reversed__(self): 50164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum for i in reversed(range(len(self))): 50264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum yield self[i] 50364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 50464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def index(self, value): 50564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum for i, v in enumerate(self): 50664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum if v == value: 50764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return i 50864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum raise ValueError 50964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 51064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def count(self, value): 51164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return sum(1 for v in self if v == value) 51264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 51364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van RossumSequence.register(tuple) 51464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van RossumSequence.register(basestring) 51564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van RossumSequence.register(buffer) 51664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 51764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 51864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossumclass MutableSequence(Sequence): 51964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 52064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum @abstractmethod 52164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __setitem__(self, index, value): 52264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum raise IndexError 52364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 52464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum @abstractmethod 52564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __delitem__(self, index): 52664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum raise IndexError 52764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 52864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum @abstractmethod 52964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def insert(self, index, value): 53064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum raise IndexError 53164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 53264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def append(self, value): 53364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum self.insert(len(self), value) 53464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 53564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def reverse(self): 53664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum n = len(self) 53764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum for i in range(n//2): 53864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum self[i], self[n-i-1] = self[n-i-1], self[i] 53964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 54064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def extend(self, values): 54164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum for v in values: 54264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum self.append(v) 54364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 54464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def pop(self, index=-1): 54564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum v = self[index] 54664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum del self[index] 54764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return v 54864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 54964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def remove(self, value): 55064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum del self[self.index(value)] 55164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 55264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __iadd__(self, values): 55364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum self.extend(values) 55464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 55564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van RossumMutableSequence.register(list) 556