_abcoll.py revision cce5b04c75e1959a48cf41d210c9179ef3ce2e69
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 14664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum semantics are fixed), all you have to do is redefine __le__ and 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 168d53f1c4d41e863c8a7f0653ea7af04dc0b4faa84Raymond Hettinger return other < self 169d53f1c4d41e863c8a7f0653ea7af04dc0b4faa84Raymond Hettinger 170d53f1c4d41e863c8a7f0653ea7af04dc0b4faa84Raymond Hettinger def __ge__(self, other): 171d53f1c4d41e863c8a7f0653ea7af04dc0b4faa84Raymond Hettinger if not isinstance(other, Set): 172d53f1c4d41e863c8a7f0653ea7af04dc0b4faa84Raymond Hettinger return NotImplemented 173d53f1c4d41e863c8a7f0653ea7af04dc0b4faa84Raymond Hettinger return other <= self 174d53f1c4d41e863c8a7f0653ea7af04dc0b4faa84Raymond Hettinger 17564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __eq__(self, other): 17664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum if not isinstance(other, Set): 17764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return NotImplemented 17864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return len(self) == len(other) and self.__le__(other) 17964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 180d53f1c4d41e863c8a7f0653ea7af04dc0b4faa84Raymond Hettinger def __ne__(self, other): 181d53f1c4d41e863c8a7f0653ea7af04dc0b4faa84Raymond Hettinger return not (self == other) 182d53f1c4d41e863c8a7f0653ea7af04dc0b4faa84Raymond Hettinger 18364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum @classmethod 18464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def _from_iterable(cls, it): 185017b6a3ad2be5c0e3309fb016234397211d6ffa7Raymond Hettinger '''Construct an instance of the class from any iterable input. 186017b6a3ad2be5c0e3309fb016234397211d6ffa7Raymond Hettinger 187017b6a3ad2be5c0e3309fb016234397211d6ffa7Raymond Hettinger Must override this method if the class constructor signature 1882e827bfdfea7b940517f90af78c986aec9159d2cRaymond Hettinger does not accept an iterable for an input. 189017b6a3ad2be5c0e3309fb016234397211d6ffa7Raymond Hettinger ''' 1902e827bfdfea7b940517f90af78c986aec9159d2cRaymond Hettinger return cls(it) 19164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 19264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __and__(self, other): 19364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum if not isinstance(other, Iterable): 19464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return NotImplemented 19564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return self._from_iterable(value for value in other if value in self) 19664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 197abf3fcf39fb3bff4d347296a083a4c62d515dacdRaymond Hettinger def isdisjoint(self, other): 198cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger 'Return True if two sets have a null intersection.' 199abf3fcf39fb3bff4d347296a083a4c62d515dacdRaymond Hettinger for value in other: 200abf3fcf39fb3bff4d347296a083a4c62d515dacdRaymond Hettinger if value in self: 201abf3fcf39fb3bff4d347296a083a4c62d515dacdRaymond Hettinger return False 202abf3fcf39fb3bff4d347296a083a4c62d515dacdRaymond Hettinger return True 203abf3fcf39fb3bff4d347296a083a4c62d515dacdRaymond Hettinger 20464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __or__(self, other): 20564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum if not isinstance(other, Iterable): 20664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return NotImplemented 207972fb077a022722113e155ebf564f98ebdbe2b65Raymond Hettinger chain = (e for s in (self, other) for e in s) 208972fb077a022722113e155ebf564f98ebdbe2b65Raymond Hettinger return self._from_iterable(chain) 20964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 21064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __sub__(self, other): 21164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum if not isinstance(other, Set): 21264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum if not isinstance(other, Iterable): 21364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return NotImplemented 21464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum other = self._from_iterable(other) 21564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return self._from_iterable(value for value in self 21664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum if value not in other) 21764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 21864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __xor__(self, other): 21964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum if not isinstance(other, Set): 22064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum if not isinstance(other, Iterable): 22164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return NotImplemented 22264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum other = self._from_iterable(other) 22364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return (self - other) | (other - self) 22464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 22548361f5cbf419cce361fd1aa0389d6304ad167dbNick Coghlan # Sets are not hashable by default, but subclasses can change this 22648361f5cbf419cce361fd1aa0389d6304ad167dbNick Coghlan __hash__ = None 22748361f5cbf419cce361fd1aa0389d6304ad167dbNick Coghlan 22864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def _hash(self): 22964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum """Compute the hash value of a set. 23064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 23164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum Note that we don't define __hash__: not all sets are hashable. 23264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum But if you define a hashable set type, its __hash__ should 23364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum call this function. 23464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 23564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum This must be compatible __eq__. 23664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 23764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum All sets ought to compare equal if they contain the same 23864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum elements, regardless of how they are implemented, and 23964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum regardless of the order of the elements; so there's not much 24064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum freedom for __eq__ or __hash__. We match the algorithm used 24164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum by the built-in frozenset type. 24264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum """ 24364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum MAX = sys.maxint 24464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum MASK = 2 * MAX + 1 24564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum n = len(self) 24664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum h = 1927868237 * (n + 1) 24764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum h &= MASK 24864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum for x in self: 24964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum hx = hash(x) 25064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum h ^= (hx ^ (hx << 16) ^ 89869747) * 3644798167 25164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum h &= MASK 25264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum h = h * 69069 + 907133923 25364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum h &= MASK 25464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum if h > MAX: 25564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum h -= MASK + 1 25664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum if h == -1: 25764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum h = 590923713 25864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return h 25964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 26064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van RossumSet.register(frozenset) 26164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 26264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 26364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossumclass MutableSet(Set): 264cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger """A mutable set is a finite, iterable container. 265cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger 266cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger This class provides concrete generic implementations of all 267cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger methods except for __contains__, __iter__, __len__, 268cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger add(), and discard(). 269cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger 270cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger To override the comparisons (presumably for speed, as the 271cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger semantics are fixed), all you have to do is redefine __le__ and 272cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger then the other operations will automatically follow suit. 273cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger """ 27464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 27564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum @abstractmethod 27664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def add(self, value): 2772d21d50c10d1041f56d6f089d66a98b2bbf55e12Raymond Hettinger """Add an element.""" 27864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum raise NotImplementedError 27964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 28064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum @abstractmethod 28164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def discard(self, value): 2822d21d50c10d1041f56d6f089d66a98b2bbf55e12Raymond Hettinger """Remove an element. Do not raise an exception if absent.""" 28364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum raise NotImplementedError 28464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 2857d518f418b8bb7f155c8e695adbc5b69ac0ed0fdRaymond Hettinger def remove(self, value): 2867d518f418b8bb7f155c8e695adbc5b69ac0ed0fdRaymond Hettinger """Remove an element. If not a member, raise a KeyError.""" 2877d518f418b8bb7f155c8e695adbc5b69ac0ed0fdRaymond Hettinger if value not in self: 2887d518f418b8bb7f155c8e695adbc5b69ac0ed0fdRaymond Hettinger raise KeyError(value) 2897d518f418b8bb7f155c8e695adbc5b69ac0ed0fdRaymond Hettinger self.discard(value) 2907d518f418b8bb7f155c8e695adbc5b69ac0ed0fdRaymond Hettinger 29164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def pop(self): 29264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum """Return the popped value. Raise KeyError if empty.""" 29364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum it = iter(self) 29464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum try: 295f779e6f51bc9e96af8478d9463b1f10876fdc729Raymond Hettinger value = next(it) 29664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum except StopIteration: 29764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum raise KeyError 29864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum self.discard(value) 29964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return value 30064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 30164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def clear(self): 30264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum """This is slow (creates N new iterators!) but effective.""" 30364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum try: 30464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum while True: 30564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum self.pop() 30664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum except KeyError: 30764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum pass 30864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 30964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __ior__(self, it): 31064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum for value in it: 31164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum self.add(value) 31264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return self 31364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 31466c4a6b51cea40215e8f61e1abe2e3d89c4aeb1eRaymond Hettinger def __iand__(self, it): 31566c4a6b51cea40215e8f61e1abe2e3d89c4aeb1eRaymond Hettinger for value in (self - it): 31666c4a6b51cea40215e8f61e1abe2e3d89c4aeb1eRaymond Hettinger self.discard(value) 31764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return self 31864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 31964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __ixor__(self, it): 3209128732de668e5777e135a423d3fa8b9bbd71fe1Daniel Stutzbach if it is self: 3219128732de668e5777e135a423d3fa8b9bbd71fe1Daniel Stutzbach self.clear() 3229128732de668e5777e135a423d3fa8b9bbd71fe1Daniel Stutzbach else: 3239128732de668e5777e135a423d3fa8b9bbd71fe1Daniel Stutzbach if not isinstance(it, Set): 3249128732de668e5777e135a423d3fa8b9bbd71fe1Daniel Stutzbach it = self._from_iterable(it) 3259128732de668e5777e135a423d3fa8b9bbd71fe1Daniel Stutzbach for value in it: 3269128732de668e5777e135a423d3fa8b9bbd71fe1Daniel Stutzbach if value in self: 3279128732de668e5777e135a423d3fa8b9bbd71fe1Daniel Stutzbach self.discard(value) 3289128732de668e5777e135a423d3fa8b9bbd71fe1Daniel Stutzbach else: 3299128732de668e5777e135a423d3fa8b9bbd71fe1Daniel Stutzbach self.add(value) 330e973c61238807dcf4ccedc18a99db8f478c422c7Raymond Hettinger return self 33164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 33264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __isub__(self, it): 3339128732de668e5777e135a423d3fa8b9bbd71fe1Daniel Stutzbach if it is self: 3349128732de668e5777e135a423d3fa8b9bbd71fe1Daniel Stutzbach self.clear() 3359128732de668e5777e135a423d3fa8b9bbd71fe1Daniel Stutzbach else: 3369128732de668e5777e135a423d3fa8b9bbd71fe1Daniel Stutzbach for value in it: 3379128732de668e5777e135a423d3fa8b9bbd71fe1Daniel Stutzbach self.discard(value) 33864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return self 33964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 34064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van RossumMutableSet.register(set) 34164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 34264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 34364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum### MAPPINGS ### 34464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 34564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 346c2bc0d17e83ad88b829a669cc9ee7194b9e46593Raymond Hettingerclass Mapping(Sized, Iterable, Container): 34764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 348cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger """A Mapping is a generic container for associating key/value 349cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger pairs. 350cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger 351cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger This class provides concrete generic implementations of all 352cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger methods except for __getitem__, __iter__, and __len__. 353cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger 354cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger """ 355cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger 35664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum @abstractmethod 35764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __getitem__(self, key): 35864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum raise KeyError 35964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 36064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def get(self, key, default=None): 361cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger 'D.get(k[,d]) -> D[k] if k in D, else d. d defaults to None.' 36264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum try: 36364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return self[key] 36464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum except KeyError: 36564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return default 36664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 36764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __contains__(self, key): 36864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum try: 36964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum self[key] 37064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum except KeyError: 37164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return False 37264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum else: 37364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return True 37464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 37560fbf7f8bb83dd10a8d71ae763f845e688399fa0Georg Brandl def iterkeys(self): 376cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger 'D.iterkeys() -> an iterator over the keys of D' 37760fbf7f8bb83dd10a8d71ae763f845e688399fa0Georg Brandl return iter(self) 37860fbf7f8bb83dd10a8d71ae763f845e688399fa0Georg Brandl 37960fbf7f8bb83dd10a8d71ae763f845e688399fa0Georg Brandl def itervalues(self): 380cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger 'D.itervalues() -> an iterator over the values of D' 38160fbf7f8bb83dd10a8d71ae763f845e688399fa0Georg Brandl for key in self: 38260fbf7f8bb83dd10a8d71ae763f845e688399fa0Georg Brandl yield self[key] 38360fbf7f8bb83dd10a8d71ae763f845e688399fa0Georg Brandl 38460fbf7f8bb83dd10a8d71ae763f845e688399fa0Georg Brandl def iteritems(self): 385cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger 'D.iteritems() -> an iterator over the (key, value) items of D' 38660fbf7f8bb83dd10a8d71ae763f845e688399fa0Georg Brandl for key in self: 38760fbf7f8bb83dd10a8d71ae763f845e688399fa0Georg Brandl yield (key, self[key]) 38860fbf7f8bb83dd10a8d71ae763f845e688399fa0Georg Brandl 38964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def keys(self): 390cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger "D.keys() -> list of D's keys" 39160fbf7f8bb83dd10a8d71ae763f845e688399fa0Georg Brandl return list(self) 39264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 39364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def items(self): 394cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger "D.items() -> list of D's (key, value) pairs, as 2-tuples" 39560fbf7f8bb83dd10a8d71ae763f845e688399fa0Georg Brandl return [(key, self[key]) for key in self] 39664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 39764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def values(self): 398cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger "D.values() -> list of D's values" 39960fbf7f8bb83dd10a8d71ae763f845e688399fa0Georg Brandl return [self[key] for key in self] 40064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 40148361f5cbf419cce361fd1aa0389d6304ad167dbNick Coghlan # Mappings are not hashable by default, but subclasses can change this 40248361f5cbf419cce361fd1aa0389d6304ad167dbNick Coghlan __hash__ = None 40348361f5cbf419cce361fd1aa0389d6304ad167dbNick Coghlan 40445eda6469124855d349666184c6f92058a9e08f0Raymond Hettinger def __eq__(self, other): 405eb318d3b160a1631e462d1434e2ae9e1b5cfe158Benjamin Peterson if not isinstance(other, Mapping): 406eb318d3b160a1631e462d1434e2ae9e1b5cfe158Benjamin Peterson return NotImplemented 407eb318d3b160a1631e462d1434e2ae9e1b5cfe158Benjamin Peterson return dict(self.items()) == dict(other.items()) 40845eda6469124855d349666184c6f92058a9e08f0Raymond Hettinger 40945eda6469124855d349666184c6f92058a9e08f0Raymond Hettinger def __ne__(self, other): 41045eda6469124855d349666184c6f92058a9e08f0Raymond Hettinger return not (self == other) 41164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 412c2bc0d17e83ad88b829a669cc9ee7194b9e46593Raymond Hettingerclass MappingView(Sized): 41364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 41464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __init__(self, mapping): 41564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum self._mapping = mapping 41664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 41764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __len__(self): 41864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return len(self._mapping) 41964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 420b31a6d0949faecc933754f32ac956bc4aad76fffRaymond Hettinger def __repr__(self): 421b31a6d0949faecc933754f32ac956bc4aad76fffRaymond Hettinger return '{0.__class__.__name__}({0._mapping!r})'.format(self) 422b31a6d0949faecc933754f32ac956bc4aad76fffRaymond Hettinger 42364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 42464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossumclass KeysView(MappingView, Set): 42564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 426917bba1f2a382d5251b94eeadc344ec6ed3eaa97Raymond Hettinger @classmethod 427917bba1f2a382d5251b94eeadc344ec6ed3eaa97Raymond Hettinger def _from_iterable(self, it): 428917bba1f2a382d5251b94eeadc344ec6ed3eaa97Raymond Hettinger return set(it) 429917bba1f2a382d5251b94eeadc344ec6ed3eaa97Raymond Hettinger 43064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __contains__(self, key): 43164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return key in self._mapping 43264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 43364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __iter__(self): 43464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum for key in self._mapping: 43564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum yield key 43664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 43764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 43864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossumclass ItemsView(MappingView, Set): 43964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 440917bba1f2a382d5251b94eeadc344ec6ed3eaa97Raymond Hettinger @classmethod 441917bba1f2a382d5251b94eeadc344ec6ed3eaa97Raymond Hettinger def _from_iterable(self, it): 442917bba1f2a382d5251b94eeadc344ec6ed3eaa97Raymond Hettinger return set(it) 443917bba1f2a382d5251b94eeadc344ec6ed3eaa97Raymond Hettinger 44464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __contains__(self, item): 44564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum key, value = item 44664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum try: 44764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum v = self._mapping[key] 44864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum except KeyError: 44964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return False 45064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum else: 45164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return v == value 45264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 45364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __iter__(self): 45464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum for key in self._mapping: 45564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum yield (key, self._mapping[key]) 45664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 45764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 45864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossumclass ValuesView(MappingView): 45964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 46064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __contains__(self, value): 46164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum for key in self._mapping: 46264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum if value == self._mapping[key]: 46364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return True 46464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return False 46564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 46664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __iter__(self): 46764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum for key in self._mapping: 46864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum yield self._mapping[key] 46964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 47064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 47164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossumclass MutableMapping(Mapping): 47264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 473cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger """A MutableMapping is a generic container for associating 474cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger key/value pairs. 475cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger 476cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger This class provides concrete generic implementations of all 477cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger methods except for __getitem__, __setitem__, __delitem__, 478cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger __iter__, and __len__. 479cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger 480cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger """ 481cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger 48264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum @abstractmethod 48364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __setitem__(self, key, value): 48464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum raise KeyError 48564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 48664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum @abstractmethod 48764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __delitem__(self, key): 48864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum raise KeyError 48964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 49064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum __marker = object() 49164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 49264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def pop(self, key, default=__marker): 493cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger '''D.pop(k[,d]) -> v, remove specified key and return the corresponding value. 494cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger If key is not found, d is returned if given, otherwise KeyError is raised. 495cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger ''' 49664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum try: 49764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum value = self[key] 49864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum except KeyError: 49964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum if default is self.__marker: 50064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum raise 50164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return default 50264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum else: 50364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum del self[key] 50464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return value 50564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 50664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def popitem(self): 507cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger '''D.popitem() -> (k, v), remove and return some (key, value) pair 508cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger as a 2-tuple; but raise KeyError if D is empty. 509cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger ''' 51064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum try: 51164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum key = next(iter(self)) 51264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum except StopIteration: 51364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum raise KeyError 51464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum value = self[key] 51564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum del self[key] 51664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return key, value 51764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 51864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def clear(self): 519cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger 'D.clear() -> None. Remove all items from D.' 52064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum try: 52164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum while True: 52264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum self.popitem() 52364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum except KeyError: 52464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum pass 52564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 52642add99f77fbb4eb1af65213e1b4936397afe490Mark Dickinson def update(*args, **kwds): 527cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger ''' D.update([E, ]**F) -> None. Update D from mapping/iterable E and F. 528cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger If E present and has a .keys() method, does: for k in E: D[k] = E[k] 529cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger If E present and lacks .keys() method, does: for (k, v) in E: D[k] = v 530cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger In either case, this is followed by: for k, v in F.items(): D[k] = v 531cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger ''' 53242add99f77fbb4eb1af65213e1b4936397afe490Mark Dickinson if len(args) > 2: 53342add99f77fbb4eb1af65213e1b4936397afe490Mark Dickinson raise TypeError("update() takes at most 2 positional " 53442add99f77fbb4eb1af65213e1b4936397afe490Mark Dickinson "arguments ({} given)".format(len(args))) 53542add99f77fbb4eb1af65213e1b4936397afe490Mark Dickinson elif not args: 53642add99f77fbb4eb1af65213e1b4936397afe490Mark Dickinson raise TypeError("update() takes at least 1 argument (0 given)") 53742add99f77fbb4eb1af65213e1b4936397afe490Mark Dickinson self = args[0] 53842add99f77fbb4eb1af65213e1b4936397afe490Mark Dickinson other = args[1] if len(args) >= 2 else () 53942add99f77fbb4eb1af65213e1b4936397afe490Mark Dickinson 54064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum if isinstance(other, Mapping): 54164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum for key in other: 54264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum self[key] = other[key] 54364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum elif hasattr(other, "keys"): 54464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum for key in other.keys(): 54564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum self[key] = other[key] 54664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum else: 54764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum for key, value in other: 54864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum self[key] = value 54964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum for key, value in kwds.items(): 55064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum self[key] = value 55164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 55245eda6469124855d349666184c6f92058a9e08f0Raymond Hettinger def setdefault(self, key, default=None): 553cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger 'D.setdefault(k[,d]) -> D.get(k,d), also set D[k]=d if k not in D' 55445eda6469124855d349666184c6f92058a9e08f0Raymond Hettinger try: 55545eda6469124855d349666184c6f92058a9e08f0Raymond Hettinger return self[key] 55645eda6469124855d349666184c6f92058a9e08f0Raymond Hettinger except KeyError: 55745eda6469124855d349666184c6f92058a9e08f0Raymond Hettinger self[key] = default 55845eda6469124855d349666184c6f92058a9e08f0Raymond Hettinger return default 55945eda6469124855d349666184c6f92058a9e08f0Raymond Hettinger 56064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van RossumMutableMapping.register(dict) 56164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 56264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 56364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum### SEQUENCES ### 56464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 56564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 566c2bc0d17e83ad88b829a669cc9ee7194b9e46593Raymond Hettingerclass Sequence(Sized, Iterable, Container): 56764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum """All the operations on a read-only sequence. 56864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 56964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum Concrete subclasses must override __new__ or __init__, 57064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum __getitem__, and __len__. 57164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum """ 57264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 57364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum @abstractmethod 57464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __getitem__(self, index): 57564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum raise IndexError 57664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 57764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __iter__(self): 57864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum i = 0 57918a1ffcda373fad5f60c187217d7c2125bccf005Raymond Hettinger try: 58018a1ffcda373fad5f60c187217d7c2125bccf005Raymond Hettinger while True: 58164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum v = self[i] 58218a1ffcda373fad5f60c187217d7c2125bccf005Raymond Hettinger yield v 58318a1ffcda373fad5f60c187217d7c2125bccf005Raymond Hettinger i += 1 58418a1ffcda373fad5f60c187217d7c2125bccf005Raymond Hettinger except IndexError: 58518a1ffcda373fad5f60c187217d7c2125bccf005Raymond Hettinger return 58664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 58764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __contains__(self, value): 58864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum for v in self: 58964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum if v == value: 59064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return True 59164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return False 59264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 59364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __reversed__(self): 59464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum for i in reversed(range(len(self))): 59564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum yield self[i] 59664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 59764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def index(self, value): 598cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger '''S.index(value) -> integer -- return first index of value. 599cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger Raises ValueError if the value is not present. 600cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger ''' 60164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum for i, v in enumerate(self): 60264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum if v == value: 60364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return i 60464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum raise ValueError 60564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 60664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def count(self, value): 607cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger 'S.count(value) -> integer -- return number of occurrences of value' 60864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return sum(1 for v in self if v == value) 60964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 61064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van RossumSequence.register(tuple) 61164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van RossumSequence.register(basestring) 61264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van RossumSequence.register(buffer) 6138c56f8890eefdfd769d864aa901db5cf4586b4cdRaymond HettingerSequence.register(xrange) 61464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 61564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 61664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossumclass MutableSequence(Sequence): 61764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 618cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger """All the operations on a read-only sequence. 619cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger 620cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger Concrete subclasses must provide __new__ or __init__, 621cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger __getitem__, __setitem__, __delitem__, __len__, and insert(). 622cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger 623cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger """ 624cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger 62564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum @abstractmethod 62664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __setitem__(self, index, value): 62764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum raise IndexError 62864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 62964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum @abstractmethod 63064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __delitem__(self, index): 63164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum raise IndexError 63264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 63364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum @abstractmethod 63464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def insert(self, index, value): 635cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger 'S.insert(index, object) -- insert object before index' 63664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum raise IndexError 63764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 63864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def append(self, value): 639cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger 'S.append(object) -- append object to the end of the sequence' 64064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum self.insert(len(self), value) 64164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 64264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def reverse(self): 643cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger 'S.reverse() -- reverse *IN PLACE*' 64464c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum n = len(self) 64564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum for i in range(n//2): 64664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum self[i], self[n-i-1] = self[n-i-1], self[i] 64764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 64864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def extend(self, values): 649cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger 'S.extend(iterable) -- extend sequence by appending elements from the iterable' 65064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum for v in values: 65164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum self.append(v) 65264c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 65364c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def pop(self, index=-1): 654cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger '''S.pop([index]) -> item -- remove and return item at index (default last). 655cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger Raise IndexError if list is empty or index is out of range. 656cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger ''' 65764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum v = self[index] 65864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum del self[index] 65964c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum return v 66064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 66164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def remove(self, value): 662cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger '''S.remove(value) -- remove first occurrence of value. 663cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger Raise ValueError if the value is not present. 664cce5b04c75e1959a48cf41d210c9179ef3ce2e69Raymond Hettinger ''' 66564c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum del self[self.index(value)] 66664c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 66764c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum def __iadd__(self, values): 66864c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum self.extend(values) 669fceb5d478fcc43b764a9d1ad0a90e098828a7f64Raymond Hettinger return self 67064c06e327d48150fc548cf18a4a7ae0b890e69faGuido van Rossum 67164c06e327d48150fc548cf18a4a7ae0b890e69faGuido van RossumMutableSequence.register(list) 672