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

annotate Lib/sets.py @ 58925:eecf1bef052d 2.6

Merged revisions 78207 via svnmerge from svn+ssh://pythondev@svn.python.org/python/trunk ........ r78207 | ezio.melotti | 2010-02-17 01:26:09 +0200 (Wed, 17 Feb 2010) | 1 line #7930: fix stripid ........

author	Ezio Melotti <ezio.melotti@gmail.com>
date	Tue, 16 Feb 2010 23:29:44 +0000
parents	f9b80a820a25
children	751c6dd71b5e

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

Mercurial > cpython-lru_cache-weakref

annotate Lib/sets.py @ 58925:eecf1bef052d 2.6