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

annotate Lib/sets.py @ 39042:c02fa187e0f4 legacy-trunk

Part of SF patch #1484695. This removes dead code. The chksum was already verified in .frombuf() on the lines above. If there was a problem an exception is raised, so there was no way this condition could have been true.

author	Neal Norwitz <nnorwitz@gmail.com>
date	Mon, 10 Jul 2006 00:23:17 +0000
parents	def434e2a81a
children	63237fcefd99 b303fb383fa4

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

Mercurial > cpython-lru_cache-weakref

annotate Lib/sets.py @ 39042:c02fa187e0f4 legacy-trunk