+++ /dev/null
-"""Classes to represent arbitrary sets (including sets of sets).\r
-\r
-This module implements sets using dictionaries whose values are\r
-ignored. The usual operations (union, intersection, deletion, etc.)\r
-are provided as both methods and operators.\r
-\r
-Important: sets are not sequences! While they support 'x in s',\r
-'len(s)', and 'for x in s', none of those operations are unique for\r
-sequences; for example, mappings support all three as well. The\r
-characteristic operation for sequences is subscripting with small\r
-integers: s[i], for i in range(len(s)). Sets don't support\r
-subscripting at all. Also, sequences allow multiple occurrences and\r
-their elements have a definite order; sets on the other hand don't\r
-record multiple occurrences and don't remember the order of element\r
-insertion (which is why they don't support s[i]).\r
-\r
-The following classes are provided:\r
-\r
-BaseSet -- All the operations common to both mutable and immutable\r
- sets. This is an abstract class, not meant to be directly\r
- instantiated.\r
-\r
-Set -- Mutable sets, subclass of BaseSet; not hashable.\r
-\r
-ImmutableSet -- Immutable sets, subclass of BaseSet; hashable.\r
- An iterable argument is mandatory to create an ImmutableSet.\r
-\r
-_TemporarilyImmutableSet -- A wrapper around a Set, hashable,\r
- giving the same hash value as the immutable set equivalent\r
- would have. Do not use this class directly.\r
-\r
-Only hashable objects can be added to a Set. In particular, you cannot\r
-really add a Set as an element to another Set; if you try, what is\r
-actually added is an ImmutableSet built from it (it compares equal to\r
-the one you tried adding).\r
-\r
-When you ask if `x in y' where x is a Set and y is a Set or\r
-ImmutableSet, x is wrapped into a _TemporarilyImmutableSet z, and\r
-what's tested is actually `z in y'.\r
-\r
-"""\r
-\r
-# Code history:\r
-#\r
-# - Greg V. Wilson wrote the first version, using a different approach\r
-# to the mutable/immutable problem, and inheriting from dict.\r
-#\r
-# - Alex Martelli modified Greg's version to implement the current\r
-# Set/ImmutableSet approach, and make the data an attribute.\r
-#\r
-# - Guido van Rossum rewrote much of the code, made some API changes,\r
-# and cleaned up the docstrings.\r
-#\r
-# - Raymond Hettinger added a number of speedups and other\r
-# improvements.\r
-\r
-from itertools import ifilter, ifilterfalse\r
-\r
-__all__ = ['BaseSet', 'Set', 'ImmutableSet']\r
-\r
-import warnings\r
-warnings.warn("the sets module is deprecated", DeprecationWarning,\r
- stacklevel=2)\r
-\r
-class BaseSet(object):\r
- """Common base class for mutable and immutable sets."""\r
-\r
- __slots__ = ['_data']\r
-\r
- # Constructor\r
-\r
- def __init__(self):\r
- """This is an abstract class."""\r
- # Don't call this from a concrete subclass!\r
- if self.__class__ is BaseSet:\r
- raise TypeError, ("BaseSet is an abstract class. "\r
- "Use Set or ImmutableSet.")\r
-\r
- # Standard protocols: __len__, __repr__, __str__, __iter__\r
-\r
- def __len__(self):\r
- """Return the number of elements of a set."""\r
- return len(self._data)\r
-\r
- def __repr__(self):\r
- """Return string representation of a set.\r
-\r
- This looks like 'Set([<list of elements>])'.\r
- """\r
- return self._repr()\r
-\r
- # __str__ is the same as __repr__\r
- __str__ = __repr__\r
-\r
- def _repr(self, sorted=False):\r
- elements = self._data.keys()\r
- if sorted:\r
- elements.sort()\r
- return '%s(%r)' % (self.__class__.__name__, elements)\r
-\r
- def __iter__(self):\r
- """Return an iterator over the elements or a set.\r
-\r
- This is the keys iterator for the underlying dict.\r
- """\r
- return self._data.iterkeys()\r
-\r
- # Three-way comparison is not supported. However, because __eq__ is\r
- # tried before __cmp__, if Set x == Set y, x.__eq__(y) returns True and\r
- # then cmp(x, y) returns 0 (Python doesn't actually call __cmp__ in this\r
- # case).\r
-\r
- def __cmp__(self, other):\r
- raise TypeError, "can't compare sets using cmp()"\r
-\r
- # Equality comparisons using the underlying dicts. Mixed-type comparisons\r
- # are allowed here, where Set == z for non-Set z always returns False,\r
- # and Set != z always True. This allows expressions like "x in y" to\r
- # give the expected result when y is a sequence of mixed types, not\r
- # raising a pointless TypeError just because y contains a Set, or x is\r
- # a Set and y contain's a non-set ("in" invokes only __eq__).\r
- # Subtle: it would be nicer if __eq__ and __ne__ could return\r
- # NotImplemented instead of True or False. Then the other comparand\r
- # would get a chance to determine the result, and if the other comparand\r
- # also returned NotImplemented then it would fall back to object address\r
- # comparison (which would always return False for __eq__ and always\r
- # True for __ne__). However, that doesn't work, because this type\r
- # *also* implements __cmp__: if, e.g., __eq__ returns NotImplemented,\r
- # Python tries __cmp__ next, and the __cmp__ here then raises TypeError.\r
-\r
- def __eq__(self, other):\r
- if isinstance(other, BaseSet):\r
- return self._data == other._data\r
- else:\r
- return False\r
-\r
- def __ne__(self, other):\r
- if isinstance(other, BaseSet):\r
- return self._data != other._data\r
- else:\r
- return True\r
-\r
- # Copying operations\r
-\r
- def copy(self):\r
- """Return a shallow copy of a set."""\r
- result = self.__class__()\r
- result._data.update(self._data)\r
- return result\r
-\r
- __copy__ = copy # For the copy module\r
-\r
- def __deepcopy__(self, memo):\r
- """Return a deep copy of a set; used by copy module."""\r
- # This pre-creates the result and inserts it in the memo\r
- # early, in case the deep copy recurses into another reference\r
- # to this same set. A set can't be an element of itself, but\r
- # it can certainly contain an object that has a reference to\r
- # itself.\r
- from copy import deepcopy\r
- result = self.__class__()\r
- memo[id(self)] = result\r
- data = result._data\r
- value = True\r
- for elt in self:\r
- data[deepcopy(elt, memo)] = value\r
- return result\r
-\r
- # Standard set operations: union, intersection, both differences.\r
- # Each has an operator version (e.g. __or__, invoked with |) and a\r
- # method version (e.g. union).\r
- # Subtle: Each pair requires distinct code so that the outcome is\r
- # correct when the type of other isn't suitable. For example, if\r
- # we did "union = __or__" instead, then Set().union(3) would return\r
- # NotImplemented instead of raising TypeError (albeit that *why* it\r
- # raises TypeError as-is is also a bit subtle).\r
-\r
- def __or__(self, other):\r
- """Return the union of two sets as a new set.\r
-\r
- (I.e. all elements that are in either set.)\r
- """\r
- if not isinstance(other, BaseSet):\r
- return NotImplemented\r
- return self.union(other)\r
-\r
- def union(self, other):\r
- """Return the union of two sets as a new set.\r
-\r
- (I.e. all elements that are in either set.)\r
- """\r
- result = self.__class__(self)\r
- result._update(other)\r
- return result\r
-\r
- def __and__(self, other):\r
- """Return the intersection of two sets as a new set.\r
-\r
- (I.e. all elements that are in both sets.)\r
- """\r
- if not isinstance(other, BaseSet):\r
- return NotImplemented\r
- return self.intersection(other)\r
-\r
- def intersection(self, other):\r
- """Return the intersection of two sets as a new set.\r
-\r
- (I.e. all elements that are in both sets.)\r
- """\r
- if not isinstance(other, BaseSet):\r
- other = Set(other)\r
- if len(self) <= len(other):\r
- little, big = self, other\r
- else:\r
- little, big = other, self\r
- common = ifilter(big._data.__contains__, little)\r
- return self.__class__(common)\r
-\r
- def __xor__(self, other):\r
- """Return the symmetric difference of two sets as a new set.\r
-\r
- (I.e. all elements that are in exactly one of the sets.)\r
- """\r
- if not isinstance(other, BaseSet):\r
- return NotImplemented\r
- return self.symmetric_difference(other)\r
-\r
- def symmetric_difference(self, other):\r
- """Return the symmetric difference of two sets as a new set.\r
-\r
- (I.e. all elements that are in exactly one of the sets.)\r
- """\r
- result = self.__class__()\r
- data = result._data\r
- value = True\r
- selfdata = self._data\r
- try:\r
- otherdata = other._data\r
- except AttributeError:\r
- otherdata = Set(other)._data\r
- for elt in ifilterfalse(otherdata.__contains__, selfdata):\r
- data[elt] = value\r
- for elt in ifilterfalse(selfdata.__contains__, otherdata):\r
- data[elt] = value\r
- return result\r
-\r
- def __sub__(self, other):\r
- """Return the difference of two sets as a new Set.\r
-\r
- (I.e. all elements that are in this set and not in the other.)\r
- """\r
- if not isinstance(other, BaseSet):\r
- return NotImplemented\r
- return self.difference(other)\r
-\r
- def difference(self, other):\r
- """Return the difference of two sets as a new Set.\r
-\r
- (I.e. all elements that are in this set and not in the other.)\r
- """\r
- result = self.__class__()\r
- data = result._data\r
- try:\r
- otherdata = other._data\r
- except AttributeError:\r
- otherdata = Set(other)._data\r
- value = True\r
- for elt in ifilterfalse(otherdata.__contains__, self):\r
- data[elt] = value\r
- return result\r
-\r
- # Membership test\r
-\r
- def __contains__(self, element):\r
- """Report whether an element is a member of a set.\r
-\r
- (Called in response to the expression `element in self'.)\r
- """\r
- try:\r
- return element in self._data\r
- except TypeError:\r
- transform = getattr(element, "__as_temporarily_immutable__", None)\r
- if transform is None:\r
- raise # re-raise the TypeError exception we caught\r
- return transform() in self._data\r
-\r
- # Subset and superset test\r
-\r
- def issubset(self, other):\r
- """Report whether another set contains this set."""\r
- self._binary_sanity_check(other)\r
- if len(self) > len(other): # Fast check for obvious cases\r
- return False\r
- for elt in ifilterfalse(other._data.__contains__, self):\r
- return False\r
- return True\r
-\r
- def issuperset(self, other):\r
- """Report whether this set contains another set."""\r
- self._binary_sanity_check(other)\r
- if len(self) < len(other): # Fast check for obvious cases\r
- return False\r
- for elt in ifilterfalse(self._data.__contains__, other):\r
- return False\r
- return True\r
-\r
- # Inequality comparisons using the is-subset relation.\r
- __le__ = issubset\r
- __ge__ = issuperset\r
-\r
- def __lt__(self, other):\r
- self._binary_sanity_check(other)\r
- return len(self) < len(other) and self.issubset(other)\r
-\r
- def __gt__(self, other):\r
- self._binary_sanity_check(other)\r
- return len(self) > len(other) and self.issuperset(other)\r
-\r
- # We inherit object.__hash__, so we must deny this explicitly\r
- __hash__ = None\r
-\r
- # Assorted helpers\r
-\r
- def _binary_sanity_check(self, other):\r
- # Check that the other argument to a binary operation is also\r
- # a set, raising a TypeError otherwise.\r
- if not isinstance(other, BaseSet):\r
- raise TypeError, "Binary operation only permitted between sets"\r
-\r
- def _compute_hash(self):\r
- # Calculate hash code for a set by xor'ing the hash codes of\r
- # the elements. This ensures that the hash code does not depend\r
- # on the order in which elements are added to the set. This is\r
- # not called __hash__ because a BaseSet should not be hashable;\r
- # only an ImmutableSet is hashable.\r
- result = 0\r
- for elt in self:\r
- result ^= hash(elt)\r
- return result\r
-\r
- def _update(self, iterable):\r
- # The main loop for update() and the subclass __init__() methods.\r
- data = self._data\r
-\r
- # Use the fast update() method when a dictionary is available.\r
- if isinstance(iterable, BaseSet):\r
- data.update(iterable._data)\r
- return\r
-\r
- value = True\r
-\r
- if type(iterable) in (list, tuple, xrange):\r
- # Optimized: we know that __iter__() and next() can't\r
- # raise TypeError, so we can move 'try:' out of the loop.\r
- it = iter(iterable)\r
- while True:\r
- try:\r
- for element in it:\r
- data[element] = value\r
- return\r
- except TypeError:\r
- transform = getattr(element, "__as_immutable__", None)\r
- if transform is None:\r
- raise # re-raise the TypeError exception we caught\r
- data[transform()] = value\r
- else:\r
- # Safe: only catch TypeError where intended\r
- for element in iterable:\r
- try:\r
- data[element] = value\r
- except TypeError:\r
- transform = getattr(element, "__as_immutable__", None)\r
- if transform is None:\r
- raise # re-raise the TypeError exception we caught\r
- data[transform()] = value\r
-\r
-\r
-class ImmutableSet(BaseSet):\r
- """Immutable set class."""\r
-\r
- __slots__ = ['_hashcode']\r
-\r
- # BaseSet + hashing\r
-\r
- def __init__(self, iterable=None):\r
- """Construct an immutable set from an optional iterable."""\r
- self._hashcode = None\r
- self._data = {}\r
- if iterable is not None:\r
- self._update(iterable)\r
-\r
- def __hash__(self):\r
- if self._hashcode is None:\r
- self._hashcode = self._compute_hash()\r
- return self._hashcode\r
-\r
- def __getstate__(self):\r
- return self._data, self._hashcode\r
-\r
- def __setstate__(self, state):\r
- self._data, self._hashcode = state\r
-\r
-class Set(BaseSet):\r
- """ Mutable set class."""\r
-\r
- __slots__ = []\r
-\r
- # BaseSet + operations requiring mutability; no hashing\r
-\r
- def __init__(self, iterable=None):\r
- """Construct a set from an optional iterable."""\r
- self._data = {}\r
- if iterable is not None:\r
- self._update(iterable)\r
-\r
- def __getstate__(self):\r
- # getstate's results are ignored if it is not\r
- return self._data,\r
-\r
- def __setstate__(self, data):\r
- self._data, = data\r
-\r
- # In-place union, intersection, differences.\r
- # Subtle: The xyz_update() functions deliberately return None,\r
- # as do all mutating operations on built-in container types.\r
- # The __xyz__ spellings have to return self, though.\r
-\r
- def __ior__(self, other):\r
- """Update a set with the union of itself and another."""\r
- self._binary_sanity_check(other)\r
- self._data.update(other._data)\r
- return self\r
-\r
- def union_update(self, other):\r
- """Update a set with the union of itself and another."""\r
- self._update(other)\r
-\r
- def __iand__(self, other):\r
- """Update a set with the intersection of itself and another."""\r
- self._binary_sanity_check(other)\r
- self._data = (self & other)._data\r
- return self\r
-\r
- def intersection_update(self, other):\r
- """Update a set with the intersection of itself and another."""\r
- if isinstance(other, BaseSet):\r
- self &= other\r
- else:\r
- self._data = (self.intersection(other))._data\r
-\r
- def __ixor__(self, other):\r
- """Update a set with the symmetric difference of itself and another."""\r
- self._binary_sanity_check(other)\r
- self.symmetric_difference_update(other)\r
- return self\r
-\r
- def symmetric_difference_update(self, other):\r
- """Update a set with the symmetric difference of itself and another."""\r
- data = self._data\r
- value = True\r
- if not isinstance(other, BaseSet):\r
- other = Set(other)\r
- if self is other:\r
- self.clear()\r
- for elt in other:\r
- if elt in data:\r
- del data[elt]\r
- else:\r
- data[elt] = value\r
-\r
- def __isub__(self, other):\r
- """Remove all elements of another set from this set."""\r
- self._binary_sanity_check(other)\r
- self.difference_update(other)\r
- return self\r
-\r
- def difference_update(self, other):\r
- """Remove all elements of another set from this set."""\r
- data = self._data\r
- if not isinstance(other, BaseSet):\r
- other = Set(other)\r
- if self is other:\r
- self.clear()\r
- for elt in ifilter(data.__contains__, other):\r
- del data[elt]\r
-\r
- # Python dict-like mass mutations: update, clear\r
-\r
- def update(self, iterable):\r
- """Add all values from an iterable (such as a list or file)."""\r
- self._update(iterable)\r
-\r
- def clear(self):\r
- """Remove all elements from this set."""\r
- self._data.clear()\r
-\r
- # Single-element mutations: add, remove, discard\r
-\r
- def add(self, element):\r
- """Add an element to a set.\r
-\r
- This has no effect if the element is already present.\r
- """\r
- try:\r
- self._data[element] = True\r
- except TypeError:\r
- transform = getattr(element, "__as_immutable__", None)\r
- if transform is None:\r
- raise # re-raise the TypeError exception we caught\r
- self._data[transform()] = True\r
-\r
- def remove(self, element):\r
- """Remove an element from a set; it must be a member.\r
-\r
- If the element is not a member, raise a KeyError.\r
- """\r
- try:\r
- del self._data[element]\r
- except TypeError:\r
- transform = getattr(element, "__as_temporarily_immutable__", None)\r
- if transform is None:\r
- raise # re-raise the TypeError exception we caught\r
- del self._data[transform()]\r
-\r
- def discard(self, element):\r
- """Remove an element from a set if it is a member.\r
-\r
- If the element is not a member, do nothing.\r
- """\r
- try:\r
- self.remove(element)\r
- except KeyError:\r
- pass\r
-\r
- def pop(self):\r
- """Remove and return an arbitrary set element."""\r
- return self._data.popitem()[0]\r
-\r
- def __as_immutable__(self):\r
- # Return a copy of self as an immutable set\r
- return ImmutableSet(self)\r
-\r
- def __as_temporarily_immutable__(self):\r
- # Return self wrapped in a temporarily immutable set\r
- return _TemporarilyImmutableSet(self)\r
-\r
-\r
-class _TemporarilyImmutableSet(BaseSet):\r
- # Wrap a mutable set as if it was temporarily immutable.\r
- # This only supplies hashing and equality comparisons.\r
-\r
- def __init__(self, set):\r
- self._set = set\r
- self._data = set._data # Needed by ImmutableSet.__eq__()\r
-\r
- def __hash__(self):\r
- return self._set._compute_hash()\r
projects / mirror_edk2.git / blobdiff