Guido van Rossum | d6cf3af | 2002-08-19 16:19:15 +0000 | [diff] [blame] | 1 | """Classes to represent arbitrary sets (including sets of sets). |
| 2 | |
| 3 | This module implements sets using dictionaries whose values are |
| 4 | ignored. The usual operations (union, intersection, deletion, etc.) |
| 5 | are provided as both methods and operators. |
| 6 | |
Guido van Rossum | 290f187 | 2002-08-20 20:05:23 +0000 | [diff] [blame] | 7 | Important: sets are not sequences! While they support 'x in s', |
| 8 | 'len(s)', and 'for x in s', none of those operations are unique for |
| 9 | sequences; for example, mappings support all three as well. The |
| 10 | characteristic operation for sequences is subscripting with small |
| 11 | integers: s[i], for i in range(len(s)). Sets don't support |
| 12 | subscripting at all. Also, sequences allow multiple occurrences and |
| 13 | their elements have a definite order; sets on the other hand don't |
| 14 | record multiple occurrences and don't remember the order of element |
| 15 | insertion (which is why they don't support s[i]). |
| 16 | |
Guido van Rossum | d6cf3af | 2002-08-19 16:19:15 +0000 | [diff] [blame] | 17 | The following classes are provided: |
| 18 | |
| 19 | BaseSet -- All the operations common to both mutable and immutable |
| 20 | sets. This is an abstract class, not meant to be directly |
| 21 | instantiated. |
| 22 | |
| 23 | Set -- Mutable sets, subclass of BaseSet; not hashable. |
| 24 | |
| 25 | ImmutableSet -- Immutable sets, subclass of BaseSet; hashable. |
| 26 | An iterable argument is mandatory to create an ImmutableSet. |
| 27 | |
Raymond Hettinger | f6fe4ed | 2003-06-26 18:49:28 +0000 | [diff] [blame] | 28 | _TemporarilyImmutableSet -- A wrapper around a Set, hashable, |
| 29 | giving the same hash value as the immutable set equivalent |
| 30 | would have. Do not use this class directly. |
Guido van Rossum | d6cf3af | 2002-08-19 16:19:15 +0000 | [diff] [blame] | 31 | |
| 32 | Only hashable objects can be added to a Set. In particular, you cannot |
| 33 | really add a Set as an element to another Set; if you try, what is |
Raymond Hettinger | ede3a0d | 2002-08-20 23:34:01 +0000 | [diff] [blame] | 34 | actually added is an ImmutableSet built from it (it compares equal to |
Guido van Rossum | d6cf3af | 2002-08-19 16:19:15 +0000 | [diff] [blame] | 35 | the one you tried adding). |
| 36 | |
| 37 | When you ask if `x in y' where x is a Set and y is a Set or |
| 38 | ImmutableSet, x is wrapped into a _TemporarilyImmutableSet z, and |
| 39 | what's tested is actually `z in y'. |
| 40 | |
| 41 | """ |
| 42 | |
| 43 | # Code history: |
| 44 | # |
| 45 | # - Greg V. Wilson wrote the first version, using a different approach |
| 46 | # to the mutable/immutable problem, and inheriting from dict. |
| 47 | # |
| 48 | # - Alex Martelli modified Greg's version to implement the current |
| 49 | # Set/ImmutableSet approach, and make the data an attribute. |
| 50 | # |
| 51 | # - Guido van Rossum rewrote much of the code, made some API changes, |
| 52 | # and cleaned up the docstrings. |
Guido van Rossum | 2658822 | 2002-08-21 02:44:04 +0000 | [diff] [blame] | 53 | # |
Guido van Rossum | 9f87293 | 2002-08-21 03:20:44 +0000 | [diff] [blame] | 54 | # - Raymond Hettinger added a number of speedups and other |
Guido van Rossum | dc61cdf | 2002-08-22 17:23:33 +0000 | [diff] [blame] | 55 | # improvements. |
Guido van Rossum | d6cf3af | 2002-08-19 16:19:15 +0000 | [diff] [blame] | 56 | |
Raymond Hettinger | ee562fc | 2003-08-15 21:17:04 +0000 | [diff] [blame] | 57 | from __future__ import generators |
| 58 | try: |
| 59 | from itertools import ifilter, ifilterfalse |
| 60 | except ImportError: |
| 61 | # Code to make the module run under Py2.2 |
| 62 | def ifilter(predicate, iterable): |
| 63 | if predicate is None: |
| 64 | def predicate(x): |
| 65 | return x |
| 66 | for x in iterable: |
| 67 | if predicate(x): |
| 68 | yield x |
| 69 | def ifilterfalse(predicate, iterable): |
| 70 | if predicate is None: |
| 71 | def predicate(x): |
| 72 | return x |
| 73 | for x in iterable: |
| 74 | if not predicate(x): |
| 75 | yield x |
Raymond Hettinger | 859db26 | 2003-11-12 15:21:20 +0000 | [diff] [blame] | 76 | try: |
| 77 | True, False |
| 78 | except NameError: |
| 79 | True, False = (0==0, 0!=0) |
Guido van Rossum | d6cf3af | 2002-08-19 16:19:15 +0000 | [diff] [blame] | 80 | |
| 81 | __all__ = ['BaseSet', 'Set', 'ImmutableSet'] |
Guido van Rossum | d6cf3af | 2002-08-19 16:19:15 +0000 | [diff] [blame] | 82 | |
Brett Cannon | 093b670 | 2007-01-13 00:29:49 +0000 | [diff] [blame] | 83 | import warnings |
| 84 | warnings.warn("the sets module is deprecated", DeprecationWarning, |
| 85 | stacklevel=2) |
| 86 | |
Guido van Rossum | d6cf3af | 2002-08-19 16:19:15 +0000 | [diff] [blame] | 87 | class BaseSet(object): |
| 88 | """Common base class for mutable and immutable sets.""" |
| 89 | |
| 90 | __slots__ = ['_data'] |
| 91 | |
| 92 | # Constructor |
| 93 | |
Guido van Rossum | 5033b36 | 2002-08-20 21:38:37 +0000 | [diff] [blame] | 94 | def __init__(self): |
| 95 | """This is an abstract class.""" |
| 96 | # Don't call this from a concrete subclass! |
| 97 | if self.__class__ is BaseSet: |
Guido van Rossum | 9f87293 | 2002-08-21 03:20:44 +0000 | [diff] [blame] | 98 | raise TypeError, ("BaseSet is an abstract class. " |
| 99 | "Use Set or ImmutableSet.") |
Guido van Rossum | d6cf3af | 2002-08-19 16:19:15 +0000 | [diff] [blame] | 100 | |
| 101 | # Standard protocols: __len__, __repr__, __str__, __iter__ |
| 102 | |
| 103 | def __len__(self): |
| 104 | """Return the number of elements of a set.""" |
| 105 | return len(self._data) |
| 106 | |
| 107 | def __repr__(self): |
| 108 | """Return string representation of a set. |
| 109 | |
| 110 | This looks like 'Set([<list of elements>])'. |
| 111 | """ |
| 112 | return self._repr() |
| 113 | |
| 114 | # __str__ is the same as __repr__ |
| 115 | __str__ = __repr__ |
| 116 | |
| 117 | def _repr(self, sorted=False): |
| 118 | elements = self._data.keys() |
| 119 | if sorted: |
| 120 | elements.sort() |
| 121 | return '%s(%r)' % (self.__class__.__name__, elements) |
| 122 | |
| 123 | def __iter__(self): |
| 124 | """Return an iterator over the elements or a set. |
| 125 | |
| 126 | This is the keys iterator for the underlying dict. |
| 127 | """ |
| 128 | return self._data.iterkeys() |
| 129 | |
Tim Peters | 44f14b0 | 2003-03-02 00:19:49 +0000 | [diff] [blame] | 130 | # Three-way comparison is not supported. However, because __eq__ is |
| 131 | # tried before __cmp__, if Set x == Set y, x.__eq__(y) returns True and |
| 132 | # then cmp(x, y) returns 0 (Python doesn't actually call __cmp__ in this |
| 133 | # case). |
Guido van Rossum | 50e9223 | 2003-01-14 16:45:04 +0000 | [diff] [blame] | 134 | |
| 135 | def __cmp__(self, other): |
| 136 | raise TypeError, "can't compare sets using cmp()" |
| 137 | |
Tim Peters | 44f14b0 | 2003-03-02 00:19:49 +0000 | [diff] [blame] | 138 | # Equality comparisons using the underlying dicts. Mixed-type comparisons |
| 139 | # are allowed here, where Set == z for non-Set z always returns False, |
| 140 | # and Set != z always True. This allows expressions like "x in y" to |
| 141 | # give the expected result when y is a sequence of mixed types, not |
| 142 | # raising a pointless TypeError just because y contains a Set, or x is |
| 143 | # a Set and y contain's a non-set ("in" invokes only __eq__). |
| 144 | # Subtle: it would be nicer if __eq__ and __ne__ could return |
| 145 | # NotImplemented instead of True or False. Then the other comparand |
| 146 | # would get a chance to determine the result, and if the other comparand |
| 147 | # also returned NotImplemented then it would fall back to object address |
| 148 | # comparison (which would always return False for __eq__ and always |
| 149 | # True for __ne__). However, that doesn't work, because this type |
| 150 | # *also* implements __cmp__: if, e.g., __eq__ returns NotImplemented, |
| 151 | # Python tries __cmp__ next, and the __cmp__ here then raises TypeError. |
Guido van Rossum | d6cf3af | 2002-08-19 16:19:15 +0000 | [diff] [blame] | 152 | |
| 153 | def __eq__(self, other): |
Tim Peters | 44f14b0 | 2003-03-02 00:19:49 +0000 | [diff] [blame] | 154 | if isinstance(other, BaseSet): |
| 155 | return self._data == other._data |
| 156 | else: |
| 157 | return False |
Guido van Rossum | d6cf3af | 2002-08-19 16:19:15 +0000 | [diff] [blame] | 158 | |
| 159 | def __ne__(self, other): |
Tim Peters | 44f14b0 | 2003-03-02 00:19:49 +0000 | [diff] [blame] | 160 | if isinstance(other, BaseSet): |
| 161 | return self._data != other._data |
| 162 | else: |
| 163 | return True |
Guido van Rossum | d6cf3af | 2002-08-19 16:19:15 +0000 | [diff] [blame] | 164 | |
Guido van Rossum | d6cf3af | 2002-08-19 16:19:15 +0000 | [diff] [blame] | 165 | # Copying operations |
| 166 | |
| 167 | def copy(self): |
| 168 | """Return a shallow copy of a set.""" |
Raymond Hettinger | fa1480f | 2002-08-24 02:35:48 +0000 | [diff] [blame] | 169 | result = self.__class__() |
Raymond Hettinger | d9c9151 | 2002-08-21 13:20:51 +0000 | [diff] [blame] | 170 | result._data.update(self._data) |
| 171 | return result |
Guido van Rossum | d6cf3af | 2002-08-19 16:19:15 +0000 | [diff] [blame] | 172 | |
| 173 | __copy__ = copy # For the copy module |
| 174 | |
| 175 | def __deepcopy__(self, memo): |
| 176 | """Return a deep copy of a set; used by copy module.""" |
| 177 | # This pre-creates the result and inserts it in the memo |
| 178 | # early, in case the deep copy recurses into another reference |
| 179 | # to this same set. A set can't be an element of itself, but |
| 180 | # it can certainly contain an object that has a reference to |
| 181 | # itself. |
| 182 | from copy import deepcopy |
Raymond Hettinger | fa1480f | 2002-08-24 02:35:48 +0000 | [diff] [blame] | 183 | result = self.__class__() |
Guido van Rossum | d6cf3af | 2002-08-19 16:19:15 +0000 | [diff] [blame] | 184 | memo[id(self)] = result |
| 185 | data = result._data |
| 186 | value = True |
| 187 | for elt in self: |
| 188 | data[deepcopy(elt, memo)] = value |
| 189 | return result |
| 190 | |
Guido van Rossum | dc61cdf | 2002-08-22 17:23:33 +0000 | [diff] [blame] | 191 | # Standard set operations: union, intersection, both differences. |
| 192 | # Each has an operator version (e.g. __or__, invoked with |) and a |
| 193 | # method version (e.g. union). |
Tim Peters | 4924db1 | 2002-08-25 17:10:17 +0000 | [diff] [blame] | 194 | # Subtle: Each pair requires distinct code so that the outcome is |
| 195 | # correct when the type of other isn't suitable. For example, if |
| 196 | # we did "union = __or__" instead, then Set().union(3) would return |
| 197 | # NotImplemented instead of raising TypeError (albeit that *why* it |
| 198 | # raises TypeError as-is is also a bit subtle). |
Guido van Rossum | dc61cdf | 2002-08-22 17:23:33 +0000 | [diff] [blame] | 199 | |
| 200 | def __or__(self, other): |
| 201 | """Return the union of two sets as a new set. |
| 202 | |
| 203 | (I.e. all elements that are in either set.) |
| 204 | """ |
| 205 | if not isinstance(other, BaseSet): |
| 206 | return NotImplemented |
Raymond Hettinger | 6a18012 | 2003-08-17 08:34:09 +0000 | [diff] [blame] | 207 | return self.union(other) |
Guido van Rossum | d6cf3af | 2002-08-19 16:19:15 +0000 | [diff] [blame] | 208 | |
| 209 | def union(self, other): |
| 210 | """Return the union of two sets as a new set. |
| 211 | |
| 212 | (I.e. all elements that are in either set.) |
| 213 | """ |
Raymond Hettinger | 6a18012 | 2003-08-17 08:34:09 +0000 | [diff] [blame] | 214 | result = self.__class__(self) |
| 215 | result._update(other) |
| 216 | return result |
Guido van Rossum | d6cf3af | 2002-08-19 16:19:15 +0000 | [diff] [blame] | 217 | |
Guido van Rossum | dc61cdf | 2002-08-22 17:23:33 +0000 | [diff] [blame] | 218 | def __and__(self, other): |
Guido van Rossum | d6cf3af | 2002-08-19 16:19:15 +0000 | [diff] [blame] | 219 | """Return the intersection of two sets as a new set. |
| 220 | |
| 221 | (I.e. all elements that are in both sets.) |
| 222 | """ |
Guido van Rossum | dc61cdf | 2002-08-22 17:23:33 +0000 | [diff] [blame] | 223 | if not isinstance(other, BaseSet): |
| 224 | return NotImplemented |
Raymond Hettinger | 6a18012 | 2003-08-17 08:34:09 +0000 | [diff] [blame] | 225 | return self.intersection(other) |
Guido van Rossum | d6cf3af | 2002-08-19 16:19:15 +0000 | [diff] [blame] | 226 | |
Guido van Rossum | dc61cdf | 2002-08-22 17:23:33 +0000 | [diff] [blame] | 227 | def intersection(self, other): |
| 228 | """Return the intersection of two sets as a new set. |
Guido van Rossum | d6cf3af | 2002-08-19 16:19:15 +0000 | [diff] [blame] | 229 | |
Guido van Rossum | dc61cdf | 2002-08-22 17:23:33 +0000 | [diff] [blame] | 230 | (I.e. all elements that are in both sets.) |
| 231 | """ |
Raymond Hettinger | 6a18012 | 2003-08-17 08:34:09 +0000 | [diff] [blame] | 232 | if not isinstance(other, BaseSet): |
| 233 | other = Set(other) |
| 234 | if len(self) <= len(other): |
| 235 | little, big = self, other |
| 236 | else: |
| 237 | little, big = other, self |
| 238 | common = ifilter(big._data.has_key, little) |
| 239 | return self.__class__(common) |
Guido van Rossum | dc61cdf | 2002-08-22 17:23:33 +0000 | [diff] [blame] | 240 | |
| 241 | def __xor__(self, other): |
Guido van Rossum | d6cf3af | 2002-08-19 16:19:15 +0000 | [diff] [blame] | 242 | """Return the symmetric difference of two sets as a new set. |
| 243 | |
| 244 | (I.e. all elements that are in exactly one of the sets.) |
| 245 | """ |
Guido van Rossum | dc61cdf | 2002-08-22 17:23:33 +0000 | [diff] [blame] | 246 | if not isinstance(other, BaseSet): |
| 247 | return NotImplemented |
Raymond Hettinger | 6a18012 | 2003-08-17 08:34:09 +0000 | [diff] [blame] | 248 | return self.symmetric_difference(other) |
Guido van Rossum | d6cf3af | 2002-08-19 16:19:15 +0000 | [diff] [blame] | 249 | |
Guido van Rossum | dc61cdf | 2002-08-22 17:23:33 +0000 | [diff] [blame] | 250 | def symmetric_difference(self, other): |
| 251 | """Return the symmetric difference of two sets as a new set. |
Guido van Rossum | d6cf3af | 2002-08-19 16:19:15 +0000 | [diff] [blame] | 252 | |
Guido van Rossum | dc61cdf | 2002-08-22 17:23:33 +0000 | [diff] [blame] | 253 | (I.e. all elements that are in exactly one of the sets.) |
| 254 | """ |
Raymond Hettinger | 6a18012 | 2003-08-17 08:34:09 +0000 | [diff] [blame] | 255 | result = self.__class__() |
| 256 | data = result._data |
| 257 | value = True |
| 258 | selfdata = self._data |
| 259 | try: |
| 260 | otherdata = other._data |
| 261 | except AttributeError: |
| 262 | otherdata = Set(other)._data |
| 263 | for elt in ifilterfalse(otherdata.has_key, selfdata): |
| 264 | data[elt] = value |
| 265 | for elt in ifilterfalse(selfdata.has_key, otherdata): |
| 266 | data[elt] = value |
| 267 | return result |
Guido van Rossum | dc61cdf | 2002-08-22 17:23:33 +0000 | [diff] [blame] | 268 | |
| 269 | def __sub__(self, other): |
Guido van Rossum | d6cf3af | 2002-08-19 16:19:15 +0000 | [diff] [blame] | 270 | """Return the difference of two sets as a new Set. |
| 271 | |
| 272 | (I.e. all elements that are in this set and not in the other.) |
| 273 | """ |
Guido van Rossum | dc61cdf | 2002-08-22 17:23:33 +0000 | [diff] [blame] | 274 | if not isinstance(other, BaseSet): |
| 275 | return NotImplemented |
Raymond Hettinger | 6a18012 | 2003-08-17 08:34:09 +0000 | [diff] [blame] | 276 | return self.difference(other) |
Guido van Rossum | d6cf3af | 2002-08-19 16:19:15 +0000 | [diff] [blame] | 277 | |
Guido van Rossum | dc61cdf | 2002-08-22 17:23:33 +0000 | [diff] [blame] | 278 | def difference(self, other): |
| 279 | """Return the difference of two sets as a new Set. |
| 280 | |
| 281 | (I.e. all elements that are in this set and not in the other.) |
| 282 | """ |
Raymond Hettinger | 6a18012 | 2003-08-17 08:34:09 +0000 | [diff] [blame] | 283 | result = self.__class__() |
| 284 | data = result._data |
| 285 | try: |
| 286 | otherdata = other._data |
| 287 | except AttributeError: |
| 288 | otherdata = Set(other)._data |
| 289 | value = True |
| 290 | for elt in ifilterfalse(otherdata.has_key, self): |
| 291 | data[elt] = value |
| 292 | return result |
Guido van Rossum | d6cf3af | 2002-08-19 16:19:15 +0000 | [diff] [blame] | 293 | |
| 294 | # Membership test |
| 295 | |
| 296 | def __contains__(self, element): |
| 297 | """Report whether an element is a member of a set. |
| 298 | |
| 299 | (Called in response to the expression `element in self'.) |
| 300 | """ |
| 301 | try: |
Raymond Hettinger | de6d697 | 2002-08-21 01:35:29 +0000 | [diff] [blame] | 302 | return element in self._data |
| 303 | except TypeError: |
Raymond Hettinger | 2835e37 | 2003-02-14 03:42:11 +0000 | [diff] [blame] | 304 | transform = getattr(element, "__as_temporarily_immutable__", None) |
Raymond Hettinger | de6d697 | 2002-08-21 01:35:29 +0000 | [diff] [blame] | 305 | if transform is None: |
| 306 | raise # re-raise the TypeError exception we caught |
| 307 | return transform() in self._data |
Guido van Rossum | d6cf3af | 2002-08-19 16:19:15 +0000 | [diff] [blame] | 308 | |
| 309 | # Subset and superset test |
| 310 | |
| 311 | def issubset(self, other): |
| 312 | """Report whether another set contains this set.""" |
| 313 | self._binary_sanity_check(other) |
Raymond Hettinger | 43db0d6 | 2002-08-21 02:22:08 +0000 | [diff] [blame] | 314 | if len(self) > len(other): # Fast check for obvious cases |
| 315 | return False |
Raymond Hettinger | 60eca93 | 2003-02-09 06:40:58 +0000 | [diff] [blame] | 316 | for elt in ifilterfalse(other._data.has_key, self): |
Raymond Hettinger | a3a5318 | 2003-02-02 14:27:19 +0000 | [diff] [blame] | 317 | return False |
Guido van Rossum | d6cf3af | 2002-08-19 16:19:15 +0000 | [diff] [blame] | 318 | return True |
| 319 | |
| 320 | def issuperset(self, other): |
| 321 | """Report whether this set contains another set.""" |
| 322 | self._binary_sanity_check(other) |
Raymond Hettinger | 43db0d6 | 2002-08-21 02:22:08 +0000 | [diff] [blame] | 323 | if len(self) < len(other): # Fast check for obvious cases |
| 324 | return False |
Raymond Hettinger | 60eca93 | 2003-02-09 06:40:58 +0000 | [diff] [blame] | 325 | for elt in ifilterfalse(self._data.has_key, other): |
Tim Peters | 322d553 | 2003-02-04 00:38:20 +0000 | [diff] [blame] | 326 | return False |
Guido van Rossum | d6cf3af | 2002-08-19 16:19:15 +0000 | [diff] [blame] | 327 | return True |
| 328 | |
Tim Peters | ea76c98 | 2002-08-25 18:43:10 +0000 | [diff] [blame] | 329 | # Inequality comparisons using the is-subset relation. |
| 330 | __le__ = issubset |
| 331 | __ge__ = issuperset |
| 332 | |
| 333 | def __lt__(self, other): |
| 334 | self._binary_sanity_check(other) |
| 335 | return len(self) < len(other) and self.issubset(other) |
| 336 | |
| 337 | def __gt__(self, other): |
| 338 | self._binary_sanity_check(other) |
| 339 | return len(self) > len(other) and self.issuperset(other) |
| 340 | |
Guido van Rossum | d6cf3af | 2002-08-19 16:19:15 +0000 | [diff] [blame] | 341 | # Assorted helpers |
| 342 | |
| 343 | def _binary_sanity_check(self, other): |
| 344 | # Check that the other argument to a binary operation is also |
| 345 | # a set, raising a TypeError otherwise. |
| 346 | if not isinstance(other, BaseSet): |
| 347 | raise TypeError, "Binary operation only permitted between sets" |
| 348 | |
| 349 | def _compute_hash(self): |
| 350 | # Calculate hash code for a set by xor'ing the hash codes of |
Tim Peters | d06d030 | 2002-08-23 20:06:42 +0000 | [diff] [blame] | 351 | # the elements. This ensures that the hash code does not depend |
| 352 | # on the order in which elements are added to the set. This is |
| 353 | # not called __hash__ because a BaseSet should not be hashable; |
| 354 | # only an ImmutableSet is hashable. |
Guido van Rossum | d6cf3af | 2002-08-19 16:19:15 +0000 | [diff] [blame] | 355 | result = 0 |
| 356 | for elt in self: |
| 357 | result ^= hash(elt) |
| 358 | return result |
| 359 | |
Guido van Rossum | 9f87293 | 2002-08-21 03:20:44 +0000 | [diff] [blame] | 360 | def _update(self, iterable): |
| 361 | # The main loop for update() and the subclass __init__() methods. |
Guido van Rossum | 9f87293 | 2002-08-21 03:20:44 +0000 | [diff] [blame] | 362 | data = self._data |
Raymond Hettinger | 1a8d193 | 2002-08-29 15:13:50 +0000 | [diff] [blame] | 363 | |
| 364 | # Use the fast update() method when a dictionary is available. |
| 365 | if isinstance(iterable, BaseSet): |
| 366 | data.update(iterable._data) |
| 367 | return |
Raymond Hettinger | 1a8d193 | 2002-08-29 15:13:50 +0000 | [diff] [blame] | 368 | |
Tim Peters | 0ec1ddc | 2002-11-08 05:26:52 +0000 | [diff] [blame] | 369 | value = True |
Guido van Rossum | 7cd83ca | 2002-11-08 17:03:36 +0000 | [diff] [blame] | 370 | |
| 371 | if type(iterable) in (list, tuple, xrange): |
| 372 | # Optimized: we know that __iter__() and next() can't |
| 373 | # raise TypeError, so we can move 'try:' out of the loop. |
| 374 | it = iter(iterable) |
| 375 | while True: |
| 376 | try: |
| 377 | for element in it: |
| 378 | data[element] = value |
| 379 | return |
| 380 | except TypeError: |
Raymond Hettinger | 2835e37 | 2003-02-14 03:42:11 +0000 | [diff] [blame] | 381 | transform = getattr(element, "__as_immutable__", None) |
Guido van Rossum | 7cd83ca | 2002-11-08 17:03:36 +0000 | [diff] [blame] | 382 | if transform is None: |
| 383 | raise # re-raise the TypeError exception we caught |
| 384 | data[transform()] = value |
| 385 | else: |
| 386 | # Safe: only catch TypeError where intended |
| 387 | for element in iterable: |
| 388 | try: |
Raymond Hettinger | 80d21af | 2002-08-21 04:12:03 +0000 | [diff] [blame] | 389 | data[element] = value |
Guido van Rossum | 7cd83ca | 2002-11-08 17:03:36 +0000 | [diff] [blame] | 390 | except TypeError: |
Raymond Hettinger | 2835e37 | 2003-02-14 03:42:11 +0000 | [diff] [blame] | 391 | transform = getattr(element, "__as_immutable__", None) |
Guido van Rossum | 7cd83ca | 2002-11-08 17:03:36 +0000 | [diff] [blame] | 392 | if transform is None: |
| 393 | raise # re-raise the TypeError exception we caught |
| 394 | data[transform()] = value |
Guido van Rossum | 9f87293 | 2002-08-21 03:20:44 +0000 | [diff] [blame] | 395 | |
Guido van Rossum | d6cf3af | 2002-08-19 16:19:15 +0000 | [diff] [blame] | 396 | |
| 397 | class ImmutableSet(BaseSet): |
| 398 | """Immutable set class.""" |
| 399 | |
Guido van Rossum | 0b650d7 | 2002-08-19 16:29:58 +0000 | [diff] [blame] | 400 | __slots__ = ['_hashcode'] |
Guido van Rossum | d6cf3af | 2002-08-19 16:19:15 +0000 | [diff] [blame] | 401 | |
| 402 | # BaseSet + hashing |
| 403 | |
Guido van Rossum | 9f87293 | 2002-08-21 03:20:44 +0000 | [diff] [blame] | 404 | def __init__(self, iterable=None): |
| 405 | """Construct an immutable set from an optional iterable.""" |
Guido van Rossum | d6cf3af | 2002-08-19 16:19:15 +0000 | [diff] [blame] | 406 | self._hashcode = None |
Guido van Rossum | 9f87293 | 2002-08-21 03:20:44 +0000 | [diff] [blame] | 407 | self._data = {} |
| 408 | if iterable is not None: |
| 409 | self._update(iterable) |
Guido van Rossum | d6cf3af | 2002-08-19 16:19:15 +0000 | [diff] [blame] | 410 | |
| 411 | def __hash__(self): |
| 412 | if self._hashcode is None: |
| 413 | self._hashcode = self._compute_hash() |
| 414 | return self._hashcode |
| 415 | |
Jeremy Hylton | cd58b8f | 2002-11-13 19:34:26 +0000 | [diff] [blame] | 416 | def __getstate__(self): |
| 417 | return self._data, self._hashcode |
| 418 | |
| 419 | def __setstate__(self, state): |
| 420 | self._data, self._hashcode = state |
Guido van Rossum | d6cf3af | 2002-08-19 16:19:15 +0000 | [diff] [blame] | 421 | |
| 422 | class Set(BaseSet): |
| 423 | """ Mutable set class.""" |
| 424 | |
| 425 | __slots__ = [] |
| 426 | |
| 427 | # BaseSet + operations requiring mutability; no hashing |
| 428 | |
Guido van Rossum | 9f87293 | 2002-08-21 03:20:44 +0000 | [diff] [blame] | 429 | def __init__(self, iterable=None): |
| 430 | """Construct a set from an optional iterable.""" |
| 431 | self._data = {} |
| 432 | if iterable is not None: |
| 433 | self._update(iterable) |
| 434 | |
Jeremy Hylton | cd58b8f | 2002-11-13 19:34:26 +0000 | [diff] [blame] | 435 | def __getstate__(self): |
| 436 | # getstate's results are ignored if it is not |
| 437 | return self._data, |
| 438 | |
| 439 | def __setstate__(self, data): |
| 440 | self._data, = data |
| 441 | |
Nick Coghlan | 53663a6 | 2008-07-15 14:27:37 +0000 | [diff] [blame] | 442 | # We inherit object.__hash__, so we must deny this explicitly |
| 443 | __hash__ = None |
Guido van Rossum | 5033b36 | 2002-08-20 21:38:37 +0000 | [diff] [blame] | 444 | |
Tim Peters | 4a2f91e | 2002-08-25 18:59:04 +0000 | [diff] [blame] | 445 | # In-place union, intersection, differences. |
| 446 | # Subtle: The xyz_update() functions deliberately return None, |
| 447 | # as do all mutating operations on built-in container types. |
| 448 | # The __xyz__ spellings have to return self, though. |
Guido van Rossum | d6cf3af | 2002-08-19 16:19:15 +0000 | [diff] [blame] | 449 | |
Raymond Hettinger | 1b9f5d4 | 2002-08-24 06:19:02 +0000 | [diff] [blame] | 450 | def __ior__(self, other): |
Guido van Rossum | d6cf3af | 2002-08-19 16:19:15 +0000 | [diff] [blame] | 451 | """Update a set with the union of itself and another.""" |
| 452 | self._binary_sanity_check(other) |
| 453 | self._data.update(other._data) |
| 454 | return self |
| 455 | |
Raymond Hettinger | 1b9f5d4 | 2002-08-24 06:19:02 +0000 | [diff] [blame] | 456 | def union_update(self, other): |
| 457 | """Update a set with the union of itself and another.""" |
Raymond Hettinger | 6a18012 | 2003-08-17 08:34:09 +0000 | [diff] [blame] | 458 | self._update(other) |
Guido van Rossum | d6cf3af | 2002-08-19 16:19:15 +0000 | [diff] [blame] | 459 | |
Raymond Hettinger | 1b9f5d4 | 2002-08-24 06:19:02 +0000 | [diff] [blame] | 460 | def __iand__(self, other): |
Guido van Rossum | d6cf3af | 2002-08-19 16:19:15 +0000 | [diff] [blame] | 461 | """Update a set with the intersection of itself and another.""" |
| 462 | self._binary_sanity_check(other) |
Tim Peters | 454602f | 2002-08-26 00:44:07 +0000 | [diff] [blame] | 463 | self._data = (self & other)._data |
Guido van Rossum | d6cf3af | 2002-08-19 16:19:15 +0000 | [diff] [blame] | 464 | return self |
| 465 | |
Raymond Hettinger | 1b9f5d4 | 2002-08-24 06:19:02 +0000 | [diff] [blame] | 466 | def intersection_update(self, other): |
| 467 | """Update a set with the intersection of itself and another.""" |
Raymond Hettinger | 6a18012 | 2003-08-17 08:34:09 +0000 | [diff] [blame] | 468 | if isinstance(other, BaseSet): |
| 469 | self &= other |
| 470 | else: |
| 471 | self._data = (self.intersection(other))._data |
Guido van Rossum | d6cf3af | 2002-08-19 16:19:15 +0000 | [diff] [blame] | 472 | |
Raymond Hettinger | 1b9f5d4 | 2002-08-24 06:19:02 +0000 | [diff] [blame] | 473 | def __ixor__(self, other): |
Guido van Rossum | d6cf3af | 2002-08-19 16:19:15 +0000 | [diff] [blame] | 474 | """Update a set with the symmetric difference of itself and another.""" |
| 475 | self._binary_sanity_check(other) |
Raymond Hettinger | 6a18012 | 2003-08-17 08:34:09 +0000 | [diff] [blame] | 476 | self.symmetric_difference_update(other) |
| 477 | return self |
| 478 | |
| 479 | def symmetric_difference_update(self, other): |
| 480 | """Update a set with the symmetric difference of itself and another.""" |
Guido van Rossum | d6cf3af | 2002-08-19 16:19:15 +0000 | [diff] [blame] | 481 | data = self._data |
| 482 | value = True |
Raymond Hettinger | 6a18012 | 2003-08-17 08:34:09 +0000 | [diff] [blame] | 483 | if not isinstance(other, BaseSet): |
| 484 | other = Set(other) |
Raymond Hettinger | 038ca2a | 2005-08-13 02:29:58 +0000 | [diff] [blame] | 485 | if self is other: |
| 486 | self.clear() |
Guido van Rossum | d6cf3af | 2002-08-19 16:19:15 +0000 | [diff] [blame] | 487 | for elt in other: |
| 488 | if elt in data: |
| 489 | del data[elt] |
| 490 | else: |
| 491 | data[elt] = value |
Guido van Rossum | d6cf3af | 2002-08-19 16:19:15 +0000 | [diff] [blame] | 492 | |
Raymond Hettinger | 1b9f5d4 | 2002-08-24 06:19:02 +0000 | [diff] [blame] | 493 | def __isub__(self, other): |
Guido van Rossum | d6cf3af | 2002-08-19 16:19:15 +0000 | [diff] [blame] | 494 | """Remove all elements of another set from this set.""" |
| 495 | self._binary_sanity_check(other) |
Raymond Hettinger | 6a18012 | 2003-08-17 08:34:09 +0000 | [diff] [blame] | 496 | self.difference_update(other) |
Guido van Rossum | d6cf3af | 2002-08-19 16:19:15 +0000 | [diff] [blame] | 497 | return self |
| 498 | |
Raymond Hettinger | 1b9f5d4 | 2002-08-24 06:19:02 +0000 | [diff] [blame] | 499 | def difference_update(self, other): |
| 500 | """Remove all elements of another set from this set.""" |
Raymond Hettinger | 6a18012 | 2003-08-17 08:34:09 +0000 | [diff] [blame] | 501 | data = self._data |
| 502 | if not isinstance(other, BaseSet): |
| 503 | other = Set(other) |
Raymond Hettinger | 038ca2a | 2005-08-13 02:29:58 +0000 | [diff] [blame] | 504 | if self is other: |
| 505 | self.clear() |
Raymond Hettinger | 6a18012 | 2003-08-17 08:34:09 +0000 | [diff] [blame] | 506 | for elt in ifilter(data.has_key, other): |
| 507 | del data[elt] |
Guido van Rossum | d6cf3af | 2002-08-19 16:19:15 +0000 | [diff] [blame] | 508 | |
| 509 | # Python dict-like mass mutations: update, clear |
| 510 | |
| 511 | def update(self, iterable): |
| 512 | """Add all values from an iterable (such as a list or file).""" |
Guido van Rossum | 9f87293 | 2002-08-21 03:20:44 +0000 | [diff] [blame] | 513 | self._update(iterable) |
Guido van Rossum | d6cf3af | 2002-08-19 16:19:15 +0000 | [diff] [blame] | 514 | |
| 515 | def clear(self): |
| 516 | """Remove all elements from this set.""" |
| 517 | self._data.clear() |
| 518 | |
| 519 | # Single-element mutations: add, remove, discard |
| 520 | |
| 521 | def add(self, element): |
| 522 | """Add an element to a set. |
| 523 | |
| 524 | This has no effect if the element is already present. |
| 525 | """ |
| 526 | try: |
Raymond Hettinger | de6d697 | 2002-08-21 01:35:29 +0000 | [diff] [blame] | 527 | self._data[element] = True |
| 528 | except TypeError: |
Raymond Hettinger | 2835e37 | 2003-02-14 03:42:11 +0000 | [diff] [blame] | 529 | transform = getattr(element, "__as_immutable__", None) |
Raymond Hettinger | de6d697 | 2002-08-21 01:35:29 +0000 | [diff] [blame] | 530 | if transform is None: |
| 531 | raise # re-raise the TypeError exception we caught |
| 532 | self._data[transform()] = True |
Guido van Rossum | d6cf3af | 2002-08-19 16:19:15 +0000 | [diff] [blame] | 533 | |
| 534 | def remove(self, element): |
| 535 | """Remove an element from a set; it must be a member. |
| 536 | |
| 537 | If the element is not a member, raise a KeyError. |
| 538 | """ |
| 539 | try: |
Raymond Hettinger | de6d697 | 2002-08-21 01:35:29 +0000 | [diff] [blame] | 540 | del self._data[element] |
| 541 | except TypeError: |
Raymond Hettinger | 2835e37 | 2003-02-14 03:42:11 +0000 | [diff] [blame] | 542 | transform = getattr(element, "__as_temporarily_immutable__", None) |
Raymond Hettinger | de6d697 | 2002-08-21 01:35:29 +0000 | [diff] [blame] | 543 | if transform is None: |
| 544 | raise # re-raise the TypeError exception we caught |
| 545 | del self._data[transform()] |
Guido van Rossum | d6cf3af | 2002-08-19 16:19:15 +0000 | [diff] [blame] | 546 | |
| 547 | def discard(self, element): |
| 548 | """Remove an element from a set if it is a member. |
| 549 | |
| 550 | If the element is not a member, do nothing. |
| 551 | """ |
| 552 | try: |
Guido van Rossum | e399d08 | 2002-08-23 14:45:02 +0000 | [diff] [blame] | 553 | self.remove(element) |
Guido van Rossum | d6cf3af | 2002-08-19 16:19:15 +0000 | [diff] [blame] | 554 | except KeyError: |
| 555 | pass |
| 556 | |
Guido van Rossum | c9196bc | 2002-08-20 21:51:59 +0000 | [diff] [blame] | 557 | def pop(self): |
Tim Peters | 53506be | 2002-08-23 20:36:58 +0000 | [diff] [blame] | 558 | """Remove and return an arbitrary set element.""" |
Guido van Rossum | d6cf3af | 2002-08-19 16:19:15 +0000 | [diff] [blame] | 559 | return self._data.popitem()[0] |
| 560 | |
Raymond Hettinger | 2835e37 | 2003-02-14 03:42:11 +0000 | [diff] [blame] | 561 | def __as_immutable__(self): |
Guido van Rossum | d6cf3af | 2002-08-19 16:19:15 +0000 | [diff] [blame] | 562 | # Return a copy of self as an immutable set |
| 563 | return ImmutableSet(self) |
| 564 | |
Raymond Hettinger | 2835e37 | 2003-02-14 03:42:11 +0000 | [diff] [blame] | 565 | def __as_temporarily_immutable__(self): |
Guido van Rossum | d6cf3af | 2002-08-19 16:19:15 +0000 | [diff] [blame] | 566 | # Return self wrapped in a temporarily immutable set |
| 567 | return _TemporarilyImmutableSet(self) |
| 568 | |
| 569 | |
Raymond Hettinger | fa1480f | 2002-08-24 02:35:48 +0000 | [diff] [blame] | 570 | class _TemporarilyImmutableSet(BaseSet): |
Guido van Rossum | d6cf3af | 2002-08-19 16:19:15 +0000 | [diff] [blame] | 571 | # Wrap a mutable set as if it was temporarily immutable. |
| 572 | # This only supplies hashing and equality comparisons. |
| 573 | |
Guido van Rossum | d6cf3af | 2002-08-19 16:19:15 +0000 | [diff] [blame] | 574 | def __init__(self, set): |
| 575 | self._set = set |
Raymond Hettinger | fa1480f | 2002-08-24 02:35:48 +0000 | [diff] [blame] | 576 | self._data = set._data # Needed by ImmutableSet.__eq__() |
Guido van Rossum | d6cf3af | 2002-08-19 16:19:15 +0000 | [diff] [blame] | 577 | |
| 578 | def __hash__(self): |
Raymond Hettinger | d501851 | 2002-08-24 04:47:42 +0000 | [diff] [blame] | 579 | return self._set._compute_hash() |