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

annotate Lib/sets.py @ 28646:193b8aec00ce legacy-trunk

Changes from Jonathan Riehl to allow his pgen extension (PEP 269) to work. This includes some more code that used to be part of pgen in the main parser; I'm okay with that. I'll see if the Windows build needs work next.

author	Guido van Rossum <guido@python.org>
date	Thu, 17 Apr 2003 14:55:42 +0000
parents	5f923165319d
children	466b579e0088

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

Mercurial > cpython-lru_cache-weakref

annotate Lib/sets.py @ 28646:193b8aec00ce legacy-trunk