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

annotate Lib/sets.py @ 80661:94de77bd0b4b 2.7

Issue #16194: document imp.load_dynamic problems when read several extension modules from the same binary object file.

author	Andrew Svetlov <andrew.svetlov@gmail.com>
date	Thu, 29 Nov 2012 19:51:28 +0200
parents	751c6dd71b5e
children

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
29597 466b579e0088 Portion of SF patch #761104. Fixes a minor docstring error. Raymond Hettinger <python@rcn.com> parents: 28127 diff changeset	28 _TemporarilyImmutableSet -- A wrapper around a Set, hashable,
466b579e0088 Portion of SF patch #761104. Fixes a minor docstring error. Raymond Hettinger <python@rcn.com> parents: 28127 diff changeset	29 giving the same hash value as the immutable set equivalent
466b579e0088 Portion of SF patch #761104. Fixes a minor docstring error. Raymond Hettinger <python@rcn.com> parents: 28127 diff changeset	30 would have. Do not use this class directly.
24891 aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	31
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	32 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	33 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	34 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	35 the one you tried adding).
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	36
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	37 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	38 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	39 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	40
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 # Code history:
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	44 #
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	45 # - 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	46 # 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	47 #
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	48 # - 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	49 # 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	50 #
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	51 # - 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	52 # 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	53 #
24930 e8f77307d9c6 Ouch. The test suite really needs work!!!!! There were several Guido van Rossum <guido@python.org> parents: 24929 diff changeset	54 # - 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	55 # improvements.
24891 aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	56
63528 751c6dd71b5e Merged revisions 77310-77311 via svnmerge from Ezio Melotti <ezio.melotti@gmail.com> parents: 47961 diff changeset	57 from itertools import ifilter, ifilterfalse
24891 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']
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	60
40614 b303fb383fa4 Deprecate the sets module. Brett Cannon <bcannon@gmail.com> parents: 35337 diff changeset	61 import warnings
b303fb383fa4 Deprecate the sets module. Brett Cannon <bcannon@gmail.com> parents: 35337 diff changeset	62 warnings.warn("the sets module is deprecated", DeprecationWarning,
b303fb383fa4 Deprecate the sets module. Brett Cannon <bcannon@gmail.com> parents: 35337 diff changeset	63 stacklevel=2)
b303fb383fa4 Deprecate the sets module. Brett Cannon <bcannon@gmail.com> parents: 35337 diff changeset	64
24891 aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	65 class BaseSet(object):
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	66 """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	67
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	68 __slots__ = ['_data']
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	69
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	70 # Constructor
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	71
24923 51c26994d8ec Move __init__ from BaseSet into Set and ImmutableSet. This causes a Guido van Rossum <guido@python.org> parents: 24921 diff changeset	72 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	73 """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	74 # 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	75 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	76 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	77 "Use Set or ImmutableSet.")
24891 aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	78
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	79 # Standard protocols: __len__, __repr__, __str__, __iter__
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	80
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	81 def __len__(self):
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	82 """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	83 return len(self._data)
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 def __repr__(self):
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	86 """Return string representation of a set.
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	87
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	88 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	89 """
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	90 return self._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 # __str__ is the same as __repr__
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	93 __str__ = __repr__
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	94
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	95 def _repr(self, sorted=False):
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	96 elements = self._data.keys()
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	97 if sorted:
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	98 elements.sort()
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	99 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	100
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	101 def __iter__(self):
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	102 """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	103
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	104 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	105 """
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	106 return self._data.iterkeys()
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	107
28127 5f923165319d SF bug 693121: Set == non-Set is a TypeError. Tim Peters <tim.peters@gmail.com> parents: 27887 diff changeset	108 # Three-way comparison is not supported. However, because __eq__ is
5f923165319d SF bug 693121: Set == non-Set is a TypeError. Tim Peters <tim.peters@gmail.com> parents: 27887 diff changeset	109 # tried before __cmp__, if Set x == Set y, x.__eq__(y) returns True and
5f923165319d SF bug 693121: Set == non-Set is a TypeError. Tim Peters <tim.peters@gmail.com> parents: 27887 diff changeset	110 # then cmp(x, y) returns 0 (Python doesn't actually call __cmp__ in this
5f923165319d SF bug 693121: Set == non-Set is a TypeError. Tim Peters <tim.peters@gmail.com> parents: 27887 diff changeset	111 # case).
27244 b3f105399d22 Explicitly raise an exception in __cmp__ -- this clarifies that cmp() Guido van Rossum <guido@python.org> parents: 26408 diff changeset	112
b3f105399d22 Explicitly raise an exception in __cmp__ -- this clarifies that cmp() Guido van Rossum <guido@python.org> parents: 26408 diff changeset	113 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	114 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	115
28127 5f923165319d SF bug 693121: Set == non-Set is a TypeError. Tim Peters <tim.peters@gmail.com> parents: 27887 diff changeset	116 # Equality comparisons using the underlying dicts. Mixed-type comparisons
5f923165319d SF bug 693121: Set == non-Set is a TypeError. Tim Peters <tim.peters@gmail.com> parents: 27887 diff changeset	117 # are allowed here, where Set == z for non-Set z always returns False,
5f923165319d SF bug 693121: Set == non-Set is a TypeError. Tim Peters <tim.peters@gmail.com> parents: 27887 diff changeset	118 # and Set != z always True. This allows expressions like "x in y" to
5f923165319d SF bug 693121: Set == non-Set is a TypeError. Tim Peters <tim.peters@gmail.com> parents: 27887 diff changeset	119 # give the expected result when y is a sequence of mixed types, not
5f923165319d SF bug 693121: Set == non-Set is a TypeError. Tim Peters <tim.peters@gmail.com> parents: 27887 diff changeset	120 # raising a pointless TypeError just because y contains a Set, or x is
5f923165319d SF bug 693121: Set == non-Set is a TypeError. Tim Peters <tim.peters@gmail.com> parents: 27887 diff changeset	121 # a Set and y contain's a non-set ("in" invokes only __eq__).
5f923165319d SF bug 693121: Set == non-Set is a TypeError. Tim Peters <tim.peters@gmail.com> parents: 27887 diff changeset	122 # Subtle: it would be nicer if __eq__ and __ne__ could return
5f923165319d SF bug 693121: Set == non-Set is a TypeError. Tim Peters <tim.peters@gmail.com> parents: 27887 diff changeset	123 # NotImplemented instead of True or False. Then the other comparand
5f923165319d SF bug 693121: Set == non-Set is a TypeError. Tim Peters <tim.peters@gmail.com> parents: 27887 diff changeset	124 # would get a chance to determine the result, and if the other comparand
5f923165319d SF bug 693121: Set == non-Set is a TypeError. Tim Peters <tim.peters@gmail.com> parents: 27887 diff changeset	125 # also returned NotImplemented then it would fall back to object address
5f923165319d SF bug 693121: Set == non-Set is a TypeError. Tim Peters <tim.peters@gmail.com> parents: 27887 diff changeset	126 # comparison (which would always return False for __eq__ and always
5f923165319d SF bug 693121: Set == non-Set is a TypeError. Tim Peters <tim.peters@gmail.com> parents: 27887 diff changeset	127 # True for __ne__). However, that doesn't work, because this type
5f923165319d SF bug 693121: Set == non-Set is a TypeError. Tim Peters <tim.peters@gmail.com> parents: 27887 diff changeset	128 # also implements __cmp__: if, e.g., __eq__ returns NotImplemented,
5f923165319d SF bug 693121: Set == non-Set is a TypeError. Tim Peters <tim.peters@gmail.com> parents: 27887 diff changeset	129 # Python tries __cmp__ next, and the __cmp__ here then raises TypeError.
24891 aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	130
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	131 def __eq__(self, other):
28127 5f923165319d SF bug 693121: Set == non-Set is a TypeError. Tim Peters <tim.peters@gmail.com> parents: 27887 diff changeset	132 if isinstance(other, BaseSet):
5f923165319d SF bug 693121: Set == non-Set is a TypeError. Tim Peters <tim.peters@gmail.com> parents: 27887 diff changeset	133 return self._data == other._data
5f923165319d SF bug 693121: Set == non-Set is a TypeError. Tim Peters <tim.peters@gmail.com> parents: 27887 diff changeset	134 else:
5f923165319d SF bug 693121: Set == non-Set is a TypeError. Tim Peters <tim.peters@gmail.com> parents: 27887 diff changeset	135 return False
24891 aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	136
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	137 def __ne__(self, other):
28127 5f923165319d SF bug 693121: Set == non-Set is a TypeError. Tim Peters <tim.peters@gmail.com> parents: 27887 diff changeset	138 if isinstance(other, BaseSet):
5f923165319d SF bug 693121: Set == non-Set is a TypeError. Tim Peters <tim.peters@gmail.com> parents: 27887 diff changeset	139 return self._data != other._data
5f923165319d SF bug 693121: Set == non-Set is a TypeError. Tim Peters <tim.peters@gmail.com> parents: 27887 diff changeset	140 else:
5f923165319d SF bug 693121: Set == non-Set is a TypeError. Tim Peters <tim.peters@gmail.com> parents: 27887 diff changeset	141 return True
24891 aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	142
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	143 # Copying operations
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	144
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	145 def copy(self):
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	146 """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	147 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	148 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	149 return result
24891 aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	150
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	151 __copy__ = copy # For the copy module
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	152
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	153 def __deepcopy__(self, memo):
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	154 """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	155 # 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	156 # 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	157 # 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	158 # 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	159 # itself.
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	160 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	161 result = self.__class__()
24891 aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	162 memo[id(self)] = result
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	163 data = result._data
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	164 value = True
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	165 for elt in self:
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	166 data[deepcopy(elt, memo)] = value
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	167 return result
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	168
24943 5306408657fc Change the binary operators \|, &, ^, - to return NotImplemented rather Guido van Rossum <guido@python.org> parents: 24934 diff changeset	169 # 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	170 # 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	171 # 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	172 # 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	173 # 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	174 # 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	175 # 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	176 # 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	177
5306408657fc Change the binary operators \|, &, ^, - to return NotImplemented rather Guido van Rossum <guido@python.org> parents: 24934 diff changeset	178 def __or__(self, other):
5306408657fc Change the binary operators \|, &, ^, - to return NotImplemented rather Guido van Rossum <guido@python.org> parents: 24934 diff changeset	179 """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	180
5306408657fc Change the binary operators \|, &, ^, - to return NotImplemented rather Guido van Rossum <guido@python.org> parents: 24934 diff changeset	181 (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	182 """
5306408657fc Change the binary operators \|, &, ^, - to return NotImplemented rather Guido van Rossum <guido@python.org> parents: 24934 diff changeset	183 if not isinstance(other, BaseSet):
5306408657fc Change the binary operators \|, &, ^, - to return NotImplemented rather Guido van Rossum <guido@python.org> parents: 24934 diff changeset	184 return NotImplemented
30176 3db50d31340d Improvements to set.py: Raymond Hettinger <python@rcn.com> parents: 30171 diff changeset	185 return self.union(other)
24891 aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	186
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	187 def union(self, other):
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	188 """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	189
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	190 (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	191 """
30176 3db50d31340d Improvements to set.py: Raymond Hettinger <python@rcn.com> parents: 30171 diff changeset	192 result = self.__class__(self)
3db50d31340d Improvements to set.py: Raymond Hettinger <python@rcn.com> parents: 30171 diff changeset	193 result._update(other)
3db50d31340d Improvements to set.py: Raymond Hettinger <python@rcn.com> parents: 30171 diff changeset	194 return result
24891 aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	195
24943 5306408657fc Change the binary operators \|, &, ^, - to return NotImplemented rather Guido van Rossum <guido@python.org> parents: 24934 diff changeset	196 def __and__(self, other):
24891 aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	197 """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	198
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	199 (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	200 """
24943 5306408657fc Change the binary operators \|, &, ^, - to return NotImplemented rather Guido van Rossum <guido@python.org> parents: 24934 diff changeset	201 if not isinstance(other, BaseSet):
5306408657fc Change the binary operators \|, &, ^, - to return NotImplemented rather Guido van Rossum <guido@python.org> parents: 24934 diff changeset	202 return NotImplemented
30176 3db50d31340d Improvements to set.py: Raymond Hettinger <python@rcn.com> parents: 30171 diff changeset	203 return self.intersection(other)
3db50d31340d Improvements to set.py: Raymond Hettinger <python@rcn.com> parents: 30171 diff changeset	204
3db50d31340d Improvements to set.py: Raymond Hettinger <python@rcn.com> parents: 30171 diff changeset	205 def intersection(self, other):
3db50d31340d Improvements to set.py: Raymond Hettinger <python@rcn.com> parents: 30171 diff changeset	206 """Return the intersection of two sets as a new set.
3db50d31340d Improvements to set.py: Raymond Hettinger <python@rcn.com> parents: 30171 diff changeset	207
3db50d31340d Improvements to set.py: Raymond Hettinger <python@rcn.com> parents: 30171 diff changeset	208 (I.e. all elements that are in both sets.)
3db50d31340d Improvements to set.py: Raymond Hettinger <python@rcn.com> parents: 30171 diff changeset	209 """
3db50d31340d Improvements to set.py: Raymond Hettinger <python@rcn.com> parents: 30171 diff changeset	210 if not isinstance(other, BaseSet):
3db50d31340d Improvements to set.py: Raymond Hettinger <python@rcn.com> parents: 30171 diff changeset	211 other = Set(other)
24891 aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	212 if len(self) <= len(other):
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	213 little, big = self, other
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	214 else:
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	215 little, big = other, self
63528 751c6dd71b5e Merged revisions 77310-77311 via svnmerge from Ezio Melotti <ezio.melotti@gmail.com> parents: 47961 diff changeset	216 common = ifilter(big._data.__contains__, 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	217 return self.__class__(common)
24891 aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	218
24943 5306408657fc Change the binary operators \|, &, ^, - to return NotImplemented rather Guido van Rossum <guido@python.org> parents: 24934 diff changeset	219 def __xor__(self, other):
24891 aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	220 """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	221
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	222 (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	223 """
24943 5306408657fc Change the binary operators \|, &, ^, - to return NotImplemented rather Guido van Rossum <guido@python.org> parents: 24934 diff changeset	224 if not isinstance(other, BaseSet):
5306408657fc Change the binary operators \|, &, ^, - to return NotImplemented rather Guido van Rossum <guido@python.org> parents: 24934 diff changeset	225 return NotImplemented
30176 3db50d31340d Improvements to set.py: Raymond Hettinger <python@rcn.com> parents: 30171 diff changeset	226 return self.symmetric_difference(other)
24891 aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	227
24943 5306408657fc Change the binary operators \|, &, ^, - to return NotImplemented rather Guido van Rossum <guido@python.org> parents: 24934 diff changeset	228 def symmetric_difference(self, other):
5306408657fc Change the binary operators \|, &, ^, - to return NotImplemented rather Guido van Rossum <guido@python.org> parents: 24934 diff changeset	229 """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	230
24943 5306408657fc Change the binary operators \|, &, ^, - to return NotImplemented rather Guido van Rossum <guido@python.org> parents: 24934 diff changeset	231 (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	232 """
30176 3db50d31340d Improvements to set.py: Raymond Hettinger <python@rcn.com> parents: 30171 diff changeset	233 result = self.__class__()
3db50d31340d Improvements to set.py: Raymond Hettinger <python@rcn.com> parents: 30171 diff changeset	234 data = result._data
3db50d31340d Improvements to set.py: Raymond Hettinger <python@rcn.com> parents: 30171 diff changeset	235 value = True
3db50d31340d Improvements to set.py: Raymond Hettinger <python@rcn.com> parents: 30171 diff changeset	236 selfdata = self._data
3db50d31340d Improvements to set.py: Raymond Hettinger <python@rcn.com> parents: 30171 diff changeset	237 try:
3db50d31340d Improvements to set.py: Raymond Hettinger <python@rcn.com> parents: 30171 diff changeset	238 otherdata = other._data
3db50d31340d Improvements to set.py: Raymond Hettinger <python@rcn.com> parents: 30171 diff changeset	239 except AttributeError:
3db50d31340d Improvements to set.py: Raymond Hettinger <python@rcn.com> parents: 30171 diff changeset	240 otherdata = Set(other)._data
63528 751c6dd71b5e Merged revisions 77310-77311 via svnmerge from Ezio Melotti <ezio.melotti@gmail.com> parents: 47961 diff changeset	241 for elt in ifilterfalse(otherdata.__contains__, selfdata):
30176 3db50d31340d Improvements to set.py: Raymond Hettinger <python@rcn.com> parents: 30171 diff changeset	242 data[elt] = value
63528 751c6dd71b5e Merged revisions 77310-77311 via svnmerge from Ezio Melotti <ezio.melotti@gmail.com> parents: 47961 diff changeset	243 for elt in ifilterfalse(selfdata.__contains__, otherdata):
30176 3db50d31340d Improvements to set.py: Raymond Hettinger <python@rcn.com> parents: 30171 diff changeset	244 data[elt] = value
3db50d31340d Improvements to set.py: Raymond Hettinger <python@rcn.com> parents: 30171 diff changeset	245 return result
24943 5306408657fc Change the binary operators \|, &, ^, - to return NotImplemented rather Guido van Rossum <guido@python.org> parents: 24934 diff changeset	246
5306408657fc Change the binary operators \|, &, ^, - to return NotImplemented rather Guido van Rossum <guido@python.org> parents: 24934 diff changeset	247 def __sub__(self, other):
24891 aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	248 """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	249
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	250 (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	251 """
24943 5306408657fc Change the binary operators \|, &, ^, - to return NotImplemented rather Guido van Rossum <guido@python.org> parents: 24934 diff changeset	252 if not isinstance(other, BaseSet):
5306408657fc Change the binary operators \|, &, ^, - to return NotImplemented rather Guido van Rossum <guido@python.org> parents: 24934 diff changeset	253 return NotImplemented
30176 3db50d31340d Improvements to set.py: Raymond Hettinger <python@rcn.com> parents: 30171 diff changeset	254 return self.difference(other)
24891 aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	255
24943 5306408657fc Change the binary operators \|, &, ^, - to return NotImplemented rather Guido van Rossum <guido@python.org> parents: 24934 diff changeset	256 def difference(self, other):
5306408657fc Change the binary operators \|, &, ^, - to return NotImplemented rather Guido van Rossum <guido@python.org> parents: 24934 diff changeset	257 """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	258
5306408657fc Change the binary operators \|, &, ^, - to return NotImplemented rather Guido van Rossum <guido@python.org> parents: 24934 diff changeset	259 (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	260 """
30176 3db50d31340d Improvements to set.py: Raymond Hettinger <python@rcn.com> parents: 30171 diff changeset	261 result = self.__class__()
3db50d31340d Improvements to set.py: Raymond Hettinger <python@rcn.com> parents: 30171 diff changeset	262 data = result._data
3db50d31340d Improvements to set.py: Raymond Hettinger <python@rcn.com> parents: 30171 diff changeset	263 try:
3db50d31340d Improvements to set.py: Raymond Hettinger <python@rcn.com> parents: 30171 diff changeset	264 otherdata = other._data
3db50d31340d Improvements to set.py: Raymond Hettinger <python@rcn.com> parents: 30171 diff changeset	265 except AttributeError:
3db50d31340d Improvements to set.py: Raymond Hettinger <python@rcn.com> parents: 30171 diff changeset	266 otherdata = Set(other)._data
3db50d31340d Improvements to set.py: Raymond Hettinger <python@rcn.com> parents: 30171 diff changeset	267 value = True
63528 751c6dd71b5e Merged revisions 77310-77311 via svnmerge from Ezio Melotti <ezio.melotti@gmail.com> parents: 47961 diff changeset	268 for elt in ifilterfalse(otherdata.__contains__, self):
30176 3db50d31340d Improvements to set.py: Raymond Hettinger <python@rcn.com> parents: 30171 diff changeset	269 data[elt] = value
3db50d31340d Improvements to set.py: Raymond Hettinger <python@rcn.com> parents: 30171 diff changeset	270 return result
24891 aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	271
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	272 # Membership test
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	273
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	274 def __contains__(self, element):
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	275 """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	276
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	277 (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	278 """
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	279 try:
24927 c4a4b742ad6c Optimize try/except ordering in sets.py. Raymond Hettinger <python@rcn.com> parents: 24925 diff changeset	280 return element in self._data
c4a4b742ad6c Optimize try/except ordering in sets.py. Raymond Hettinger <python@rcn.com> parents: 24925 diff changeset	281 except TypeError:
27887 cedf9efa68f8 SF bug #663701: sets module review Raymond Hettinger <python@rcn.com> parents: 27769 diff changeset	282 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	283 if transform is None:
c4a4b742ad6c Optimize try/except ordering in sets.py. Raymond Hettinger <python@rcn.com> parents: 24925 diff changeset	284 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	285 return transform() in self._data
24891 aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	286
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	287 # Subset and superset test
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	288
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	289 def issubset(self, other):
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	290 """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	291 self._binary_sanity_check(other)
24928 0dd5bcc1ee0b Fast size check for sub/super set tests Raymond Hettinger <python@rcn.com> parents: 24927 diff changeset	292 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	293 return False
63528 751c6dd71b5e Merged revisions 77310-77311 via svnmerge from Ezio Melotti <ezio.melotti@gmail.com> parents: 47961 diff changeset	294 for elt in ifilterfalse(other._data.__contains__, 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	295 return False
24891 aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	296 return True
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	297
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	298 def issuperset(self, other):
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	299 """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	300 self._binary_sanity_check(other)
24928 0dd5bcc1ee0b Fast size check for sub/super set tests Raymond Hettinger <python@rcn.com> parents: 24927 diff changeset	301 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	302 return False
63528 751c6dd71b5e Merged revisions 77310-77311 via svnmerge from Ezio Melotti <ezio.melotti@gmail.com> parents: 47961 diff changeset	303 for elt in ifilterfalse(self._data.__contains__, other):
27664 652df4549708 Whitespace normalization. Tim Peters <tim.peters@gmail.com> parents: 27590 diff changeset	304 return False
24891 aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	305 return True
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	306
25031 40e9cfde1c50 Implemented <, <=, >, >= for sets, giving subset and proper-subset Tim Peters <tim.peters@gmail.com> parents: 25024 diff changeset	307 # 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	308 __le__ = issubset
40e9cfde1c50 Implemented <, <=, >, >= for sets, giving subset and proper-subset Tim Peters <tim.peters@gmail.com> parents: 25024 diff changeset	309 __ge__ = issuperset
40e9cfde1c50 Implemented <, <=, >, >= for sets, giving subset and proper-subset Tim Peters <tim.peters@gmail.com> parents: 25024 diff changeset	310
40e9cfde1c50 Implemented <, <=, >, >= for sets, giving subset and proper-subset Tim Peters <tim.peters@gmail.com> parents: 25024 diff changeset	311 def __lt__(self, other):
40e9cfde1c50 Implemented <, <=, >, >= for sets, giving subset and proper-subset Tim Peters <tim.peters@gmail.com> parents: 25024 diff changeset	312 self._binary_sanity_check(other)
40e9cfde1c50 Implemented <, <=, >, >= for sets, giving subset and proper-subset Tim Peters <tim.peters@gmail.com> parents: 25024 diff changeset	313 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	314
40e9cfde1c50 Implemented <, <=, >, >= for sets, giving subset and proper-subset Tim Peters <tim.peters@gmail.com> parents: 25024 diff changeset	315 def __gt__(self, other):
40e9cfde1c50 Implemented <, <=, >, >= for sets, giving subset and proper-subset Tim Peters <tim.peters@gmail.com> parents: 25024 diff changeset	316 self._binary_sanity_check(other)
40e9cfde1c50 Implemented <, <=, >, >= for sets, giving subset and proper-subset Tim Peters <tim.peters@gmail.com> parents: 25024 diff changeset	317 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	318
63528 751c6dd71b5e Merged revisions 77310-77311 via svnmerge from Ezio Melotti <ezio.melotti@gmail.com> parents: 47961 diff changeset	319 # We inherit object.__hash__, so we must deny this explicitly
751c6dd71b5e Merged revisions 77310-77311 via svnmerge from Ezio Melotti <ezio.melotti@gmail.com> parents: 47961 diff changeset	320 __hash__ = None
751c6dd71b5e Merged revisions 77310-77311 via svnmerge from Ezio Melotti <ezio.melotti@gmail.com> parents: 47961 diff changeset	321
24891 aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	322 # Assorted helpers
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	323
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	324 def _binary_sanity_check(self, other):
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	325 # 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	326 # a set, raising a TypeError otherwise.
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	327 if not isinstance(other, BaseSet):
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	328 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	329
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	330 def _compute_hash(self):
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	331 # 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	332 # the elements. This ensures that the hash code does not depend
0857aadc612a Comment repair. Tim Peters <tim.peters@gmail.com> parents: 24979 diff changeset	333 # 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	334 # not called __hash__ because a BaseSet should not be hashable;
0857aadc612a Comment repair. Tim Peters <tim.peters@gmail.com> parents: 24979 diff changeset	335 # only an ImmutableSet is hashable.
24891 aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	336 result = 0
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	337 for elt in self:
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	338 result ^= hash(elt)
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	339 return result
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	340
24930 e8f77307d9c6 Ouch. The test suite really needs work!!!!! There were several Guido van Rossum <guido@python.org> parents: 24929 diff changeset	341 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	342 # 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	343 data = self._data
25068 03eadc57d429 Sped _update(). Raymond Hettinger <python@rcn.com> parents: 25038 diff changeset	344
03eadc57d429 Sped _update(). Raymond Hettinger <python@rcn.com> parents: 25038 diff changeset	345 # Use the fast update() method when a dictionary is available.
03eadc57d429 Sped _update(). Raymond Hettinger <python@rcn.com> parents: 25038 diff changeset	346 if isinstance(iterable, BaseSet):
03eadc57d429 Sped _update(). Raymond Hettinger <python@rcn.com> parents: 25038 diff changeset	347 data.update(iterable._data)
03eadc57d429 Sped _update(). Raymond Hettinger <python@rcn.com> parents: 25038 diff changeset	348 return
03eadc57d429 Sped _update(). Raymond Hettinger <python@rcn.com> parents: 25038 diff changeset	349
26116 8965a2b804b5 Another attempt at making the set constructor both safe and fast. [SF Guido van Rossum <guido@python.org> parents: 26102 diff changeset	350 value = True
26102 1f365b98f11c _update(): Commented the new obscurity. Materialized into a tuple Tim Peters <tim.peters@gmail.com> parents: 26101 diff changeset	351
26116 8965a2b804b5 Another attempt at making the set constructor both safe and fast. [SF Guido van Rossum <guido@python.org> parents: 26102 diff changeset	352 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	353 # 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	354 # 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	355 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	356 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	357 try:
8965a2b804b5 Another attempt at making the set constructor both safe and fast. [SF Guido van Rossum <guido@python.org> parents: 26102 diff changeset	358 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	359 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	360 return
8965a2b804b5 Another attempt at making the set constructor both safe and fast. [SF Guido van Rossum <guido@python.org> parents: 26102 diff changeset	361 except TypeError:
27887 cedf9efa68f8 SF bug #663701: sets module review Raymond Hettinger <python@rcn.com> parents: 27769 diff changeset	362 transform = getattr(element, "__as_immutable__", None)
26116 8965a2b804b5 Another attempt at making the set constructor both safe and fast. [SF Guido van Rossum <guido@python.org> parents: 26102 diff changeset	363 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	364 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	365 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	366 else:
8965a2b804b5 Another attempt at making the set constructor both safe and fast. [SF Guido van Rossum <guido@python.org> parents: 26102 diff changeset	367 # 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	368 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	369 try:
24931 c0e980ab54db Sped ._update() method by factoring try/except out of the inner loop. Raymond Hettinger <python@rcn.com> parents: 24930 diff changeset	370 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	371 except TypeError:
27887 cedf9efa68f8 SF bug #663701: sets module review Raymond Hettinger <python@rcn.com> parents: 27769 diff changeset	372 transform = getattr(element, "__as_immutable__", None)
26116 8965a2b804b5 Another attempt at making the set constructor both safe and fast. [SF Guido van Rossum <guido@python.org> parents: 26102 diff changeset	373 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	374 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	375 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	376
24891 aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	377
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	378 class ImmutableSet(BaseSet):
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	379 """Immutable set class."""
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	380
24893 44d1d0b623a9 Fix typo in __slots__ of ImmutableSet. Guido van Rossum <guido@python.org> parents: 24891 diff changeset	381 __slots__ = ['_hashcode']
24891 aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	382
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	383 # BaseSet + hashing
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	384
24930 e8f77307d9c6 Ouch. The test suite really needs work!!!!! There were several Guido van Rossum <guido@python.org> parents: 24929 diff changeset	385 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	386 """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	387 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	388 self._data = {}
e8f77307d9c6 Ouch. The test suite really needs work!!!!! There were several Guido van Rossum <guido@python.org> parents: 24929 diff changeset	389 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	390 self._update(iterable)
24891 aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	391
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	392 def __hash__(self):
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	393 if self._hashcode is None:
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	394 self._hashcode = self._compute_hash()
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	395 return self._hashcode
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	396
26197 cb71e7c620e2 Add getstate and setstate implementation to concrete set classes. Jeremy Hylton <jeremy@alum.mit.edu> parents: 26116 diff changeset	397 def __getstate__(self):
cb71e7c620e2 Add getstate and setstate implementation to concrete set classes. Jeremy Hylton <jeremy@alum.mit.edu> parents: 26116 diff changeset	398 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	399
cb71e7c620e2 Add getstate and setstate implementation to concrete set classes. Jeremy Hylton <jeremy@alum.mit.edu> parents: 26116 diff changeset	400 def __setstate__(self, state):
cb71e7c620e2 Add getstate and setstate implementation to concrete set classes. Jeremy Hylton <jeremy@alum.mit.edu> parents: 26116 diff changeset	401 self._data, self._hashcode = state
24891 aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	402
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	403 class Set(BaseSet):
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	404 """ Mutable set class."""
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	405
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	406 __slots__ = []
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	407
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	408 # BaseSet + operations requiring mutability; no hashing
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	409
24930 e8f77307d9c6 Ouch. The test suite really needs work!!!!! There were several Guido van Rossum <guido@python.org> parents: 24929 diff changeset	410 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	411 """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	412 self._data = {}
e8f77307d9c6 Ouch. The test suite really needs work!!!!! There were several Guido van Rossum <guido@python.org> parents: 24929 diff changeset	413 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	414 self._update(iterable)
e8f77307d9c6 Ouch. The test suite really needs work!!!!! There were several Guido van Rossum <guido@python.org> parents: 24929 diff changeset	415
26197 cb71e7c620e2 Add getstate and setstate implementation to concrete set classes. Jeremy Hylton <jeremy@alum.mit.edu> parents: 26116 diff changeset	416 def __getstate__(self):
cb71e7c620e2 Add getstate and setstate implementation to concrete set classes. Jeremy Hylton <jeremy@alum.mit.edu> parents: 26116 diff changeset	417 # 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	418 return self._data,
cb71e7c620e2 Add getstate and setstate implementation to concrete set classes. Jeremy Hylton <jeremy@alum.mit.edu> parents: 26116 diff changeset	419
cb71e7c620e2 Add getstate and setstate implementation to concrete set classes. Jeremy Hylton <jeremy@alum.mit.edu> parents: 26116 diff changeset	420 def __setstate__(self, data):
cb71e7c620e2 Add getstate and setstate implementation to concrete set classes. Jeremy Hylton <jeremy@alum.mit.edu> parents: 26116 diff changeset	421 self._data, = data
cb71e7c620e2 Add getstate and setstate implementation to concrete set classes. Jeremy Hylton <jeremy@alum.mit.edu> parents: 26116 diff changeset	422
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	423 # 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	424 # 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	425 # 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	426 # 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	427
25014 feeb0b02b8f2 At Tim Peter's suggestion, propagated GvR's binary operator changes to Raymond Hettinger <python@rcn.com> parents: 25012 diff changeset	428 def __ior__(self, other):
24891 aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	429 """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	430 self._binary_sanity_check(other)
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	431 self._data.update(other._data)
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	432 return self
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	433
25014 feeb0b02b8f2 At Tim Peter's suggestion, propagated GvR's binary operator changes to Raymond Hettinger <python@rcn.com> parents: 25012 diff changeset	434 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	435 """Update a set with the union of itself and another."""
30176 3db50d31340d Improvements to set.py: Raymond Hettinger <python@rcn.com> parents: 30171 diff changeset	436 self._update(other)
24891 aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	437
25014 feeb0b02b8f2 At Tim Peter's suggestion, propagated GvR's binary operator changes to Raymond Hettinger <python@rcn.com> parents: 25012 diff changeset	438 def __iand__(self, other):
24891 aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	439 """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	440 self._binary_sanity_check(other)
25038 0b9792cbe900 Gave intersection_update a speed boost. Tim Peters <tim.peters@gmail.com> parents: 25037 diff changeset	441 self._data = (self & other)._data
24891 aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	442 return self
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	443
25014 feeb0b02b8f2 At Tim Peter's suggestion, propagated GvR's binary operator changes to Raymond Hettinger <python@rcn.com> parents: 25012 diff changeset	444 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	445 """Update a set with the intersection of itself and another."""
30176 3db50d31340d Improvements to set.py: Raymond Hettinger <python@rcn.com> parents: 30171 diff changeset	446 if isinstance(other, BaseSet):
3db50d31340d Improvements to set.py: Raymond Hettinger <python@rcn.com> parents: 30171 diff changeset	447 self &= other
3db50d31340d Improvements to set.py: Raymond Hettinger <python@rcn.com> parents: 30171 diff changeset	448 else:
3db50d31340d Improvements to set.py: Raymond Hettinger <python@rcn.com> parents: 30171 diff changeset	449 self._data = (self.intersection(other))._data
24891 aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	450
25014 feeb0b02b8f2 At Tim Peter's suggestion, propagated GvR's binary operator changes to Raymond Hettinger <python@rcn.com> parents: 25012 diff changeset	451 def __ixor__(self, other):
24891 aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	452 """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	453 self._binary_sanity_check(other)
30176 3db50d31340d Improvements to set.py: Raymond Hettinger <python@rcn.com> parents: 30171 diff changeset	454 self.symmetric_difference_update(other)
3db50d31340d Improvements to set.py: Raymond Hettinger <python@rcn.com> parents: 30171 diff changeset	455 return self
3db50d31340d Improvements to set.py: Raymond Hettinger <python@rcn.com> parents: 30171 diff changeset	456
3db50d31340d Improvements to set.py: Raymond Hettinger <python@rcn.com> parents: 30171 diff changeset	457 def symmetric_difference_update(self, other):
3db50d31340d Improvements to set.py: Raymond Hettinger <python@rcn.com> parents: 30171 diff changeset	458 """Update a set with the symmetric difference of itself and another."""
24891 aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	459 data = self._data
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	460 value = True
30176 3db50d31340d Improvements to set.py: Raymond Hettinger <python@rcn.com> parents: 30171 diff changeset	461 if not isinstance(other, BaseSet):
3db50d31340d Improvements to set.py: Raymond Hettinger <python@rcn.com> parents: 30171 diff changeset	462 other = Set(other)
35337 def434e2a81a Teach the sets module to correctly compute s-=s and s^=s as the empty set. Raymond Hettinger <python@rcn.com> parents: 30971 diff changeset	463 if self is other:
def434e2a81a Teach the sets module to correctly compute s-=s and s^=s as the empty set. Raymond Hettinger <python@rcn.com> parents: 30971 diff changeset	464 self.clear()
24891 aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	465 for elt in other:
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	466 if elt in data:
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	467 del data[elt]
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	468 else:
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	469 data[elt] = value
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	470
25014 feeb0b02b8f2 At Tim Peter's suggestion, propagated GvR's binary operator changes to Raymond Hettinger <python@rcn.com> parents: 25012 diff changeset	471 def __isub__(self, other):
24891 aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	472 """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	473 self._binary_sanity_check(other)
30176 3db50d31340d Improvements to set.py: Raymond Hettinger <python@rcn.com> parents: 30171 diff changeset	474 self.difference_update(other)
24891 aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	475 return self
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	476
25014 feeb0b02b8f2 At Tim Peter's suggestion, propagated GvR's binary operator changes to Raymond Hettinger <python@rcn.com> parents: 25012 diff changeset	477 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	478 """Remove all elements of another set from this set."""
30176 3db50d31340d Improvements to set.py: Raymond Hettinger <python@rcn.com> parents: 30171 diff changeset	479 data = self._data
3db50d31340d Improvements to set.py: Raymond Hettinger <python@rcn.com> parents: 30171 diff changeset	480 if not isinstance(other, BaseSet):
3db50d31340d Improvements to set.py: Raymond Hettinger <python@rcn.com> parents: 30171 diff changeset	481 other = Set(other)
35337 def434e2a81a Teach the sets module to correctly compute s-=s and s^=s as the empty set. Raymond Hettinger <python@rcn.com> parents: 30971 diff changeset	482 if self is other:
def434e2a81a Teach the sets module to correctly compute s-=s and s^=s as the empty set. Raymond Hettinger <python@rcn.com> parents: 30971 diff changeset	483 self.clear()
63528 751c6dd71b5e Merged revisions 77310-77311 via svnmerge from Ezio Melotti <ezio.melotti@gmail.com> parents: 47961 diff changeset	484 for elt in ifilter(data.__contains__, other):
30176 3db50d31340d Improvements to set.py: Raymond Hettinger <python@rcn.com> parents: 30171 diff changeset	485 del data[elt]
24891 aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	486
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	487 # 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	488
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	489 def update(self, iterable):
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	490 """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	491 self._update(iterable)
24891 aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	492
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	493 def clear(self):
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	494 """Remove all elements from this set."""
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	495 self._data.clear()
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	496
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	497 # Single-element mutations: add, remove, discard
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 add(self, element):
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	500 """Add an element to a set.
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	501
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	502 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	503 """
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	504 try:
24927 c4a4b742ad6c Optimize try/except ordering in sets.py. Raymond Hettinger <python@rcn.com> parents: 24925 diff changeset	505 self._data[element] = True
c4a4b742ad6c Optimize try/except ordering in sets.py. Raymond Hettinger <python@rcn.com> parents: 24925 diff changeset	506 except TypeError:
27887 cedf9efa68f8 SF bug #663701: sets module review Raymond Hettinger <python@rcn.com> parents: 27769 diff changeset	507 transform = getattr(element, "__as_immutable__", None)
24927 c4a4b742ad6c Optimize try/except ordering in sets.py. Raymond Hettinger <python@rcn.com> parents: 24925 diff changeset	508 if transform is None:
c4a4b742ad6c Optimize try/except ordering in sets.py. Raymond Hettinger <python@rcn.com> parents: 24925 diff changeset	509 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	510 self._data[transform()] = True
24891 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 remove(self, element):
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	513 """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	514
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	515 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	516 """
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	517 try:
24927 c4a4b742ad6c Optimize try/except ordering in sets.py. Raymond Hettinger <python@rcn.com> parents: 24925 diff changeset	518 del self._data[element]
c4a4b742ad6c Optimize try/except ordering in sets.py. Raymond Hettinger <python@rcn.com> parents: 24925 diff changeset	519 except TypeError:
27887 cedf9efa68f8 SF bug #663701: sets module review Raymond Hettinger <python@rcn.com> parents: 27769 diff changeset	520 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	521 if transform is None:
c4a4b742ad6c Optimize try/except ordering in sets.py. Raymond Hettinger <python@rcn.com> parents: 24925 diff changeset	522 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	523 del self._data[transform()]
24891 aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	524
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	525 def discard(self, element):
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	526 """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	527
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	528 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	529 """
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	530 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	531 self.remove(element)
24891 aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	532 except KeyError:
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	533 pass
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	534
24924 a1143224ee0d Rename popitem() to pop(). (An idea from SF patch 597444.) Guido van Rossum <guido@python.org> parents: 24923 diff changeset	535 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	536 """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	537 return self._data.popitem()[0]
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	538
27887 cedf9efa68f8 SF bug #663701: sets module review Raymond Hettinger <python@rcn.com> parents: 27769 diff changeset	539 def __as_immutable__(self):
24891 aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	540 # 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	541 return ImmutableSet(self)
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	542
27887 cedf9efa68f8 SF bug #663701: sets module review Raymond Hettinger <python@rcn.com> parents: 27769 diff changeset	543 def __as_temporarily_immutable__(self):
24891 aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	544 # 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	545 return _TemporarilyImmutableSet(self)
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	546
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	547
25010 35749db10809 1. Removed module self test in favor of unittests -- Timbot's suggestion. Raymond Hettinger <python@rcn.com> parents: 25007 diff changeset	548 class _TemporarilyImmutableSet(BaseSet):
24891 aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	549 # 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	550 # 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	551
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	552 def __init__(self, set):
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	553 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	554 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	555
aebf8c52a842 Set classes and their unit tests, from sandbox. Guido van Rossum <guido@python.org> parents: diff changeset	556 def __hash__(self):
25012 f2d75749e61c Since instances of _TemporarilyImmutableSet are always thrown away Raymond Hettinger <python@rcn.com> parents: 25010 diff changeset	557 return self._set._compute_hash()

Mercurial > cpython-lru_cache-weakref

annotate Lib/sets.py @ 80661:94de77bd0b4b 2.7