183760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh"""Classes to represent arbitrary sets (including sets of sets). 283760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 383760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew HsiehThis module implements sets using dictionaries whose values are 483760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsiehignored. The usual operations (union, intersection, deletion, etc.) 583760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsiehare provided as both methods and operators. 683760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 783760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew HsiehImportant: sets are not sequences! While they support 'x in s', 883760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh'len(s)', and 'for x in s', none of those operations are unique for 983760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsiehsequences; for example, mappings support all three as well. The 1083760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsiehcharacteristic operation for sequences is subscripting with small 1183760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsiehintegers: s[i], for i in range(len(s)). Sets don't support 1283760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsiehsubscripting at all. Also, sequences allow multiple occurrences and 1383760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsiehtheir elements have a definite order; sets on the other hand don't 1483760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsiehrecord multiple occurrences and don't remember the order of element 1583760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsiehinsertion (which is why they don't support s[i]). 1683760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 1783760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew HsiehThe following classes are provided: 1883760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 1983760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew HsiehBaseSet -- All the operations common to both mutable and immutable 2083760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh sets. This is an abstract class, not meant to be directly 2183760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh instantiated. 2283760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 2383760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew HsiehSet -- Mutable sets, subclass of BaseSet; not hashable. 2483760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 2583760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew HsiehImmutableSet -- Immutable sets, subclass of BaseSet; hashable. 2683760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh An iterable argument is mandatory to create an ImmutableSet. 2783760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 2883760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh_TemporarilyImmutableSet -- A wrapper around a Set, hashable, 2983760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh giving the same hash value as the immutable set equivalent 3083760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh would have. Do not use this class directly. 3183760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 3283760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew HsiehOnly hashable objects can be added to a Set. In particular, you cannot 3383760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsiehreally add a Set as an element to another Set; if you try, what is 3483760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsiehactually added is an ImmutableSet built from it (it compares equal to 3583760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsiehthe one you tried adding). 3683760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 3783760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew HsiehWhen you ask if `x in y' where x is a Set and y is a Set or 3883760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew HsiehImmutableSet, x is wrapped into a _TemporarilyImmutableSet z, and 3983760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsiehwhat's tested is actually `z in y'. 4083760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 4183760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh""" 4283760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 4383760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh# Code history: 4483760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh# 4583760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh# - Greg V. Wilson wrote the first version, using a different approach 4683760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh# to the mutable/immutable problem, and inheriting from dict. 4783760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh# 4883760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh# - Alex Martelli modified Greg's version to implement the current 4983760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh# Set/ImmutableSet approach, and make the data an attribute. 5083760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh# 5183760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh# - Guido van Rossum rewrote much of the code, made some API changes, 5283760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh# and cleaned up the docstrings. 5383760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh# 5483760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh# - Raymond Hettinger added a number of speedups and other 5583760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh# improvements. 5683760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 5783760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsiehfrom itertools import ifilter, ifilterfalse 5883760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 5983760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh__all__ = ['BaseSet', 'Set', 'ImmutableSet'] 6083760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 6183760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsiehimport warnings 6283760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsiehwarnings.warn("the sets module is deprecated", DeprecationWarning, 6383760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh stacklevel=2) 6483760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 6583760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsiehclass BaseSet(object): 6683760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh """Common base class for mutable and immutable sets.""" 6783760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 6883760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh __slots__ = ['_data'] 6983760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 7083760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh # Constructor 7183760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 7283760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh def __init__(self): 7383760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh """This is an abstract class.""" 7483760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh # Don't call this from a concrete subclass! 7583760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh if self.__class__ is BaseSet: 7683760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh raise TypeError, ("BaseSet is an abstract class. " 7783760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh "Use Set or ImmutableSet.") 7883760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 7983760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh # Standard protocols: __len__, __repr__, __str__, __iter__ 8083760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 8183760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh def __len__(self): 8283760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh """Return the number of elements of a set.""" 8383760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh return len(self._data) 8483760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 8583760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh def __repr__(self): 8683760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh """Return string representation of a set. 8783760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 8883760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh This looks like 'Set([<list of elements>])'. 8983760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh """ 9083760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh return self._repr() 9183760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 9283760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh # __str__ is the same as __repr__ 9383760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh __str__ = __repr__ 9483760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 9583760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh def _repr(self, sorted=False): 9683760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh elements = self._data.keys() 9783760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh if sorted: 9883760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh elements.sort() 9983760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh return '%s(%r)' % (self.__class__.__name__, elements) 10083760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 10183760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh def __iter__(self): 10283760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh """Return an iterator over the elements or a set. 10383760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 10483760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh This is the keys iterator for the underlying dict. 10583760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh """ 10683760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh return self._data.iterkeys() 10783760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 10883760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh # Three-way comparison is not supported. However, because __eq__ is 10983760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh # tried before __cmp__, if Set x == Set y, x.__eq__(y) returns True and 11083760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh # then cmp(x, y) returns 0 (Python doesn't actually call __cmp__ in this 11183760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh # case). 11283760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 11383760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh def __cmp__(self, other): 11483760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh raise TypeError, "can't compare sets using cmp()" 11583760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 11683760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh # Equality comparisons using the underlying dicts. Mixed-type comparisons 11783760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh # are allowed here, where Set == z for non-Set z always returns False, 11883760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh # and Set != z always True. This allows expressions like "x in y" to 11983760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh # give the expected result when y is a sequence of mixed types, not 12083760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh # raising a pointless TypeError just because y contains a Set, or x is 12183760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh # a Set and y contain's a non-set ("in" invokes only __eq__). 12283760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh # Subtle: it would be nicer if __eq__ and __ne__ could return 12383760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh # NotImplemented instead of True or False. Then the other comparand 12483760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh # would get a chance to determine the result, and if the other comparand 12583760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh # also returned NotImplemented then it would fall back to object address 12683760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh # comparison (which would always return False for __eq__ and always 12783760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh # True for __ne__). However, that doesn't work, because this type 12883760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh # *also* implements __cmp__: if, e.g., __eq__ returns NotImplemented, 12983760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh # Python tries __cmp__ next, and the __cmp__ here then raises TypeError. 13083760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 13183760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh def __eq__(self, other): 13283760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh if isinstance(other, BaseSet): 13383760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh return self._data == other._data 13483760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh else: 13583760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh return False 13683760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 13783760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh def __ne__(self, other): 13883760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh if isinstance(other, BaseSet): 13983760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh return self._data != other._data 14083760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh else: 14183760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh return True 14283760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 14383760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh # Copying operations 14483760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 14583760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh def copy(self): 14683760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh """Return a shallow copy of a set.""" 14783760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh result = self.__class__() 14883760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh result._data.update(self._data) 14983760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh return result 15083760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 15183760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh __copy__ = copy # For the copy module 15283760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 15383760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh def __deepcopy__(self, memo): 15483760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh """Return a deep copy of a set; used by copy module.""" 15583760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh # This pre-creates the result and inserts it in the memo 15683760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh # early, in case the deep copy recurses into another reference 15783760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh # to this same set. A set can't be an element of itself, but 15883760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh # it can certainly contain an object that has a reference to 15983760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh # itself. 16083760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh from copy import deepcopy 16183760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh result = self.__class__() 16283760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh memo[id(self)] = result 16383760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh data = result._data 16483760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh value = True 16583760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh for elt in self: 16683760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh data[deepcopy(elt, memo)] = value 16783760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh return result 16883760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 16983760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh # Standard set operations: union, intersection, both differences. 17083760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh # Each has an operator version (e.g. __or__, invoked with |) and a 17183760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh # method version (e.g. union). 17283760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh # Subtle: Each pair requires distinct code so that the outcome is 17383760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh # correct when the type of other isn't suitable. For example, if 17483760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh # we did "union = __or__" instead, then Set().union(3) would return 17583760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh # NotImplemented instead of raising TypeError (albeit that *why* it 17683760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh # raises TypeError as-is is also a bit subtle). 17783760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 17883760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh def __or__(self, other): 17983760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh """Return the union of two sets as a new set. 18083760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 18183760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh (I.e. all elements that are in either set.) 18283760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh """ 18383760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh if not isinstance(other, BaseSet): 18483760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh return NotImplemented 18583760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh return self.union(other) 18683760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 18783760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh def union(self, other): 18883760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh """Return the union of two sets as a new set. 18983760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 19083760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh (I.e. all elements that are in either set.) 19183760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh """ 19283760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh result = self.__class__(self) 19383760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh result._update(other) 19483760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh return result 19583760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 19683760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh def __and__(self, other): 19783760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh """Return the intersection of two sets as a new set. 19883760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 19983760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh (I.e. all elements that are in both sets.) 20083760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh """ 20183760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh if not isinstance(other, BaseSet): 20283760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh return NotImplemented 20383760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh return self.intersection(other) 20483760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 20583760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh def intersection(self, other): 20683760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh """Return the intersection of two sets as a new set. 20783760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 20883760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh (I.e. all elements that are in both sets.) 20983760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh """ 21083760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh if not isinstance(other, BaseSet): 21183760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh other = Set(other) 21283760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh if len(self) <= len(other): 21383760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh little, big = self, other 21483760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh else: 21583760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh little, big = other, self 21683760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh common = ifilter(big._data.__contains__, little) 21783760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh return self.__class__(common) 21883760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 21983760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh def __xor__(self, other): 22083760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh """Return the symmetric difference of two sets as a new set. 22183760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 22283760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh (I.e. all elements that are in exactly one of the sets.) 22383760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh """ 22483760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh if not isinstance(other, BaseSet): 22583760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh return NotImplemented 22683760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh return self.symmetric_difference(other) 22783760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 22883760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh def symmetric_difference(self, other): 22983760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh """Return the symmetric difference of two sets as a new set. 23083760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 23183760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh (I.e. all elements that are in exactly one of the sets.) 23283760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh """ 23383760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh result = self.__class__() 23483760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh data = result._data 23583760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh value = True 23683760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh selfdata = self._data 23783760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh try: 23883760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh otherdata = other._data 23983760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh except AttributeError: 24083760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh otherdata = Set(other)._data 24183760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh for elt in ifilterfalse(otherdata.__contains__, selfdata): 24283760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh data[elt] = value 24383760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh for elt in ifilterfalse(selfdata.__contains__, otherdata): 24483760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh data[elt] = value 24583760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh return result 24683760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 24783760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh def __sub__(self, other): 24883760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh """Return the difference of two sets as a new Set. 24983760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 25083760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh (I.e. all elements that are in this set and not in the other.) 25183760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh """ 25283760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh if not isinstance(other, BaseSet): 25383760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh return NotImplemented 25483760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh return self.difference(other) 25583760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 25683760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh def difference(self, other): 25783760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh """Return the difference of two sets as a new Set. 25883760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 25983760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh (I.e. all elements that are in this set and not in the other.) 26083760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh """ 26183760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh result = self.__class__() 26283760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh data = result._data 26383760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh try: 26483760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh otherdata = other._data 26583760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh except AttributeError: 26683760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh otherdata = Set(other)._data 26783760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh value = True 26883760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh for elt in ifilterfalse(otherdata.__contains__, self): 26983760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh data[elt] = value 27083760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh return result 27183760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 27283760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh # Membership test 27383760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 27483760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh def __contains__(self, element): 27583760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh """Report whether an element is a member of a set. 27683760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 27783760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh (Called in response to the expression `element in self'.) 27883760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh """ 27983760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh try: 28083760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh return element in self._data 28183760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh except TypeError: 28283760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh transform = getattr(element, "__as_temporarily_immutable__", None) 28383760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh if transform is None: 28483760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh raise # re-raise the TypeError exception we caught 28583760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh return transform() in self._data 28683760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 28783760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh # Subset and superset test 28883760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 28983760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh def issubset(self, other): 29083760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh """Report whether another set contains this set.""" 29183760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh self._binary_sanity_check(other) 29283760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh if len(self) > len(other): # Fast check for obvious cases 29383760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh return False 29483760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh for elt in ifilterfalse(other._data.__contains__, self): 29583760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh return False 29683760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh return True 29783760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 29883760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh def issuperset(self, other): 29983760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh """Report whether this set contains another set.""" 30083760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh self._binary_sanity_check(other) 30183760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh if len(self) < len(other): # Fast check for obvious cases 30283760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh return False 30383760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh for elt in ifilterfalse(self._data.__contains__, other): 30483760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh return False 30583760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh return True 30683760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 30783760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh # Inequality comparisons using the is-subset relation. 30883760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh __le__ = issubset 30983760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh __ge__ = issuperset 31083760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 31183760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh def __lt__(self, other): 31283760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh self._binary_sanity_check(other) 31383760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh return len(self) < len(other) and self.issubset(other) 31483760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 31583760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh def __gt__(self, other): 31683760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh self._binary_sanity_check(other) 31783760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh return len(self) > len(other) and self.issuperset(other) 31883760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 31983760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh # We inherit object.__hash__, so we must deny this explicitly 32083760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh __hash__ = None 32183760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 32283760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh # Assorted helpers 32383760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 32483760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh def _binary_sanity_check(self, other): 32583760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh # Check that the other argument to a binary operation is also 32683760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh # a set, raising a TypeError otherwise. 32783760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh if not isinstance(other, BaseSet): 32883760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh raise TypeError, "Binary operation only permitted between sets" 32983760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 33083760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh def _compute_hash(self): 33183760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh # Calculate hash code for a set by xor'ing the hash codes of 33283760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh # the elements. This ensures that the hash code does not depend 33383760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh # on the order in which elements are added to the set. This is 33483760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh # not called __hash__ because a BaseSet should not be hashable; 33583760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh # only an ImmutableSet is hashable. 33683760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh result = 0 33783760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh for elt in self: 33883760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh result ^= hash(elt) 33983760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh return result 34083760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 34183760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh def _update(self, iterable): 34283760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh # The main loop for update() and the subclass __init__() methods. 34383760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh data = self._data 34483760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 34583760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh # Use the fast update() method when a dictionary is available. 34683760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh if isinstance(iterable, BaseSet): 34783760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh data.update(iterable._data) 34883760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh return 34983760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 35083760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh value = True 35183760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 35283760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh if type(iterable) in (list, tuple, xrange): 35383760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh # Optimized: we know that __iter__() and next() can't 35483760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh # raise TypeError, so we can move 'try:' out of the loop. 35583760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh it = iter(iterable) 35683760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh while True: 35783760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh try: 35883760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh for element in it: 35983760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh data[element] = value 36083760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh return 36183760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh except TypeError: 36283760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh transform = getattr(element, "__as_immutable__", None) 36383760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh if transform is None: 36483760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh raise # re-raise the TypeError exception we caught 36583760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh data[transform()] = value 36683760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh else: 36783760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh # Safe: only catch TypeError where intended 36883760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh for element in iterable: 36983760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh try: 37083760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh data[element] = value 37183760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh except TypeError: 37283760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh transform = getattr(element, "__as_immutable__", None) 37383760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh if transform is None: 37483760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh raise # re-raise the TypeError exception we caught 37583760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh data[transform()] = value 37683760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 37783760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 37883760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsiehclass ImmutableSet(BaseSet): 37983760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh """Immutable set class.""" 38083760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 38183760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh __slots__ = ['_hashcode'] 38283760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 38383760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh # BaseSet + hashing 38483760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 38583760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh def __init__(self, iterable=None): 38683760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh """Construct an immutable set from an optional iterable.""" 38783760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh self._hashcode = None 38883760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh self._data = {} 38983760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh if iterable is not None: 39083760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh self._update(iterable) 39183760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 39283760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh def __hash__(self): 39383760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh if self._hashcode is None: 39483760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh self._hashcode = self._compute_hash() 39583760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh return self._hashcode 39683760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 39783760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh def __getstate__(self): 39883760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh return self._data, self._hashcode 39983760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 40083760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh def __setstate__(self, state): 40183760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh self._data, self._hashcode = state 40283760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 40383760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsiehclass Set(BaseSet): 40483760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh """ Mutable set class.""" 40583760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 40683760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh __slots__ = [] 40783760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 40883760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh # BaseSet + operations requiring mutability; no hashing 40983760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 41083760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh def __init__(self, iterable=None): 41183760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh """Construct a set from an optional iterable.""" 41283760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh self._data = {} 41383760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh if iterable is not None: 41483760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh self._update(iterable) 41583760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 41683760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh def __getstate__(self): 41783760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh # getstate's results are ignored if it is not 41883760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh return self._data, 41983760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 42083760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh def __setstate__(self, data): 42183760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh self._data, = data 42283760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 42383760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh # In-place union, intersection, differences. 42483760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh # Subtle: The xyz_update() functions deliberately return None, 42583760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh # as do all mutating operations on built-in container types. 42683760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh # The __xyz__ spellings have to return self, though. 42783760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 42883760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh def __ior__(self, other): 42983760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh """Update a set with the union of itself and another.""" 43083760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh self._binary_sanity_check(other) 43183760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh self._data.update(other._data) 43283760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh return self 43383760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 43483760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh def union_update(self, other): 43583760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh """Update a set with the union of itself and another.""" 43683760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh self._update(other) 43783760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 43883760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh def __iand__(self, other): 43983760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh """Update a set with the intersection of itself and another.""" 44083760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh self._binary_sanity_check(other) 44183760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh self._data = (self & other)._data 44283760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh return self 44383760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 44483760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh def intersection_update(self, other): 44583760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh """Update a set with the intersection of itself and another.""" 44683760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh if isinstance(other, BaseSet): 44783760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh self &= other 44883760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh else: 44983760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh self._data = (self.intersection(other))._data 45083760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 45183760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh def __ixor__(self, other): 45283760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh """Update a set with the symmetric difference of itself and another.""" 45383760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh self._binary_sanity_check(other) 45483760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh self.symmetric_difference_update(other) 45583760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh return self 45683760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 45783760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh def symmetric_difference_update(self, other): 45883760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh """Update a set with the symmetric difference of itself and another.""" 45983760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh data = self._data 46083760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh value = True 46183760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh if not isinstance(other, BaseSet): 46283760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh other = Set(other) 46383760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh if self is other: 46483760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh self.clear() 46583760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh for elt in other: 46683760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh if elt in data: 46783760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh del data[elt] 46883760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh else: 46983760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh data[elt] = value 47083760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 47183760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh def __isub__(self, other): 47283760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh """Remove all elements of another set from this set.""" 47383760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh self._binary_sanity_check(other) 47483760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh self.difference_update(other) 47583760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh return self 47683760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 47783760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh def difference_update(self, other): 47883760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh """Remove all elements of another set from this set.""" 47983760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh data = self._data 48083760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh if not isinstance(other, BaseSet): 48183760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh other = Set(other) 48283760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh if self is other: 48383760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh self.clear() 48483760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh for elt in ifilter(data.__contains__, other): 48583760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh del data[elt] 48683760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 48783760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh # Python dict-like mass mutations: update, clear 48883760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 48983760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh def update(self, iterable): 49083760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh """Add all values from an iterable (such as a list or file).""" 49183760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh self._update(iterable) 49283760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 49383760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh def clear(self): 49483760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh """Remove all elements from this set.""" 49583760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh self._data.clear() 49683760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 49783760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh # Single-element mutations: add, remove, discard 49883760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 49983760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh def add(self, element): 50083760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh """Add an element to a set. 50183760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 50283760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh This has no effect if the element is already present. 50383760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh """ 50483760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh try: 50583760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh self._data[element] = True 50683760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh except TypeError: 50783760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh transform = getattr(element, "__as_immutable__", None) 50883760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh if transform is None: 50983760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh raise # re-raise the TypeError exception we caught 51083760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh self._data[transform()] = True 51183760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 51283760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh def remove(self, element): 51383760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh """Remove an element from a set; it must be a member. 51483760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 51583760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh If the element is not a member, raise a KeyError. 51683760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh """ 51783760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh try: 51883760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh del self._data[element] 51983760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh except TypeError: 52083760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh transform = getattr(element, "__as_temporarily_immutable__", None) 52183760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh if transform is None: 52283760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh raise # re-raise the TypeError exception we caught 52383760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh del self._data[transform()] 52483760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 52583760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh def discard(self, element): 52683760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh """Remove an element from a set if it is a member. 52783760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 52883760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh If the element is not a member, do nothing. 52983760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh """ 53083760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh try: 53183760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh self.remove(element) 53283760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh except KeyError: 53383760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh pass 53483760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 53583760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh def pop(self): 53683760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh """Remove and return an arbitrary set element.""" 53783760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh return self._data.popitem()[0] 53883760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 53983760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh def __as_immutable__(self): 54083760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh # Return a copy of self as an immutable set 54183760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh return ImmutableSet(self) 54283760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 54383760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh def __as_temporarily_immutable__(self): 54483760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh # Return self wrapped in a temporarily immutable set 54583760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh return _TemporarilyImmutableSet(self) 54683760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 54783760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 54883760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsiehclass _TemporarilyImmutableSet(BaseSet): 54983760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh # Wrap a mutable set as if it was temporarily immutable. 55083760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh # This only supplies hashing and equality comparisons. 55183760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 55283760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh def __init__(self, set): 55383760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh self._set = set 55483760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh self._data = set._data # Needed by ImmutableSet.__eq__() 55583760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh 55683760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh def __hash__(self): 55783760d213fb3bec7b4117d266fcfbf6fe2ba14abAndrew Hsieh return self._set._compute_hash() 558