Python code coverage for Lib/sets.py

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