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
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
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
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.
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
34 actually added is an ImmutableSet built from it (it compares equal to
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
44
45
46
47
48
49
50
51
52
53
54
55
56
57 from __future__ import generators
58 try:
59 from itertools import ifilter, ifilterfalse
60 except ImportError:
61
63 if predicate is None:
64 def predicate(x):
65 return x
66 for x in iterable:
67 if predicate(x):
68 yield x
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
76 try:
77 True, False
78 except NameError:
79 True, False = (0==0, 0!=0)
80
81 __all__ = ['BaseSet', 'Set', 'ImmutableSet']
82
84 """Common base class for mutable and immutable sets."""
85
86 __slots__ = ['_data']
87
88
89
91 """This is an abstract class."""
92
93 if self.__class__ is BaseSet:
94 raise TypeError, ("BaseSet is an abstract class. "
95 "Use Set or ImmutableSet.")
96
97
98
100 """Return the number of elements of a set."""
101 return len(self._data)
102
104 """Return string representation of a set.
105
106 This looks like 'Set([<list of elements>])'.
107 """
108 return self._repr()
109
110
111 __str__ = __repr__
112
114 elements = self._data.keys()
115 if sorted:
116 elements.sort()
117 return '%s(%r)' % (self.__class__.__name__, elements)
118
120 """Return an iterator over the elements or a set.
121
122 This is the keys iterator for the underlying dict.
123 """
124 return self._data.iterkeys()
125
126
127
128
129
130
132 raise TypeError, "can't compare sets using cmp()"
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
154
160
161
162
168
169 __copy__ = copy
170
172 """Return a deep copy of a set; used by copy module."""
173
174
175
176
177
178 from copy import deepcopy
179 result = self.__class__()
180 memo[id(self)] = result
181 data = result._data
182 value = True
183 for elt in self:
184 data[deepcopy(elt, memo)] = value
185 return result
186
187
188
189
190
191
192
193
194
195
197 """Return the union of two sets as a new set.
198
199 (I.e. all elements that are in either set.)
200 """
201 if not isinstance(other, BaseSet):
202 return NotImplemented
203 return self.union(other)
204
206 """Return the union of two sets as a new set.
207
208 (I.e. all elements that are in either set.)
209 """
210 result = self.__class__(self)
211 result._update(other)
212 return result
213
215 """Return the intersection of two sets as a new set.
216
217 (I.e. all elements that are in both sets.)
218 """
219 if not isinstance(other, BaseSet):
220 return NotImplemented
221 return self.intersection(other)
222
224 """Return the intersection of two sets as a new set.
225
226 (I.e. all elements that are in both sets.)
227 """
228 if not isinstance(other, BaseSet):
229 other = Set(other)
230 if len(self) <= len(other):
231 little, big = self, other
232 else:
233 little, big = other, self
234 common = ifilter(big._data.has_key, little)
235 return self.__class__(common)
236
238 """Return the symmetric difference of two sets as a new set.
239
240 (I.e. all elements that are in exactly one of the sets.)
241 """
242 if not isinstance(other, BaseSet):
243 return NotImplemented
244 return self.symmetric_difference(other)
245
247 """Return the symmetric difference of two sets as a new set.
248
249 (I.e. all elements that are in exactly one of the sets.)
250 """
251 result = self.__class__()
252 data = result._data
253 value = True
254 selfdata = self._data
255 try:
256 otherdata = other._data
257 except AttributeError:
258 otherdata = Set(other)._data
259 for elt in ifilterfalse(otherdata.has_key, selfdata):
260 data[elt] = value
261 for elt in ifilterfalse(selfdata.has_key, otherdata):
262 data[elt] = value
263 return result
264
266 """Return the difference of two sets as a new Set.
267
268 (I.e. all elements that are in this set and not in the other.)
269 """
270 if not isinstance(other, BaseSet):
271 return NotImplemented
272 return self.difference(other)
273
275 """Return the difference of two sets as a new Set.
276
277 (I.e. all elements that are in this set and not in the other.)
278 """
279 result = self.__class__()
280 data = result._data
281 try:
282 otherdata = other._data
283 except AttributeError:
284 otherdata = Set(other)._data
285 value = True
286 for elt in ifilterfalse(otherdata.has_key, self):
287 data[elt] = value
288 return result
289
290
291
293 """Report whether an element is a member of a set.
294
295 (Called in response to the expression `element in self'.)
296 """
297 try:
298 return element in self._data
299 except TypeError:
300 transform = getattr(element, "__as_temporarily_immutable__", None)
301 if transform is None:
302 raise
303 return transform() in self._data
304
305
306
315
324
325
326 __le__ = issubset
327 __ge__ = issuperset
328
332
336
337
338
340
341
342 if not isinstance(other, BaseSet):
343 raise TypeError, "Binary operation only permitted between sets"
344
346
347
348
349
350
351 result = 0
352 for elt in self:
353 result ^= hash(elt)
354 return result
355
357
358 data = self._data
359
360
361 if isinstance(iterable, BaseSet):
362 data.update(iterable._data)
363 return
364
365 value = True
366
367 if type(iterable) in (list, tuple, xrange):
368
369
370 it = iter(iterable)
371 while True:
372 try:
373 for element in it:
374 data[element] = value
375 return
376 except TypeError:
377 transform = getattr(element, "__as_immutable__", None)
378 if transform is None:
379 raise
380 data[transform()] = value
381 else:
382
383 for element in iterable:
384 try:
385 data[element] = value
386 except TypeError:
387 transform = getattr(element, "__as_immutable__", None)
388 if transform is None:
389 raise
390 data[transform()] = value
391
392
394 """Immutable set class."""
395
396 __slots__ = ['_hashcode']
397
398
399
401 """Construct an immutable set from an optional iterable."""
402 self._hashcode = None
403 self._data = {}
404 if iterable is not None:
405 self._update(iterable)
406
411
414
417
419 """ Mutable set class."""
420
421 __slots__ = []
422
423
424
426 """Construct a set from an optional iterable."""
427 self._data = {}
428 if iterable is not None:
429 self._update(iterable)
430
432
433 return self._data,
434
437
439 """A Set cannot be hashed."""
440
441 raise TypeError, "Can't hash a Set, only an ImmutableSet."
442
443
444
445
446
447
453
455 """Update a set with the union of itself and another."""
456 self._update(other)
457
459 """Update a set with the intersection of itself and another."""
460 self._binary_sanity_check(other)
461 self._data = (self & other)._data
462 return self
463
465 """Update a set with the intersection of itself and another."""
466 if isinstance(other, BaseSet):
467 self &= other
468 else:
469 self._data = (self.intersection(other))._data
470
476
478 """Update a set with the symmetric difference of itself and another."""
479 data = self._data
480 value = True
481 if not isinstance(other, BaseSet):
482 other = Set(other)
483 if self is other:
484 self.clear()
485 for elt in other:
486 if elt in data:
487 del data[elt]
488 else:
489 data[elt] = value
490
496
498 """Remove all elements of another set from this set."""
499 data = self._data
500 if not isinstance(other, BaseSet):
501 other = Set(other)
502 if self is other:
503 self.clear()
504 for elt in ifilter(data.has_key, other):
505 del data[elt]
506
507
508
510 """Add all values from an iterable (such as a list or file)."""
511 self._update(iterable)
512
514 """Remove all elements from this set."""
515 self._data.clear()
516
517
518
519 - def add(self, element):
520 """Add an element to a set.
521
522 This has no effect if the element is already present.
523 """
524 try:
525 self._data[element] = True
526 except TypeError:
527 transform = getattr(element, "__as_immutable__", None)
528 if transform is None:
529 raise
530 self._data[transform()] = True
531
533 """Remove an element from a set; it must be a member.
534
535 If the element is not a member, raise a KeyError.
536 """
537 try:
538 del self._data[element]
539 except TypeError:
540 transform = getattr(element, "__as_temporarily_immutable__", None)
541 if transform is None:
542 raise
543 del self._data[transform()]
544
546 """Remove an element from a set if it is a member.
547
548 If the element is not a member, do nothing.
549 """
550 try:
551 self.remove(element)
552 except KeyError:
553 pass
554
556 """Remove and return an arbitrary set element."""
557 return self._data.popitem()[0]
558
562
566
567
578
579
580
581
582
583
584