1ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh# Copyright 2007 Google, Inc. All Rights Reserved. 2ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh# Licensed to PSF under a Contributor Agreement. 3ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 4ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh"""Abstract Base Classes (ABCs) for collections, according to PEP 3119. 5ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 6ffab958fd8d42ed7227d83007350e61555a1fa36Andrew HsiehDON'T USE THIS MODULE DIRECTLY! The classes here should be imported 7ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsiehvia collections; they are defined here only to alleviate certain 8ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsiehbootstrapping issues. Unit tests are in test_collections. 9ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh""" 10ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 11ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsiehfrom abc import ABCMeta, abstractmethod 12ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsiehimport sys 13ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 14ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh__all__ = ["Hashable", "Iterable", "Iterator", 15ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh "Sized", "Container", "Callable", 16ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh "Set", "MutableSet", 17ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh "Mapping", "MutableMapping", 18ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh "MappingView", "KeysView", "ItemsView", "ValuesView", 19ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh "Sequence", "MutableSequence", 20ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh ] 21ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 22ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh### ONE-TRICK PONIES ### 23ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 24ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsiehdef _hasattr(C, attr): 25ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh try: 26ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return any(attr in B.__dict__ for B in C.__mro__) 27ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh except AttributeError: 28ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh # Old-style class 29ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return hasattr(C, attr) 30ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 31ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 32ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsiehclass Hashable: 33ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh __metaclass__ = ABCMeta 34ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 35ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh @abstractmethod 36ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def __hash__(self): 37ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return 0 38ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 39ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh @classmethod 40ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def __subclasshook__(cls, C): 41ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh if cls is Hashable: 42ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh try: 43ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh for B in C.__mro__: 44ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh if "__hash__" in B.__dict__: 45ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh if B.__dict__["__hash__"]: 46ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return True 47ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh break 48ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh except AttributeError: 49ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh # Old-style class 50ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh if getattr(C, "__hash__", None): 51ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return True 52ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return NotImplemented 53ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 54ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 55ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsiehclass Iterable: 56ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh __metaclass__ = ABCMeta 57ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 58ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh @abstractmethod 59ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def __iter__(self): 60ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh while False: 61ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh yield None 62ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 63ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh @classmethod 64ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def __subclasshook__(cls, C): 65ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh if cls is Iterable: 66ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh if _hasattr(C, "__iter__"): 67ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return True 68ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return NotImplemented 69ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 70ffab958fd8d42ed7227d83007350e61555a1fa36Andrew HsiehIterable.register(str) 71ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 72ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 73ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsiehclass Iterator(Iterable): 74ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 75ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh @abstractmethod 76ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def next(self): 77ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 'Return the next item from the iterator. When exhausted, raise StopIteration' 78ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh raise StopIteration 79ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 80ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def __iter__(self): 81ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return self 82ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 83ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh @classmethod 84ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def __subclasshook__(cls, C): 85ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh if cls is Iterator: 86ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh if _hasattr(C, "next") and _hasattr(C, "__iter__"): 87ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return True 88ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return NotImplemented 89ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 90ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 91ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsiehclass Sized: 92ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh __metaclass__ = ABCMeta 93ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 94ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh @abstractmethod 95ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def __len__(self): 96ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return 0 97ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 98ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh @classmethod 99ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def __subclasshook__(cls, C): 100ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh if cls is Sized: 101ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh if _hasattr(C, "__len__"): 102ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return True 103ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return NotImplemented 104ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 105ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 106ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsiehclass Container: 107ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh __metaclass__ = ABCMeta 108ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 109ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh @abstractmethod 110ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def __contains__(self, x): 111ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return False 112ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 113ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh @classmethod 114ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def __subclasshook__(cls, C): 115ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh if cls is Container: 116ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh if _hasattr(C, "__contains__"): 117ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return True 118ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return NotImplemented 119ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 120ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 121ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsiehclass Callable: 122ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh __metaclass__ = ABCMeta 123ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 124ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh @abstractmethod 125ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def __call__(self, *args, **kwds): 126ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return False 127ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 128ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh @classmethod 129ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def __subclasshook__(cls, C): 130ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh if cls is Callable: 131ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh if _hasattr(C, "__call__"): 132ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return True 133ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return NotImplemented 134ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 135ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 136ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh### SETS ### 137ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 138ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 139ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsiehclass Set(Sized, Iterable, Container): 140ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh """A set is a finite, iterable container. 141ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 142ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh This class provides concrete generic implementations of all 143ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh methods except for __contains__, __iter__ and __len__. 144ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 145ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh To override the comparisons (presumably for speed, as the 146ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh semantics are fixed), all you have to do is redefine __le__ and 147ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh then the other operations will automatically follow suit. 148ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh """ 149ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 150ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def __le__(self, other): 151ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh if not isinstance(other, Set): 152ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return NotImplemented 153ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh if len(self) > len(other): 154ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return False 155ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh for elem in self: 156ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh if elem not in other: 157ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return False 158ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return True 159ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 160ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def __lt__(self, other): 161ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh if not isinstance(other, Set): 162ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return NotImplemented 163ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return len(self) < len(other) and self.__le__(other) 164ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 165ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def __gt__(self, other): 166ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh if not isinstance(other, Set): 167ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return NotImplemented 168ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return other < self 169ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 170ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def __ge__(self, other): 171ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh if not isinstance(other, Set): 172ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return NotImplemented 173ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return other <= self 174ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 175ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def __eq__(self, other): 176ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh if not isinstance(other, Set): 177ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return NotImplemented 178ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return len(self) == len(other) and self.__le__(other) 179ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 180ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def __ne__(self, other): 181ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return not (self == other) 182ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 183ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh @classmethod 184ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def _from_iterable(cls, it): 185ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh '''Construct an instance of the class from any iterable input. 186ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 187ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh Must override this method if the class constructor signature 188ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh does not accept an iterable for an input. 189ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh ''' 190ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return cls(it) 191ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 192ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def __and__(self, other): 193ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh if not isinstance(other, Iterable): 194ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return NotImplemented 195ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return self._from_iterable(value for value in other if value in self) 196ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 197ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def isdisjoint(self, other): 198ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 'Return True if two sets have a null intersection.' 199ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh for value in other: 200ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh if value in self: 201ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return False 202ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return True 203ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 204ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def __or__(self, other): 205ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh if not isinstance(other, Iterable): 206ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return NotImplemented 207ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh chain = (e for s in (self, other) for e in s) 208ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return self._from_iterable(chain) 209ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 210ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def __sub__(self, other): 211ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh if not isinstance(other, Set): 212ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh if not isinstance(other, Iterable): 213ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return NotImplemented 214ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh other = self._from_iterable(other) 215ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return self._from_iterable(value for value in self 216ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh if value not in other) 217ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 218ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def __xor__(self, other): 219ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh if not isinstance(other, Set): 220ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh if not isinstance(other, Iterable): 221ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return NotImplemented 222ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh other = self._from_iterable(other) 223ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return (self - other) | (other - self) 224ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 225ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh # Sets are not hashable by default, but subclasses can change this 226ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh __hash__ = None 227ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 228ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def _hash(self): 229ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh """Compute the hash value of a set. 230ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 231ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh Note that we don't define __hash__: not all sets are hashable. 232ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh But if you define a hashable set type, its __hash__ should 233ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh call this function. 234ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 235ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh This must be compatible __eq__. 236ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 237ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh All sets ought to compare equal if they contain the same 238ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh elements, regardless of how they are implemented, and 239ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh regardless of the order of the elements; so there's not much 240ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh freedom for __eq__ or __hash__. We match the algorithm used 241ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh by the built-in frozenset type. 242ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh """ 243ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh MAX = sys.maxint 244ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh MASK = 2 * MAX + 1 245ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh n = len(self) 246ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh h = 1927868237 * (n + 1) 247ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh h &= MASK 248ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh for x in self: 249ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh hx = hash(x) 250ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh h ^= (hx ^ (hx << 16) ^ 89869747) * 3644798167 251ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh h &= MASK 252ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh h = h * 69069 + 907133923 253ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh h &= MASK 254ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh if h > MAX: 255ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh h -= MASK + 1 256ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh if h == -1: 257ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh h = 590923713 258ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return h 259ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 260ffab958fd8d42ed7227d83007350e61555a1fa36Andrew HsiehSet.register(frozenset) 261ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 262ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 263ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsiehclass MutableSet(Set): 264ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh """A mutable set is a finite, iterable container. 265ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 266ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh This class provides concrete generic implementations of all 267ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh methods except for __contains__, __iter__, __len__, 268ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh add(), and discard(). 269ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 270ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh To override the comparisons (presumably for speed, as the 271ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh semantics are fixed), all you have to do is redefine __le__ and 272ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh then the other operations will automatically follow suit. 273ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh """ 274ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 275ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh @abstractmethod 276ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def add(self, value): 277ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh """Add an element.""" 278ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh raise NotImplementedError 279ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 280ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh @abstractmethod 281ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def discard(self, value): 282ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh """Remove an element. Do not raise an exception if absent.""" 283ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh raise NotImplementedError 284ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 285ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def remove(self, value): 286ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh """Remove an element. If not a member, raise a KeyError.""" 287ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh if value not in self: 288ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh raise KeyError(value) 289ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh self.discard(value) 290ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 291ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def pop(self): 292ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh """Return the popped value. Raise KeyError if empty.""" 293ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh it = iter(self) 294ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh try: 295ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh value = next(it) 296ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh except StopIteration: 297ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh raise KeyError 298ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh self.discard(value) 299ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return value 300ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 301ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def clear(self): 302ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh """This is slow (creates N new iterators!) but effective.""" 303ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh try: 304ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh while True: 305ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh self.pop() 306ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh except KeyError: 307ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh pass 308ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 309ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def __ior__(self, it): 310ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh for value in it: 311ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh self.add(value) 312ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return self 313ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 314ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def __iand__(self, it): 315ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh for value in (self - it): 316ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh self.discard(value) 317ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return self 318ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 319ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def __ixor__(self, it): 320ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh if it is self: 321ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh self.clear() 322ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh else: 323ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh if not isinstance(it, Set): 324ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh it = self._from_iterable(it) 325ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh for value in it: 326ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh if value in self: 327ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh self.discard(value) 328ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh else: 329ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh self.add(value) 330ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return self 331ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 332ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def __isub__(self, it): 333ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh if it is self: 334ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh self.clear() 335ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh else: 336ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh for value in it: 337ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh self.discard(value) 338ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return self 339ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 340ffab958fd8d42ed7227d83007350e61555a1fa36Andrew HsiehMutableSet.register(set) 341ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 342ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 343ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh### MAPPINGS ### 344ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 345ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 346ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsiehclass Mapping(Sized, Iterable, Container): 347ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 348ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh """A Mapping is a generic container for associating key/value 349ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh pairs. 350ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 351ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh This class provides concrete generic implementations of all 352ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh methods except for __getitem__, __iter__, and __len__. 353ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 354ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh """ 355ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 356ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh @abstractmethod 357ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def __getitem__(self, key): 358ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh raise KeyError 359ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 360ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def get(self, key, default=None): 361ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 'D.get(k[,d]) -> D[k] if k in D, else d. d defaults to None.' 362ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh try: 363ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return self[key] 364ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh except KeyError: 365ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return default 366ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 367ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def __contains__(self, key): 368ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh try: 369ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh self[key] 370ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh except KeyError: 371ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return False 372ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh else: 373ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return True 374ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 375ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def iterkeys(self): 376ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 'D.iterkeys() -> an iterator over the keys of D' 377ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return iter(self) 378ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 379ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def itervalues(self): 380ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 'D.itervalues() -> an iterator over the values of D' 381ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh for key in self: 382ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh yield self[key] 383ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 384ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def iteritems(self): 385ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 'D.iteritems() -> an iterator over the (key, value) items of D' 386ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh for key in self: 387ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh yield (key, self[key]) 388ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 389ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def keys(self): 390ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh "D.keys() -> list of D's keys" 391ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return list(self) 392ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 393ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def items(self): 394ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh "D.items() -> list of D's (key, value) pairs, as 2-tuples" 395ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return [(key, self[key]) for key in self] 396ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 397ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def values(self): 398ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh "D.values() -> list of D's values" 399ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return [self[key] for key in self] 400ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 401ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh # Mappings are not hashable by default, but subclasses can change this 402ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh __hash__ = None 403ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 404ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def __eq__(self, other): 405ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh if not isinstance(other, Mapping): 406ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return NotImplemented 407ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return dict(self.items()) == dict(other.items()) 408ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 409ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def __ne__(self, other): 410ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return not (self == other) 411ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 412ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsiehclass MappingView(Sized): 413ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 414ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def __init__(self, mapping): 415ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh self._mapping = mapping 416ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 417ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def __len__(self): 418ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return len(self._mapping) 419ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 420ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def __repr__(self): 421ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return '{0.__class__.__name__}({0._mapping!r})'.format(self) 422ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 423ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 424ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsiehclass KeysView(MappingView, Set): 425ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 426ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh @classmethod 427ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def _from_iterable(self, it): 428ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return set(it) 429ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 430ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def __contains__(self, key): 431ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return key in self._mapping 432ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 433ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def __iter__(self): 434ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh for key in self._mapping: 435ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh yield key 436ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 437ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 438ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsiehclass ItemsView(MappingView, Set): 439ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 440ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh @classmethod 441ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def _from_iterable(self, it): 442ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return set(it) 443ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 444ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def __contains__(self, item): 445ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh key, value = item 446ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh try: 447ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh v = self._mapping[key] 448ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh except KeyError: 449ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return False 450ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh else: 451ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return v == value 452ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 453ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def __iter__(self): 454ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh for key in self._mapping: 455ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh yield (key, self._mapping[key]) 456ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 457ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 458ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsiehclass ValuesView(MappingView): 459ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 460ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def __contains__(self, value): 461ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh for key in self._mapping: 462ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh if value == self._mapping[key]: 463ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return True 464ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return False 465ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 466ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def __iter__(self): 467ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh for key in self._mapping: 468ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh yield self._mapping[key] 469ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 470ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 471ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsiehclass MutableMapping(Mapping): 472ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 473ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh """A MutableMapping is a generic container for associating 474ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh key/value pairs. 475ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 476ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh This class provides concrete generic implementations of all 477ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh methods except for __getitem__, __setitem__, __delitem__, 478ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh __iter__, and __len__. 479ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 480ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh """ 481ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 482ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh @abstractmethod 483ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def __setitem__(self, key, value): 484ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh raise KeyError 485ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 486ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh @abstractmethod 487ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def __delitem__(self, key): 488ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh raise KeyError 489ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 490ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh __marker = object() 491ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 492ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def pop(self, key, default=__marker): 493ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh '''D.pop(k[,d]) -> v, remove specified key and return the corresponding value. 494ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh If key is not found, d is returned if given, otherwise KeyError is raised. 495ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh ''' 496ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh try: 497ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh value = self[key] 498ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh except KeyError: 499ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh if default is self.__marker: 500ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh raise 501ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return default 502ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh else: 503ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh del self[key] 504ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return value 505ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 506ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def popitem(self): 507ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh '''D.popitem() -> (k, v), remove and return some (key, value) pair 508ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh as a 2-tuple; but raise KeyError if D is empty. 509ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh ''' 510ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh try: 511ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh key = next(iter(self)) 512ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh except StopIteration: 513ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh raise KeyError 514ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh value = self[key] 515ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh del self[key] 516ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return key, value 517ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 518ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def clear(self): 519ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 'D.clear() -> None. Remove all items from D.' 520ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh try: 521ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh while True: 522ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh self.popitem() 523ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh except KeyError: 524ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh pass 525ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 526ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def update(*args, **kwds): 527ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh ''' D.update([E, ]**F) -> None. Update D from mapping/iterable E and F. 528ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh If E present and has a .keys() method, does: for k in E: D[k] = E[k] 529ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh If E present and lacks .keys() method, does: for (k, v) in E: D[k] = v 530ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh In either case, this is followed by: for k, v in F.items(): D[k] = v 531ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh ''' 532ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh if len(args) > 2: 533ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh raise TypeError("update() takes at most 2 positional " 534ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh "arguments ({} given)".format(len(args))) 535ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh elif not args: 536ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh raise TypeError("update() takes at least 1 argument (0 given)") 537ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh self = args[0] 538ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh other = args[1] if len(args) >= 2 else () 539ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 540ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh if isinstance(other, Mapping): 541ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh for key in other: 542ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh self[key] = other[key] 543ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh elif hasattr(other, "keys"): 544ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh for key in other.keys(): 545ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh self[key] = other[key] 546ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh else: 547ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh for key, value in other: 548ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh self[key] = value 549ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh for key, value in kwds.items(): 550ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh self[key] = value 551ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 552ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def setdefault(self, key, default=None): 553ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 'D.setdefault(k[,d]) -> D.get(k,d), also set D[k]=d if k not in D' 554ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh try: 555ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return self[key] 556ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh except KeyError: 557ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh self[key] = default 558ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return default 559ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 560ffab958fd8d42ed7227d83007350e61555a1fa36Andrew HsiehMutableMapping.register(dict) 561ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 562ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 563ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh### SEQUENCES ### 564ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 565ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 566ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsiehclass Sequence(Sized, Iterable, Container): 567ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh """All the operations on a read-only sequence. 568ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 569ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh Concrete subclasses must override __new__ or __init__, 570ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh __getitem__, and __len__. 571ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh """ 572ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 573ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh @abstractmethod 574ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def __getitem__(self, index): 575ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh raise IndexError 576ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 577ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def __iter__(self): 578ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh i = 0 579ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh try: 580ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh while True: 581ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh v = self[i] 582ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh yield v 583ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh i += 1 584ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh except IndexError: 585ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return 586ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 587ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def __contains__(self, value): 588ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh for v in self: 589ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh if v == value: 590ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return True 591ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return False 592ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 593ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def __reversed__(self): 594ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh for i in reversed(range(len(self))): 595ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh yield self[i] 596ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 597ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def index(self, value): 598ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh '''S.index(value) -> integer -- return first index of value. 599ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh Raises ValueError if the value is not present. 600ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh ''' 601ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh for i, v in enumerate(self): 602ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh if v == value: 603ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return i 604ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh raise ValueError 605ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 606ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def count(self, value): 607ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 'S.count(value) -> integer -- return number of occurrences of value' 608ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return sum(1 for v in self if v == value) 609ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 610ffab958fd8d42ed7227d83007350e61555a1fa36Andrew HsiehSequence.register(tuple) 611ffab958fd8d42ed7227d83007350e61555a1fa36Andrew HsiehSequence.register(basestring) 612ffab958fd8d42ed7227d83007350e61555a1fa36Andrew HsiehSequence.register(buffer) 613ffab958fd8d42ed7227d83007350e61555a1fa36Andrew HsiehSequence.register(xrange) 614ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 615ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 616ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsiehclass MutableSequence(Sequence): 617ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 618ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh """All the operations on a read-only sequence. 619ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 620ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh Concrete subclasses must provide __new__ or __init__, 621ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh __getitem__, __setitem__, __delitem__, __len__, and insert(). 622ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 623ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh """ 624ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 625ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh @abstractmethod 626ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def __setitem__(self, index, value): 627ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh raise IndexError 628ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 629ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh @abstractmethod 630ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def __delitem__(self, index): 631ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh raise IndexError 632ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 633ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh @abstractmethod 634ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def insert(self, index, value): 635ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 'S.insert(index, object) -- insert object before index' 636ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh raise IndexError 637ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 638ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def append(self, value): 639ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 'S.append(object) -- append object to the end of the sequence' 640ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh self.insert(len(self), value) 641ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 642ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def reverse(self): 643ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 'S.reverse() -- reverse *IN PLACE*' 644ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh n = len(self) 645ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh for i in range(n//2): 646ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh self[i], self[n-i-1] = self[n-i-1], self[i] 647ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 648ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def extend(self, values): 649ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 'S.extend(iterable) -- extend sequence by appending elements from the iterable' 650ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh for v in values: 651ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh self.append(v) 652ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 653ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def pop(self, index=-1): 654ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh '''S.pop([index]) -> item -- remove and return item at index (default last). 655ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh Raise IndexError if list is empty or index is out of range. 656ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh ''' 657ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh v = self[index] 658ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh del self[index] 659ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return v 660ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 661ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def remove(self, value): 662ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh '''S.remove(value) -- remove first occurrence of value. 663ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh Raise ValueError if the value is not present. 664ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh ''' 665ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh del self[self.index(value)] 666ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 667ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh def __iadd__(self, values): 668ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh self.extend(values) 669ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh return self 670ffab958fd8d42ed7227d83007350e61555a1fa36Andrew Hsieh 671ffab958fd8d42ed7227d83007350e61555a1fa36Andrew HsiehMutableSequence.register(list) 672