_collections_abc.py revision 158c9c26fca16dee2f7a8d89707cf9c149bd04f2
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 21f83be4e3f353c4cfb53a22793dd1394797988c30Christian Heimes 22f83be4e3f353c4cfb53a22793dd1394797988c30Christian Heimes### collection related types which are not exposed through builtin ### 23f83be4e3f353c4cfb53a22793dd1394797988c30Christian Heimes## iterators ## 24f83be4e3f353c4cfb53a22793dd1394797988c30Christian Heimesbytes_iterator = type(iter(b'')) 25f83be4e3f353c4cfb53a22793dd1394797988c30Christian Heimesbytearray_iterator = type(iter(bytearray())) 26f83be4e3f353c4cfb53a22793dd1394797988c30Christian Heimes#callable_iterator = ??? 27f83be4e3f353c4cfb53a22793dd1394797988c30Christian Heimesdict_keyiterator = type(iter({}.keys())) 28f83be4e3f353c4cfb53a22793dd1394797988c30Christian Heimesdict_valueiterator = type(iter({}.values())) 29f83be4e3f353c4cfb53a22793dd1394797988c30Christian Heimesdict_itemiterator = type(iter({}.items())) 30f83be4e3f353c4cfb53a22793dd1394797988c30Christian Heimeslist_iterator = type(iter([])) 31f83be4e3f353c4cfb53a22793dd1394797988c30Christian Heimeslist_reverseiterator = type(iter(reversed([]))) 32f83be4e3f353c4cfb53a22793dd1394797988c30Christian Heimesrange_iterator = type(iter(range(0))) 33f83be4e3f353c4cfb53a22793dd1394797988c30Christian Heimesset_iterator = type(iter(set())) 34f83be4e3f353c4cfb53a22793dd1394797988c30Christian Heimesstr_iterator = type(iter("")) 35f83be4e3f353c4cfb53a22793dd1394797988c30Christian Heimestuple_iterator = type(iter(())) 36f83be4e3f353c4cfb53a22793dd1394797988c30Christian Heimeszip_iterator = type(iter(zip())) 37f83be4e3f353c4cfb53a22793dd1394797988c30Christian Heimes## views ## 38f83be4e3f353c4cfb53a22793dd1394797988c30Christian Heimesdict_keys = type({}.keys()) 39f83be4e3f353c4cfb53a22793dd1394797988c30Christian Heimesdict_values = type({}.values()) 40f83be4e3f353c4cfb53a22793dd1394797988c30Christian Heimesdict_items = type({}.items()) 410db38532b304c89a998e4fc53b3ac8cd7ff23a8aChristian Heimes## misc ## 420db38532b304c89a998e4fc53b3ac8cd7ff23a8aChristian Heimesdict_proxy = type(type.__dict__) 43f83be4e3f353c4cfb53a22793dd1394797988c30Christian Heimes 44f83be4e3f353c4cfb53a22793dd1394797988c30Christian Heimes 45cd16bf640405065e4702539632ce577536207d88Guido van Rossum### ONE-TRICK PONIES ### 46cd16bf640405065e4702539632ce577536207d88Guido van Rossum 47cd16bf640405065e4702539632ce577536207d88Guido van Rossumclass Hashable(metaclass=ABCMeta): 48cd16bf640405065e4702539632ce577536207d88Guido van Rossum 49cd16bf640405065e4702539632ce577536207d88Guido van Rossum @abstractmethod 50cd16bf640405065e4702539632ce577536207d88Guido van Rossum def __hash__(self): 51cd16bf640405065e4702539632ce577536207d88Guido van Rossum return 0 52cd16bf640405065e4702539632ce577536207d88Guido van Rossum 53cd16bf640405065e4702539632ce577536207d88Guido van Rossum @classmethod 54cd16bf640405065e4702539632ce577536207d88Guido van Rossum def __subclasshook__(cls, C): 55cd16bf640405065e4702539632ce577536207d88Guido van Rossum if cls is Hashable: 56cd16bf640405065e4702539632ce577536207d88Guido van Rossum for B in C.__mro__: 57cd16bf640405065e4702539632ce577536207d88Guido van Rossum if "__hash__" in B.__dict__: 58cd16bf640405065e4702539632ce577536207d88Guido van Rossum if B.__dict__["__hash__"]: 59cd16bf640405065e4702539632ce577536207d88Guido van Rossum return True 60cd16bf640405065e4702539632ce577536207d88Guido van Rossum break 61cd16bf640405065e4702539632ce577536207d88Guido van Rossum return NotImplemented 62cd16bf640405065e4702539632ce577536207d88Guido van Rossum 63cd16bf640405065e4702539632ce577536207d88Guido van Rossum 64cd16bf640405065e4702539632ce577536207d88Guido van Rossumclass Iterable(metaclass=ABCMeta): 65cd16bf640405065e4702539632ce577536207d88Guido van Rossum 66cd16bf640405065e4702539632ce577536207d88Guido van Rossum @abstractmethod 67cd16bf640405065e4702539632ce577536207d88Guido van Rossum def __iter__(self): 68cd16bf640405065e4702539632ce577536207d88Guido van Rossum while False: 69cd16bf640405065e4702539632ce577536207d88Guido van Rossum yield None 70cd16bf640405065e4702539632ce577536207d88Guido van Rossum 71cd16bf640405065e4702539632ce577536207d88Guido van Rossum @classmethod 72cd16bf640405065e4702539632ce577536207d88Guido van Rossum def __subclasshook__(cls, C): 73cd16bf640405065e4702539632ce577536207d88Guido van Rossum if cls is Iterable: 74cd16bf640405065e4702539632ce577536207d88Guido van Rossum if any("__iter__" in B.__dict__ for B in C.__mro__): 75cd16bf640405065e4702539632ce577536207d88Guido van Rossum return True 76cd16bf640405065e4702539632ce577536207d88Guido van Rossum return NotImplemented 77cd16bf640405065e4702539632ce577536207d88Guido van Rossum 78cd16bf640405065e4702539632ce577536207d88Guido van Rossum 7974b6495b344303a84bf5e51ff388d8200dad4f64Raymond Hettingerclass Iterator(Iterable): 80cd16bf640405065e4702539632ce577536207d88Guido van Rossum 81cd16bf640405065e4702539632ce577536207d88Guido van Rossum @abstractmethod 82cd16bf640405065e4702539632ce577536207d88Guido van Rossum def __next__(self): 83cd16bf640405065e4702539632ce577536207d88Guido van Rossum raise StopIteration 84cd16bf640405065e4702539632ce577536207d88Guido van Rossum 85cd16bf640405065e4702539632ce577536207d88Guido van Rossum def __iter__(self): 86cd16bf640405065e4702539632ce577536207d88Guido van Rossum return self 87cd16bf640405065e4702539632ce577536207d88Guido van Rossum 88cd16bf640405065e4702539632ce577536207d88Guido van Rossum @classmethod 89cd16bf640405065e4702539632ce577536207d88Guido van Rossum def __subclasshook__(cls, C): 90cd16bf640405065e4702539632ce577536207d88Guido van Rossum if cls is Iterator: 91ead22227cce112457b6beba8b008699ea4a3a084Raymond Hettinger if (any("__next__" in B.__dict__ for B in C.__mro__) and 92ead22227cce112457b6beba8b008699ea4a3a084Raymond Hettinger any("__iter__" in B.__dict__ for B in C.__mro__)): 93cd16bf640405065e4702539632ce577536207d88Guido van Rossum return True 94cd16bf640405065e4702539632ce577536207d88Guido van Rossum return NotImplemented 95cd16bf640405065e4702539632ce577536207d88Guido van Rossum 96f83be4e3f353c4cfb53a22793dd1394797988c30Christian HeimesIterator.register(bytes_iterator) 97f83be4e3f353c4cfb53a22793dd1394797988c30Christian HeimesIterator.register(bytearray_iterator) 98f83be4e3f353c4cfb53a22793dd1394797988c30Christian Heimes#Iterator.register(callable_iterator) 99f83be4e3f353c4cfb53a22793dd1394797988c30Christian HeimesIterator.register(dict_keyiterator) 100f83be4e3f353c4cfb53a22793dd1394797988c30Christian HeimesIterator.register(dict_valueiterator) 101f83be4e3f353c4cfb53a22793dd1394797988c30Christian HeimesIterator.register(dict_itemiterator) 102f83be4e3f353c4cfb53a22793dd1394797988c30Christian HeimesIterator.register(list_iterator) 103f83be4e3f353c4cfb53a22793dd1394797988c30Christian HeimesIterator.register(list_reverseiterator) 104f83be4e3f353c4cfb53a22793dd1394797988c30Christian HeimesIterator.register(range_iterator) 105f83be4e3f353c4cfb53a22793dd1394797988c30Christian HeimesIterator.register(set_iterator) 106f83be4e3f353c4cfb53a22793dd1394797988c30Christian HeimesIterator.register(str_iterator) 107f83be4e3f353c4cfb53a22793dd1394797988c30Christian HeimesIterator.register(tuple_iterator) 108f83be4e3f353c4cfb53a22793dd1394797988c30Christian HeimesIterator.register(zip_iterator) 109cd16bf640405065e4702539632ce577536207d88Guido van Rossum 110cd16bf640405065e4702539632ce577536207d88Guido van Rossumclass Sized(metaclass=ABCMeta): 111cd16bf640405065e4702539632ce577536207d88Guido van Rossum 112cd16bf640405065e4702539632ce577536207d88Guido van Rossum @abstractmethod 113cd16bf640405065e4702539632ce577536207d88Guido van Rossum def __len__(self): 114cd16bf640405065e4702539632ce577536207d88Guido van Rossum return 0 115cd16bf640405065e4702539632ce577536207d88Guido van Rossum 116cd16bf640405065e4702539632ce577536207d88Guido van Rossum @classmethod 117cd16bf640405065e4702539632ce577536207d88Guido van Rossum def __subclasshook__(cls, C): 118cd16bf640405065e4702539632ce577536207d88Guido van Rossum if cls is Sized: 119cd16bf640405065e4702539632ce577536207d88Guido van Rossum if any("__len__" in B.__dict__ for B in C.__mro__): 120cd16bf640405065e4702539632ce577536207d88Guido van Rossum return True 121cd16bf640405065e4702539632ce577536207d88Guido van Rossum return NotImplemented 122cd16bf640405065e4702539632ce577536207d88Guido van Rossum 123cd16bf640405065e4702539632ce577536207d88Guido van Rossum 124cd16bf640405065e4702539632ce577536207d88Guido van Rossumclass Container(metaclass=ABCMeta): 125cd16bf640405065e4702539632ce577536207d88Guido van Rossum 126cd16bf640405065e4702539632ce577536207d88Guido van Rossum @abstractmethod 127cd16bf640405065e4702539632ce577536207d88Guido van Rossum def __contains__(self, x): 128cd16bf640405065e4702539632ce577536207d88Guido van Rossum return False 129cd16bf640405065e4702539632ce577536207d88Guido van Rossum 130cd16bf640405065e4702539632ce577536207d88Guido van Rossum @classmethod 131cd16bf640405065e4702539632ce577536207d88Guido van Rossum def __subclasshook__(cls, C): 132cd16bf640405065e4702539632ce577536207d88Guido van Rossum if cls is Container: 133cd16bf640405065e4702539632ce577536207d88Guido van Rossum if any("__contains__" in B.__dict__ for B in C.__mro__): 134cd16bf640405065e4702539632ce577536207d88Guido van Rossum return True 135cd16bf640405065e4702539632ce577536207d88Guido van Rossum return NotImplemented 136cd16bf640405065e4702539632ce577536207d88Guido van Rossum 137cd16bf640405065e4702539632ce577536207d88Guido van Rossum 138cd16bf640405065e4702539632ce577536207d88Guido van Rossumclass Callable(metaclass=ABCMeta): 139cd16bf640405065e4702539632ce577536207d88Guido van Rossum 140cd16bf640405065e4702539632ce577536207d88Guido van Rossum @abstractmethod 1417864476afa402a0537c33ba9630e77351720baf8Christian Heimes def __call__(self, *args, **kwds): 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 Callable: 147cd16bf640405065e4702539632ce577536207d88Guido van Rossum if any("__call__" 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 Rossum### SETS ### 153cd16bf640405065e4702539632ce577536207d88Guido van Rossum 154cd16bf640405065e4702539632ce577536207d88Guido van Rossum 15574b6495b344303a84bf5e51ff388d8200dad4f64Raymond Hettingerclass Set(Sized, Iterable, Container): 156cd16bf640405065e4702539632ce577536207d88Guido van Rossum 157cd16bf640405065e4702539632ce577536207d88Guido van Rossum """A set is a finite, iterable container. 158cd16bf640405065e4702539632ce577536207d88Guido van Rossum 159cd16bf640405065e4702539632ce577536207d88Guido van Rossum This class provides concrete generic implementations of all 160cd16bf640405065e4702539632ce577536207d88Guido van Rossum methods except for __contains__, __iter__ and __len__. 161cd16bf640405065e4702539632ce577536207d88Guido van Rossum 162cd16bf640405065e4702539632ce577536207d88Guido van Rossum To override the comparisons (presumably for speed, as the 163cd16bf640405065e4702539632ce577536207d88Guido van Rossum semantics are fixed), all you have to do is redefine __le__ and 164cd16bf640405065e4702539632ce577536207d88Guido van Rossum then the other operations will automatically follow suit. 165cd16bf640405065e4702539632ce577536207d88Guido van Rossum """ 166cd16bf640405065e4702539632ce577536207d88Guido van Rossum 167cd16bf640405065e4702539632ce577536207d88Guido van Rossum def __le__(self, other): 168cd16bf640405065e4702539632ce577536207d88Guido van Rossum if not isinstance(other, Set): 169cd16bf640405065e4702539632ce577536207d88Guido van Rossum return NotImplemented 170cd16bf640405065e4702539632ce577536207d88Guido van Rossum if len(self) > len(other): 171cd16bf640405065e4702539632ce577536207d88Guido van Rossum return False 172cd16bf640405065e4702539632ce577536207d88Guido van Rossum for elem in self: 173cd16bf640405065e4702539632ce577536207d88Guido van Rossum if elem not in other: 174cd16bf640405065e4702539632ce577536207d88Guido van Rossum return False 175cd16bf640405065e4702539632ce577536207d88Guido van Rossum return True 176cd16bf640405065e4702539632ce577536207d88Guido van Rossum 177cd16bf640405065e4702539632ce577536207d88Guido van Rossum def __lt__(self, other): 178cd16bf640405065e4702539632ce577536207d88Guido van Rossum if not isinstance(other, Set): 179cd16bf640405065e4702539632ce577536207d88Guido van Rossum return NotImplemented 180cd16bf640405065e4702539632ce577536207d88Guido van Rossum return len(self) < len(other) and self.__le__(other) 181cd16bf640405065e4702539632ce577536207d88Guido van Rossum 18271909423fd92862b869d8019d5e10c29bf946cb0Raymond Hettinger def __gt__(self, other): 18371909423fd92862b869d8019d5e10c29bf946cb0Raymond Hettinger if not isinstance(other, Set): 18471909423fd92862b869d8019d5e10c29bf946cb0Raymond Hettinger return NotImplemented 18571909423fd92862b869d8019d5e10c29bf946cb0Raymond Hettinger return other < self 18671909423fd92862b869d8019d5e10c29bf946cb0Raymond Hettinger 18771909423fd92862b869d8019d5e10c29bf946cb0Raymond Hettinger def __ge__(self, other): 18871909423fd92862b869d8019d5e10c29bf946cb0Raymond Hettinger if not isinstance(other, Set): 18971909423fd92862b869d8019d5e10c29bf946cb0Raymond Hettinger return NotImplemented 19071909423fd92862b869d8019d5e10c29bf946cb0Raymond Hettinger return other <= self 19171909423fd92862b869d8019d5e10c29bf946cb0Raymond Hettinger 192cd16bf640405065e4702539632ce577536207d88Guido van Rossum def __eq__(self, other): 193cd16bf640405065e4702539632ce577536207d88Guido van Rossum if not isinstance(other, Set): 194cd16bf640405065e4702539632ce577536207d88Guido van Rossum return NotImplemented 195cd16bf640405065e4702539632ce577536207d88Guido van Rossum return len(self) == len(other) and self.__le__(other) 196cd16bf640405065e4702539632ce577536207d88Guido van Rossum 19771909423fd92862b869d8019d5e10c29bf946cb0Raymond Hettinger def __ne__(self, other): 19871909423fd92862b869d8019d5e10c29bf946cb0Raymond Hettinger return not (self == other) 19971909423fd92862b869d8019d5e10c29bf946cb0Raymond Hettinger 200cd16bf640405065e4702539632ce577536207d88Guido van Rossum @classmethod 201cd16bf640405065e4702539632ce577536207d88Guido van Rossum def _from_iterable(cls, it): 2028284c4a7fb27efd55323513572e247a895a35ae1Raymond Hettinger '''Construct an instance of the class from any iterable input. 2038284c4a7fb27efd55323513572e247a895a35ae1Raymond Hettinger 2048284c4a7fb27efd55323513572e247a895a35ae1Raymond Hettinger Must override this method if the class constructor signature 2057aebb64bab2ef75c6d9ae55da9ae7049f05c8670Raymond Hettinger does not accept an iterable for an input. 2068284c4a7fb27efd55323513572e247a895a35ae1Raymond Hettinger ''' 2077aebb64bab2ef75c6d9ae55da9ae7049f05c8670Raymond Hettinger return cls(it) 208cd16bf640405065e4702539632ce577536207d88Guido van Rossum 209cd16bf640405065e4702539632ce577536207d88Guido van Rossum def __and__(self, other): 210cd16bf640405065e4702539632ce577536207d88Guido van Rossum if not isinstance(other, Iterable): 211cd16bf640405065e4702539632ce577536207d88Guido van Rossum return NotImplemented 212cd16bf640405065e4702539632ce577536207d88Guido van Rossum return self._from_iterable(value for value in other if value in self) 213cd16bf640405065e4702539632ce577536207d88Guido van Rossum 214190d79e5c648174b550de2bef75d1b4addf0d625Christian Heimes def isdisjoint(self, other): 215190d79e5c648174b550de2bef75d1b4addf0d625Christian Heimes for value in other: 216190d79e5c648174b550de2bef75d1b4addf0d625Christian Heimes if value in self: 217190d79e5c648174b550de2bef75d1b4addf0d625Christian Heimes return False 218190d79e5c648174b550de2bef75d1b4addf0d625Christian Heimes return True 219190d79e5c648174b550de2bef75d1b4addf0d625Christian Heimes 220cd16bf640405065e4702539632ce577536207d88Guido van Rossum def __or__(self, other): 221cd16bf640405065e4702539632ce577536207d88Guido van Rossum if not isinstance(other, Iterable): 222cd16bf640405065e4702539632ce577536207d88Guido van Rossum return NotImplemented 2237864476afa402a0537c33ba9630e77351720baf8Christian Heimes chain = (e for s in (self, other) for e in s) 2247864476afa402a0537c33ba9630e77351720baf8Christian Heimes return self._from_iterable(chain) 225cd16bf640405065e4702539632ce577536207d88Guido van Rossum 226cd16bf640405065e4702539632ce577536207d88Guido van Rossum def __sub__(self, other): 227cd16bf640405065e4702539632ce577536207d88Guido van Rossum if not isinstance(other, Set): 228cd16bf640405065e4702539632ce577536207d88Guido van Rossum if not isinstance(other, Iterable): 229cd16bf640405065e4702539632ce577536207d88Guido van Rossum return NotImplemented 230cd16bf640405065e4702539632ce577536207d88Guido van Rossum other = self._from_iterable(other) 231cd16bf640405065e4702539632ce577536207d88Guido van Rossum return self._from_iterable(value for value in self 232cd16bf640405065e4702539632ce577536207d88Guido van Rossum if value not in other) 233cd16bf640405065e4702539632ce577536207d88Guido van Rossum 234cd16bf640405065e4702539632ce577536207d88Guido van Rossum def __xor__(self, other): 235cd16bf640405065e4702539632ce577536207d88Guido van Rossum if not isinstance(other, Set): 236cd16bf640405065e4702539632ce577536207d88Guido van Rossum if not isinstance(other, Iterable): 237cd16bf640405065e4702539632ce577536207d88Guido van Rossum return NotImplemented 238cd16bf640405065e4702539632ce577536207d88Guido van Rossum other = self._from_iterable(other) 239cd16bf640405065e4702539632ce577536207d88Guido van Rossum return (self - other) | (other - self) 240cd16bf640405065e4702539632ce577536207d88Guido van Rossum 241cd16bf640405065e4702539632ce577536207d88Guido van Rossum def _hash(self): 242cd16bf640405065e4702539632ce577536207d88Guido van Rossum """Compute the hash value of a set. 243cd16bf640405065e4702539632ce577536207d88Guido van Rossum 244cd16bf640405065e4702539632ce577536207d88Guido van Rossum Note that we don't define __hash__: not all sets are hashable. 245cd16bf640405065e4702539632ce577536207d88Guido van Rossum But if you define a hashable set type, its __hash__ should 246cd16bf640405065e4702539632ce577536207d88Guido van Rossum call this function. 247cd16bf640405065e4702539632ce577536207d88Guido van Rossum 248cd16bf640405065e4702539632ce577536207d88Guido van Rossum This must be compatible __eq__. 249cd16bf640405065e4702539632ce577536207d88Guido van Rossum 250cd16bf640405065e4702539632ce577536207d88Guido van Rossum All sets ought to compare equal if they contain the same 251cd16bf640405065e4702539632ce577536207d88Guido van Rossum elements, regardless of how they are implemented, and 252cd16bf640405065e4702539632ce577536207d88Guido van Rossum regardless of the order of the elements; so there's not much 253cd16bf640405065e4702539632ce577536207d88Guido van Rossum freedom for __eq__ or __hash__. We match the algorithm used 254cd16bf640405065e4702539632ce577536207d88Guido van Rossum by the built-in frozenset type. 255cd16bf640405065e4702539632ce577536207d88Guido van Rossum """ 256a37d4c693a024154093b36a612810c3bd72d9254Christian Heimes MAX = sys.maxsize 257cd16bf640405065e4702539632ce577536207d88Guido van Rossum MASK = 2 * MAX + 1 258cd16bf640405065e4702539632ce577536207d88Guido van Rossum n = len(self) 259cd16bf640405065e4702539632ce577536207d88Guido van Rossum h = 1927868237 * (n + 1) 260cd16bf640405065e4702539632ce577536207d88Guido van Rossum h &= MASK 261cd16bf640405065e4702539632ce577536207d88Guido van Rossum for x in self: 262cd16bf640405065e4702539632ce577536207d88Guido van Rossum hx = hash(x) 263cd16bf640405065e4702539632ce577536207d88Guido van Rossum h ^= (hx ^ (hx << 16) ^ 89869747) * 3644798167 264cd16bf640405065e4702539632ce577536207d88Guido van Rossum h &= MASK 265cd16bf640405065e4702539632ce577536207d88Guido van Rossum h = h * 69069 + 907133923 266cd16bf640405065e4702539632ce577536207d88Guido van Rossum h &= MASK 267cd16bf640405065e4702539632ce577536207d88Guido van Rossum if h > MAX: 268cd16bf640405065e4702539632ce577536207d88Guido van Rossum h -= MASK + 1 269cd16bf640405065e4702539632ce577536207d88Guido van Rossum if h == -1: 270cd16bf640405065e4702539632ce577536207d88Guido van Rossum h = 590923713 271cd16bf640405065e4702539632ce577536207d88Guido van Rossum return h 272cd16bf640405065e4702539632ce577536207d88Guido van Rossum 273cd16bf640405065e4702539632ce577536207d88Guido van RossumSet.register(frozenset) 274cd16bf640405065e4702539632ce577536207d88Guido van Rossum 275cd16bf640405065e4702539632ce577536207d88Guido van Rossum 276cd16bf640405065e4702539632ce577536207d88Guido van Rossumclass MutableSet(Set): 277cd16bf640405065e4702539632ce577536207d88Guido van Rossum 278cd16bf640405065e4702539632ce577536207d88Guido van Rossum @abstractmethod 279cd16bf640405065e4702539632ce577536207d88Guido van Rossum def add(self, value): 280058e31ef2aec3ea079cdf297fc0d4f40d3d9975aBenjamin Peterson """Add an element.""" 281cd16bf640405065e4702539632ce577536207d88Guido van Rossum raise NotImplementedError 282cd16bf640405065e4702539632ce577536207d88Guido van Rossum 283cd16bf640405065e4702539632ce577536207d88Guido van Rossum @abstractmethod 284cd16bf640405065e4702539632ce577536207d88Guido van Rossum def discard(self, value): 285058e31ef2aec3ea079cdf297fc0d4f40d3d9975aBenjamin Peterson """Remove an element. Do not raise an exception if absent.""" 286cd16bf640405065e4702539632ce577536207d88Guido van Rossum raise NotImplementedError 287cd16bf640405065e4702539632ce577536207d88Guido van Rossum 288190d79e5c648174b550de2bef75d1b4addf0d625Christian Heimes def remove(self, value): 289190d79e5c648174b550de2bef75d1b4addf0d625Christian Heimes """Remove an element. If not a member, raise a KeyError.""" 290190d79e5c648174b550de2bef75d1b4addf0d625Christian Heimes if value not in self: 291190d79e5c648174b550de2bef75d1b4addf0d625Christian Heimes raise KeyError(value) 292190d79e5c648174b550de2bef75d1b4addf0d625Christian Heimes self.discard(value) 293190d79e5c648174b550de2bef75d1b4addf0d625Christian Heimes 294cd16bf640405065e4702539632ce577536207d88Guido van Rossum def pop(self): 295cd16bf640405065e4702539632ce577536207d88Guido van Rossum """Return the popped value. Raise KeyError if empty.""" 296cd16bf640405065e4702539632ce577536207d88Guido van Rossum it = iter(self) 297cd16bf640405065e4702539632ce577536207d88Guido van Rossum try: 298ae650181b89feeb1f68fb7643d190df52d13bd9eRaymond Hettinger value = next(it) 299cd16bf640405065e4702539632ce577536207d88Guido van Rossum except StopIteration: 300cd16bf640405065e4702539632ce577536207d88Guido van Rossum raise KeyError 301cd16bf640405065e4702539632ce577536207d88Guido van Rossum self.discard(value) 302cd16bf640405065e4702539632ce577536207d88Guido van Rossum return value 303cd16bf640405065e4702539632ce577536207d88Guido van Rossum 304cd16bf640405065e4702539632ce577536207d88Guido van Rossum def clear(self): 305cd16bf640405065e4702539632ce577536207d88Guido van Rossum """This is slow (creates N new iterators!) but effective.""" 306cd16bf640405065e4702539632ce577536207d88Guido van Rossum try: 307cd16bf640405065e4702539632ce577536207d88Guido van Rossum while True: 308cd16bf640405065e4702539632ce577536207d88Guido van Rossum self.pop() 309cd16bf640405065e4702539632ce577536207d88Guido van Rossum except KeyError: 310cd16bf640405065e4702539632ce577536207d88Guido van Rossum pass 311cd16bf640405065e4702539632ce577536207d88Guido van Rossum 312b3d89a4ee438ee6927bfe553694b5b06f5672274Raymond Hettinger def __ior__(self, it): 313cd16bf640405065e4702539632ce577536207d88Guido van Rossum for value in it: 314cd16bf640405065e4702539632ce577536207d88Guido van Rossum self.add(value) 315cd16bf640405065e4702539632ce577536207d88Guido van Rossum return self 316cd16bf640405065e4702539632ce577536207d88Guido van Rossum 317b3d89a4ee438ee6927bfe553694b5b06f5672274Raymond Hettinger def __iand__(self, it): 3183f10a952f6056b6797e4187bcfa1a97c21d1b3bbRaymond Hettinger for value in (self - it): 3193f10a952f6056b6797e4187bcfa1a97c21d1b3bbRaymond Hettinger self.discard(value) 320cd16bf640405065e4702539632ce577536207d88Guido van Rossum return self 321cd16bf640405065e4702539632ce577536207d88Guido van Rossum 322b3d89a4ee438ee6927bfe553694b5b06f5672274Raymond Hettinger def __ixor__(self, it): 32331da5b2f69d408ac2448eb04ee2892b8aa3aac79Daniel Stutzbach if it is self: 32431da5b2f69d408ac2448eb04ee2892b8aa3aac79Daniel Stutzbach self.clear() 32531da5b2f69d408ac2448eb04ee2892b8aa3aac79Daniel Stutzbach else: 32631da5b2f69d408ac2448eb04ee2892b8aa3aac79Daniel Stutzbach if not isinstance(it, Set): 32731da5b2f69d408ac2448eb04ee2892b8aa3aac79Daniel Stutzbach it = self._from_iterable(it) 32831da5b2f69d408ac2448eb04ee2892b8aa3aac79Daniel Stutzbach for value in it: 32931da5b2f69d408ac2448eb04ee2892b8aa3aac79Daniel Stutzbach if value in self: 33031da5b2f69d408ac2448eb04ee2892b8aa3aac79Daniel Stutzbach self.discard(value) 33131da5b2f69d408ac2448eb04ee2892b8aa3aac79Daniel Stutzbach else: 33231da5b2f69d408ac2448eb04ee2892b8aa3aac79Daniel Stutzbach self.add(value) 333cd16bf640405065e4702539632ce577536207d88Guido van Rossum return self 334cd16bf640405065e4702539632ce577536207d88Guido van Rossum 335b3d89a4ee438ee6927bfe553694b5b06f5672274Raymond Hettinger def __isub__(self, it): 33631da5b2f69d408ac2448eb04ee2892b8aa3aac79Daniel Stutzbach if it is self: 33731da5b2f69d408ac2448eb04ee2892b8aa3aac79Daniel Stutzbach self.clear() 33831da5b2f69d408ac2448eb04ee2892b8aa3aac79Daniel Stutzbach else: 33931da5b2f69d408ac2448eb04ee2892b8aa3aac79Daniel Stutzbach for value in it: 34031da5b2f69d408ac2448eb04ee2892b8aa3aac79Daniel Stutzbach self.discard(value) 341cd16bf640405065e4702539632ce577536207d88Guido van Rossum return self 342cd16bf640405065e4702539632ce577536207d88Guido van Rossum 343cd16bf640405065e4702539632ce577536207d88Guido van RossumMutableSet.register(set) 344cd16bf640405065e4702539632ce577536207d88Guido van Rossum 345cd16bf640405065e4702539632ce577536207d88Guido van Rossum 346cd16bf640405065e4702539632ce577536207d88Guido van Rossum### MAPPINGS ### 347cd16bf640405065e4702539632ce577536207d88Guido van Rossum 348cd16bf640405065e4702539632ce577536207d88Guido van Rossum 34974b6495b344303a84bf5e51ff388d8200dad4f64Raymond Hettingerclass Mapping(Sized, Iterable, Container): 350cd16bf640405065e4702539632ce577536207d88Guido van Rossum 351cd16bf640405065e4702539632ce577536207d88Guido van Rossum @abstractmethod 352cd16bf640405065e4702539632ce577536207d88Guido van Rossum def __getitem__(self, key): 353cd16bf640405065e4702539632ce577536207d88Guido van Rossum raise KeyError 354cd16bf640405065e4702539632ce577536207d88Guido van Rossum 355cd16bf640405065e4702539632ce577536207d88Guido van Rossum def get(self, key, default=None): 356cd16bf640405065e4702539632ce577536207d88Guido van Rossum try: 357cd16bf640405065e4702539632ce577536207d88Guido van Rossum return self[key] 358cd16bf640405065e4702539632ce577536207d88Guido van Rossum except KeyError: 359cd16bf640405065e4702539632ce577536207d88Guido van Rossum return default 360cd16bf640405065e4702539632ce577536207d88Guido van Rossum 361cd16bf640405065e4702539632ce577536207d88Guido van Rossum def __contains__(self, key): 362cd16bf640405065e4702539632ce577536207d88Guido van Rossum try: 363cd16bf640405065e4702539632ce577536207d88Guido van Rossum self[key] 364cd16bf640405065e4702539632ce577536207d88Guido van Rossum except KeyError: 365cd16bf640405065e4702539632ce577536207d88Guido van Rossum return False 366cd16bf640405065e4702539632ce577536207d88Guido van Rossum else: 367cd16bf640405065e4702539632ce577536207d88Guido van Rossum return True 368cd16bf640405065e4702539632ce577536207d88Guido van Rossum 369cd16bf640405065e4702539632ce577536207d88Guido van Rossum def keys(self): 370cd16bf640405065e4702539632ce577536207d88Guido van Rossum return KeysView(self) 371cd16bf640405065e4702539632ce577536207d88Guido van Rossum 372cd16bf640405065e4702539632ce577536207d88Guido van Rossum def items(self): 373cd16bf640405065e4702539632ce577536207d88Guido van Rossum return ItemsView(self) 374cd16bf640405065e4702539632ce577536207d88Guido van Rossum 375cd16bf640405065e4702539632ce577536207d88Guido van Rossum def values(self): 376cd16bf640405065e4702539632ce577536207d88Guido van Rossum return ValuesView(self) 377cd16bf640405065e4702539632ce577536207d88Guido van Rossum 378b9da9bc0a04b718e8395e2e88c3053ab944579b7Raymond Hettinger def __eq__(self, other): 3794ad6bd5482514631680cebea3cdf06c56b87bac8Benjamin Peterson if not isinstance(other, Mapping): 3804ad6bd5482514631680cebea3cdf06c56b87bac8Benjamin Peterson return NotImplemented 3814ad6bd5482514631680cebea3cdf06c56b87bac8Benjamin Peterson return dict(self.items()) == dict(other.items()) 382b9da9bc0a04b718e8395e2e88c3053ab944579b7Raymond Hettinger 383b9da9bc0a04b718e8395e2e88c3053ab944579b7Raymond Hettinger def __ne__(self, other): 384554c8b856cbeb29f3fef0350846aef442832acacRaymond Hettinger return not (self == other) 385cd16bf640405065e4702539632ce577536207d88Guido van Rossum 3862202f877b1fdd13ae94dd7dc559b44903baf2f99Christian Heimes 387bfd061218b153f1d30b6bd344e947b4ae0fd49a5Raymond Hettingerclass MappingView(Sized): 388cd16bf640405065e4702539632ce577536207d88Guido van Rossum 389cd16bf640405065e4702539632ce577536207d88Guido van Rossum def __init__(self, mapping): 390cd16bf640405065e4702539632ce577536207d88Guido van Rossum self._mapping = mapping 391cd16bf640405065e4702539632ce577536207d88Guido van Rossum 392cd16bf640405065e4702539632ce577536207d88Guido van Rossum def __len__(self): 393cd16bf640405065e4702539632ce577536207d88Guido van Rossum return len(self._mapping) 394cd16bf640405065e4702539632ce577536207d88Guido van Rossum 39589fc2b78214b97f7bc5d3fcf32d9e4cb9940c1ddRaymond Hettinger def __repr__(self): 39689fc2b78214b97f7bc5d3fcf32d9e4cb9940c1ddRaymond Hettinger return '{0.__class__.__name__}({0._mapping!r})'.format(self) 39789fc2b78214b97f7bc5d3fcf32d9e4cb9940c1ddRaymond Hettinger 398cd16bf640405065e4702539632ce577536207d88Guido van Rossum 399cd16bf640405065e4702539632ce577536207d88Guido van Rossumclass KeysView(MappingView, Set): 400cd16bf640405065e4702539632ce577536207d88Guido van Rossum 4019117c751488a98810d758f15b3113527beb920efRaymond Hettinger @classmethod 4029117c751488a98810d758f15b3113527beb920efRaymond Hettinger def _from_iterable(self, it): 4039117c751488a98810d758f15b3113527beb920efRaymond Hettinger return set(it) 4049117c751488a98810d758f15b3113527beb920efRaymond Hettinger 405cd16bf640405065e4702539632ce577536207d88Guido van Rossum def __contains__(self, key): 406cd16bf640405065e4702539632ce577536207d88Guido van Rossum return key in self._mapping 407cd16bf640405065e4702539632ce577536207d88Guido van Rossum 408cd16bf640405065e4702539632ce577536207d88Guido van Rossum def __iter__(self): 409cd16bf640405065e4702539632ce577536207d88Guido van Rossum for key in self._mapping: 410cd16bf640405065e4702539632ce577536207d88Guido van Rossum yield key 411cd16bf640405065e4702539632ce577536207d88Guido van Rossum 412f83be4e3f353c4cfb53a22793dd1394797988c30Christian HeimesKeysView.register(dict_keys) 413cd16bf640405065e4702539632ce577536207d88Guido van Rossum 414cd16bf640405065e4702539632ce577536207d88Guido van Rossum 415cd16bf640405065e4702539632ce577536207d88Guido van Rossumclass ItemsView(MappingView, Set): 416cd16bf640405065e4702539632ce577536207d88Guido van Rossum 4179117c751488a98810d758f15b3113527beb920efRaymond Hettinger @classmethod 4189117c751488a98810d758f15b3113527beb920efRaymond Hettinger def _from_iterable(self, it): 4199117c751488a98810d758f15b3113527beb920efRaymond Hettinger return set(it) 4209117c751488a98810d758f15b3113527beb920efRaymond Hettinger 421cd16bf640405065e4702539632ce577536207d88Guido van Rossum def __contains__(self, item): 422cd16bf640405065e4702539632ce577536207d88Guido van Rossum key, value = item 423cd16bf640405065e4702539632ce577536207d88Guido van Rossum try: 424cd16bf640405065e4702539632ce577536207d88Guido van Rossum v = self._mapping[key] 425cd16bf640405065e4702539632ce577536207d88Guido van Rossum except KeyError: 426cd16bf640405065e4702539632ce577536207d88Guido van Rossum return False 427cd16bf640405065e4702539632ce577536207d88Guido van Rossum else: 428cd16bf640405065e4702539632ce577536207d88Guido van Rossum return v == value 429cd16bf640405065e4702539632ce577536207d88Guido van Rossum 430cd16bf640405065e4702539632ce577536207d88Guido van Rossum def __iter__(self): 431cd16bf640405065e4702539632ce577536207d88Guido van Rossum for key in self._mapping: 432cd16bf640405065e4702539632ce577536207d88Guido van Rossum yield (key, self._mapping[key]) 433cd16bf640405065e4702539632ce577536207d88Guido van Rossum 434f83be4e3f353c4cfb53a22793dd1394797988c30Christian HeimesItemsView.register(dict_items) 435cd16bf640405065e4702539632ce577536207d88Guido van Rossum 436cd16bf640405065e4702539632ce577536207d88Guido van Rossum 437cd16bf640405065e4702539632ce577536207d88Guido van Rossumclass ValuesView(MappingView): 438cd16bf640405065e4702539632ce577536207d88Guido van Rossum 439cd16bf640405065e4702539632ce577536207d88Guido van Rossum def __contains__(self, value): 440cd16bf640405065e4702539632ce577536207d88Guido van Rossum for key in self._mapping: 441cd16bf640405065e4702539632ce577536207d88Guido van Rossum if value == self._mapping[key]: 442cd16bf640405065e4702539632ce577536207d88Guido van Rossum return True 443cd16bf640405065e4702539632ce577536207d88Guido van Rossum return False 444cd16bf640405065e4702539632ce577536207d88Guido van Rossum 445cd16bf640405065e4702539632ce577536207d88Guido van Rossum def __iter__(self): 446cd16bf640405065e4702539632ce577536207d88Guido van Rossum for key in self._mapping: 447cd16bf640405065e4702539632ce577536207d88Guido van Rossum yield self._mapping[key] 448cd16bf640405065e4702539632ce577536207d88Guido van Rossum 449f83be4e3f353c4cfb53a22793dd1394797988c30Christian HeimesValuesView.register(dict_values) 450cd16bf640405065e4702539632ce577536207d88Guido van Rossum 451cd16bf640405065e4702539632ce577536207d88Guido van Rossum 452cd16bf640405065e4702539632ce577536207d88Guido van Rossumclass MutableMapping(Mapping): 453cd16bf640405065e4702539632ce577536207d88Guido van Rossum 454cd16bf640405065e4702539632ce577536207d88Guido van Rossum @abstractmethod 455cd16bf640405065e4702539632ce577536207d88Guido van Rossum def __setitem__(self, key, value): 456cd16bf640405065e4702539632ce577536207d88Guido van Rossum raise KeyError 457cd16bf640405065e4702539632ce577536207d88Guido van Rossum 458cd16bf640405065e4702539632ce577536207d88Guido van Rossum @abstractmethod 459cd16bf640405065e4702539632ce577536207d88Guido van Rossum def __delitem__(self, key): 460cd16bf640405065e4702539632ce577536207d88Guido van Rossum raise KeyError 461cd16bf640405065e4702539632ce577536207d88Guido van Rossum 462cd16bf640405065e4702539632ce577536207d88Guido van Rossum __marker = object() 463cd16bf640405065e4702539632ce577536207d88Guido van Rossum 464cd16bf640405065e4702539632ce577536207d88Guido van Rossum def pop(self, key, default=__marker): 465cd16bf640405065e4702539632ce577536207d88Guido van Rossum try: 466cd16bf640405065e4702539632ce577536207d88Guido van Rossum value = self[key] 467cd16bf640405065e4702539632ce577536207d88Guido van Rossum except KeyError: 468cd16bf640405065e4702539632ce577536207d88Guido van Rossum if default is self.__marker: 469cd16bf640405065e4702539632ce577536207d88Guido van Rossum raise 470cd16bf640405065e4702539632ce577536207d88Guido van Rossum return default 471cd16bf640405065e4702539632ce577536207d88Guido van Rossum else: 472cd16bf640405065e4702539632ce577536207d88Guido van Rossum del self[key] 473cd16bf640405065e4702539632ce577536207d88Guido van Rossum return value 474cd16bf640405065e4702539632ce577536207d88Guido van Rossum 475cd16bf640405065e4702539632ce577536207d88Guido van Rossum def popitem(self): 476cd16bf640405065e4702539632ce577536207d88Guido van Rossum try: 477cd16bf640405065e4702539632ce577536207d88Guido van Rossum key = next(iter(self)) 478cd16bf640405065e4702539632ce577536207d88Guido van Rossum except StopIteration: 479cd16bf640405065e4702539632ce577536207d88Guido van Rossum raise KeyError 480cd16bf640405065e4702539632ce577536207d88Guido van Rossum value = self[key] 481cd16bf640405065e4702539632ce577536207d88Guido van Rossum del self[key] 482cd16bf640405065e4702539632ce577536207d88Guido van Rossum return key, value 483cd16bf640405065e4702539632ce577536207d88Guido van Rossum 484cd16bf640405065e4702539632ce577536207d88Guido van Rossum def clear(self): 485cd16bf640405065e4702539632ce577536207d88Guido van Rossum try: 486cd16bf640405065e4702539632ce577536207d88Guido van Rossum while True: 487cd16bf640405065e4702539632ce577536207d88Guido van Rossum self.popitem() 488cd16bf640405065e4702539632ce577536207d88Guido van Rossum except KeyError: 489cd16bf640405065e4702539632ce577536207d88Guido van Rossum pass 490cd16bf640405065e4702539632ce577536207d88Guido van Rossum 491b214e90e010f86b7d899cd88ada8c68fff90c870Mark Dickinson def update(*args, **kwds): 492b214e90e010f86b7d899cd88ada8c68fff90c870Mark Dickinson if len(args) > 2: 493b214e90e010f86b7d899cd88ada8c68fff90c870Mark Dickinson raise TypeError("update() takes at most 2 positional " 494b214e90e010f86b7d899cd88ada8c68fff90c870Mark Dickinson "arguments ({} given)".format(len(args))) 495b214e90e010f86b7d899cd88ada8c68fff90c870Mark Dickinson elif not args: 496b214e90e010f86b7d899cd88ada8c68fff90c870Mark Dickinson raise TypeError("update() takes at least 1 argument (0 given)") 497b214e90e010f86b7d899cd88ada8c68fff90c870Mark Dickinson self = args[0] 498b214e90e010f86b7d899cd88ada8c68fff90c870Mark Dickinson other = args[1] if len(args) >= 2 else () 499b214e90e010f86b7d899cd88ada8c68fff90c870Mark Dickinson 500cd16bf640405065e4702539632ce577536207d88Guido van Rossum if isinstance(other, Mapping): 501cd16bf640405065e4702539632ce577536207d88Guido van Rossum for key in other: 502cd16bf640405065e4702539632ce577536207d88Guido van Rossum self[key] = other[key] 503cd16bf640405065e4702539632ce577536207d88Guido van Rossum elif hasattr(other, "keys"): 504cd16bf640405065e4702539632ce577536207d88Guido van Rossum for key in other.keys(): 505cd16bf640405065e4702539632ce577536207d88Guido van Rossum self[key] = other[key] 506cd16bf640405065e4702539632ce577536207d88Guido van Rossum else: 507cd16bf640405065e4702539632ce577536207d88Guido van Rossum for key, value in other: 508cd16bf640405065e4702539632ce577536207d88Guido van Rossum self[key] = value 509cd16bf640405065e4702539632ce577536207d88Guido van Rossum for key, value in kwds.items(): 510cd16bf640405065e4702539632ce577536207d88Guido van Rossum self[key] = value 511cd16bf640405065e4702539632ce577536207d88Guido van Rossum 512b9da9bc0a04b718e8395e2e88c3053ab944579b7Raymond Hettinger def setdefault(self, key, default=None): 513b9da9bc0a04b718e8395e2e88c3053ab944579b7Raymond Hettinger try: 514b9da9bc0a04b718e8395e2e88c3053ab944579b7Raymond Hettinger return self[key] 515b9da9bc0a04b718e8395e2e88c3053ab944579b7Raymond Hettinger except KeyError: 516b9da9bc0a04b718e8395e2e88c3053ab944579b7Raymond Hettinger self[key] = default 517b9da9bc0a04b718e8395e2e88c3053ab944579b7Raymond Hettinger return default 518b9da9bc0a04b718e8395e2e88c3053ab944579b7Raymond Hettinger 519cd16bf640405065e4702539632ce577536207d88Guido van RossumMutableMapping.register(dict) 520cd16bf640405065e4702539632ce577536207d88Guido van Rossum 521cd16bf640405065e4702539632ce577536207d88Guido van Rossum 522cd16bf640405065e4702539632ce577536207d88Guido van Rossum### SEQUENCES ### 523cd16bf640405065e4702539632ce577536207d88Guido van Rossum 524cd16bf640405065e4702539632ce577536207d88Guido van Rossum 52574b6495b344303a84bf5e51ff388d8200dad4f64Raymond Hettingerclass Sequence(Sized, Iterable, Container): 526cd16bf640405065e4702539632ce577536207d88Guido van Rossum 527cd16bf640405065e4702539632ce577536207d88Guido van Rossum """All the operations on a read-only sequence. 528cd16bf640405065e4702539632ce577536207d88Guido van Rossum 529cd16bf640405065e4702539632ce577536207d88Guido van Rossum Concrete subclasses must override __new__ or __init__, 530cd16bf640405065e4702539632ce577536207d88Guido van Rossum __getitem__, and __len__. 531cd16bf640405065e4702539632ce577536207d88Guido van Rossum """ 532cd16bf640405065e4702539632ce577536207d88Guido van Rossum 533cd16bf640405065e4702539632ce577536207d88Guido van Rossum @abstractmethod 534cd16bf640405065e4702539632ce577536207d88Guido van Rossum def __getitem__(self, index): 535cd16bf640405065e4702539632ce577536207d88Guido van Rossum raise IndexError 536cd16bf640405065e4702539632ce577536207d88Guido van Rossum 537cd16bf640405065e4702539632ce577536207d88Guido van Rossum def __iter__(self): 538cd16bf640405065e4702539632ce577536207d88Guido van Rossum i = 0 53971909423fd92862b869d8019d5e10c29bf946cb0Raymond Hettinger try: 54071909423fd92862b869d8019d5e10c29bf946cb0Raymond Hettinger while True: 541cd16bf640405065e4702539632ce577536207d88Guido van Rossum v = self[i] 54271909423fd92862b869d8019d5e10c29bf946cb0Raymond Hettinger yield v 54371909423fd92862b869d8019d5e10c29bf946cb0Raymond Hettinger i += 1 54471909423fd92862b869d8019d5e10c29bf946cb0Raymond Hettinger except IndexError: 54571909423fd92862b869d8019d5e10c29bf946cb0Raymond Hettinger return 546cd16bf640405065e4702539632ce577536207d88Guido van Rossum 547cd16bf640405065e4702539632ce577536207d88Guido van Rossum def __contains__(self, value): 548cd16bf640405065e4702539632ce577536207d88Guido van Rossum for v in self: 549cd16bf640405065e4702539632ce577536207d88Guido van Rossum if v == value: 550cd16bf640405065e4702539632ce577536207d88Guido van Rossum return True 551cd16bf640405065e4702539632ce577536207d88Guido van Rossum return False 552cd16bf640405065e4702539632ce577536207d88Guido van Rossum 553cd16bf640405065e4702539632ce577536207d88Guido van Rossum def __reversed__(self): 554cd16bf640405065e4702539632ce577536207d88Guido van Rossum for i in reversed(range(len(self))): 555cd16bf640405065e4702539632ce577536207d88Guido van Rossum yield self[i] 556cd16bf640405065e4702539632ce577536207d88Guido van Rossum 557cd16bf640405065e4702539632ce577536207d88Guido van Rossum def index(self, value): 558cd16bf640405065e4702539632ce577536207d88Guido van Rossum for i, v in enumerate(self): 559cd16bf640405065e4702539632ce577536207d88Guido van Rossum if v == value: 560cd16bf640405065e4702539632ce577536207d88Guido van Rossum return i 561cd16bf640405065e4702539632ce577536207d88Guido van Rossum raise ValueError 562cd16bf640405065e4702539632ce577536207d88Guido van Rossum 563cd16bf640405065e4702539632ce577536207d88Guido van Rossum def count(self, value): 564cd16bf640405065e4702539632ce577536207d88Guido van Rossum return sum(1 for v in self if v == value) 565cd16bf640405065e4702539632ce577536207d88Guido van Rossum 566cd16bf640405065e4702539632ce577536207d88Guido van RossumSequence.register(tuple) 5673172c5d263eeffff1e89d03d79be3ccc1d60fbdeGuido van RossumSequence.register(str) 5689aa53c2f0151032c5592d0c8b112fc35d7f77078Raymond HettingerSequence.register(range) 569d05eb0043e597cf2d5c429d0e554fd39364e36b0Guido van Rossum 570d05eb0043e597cf2d5c429d0e554fd39364e36b0Guido van Rossum 571d05eb0043e597cf2d5c429d0e554fd39364e36b0Guido van Rossumclass ByteString(Sequence): 572d05eb0043e597cf2d5c429d0e554fd39364e36b0Guido van Rossum 573d05eb0043e597cf2d5c429d0e554fd39364e36b0Guido van Rossum """This unifies bytes and bytearray. 574d05eb0043e597cf2d5c429d0e554fd39364e36b0Guido van Rossum 575d05eb0043e597cf2d5c429d0e554fd39364e36b0Guido van Rossum XXX Should add all their methods. 576d05eb0043e597cf2d5c429d0e554fd39364e36b0Guido van Rossum """ 577d05eb0043e597cf2d5c429d0e554fd39364e36b0Guido van Rossum 578d05eb0043e597cf2d5c429d0e554fd39364e36b0Guido van RossumByteString.register(bytes) 579d05eb0043e597cf2d5c429d0e554fd39364e36b0Guido van RossumByteString.register(bytearray) 580cd16bf640405065e4702539632ce577536207d88Guido van Rossum 581cd16bf640405065e4702539632ce577536207d88Guido van Rossum 582cd16bf640405065e4702539632ce577536207d88Guido van Rossumclass MutableSequence(Sequence): 583cd16bf640405065e4702539632ce577536207d88Guido van Rossum 584cd16bf640405065e4702539632ce577536207d88Guido van Rossum @abstractmethod 585cd16bf640405065e4702539632ce577536207d88Guido van Rossum def __setitem__(self, index, value): 586cd16bf640405065e4702539632ce577536207d88Guido van Rossum raise IndexError 587cd16bf640405065e4702539632ce577536207d88Guido van Rossum 588cd16bf640405065e4702539632ce577536207d88Guido van Rossum @abstractmethod 589cd16bf640405065e4702539632ce577536207d88Guido van Rossum def __delitem__(self, index): 590cd16bf640405065e4702539632ce577536207d88Guido van Rossum raise IndexError 591cd16bf640405065e4702539632ce577536207d88Guido van Rossum 592cd16bf640405065e4702539632ce577536207d88Guido van Rossum @abstractmethod 593cd16bf640405065e4702539632ce577536207d88Guido van Rossum def insert(self, index, value): 594cd16bf640405065e4702539632ce577536207d88Guido van Rossum raise IndexError 595cd16bf640405065e4702539632ce577536207d88Guido van Rossum 596cd16bf640405065e4702539632ce577536207d88Guido van Rossum def append(self, value): 597cd16bf640405065e4702539632ce577536207d88Guido van Rossum self.insert(len(self), value) 598cd16bf640405065e4702539632ce577536207d88Guido van Rossum 599cd16bf640405065e4702539632ce577536207d88Guido van Rossum def reverse(self): 600cd16bf640405065e4702539632ce577536207d88Guido van Rossum n = len(self) 601cd16bf640405065e4702539632ce577536207d88Guido van Rossum for i in range(n//2): 602cd16bf640405065e4702539632ce577536207d88Guido van Rossum self[i], self[n-i-1] = self[n-i-1], self[i] 603cd16bf640405065e4702539632ce577536207d88Guido van Rossum 604cd16bf640405065e4702539632ce577536207d88Guido van Rossum def extend(self, values): 605cd16bf640405065e4702539632ce577536207d88Guido van Rossum for v in values: 606cd16bf640405065e4702539632ce577536207d88Guido van Rossum self.append(v) 607cd16bf640405065e4702539632ce577536207d88Guido van Rossum 608cd16bf640405065e4702539632ce577536207d88Guido van Rossum def pop(self, index=-1): 609cd16bf640405065e4702539632ce577536207d88Guido van Rossum v = self[index] 610cd16bf640405065e4702539632ce577536207d88Guido van Rossum del self[index] 611cd16bf640405065e4702539632ce577536207d88Guido van Rossum return v 612cd16bf640405065e4702539632ce577536207d88Guido van Rossum 613cd16bf640405065e4702539632ce577536207d88Guido van Rossum def remove(self, value): 614cd16bf640405065e4702539632ce577536207d88Guido van Rossum del self[self.index(value)] 615cd16bf640405065e4702539632ce577536207d88Guido van Rossum 616cd16bf640405065e4702539632ce577536207d88Guido van Rossum def __iadd__(self, values): 617cd16bf640405065e4702539632ce577536207d88Guido van Rossum self.extend(values) 618c384b226d765d5f57a909df8da3f4fcdfb4b7246Raymond Hettinger return self 619cd16bf640405065e4702539632ce577536207d88Guido van Rossum 620cd16bf640405065e4702539632ce577536207d88Guido van RossumMutableSequence.register(list) 621d05eb0043e597cf2d5c429d0e554fd39364e36b0Guido van RossumMutableSequence.register(bytearray) # Multiply inheriting, see ByteString 622