cpython-lru_cache-weakref: Lib/sets.py annotate

annotate Lib/sets.py @ 27664:652df4549708 legacy-trunk

Whitespace normalization.

author	Tim Peters <tim.peters@gmail.com>
date	Tue, 04 Feb 2003 00:38:20 +0000
parents	93210564bb46
children	dc5e1d918055

rev	line source
24891 aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	1 """Classes to represent arbitrary sets (including sets of sets).
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	2
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	3 This module implements sets using dictionaries whose values are
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	4 ignored. The usual operations (union, intersection, deletion, etc.)
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	5 are provided as both methods and operators.
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	6
24921 8eef03850f57 Add a note reminding the reader that sets are not sequences. I Guido van Rossum <guido@python.org> parents: 24893 diff changeset	7 Important: sets are not sequences! While they support 'x in s',
8eef03850f57 Add a note reminding the reader that sets are not sequences. I Guido van Rossum <guido@python.org> parents: 24893 diff changeset	8 'len(s)', and 'for x in s', none of those operations are unique for
8eef03850f57 Add a note reminding the reader that sets are not sequences. I Guido van Rossum <guido@python.org> parents: 24893 diff changeset	9 sequences; for example, mappings support all three as well. The
8eef03850f57 Add a note reminding the reader that sets are not sequences. I Guido van Rossum <guido@python.org> parents: 24893 diff changeset	10 characteristic operation for sequences is subscripting with small
8eef03850f57 Add a note reminding the reader that sets are not sequences. I Guido van Rossum <guido@python.org> parents: 24893 diff changeset	11 integers: s[i], for i in range(len(s)). Sets don't support
8eef03850f57 Add a note reminding the reader that sets are not sequences. I Guido van Rossum <guido@python.org> parents: 24893 diff changeset	12 subscripting at all. Also, sequences allow multiple occurrences and
8eef03850f57 Add a note reminding the reader that sets are not sequences. I Guido van Rossum <guido@python.org> parents: 24893 diff changeset	13 their elements have a definite order; sets on the other hand don't
8eef03850f57 Add a note reminding the reader that sets are not sequences. I Guido van Rossum <guido@python.org> parents: 24893 diff changeset	14 record multiple occurrences and don't remember the order of element
8eef03850f57 Add a note reminding the reader that sets are not sequences. I Guido van Rossum <guido@python.org> parents: 24893 diff changeset	15 insertion (which is why they don't support s[i]).
8eef03850f57 Add a note reminding the reader that sets are not sequences. I Guido van Rossum <guido@python.org> parents: 24893 diff changeset	16
24891 aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	17 The following classes are provided:
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	18
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	19 BaseSet -- All the operations common to both mutable and immutable
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	20 sets. This is an abstract class, not meant to be directly
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	21 instantiated.
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	22
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	23 Set -- Mutable sets, subclass of BaseSet; not hashable.
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	24
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	25 ImmutableSet -- Immutable sets, subclass of BaseSet; hashable.
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	26 An iterable argument is mandatory to create an ImmutableSet.
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	27
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	28 _TemporarilyImmutableSet -- Not a subclass of BaseSet: just a wrapper
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	29 around a Set, hashable, giving the same hash value as the
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	30 immutable set equivalent would have. Do not use this class
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	31 directly.
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	32
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	33 Only hashable objects can be added to a Set. In particular, you cannot
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	34 really add a Set as an element to another Set; if you try, what is
24925 940605d4155f Minor typo Raymond Hettinger <python@rcn.com> parents: 24924 diff changeset	35 actually added is an ImmutableSet built from it (it compares equal to
24891 aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	36 the one you tried adding).
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	37
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	38 When you ask if `x in y' where x is a Set and y is a Set or
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	39 ImmutableSet, x is wrapped into a _TemporarilyImmutableSet z, and
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	40 what's tested is actually `z in y'.
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	41
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	42 """
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	43
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	44 # Code history:
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	45 #
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	46 # - Greg V. Wilson wrote the first version, using a different approach
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	47 # to the mutable/immutable problem, and inheriting from dict.
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	48 #
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	49 # - Alex Martelli modified Greg's version to implement the current
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	50 # Set/ImmutableSet approach, and make the data an attribute.
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	51 #
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	52 # - Guido van Rossum rewrote much of the code, made some API changes,
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	53 # and cleaned up the docstrings.
24929 419d47c77143 Add Raymond H to the list of authors; add some XXX comments about Guido van Rossum <guido@python.org> parents: 24928 diff changeset	54 #
24930 e8f77307d9c6 Ouch. The test suite really needs work!!!!! There were several Guido van Rossum <guido@python.org> parents: 24929 diff changeset	55 # - Raymond Hettinger added a number of speedups and other
24943 5306408657fc Change the binary operators \|, &, ^, - to return NotImplemented rather Guido van Rossum <guido@python.org> parents: 24934 diff changeset	56 # improvements.
24891 aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	57
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	58
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	59 __all__ = ['BaseSet', 'Set', 'ImmutableSet']
27589 e3fa8377f30c SF patch #678899: Save time and memory by using itertools in sets module. Raymond Hettinger <python@rcn.com> parents: 27244 diff changeset	60 from itertools import ifilter
24891 aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	61
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	62 class BaseSet(object):
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	63 """Common base class for mutable and immutable sets."""
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	64
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	65 __slots__ = ['_data']
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	66
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	67 # Constructor
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	68
24923 51c26994d8ec Move __init__ from BaseSet into Set and ImmutableSet. This causes a Guido van Rossum <guido@python.org> parents: 24921 diff changeset	69 def __init__(self):
51c26994d8ec Move __init__ from BaseSet into Set and ImmutableSet. This causes a Guido van Rossum <guido@python.org> parents: 24921 diff changeset	70 """This is an abstract class."""
51c26994d8ec Move __init__ from BaseSet into Set and ImmutableSet. This causes a Guido van Rossum <guido@python.org> parents: 24921 diff changeset	71 # Don't call this from a concrete subclass!
51c26994d8ec Move __init__ from BaseSet into Set and ImmutableSet. This causes a Guido van Rossum <guido@python.org> parents: 24921 diff changeset	72 if self.__class__ is BaseSet:
24930 e8f77307d9c6 Ouch. The test suite really needs work!!!!! There were several Guido van Rossum <guido@python.org> parents: 24929 diff changeset	73 raise TypeError, ("BaseSet is an abstract class. "
e8f77307d9c6 Ouch. The test suite really needs work!!!!! There were several Guido van Rossum <guido@python.org> parents: 24929 diff changeset	74 "Use Set or ImmutableSet.")
24891 aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	75
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	76 # Standard protocols: __len__, __repr__, __str__, __iter__
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	77
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	78 def __len__(self):
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	79 """Return the number of elements of a set."""
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	80 return len(self._data)
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	81
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	82 def __repr__(self):
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	83 """Return string representation of a set.
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	84
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	85 This looks like 'Set([<list of elements>])'.
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	86 """
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	87 return self._repr()
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	88
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	89 # __str__ is the same as __repr__
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	90 __str__ = __repr__
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	91
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	92 def _repr(self, sorted=False):
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	93 elements = self._data.keys()
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	94 if sorted:
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	95 elements.sort()
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	96 return '%s(%r)' % (self.__class__.__name__, elements)
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	97
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	98 def __iter__(self):
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	99 """Return an iterator over the elements or a set.
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	100
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	101 This is the keys iterator for the underlying dict.
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	102 """
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	103 return self._data.iterkeys()
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	104
27244 b3f105399d22 Explicitly raise an exception in __cmp__ -- this clarifies that cmp() Guido van Rossum <guido@python.org> parents: 26408 diff changeset	105 # Three-way comparison is not supported
b3f105399d22 Explicitly raise an exception in __cmp__ -- this clarifies that cmp() Guido van Rossum <guido@python.org> parents: 26408 diff changeset	106
b3f105399d22 Explicitly raise an exception in __cmp__ -- this clarifies that cmp() Guido van Rossum <guido@python.org> parents: 26408 diff changeset	107 def __cmp__(self, other):
b3f105399d22 Explicitly raise an exception in __cmp__ -- this clarifies that cmp() Guido van Rossum <guido@python.org> parents: 26408 diff changeset	108 raise TypeError, "can't compare sets using cmp()"
b3f105399d22 Explicitly raise an exception in __cmp__ -- this clarifies that cmp() Guido van Rossum <guido@python.org> parents: 26408 diff changeset	109
25018 81be61056717 Removed < <= > >= from the API. Implemented as comparisons of the Raymond Hettinger <python@rcn.com> parents: 25014 diff changeset	110 # Equality comparisons using the underlying dicts
24891 aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	111
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	112 def __eq__(self, other):
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	113 self._binary_sanity_check(other)
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	114 return self._data == other._data
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	115
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	116 def __ne__(self, other):
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	117 self._binary_sanity_check(other)
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	118 return self._data != other._data
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	119
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	120 # Copying operations
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	121
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	122 def copy(self):
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	123 """Return a shallow copy of a set."""
25010 35749db10809 1. Removed module self test in favor of unittests -- Timbot's suggestion. Raymond Hettinger <python@rcn.com> parents: 25007 diff changeset	124 result = self.__class__()
24934 6060cf6682c0 Now that __init__ transforms set elements, we know that all of the Raymond Hettinger <python@rcn.com> parents: 24931 diff changeset	125 result._data.update(self._data)
6060cf6682c0 Now that __init__ transforms set elements, we know that all of the Raymond Hettinger <python@rcn.com> parents: 24931 diff changeset	126 return result
24891 aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	127
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	128 __copy__ = copy # For the copy module
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	129
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	130 def __deepcopy__(self, memo):
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	131 """Return a deep copy of a set; used by copy module."""
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	132 # This pre-creates the result and inserts it in the memo
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	133 # early, in case the deep copy recurses into another reference
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	134 # to this same set. A set can't be an element of itself, but
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	135 # it can certainly contain an object that has a reference to
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	136 # itself.
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	137 from copy import deepcopy
25010 35749db10809 1. Removed module self test in favor of unittests -- Timbot's suggestion. Raymond Hettinger <python@rcn.com> parents: 25007 diff changeset	138 result = self.__class__()
24891 aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	139 memo[id(self)] = result
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	140 data = result._data
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	141 value = True
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	142 for elt in self:
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	143 data[deepcopy(elt, memo)] = value
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	144 return result
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	145
24943 5306408657fc Change the binary operators \|, &, ^, - to return NotImplemented rather Guido van Rossum <guido@python.org> parents: 24934 diff changeset	146 # Standard set operations: union, intersection, both differences.
5306408657fc Change the binary operators \|, &, ^, - to return NotImplemented rather Guido van Rossum <guido@python.org> parents: 24934 diff changeset	147 # Each has an operator version (e.g. __or__, invoked with \|) and a
5306408657fc Change the binary operators \|, &, ^, - to return NotImplemented rather Guido van Rossum <guido@python.org> parents: 24934 diff changeset	148 # method version (e.g. union).
25024 049096efa2c3 Record a clue about why __or__ is not union, etc. Tim Peters <tim.peters@gmail.com> parents: 25018 diff changeset	149 # Subtle: Each pair requires distinct code so that the outcome is
049096efa2c3 Record a clue about why __or__ is not union, etc. Tim Peters <tim.peters@gmail.com> parents: 25018 diff changeset	150 # correct when the type of other isn't suitable. For example, if
049096efa2c3 Record a clue about why __or__ is not union, etc. Tim Peters <tim.peters@gmail.com> parents: 25018 diff changeset	151 # we did "union = __or__" instead, then Set().union(3) would return
049096efa2c3 Record a clue about why __or__ is not union, etc. Tim Peters <tim.peters@gmail.com> parents: 25018 diff changeset	152 # NotImplemented instead of raising TypeError (albeit that why it
049096efa2c3 Record a clue about why __or__ is not union, etc. Tim Peters <tim.peters@gmail.com> parents: 25018 diff changeset	153 # raises TypeError as-is is also a bit subtle).
24943 5306408657fc Change the binary operators \|, &, ^, - to return NotImplemented rather Guido van Rossum <guido@python.org> parents: 24934 diff changeset	154
5306408657fc Change the binary operators \|, &, ^, - to return NotImplemented rather Guido van Rossum <guido@python.org> parents: 24934 diff changeset	155 def __or__(self, other):
5306408657fc Change the binary operators \|, &, ^, - to return NotImplemented rather Guido van Rossum <guido@python.org> parents: 24934 diff changeset	156 """Return the union of two sets as a new set.
5306408657fc Change the binary operators \|, &, ^, - to return NotImplemented rather Guido van Rossum <guido@python.org> parents: 24934 diff changeset	157
5306408657fc Change the binary operators \|, &, ^, - to return NotImplemented rather Guido van Rossum <guido@python.org> parents: 24934 diff changeset	158 (I.e. all elements that are in either set.)
5306408657fc Change the binary operators \|, &, ^, - to return NotImplemented rather Guido van Rossum <guido@python.org> parents: 24934 diff changeset	159 """
5306408657fc Change the binary operators \|, &, ^, - to return NotImplemented rather Guido van Rossum <guido@python.org> parents: 24934 diff changeset	160 if not isinstance(other, BaseSet):
5306408657fc Change the binary operators \|, &, ^, - to return NotImplemented rather Guido van Rossum <guido@python.org> parents: 24934 diff changeset	161 return NotImplemented
25034 4e996e959ec1 Sped union by a factor of 3-4. Tim Peters <tim.peters@gmail.com> parents: 25033 diff changeset	162 result = self.__class__()
4e996e959ec1 Sped union by a factor of 3-4. Tim Peters <tim.peters@gmail.com> parents: 25033 diff changeset	163 result._data = self._data.copy()
24943 5306408657fc Change the binary operators \|, &, ^, - to return NotImplemented rather Guido van Rossum <guido@python.org> parents: 24934 diff changeset	164 result._data.update(other._data)
5306408657fc Change the binary operators \|, &, ^, - to return NotImplemented rather Guido van Rossum <guido@python.org> parents: 24934 diff changeset	165 return result
24891 aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	166
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	167 def union(self, other):
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	168 """Return the union of two sets as a new set.
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	169
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	170 (I.e. all elements that are in either set.)
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	171 """
24943 5306408657fc Change the binary operators \|, &, ^, - to return NotImplemented rather Guido van Rossum <guido@python.org> parents: 24934 diff changeset	172 return self \| other
24891 aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	173
24943 5306408657fc Change the binary operators \|, &, ^, - to return NotImplemented rather Guido van Rossum <guido@python.org> parents: 24934 diff changeset	174 def __and__(self, other):
24891 aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	175 """Return the intersection of two sets as a new set.
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	176
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	177 (I.e. all elements that are in both sets.)
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	178 """
24943 5306408657fc Change the binary operators \|, &, ^, - to return NotImplemented rather Guido van Rossum <guido@python.org> parents: 24934 diff changeset	179 if not isinstance(other, BaseSet):
5306408657fc Change the binary operators \|, &, ^, - to return NotImplemented rather Guido van Rossum <guido@python.org> parents: 24934 diff changeset	180 return NotImplemented
24891 aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	181 if len(self) <= len(other):
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	182 little, big = self, other
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	183 else:
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	184 little, big = other, self
27589 e3fa8377f30c SF patch #678899: Save time and memory by using itertools in sets module. Raymond Hettinger <python@rcn.com> parents: 27244 diff changeset	185 common = ifilter(big._data.has_key, little)
25033 8c8052378017 Sped intersection by large factors (3-5x faster than before on sets of Tim Peters <tim.peters@gmail.com> parents: 25032 diff changeset	186 return self.__class__(common)
24891 aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	187
24943 5306408657fc Change the binary operators \|, &, ^, - to return NotImplemented rather Guido van Rossum <guido@python.org> parents: 24934 diff changeset	188 def intersection(self, other):
5306408657fc Change the binary operators \|, &, ^, - to return NotImplemented rather Guido van Rossum <guido@python.org> parents: 24934 diff changeset	189 """Return the intersection of two sets as a new set.
24891 aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	190
24943 5306408657fc Change the binary operators \|, &, ^, - to return NotImplemented rather Guido van Rossum <guido@python.org> parents: 24934 diff changeset	191 (I.e. all elements that are in both sets.)
5306408657fc Change the binary operators \|, &, ^, - to return NotImplemented rather Guido van Rossum <guido@python.org> parents: 24934 diff changeset	192 """
5306408657fc Change the binary operators \|, &, ^, - to return NotImplemented rather Guido van Rossum <guido@python.org> parents: 24934 diff changeset	193 return self & other
5306408657fc Change the binary operators \|, &, ^, - to return NotImplemented rather Guido van Rossum <guido@python.org> parents: 24934 diff changeset	194
5306408657fc Change the binary operators \|, &, ^, - to return NotImplemented rather Guido van Rossum <guido@python.org> parents: 24934 diff changeset	195 def __xor__(self, other):
24891 aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	196 """Return the symmetric difference of two sets as a new set.
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	197
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	198 (I.e. all elements that are in exactly one of the sets.)
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	199 """
24943 5306408657fc Change the binary operators \|, &, ^, - to return NotImplemented rather Guido van Rossum <guido@python.org> parents: 24934 diff changeset	200 if not isinstance(other, BaseSet):
5306408657fc Change the binary operators \|, &, ^, - to return NotImplemented rather Guido van Rossum <guido@python.org> parents: 24934 diff changeset	201 return NotImplemented
25010 35749db10809 1. Removed module self test in favor of unittests -- Timbot's suggestion. Raymond Hettinger <python@rcn.com> parents: 25007 diff changeset	202 result = self.__class__()
24891 aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	203 data = result._data
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	204 value = True
25035 d5ebd616a3e6 Gave __xor__/symmetric_difference a factor of 2-5 speed boost. Tim Peters <tim.peters@gmail.com> parents: 25034 diff changeset	205 selfdata = self._data
d5ebd616a3e6 Gave __xor__/symmetric_difference a factor of 2-5 speed boost. Tim Peters <tim.peters@gmail.com> parents: 25034 diff changeset	206 otherdata = other._data
27589 e3fa8377f30c SF patch #678899: Save time and memory by using itertools in sets module. Raymond Hettinger <python@rcn.com> parents: 27244 diff changeset	207 for elt in ifilter(otherdata.has_key, selfdata, True):
e3fa8377f30c SF patch #678899: Save time and memory by using itertools in sets module. Raymond Hettinger <python@rcn.com> parents: 27244 diff changeset	208 data[elt] = value
e3fa8377f30c SF patch #678899: Save time and memory by using itertools in sets module. Raymond Hettinger <python@rcn.com> parents: 27244 diff changeset	209 for elt in ifilter(selfdata.has_key, otherdata, True):
e3fa8377f30c SF patch #678899: Save time and memory by using itertools in sets module. Raymond Hettinger <python@rcn.com> parents: 27244 diff changeset	210 data[elt] = value
24891 aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	211 return result
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	212
24943 5306408657fc Change the binary operators \|, &, ^, - to return NotImplemented rather Guido van Rossum <guido@python.org> parents: 24934 diff changeset	213 def symmetric_difference(self, other):
5306408657fc Change the binary operators \|, &, ^, - to return NotImplemented rather Guido van Rossum <guido@python.org> parents: 24934 diff changeset	214 """Return the symmetric difference of two sets as a new set.
24891 aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	215
24943 5306408657fc Change the binary operators \|, &, ^, - to return NotImplemented rather Guido van Rossum <guido@python.org> parents: 24934 diff changeset	216 (I.e. all elements that are in exactly one of the sets.)
5306408657fc Change the binary operators \|, &, ^, - to return NotImplemented rather Guido van Rossum <guido@python.org> parents: 24934 diff changeset	217 """
5306408657fc Change the binary operators \|, &, ^, - to return NotImplemented rather Guido van Rossum <guido@python.org> parents: 24934 diff changeset	218 return self ^ other
5306408657fc Change the binary operators \|, &, ^, - to return NotImplemented rather Guido van Rossum <guido@python.org> parents: 24934 diff changeset	219
5306408657fc Change the binary operators \|, &, ^, - to return NotImplemented rather Guido van Rossum <guido@python.org> parents: 24934 diff changeset	220 def __sub__(self, other):
24891 aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	221 """Return the difference of two sets as a new Set.
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	222
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	223 (I.e. all elements that are in this set and not in the other.)
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	224 """
24943 5306408657fc Change the binary operators \|, &, ^, - to return NotImplemented rather Guido van Rossum <guido@python.org> parents: 24934 diff changeset	225 if not isinstance(other, BaseSet):
5306408657fc Change the binary operators \|, &, ^, - to return NotImplemented rather Guido van Rossum <guido@python.org> parents: 24934 diff changeset	226 return NotImplemented
25010 35749db10809 1. Removed module self test in favor of unittests -- Timbot's suggestion. Raymond Hettinger <python@rcn.com> parents: 25007 diff changeset	227 result = self.__class__()
24891 aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	228 data = result._data
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	229 value = True
27589 e3fa8377f30c SF patch #678899: Save time and memory by using itertools in sets module. Raymond Hettinger <python@rcn.com> parents: 27244 diff changeset	230 for elt in ifilter(other._data.has_key, self, True):
e3fa8377f30c SF patch #678899: Save time and memory by using itertools in sets module. Raymond Hettinger <python@rcn.com> parents: 27244 diff changeset	231 data[elt] = value
24891 aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	232 return result
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	233
24943 5306408657fc Change the binary operators \|, &, ^, - to return NotImplemented rather Guido van Rossum <guido@python.org> parents: 24934 diff changeset	234 def difference(self, other):
5306408657fc Change the binary operators \|, &, ^, - to return NotImplemented rather Guido van Rossum <guido@python.org> parents: 24934 diff changeset	235 """Return the difference of two sets as a new Set.
5306408657fc Change the binary operators \|, &, ^, - to return NotImplemented rather Guido van Rossum <guido@python.org> parents: 24934 diff changeset	236
5306408657fc Change the binary operators \|, &, ^, - to return NotImplemented rather Guido van Rossum <guido@python.org> parents: 24934 diff changeset	237 (I.e. all elements that are in this set and not in the other.)
5306408657fc Change the binary operators \|, &, ^, - to return NotImplemented rather Guido van Rossum <guido@python.org> parents: 24934 diff changeset	238 """
5306408657fc Change the binary operators \|, &, ^, - to return NotImplemented rather Guido van Rossum <guido@python.org> parents: 24934 diff changeset	239 return self - other
24891 aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	240
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	241 # Membership test
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	242
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	243 def __contains__(self, element):
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	244 """Report whether an element is a member of a set.
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	245
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	246 (Called in response to the expression `element in self'.)
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	247 """
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	248 try:
24927 c4a4b742ad6c Optimize try/except ordering in sets.py. Raymond Hettinger <python@rcn.com> parents: 24925 diff changeset	249 return element in self._data
c4a4b742ad6c Optimize try/except ordering in sets.py. Raymond Hettinger <python@rcn.com> parents: 24925 diff changeset	250 except TypeError:
24930 e8f77307d9c6 Ouch. The test suite really needs work!!!!! There were several Guido van Rossum <guido@python.org> parents: 24929 diff changeset	251 transform = getattr(element, "_as_temporarily_immutable", None)
24927 c4a4b742ad6c Optimize try/except ordering in sets.py. Raymond Hettinger <python@rcn.com> parents: 24925 diff changeset	252 if transform is None:
c4a4b742ad6c Optimize try/except ordering in sets.py. Raymond Hettinger <python@rcn.com> parents: 24925 diff changeset	253 raise # re-raise the TypeError exception we caught
c4a4b742ad6c Optimize try/except ordering in sets.py. Raymond Hettinger <python@rcn.com> parents: 24925 diff changeset	254 return transform() in self._data
24891 aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	255
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	256 # Subset and superset test
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	257
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	258 def issubset(self, other):
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	259 """Report whether another set contains this set."""
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	260 self._binary_sanity_check(other)
24928 0dd5bcc1ee0b Fast size check for sub/super set tests Raymond Hettinger <python@rcn.com> parents: 24927 diff changeset	261 if len(self) > len(other): # Fast check for obvious cases
0dd5bcc1ee0b Fast size check for sub/super set tests Raymond Hettinger <python@rcn.com> parents: 24927 diff changeset	262 return False
27589 e3fa8377f30c SF patch #678899: Save time and memory by using itertools in sets module. Raymond Hettinger <python@rcn.com> parents: 27244 diff changeset	263 for elt in ifilter(other._data.has_key, self, True):
e3fa8377f30c SF patch #678899: Save time and memory by using itertools in sets module. Raymond Hettinger <python@rcn.com> parents: 27244 diff changeset	264 return False
24891 aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	265 return True
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	266
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	267 def issuperset(self, other):
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	268 """Report whether this set contains another set."""
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	269 self._binary_sanity_check(other)
24928 0dd5bcc1ee0b Fast size check for sub/super set tests Raymond Hettinger <python@rcn.com> parents: 24927 diff changeset	270 if len(self) < len(other): # Fast check for obvious cases
0dd5bcc1ee0b Fast size check for sub/super set tests Raymond Hettinger <python@rcn.com> parents: 24927 diff changeset	271 return False
27589 e3fa8377f30c SF patch #678899: Save time and memory by using itertools in sets module. Raymond Hettinger <python@rcn.com> parents: 27244 diff changeset	272 for elt in ifilter(self._data.has_key, other, True):
27664 652df4549708 Whitespace normalization. Tim Peters <tim.peters@gmail.com> parents: 27590 diff changeset	273 return False
24891 aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	274 return True
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	275
25031 40e9cfde1c50 Implemented <, <=, >, >= for sets, giving subset and proper-subset Tim Peters <tim.peters@gmail.com> parents: 25024 diff changeset	276 # Inequality comparisons using the is-subset relation.
40e9cfde1c50 Implemented <, <=, >, >= for sets, giving subset and proper-subset Tim Peters <tim.peters@gmail.com> parents: 25024 diff changeset	277 __le__ = issubset
40e9cfde1c50 Implemented <, <=, >, >= for sets, giving subset and proper-subset Tim Peters <tim.peters@gmail.com> parents: 25024 diff changeset	278 __ge__ = issuperset
40e9cfde1c50 Implemented <, <=, >, >= for sets, giving subset and proper-subset Tim Peters <tim.peters@gmail.com> parents: 25024 diff changeset	279
40e9cfde1c50 Implemented <, <=, >, >= for sets, giving subset and proper-subset Tim Peters <tim.peters@gmail.com> parents: 25024 diff changeset	280 def __lt__(self, other):
40e9cfde1c50 Implemented <, <=, >, >= for sets, giving subset and proper-subset Tim Peters <tim.peters@gmail.com> parents: 25024 diff changeset	281 self._binary_sanity_check(other)
40e9cfde1c50 Implemented <, <=, >, >= for sets, giving subset and proper-subset Tim Peters <tim.peters@gmail.com> parents: 25024 diff changeset	282 return len(self) < len(other) and self.issubset(other)
40e9cfde1c50 Implemented <, <=, >, >= for sets, giving subset and proper-subset Tim Peters <tim.peters@gmail.com> parents: 25024 diff changeset	283
40e9cfde1c50 Implemented <, <=, >, >= for sets, giving subset and proper-subset Tim Peters <tim.peters@gmail.com> parents: 25024 diff changeset	284 def __gt__(self, other):
40e9cfde1c50 Implemented <, <=, >, >= for sets, giving subset and proper-subset Tim Peters <tim.peters@gmail.com> parents: 25024 diff changeset	285 self._binary_sanity_check(other)
40e9cfde1c50 Implemented <, <=, >, >= for sets, giving subset and proper-subset Tim Peters <tim.peters@gmail.com> parents: 25024 diff changeset	286 return len(self) > len(other) and self.issuperset(other)
40e9cfde1c50 Implemented <, <=, >, >= for sets, giving subset and proper-subset Tim Peters <tim.peters@gmail.com> parents: 25024 diff changeset	287
24891 aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	288 # Assorted helpers
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	289
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	290 def _binary_sanity_check(self, other):
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	291 # Check that the other argument to a binary operation is also
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	292 # a set, raising a TypeError otherwise.
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	293 if not isinstance(other, BaseSet):
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	294 raise TypeError, "Binary operation only permitted between sets"
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	295
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	296 def _compute_hash(self):
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	297 # Calculate hash code for a set by xor'ing the hash codes of
25006 0857aadc612a Comment repair. Tim Peters <tim.peters@gmail.com> parents: 24979 diff changeset	298 # the elements. This ensures that the hash code does not depend
0857aadc612a Comment repair. Tim Peters <tim.peters@gmail.com> parents: 24979 diff changeset	299 # on the order in which elements are added to the set. This is
0857aadc612a Comment repair. Tim Peters <tim.peters@gmail.com> parents: 24979 diff changeset	300 # not called __hash__ because a BaseSet should not be hashable;
0857aadc612a Comment repair. Tim Peters <tim.peters@gmail.com> parents: 24979 diff changeset	301 # only an ImmutableSet is hashable.
24891 aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	302 result = 0
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	303 for elt in self:
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	304 result ^= hash(elt)
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	305 return result
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	306
24930 e8f77307d9c6 Ouch. The test suite really needs work!!!!! There were several Guido van Rossum <guido@python.org> parents: 24929 diff changeset	307 def _update(self, iterable):
e8f77307d9c6 Ouch. The test suite really needs work!!!!! There were several Guido van Rossum <guido@python.org> parents: 24929 diff changeset	308 # The main loop for update() and the subclass __init__() methods.
e8f77307d9c6 Ouch. The test suite really needs work!!!!! There were several Guido van Rossum <guido@python.org> parents: 24929 diff changeset	309 data = self._data
25068 03eadc57d429 Sped _update(). Raymond Hettinger <python@rcn.com> parents: 25038 diff changeset	310
03eadc57d429 Sped _update(). Raymond Hettinger <python@rcn.com> parents: 25038 diff changeset	311 # Use the fast update() method when a dictionary is available.
03eadc57d429 Sped _update(). Raymond Hettinger <python@rcn.com> parents: 25038 diff changeset	312 if isinstance(iterable, BaseSet):
03eadc57d429 Sped _update(). Raymond Hettinger <python@rcn.com> parents: 25038 diff changeset	313 data.update(iterable._data)
03eadc57d429 Sped _update(). Raymond Hettinger <python@rcn.com> parents: 25038 diff changeset	314 return
03eadc57d429 Sped _update(). Raymond Hettinger <python@rcn.com> parents: 25038 diff changeset	315
26116 8965a2b804b5 Another attempt at making the set constructor both safe and fast. [SF Guido van Rossum <guido@python.org> parents: 26102 diff changeset	316 value = True
26102 1f365b98f11c _update(): Commented the new obscurity. Materialized into a tuple Tim Peters <tim.peters@gmail.com> parents: 26101 diff changeset	317
26116 8965a2b804b5 Another attempt at making the set constructor both safe and fast. [SF Guido van Rossum <guido@python.org> parents: 26102 diff changeset	318 if type(iterable) in (list, tuple, xrange):
8965a2b804b5 Another attempt at making the set constructor both safe and fast. [SF Guido van Rossum <guido@python.org> parents: 26102 diff changeset	319 # Optimized: we know that __iter__() and next() can't
8965a2b804b5 Another attempt at making the set constructor both safe and fast. [SF Guido van Rossum <guido@python.org> parents: 26102 diff changeset	320 # raise TypeError, so we can move 'try:' out of the loop.
8965a2b804b5 Another attempt at making the set constructor both safe and fast. [SF Guido van Rossum <guido@python.org> parents: 26102 diff changeset	321 it = iter(iterable)
8965a2b804b5 Another attempt at making the set constructor both safe and fast. [SF Guido van Rossum <guido@python.org> parents: 26102 diff changeset	322 while True:
8965a2b804b5 Another attempt at making the set constructor both safe and fast. [SF Guido van Rossum <guido@python.org> parents: 26102 diff changeset	323 try:
8965a2b804b5 Another attempt at making the set constructor both safe and fast. [SF Guido van Rossum <guido@python.org> parents: 26102 diff changeset	324 for element in it:
8965a2b804b5 Another attempt at making the set constructor both safe and fast. [SF Guido van Rossum <guido@python.org> parents: 26102 diff changeset	325 data[element] = value
8965a2b804b5 Another attempt at making the set constructor both safe and fast. [SF Guido van Rossum <guido@python.org> parents: 26102 diff changeset	326 return
8965a2b804b5 Another attempt at making the set constructor both safe and fast. [SF Guido van Rossum <guido@python.org> parents: 26102 diff changeset	327 except TypeError:
8965a2b804b5 Another attempt at making the set constructor both safe and fast. [SF Guido van Rossum <guido@python.org> parents: 26102 diff changeset	328 transform = getattr(element, "_as_immutable", None)
8965a2b804b5 Another attempt at making the set constructor both safe and fast. [SF Guido van Rossum <guido@python.org> parents: 26102 diff changeset	329 if transform is None:
8965a2b804b5 Another attempt at making the set constructor both safe and fast. [SF Guido van Rossum <guido@python.org> parents: 26102 diff changeset	330 raise # re-raise the TypeError exception we caught
8965a2b804b5 Another attempt at making the set constructor both safe and fast. [SF Guido van Rossum <guido@python.org> parents: 26102 diff changeset	331 data[transform()] = value
8965a2b804b5 Another attempt at making the set constructor both safe and fast. [SF Guido van Rossum <guido@python.org> parents: 26102 diff changeset	332 else:
8965a2b804b5 Another attempt at making the set constructor both safe and fast. [SF Guido van Rossum <guido@python.org> parents: 26102 diff changeset	333 # Safe: only catch TypeError where intended
8965a2b804b5 Another attempt at making the set constructor both safe and fast. [SF Guido van Rossum <guido@python.org> parents: 26102 diff changeset	334 for element in iterable:
8965a2b804b5 Another attempt at making the set constructor both safe and fast. [SF Guido van Rossum <guido@python.org> parents: 26102 diff changeset	335 try:
24931 c0e980ab54db Sped ._update() method by factoring try/except out of the inner loop. Raymond Hettinger <python@rcn.com> parents: 24930 diff changeset	336 data[element] = value
26116 8965a2b804b5 Another attempt at making the set constructor both safe and fast. [SF Guido van Rossum <guido@python.org> parents: 26102 diff changeset	337 except TypeError:
8965a2b804b5 Another attempt at making the set constructor both safe and fast. [SF Guido van Rossum <guido@python.org> parents: 26102 diff changeset	338 transform = getattr(element, "_as_immutable", None)
8965a2b804b5 Another attempt at making the set constructor both safe and fast. [SF Guido van Rossum <guido@python.org> parents: 26102 diff changeset	339 if transform is None:
8965a2b804b5 Another attempt at making the set constructor both safe and fast. [SF Guido van Rossum <guido@python.org> parents: 26102 diff changeset	340 raise # re-raise the TypeError exception we caught
8965a2b804b5 Another attempt at making the set constructor both safe and fast. [SF Guido van Rossum <guido@python.org> parents: 26102 diff changeset	341 data[transform()] = value
24930 e8f77307d9c6 Ouch. The test suite really needs work!!!!! There were several Guido van Rossum <guido@python.org> parents: 24929 diff changeset	342
24891 aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	343
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	344 class ImmutableSet(BaseSet):
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	345 """Immutable set class."""
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	346
24893 44d1d0b623a9 Fix typo in __slots__ of ImmutableSet. Guido van Rossum <guido@python.org> parents: 24891 diff changeset	347 __slots__ = ['_hashcode']
24891 aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	348
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	349 # BaseSet + hashing
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	350
24930 e8f77307d9c6 Ouch. The test suite really needs work!!!!! There were several Guido van Rossum <guido@python.org> parents: 24929 diff changeset	351 def __init__(self, iterable=None):
e8f77307d9c6 Ouch. The test suite really needs work!!!!! There were several Guido van Rossum <guido@python.org> parents: 24929 diff changeset	352 """Construct an immutable set from an optional iterable."""
24891 aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	353 self._hashcode = None
24930 e8f77307d9c6 Ouch. The test suite really needs work!!!!! There were several Guido van Rossum <guido@python.org> parents: 24929 diff changeset	354 self._data = {}
e8f77307d9c6 Ouch. The test suite really needs work!!!!! There were several Guido van Rossum <guido@python.org> parents: 24929 diff changeset	355 if iterable is not None:
e8f77307d9c6 Ouch. The test suite really needs work!!!!! There were several Guido van Rossum <guido@python.org> parents: 24929 diff changeset	356 self._update(iterable)
24891 aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	357
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	358 def __hash__(self):
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	359 if self._hashcode is None:
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	360 self._hashcode = self._compute_hash()
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	361 return self._hashcode
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	362
26197 cb71e7c620e2 Add getstate and setstate implementation to concrete set classes. Jeremy Hylton <jeremy@alum.mit.edu> parents: 26116 diff changeset	363 def __getstate__(self):
cb71e7c620e2 Add getstate and setstate implementation to concrete set classes. Jeremy Hylton <jeremy@alum.mit.edu> parents: 26116 diff changeset	364 return self._data, self._hashcode
cb71e7c620e2 Add getstate and setstate implementation to concrete set classes. Jeremy Hylton <jeremy@alum.mit.edu> parents: 26116 diff changeset	365
cb71e7c620e2 Add getstate and setstate implementation to concrete set classes. Jeremy Hylton <jeremy@alum.mit.edu> parents: 26116 diff changeset	366 def __setstate__(self, state):
cb71e7c620e2 Add getstate and setstate implementation to concrete set classes. Jeremy Hylton <jeremy@alum.mit.edu> parents: 26116 diff changeset	367 self._data, self._hashcode = state
24891 aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	368
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	369 class Set(BaseSet):
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	370 """ Mutable set class."""
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	371
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	372 __slots__ = []
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	373
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	374 # BaseSet + operations requiring mutability; no hashing
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	375
24930 e8f77307d9c6 Ouch. The test suite really needs work!!!!! There were several Guido van Rossum <guido@python.org> parents: 24929 diff changeset	376 def __init__(self, iterable=None):
e8f77307d9c6 Ouch. The test suite really needs work!!!!! There were several Guido van Rossum <guido@python.org> parents: 24929 diff changeset	377 """Construct a set from an optional iterable."""
e8f77307d9c6 Ouch. The test suite really needs work!!!!! There were several Guido van Rossum <guido@python.org> parents: 24929 diff changeset	378 self._data = {}
e8f77307d9c6 Ouch. The test suite really needs work!!!!! There were several Guido van Rossum <guido@python.org> parents: 24929 diff changeset	379 if iterable is not None:
e8f77307d9c6 Ouch. The test suite really needs work!!!!! There were several Guido van Rossum <guido@python.org> parents: 24929 diff changeset	380 self._update(iterable)
e8f77307d9c6 Ouch. The test suite really needs work!!!!! There were several Guido van Rossum <guido@python.org> parents: 24929 diff changeset	381
26197 cb71e7c620e2 Add getstate and setstate implementation to concrete set classes. Jeremy Hylton <jeremy@alum.mit.edu> parents: 26116 diff changeset	382 def __getstate__(self):
cb71e7c620e2 Add getstate and setstate implementation to concrete set classes. Jeremy Hylton <jeremy@alum.mit.edu> parents: 26116 diff changeset	383 # getstate's results are ignored if it is not
cb71e7c620e2 Add getstate and setstate implementation to concrete set classes. Jeremy Hylton <jeremy@alum.mit.edu> parents: 26116 diff changeset	384 return self._data,
cb71e7c620e2 Add getstate and setstate implementation to concrete set classes. Jeremy Hylton <jeremy@alum.mit.edu> parents: 26116 diff changeset	385
cb71e7c620e2 Add getstate and setstate implementation to concrete set classes. Jeremy Hylton <jeremy@alum.mit.edu> parents: 26116 diff changeset	386 def __setstate__(self, data):
cb71e7c620e2 Add getstate and setstate implementation to concrete set classes. Jeremy Hylton <jeremy@alum.mit.edu> parents: 26116 diff changeset	387 self._data, = data
cb71e7c620e2 Add getstate and setstate implementation to concrete set classes. Jeremy Hylton <jeremy@alum.mit.edu> parents: 26116 diff changeset	388
24930 e8f77307d9c6 Ouch. The test suite really needs work!!!!! There were several Guido van Rossum <guido@python.org> parents: 24929 diff changeset	389 def __hash__(self):
e8f77307d9c6 Ouch. The test suite really needs work!!!!! There were several Guido van Rossum <guido@python.org> parents: 24929 diff changeset	390 """A Set cannot be hashed."""
e8f77307d9c6 Ouch. The test suite really needs work!!!!! There were several Guido van Rossum <guido@python.org> parents: 24929 diff changeset	391 # We inherit object.__hash__, so we must deny this explicitly
e8f77307d9c6 Ouch. The test suite really needs work!!!!! There were several Guido van Rossum <guido@python.org> parents: 24929 diff changeset	392 raise TypeError, "Can't hash a Set, only an ImmutableSet."
24923 51c26994d8ec Move __init__ from BaseSet into Set and ImmutableSet. This causes a Guido van Rossum <guido@python.org> parents: 24921 diff changeset	393
25032 7fb3759d3866 Added a clue about why xyz_update isn't the same as __xyz__. Tim Peters <tim.peters@gmail.com> parents: 25031 diff changeset	394 # In-place union, intersection, differences.
7fb3759d3866 Added a clue about why xyz_update isn't the same as __xyz__. Tim Peters <tim.peters@gmail.com> parents: 25031 diff changeset	395 # Subtle: The xyz_update() functions deliberately return None,
7fb3759d3866 Added a clue about why xyz_update isn't the same as __xyz__. Tim Peters <tim.peters@gmail.com> parents: 25031 diff changeset	396 # as do all mutating operations on built-in container types.
7fb3759d3866 Added a clue about why xyz_update isn't the same as __xyz__. Tim Peters <tim.peters@gmail.com> parents: 25031 diff changeset	397 # The __xyz__ spellings have to return self, though.
24891 aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	398
25014 feeb0b02b8f2 At Tim Peter's suggestion, propagated GvR's binary operator changes to Raymond Hettinger <python@rcn.com> parents: 25012 diff changeset	399 def __ior__(self, other):
24891 aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	400 """Update a set with the union of itself and another."""
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	401 self._binary_sanity_check(other)
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	402 self._data.update(other._data)
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	403 return self
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	404
25014 feeb0b02b8f2 At Tim Peter's suggestion, propagated GvR's binary operator changes to Raymond Hettinger <python@rcn.com> parents: 25012 diff changeset	405 def union_update(self, other):
feeb0b02b8f2 At Tim Peter's suggestion, propagated GvR's binary operator changes to Raymond Hettinger <python@rcn.com> parents: 25012 diff changeset	406 """Update a set with the union of itself and another."""
feeb0b02b8f2 At Tim Peter's suggestion, propagated GvR's binary operator changes to Raymond Hettinger <python@rcn.com> parents: 25012 diff changeset	407 self \|= other
24891 aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	408
25014 feeb0b02b8f2 At Tim Peter's suggestion, propagated GvR's binary operator changes to Raymond Hettinger <python@rcn.com> parents: 25012 diff changeset	409 def __iand__(self, other):
24891 aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	410 """Update a set with the intersection of itself and another."""
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	411 self._binary_sanity_check(other)
25038 0b9792cbe900 Gave intersection_update a speed boost. Tim Peters <tim.peters@gmail.com> parents: 25037 diff changeset	412 self._data = (self & other)._data
24891 aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	413 return self
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	414
25014 feeb0b02b8f2 At Tim Peter's suggestion, propagated GvR's binary operator changes to Raymond Hettinger <python@rcn.com> parents: 25012 diff changeset	415 def intersection_update(self, other):
feeb0b02b8f2 At Tim Peter's suggestion, propagated GvR's binary operator changes to Raymond Hettinger <python@rcn.com> parents: 25012 diff changeset	416 """Update a set with the intersection of itself and another."""
feeb0b02b8f2 At Tim Peter's suggestion, propagated GvR's binary operator changes to Raymond Hettinger <python@rcn.com> parents: 25012 diff changeset	417 self &= other
24891 aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	418
25014 feeb0b02b8f2 At Tim Peter's suggestion, propagated GvR's binary operator changes to Raymond Hettinger <python@rcn.com> parents: 25012 diff changeset	419 def __ixor__(self, other):
24891 aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	420 """Update a set with the symmetric difference of itself and another."""
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	421 self._binary_sanity_check(other)
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	422 data = self._data
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	423 value = True
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	424 for elt in other:
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	425 if elt in data:
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	426 del data[elt]
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	427 else:
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	428 data[elt] = value
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	429 return self
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	430
25014 feeb0b02b8f2 At Tim Peter's suggestion, propagated GvR's binary operator changes to Raymond Hettinger <python@rcn.com> parents: 25012 diff changeset	431 def symmetric_difference_update(self, other):
feeb0b02b8f2 At Tim Peter's suggestion, propagated GvR's binary operator changes to Raymond Hettinger <python@rcn.com> parents: 25012 diff changeset	432 """Update a set with the symmetric difference of itself and another."""
feeb0b02b8f2 At Tim Peter's suggestion, propagated GvR's binary operator changes to Raymond Hettinger <python@rcn.com> parents: 25012 diff changeset	433 self ^= other
24891 aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	434
25014 feeb0b02b8f2 At Tim Peter's suggestion, propagated GvR's binary operator changes to Raymond Hettinger <python@rcn.com> parents: 25012 diff changeset	435 def __isub__(self, other):
24891 aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	436 """Remove all elements of another set from this set."""
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	437 self._binary_sanity_check(other)
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	438 data = self._data
27590 93210564bb46 One more use of ifilter() Raymond Hettinger <python@rcn.com> parents: 27589 diff changeset	439 for elt in ifilter(data.has_key, other):
93210564bb46 One more use of ifilter() Raymond Hettinger <python@rcn.com> parents: 27589 diff changeset	440 del data[elt]
24891 aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	441 return self
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	442
25014 feeb0b02b8f2 At Tim Peter's suggestion, propagated GvR's binary operator changes to Raymond Hettinger <python@rcn.com> parents: 25012 diff changeset	443 def difference_update(self, other):
feeb0b02b8f2 At Tim Peter's suggestion, propagated GvR's binary operator changes to Raymond Hettinger <python@rcn.com> parents: 25012 diff changeset	444 """Remove all elements of another set from this set."""
feeb0b02b8f2 At Tim Peter's suggestion, propagated GvR's binary operator changes to Raymond Hettinger <python@rcn.com> parents: 25012 diff changeset	445 self -= other
24891 aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	446
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	447 # Python dict-like mass mutations: update, clear
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	448
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	449 def update(self, iterable):
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	450 """Add all values from an iterable (such as a list or file)."""
24930 e8f77307d9c6 Ouch. The test suite really needs work!!!!! There were several Guido van Rossum <guido@python.org> parents: 24929 diff changeset	451 self._update(iterable)
24891 aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	452
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	453 def clear(self):
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	454 """Remove all elements from this set."""
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	455 self._data.clear()
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	456
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	457 # Single-element mutations: add, remove, discard
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	458
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	459 def add(self, element):
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	460 """Add an element to a set.
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	461
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	462 This has no effect if the element is already present.
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	463 """
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	464 try:
24927 c4a4b742ad6c Optimize try/except ordering in sets.py. Raymond Hettinger <python@rcn.com> parents: 24925 diff changeset	465 self._data[element] = True
c4a4b742ad6c Optimize try/except ordering in sets.py. Raymond Hettinger <python@rcn.com> parents: 24925 diff changeset	466 except TypeError:
24930 e8f77307d9c6 Ouch. The test suite really needs work!!!!! There were several Guido van Rossum <guido@python.org> parents: 24929 diff changeset	467 transform = getattr(element, "_as_immutable", None)
24927 c4a4b742ad6c Optimize try/except ordering in sets.py. Raymond Hettinger <python@rcn.com> parents: 24925 diff changeset	468 if transform is None:
c4a4b742ad6c Optimize try/except ordering in sets.py. Raymond Hettinger <python@rcn.com> parents: 24925 diff changeset	469 raise # re-raise the TypeError exception we caught
c4a4b742ad6c Optimize try/except ordering in sets.py. Raymond Hettinger <python@rcn.com> parents: 24925 diff changeset	470 self._data[transform()] = True
24891 aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	471
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	472 def remove(self, element):
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	473 """Remove an element from a set; it must be a member.
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	474
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	475 If the element is not a member, raise a KeyError.
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	476 """
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	477 try:
24927 c4a4b742ad6c Optimize try/except ordering in sets.py. Raymond Hettinger <python@rcn.com> parents: 24925 diff changeset	478 del self._data[element]
c4a4b742ad6c Optimize try/except ordering in sets.py. Raymond Hettinger <python@rcn.com> parents: 24925 diff changeset	479 except TypeError:
24930 e8f77307d9c6 Ouch. The test suite really needs work!!!!! There were several Guido van Rossum <guido@python.org> parents: 24929 diff changeset	480 transform = getattr(element, "_as_temporarily_immutable", None)
24927 c4a4b742ad6c Optimize try/except ordering in sets.py. Raymond Hettinger <python@rcn.com> parents: 24925 diff changeset	481 if transform is None:
c4a4b742ad6c Optimize try/except ordering in sets.py. Raymond Hettinger <python@rcn.com> parents: 24925 diff changeset	482 raise # re-raise the TypeError exception we caught
c4a4b742ad6c Optimize try/except ordering in sets.py. Raymond Hettinger <python@rcn.com> parents: 24925 diff changeset	483 del self._data[transform()]
24891 aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	484
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	485 def discard(self, element):
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	486 """Remove an element from a set if it is a member.
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	487
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	488 If the element is not a member, do nothing.
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	489 """
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	490 try:
24979 80ac86194a12 RH pointed out that discard(element) doesn't do the transformation on Guido van Rossum <guido@python.org> parents: 24943 diff changeset	491 self.remove(element)
24891 aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	492 except KeyError:
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	493 pass
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	494
24924 a1143224ee0d Rename popitem() to pop(). (An idea from SF patch 597444.) Guido van Rossum <guido@python.org> parents: 24923 diff changeset	495 def pop(self):
25007 b5b70e410f12 pop() docstring: this isn't a randomly-chosen element, it's merely Tim Peters <tim.peters@gmail.com> parents: 25006 diff changeset	496 """Remove and return an arbitrary set element."""
24891 aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	497 return self._data.popitem()[0]
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	498
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	499 def _as_immutable(self):
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	500 # Return a copy of self as an immutable set
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	501 return ImmutableSet(self)
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	502
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	503 def _as_temporarily_immutable(self):
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	504 # Return self wrapped in a temporarily immutable set
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	505 return _TemporarilyImmutableSet(self)
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	506
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	507
25010 35749db10809 1. Removed module self test in favor of unittests -- Timbot's suggestion. Raymond Hettinger <python@rcn.com> parents: 25007 diff changeset	508 class _TemporarilyImmutableSet(BaseSet):
24891 aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	509 # Wrap a mutable set as if it was temporarily immutable.
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	510 # This only supplies hashing and equality comparisons.
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	511
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	512 def __init__(self, set):
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	513 self._set = set
25010 35749db10809 1. Removed module self test in favor of unittests -- Timbot's suggestion. Raymond Hettinger <python@rcn.com> parents: 25007 diff changeset	514 self._data = set._data # Needed by ImmutableSet.__eq__()
24891 aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	515
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	516 def __hash__(self):
25012 f2d75749e61c Since instances of _TemporarilyImmutableSet are always thrown away Raymond Hettinger <python@rcn.com> parents: 25010 diff changeset	517 return self._set._compute_hash()

Mercurial > cpython-lru_cache-weakref

annotate Lib/sets.py @ 27664:652df4549708 legacy-trunk