_collections_abc.py revision 02184282c7b6f68f905a08670b93862662bf4397
1cd16bf640405065e4702539632ce577536207d88Guido van Rossum# Copyright 2007 Google, Inc. All Rights Reserved. 2cd16bf640405065e4702539632ce577536207d88Guido van Rossum# Licensed to PSF under a Contributor Agreement. 3cd16bf640405065e4702539632ce577536207d88Guido van Rossum 4cd16bf640405065e4702539632ce577536207d88Guido van Rossum"""Abstract Base Classes (ABCs) for collections, according to PEP 3119. 5cd16bf640405065e4702539632ce577536207d88Guido van Rossum 6158c9c26fca16dee2f7a8d89707cf9c149bd04f2Raymond HettingerUnit tests are in test_collections. 7cd16bf640405065e4702539632ce577536207d88Guido van Rossum""" 8cd16bf640405065e4702539632ce577536207d88Guido van Rossum 9cd16bf640405065e4702539632ce577536207d88Guido van Rossumfrom abc import ABCMeta, abstractmethod 104118174315f4cba03208886af868fe31f1cd5b9dBenjamin Petersonimport sys 11cd16bf640405065e4702539632ce577536207d88Guido van Rossum 12cd16bf640405065e4702539632ce577536207d88Guido van Rossum__all__ = ["Hashable", "Iterable", "Iterator", 13cd16bf640405065e4702539632ce577536207d88Guido van Rossum "Sized", "Container", "Callable", 14cd16bf640405065e4702539632ce577536207d88Guido van Rossum "Set", "MutableSet", 15cd16bf640405065e4702539632ce577536207d88Guido van Rossum "Mapping", "MutableMapping", 16cd16bf640405065e4702539632ce577536207d88Guido van Rossum "MappingView", "KeysView", "ItemsView", "ValuesView", 17cd16bf640405065e4702539632ce577536207d88Guido van Rossum "Sequence", "MutableSequence", 18d05eb0043e597cf2d5c429d0e554fd39364e36b0Guido van Rossum "ByteString", 19cd16bf640405065e4702539632ce577536207d88Guido van Rossum ] 20cd16bf640405065e4702539632ce577536207d88Guido van Rossum 2102184282c7b6f68f905a08670b93862662bf4397Raymond Hettinger# Private list of types that we want to register with the various ABCs 2202184282c7b6f68f905a08670b93862662bf4397Raymond Hettinger# so that they will pass tests like: 2302184282c7b6f68f905a08670b93862662bf4397Raymond Hettinger# it = iter(somebytearray) 2402184282c7b6f68f905a08670b93862662bf4397Raymond Hettinger# assert isinstance(it, Iterable) 2502184282c7b6f68f905a08670b93862662bf4397Raymond Hettinger# Note: in other implementations, these types many not be distinct 2602184282c7b6f68f905a08670b93862662bf4397Raymond Hettinger# and they make have their own implementation specific types that 2702184282c7b6f68f905a08670b93862662bf4397Raymond Hettinger# are not included on this list. 28f83be4e3f353c4cfb53a22793dd1394797988c30Christian Heimesbytes_iterator = type(iter(b'')) 29f83be4e3f353c4cfb53a22793dd1394797988c30Christian Heimesbytearray_iterator = type(iter(bytearray())) 30f83be4e3f353c4cfb53a22793dd1394797988c30Christian Heimes#callable_iterator = ??? 31f83be4e3f353c4cfb53a22793dd1394797988c30Christian Heimesdict_keyiterator = type(iter({}.keys())) 32f83be4e3f353c4cfb53a22793dd1394797988c30Christian Heimesdict_valueiterator = type(iter({}.values())) 33f83be4e3f353c4cfb53a22793dd1394797988c30Christian Heimesdict_itemiterator = type(iter({}.items())) 34f83be4e3f353c4cfb53a22793dd1394797988c30Christian Heimeslist_iterator = type(iter([])) 35f83be4e3f353c4cfb53a22793dd1394797988c30Christian Heimeslist_reverseiterator = type(iter(reversed([]))) 36f83be4e3f353c4cfb53a22793dd1394797988c30Christian Heimesrange_iterator = type(iter(range(0))) 37f83be4e3f353c4cfb53a22793dd1394797988c30Christian Heimesset_iterator = type(iter(set())) 38f83be4e3f353c4cfb53a22793dd1394797988c30Christian Heimesstr_iterator = type(iter("")) 39f83be4e3f353c4cfb53a22793dd1394797988c30Christian Heimestuple_iterator = type(iter(())) 40f83be4e3f353c4cfb53a22793dd1394797988c30Christian Heimeszip_iterator = type(iter(zip())) 41f83be4e3f353c4cfb53a22793dd1394797988c30Christian Heimes## views ## 42f83be4e3f353c4cfb53a22793dd1394797988c30Christian Heimesdict_keys = type({}.keys()) 43f83be4e3f353c4cfb53a22793dd1394797988c30Christian Heimesdict_values = type({}.values()) 44f83be4e3f353c4cfb53a22793dd1394797988c30Christian Heimesdict_items = type({}.items()) 450db38532b304c89a998e4fc53b3ac8cd7ff23a8aChristian Heimes## misc ## 460db38532b304c89a998e4fc53b3ac8cd7ff23a8aChristian Heimesdict_proxy = type(type.__dict__) 47f83be4e3f353c4cfb53a22793dd1394797988c30Christian Heimes 48f83be4e3f353c4cfb53a22793dd1394797988c30Christian Heimes 49cd16bf640405065e4702539632ce577536207d88Guido van Rossum### ONE-TRICK PONIES ### 50cd16bf640405065e4702539632ce577536207d88Guido van Rossum 51cd16bf640405065e4702539632ce577536207d88Guido van Rossumclass Hashable(metaclass=ABCMeta): 52cd16bf640405065e4702539632ce577536207d88Guido van Rossum 53c46759ad0b3419bb67b33f0358af5ae50dc0c5feRaymond Hettinger __slots__ = () 54c46759ad0b3419bb67b33f0358af5ae50dc0c5feRaymond Hettinger 55cd16bf640405065e4702539632ce577536207d88Guido van Rossum @abstractmethod 56cd16bf640405065e4702539632ce577536207d88Guido van Rossum def __hash__(self): 57cd16bf640405065e4702539632ce577536207d88Guido van Rossum return 0 58cd16bf640405065e4702539632ce577536207d88Guido van Rossum 59cd16bf640405065e4702539632ce577536207d88Guido van Rossum @classmethod 60cd16bf640405065e4702539632ce577536207d88Guido van Rossum def __subclasshook__(cls, C): 61cd16bf640405065e4702539632ce577536207d88Guido van Rossum if cls is Hashable: 62cd16bf640405065e4702539632ce577536207d88Guido van Rossum for B in C.__mro__: 63cd16bf640405065e4702539632ce577536207d88Guido van Rossum if "__hash__" in B.__dict__: 64cd16bf640405065e4702539632ce577536207d88Guido van Rossum if B.__dict__["__hash__"]: 65cd16bf640405065e4702539632ce577536207d88Guido van Rossum return True 66cd16bf640405065e4702539632ce577536207d88Guido van Rossum break 67cd16bf640405065e4702539632ce577536207d88Guido van Rossum return NotImplemented 68cd16bf640405065e4702539632ce577536207d88Guido van Rossum 69cd16bf640405065e4702539632ce577536207d88Guido van Rossum 70cd16bf640405065e4702539632ce577536207d88Guido van Rossumclass Iterable(metaclass=ABCMeta): 71cd16bf640405065e4702539632ce577536207d88Guido van Rossum 72c46759ad0b3419bb67b33f0358af5ae50dc0c5feRaymond Hettinger __slots__ = () 73c46759ad0b3419bb67b33f0358af5ae50dc0c5feRaymond Hettinger 74cd16bf640405065e4702539632ce577536207d88Guido van Rossum @abstractmethod 75cd16bf640405065e4702539632ce577536207d88Guido van Rossum def __iter__(self): 76cd16bf640405065e4702539632ce577536207d88Guido van Rossum while False: 77cd16bf640405065e4702539632ce577536207d88Guido van Rossum yield None 78cd16bf640405065e4702539632ce577536207d88Guido van Rossum 79cd16bf640405065e4702539632ce577536207d88Guido van Rossum @classmethod 80cd16bf640405065e4702539632ce577536207d88Guido van Rossum def __subclasshook__(cls, C): 81cd16bf640405065e4702539632ce577536207d88Guido van Rossum if cls is Iterable: 82cd16bf640405065e4702539632ce577536207d88Guido van Rossum if any("__iter__" in B.__dict__ for B in C.__mro__): 83cd16bf640405065e4702539632ce577536207d88Guido van Rossum return True 84cd16bf640405065e4702539632ce577536207d88Guido van Rossum return NotImplemented 85cd16bf640405065e4702539632ce577536207d88Guido van Rossum 86cd16bf640405065e4702539632ce577536207d88Guido van Rossum 8774b6495b344303a84bf5e51ff388d8200dad4f64Raymond Hettingerclass Iterator(Iterable): 88cd16bf640405065e4702539632ce577536207d88Guido van Rossum 89c46759ad0b3419bb67b33f0358af5ae50dc0c5feRaymond Hettinger __slots__ = () 90c46759ad0b3419bb67b33f0358af5ae50dc0c5feRaymond Hettinger 91cd16bf640405065e4702539632ce577536207d88Guido van Rossum @abstractmethod 92cd16bf640405065e4702539632ce577536207d88Guido van Rossum def __next__(self): 93cd16bf640405065e4702539632ce577536207d88Guido van Rossum raise StopIteration 94cd16bf640405065e4702539632ce577536207d88Guido van Rossum 95cd16bf640405065e4702539632ce577536207d88Guido van Rossum def __iter__(self): 96cd16bf640405065e4702539632ce577536207d88Guido van Rossum return self 97cd16bf640405065e4702539632ce577536207d88Guido van Rossum 98cd16bf640405065e4702539632ce577536207d88Guido van Rossum @classmethod 99cd16bf640405065e4702539632ce577536207d88Guido van Rossum def __subclasshook__(cls, C): 100cd16bf640405065e4702539632ce577536207d88Guido van Rossum if cls is Iterator: 101ead22227cce112457b6beba8b008699ea4a3a084Raymond Hettinger if (any("__next__" in B.__dict__ for B in C.__mro__) and 102ead22227cce112457b6beba8b008699ea4a3a084Raymond Hettinger any("__iter__" in B.__dict__ for B in C.__mro__)): 103cd16bf640405065e4702539632ce577536207d88Guido van Rossum return True 104cd16bf640405065e4702539632ce577536207d88Guido van Rossum return NotImplemented 105cd16bf640405065e4702539632ce577536207d88Guido van Rossum 106f83be4e3f353c4cfb53a22793dd1394797988c30Christian HeimesIterator.register(bytes_iterator) 107f83be4e3f353c4cfb53a22793dd1394797988c30Christian HeimesIterator.register(bytearray_iterator) 108f83be4e3f353c4cfb53a22793dd1394797988c30Christian Heimes#Iterator.register(callable_iterator) 109f83be4e3f353c4cfb53a22793dd1394797988c30Christian HeimesIterator.register(dict_keyiterator) 110f83be4e3f353c4cfb53a22793dd1394797988c30Christian HeimesIterator.register(dict_valueiterator) 111f83be4e3f353c4cfb53a22793dd1394797988c30Christian HeimesIterator.register(dict_itemiterator) 112f83be4e3f353c4cfb53a22793dd1394797988c30Christian HeimesIterator.register(list_iterator) 113f83be4e3f353c4cfb53a22793dd1394797988c30Christian HeimesIterator.register(list_reverseiterator) 114f83be4e3f353c4cfb53a22793dd1394797988c30Christian HeimesIterator.register(range_iterator) 115f83be4e3f353c4cfb53a22793dd1394797988c30Christian HeimesIterator.register(set_iterator) 116f83be4e3f353c4cfb53a22793dd1394797988c30Christian HeimesIterator.register(str_iterator) 117f83be4e3f353c4cfb53a22793dd1394797988c30Christian HeimesIterator.register(tuple_iterator) 118f83be4e3f353c4cfb53a22793dd1394797988c30Christian HeimesIterator.register(zip_iterator) 119cd16bf640405065e4702539632ce577536207d88Guido van Rossum 120cd16bf640405065e4702539632ce577536207d88Guido van Rossumclass Sized(metaclass=ABCMeta): 121cd16bf640405065e4702539632ce577536207d88Guido van Rossum 122c46759ad0b3419bb67b33f0358af5ae50dc0c5feRaymond Hettinger __slots__ = () 123c46759ad0b3419bb67b33f0358af5ae50dc0c5feRaymond Hettinger 124cd16bf640405065e4702539632ce577536207d88Guido van Rossum @abstractmethod 125cd16bf640405065e4702539632ce577536207d88Guido van Rossum def __len__(self): 126cd16bf640405065e4702539632ce577536207d88Guido van Rossum return 0 127cd16bf640405065e4702539632ce577536207d88Guido van Rossum 128cd16bf640405065e4702539632ce577536207d88Guido van Rossum @classmethod 129cd16bf640405065e4702539632ce577536207d88Guido van Rossum def __subclasshook__(cls, C): 130cd16bf640405065e4702539632ce577536207d88Guido van Rossum if cls is Sized: 131cd16bf640405065e4702539632ce577536207d88Guido van Rossum if any("__len__" in B.__dict__ for B in C.__mro__): 132cd16bf640405065e4702539632ce577536207d88Guido van Rossum return True 133cd16bf640405065e4702539632ce577536207d88Guido van Rossum return NotImplemented 134cd16bf640405065e4702539632ce577536207d88Guido van Rossum 135cd16bf640405065e4702539632ce577536207d88Guido van Rossum 136cd16bf640405065e4702539632ce577536207d88Guido van Rossumclass Container(metaclass=ABCMeta): 137cd16bf640405065e4702539632ce577536207d88Guido van Rossum 138c46759ad0b3419bb67b33f0358af5ae50dc0c5feRaymond Hettinger __slots__ = () 139c46759ad0b3419bb67b33f0358af5ae50dc0c5feRaymond Hettinger 140cd16bf640405065e4702539632ce577536207d88Guido van Rossum @abstractmethod 141cd16bf640405065e4702539632ce577536207d88Guido van Rossum def __contains__(self, x): 142cd16bf640405065e4702539632ce577536207d88Guido van Rossum return False 143cd16bf640405065e4702539632ce577536207d88Guido van Rossum 144cd16bf640405065e4702539632ce577536207d88Guido van Rossum @classmethod 145cd16bf640405065e4702539632ce577536207d88Guido van Rossum def __subclasshook__(cls, C): 146cd16bf640405065e4702539632ce577536207d88Guido van Rossum if cls is Container: 147cd16bf640405065e4702539632ce577536207d88Guido van Rossum if any("__contains__" in B.__dict__ for B in C.__mro__): 148cd16bf640405065e4702539632ce577536207d88Guido van Rossum return True 149cd16bf640405065e4702539632ce577536207d88Guido van Rossum return NotImplemented 150cd16bf640405065e4702539632ce577536207d88Guido van Rossum 151cd16bf640405065e4702539632ce577536207d88Guido van Rossum 152cd16bf640405065e4702539632ce577536207d88Guido van Rossumclass Callable(metaclass=ABCMeta): 153cd16bf640405065e4702539632ce577536207d88Guido van Rossum 154c46759ad0b3419bb67b33f0358af5ae50dc0c5feRaymond Hettinger __slots__ = () 155c46759ad0b3419bb67b33f0358af5ae50dc0c5feRaymond Hettinger 156cd16bf640405065e4702539632ce577536207d88Guido van Rossum @abstractmethod 1577864476afa402a0537c33ba9630e77351720baf8Christian Heimes def __call__(self, *args, **kwds): 158cd16bf640405065e4702539632ce577536207d88Guido van Rossum return False 159cd16bf640405065e4702539632ce577536207d88Guido van Rossum 160cd16bf640405065e4702539632ce577536207d88Guido van Rossum @classmethod 161cd16bf640405065e4702539632ce577536207d88Guido van Rossum def __subclasshook__(cls, C): 162cd16bf640405065e4702539632ce577536207d88Guido van Rossum if cls is Callable: 163cd16bf640405065e4702539632ce577536207d88Guido van Rossum if any("__call__" in B.__dict__ for B in C.__mro__): 164cd16bf640405065e4702539632ce577536207d88Guido van Rossum return True 165cd16bf640405065e4702539632ce577536207d88Guido van Rossum return NotImplemented 166cd16bf640405065e4702539632ce577536207d88Guido van Rossum 167cd16bf640405065e4702539632ce577536207d88Guido van Rossum 168cd16bf640405065e4702539632ce577536207d88Guido van Rossum### SETS ### 169cd16bf640405065e4702539632ce577536207d88Guido van Rossum 170cd16bf640405065e4702539632ce577536207d88Guido van Rossum 17174b6495b344303a84bf5e51ff388d8200dad4f64Raymond Hettingerclass Set(Sized, Iterable, Container): 172cd16bf640405065e4702539632ce577536207d88Guido van Rossum 173cd16bf640405065e4702539632ce577536207d88Guido van Rossum """A set is a finite, iterable container. 174cd16bf640405065e4702539632ce577536207d88Guido van Rossum 175cd16bf640405065e4702539632ce577536207d88Guido van Rossum This class provides concrete generic implementations of all 176cd16bf640405065e4702539632ce577536207d88Guido van Rossum methods except for __contains__, __iter__ and __len__. 177cd16bf640405065e4702539632ce577536207d88Guido van Rossum 178cd16bf640405065e4702539632ce577536207d88Guido van Rossum To override the comparisons (presumably for speed, as the 179cd16bf640405065e4702539632ce577536207d88Guido van Rossum semantics are fixed), all you have to do is redefine __le__ and 180cd16bf640405065e4702539632ce577536207d88Guido van Rossum then the other operations will automatically follow suit. 181cd16bf640405065e4702539632ce577536207d88Guido van Rossum """ 182cd16bf640405065e4702539632ce577536207d88Guido van Rossum 183c46759ad0b3419bb67b33f0358af5ae50dc0c5feRaymond Hettinger __slots__ = () 184c46759ad0b3419bb67b33f0358af5ae50dc0c5feRaymond Hettinger 185cd16bf640405065e4702539632ce577536207d88Guido van Rossum def __le__(self, other): 186cd16bf640405065e4702539632ce577536207d88Guido van Rossum if not isinstance(other, Set): 187cd16bf640405065e4702539632ce577536207d88Guido van Rossum return NotImplemented 188cd16bf640405065e4702539632ce577536207d88Guido van Rossum if len(self) > len(other): 189cd16bf640405065e4702539632ce577536207d88Guido van Rossum return False 190cd16bf640405065e4702539632ce577536207d88Guido van Rossum for elem in self: 191cd16bf640405065e4702539632ce577536207d88Guido van Rossum if elem not in other: 192cd16bf640405065e4702539632ce577536207d88Guido van Rossum return False 193cd16bf640405065e4702539632ce577536207d88Guido van Rossum return True 194cd16bf640405065e4702539632ce577536207d88Guido van Rossum 195cd16bf640405065e4702539632ce577536207d88Guido van Rossum def __lt__(self, other): 196cd16bf640405065e4702539632ce577536207d88Guido van Rossum if not isinstance(other, Set): 197cd16bf640405065e4702539632ce577536207d88Guido van Rossum return NotImplemented 198cd16bf640405065e4702539632ce577536207d88Guido van Rossum return len(self) < len(other) and self.__le__(other) 199cd16bf640405065e4702539632ce577536207d88Guido van Rossum 20071909423fd92862b869d8019d5e10c29bf946cb0Raymond Hettinger def __gt__(self, other): 20171909423fd92862b869d8019d5e10c29bf946cb0Raymond Hettinger if not isinstance(other, Set): 20271909423fd92862b869d8019d5e10c29bf946cb0Raymond Hettinger return NotImplemented 20371909423fd92862b869d8019d5e10c29bf946cb0Raymond Hettinger return other < self 20471909423fd92862b869d8019d5e10c29bf946cb0Raymond Hettinger 20571909423fd92862b869d8019d5e10c29bf946cb0Raymond Hettinger def __ge__(self, other): 20671909423fd92862b869d8019d5e10c29bf946cb0Raymond Hettinger if not isinstance(other, Set): 20771909423fd92862b869d8019d5e10c29bf946cb0Raymond Hettinger return NotImplemented 20871909423fd92862b869d8019d5e10c29bf946cb0Raymond Hettinger return other <= self 20971909423fd92862b869d8019d5e10c29bf946cb0Raymond Hettinger 210cd16bf640405065e4702539632ce577536207d88Guido van Rossum def __eq__(self, other): 211cd16bf640405065e4702539632ce577536207d88Guido van Rossum if not isinstance(other, Set): 212cd16bf640405065e4702539632ce577536207d88Guido van Rossum return NotImplemented 213cd16bf640405065e4702539632ce577536207d88Guido van Rossum return len(self) == len(other) and self.__le__(other) 214cd16bf640405065e4702539632ce577536207d88Guido van Rossum 21571909423fd92862b869d8019d5e10c29bf946cb0Raymond Hettinger def __ne__(self, other): 21671909423fd92862b869d8019d5e10c29bf946cb0Raymond Hettinger return not (self == other) 21771909423fd92862b869d8019d5e10c29bf946cb0Raymond Hettinger 218cd16bf640405065e4702539632ce577536207d88Guido van Rossum @classmethod 219cd16bf640405065e4702539632ce577536207d88Guido van Rossum def _from_iterable(cls, it): 2208284c4a7fb27efd55323513572e247a895a35ae1Raymond Hettinger '''Construct an instance of the class from any iterable input. 2218284c4a7fb27efd55323513572e247a895a35ae1Raymond Hettinger 2228284c4a7fb27efd55323513572e247a895a35ae1Raymond Hettinger Must override this method if the class constructor signature 2237aebb64bab2ef75c6d9ae55da9ae7049f05c8670Raymond Hettinger does not accept an iterable for an input. 2248284c4a7fb27efd55323513572e247a895a35ae1Raymond Hettinger ''' 2257aebb64bab2ef75c6d9ae55da9ae7049f05c8670Raymond Hettinger return cls(it) 226cd16bf640405065e4702539632ce577536207d88Guido van Rossum 227cd16bf640405065e4702539632ce577536207d88Guido van Rossum def __and__(self, other): 228cd16bf640405065e4702539632ce577536207d88Guido van Rossum if not isinstance(other, Iterable): 229cd16bf640405065e4702539632ce577536207d88Guido van Rossum return NotImplemented 230cd16bf640405065e4702539632ce577536207d88Guido van Rossum return self._from_iterable(value for value in other if value in self) 231cd16bf640405065e4702539632ce577536207d88Guido van Rossum 232190d79e5c648174b550de2bef75d1b4addf0d625Christian Heimes def isdisjoint(self, other): 233190d79e5c648174b550de2bef75d1b4addf0d625Christian Heimes for value in other: 234190d79e5c648174b550de2bef75d1b4addf0d625Christian Heimes if value in self: 235190d79e5c648174b550de2bef75d1b4addf0d625Christian Heimes return False 236190d79e5c648174b550de2bef75d1b4addf0d625Christian Heimes return True 237190d79e5c648174b550de2bef75d1b4addf0d625Christian Heimes 238cd16bf640405065e4702539632ce577536207d88Guido van Rossum def __or__(self, other): 239cd16bf640405065e4702539632ce577536207d88Guido van Rossum if not isinstance(other, Iterable): 240cd16bf640405065e4702539632ce577536207d88Guido van Rossum return NotImplemented 2417864476afa402a0537c33ba9630e77351720baf8Christian Heimes chain = (e for s in (self, other) for e in s) 2427864476afa402a0537c33ba9630e77351720baf8Christian Heimes return self._from_iterable(chain) 243cd16bf640405065e4702539632ce577536207d88Guido van Rossum 244cd16bf640405065e4702539632ce577536207d88Guido van Rossum def __sub__(self, other): 245cd16bf640405065e4702539632ce577536207d88Guido van Rossum if not isinstance(other, Set): 246cd16bf640405065e4702539632ce577536207d88Guido van Rossum if not isinstance(other, Iterable): 247cd16bf640405065e4702539632ce577536207d88Guido van Rossum return NotImplemented 248cd16bf640405065e4702539632ce577536207d88Guido van Rossum other = self._from_iterable(other) 249cd16bf640405065e4702539632ce577536207d88Guido van Rossum return self._from_iterable(value for value in self 250cd16bf640405065e4702539632ce577536207d88Guido van Rossum if value not in other) 251cd16bf640405065e4702539632ce577536207d88Guido van Rossum 252cd16bf640405065e4702539632ce577536207d88Guido van Rossum def __xor__(self, other): 253cd16bf640405065e4702539632ce577536207d88Guido van Rossum if not isinstance(other, Set): 254cd16bf640405065e4702539632ce577536207d88Guido van Rossum if not isinstance(other, Iterable): 255cd16bf640405065e4702539632ce577536207d88Guido van Rossum return NotImplemented 256cd16bf640405065e4702539632ce577536207d88Guido van Rossum other = self._from_iterable(other) 257cd16bf640405065e4702539632ce577536207d88Guido van Rossum return (self - other) | (other - self) 258cd16bf640405065e4702539632ce577536207d88Guido van Rossum 259cd16bf640405065e4702539632ce577536207d88Guido van Rossum def _hash(self): 260cd16bf640405065e4702539632ce577536207d88Guido van Rossum """Compute the hash value of a set. 261cd16bf640405065e4702539632ce577536207d88Guido van Rossum 262cd16bf640405065e4702539632ce577536207d88Guido van Rossum Note that we don't define __hash__: not all sets are hashable. 263cd16bf640405065e4702539632ce577536207d88Guido van Rossum But if you define a hashable set type, its __hash__ should 264cd16bf640405065e4702539632ce577536207d88Guido van Rossum call this function. 265cd16bf640405065e4702539632ce577536207d88Guido van Rossum 266cd16bf640405065e4702539632ce577536207d88Guido van Rossum This must be compatible __eq__. 267cd16bf640405065e4702539632ce577536207d88Guido van Rossum 268cd16bf640405065e4702539632ce577536207d88Guido van Rossum All sets ought to compare equal if they contain the same 269cd16bf640405065e4702539632ce577536207d88Guido van Rossum elements, regardless of how they are implemented, and 270cd16bf640405065e4702539632ce577536207d88Guido van Rossum regardless of the order of the elements; so there's not much 271cd16bf640405065e4702539632ce577536207d88Guido van Rossum freedom for __eq__ or __hash__. We match the algorithm used 272cd16bf640405065e4702539632ce577536207d88Guido van Rossum by the built-in frozenset type. 273cd16bf640405065e4702539632ce577536207d88Guido van Rossum """ 274a37d4c693a024154093b36a612810c3bd72d9254Christian Heimes MAX = sys.maxsize 275cd16bf640405065e4702539632ce577536207d88Guido van Rossum MASK = 2 * MAX + 1 276cd16bf640405065e4702539632ce577536207d88Guido van Rossum n = len(self) 277cd16bf640405065e4702539632ce577536207d88Guido van Rossum h = 1927868237 * (n + 1) 278cd16bf640405065e4702539632ce577536207d88Guido van Rossum h &= MASK 279cd16bf640405065e4702539632ce577536207d88Guido van Rossum for x in self: 280cd16bf640405065e4702539632ce577536207d88Guido van Rossum hx = hash(x) 281cd16bf640405065e4702539632ce577536207d88Guido van Rossum h ^= (hx ^ (hx << 16) ^ 89869747) * 3644798167 282cd16bf640405065e4702539632ce577536207d88Guido van Rossum h &= MASK 283cd16bf640405065e4702539632ce577536207d88Guido van Rossum h = h * 69069 + 907133923 284cd16bf640405065e4702539632ce577536207d88Guido van Rossum h &= MASK 285cd16bf640405065e4702539632ce577536207d88Guido van Rossum if h > MAX: 286cd16bf640405065e4702539632ce577536207d88Guido van Rossum h -= MASK + 1 287cd16bf640405065e4702539632ce577536207d88Guido van Rossum if h == -1: 288cd16bf640405065e4702539632ce577536207d88Guido van Rossum h = 590923713 289cd16bf640405065e4702539632ce577536207d88Guido van Rossum return h 290cd16bf640405065e4702539632ce577536207d88Guido van Rossum 291cd16bf640405065e4702539632ce577536207d88Guido van RossumSet.register(frozenset) 292cd16bf640405065e4702539632ce577536207d88Guido van Rossum 293cd16bf640405065e4702539632ce577536207d88Guido van Rossum 294cd16bf640405065e4702539632ce577536207d88Guido van Rossumclass MutableSet(Set): 295cd16bf640405065e4702539632ce577536207d88Guido van Rossum 296c46759ad0b3419bb67b33f0358af5ae50dc0c5feRaymond Hettinger __slots__ = () 297c46759ad0b3419bb67b33f0358af5ae50dc0c5feRaymond Hettinger 298cd16bf640405065e4702539632ce577536207d88Guido van Rossum @abstractmethod 299cd16bf640405065e4702539632ce577536207d88Guido van Rossum def add(self, value): 300058e31ef2aec3ea079cdf297fc0d4f40d3d9975aBenjamin Peterson """Add an element.""" 301cd16bf640405065e4702539632ce577536207d88Guido van Rossum raise NotImplementedError 302cd16bf640405065e4702539632ce577536207d88Guido van Rossum 303cd16bf640405065e4702539632ce577536207d88Guido van Rossum @abstractmethod 304cd16bf640405065e4702539632ce577536207d88Guido van Rossum def discard(self, value): 305058e31ef2aec3ea079cdf297fc0d4f40d3d9975aBenjamin Peterson """Remove an element. Do not raise an exception if absent.""" 306cd16bf640405065e4702539632ce577536207d88Guido van Rossum raise NotImplementedError 307cd16bf640405065e4702539632ce577536207d88Guido van Rossum 308190d79e5c648174b550de2bef75d1b4addf0d625Christian Heimes def remove(self, value): 309190d79e5c648174b550de2bef75d1b4addf0d625Christian Heimes """Remove an element. If not a member, raise a KeyError.""" 310190d79e5c648174b550de2bef75d1b4addf0d625Christian Heimes if value not in self: 311190d79e5c648174b550de2bef75d1b4addf0d625Christian Heimes raise KeyError(value) 312190d79e5c648174b550de2bef75d1b4addf0d625Christian Heimes self.discard(value) 313190d79e5c648174b550de2bef75d1b4addf0d625Christian Heimes 314cd16bf640405065e4702539632ce577536207d88Guido van Rossum def pop(self): 315cd16bf640405065e4702539632ce577536207d88Guido van Rossum """Return the popped value. Raise KeyError if empty.""" 316cd16bf640405065e4702539632ce577536207d88Guido van Rossum it = iter(self) 317cd16bf640405065e4702539632ce577536207d88Guido van Rossum try: 318ae650181b89feeb1f68fb7643d190df52d13bd9eRaymond Hettinger value = next(it) 319cd16bf640405065e4702539632ce577536207d88Guido van Rossum except StopIteration: 320cd16bf640405065e4702539632ce577536207d88Guido van Rossum raise KeyError 321cd16bf640405065e4702539632ce577536207d88Guido van Rossum self.discard(value) 322cd16bf640405065e4702539632ce577536207d88Guido van Rossum return value 323cd16bf640405065e4702539632ce577536207d88Guido van Rossum 324cd16bf640405065e4702539632ce577536207d88Guido van Rossum def clear(self): 325cd16bf640405065e4702539632ce577536207d88Guido van Rossum """This is slow (creates N new iterators!) but effective.""" 326cd16bf640405065e4702539632ce577536207d88Guido van Rossum try: 327cd16bf640405065e4702539632ce577536207d88Guido van Rossum while True: 328cd16bf640405065e4702539632ce577536207d88Guido van Rossum self.pop() 329cd16bf640405065e4702539632ce577536207d88Guido van Rossum except KeyError: 330cd16bf640405065e4702539632ce577536207d88Guido van Rossum pass 331cd16bf640405065e4702539632ce577536207d88Guido van Rossum 332b3d89a4ee438ee6927bfe553694b5b06f5672274Raymond Hettinger def __ior__(self, it): 333cd16bf640405065e4702539632ce577536207d88Guido van Rossum for value in it: 334cd16bf640405065e4702539632ce577536207d88Guido van Rossum self.add(value) 335cd16bf640405065e4702539632ce577536207d88Guido van Rossum return self 336cd16bf640405065e4702539632ce577536207d88Guido van Rossum 337b3d89a4ee438ee6927bfe553694b5b06f5672274Raymond Hettinger def __iand__(self, it): 3383f10a952f6056b6797e4187bcfa1a97c21d1b3bbRaymond Hettinger for value in (self - it): 3393f10a952f6056b6797e4187bcfa1a97c21d1b3bbRaymond Hettinger self.discard(value) 340cd16bf640405065e4702539632ce577536207d88Guido van Rossum return self 341cd16bf640405065e4702539632ce577536207d88Guido van Rossum 342b3d89a4ee438ee6927bfe553694b5b06f5672274Raymond Hettinger def __ixor__(self, it): 34331da5b2f69d408ac2448eb04ee2892b8aa3aac79Daniel Stutzbach if it is self: 34431da5b2f69d408ac2448eb04ee2892b8aa3aac79Daniel Stutzbach self.clear() 34531da5b2f69d408ac2448eb04ee2892b8aa3aac79Daniel Stutzbach else: 34631da5b2f69d408ac2448eb04ee2892b8aa3aac79Daniel Stutzbach if not isinstance(it, Set): 34731da5b2f69d408ac2448eb04ee2892b8aa3aac79Daniel Stutzbach it = self._from_iterable(it) 34831da5b2f69d408ac2448eb04ee2892b8aa3aac79Daniel Stutzbach for value in it: 34931da5b2f69d408ac2448eb04ee2892b8aa3aac79Daniel Stutzbach if value in self: 35031da5b2f69d408ac2448eb04ee2892b8aa3aac79Daniel Stutzbach self.discard(value) 35131da5b2f69d408ac2448eb04ee2892b8aa3aac79Daniel Stutzbach else: 35231da5b2f69d408ac2448eb04ee2892b8aa3aac79Daniel Stutzbach self.add(value) 353cd16bf640405065e4702539632ce577536207d88Guido van Rossum return self 354cd16bf640405065e4702539632ce577536207d88Guido van Rossum 355b3d89a4ee438ee6927bfe553694b5b06f5672274Raymond Hettinger def __isub__(self, it): 35631da5b2f69d408ac2448eb04ee2892b8aa3aac79Daniel Stutzbach if it is self: 35731da5b2f69d408ac2448eb04ee2892b8aa3aac79Daniel Stutzbach self.clear() 35831da5b2f69d408ac2448eb04ee2892b8aa3aac79Daniel Stutzbach else: 35931da5b2f69d408ac2448eb04ee2892b8aa3aac79Daniel Stutzbach for value in it: 36031da5b2f69d408ac2448eb04ee2892b8aa3aac79Daniel Stutzbach self.discard(value) 361cd16bf640405065e4702539632ce577536207d88Guido van Rossum return self 362cd16bf640405065e4702539632ce577536207d88Guido van Rossum 363cd16bf640405065e4702539632ce577536207d88Guido van RossumMutableSet.register(set) 364cd16bf640405065e4702539632ce577536207d88Guido van Rossum 365cd16bf640405065e4702539632ce577536207d88Guido van Rossum 366cd16bf640405065e4702539632ce577536207d88Guido van Rossum### MAPPINGS ### 367cd16bf640405065e4702539632ce577536207d88Guido van Rossum 368cd16bf640405065e4702539632ce577536207d88Guido van Rossum 36974b6495b344303a84bf5e51ff388d8200dad4f64Raymond Hettingerclass Mapping(Sized, Iterable, Container): 370cd16bf640405065e4702539632ce577536207d88Guido van Rossum 371c46759ad0b3419bb67b33f0358af5ae50dc0c5feRaymond Hettinger __slots__ = () 372c46759ad0b3419bb67b33f0358af5ae50dc0c5feRaymond Hettinger 373cd16bf640405065e4702539632ce577536207d88Guido van Rossum @abstractmethod 374cd16bf640405065e4702539632ce577536207d88Guido van Rossum def __getitem__(self, key): 375cd16bf640405065e4702539632ce577536207d88Guido van Rossum raise KeyError 376cd16bf640405065e4702539632ce577536207d88Guido van Rossum 377cd16bf640405065e4702539632ce577536207d88Guido van Rossum def get(self, key, default=None): 378cd16bf640405065e4702539632ce577536207d88Guido van Rossum try: 379cd16bf640405065e4702539632ce577536207d88Guido van Rossum return self[key] 380cd16bf640405065e4702539632ce577536207d88Guido van Rossum except KeyError: 381cd16bf640405065e4702539632ce577536207d88Guido van Rossum return default 382cd16bf640405065e4702539632ce577536207d88Guido van Rossum 383cd16bf640405065e4702539632ce577536207d88Guido van Rossum def __contains__(self, key): 384cd16bf640405065e4702539632ce577536207d88Guido van Rossum try: 385cd16bf640405065e4702539632ce577536207d88Guido van Rossum self[key] 386cd16bf640405065e4702539632ce577536207d88Guido van Rossum except KeyError: 387cd16bf640405065e4702539632ce577536207d88Guido van Rossum return False 388cd16bf640405065e4702539632ce577536207d88Guido van Rossum else: 389cd16bf640405065e4702539632ce577536207d88Guido van Rossum return True 390cd16bf640405065e4702539632ce577536207d88Guido van Rossum 391cd16bf640405065e4702539632ce577536207d88Guido van Rossum def keys(self): 392cd16bf640405065e4702539632ce577536207d88Guido van Rossum return KeysView(self) 393cd16bf640405065e4702539632ce577536207d88Guido van Rossum 394cd16bf640405065e4702539632ce577536207d88Guido van Rossum def items(self): 395cd16bf640405065e4702539632ce577536207d88Guido van Rossum return ItemsView(self) 396cd16bf640405065e4702539632ce577536207d88Guido van Rossum 397cd16bf640405065e4702539632ce577536207d88Guido van Rossum def values(self): 398cd16bf640405065e4702539632ce577536207d88Guido van Rossum return ValuesView(self) 399cd16bf640405065e4702539632ce577536207d88Guido van Rossum 400b9da9bc0a04b718e8395e2e88c3053ab944579b7Raymond Hettinger def __eq__(self, other): 4014ad6bd5482514631680cebea3cdf06c56b87bac8Benjamin Peterson if not isinstance(other, Mapping): 4024ad6bd5482514631680cebea3cdf06c56b87bac8Benjamin Peterson return NotImplemented 4034ad6bd5482514631680cebea3cdf06c56b87bac8Benjamin Peterson return dict(self.items()) == dict(other.items()) 404b9da9bc0a04b718e8395e2e88c3053ab944579b7Raymond Hettinger 405b9da9bc0a04b718e8395e2e88c3053ab944579b7Raymond Hettinger def __ne__(self, other): 406554c8b856cbeb29f3fef0350846aef442832acacRaymond Hettinger return not (self == other) 407cd16bf640405065e4702539632ce577536207d88Guido van Rossum 4082202f877b1fdd13ae94dd7dc559b44903baf2f99Christian Heimes 409bfd061218b153f1d30b6bd344e947b4ae0fd49a5Raymond Hettingerclass MappingView(Sized): 410cd16bf640405065e4702539632ce577536207d88Guido van Rossum 411cd16bf640405065e4702539632ce577536207d88Guido van Rossum def __init__(self, mapping): 412cd16bf640405065e4702539632ce577536207d88Guido van Rossum self._mapping = mapping 413cd16bf640405065e4702539632ce577536207d88Guido van Rossum 414cd16bf640405065e4702539632ce577536207d88Guido van Rossum def __len__(self): 415cd16bf640405065e4702539632ce577536207d88Guido van Rossum return len(self._mapping) 416cd16bf640405065e4702539632ce577536207d88Guido van Rossum 41789fc2b78214b97f7bc5d3fcf32d9e4cb9940c1ddRaymond Hettinger def __repr__(self): 41889fc2b78214b97f7bc5d3fcf32d9e4cb9940c1ddRaymond Hettinger return '{0.__class__.__name__}({0._mapping!r})'.format(self) 41989fc2b78214b97f7bc5d3fcf32d9e4cb9940c1ddRaymond Hettinger 420cd16bf640405065e4702539632ce577536207d88Guido van Rossum 421cd16bf640405065e4702539632ce577536207d88Guido van Rossumclass KeysView(MappingView, Set): 422cd16bf640405065e4702539632ce577536207d88Guido van Rossum 4239117c751488a98810d758f15b3113527beb920efRaymond Hettinger @classmethod 4249117c751488a98810d758f15b3113527beb920efRaymond Hettinger def _from_iterable(self, it): 4259117c751488a98810d758f15b3113527beb920efRaymond Hettinger return set(it) 4269117c751488a98810d758f15b3113527beb920efRaymond Hettinger 427cd16bf640405065e4702539632ce577536207d88Guido van Rossum def __contains__(self, key): 428cd16bf640405065e4702539632ce577536207d88Guido van Rossum return key in self._mapping 429cd16bf640405065e4702539632ce577536207d88Guido van Rossum 430cd16bf640405065e4702539632ce577536207d88Guido van Rossum def __iter__(self): 431cd16bf640405065e4702539632ce577536207d88Guido van Rossum for key in self._mapping: 432cd16bf640405065e4702539632ce577536207d88Guido van Rossum yield key 433cd16bf640405065e4702539632ce577536207d88Guido van Rossum 434f83be4e3f353c4cfb53a22793dd1394797988c30Christian HeimesKeysView.register(dict_keys) 435cd16bf640405065e4702539632ce577536207d88Guido van Rossum 436cd16bf640405065e4702539632ce577536207d88Guido van Rossum 437cd16bf640405065e4702539632ce577536207d88Guido van Rossumclass ItemsView(MappingView, Set): 438cd16bf640405065e4702539632ce577536207d88Guido van Rossum 4399117c751488a98810d758f15b3113527beb920efRaymond Hettinger @classmethod 4409117c751488a98810d758f15b3113527beb920efRaymond Hettinger def _from_iterable(self, it): 4419117c751488a98810d758f15b3113527beb920efRaymond Hettinger return set(it) 4429117c751488a98810d758f15b3113527beb920efRaymond Hettinger 443cd16bf640405065e4702539632ce577536207d88Guido van Rossum def __contains__(self, item): 444cd16bf640405065e4702539632ce577536207d88Guido van Rossum key, value = item 445cd16bf640405065e4702539632ce577536207d88Guido van Rossum try: 446cd16bf640405065e4702539632ce577536207d88Guido van Rossum v = self._mapping[key] 447cd16bf640405065e4702539632ce577536207d88Guido van Rossum except KeyError: 448cd16bf640405065e4702539632ce577536207d88Guido van Rossum return False 449cd16bf640405065e4702539632ce577536207d88Guido van Rossum else: 450cd16bf640405065e4702539632ce577536207d88Guido van Rossum return v == value 451cd16bf640405065e4702539632ce577536207d88Guido van Rossum 452cd16bf640405065e4702539632ce577536207d88Guido van Rossum def __iter__(self): 453cd16bf640405065e4702539632ce577536207d88Guido van Rossum for key in self._mapping: 454cd16bf640405065e4702539632ce577536207d88Guido van Rossum yield (key, self._mapping[key]) 455cd16bf640405065e4702539632ce577536207d88Guido van Rossum 456f83be4e3f353c4cfb53a22793dd1394797988c30Christian HeimesItemsView.register(dict_items) 457cd16bf640405065e4702539632ce577536207d88Guido van Rossum 458cd16bf640405065e4702539632ce577536207d88Guido van Rossum 459cd16bf640405065e4702539632ce577536207d88Guido van Rossumclass ValuesView(MappingView): 460cd16bf640405065e4702539632ce577536207d88Guido van Rossum 461cd16bf640405065e4702539632ce577536207d88Guido van Rossum def __contains__(self, value): 462cd16bf640405065e4702539632ce577536207d88Guido van Rossum for key in self._mapping: 463cd16bf640405065e4702539632ce577536207d88Guido van Rossum if value == self._mapping[key]: 464cd16bf640405065e4702539632ce577536207d88Guido van Rossum return True 465cd16bf640405065e4702539632ce577536207d88Guido van Rossum return False 466cd16bf640405065e4702539632ce577536207d88Guido van Rossum 467cd16bf640405065e4702539632ce577536207d88Guido van Rossum def __iter__(self): 468cd16bf640405065e4702539632ce577536207d88Guido van Rossum for key in self._mapping: 469cd16bf640405065e4702539632ce577536207d88Guido van Rossum yield self._mapping[key] 470cd16bf640405065e4702539632ce577536207d88Guido van Rossum 471f83be4e3f353c4cfb53a22793dd1394797988c30Christian HeimesValuesView.register(dict_values) 472cd16bf640405065e4702539632ce577536207d88Guido van Rossum 473cd16bf640405065e4702539632ce577536207d88Guido van Rossum 474cd16bf640405065e4702539632ce577536207d88Guido van Rossumclass MutableMapping(Mapping): 475cd16bf640405065e4702539632ce577536207d88Guido van Rossum 476c46759ad0b3419bb67b33f0358af5ae50dc0c5feRaymond Hettinger __slots__ = () 477c46759ad0b3419bb67b33f0358af5ae50dc0c5feRaymond Hettinger 478cd16bf640405065e4702539632ce577536207d88Guido van Rossum @abstractmethod 479cd16bf640405065e4702539632ce577536207d88Guido van Rossum def __setitem__(self, key, value): 480cd16bf640405065e4702539632ce577536207d88Guido van Rossum raise KeyError 481cd16bf640405065e4702539632ce577536207d88Guido van Rossum 482cd16bf640405065e4702539632ce577536207d88Guido van Rossum @abstractmethod 483cd16bf640405065e4702539632ce577536207d88Guido van Rossum def __delitem__(self, key): 484cd16bf640405065e4702539632ce577536207d88Guido van Rossum raise KeyError 485cd16bf640405065e4702539632ce577536207d88Guido van Rossum 486cd16bf640405065e4702539632ce577536207d88Guido van Rossum __marker = object() 487cd16bf640405065e4702539632ce577536207d88Guido van Rossum 488cd16bf640405065e4702539632ce577536207d88Guido van Rossum def pop(self, key, default=__marker): 489cd16bf640405065e4702539632ce577536207d88Guido van Rossum try: 490cd16bf640405065e4702539632ce577536207d88Guido van Rossum value = self[key] 491cd16bf640405065e4702539632ce577536207d88Guido van Rossum except KeyError: 492cd16bf640405065e4702539632ce577536207d88Guido van Rossum if default is self.__marker: 493cd16bf640405065e4702539632ce577536207d88Guido van Rossum raise 494cd16bf640405065e4702539632ce577536207d88Guido van Rossum return default 495cd16bf640405065e4702539632ce577536207d88Guido van Rossum else: 496cd16bf640405065e4702539632ce577536207d88Guido van Rossum del self[key] 497cd16bf640405065e4702539632ce577536207d88Guido van Rossum return value 498cd16bf640405065e4702539632ce577536207d88Guido van Rossum 499cd16bf640405065e4702539632ce577536207d88Guido van Rossum def popitem(self): 500cd16bf640405065e4702539632ce577536207d88Guido van Rossum try: 501cd16bf640405065e4702539632ce577536207d88Guido van Rossum key = next(iter(self)) 502cd16bf640405065e4702539632ce577536207d88Guido van Rossum except StopIteration: 503cd16bf640405065e4702539632ce577536207d88Guido van Rossum raise KeyError 504cd16bf640405065e4702539632ce577536207d88Guido van Rossum value = self[key] 505cd16bf640405065e4702539632ce577536207d88Guido van Rossum del self[key] 506cd16bf640405065e4702539632ce577536207d88Guido van Rossum return key, value 507cd16bf640405065e4702539632ce577536207d88Guido van Rossum 508cd16bf640405065e4702539632ce577536207d88Guido van Rossum def clear(self): 509cd16bf640405065e4702539632ce577536207d88Guido van Rossum try: 510cd16bf640405065e4702539632ce577536207d88Guido van Rossum while True: 511cd16bf640405065e4702539632ce577536207d88Guido van Rossum self.popitem() 512cd16bf640405065e4702539632ce577536207d88Guido van Rossum except KeyError: 513cd16bf640405065e4702539632ce577536207d88Guido van Rossum pass 514cd16bf640405065e4702539632ce577536207d88Guido van Rossum 515b214e90e010f86b7d899cd88ada8c68fff90c870Mark Dickinson def update(*args, **kwds): 516b214e90e010f86b7d899cd88ada8c68fff90c870Mark Dickinson if len(args) > 2: 517b214e90e010f86b7d899cd88ada8c68fff90c870Mark Dickinson raise TypeError("update() takes at most 2 positional " 518b214e90e010f86b7d899cd88ada8c68fff90c870Mark Dickinson "arguments ({} given)".format(len(args))) 519b214e90e010f86b7d899cd88ada8c68fff90c870Mark Dickinson elif not args: 520b214e90e010f86b7d899cd88ada8c68fff90c870Mark Dickinson raise TypeError("update() takes at least 1 argument (0 given)") 521b214e90e010f86b7d899cd88ada8c68fff90c870Mark Dickinson self = args[0] 522b214e90e010f86b7d899cd88ada8c68fff90c870Mark Dickinson other = args[1] if len(args) >= 2 else () 523b214e90e010f86b7d899cd88ada8c68fff90c870Mark Dickinson 524cd16bf640405065e4702539632ce577536207d88Guido van Rossum if isinstance(other, Mapping): 525cd16bf640405065e4702539632ce577536207d88Guido van Rossum for key in other: 526cd16bf640405065e4702539632ce577536207d88Guido van Rossum self[key] = other[key] 527cd16bf640405065e4702539632ce577536207d88Guido van Rossum elif hasattr(other, "keys"): 528cd16bf640405065e4702539632ce577536207d88Guido van Rossum for key in other.keys(): 529cd16bf640405065e4702539632ce577536207d88Guido van Rossum self[key] = other[key] 530cd16bf640405065e4702539632ce577536207d88Guido van Rossum else: 531cd16bf640405065e4702539632ce577536207d88Guido van Rossum for key, value in other: 532cd16bf640405065e4702539632ce577536207d88Guido van Rossum self[key] = value 533cd16bf640405065e4702539632ce577536207d88Guido van Rossum for key, value in kwds.items(): 534cd16bf640405065e4702539632ce577536207d88Guido van Rossum self[key] = value 535cd16bf640405065e4702539632ce577536207d88Guido van Rossum 536b9da9bc0a04b718e8395e2e88c3053ab944579b7Raymond Hettinger def setdefault(self, key, default=None): 537b9da9bc0a04b718e8395e2e88c3053ab944579b7Raymond Hettinger try: 538b9da9bc0a04b718e8395e2e88c3053ab944579b7Raymond Hettinger return self[key] 539b9da9bc0a04b718e8395e2e88c3053ab944579b7Raymond Hettinger except KeyError: 540b9da9bc0a04b718e8395e2e88c3053ab944579b7Raymond Hettinger self[key] = default 541b9da9bc0a04b718e8395e2e88c3053ab944579b7Raymond Hettinger return default 542b9da9bc0a04b718e8395e2e88c3053ab944579b7Raymond Hettinger 543cd16bf640405065e4702539632ce577536207d88Guido van RossumMutableMapping.register(dict) 544cd16bf640405065e4702539632ce577536207d88Guido van Rossum 545cd16bf640405065e4702539632ce577536207d88Guido van Rossum 546cd16bf640405065e4702539632ce577536207d88Guido van Rossum### SEQUENCES ### 547cd16bf640405065e4702539632ce577536207d88Guido van Rossum 548cd16bf640405065e4702539632ce577536207d88Guido van Rossum 54974b6495b344303a84bf5e51ff388d8200dad4f64Raymond Hettingerclass Sequence(Sized, Iterable, Container): 550cd16bf640405065e4702539632ce577536207d88Guido van Rossum 551cd16bf640405065e4702539632ce577536207d88Guido van Rossum """All the operations on a read-only sequence. 552cd16bf640405065e4702539632ce577536207d88Guido van Rossum 553cd16bf640405065e4702539632ce577536207d88Guido van Rossum Concrete subclasses must override __new__ or __init__, 554cd16bf640405065e4702539632ce577536207d88Guido van Rossum __getitem__, and __len__. 555cd16bf640405065e4702539632ce577536207d88Guido van Rossum """ 556cd16bf640405065e4702539632ce577536207d88Guido van Rossum 557c46759ad0b3419bb67b33f0358af5ae50dc0c5feRaymond Hettinger __slots__ = () 558c46759ad0b3419bb67b33f0358af5ae50dc0c5feRaymond Hettinger 559cd16bf640405065e4702539632ce577536207d88Guido van Rossum @abstractmethod 560cd16bf640405065e4702539632ce577536207d88Guido van Rossum def __getitem__(self, index): 561cd16bf640405065e4702539632ce577536207d88Guido van Rossum raise IndexError 562cd16bf640405065e4702539632ce577536207d88Guido van Rossum 563cd16bf640405065e4702539632ce577536207d88Guido van Rossum def __iter__(self): 564cd16bf640405065e4702539632ce577536207d88Guido van Rossum i = 0 56571909423fd92862b869d8019d5e10c29bf946cb0Raymond Hettinger try: 56671909423fd92862b869d8019d5e10c29bf946cb0Raymond Hettinger while True: 567cd16bf640405065e4702539632ce577536207d88Guido van Rossum v = self[i] 56871909423fd92862b869d8019d5e10c29bf946cb0Raymond Hettinger yield v 56971909423fd92862b869d8019d5e10c29bf946cb0Raymond Hettinger i += 1 57071909423fd92862b869d8019d5e10c29bf946cb0Raymond Hettinger except IndexError: 57171909423fd92862b869d8019d5e10c29bf946cb0Raymond Hettinger return 572cd16bf640405065e4702539632ce577536207d88Guido van Rossum 573cd16bf640405065e4702539632ce577536207d88Guido van Rossum def __contains__(self, value): 574cd16bf640405065e4702539632ce577536207d88Guido van Rossum for v in self: 575cd16bf640405065e4702539632ce577536207d88Guido van Rossum if v == value: 576cd16bf640405065e4702539632ce577536207d88Guido van Rossum return True 577cd16bf640405065e4702539632ce577536207d88Guido van Rossum return False 578cd16bf640405065e4702539632ce577536207d88Guido van Rossum 579cd16bf640405065e4702539632ce577536207d88Guido van Rossum def __reversed__(self): 580cd16bf640405065e4702539632ce577536207d88Guido van Rossum for i in reversed(range(len(self))): 581cd16bf640405065e4702539632ce577536207d88Guido van Rossum yield self[i] 582cd16bf640405065e4702539632ce577536207d88Guido van Rossum 583cd16bf640405065e4702539632ce577536207d88Guido van Rossum def index(self, value): 584cd16bf640405065e4702539632ce577536207d88Guido van Rossum for i, v in enumerate(self): 585cd16bf640405065e4702539632ce577536207d88Guido van Rossum if v == value: 586cd16bf640405065e4702539632ce577536207d88Guido van Rossum return i 587cd16bf640405065e4702539632ce577536207d88Guido van Rossum raise ValueError 588cd16bf640405065e4702539632ce577536207d88Guido van Rossum 589cd16bf640405065e4702539632ce577536207d88Guido van Rossum def count(self, value): 590cd16bf640405065e4702539632ce577536207d88Guido van Rossum return sum(1 for v in self if v == value) 591cd16bf640405065e4702539632ce577536207d88Guido van Rossum 592cd16bf640405065e4702539632ce577536207d88Guido van RossumSequence.register(tuple) 5933172c5d263eeffff1e89d03d79be3ccc1d60fbdeGuido van RossumSequence.register(str) 5949aa53c2f0151032c5592d0c8b112fc35d7f77078Raymond HettingerSequence.register(range) 595d05eb0043e597cf2d5c429d0e554fd39364e36b0Guido van Rossum 596d05eb0043e597cf2d5c429d0e554fd39364e36b0Guido van Rossum 597d05eb0043e597cf2d5c429d0e554fd39364e36b0Guido van Rossumclass ByteString(Sequence): 598d05eb0043e597cf2d5c429d0e554fd39364e36b0Guido van Rossum 599d05eb0043e597cf2d5c429d0e554fd39364e36b0Guido van Rossum """This unifies bytes and bytearray. 600d05eb0043e597cf2d5c429d0e554fd39364e36b0Guido van Rossum 601d05eb0043e597cf2d5c429d0e554fd39364e36b0Guido van Rossum XXX Should add all their methods. 602d05eb0043e597cf2d5c429d0e554fd39364e36b0Guido van Rossum """ 603d05eb0043e597cf2d5c429d0e554fd39364e36b0Guido van Rossum 604c46759ad0b3419bb67b33f0358af5ae50dc0c5feRaymond Hettinger __slots__ = () 605c46759ad0b3419bb67b33f0358af5ae50dc0c5feRaymond Hettinger 606d05eb0043e597cf2d5c429d0e554fd39364e36b0Guido van RossumByteString.register(bytes) 607d05eb0043e597cf2d5c429d0e554fd39364e36b0Guido van RossumByteString.register(bytearray) 608cd16bf640405065e4702539632ce577536207d88Guido van Rossum 609cd16bf640405065e4702539632ce577536207d88Guido van Rossum 610cd16bf640405065e4702539632ce577536207d88Guido van Rossumclass MutableSequence(Sequence): 611cd16bf640405065e4702539632ce577536207d88Guido van Rossum 612c46759ad0b3419bb67b33f0358af5ae50dc0c5feRaymond Hettinger __slots__ = () 613c46759ad0b3419bb67b33f0358af5ae50dc0c5feRaymond Hettinger 614cd16bf640405065e4702539632ce577536207d88Guido van Rossum @abstractmethod 615cd16bf640405065e4702539632ce577536207d88Guido van Rossum def __setitem__(self, index, value): 616cd16bf640405065e4702539632ce577536207d88Guido van Rossum raise IndexError 617cd16bf640405065e4702539632ce577536207d88Guido van Rossum 618cd16bf640405065e4702539632ce577536207d88Guido van Rossum @abstractmethod 619cd16bf640405065e4702539632ce577536207d88Guido van Rossum def __delitem__(self, index): 620cd16bf640405065e4702539632ce577536207d88Guido van Rossum raise IndexError 621cd16bf640405065e4702539632ce577536207d88Guido van Rossum 622cd16bf640405065e4702539632ce577536207d88Guido van Rossum @abstractmethod 623cd16bf640405065e4702539632ce577536207d88Guido van Rossum def insert(self, index, value): 624cd16bf640405065e4702539632ce577536207d88Guido van Rossum raise IndexError 625cd16bf640405065e4702539632ce577536207d88Guido van Rossum 626cd16bf640405065e4702539632ce577536207d88Guido van Rossum def append(self, value): 627cd16bf640405065e4702539632ce577536207d88Guido van Rossum self.insert(len(self), value) 628cd16bf640405065e4702539632ce577536207d88Guido van Rossum 6299479d1ade84d7a386a107989b699fb90b73cfa15Eli Bendersky def clear(self): 6309479d1ade84d7a386a107989b699fb90b73cfa15Eli Bendersky try: 6319479d1ade84d7a386a107989b699fb90b73cfa15Eli Bendersky while True: 6329479d1ade84d7a386a107989b699fb90b73cfa15Eli Bendersky self.pop() 6339479d1ade84d7a386a107989b699fb90b73cfa15Eli Bendersky except IndexError: 6349479d1ade84d7a386a107989b699fb90b73cfa15Eli Bendersky pass 6359479d1ade84d7a386a107989b699fb90b73cfa15Eli Bendersky 636cd16bf640405065e4702539632ce577536207d88Guido van Rossum def reverse(self): 637cd16bf640405065e4702539632ce577536207d88Guido van Rossum n = len(self) 638cd16bf640405065e4702539632ce577536207d88Guido van Rossum for i in range(n//2): 639cd16bf640405065e4702539632ce577536207d88Guido van Rossum self[i], self[n-i-1] = self[n-i-1], self[i] 640cd16bf640405065e4702539632ce577536207d88Guido van Rossum 641cd16bf640405065e4702539632ce577536207d88Guido van Rossum def extend(self, values): 642cd16bf640405065e4702539632ce577536207d88Guido van Rossum for v in values: 643cd16bf640405065e4702539632ce577536207d88Guido van Rossum self.append(v) 644cd16bf640405065e4702539632ce577536207d88Guido van Rossum 645cd16bf640405065e4702539632ce577536207d88Guido van Rossum def pop(self, index=-1): 646cd16bf640405065e4702539632ce577536207d88Guido van Rossum v = self[index] 647cd16bf640405065e4702539632ce577536207d88Guido van Rossum del self[index] 648cd16bf640405065e4702539632ce577536207d88Guido van Rossum return v 649cd16bf640405065e4702539632ce577536207d88Guido van Rossum 650cd16bf640405065e4702539632ce577536207d88Guido van Rossum def remove(self, value): 651cd16bf640405065e4702539632ce577536207d88Guido van Rossum del self[self.index(value)] 652cd16bf640405065e4702539632ce577536207d88Guido van Rossum 653cd16bf640405065e4702539632ce577536207d88Guido van Rossum def __iadd__(self, values): 654cd16bf640405065e4702539632ce577536207d88Guido van Rossum self.extend(values) 655c384b226d765d5f57a909df8da3f4fcdfb4b7246Raymond Hettinger return self 656cd16bf640405065e4702539632ce577536207d88Guido van Rossum 657cd16bf640405065e4702539632ce577536207d88Guido van RossumMutableSequence.register(list) 658d05eb0043e597cf2d5c429d0e554fd39364e36b0Guido van RossumMutableSequence.register(bytearray) # Multiply inheriting, see ByteString 659