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 124c52f52ef3051af3b3504b7a0818e5948daa03a7Raymond Hettingerimport sys 1364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 1464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum__all__ = ["Hashable", "Iterable", "Iterator", 1564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum "Sized", "Container", "Callable", 1664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum "Set", "MutableSet", 1764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum "Mapping", "MutableMapping", 1864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum "MappingView", "KeysView", "ItemsView", "ValuesView", 1964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum "Sequence", "MutableSequence", 2064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum ] 2164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 2264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum### ONE-TRICK PONIES ### 2364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 2447627d51644d3fcc57390455ef845f72e6387485Florent Xiclunadef _hasattr(C, attr): 2547627d51644d3fcc57390455ef845f72e6387485Florent Xicluna try: 2647627d51644d3fcc57390455ef845f72e6387485Florent Xicluna return any(attr in B.__dict__ for B in C.__mro__) 2747627d51644d3fcc57390455ef845f72e6387485Florent Xicluna except AttributeError: 2847627d51644d3fcc57390455ef845f72e6387485Florent Xicluna # Old-style class 2947627d51644d3fcc57390455ef845f72e6387485Florent Xicluna return hasattr(C, attr) 3047627d51644d3fcc57390455ef845f72e6387485Florent Xicluna 3147627d51644d3fcc57390455ef845f72e6387485Florent Xicluna 3264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossumclass Hashable: 3364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum __metaclass__ = ABCMeta 3464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 3564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum @abstractmethod 3664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __hash__(self): 3764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return 0 3864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 3964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum @classmethod 4064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __subclasshook__(cls, C): 4164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum if cls is Hashable: 4247627d51644d3fcc57390455ef845f72e6387485Florent Xicluna try: 4347627d51644d3fcc57390455ef845f72e6387485Florent Xicluna for B in C.__mro__: 4447627d51644d3fcc57390455ef845f72e6387485Florent Xicluna if "__hash__" in B.__dict__: 4547627d51644d3fcc57390455ef845f72e6387485Florent Xicluna if B.__dict__["__hash__"]: 4647627d51644d3fcc57390455ef845f72e6387485Florent Xicluna return True 4747627d51644d3fcc57390455ef845f72e6387485Florent Xicluna break 4847627d51644d3fcc57390455ef845f72e6387485Florent Xicluna except AttributeError: 4947627d51644d3fcc57390455ef845f72e6387485Florent Xicluna # Old-style class 5047627d51644d3fcc57390455ef845f72e6387485Florent Xicluna if getattr(C, "__hash__", None): 5147627d51644d3fcc57390455ef845f72e6387485Florent Xicluna return True 5264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return NotImplemented 5364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 5464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 5564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossumclass Iterable: 5664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum __metaclass__ = ABCMeta 5764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 5864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum @abstractmethod 5964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __iter__(self): 6064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum while False: 6164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum yield None 6264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 6364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum @classmethod 6464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __subclasshook__(cls, C): 6564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum if cls is Iterable: 6647627d51644d3fcc57390455ef845f72e6387485Florent Xicluna if _hasattr(C, "__iter__"): 6764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return True 6864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return NotImplemented 6964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 7064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van RossumIterable.register(str) 7164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 7264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 73c2bc0d17e83ad88b829a669cc9ee7194b9e46593Raymond Hettingerclass Iterator(Iterable): 7464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 7564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum @abstractmethod 76f779e6f51bc9e96af8478d9463b1f10876fdc729Raymond Hettinger def next(self): 77cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger 'Return the next item from the iterator. When exhausted, raise StopIteration' 7864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum raise StopIteration 7964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 8064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __iter__(self): 8164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return self 8264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 8364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum @classmethod 8464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __subclasshook__(cls, C): 8564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum if cls is Iterator: 861fea5c4472b29fff85ae40a8d7f0c845347ad5c6Alexander Belopolsky if _hasattr(C, "next") and _hasattr(C, "__iter__"): 8764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return True 8864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return NotImplemented 8964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 9064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 9164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossumclass Sized: 9264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum __metaclass__ = ABCMeta 9364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 9464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum @abstractmethod 9564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __len__(self): 9664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return 0 9764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 9864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum @classmethod 9964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __subclasshook__(cls, C): 10064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum if cls is Sized: 10147627d51644d3fcc57390455ef845f72e6387485Florent Xicluna if _hasattr(C, "__len__"): 10264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return True 10364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return NotImplemented 10464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 10564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 10664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossumclass Container: 10764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum __metaclass__ = ABCMeta 10864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 10964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum @abstractmethod 11064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __contains__(self, x): 11164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return False 11264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 11364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum @classmethod 11464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __subclasshook__(cls, C): 11564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum if cls is Container: 11647627d51644d3fcc57390455ef845f72e6387485Florent Xicluna if _hasattr(C, "__contains__"): 11764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return True 11864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return NotImplemented 11964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 12064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 12164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossumclass Callable: 12264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum __metaclass__ = ABCMeta 12364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 12464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum @abstractmethod 12510ac19bedce075d48c8c330cadec0d98393e7270Raymond Hettinger def __call__(self, *args, **kwds): 12664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return False 12764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 12864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum @classmethod 12964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __subclasshook__(cls, C): 13064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum if cls is Callable: 13147627d51644d3fcc57390455ef845f72e6387485Florent Xicluna if _hasattr(C, "__call__"): 13264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return True 13364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return NotImplemented 13464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 13564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 13664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum### SETS ### 13764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 13864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 139c2bc0d17e83ad88b829a669cc9ee7194b9e46593Raymond Hettingerclass Set(Sized, Iterable, Container): 14064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum """A set is a finite, iterable container. 14164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 14264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum This class provides concrete generic implementations of all 14364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum methods except for __contains__, __iter__ and __len__. 14464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 14564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum To override the comparisons (presumably for speed, as the 146809b665b57edccde6418fb9e4a0135a1e629e79aRaymond Hettinger semantics are fixed), redefine __le__ and __ge__, 14764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum then the other operations will automatically follow suit. 14864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum """ 14964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 15064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __le__(self, other): 15164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum if not isinstance(other, Set): 15264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return NotImplemented 15364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum if len(self) > len(other): 15464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return False 15564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum for elem in self: 15664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum if elem not in other: 15764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return False 15864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return True 15964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 16064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __lt__(self, other): 16164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum if not isinstance(other, Set): 16264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return NotImplemented 16364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return len(self) < len(other) and self.__le__(other) 16464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 165d53f1c4d41e863c8a7f0653ea7af04dc0b4faa84Raymond Hettinger def __gt__(self, other): 166d53f1c4d41e863c8a7f0653ea7af04dc0b4faa84Raymond Hettinger if not isinstance(other, Set): 167d53f1c4d41e863c8a7f0653ea7af04dc0b4faa84Raymond Hettinger return NotImplemented 168f643b9a9c79928c4ca28d895e7e9a1dcf827cf00Raymond Hettinger return len(self) > len(other) and self.__ge__(other) 169d53f1c4d41e863c8a7f0653ea7af04dc0b4faa84Raymond Hettinger 170d53f1c4d41e863c8a7f0653ea7af04dc0b4faa84Raymond Hettinger def __ge__(self, other): 171d53f1c4d41e863c8a7f0653ea7af04dc0b4faa84Raymond Hettinger if not isinstance(other, Set): 172d53f1c4d41e863c8a7f0653ea7af04dc0b4faa84Raymond Hettinger return NotImplemented 173f643b9a9c79928c4ca28d895e7e9a1dcf827cf00Raymond Hettinger if len(self) < len(other): 174f643b9a9c79928c4ca28d895e7e9a1dcf827cf00Raymond Hettinger return False 175f643b9a9c79928c4ca28d895e7e9a1dcf827cf00Raymond Hettinger for elem in other: 176f643b9a9c79928c4ca28d895e7e9a1dcf827cf00Raymond Hettinger if elem not in self: 177f643b9a9c79928c4ca28d895e7e9a1dcf827cf00Raymond Hettinger return False 178f643b9a9c79928c4ca28d895e7e9a1dcf827cf00Raymond Hettinger return True 179d53f1c4d41e863c8a7f0653ea7af04dc0b4faa84Raymond Hettinger 18064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __eq__(self, other): 18164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum if not isinstance(other, Set): 18264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return NotImplemented 18364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return len(self) == len(other) and self.__le__(other) 18464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 185d53f1c4d41e863c8a7f0653ea7af04dc0b4faa84Raymond Hettinger def __ne__(self, other): 186d53f1c4d41e863c8a7f0653ea7af04dc0b4faa84Raymond Hettinger return not (self == other) 187d53f1c4d41e863c8a7f0653ea7af04dc0b4faa84Raymond Hettinger 18864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum @classmethod 18964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def _from_iterable(cls, it): 190017b6a3ad2be5c0e3309fb016234397211d6ffa7Raymond Hettinger '''Construct an instance of the class from any iterable input. 191017b6a3ad2be5c0e3309fb016234397211d6ffa7Raymond Hettinger 192017b6a3ad2be5c0e3309fb016234397211d6ffa7Raymond Hettinger Must override this method if the class constructor signature 1932e827bfdfea7b940517f90af78c986aec9159d2cRaymond Hettinger does not accept an iterable for an input. 194017b6a3ad2be5c0e3309fb016234397211d6ffa7Raymond Hettinger ''' 1952e827bfdfea7b940517f90af78c986aec9159d2cRaymond Hettinger return cls(it) 19664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 19764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __and__(self, other): 19864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum if not isinstance(other, Iterable): 19964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return NotImplemented 20064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return self._from_iterable(value for value in other if value in self) 20164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 202f643b9a9c79928c4ca28d895e7e9a1dcf827cf00Raymond Hettinger __rand__ = __and__ 203f643b9a9c79928c4ca28d895e7e9a1dcf827cf00Raymond Hettinger 204abf3fcf39fb3bff4d347296a083a4c62d515dacdRaymond Hettinger def isdisjoint(self, other): 205cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger 'Return True if two sets have a null intersection.' 206abf3fcf39fb3bff4d347296a083a4c62d515dacdRaymond Hettinger for value in other: 207abf3fcf39fb3bff4d347296a083a4c62d515dacdRaymond Hettinger if value in self: 208abf3fcf39fb3bff4d347296a083a4c62d515dacdRaymond Hettinger return False 209abf3fcf39fb3bff4d347296a083a4c62d515dacdRaymond Hettinger return True 210abf3fcf39fb3bff4d347296a083a4c62d515dacdRaymond Hettinger 21164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __or__(self, other): 21264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum if not isinstance(other, Iterable): 21364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return NotImplemented 214972fb077a022722113e155ebf564f98ebdbe2b65Raymond Hettinger chain = (e for s in (self, other) for e in s) 215972fb077a022722113e155ebf564f98ebdbe2b65Raymond Hettinger return self._from_iterable(chain) 21664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 217f643b9a9c79928c4ca28d895e7e9a1dcf827cf00Raymond Hettinger __ror__ = __or__ 218f643b9a9c79928c4ca28d895e7e9a1dcf827cf00Raymond Hettinger 21964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __sub__(self, other): 22064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum if not isinstance(other, Set): 22164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum if not isinstance(other, Iterable): 22264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return NotImplemented 22364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum other = self._from_iterable(other) 22464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return self._from_iterable(value for value in self 22564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum if value not in other) 22664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 227f643b9a9c79928c4ca28d895e7e9a1dcf827cf00Raymond Hettinger def __rsub__(self, other): 228f643b9a9c79928c4ca28d895e7e9a1dcf827cf00Raymond Hettinger if not isinstance(other, Set): 229f643b9a9c79928c4ca28d895e7e9a1dcf827cf00Raymond Hettinger if not isinstance(other, Iterable): 230f643b9a9c79928c4ca28d895e7e9a1dcf827cf00Raymond Hettinger return NotImplemented 231f643b9a9c79928c4ca28d895e7e9a1dcf827cf00Raymond Hettinger other = self._from_iterable(other) 232f643b9a9c79928c4ca28d895e7e9a1dcf827cf00Raymond Hettinger return self._from_iterable(value for value in other 233f643b9a9c79928c4ca28d895e7e9a1dcf827cf00Raymond Hettinger if value not in self) 234f643b9a9c79928c4ca28d895e7e9a1dcf827cf00Raymond Hettinger 23564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __xor__(self, other): 23664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum if not isinstance(other, Set): 23764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum if not isinstance(other, Iterable): 23864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return NotImplemented 23964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum other = self._from_iterable(other) 24064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return (self - other) | (other - self) 24164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 242f643b9a9c79928c4ca28d895e7e9a1dcf827cf00Raymond Hettinger __rxor__ = __xor__ 243f643b9a9c79928c4ca28d895e7e9a1dcf827cf00Raymond Hettinger 24448361f5cbf419cce361fd1aa0389d6304ad167dbNick Coghlan # Sets are not hashable by default, but subclasses can change this 24548361f5cbf419cce361fd1aa0389d6304ad167dbNick Coghlan __hash__ = None 24648361f5cbf419cce361fd1aa0389d6304ad167dbNick Coghlan 24764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def _hash(self): 24864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum """Compute the hash value of a set. 24964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 25064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum Note that we don't define __hash__: not all sets are hashable. 25164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum But if you define a hashable set type, its __hash__ should 25264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum call this function. 25364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 25464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum This must be compatible __eq__. 25564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 25664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum All sets ought to compare equal if they contain the same 25764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum elements, regardless of how they are implemented, and 25864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum regardless of the order of the elements; so there's not much 25964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum freedom for __eq__ or __hash__. We match the algorithm used 26064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum by the built-in frozenset type. 26164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum """ 26264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum MAX = sys.maxint 26364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum MASK = 2 * MAX + 1 26464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum n = len(self) 26564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum h = 1927868237 * (n + 1) 26664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum h &= MASK 26764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum for x in self: 26864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum hx = hash(x) 26964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum h ^= (hx ^ (hx << 16) ^ 89869747) * 3644798167 27064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum h &= MASK 27164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum h = h * 69069 + 907133923 27264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum h &= MASK 27364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum if h > MAX: 27464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum h -= MASK + 1 27564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum if h == -1: 27664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum h = 590923713 27764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return h 27864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 27964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van RossumSet.register(frozenset) 28064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 28164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 28264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossumclass MutableSet(Set): 283cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger """A mutable set is a finite, iterable container. 284cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger 285cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger This class provides concrete generic implementations of all 286cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger methods except for __contains__, __iter__, __len__, 287cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger add(), and discard(). 288cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger 289cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger To override the comparisons (presumably for speed, as the 290cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger semantics are fixed), all you have to do is redefine __le__ and 291cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger then the other operations will automatically follow suit. 292cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger """ 29364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 29464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum @abstractmethod 29564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def add(self, value): 2962d21d50c10d1041f56d6f089d66a98b2bbf55e12Raymond Hettinger """Add an element.""" 29764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum raise NotImplementedError 29864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 29964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum @abstractmethod 30064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def discard(self, value): 3012d21d50c10d1041f56d6f089d66a98b2bbf55e12Raymond Hettinger """Remove an element. Do not raise an exception if absent.""" 30264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum raise NotImplementedError 30364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 3047d518f418b8bb7f155c8e695adbc5b69ac0ed0fdRaymond Hettinger def remove(self, value): 3057d518f418b8bb7f155c8e695adbc5b69ac0ed0fdRaymond Hettinger """Remove an element. If not a member, raise a KeyError.""" 3067d518f418b8bb7f155c8e695adbc5b69ac0ed0fdRaymond Hettinger if value not in self: 3077d518f418b8bb7f155c8e695adbc5b69ac0ed0fdRaymond Hettinger raise KeyError(value) 3087d518f418b8bb7f155c8e695adbc5b69ac0ed0fdRaymond Hettinger self.discard(value) 3097d518f418b8bb7f155c8e695adbc5b69ac0ed0fdRaymond Hettinger 31064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def pop(self): 31164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum """Return the popped value. Raise KeyError if empty.""" 31264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum it = iter(self) 31364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum try: 314f779e6f51bc9e96af8478d9463b1f10876fdc729Raymond Hettinger value = next(it) 31564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum except StopIteration: 31664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum raise KeyError 31764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum self.discard(value) 31864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return value 31964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 32064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def clear(self): 32164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum """This is slow (creates N new iterators!) but effective.""" 32264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum try: 32364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum while True: 32464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum self.pop() 32564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum except KeyError: 32664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum pass 32764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 32864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __ior__(self, it): 32964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum for value in it: 33064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum self.add(value) 33164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return self 33264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 33366c4a6b51cea40215e8f61e1abe2e3d89c4aeb1eRaymond Hettinger def __iand__(self, it): 33466c4a6b51cea40215e8f61e1abe2e3d89c4aeb1eRaymond Hettinger for value in (self - it): 33566c4a6b51cea40215e8f61e1abe2e3d89c4aeb1eRaymond Hettinger self.discard(value) 33664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return self 33764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 33864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __ixor__(self, it): 3399128732de668e5777e135a423d3fa8b9bbd71fe1Daniel Stutzbach if it is self: 3409128732de668e5777e135a423d3fa8b9bbd71fe1Daniel Stutzbach self.clear() 3419128732de668e5777e135a423d3fa8b9bbd71fe1Daniel Stutzbach else: 3429128732de668e5777e135a423d3fa8b9bbd71fe1Daniel Stutzbach if not isinstance(it, Set): 3439128732de668e5777e135a423d3fa8b9bbd71fe1Daniel Stutzbach it = self._from_iterable(it) 3449128732de668e5777e135a423d3fa8b9bbd71fe1Daniel Stutzbach for value in it: 3459128732de668e5777e135a423d3fa8b9bbd71fe1Daniel Stutzbach if value in self: 3469128732de668e5777e135a423d3fa8b9bbd71fe1Daniel Stutzbach self.discard(value) 3479128732de668e5777e135a423d3fa8b9bbd71fe1Daniel Stutzbach else: 3489128732de668e5777e135a423d3fa8b9bbd71fe1Daniel Stutzbach self.add(value) 349e973c61238807dcf4ccedc18a99db8f478c422c7Raymond Hettinger return self 35064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 35164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __isub__(self, it): 3529128732de668e5777e135a423d3fa8b9bbd71fe1Daniel Stutzbach if it is self: 3539128732de668e5777e135a423d3fa8b9bbd71fe1Daniel Stutzbach self.clear() 3549128732de668e5777e135a423d3fa8b9bbd71fe1Daniel Stutzbach else: 3559128732de668e5777e135a423d3fa8b9bbd71fe1Daniel Stutzbach for value in it: 3569128732de668e5777e135a423d3fa8b9bbd71fe1Daniel Stutzbach self.discard(value) 35764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return self 35864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 35964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van RossumMutableSet.register(set) 36064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 36164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 36264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum### MAPPINGS ### 36364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 36464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 365c2bc0d17e83ad88b829a669cc9ee7194b9e46593Raymond Hettingerclass Mapping(Sized, Iterable, Container): 36664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 367cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger """A Mapping is a generic container for associating key/value 368cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger pairs. 369cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger 370cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger This class provides concrete generic implementations of all 371cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger methods except for __getitem__, __iter__, and __len__. 372cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger 373cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger """ 374cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger 37564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum @abstractmethod 37664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __getitem__(self, key): 37764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum raise KeyError 37864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 37964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def get(self, key, default=None): 380cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger 'D.get(k[,d]) -> D[k] if k in D, else d. d defaults to None.' 38164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum try: 38264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return self[key] 38364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum except KeyError: 38464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return default 38564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 38664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __contains__(self, key): 38764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum try: 38864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum self[key] 38964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum except KeyError: 39064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return False 39164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum else: 39264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return True 39364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 39460fbf7f8bb83dd10a8d71ae763f845e688399fa0Georg Brandl def iterkeys(self): 395cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger 'D.iterkeys() -> an iterator over the keys of D' 39660fbf7f8bb83dd10a8d71ae763f845e688399fa0Georg Brandl return iter(self) 39760fbf7f8bb83dd10a8d71ae763f845e688399fa0Georg Brandl 39860fbf7f8bb83dd10a8d71ae763f845e688399fa0Georg Brandl def itervalues(self): 399cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger 'D.itervalues() -> an iterator over the values of D' 40060fbf7f8bb83dd10a8d71ae763f845e688399fa0Georg Brandl for key in self: 40160fbf7f8bb83dd10a8d71ae763f845e688399fa0Georg Brandl yield self[key] 40260fbf7f8bb83dd10a8d71ae763f845e688399fa0Georg Brandl 40360fbf7f8bb83dd10a8d71ae763f845e688399fa0Georg Brandl def iteritems(self): 404cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger 'D.iteritems() -> an iterator over the (key, value) items of D' 40560fbf7f8bb83dd10a8d71ae763f845e688399fa0Georg Brandl for key in self: 40660fbf7f8bb83dd10a8d71ae763f845e688399fa0Georg Brandl yield (key, self[key]) 40760fbf7f8bb83dd10a8d71ae763f845e688399fa0Georg Brandl 40864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def keys(self): 409cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger "D.keys() -> list of D's keys" 41060fbf7f8bb83dd10a8d71ae763f845e688399fa0Georg Brandl return list(self) 41164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 41264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def items(self): 413cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger "D.items() -> list of D's (key, value) pairs, as 2-tuples" 41460fbf7f8bb83dd10a8d71ae763f845e688399fa0Georg Brandl return [(key, self[key]) for key in self] 41564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 41664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def values(self): 417cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger "D.values() -> list of D's values" 41860fbf7f8bb83dd10a8d71ae763f845e688399fa0Georg Brandl return [self[key] for key in self] 41964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 42048361f5cbf419cce361fd1aa0389d6304ad167dbNick Coghlan # Mappings are not hashable by default, but subclasses can change this 42148361f5cbf419cce361fd1aa0389d6304ad167dbNick Coghlan __hash__ = None 42248361f5cbf419cce361fd1aa0389d6304ad167dbNick Coghlan 42345eda6469124855d349666184c6f92058a9e08f0Raymond Hettinger def __eq__(self, other): 424eb318d3b160a1631e462d1434e2ae9e1b5cfe158Benjamin Peterson if not isinstance(other, Mapping): 425eb318d3b160a1631e462d1434e2ae9e1b5cfe158Benjamin Peterson return NotImplemented 426eb318d3b160a1631e462d1434e2ae9e1b5cfe158Benjamin Peterson return dict(self.items()) == dict(other.items()) 42745eda6469124855d349666184c6f92058a9e08f0Raymond Hettinger 42845eda6469124855d349666184c6f92058a9e08f0Raymond Hettinger def __ne__(self, other): 42945eda6469124855d349666184c6f92058a9e08f0Raymond Hettinger return not (self == other) 43064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 431c2bc0d17e83ad88b829a669cc9ee7194b9e46593Raymond Hettingerclass MappingView(Sized): 43264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 43364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __init__(self, mapping): 43464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum self._mapping = mapping 43564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 43664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __len__(self): 43764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return len(self._mapping) 43864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 439b31a6d0949faecc933754f32ac956bc4aad76fffRaymond Hettinger def __repr__(self): 440b31a6d0949faecc933754f32ac956bc4aad76fffRaymond Hettinger return '{0.__class__.__name__}({0._mapping!r})'.format(self) 441b31a6d0949faecc933754f32ac956bc4aad76fffRaymond Hettinger 44264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 44364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossumclass KeysView(MappingView, Set): 44464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 445917bba1f2a382d5251b94eeadc344ec6ed3eaa97Raymond Hettinger @classmethod 446917bba1f2a382d5251b94eeadc344ec6ed3eaa97Raymond Hettinger def _from_iterable(self, it): 447917bba1f2a382d5251b94eeadc344ec6ed3eaa97Raymond Hettinger return set(it) 448917bba1f2a382d5251b94eeadc344ec6ed3eaa97Raymond Hettinger 44964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __contains__(self, key): 45064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return key in self._mapping 45164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 45264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __iter__(self): 45364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum for key in self._mapping: 45464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum yield key 45564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 4561a7c3571c789d704503135fe7c20d6e6f78aec86Raymond HettingerKeysView.register(type({}.viewkeys())) 45764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 45864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossumclass ItemsView(MappingView, Set): 45964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 460917bba1f2a382d5251b94eeadc344ec6ed3eaa97Raymond Hettinger @classmethod 461917bba1f2a382d5251b94eeadc344ec6ed3eaa97Raymond Hettinger def _from_iterable(self, it): 462917bba1f2a382d5251b94eeadc344ec6ed3eaa97Raymond Hettinger return set(it) 463917bba1f2a382d5251b94eeadc344ec6ed3eaa97Raymond Hettinger 46464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __contains__(self, item): 46564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum key, value = item 46664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum try: 46764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum v = self._mapping[key] 46864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum except KeyError: 46964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return False 47064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum else: 47164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return v == value 47264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 47364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __iter__(self): 47464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum for key in self._mapping: 47564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum yield (key, self._mapping[key]) 47664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 4771a7c3571c789d704503135fe7c20d6e6f78aec86Raymond HettingerItemsView.register(type({}.viewitems())) 47864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 47964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossumclass ValuesView(MappingView): 48064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 48164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __contains__(self, value): 48264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum for key in self._mapping: 48364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum if value == self._mapping[key]: 48464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return True 48564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return False 48664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 48764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __iter__(self): 48864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum for key in self._mapping: 48964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum yield self._mapping[key] 49064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 4911a7c3571c789d704503135fe7c20d6e6f78aec86Raymond HettingerValuesView.register(type({}.viewvalues())) 49264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 49364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossumclass MutableMapping(Mapping): 49464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 495cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger """A MutableMapping is a generic container for associating 496cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger key/value pairs. 497cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger 498cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger This class provides concrete generic implementations of all 499cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger methods except for __getitem__, __setitem__, __delitem__, 500cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger __iter__, and __len__. 501cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger 502cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger """ 503cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger 50464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum @abstractmethod 50564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __setitem__(self, key, value): 50664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum raise KeyError 50764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 50864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum @abstractmethod 50964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __delitem__(self, key): 51064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum raise KeyError 51164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 51264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum __marker = object() 51364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 51464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def pop(self, key, default=__marker): 515cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger '''D.pop(k[,d]) -> v, remove specified key and return the corresponding value. 516cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger If key is not found, d is returned if given, otherwise KeyError is raised. 517cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger ''' 51864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum try: 51964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum value = self[key] 52064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum except KeyError: 52164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum if default is self.__marker: 52264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum raise 52364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return default 52464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum else: 52564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum del self[key] 52664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return value 52764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 52864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def popitem(self): 529cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger '''D.popitem() -> (k, v), remove and return some (key, value) pair 530cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger as a 2-tuple; but raise KeyError if D is empty. 531cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger ''' 53264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum try: 53364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum key = next(iter(self)) 53464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum except StopIteration: 53564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum raise KeyError 53664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum value = self[key] 53764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum del self[key] 53864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return key, value 53964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 54064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def clear(self): 541cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger 'D.clear() -> None. Remove all items from D.' 54264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum try: 54364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum while True: 54464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum self.popitem() 54564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum except KeyError: 54664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum pass 54764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 54842add99f77fbb4eb1af65213e1b4936397afe490Mark Dickinson def update(*args, **kwds): 549cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger ''' D.update([E, ]**F) -> None. Update D from mapping/iterable E and F. 550cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger If E present and has a .keys() method, does: for k in E: D[k] = E[k] 551cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger If E present and lacks .keys() method, does: for (k, v) in E: D[k] = v 552cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger In either case, this is followed by: for k, v in F.items(): D[k] = v 553cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger ''' 55420994f1e27c38973f1854dbdcf9b29fe8e3cd6beSerhiy Storchaka if not args: 55520994f1e27c38973f1854dbdcf9b29fe8e3cd6beSerhiy Storchaka raise TypeError("descriptor 'update' of 'MutableMapping' object " 55620994f1e27c38973f1854dbdcf9b29fe8e3cd6beSerhiy Storchaka "needs an argument") 55742add99f77fbb4eb1af65213e1b4936397afe490Mark Dickinson self = args[0] 55820994f1e27c38973f1854dbdcf9b29fe8e3cd6beSerhiy Storchaka args = args[1:] 55920994f1e27c38973f1854dbdcf9b29fe8e3cd6beSerhiy Storchaka if len(args) > 1: 56020994f1e27c38973f1854dbdcf9b29fe8e3cd6beSerhiy Storchaka raise TypeError('update expected at most 1 arguments, got %d' % 56120994f1e27c38973f1854dbdcf9b29fe8e3cd6beSerhiy Storchaka len(args)) 56220994f1e27c38973f1854dbdcf9b29fe8e3cd6beSerhiy Storchaka if args: 56320994f1e27c38973f1854dbdcf9b29fe8e3cd6beSerhiy Storchaka other = args[0] 56420994f1e27c38973f1854dbdcf9b29fe8e3cd6beSerhiy Storchaka if isinstance(other, Mapping): 56520994f1e27c38973f1854dbdcf9b29fe8e3cd6beSerhiy Storchaka for key in other: 56620994f1e27c38973f1854dbdcf9b29fe8e3cd6beSerhiy Storchaka self[key] = other[key] 56720994f1e27c38973f1854dbdcf9b29fe8e3cd6beSerhiy Storchaka elif hasattr(other, "keys"): 56820994f1e27c38973f1854dbdcf9b29fe8e3cd6beSerhiy Storchaka for key in other.keys(): 56920994f1e27c38973f1854dbdcf9b29fe8e3cd6beSerhiy Storchaka self[key] = other[key] 57020994f1e27c38973f1854dbdcf9b29fe8e3cd6beSerhiy Storchaka else: 57120994f1e27c38973f1854dbdcf9b29fe8e3cd6beSerhiy Storchaka for key, value in other: 57220994f1e27c38973f1854dbdcf9b29fe8e3cd6beSerhiy Storchaka self[key] = value 57364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum for key, value in kwds.items(): 57464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum self[key] = value 57564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 57645eda6469124855d349666184c6f92058a9e08f0Raymond Hettinger def setdefault(self, key, default=None): 577cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger 'D.setdefault(k[,d]) -> D.get(k,d), also set D[k]=d if k not in D' 57845eda6469124855d349666184c6f92058a9e08f0Raymond Hettinger try: 57945eda6469124855d349666184c6f92058a9e08f0Raymond Hettinger return self[key] 58045eda6469124855d349666184c6f92058a9e08f0Raymond Hettinger except KeyError: 58145eda6469124855d349666184c6f92058a9e08f0Raymond Hettinger self[key] = default 58245eda6469124855d349666184c6f92058a9e08f0Raymond Hettinger return default 58345eda6469124855d349666184c6f92058a9e08f0Raymond Hettinger 58464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van RossumMutableMapping.register(dict) 58564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 58664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 58764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum### SEQUENCES ### 58864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 58964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 590c2bc0d17e83ad88b829a669cc9ee7194b9e46593Raymond Hettingerclass Sequence(Sized, Iterable, Container): 59164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum """All the operations on a read-only sequence. 59264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 59364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum Concrete subclasses must override __new__ or __init__, 59464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum __getitem__, and __len__. 59564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum """ 59664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 59764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum @abstractmethod 59864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __getitem__(self, index): 59964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum raise IndexError 60064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 60164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __iter__(self): 60264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum i = 0 60318a1ffcda373fad5f60c187217d7c2125bccf005Raymond Hettinger try: 60418a1ffcda373fad5f60c187217d7c2125bccf005Raymond Hettinger while True: 60564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum v = self[i] 60618a1ffcda373fad5f60c187217d7c2125bccf005Raymond Hettinger yield v 60718a1ffcda373fad5f60c187217d7c2125bccf005Raymond Hettinger i += 1 60818a1ffcda373fad5f60c187217d7c2125bccf005Raymond Hettinger except IndexError: 60918a1ffcda373fad5f60c187217d7c2125bccf005Raymond Hettinger return 61064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 61164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __contains__(self, value): 61264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum for v in self: 61364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum if v == value: 61464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return True 61564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return False 61664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 61764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __reversed__(self): 61864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum for i in reversed(range(len(self))): 61964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum yield self[i] 62064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 62164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def index(self, value): 622cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger '''S.index(value) -> integer -- return first index of value. 623cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger Raises ValueError if the value is not present. 624cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger ''' 62564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum for i, v in enumerate(self): 62664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum if v == value: 62764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return i 62864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum raise ValueError 62964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 63064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def count(self, value): 631cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger 'S.count(value) -> integer -- return number of occurrences of value' 63264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return sum(1 for v in self if v == value) 63364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 63464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van RossumSequence.register(tuple) 63564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van RossumSequence.register(basestring) 63664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van RossumSequence.register(buffer) 6378c56f8890eefdfd769d864aa901db5cf4586b4cdRaymond HettingerSequence.register(xrange) 63864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 63964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 64064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossumclass MutableSequence(Sequence): 64164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 642cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger """All the operations on a read-only sequence. 643cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger 644cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger Concrete subclasses must provide __new__ or __init__, 645cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger __getitem__, __setitem__, __delitem__, __len__, and insert(). 646cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger 647cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger """ 648cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger 64964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum @abstractmethod 65064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __setitem__(self, index, value): 65164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum raise IndexError 65264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 65364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum @abstractmethod 65464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __delitem__(self, index): 65564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum raise IndexError 65664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 65764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum @abstractmethod 65864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def insert(self, index, value): 659cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger 'S.insert(index, object) -- insert object before index' 66064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum raise IndexError 66164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 66264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def append(self, value): 663cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger 'S.append(object) -- append object to the end of the sequence' 66464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum self.insert(len(self), value) 66564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 66664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def reverse(self): 667cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger 'S.reverse() -- reverse *IN PLACE*' 66864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum n = len(self) 66964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum for i in range(n//2): 67064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum self[i], self[n-i-1] = self[n-i-1], self[i] 67164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 67264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def extend(self, values): 673cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger 'S.extend(iterable) -- extend sequence by appending elements from the iterable' 67464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum for v in values: 67564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum self.append(v) 67664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 67764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def pop(self, index=-1): 678cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger '''S.pop([index]) -> item -- remove and return item at index (default last). 679cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger Raise IndexError if list is empty or index is out of range. 680cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger ''' 68164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum v = self[index] 68264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum del self[index] 68364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return v 68464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 68564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def remove(self, value): 686cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger '''S.remove(value) -- remove first occurrence of value. 687cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger Raise ValueError if the value is not present. 688cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger ''' 68964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum del self[self.index(value)] 69064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 69164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __iadd__(self, values): 69264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum self.extend(values) 693fceb5d478fcc43b764a9d1ad0a90e098828a7f64Raymond Hettinger return self 69464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 69564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van RossumMutableSequence.register(list) 696