Debian Codegraph @

Lib/test/test_set.py

raw
1 import collections.abc
2 import copy
3 import gc
4 import itertools
5 import operator
6 import pickle
7 import re
8 import unittest
9 import warnings
10 import weakref
11 from random import randrange, shuffle
12 from test import support
13 from test.support import warnings_helper
14
15
16 class PassThru(Exception):
17 pass
18
19 def check_pass_thru():
20 raise PassThru
21 yield 1
22
23 class CustomHash:
24 def __init__(self, hash):
25 self.hash = hash
26 def __hash__(self):
27 return self.hash
28 def __repr__(self):
29 return f'<CustomHash {self.hash} at {id(self):#x}>'
30
31 class BadCmp:
32 def __hash__(self):
33 return 1
34 def __eq__(self, other):
35 raise RuntimeError
36
37 class ReprWrapper:
38 'Used to test self-referential repr() calls'
39 def __repr__(self):
40 return repr(self.value)
41
42 class HashCountingInt(int):
43 'int-like object that counts the number of times __hash__ is called'
44 def __init__(self, *args):
45 self.hash_count = 0
46 def __hash__(self):
47 self.hash_count += 1
48 return int.__hash__(self)
49
50 class TestJointOps:
51 # Tests common to both set and frozenset
52
53 def setUp(self):
54 self.word = word = 'simsalabim'
55 self.otherword = 'madagascar'
56 self.letters = 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ'
57 self.s = self.thetype(word)
58 self.d = dict.fromkeys(word)
59
60 def test_new_or_init(self):
61 self.assertRaises(TypeError, self.thetype, [], 2)
62 self.assertRaises(TypeError, set().__init__, a=1)
63
64 def test_uniquification(self):
65 actual = sorted(self.s)
66 expected = sorted(self.d)
67 self.assertEqual(actual, expected)
68 self.assertRaises(PassThru, self.thetype, check_pass_thru())
69 self.assertRaises(TypeError, self.thetype, [[]])
70
71 def test_len(self):
72 self.assertEqual(len(self.s), len(self.d))
73
74 def test_contains(self):
75 for c in self.letters:
76 self.assertEqual(c in self.s, c in self.d)
77 self.assertRaises(TypeError, self.s.__contains__, [[]])
78 s = self.thetype([frozenset(self.letters)])
79 self.assertIn(self.thetype(self.letters), s)
80
81 def test_union(self):
82 u = self.s.union(self.otherword)
83 for c in self.letters:
84 self.assertEqual(c in u, c in self.d or c in self.otherword)
85 self.assertEqual(self.s, self.thetype(self.word))
86 self.assertEqual(type(u), self.basetype)
87 self.assertRaises(PassThru, self.s.union, check_pass_thru())
88 self.assertRaises(TypeError, self.s.union, [[]])
89 for C in set, frozenset, dict.fromkeys, str, list, tuple:
90 self.assertEqual(self.thetype('abcba').union(C('cdc')), set('abcd'))
91 self.assertEqual(self.thetype('abcba').union(C('efgfe')), set('abcefg'))
92 self.assertEqual(self.thetype('abcba').union(C('ccb')), set('abc'))
93 self.assertEqual(self.thetype('abcba').union(C('ef')), set('abcef'))
94 self.assertEqual(self.thetype('abcba').union(C('ef'), C('fg')), set('abcefg'))
95
96 # Issue #6573
97 x = self.thetype()
98 self.assertEqual(x.union(set([1]), x, set([2])), self.thetype([1, 2]))
99
100 def test_or(self):
101 i = self.s.union(self.otherword)
102 self.assertEqual(self.s | set(self.otherword), i)
103 self.assertEqual(self.s | frozenset(self.otherword), i)
104 try:
105 self.s | self.otherword
106 except TypeError:
107 pass
108 else:
109 self.fail("s|t did not screen-out general iterables")
110
111 def test_intersection(self):
112 i = self.s.intersection(self.otherword)
113 for c in self.letters:
114 self.assertEqual(c in i, c in self.d and c in self.otherword)
115 self.assertEqual(self.s, self.thetype(self.word))
116 self.assertEqual(type(i), self.basetype)
117 self.assertRaises(PassThru, self.s.intersection, check_pass_thru())
118 for C in set, frozenset, dict.fromkeys, str, list, tuple:
119 self.assertEqual(self.thetype('abcba').intersection(C('cdc')), set('cc'))
120 self.assertEqual(self.thetype('abcba').intersection(C('efgfe')), set(''))
121 self.assertEqual(self.thetype('abcba').intersection(C('ccb')), set('bc'))
122 self.assertEqual(self.thetype('abcba').intersection(C('ef')), set(''))
123 self.assertEqual(self.thetype('abcba').intersection(C('cbcf'), C('bag')), set('b'))
124 s = self.thetype('abcba')
125 z = s.intersection()
126 if self.thetype == frozenset():
127 self.assertEqual(id(s), id(z))
128 else:
129 self.assertNotEqual(id(s), id(z))
130
131 def test_isdisjoint(self):
132 def f(s1, s2):
133 'Pure python equivalent of isdisjoint()'
134 return not set(s1).intersection(s2)
135 for larg in '', 'a', 'ab', 'abc', 'ababac', 'cdc', 'cc', 'efgfe', 'ccb', 'ef':
136 s1 = self.thetype(larg)
137 for rarg in '', 'a', 'ab', 'abc', 'ababac', 'cdc', 'cc', 'efgfe', 'ccb', 'ef':
138 for C in set, frozenset, dict.fromkeys, str, list, tuple:
139 s2 = C(rarg)
140 actual = s1.isdisjoint(s2)
141 expected = f(s1, s2)
142 self.assertEqual(actual, expected)
143 self.assertTrue(actual is True or actual is False)
144
145 def test_and(self):
146 i = self.s.intersection(self.otherword)
147 self.assertEqual(self.s & set(self.otherword), i)
148 self.assertEqual(self.s & frozenset(self.otherword), i)
149 try:
150 self.s & self.otherword
151 except TypeError:
152 pass
153 else:
154 self.fail("s&t did not screen-out general iterables")
155
156 def test_difference(self):
157 i = self.s.difference(self.otherword)
158 for c in self.letters:
159 self.assertEqual(c in i, c in self.d and c not in self.otherword)
160 self.assertEqual(self.s, self.thetype(self.word))
161 self.assertEqual(type(i), self.basetype)
162 self.assertRaises(PassThru, self.s.difference, check_pass_thru())
163 self.assertRaises(TypeError, self.s.difference, [[]])
164 for C in set, frozenset, dict.fromkeys, str, list, tuple:
165 self.assertEqual(self.thetype('abcba').difference(C('cdc')), set('ab'))
166 self.assertEqual(self.thetype('abcba').difference(C('efgfe')), set('abc'))
167 self.assertEqual(self.thetype('abcba').difference(C('ccb')), set('a'))
168 self.assertEqual(self.thetype('abcba').difference(C('ef')), set('abc'))
169 self.assertEqual(self.thetype('abcba').difference(), set('abc'))
170 self.assertEqual(self.thetype('abcba').difference(C('a'), C('b')), set('c'))
171
172 def test_sub(self):
173 i = self.s.difference(self.otherword)
174 self.assertEqual(self.s - set(self.otherword), i)
175 self.assertEqual(self.s - frozenset(self.otherword), i)
176 try:
177 self.s - self.otherword
178 except TypeError:
179 pass
180 else:
181 self.fail("s-t did not screen-out general iterables")
182
183 def test_symmetric_difference(self):
184 i = self.s.symmetric_difference(self.otherword)
185 for c in self.letters:
186 self.assertEqual(c in i, (c in self.d) ^ (c in self.otherword))
187 self.assertEqual(self.s, self.thetype(self.word))
188 self.assertEqual(type(i), self.basetype)
189 self.assertRaises(PassThru, self.s.symmetric_difference, check_pass_thru())
190 self.assertRaises(TypeError, self.s.symmetric_difference, [[]])
191 for C in set, frozenset, dict.fromkeys, str, list, tuple:
192 self.assertEqual(self.thetype('abcba').symmetric_difference(C('cdc')), set('abd'))
193 self.assertEqual(self.thetype('abcba').symmetric_difference(C('efgfe')), set('abcefg'))
194 self.assertEqual(self.thetype('abcba').symmetric_difference(C('ccb')), set('a'))
195 self.assertEqual(self.thetype('abcba').symmetric_difference(C('ef')), set('abcef'))
196
197 def test_xor(self):
198 i = self.s.symmetric_difference(self.otherword)
199 self.assertEqual(self.s ^ set(self.otherword), i)
200 self.assertEqual(self.s ^ frozenset(self.otherword), i)
201 try:
202 self.s ^ self.otherword
203 except TypeError:
204 pass
205 else:
206 self.fail("s^t did not screen-out general iterables")
207
208 def test_equality(self):
209 self.assertEqual(self.s, set(self.word))
210 self.assertEqual(self.s, frozenset(self.word))
211 self.assertEqual(self.s == self.word, False)
212 self.assertNotEqual(self.s, set(self.otherword))
213 self.assertNotEqual(self.s, frozenset(self.otherword))
214 self.assertEqual(self.s != self.word, True)
215
216 def test_setOfFrozensets(self):
217 t = map(frozenset, ['abcdef', 'bcd', 'bdcb', 'fed', 'fedccba'])
218 s = self.thetype(t)
219 self.assertEqual(len(s), 3)
220
221 def test_sub_and_super(self):
222 p, q, r = map(self.thetype, ['ab', 'abcde', 'def'])
223 self.assertTrue(p < q)
224 self.assertTrue(p <= q)
225 self.assertTrue(q <= q)
226 self.assertTrue(q > p)
227 self.assertTrue(q >= p)
228 self.assertFalse(q < r)
229 self.assertFalse(q <= r)
230 self.assertFalse(q > r)
231 self.assertFalse(q >= r)
232 self.assertTrue(set('a').issubset('abc'))
233 self.assertTrue(set('abc').issuperset('a'))
234 self.assertFalse(set('a').issubset('cbs'))
235 self.assertFalse(set('cbs').issuperset('a'))
236
237 def test_pickling(self):
238 for i in range(pickle.HIGHEST_PROTOCOL + 1):
239 if type(self.s) not in (set, frozenset):
240 self.s.x = ['x']
241 self.s.z = ['z']
242 p = pickle.dumps(self.s, i)
243 dup = pickle.loads(p)
244 self.assertEqual(self.s, dup, "%s != %s" % (self.s, dup))
245 if type(self.s) not in (set, frozenset):
246 self.assertEqual(self.s.x, dup.x)
247 self.assertEqual(self.s.z, dup.z)
248 self.assertNotHasAttr(self.s, 'y')
249 del self.s.x, self.s.z
250
251 def test_iterator_pickling(self):
252 for proto in range(pickle.HIGHEST_PROTOCOL + 1):
253 itorg = iter(self.s)
254 data = self.thetype(self.s)
255 d = pickle.dumps(itorg, proto)
256 it = pickle.loads(d)
257 # Set iterators unpickle as list iterators due to the
258 # undefined order of set items.
259 # self.assertEqual(type(itorg), type(it))
260 self.assertIsInstance(it, collections.abc.Iterator)
261 self.assertEqual(self.thetype(it), data)
262
263 it = pickle.loads(d)
264 try:
265 drop = next(it)
266 except StopIteration:
267 continue
268 d = pickle.dumps(it, proto)
269 it = pickle.loads(d)
270 self.assertEqual(self.thetype(it), data - self.thetype((drop,)))
271
272 def test_deepcopy(self):
273 class Tracer:
274 def __init__(self, value):
275 self.value = value
276 def __hash__(self):
277 return self.value
278 def __deepcopy__(self, memo=None):
279 return Tracer(self.value + 1)
280 t = Tracer(10)
281 s = self.thetype([t])
282 dup = copy.deepcopy(s)
283 self.assertNotEqual(id(s), id(dup))
284 for elem in dup:
285 newt = elem
286 self.assertNotEqual(id(t), id(newt))
287 self.assertEqual(t.value + 1, newt.value)
288
289 def test_gc(self):
290 # Create a nest of cycles to exercise overall ref count check
291 class A:
292 pass
293 s = set(A() for i in range(1000))
294 for elem in s:
295 elem.cycle = s
296 elem.sub = elem
297 elem.set = set([elem])
298
299 def test_subclass_with_custom_hash(self):
300 # Bug #1257731
301 class H(self.thetype):
302 def __hash__(self):
303 return int(id(self) & 0x7fffffff)
304 s=H()
305 f=set()
306 f.add(s)
307 self.assertIn(s, f)
308 f.remove(s)
309 f.add(s)
310 f.discard(s)
311
312 def test_badcmp(self):
313 s = self.thetype([BadCmp()])
314 # Detect comparison errors during insertion and lookup
315 self.assertRaises(RuntimeError, self.thetype, [BadCmp(), BadCmp()])
316 self.assertRaises(RuntimeError, s.__contains__, BadCmp())
317 # Detect errors during mutating operations
318 if hasattr(s, 'add'):
319 self.assertRaises(RuntimeError, s.add, BadCmp())
320 self.assertRaises(RuntimeError, s.discard, BadCmp())
321 self.assertRaises(RuntimeError, s.remove, BadCmp())
322
323 def test_cyclical_repr(self):
324 w = ReprWrapper()
325 s = self.thetype([w])
326 w.value = s
327 if self.thetype == set:
328 self.assertEqual(repr(s), '{set(...)}')
329 else:
330 name = repr(s).partition('(')[0] # strip class name
331 self.assertEqual(repr(s), '%s({%s(...)})' % (name, name))
332
333 def test_do_not_rehash_dict_keys(self):
334 n = 10
335 d = dict.fromkeys(map(HashCountingInt, range(n)))
336 self.assertEqual(sum(elem.hash_count for elem in d), n)
337 s = self.thetype(d)
338 self.assertEqual(sum(elem.hash_count for elem in d), n)
339 s.difference(d)
340 self.assertEqual(sum(elem.hash_count for elem in d), n)
341 if hasattr(s, 'symmetric_difference_update'):
342 s.symmetric_difference_update(d)
343 self.assertEqual(sum(elem.hash_count for elem in d), n)
344 d2 = dict.fromkeys(set(d))
345 self.assertEqual(sum(elem.hash_count for elem in d), n)
346 d3 = dict.fromkeys(frozenset(d))
347 self.assertEqual(sum(elem.hash_count for elem in d), n)
348 d3 = dict.fromkeys(frozenset(d), 123)
349 self.assertEqual(sum(elem.hash_count for elem in d), n)
350 self.assertEqual(d3, dict.fromkeys(d, 123))
351
352 def test_container_iterator(self):
353 # Bug #3680: tp_traverse was not implemented for set iterator object
354 class C(object):
355 pass
356 obj = C()
357 ref = weakref.ref(obj)
358 container = set([obj, 1])
359 obj.x = iter(container)
360 del obj, container
361 gc.collect()
362 self.assertTrue(ref() is None, "Cycle was not collected")
363
364 def test_free_after_iterating(self):
365 support.check_free_after_iterating(self, iter, self.thetype)
366
367 class TestSet(TestJointOps, unittest.TestCase):
368 thetype = set
369 basetype = set
370
371 def test_init(self):
372 s = self.thetype()
373 s.__init__(self.word)
374 self.assertEqual(s, set(self.word))
375 s.__init__(self.otherword)
376 self.assertEqual(s, set(self.otherword))
377 self.assertRaises(TypeError, s.__init__, s, 2)
378 self.assertRaises(TypeError, s.__init__, 1)
379
380 def test_constructor_identity(self):
381 s = self.thetype(range(3))
382 t = self.thetype(s)
383 self.assertNotEqual(id(s), id(t))
384
385 def test_set_literal(self):
386 s = set([1,2,3])
387 t = {1,2,3}
388 self.assertEqual(s, t)
389
390 def test_set_literal_insertion_order(self):
391 # SF Issue #26020 -- Expect left to right insertion
392 s = {1, 1.0, True}
393 self.assertEqual(len(s), 1)
394 stored_value = s.pop()
395 self.assertEqual(type(stored_value), int)
396
397 def test_set_literal_evaluation_order(self):
398 # Expect left to right expression evaluation
399 events = []
400 def record(obj):
401 events.append(obj)
402 s = {record(1), record(2), record(3)}
403 self.assertEqual(events, [1, 2, 3])
404
405 def test_hash(self):
406 self.assertRaises(TypeError, hash, self.s)
407
408 def test_clear(self):
409 self.s.clear()
410 self.assertEqual(self.s, set())
411 self.assertEqual(len(self.s), 0)
412
413 def test_copy(self):
414 dup = self.s.copy()
415 self.assertEqual(self.s, dup)
416 self.assertNotEqual(id(self.s), id(dup))
417 self.assertEqual(type(dup), self.basetype)
418
419 def test_add(self):
420 self.s.add('Q')
421 self.assertIn('Q', self.s)
422 dup = self.s.copy()
423 self.s.add('Q')
424 self.assertEqual(self.s, dup)
425 self.assertRaises(TypeError, self.s.add, [])
426
427 def test_remove(self):
428 self.s.remove('a')
429 self.assertNotIn('a', self.s)
430 self.assertRaises(KeyError, self.s.remove, 'Q')
431 self.assertRaises(TypeError, self.s.remove, [])
432 s = self.thetype([frozenset(self.word)])
433 self.assertIn(self.thetype(self.word), s)
434 s.remove(self.thetype(self.word))
435 self.assertNotIn(self.thetype(self.word), s)
436 self.assertRaises(KeyError, self.s.remove, self.thetype(self.word))
437
438 def test_remove_keyerror_unpacking(self):
439 # https://bugs.python.org/issue1576657
440 for v1 in ['Q', (1,)]:
441 try:
442 self.s.remove(v1)
443 except KeyError as e:
444 v2 = e.args[0]
445 self.assertEqual(v1, v2)
446 else:
447 self.fail()
448
449 def test_remove_keyerror_set(self):
450 key = self.thetype([3, 4])
451 try:
452 self.s.remove(key)
453 except KeyError as e:
454 self.assertTrue(e.args[0] is key,
455 "KeyError should be {0}, not {1}".format(key,
456 e.args[0]))
457 else:
458 self.fail()
459
460 def test_discard(self):
461 self.s.discard('a')
462 self.assertNotIn('a', self.s)
463 self.s.discard('Q')
464 self.assertRaises(TypeError, self.s.discard, [])
465 s = self.thetype([frozenset(self.word)])
466 self.assertIn(self.thetype(self.word), s)
467 s.discard(self.thetype(self.word))
468 self.assertNotIn(self.thetype(self.word), s)
469 s.discard(self.thetype(self.word))
470
471 def test_pop(self):
472 for i in range(len(self.s)):
473 elem = self.s.pop()
474 self.assertNotIn(elem, self.s)
475 self.assertRaises(KeyError, self.s.pop)
476
477 def test_update(self):
478 retval = self.s.update(self.otherword)
479 self.assertEqual(retval, None)
480 for c in (self.word + self.otherword):
481 self.assertIn(c, self.s)
482 self.assertRaises(PassThru, self.s.update, check_pass_thru())
483 self.assertRaises(TypeError, self.s.update, [[]])
484 for p, q in (('cdc', 'abcd'), ('efgfe', 'abcefg'), ('ccb', 'abc'), ('ef', 'abcef')):
485 for C in set, frozenset, dict.fromkeys, str, list, tuple:
486 s = self.thetype('abcba')
487 self.assertEqual(s.update(C(p)), None)
488 self.assertEqual(s, set(q))
489 for p in ('cdc', 'efgfe', 'ccb', 'ef', 'abcda'):
490 q = 'ahi'
491 for C in set, frozenset, dict.fromkeys, str, list, tuple:
492 s = self.thetype('abcba')
493 self.assertEqual(s.update(C(p), C(q)), None)
494 self.assertEqual(s, set(s) | set(p) | set(q))
495
496 def test_ior(self):
497 self.s |= set(self.otherword)
498 for c in (self.word + self.otherword):
499 self.assertIn(c, self.s)
500
501 def test_intersection_update(self):
502 retval = self.s.intersection_update(self.otherword)
503 self.assertEqual(retval, None)
504 for c in (self.word + self.otherword):
505 if c in self.otherword and c in self.word:
506 self.assertIn(c, self.s)
507 else:
508 self.assertNotIn(c, self.s)
509 self.assertRaises(PassThru, self.s.intersection_update, check_pass_thru())
510 self.assertRaises(TypeError, self.s.intersection_update, [[]])
511 for p, q in (('cdc', 'c'), ('efgfe', ''), ('ccb', 'bc'), ('ef', '')):
512 for C in set, frozenset, dict.fromkeys, str, list, tuple:
513 s = self.thetype('abcba')
514 self.assertEqual(s.intersection_update(C(p)), None)
515 self.assertEqual(s, set(q))
516 ss = 'abcba'
517 s = self.thetype(ss)
518 t = 'cbc'
519 self.assertEqual(s.intersection_update(C(p), C(t)), None)
520 self.assertEqual(s, set('abcba')&set(p)&set(t))
521
522 def test_iand(self):
523 self.s &= set(self.otherword)
524 for c in (self.word + self.otherword):
525 if c in self.otherword and c in self.word:
526 self.assertIn(c, self.s)
527 else:
528 self.assertNotIn(c, self.s)
529
530 def test_difference_update(self):
531 retval = self.s.difference_update(self.otherword)
532 self.assertEqual(retval, None)
533 for c in (self.word + self.otherword):
534 if c in self.word and c not in self.otherword:
535 self.assertIn(c, self.s)
536 else:
537 self.assertNotIn(c, self.s)
538 self.assertRaises(PassThru, self.s.difference_update, check_pass_thru())
539 self.assertRaises(TypeError, self.s.difference_update, [[]])
540 self.assertRaises(TypeError, self.s.symmetric_difference_update, [[]])
541 for p, q in (('cdc', 'ab'), ('efgfe', 'abc'), ('ccb', 'a'), ('ef', 'abc')):
542 for C in set, frozenset, dict.fromkeys, str, list, tuple:
543 s = self.thetype('abcba')
544 self.assertEqual(s.difference_update(C(p)), None)
545 self.assertEqual(s, set(q))
546
547 s = self.thetype('abcdefghih')
548 s.difference_update()
549 self.assertEqual(s, self.thetype('abcdefghih'))
550
551 s = self.thetype('abcdefghih')
552 s.difference_update(C('aba'))
553 self.assertEqual(s, self.thetype('cdefghih'))
554
555 s = self.thetype('abcdefghih')
556 s.difference_update(C('cdc'), C('aba'))
557 self.assertEqual(s, self.thetype('efghih'))
558
559 def test_isub(self):
560 self.s -= set(self.otherword)
561 for c in (self.word + self.otherword):
562 if c in self.word and c not in self.otherword:
563 self.assertIn(c, self.s)
564 else:
565 self.assertNotIn(c, self.s)
566
567 def test_symmetric_difference_update(self):
568 retval = self.s.symmetric_difference_update(self.otherword)
569 self.assertEqual(retval, None)
570 for c in (self.word + self.otherword):
571 if (c in self.word) ^ (c in self.otherword):
572 self.assertIn(c, self.s)
573 else:
574 self.assertNotIn(c, self.s)
575 self.assertRaises(PassThru, self.s.symmetric_difference_update, check_pass_thru())
576 self.assertRaises(TypeError, self.s.symmetric_difference_update, [[]])
577 for p, q in (('cdc', 'abd'), ('efgfe', 'abcefg'), ('ccb', 'a'), ('ef', 'abcef')):
578 for C in set, frozenset, dict.fromkeys, str, list, tuple:
579 s = self.thetype('abcba')
580 self.assertEqual(s.symmetric_difference_update(C(p)), None)
581 self.assertEqual(s, set(q))
582
583 def test_ixor(self):
584 self.s ^= set(self.otherword)
585 for c in (self.word + self.otherword):
586 if (c in self.word) ^ (c in self.otherword):
587 self.assertIn(c, self.s)
588 else:
589 self.assertNotIn(c, self.s)
590
591 def test_inplace_on_self(self):
592 t = self.s.copy()
593 t |= t
594 self.assertEqual(t, self.s)
595 t &= t
596 self.assertEqual(t, self.s)
597 t -= t
598 self.assertEqual(t, self.thetype())
599 t = self.s.copy()
600 t ^= t
601 self.assertEqual(t, self.thetype())
602
603 def test_weakref(self):
604 s = self.thetype('gallahad')
605 p = weakref.proxy(s)
606 self.assertEqual(str(p), str(s))
607 s = None
608 support.gc_collect() # For PyPy or other GCs.
609 self.assertRaises(ReferenceError, str, p)
610
611 def test_rich_compare(self):
612 class TestRichSetCompare:
613 def __gt__(self, some_set):
614 self.gt_called = True
615 return False
616 def __lt__(self, some_set):
617 self.lt_called = True
618 return False
619 def __ge__(self, some_set):
620 self.ge_called = True
621 return False
622 def __le__(self, some_set):
623 self.le_called = True
624 return False
625
626 # This first tries the builtin rich set comparison, which doesn't know
627 # how to handle the custom object. Upon returning NotImplemented, the
628 # corresponding comparison on the right object is invoked.
629 myset = {1, 2, 3}
630
631 myobj = TestRichSetCompare()
632 myset < myobj
633 self.assertTrue(myobj.gt_called)
634
635 myobj = TestRichSetCompare()
636 myset > myobj
637 self.assertTrue(myobj.lt_called)
638
639 myobj = TestRichSetCompare()
640 myset <= myobj
641 self.assertTrue(myobj.ge_called)
642
643 myobj = TestRichSetCompare()
644 myset >= myobj
645 self.assertTrue(myobj.le_called)
646
647 def test_set_membership(self):
648 myfrozenset = frozenset(range(3))
649 myset = {myfrozenset, "abc", 1}
650 self.assertIn(set(range(3)), myset)
651 self.assertNotIn(set(range(1)), myset)
652 myset.discard(set(range(3)))
653 self.assertEqual(myset, {"abc", 1})
654 self.assertRaises(KeyError, myset.remove, set(range(1)))
655 self.assertRaises(KeyError, myset.remove, set(range(3)))
656
657 def test_unhashable_element(self):
658 myset = {'a'}
659 elem = [1, 2, 3]
660
661 def check_unhashable_element():
662 msg = "cannot use 'list' as a set element (unhashable type: 'list')"
663 return self.assertRaisesRegex(TypeError, re.escape(msg))
664
665 with check_unhashable_element():
666 elem in myset
667 with check_unhashable_element():
668 myset.add(elem)
669 with check_unhashable_element():
670 myset.discard(elem)
671
672 # Only TypeError exception is overriden,
673 # other exceptions are left unchanged.
674 class HashError:
675 def __hash__(self):
676 raise KeyError('error')
677
678 elem2 = HashError()
679 with self.assertRaises(KeyError):
680 elem2 in myset
681 with self.assertRaises(KeyError):
682 myset.add(elem2)
683 with self.assertRaises(KeyError):
684 myset.discard(elem2)
685
686 def test_hash_collision_remove_add(self):
687 self.maxDiff = None
688 # There should be enough space, so all elements with unique hash
689 # will be placed in corresponding cells without collision.
690 n = 64
691 elems = [CustomHash(h) for h in range(n)]
692 # Elements with hash collision.
693 a = CustomHash(n)
694 b = CustomHash(n)
695 elems += [a, b]
696 s = self.thetype(elems)
697 self.assertEqual(len(s), len(elems), s)
698 s.remove(a)
699 # "a" has been replaced with a dummy.
700 del elems[n]
701 self.assertEqual(len(s), len(elems), s)
702 self.assertEqual(s, set(elems))
703 s.add(b)
704 # "b" should not replace the dummy.
705 self.assertEqual(len(s), len(elems), s)
706 self.assertEqual(s, set(elems))
707
708
709 class SetSubclass(set):
710 pass
711
712 class TestSetSubclass(TestSet):
713 thetype = SetSubclass
714 basetype = set
715
716 def test_keywords_in_subclass(self):
717 class subclass(set):
718 pass
719 u = subclass([1, 2])
720 self.assertIs(type(u), subclass)
721 self.assertEqual(set(u), {1, 2})
722 with self.assertRaises(TypeError):
723 subclass(sequence=())
724
725 class subclass_with_init(set):
726 def __init__(self, arg, newarg=None):
727 super().__init__(arg)
728 self.newarg = newarg
729 u = subclass_with_init([1, 2], newarg=3)
730 self.assertIs(type(u), subclass_with_init)
731 self.assertEqual(set(u), {1, 2})
732 self.assertEqual(u.newarg, 3)
733
734 class subclass_with_new(set):
735 def __new__(cls, arg, newarg=None):
736 self = super().__new__(cls, arg)
737 self.newarg = newarg
738 return self
739 u = subclass_with_new([1, 2])
740 self.assertIs(type(u), subclass_with_new)
741 self.assertEqual(set(u), {1, 2})
742 self.assertIsNone(u.newarg)
743 # disallow kwargs in __new__ only (https://bugs.python.org/issue43413#msg402000)
744 with self.assertRaises(TypeError):
745 subclass_with_new([1, 2], newarg=3)
746
747
748 class TestFrozenSet(TestJointOps, unittest.TestCase):
749 thetype = frozenset
750 basetype = frozenset
751
752 def test_init(self):
753 s = self.thetype(self.word)
754 s.__init__(self.otherword)
755 self.assertEqual(s, set(self.word))
756
757 def test_constructor_identity(self):
758 s = self.thetype(range(3))
759 t = self.thetype(s)
760 self.assertEqual(id(s), id(t))
761
762 def test_hash(self):
763 self.assertEqual(hash(self.thetype('abcdeb')),
764 hash(self.thetype('ebecda')))
765
766 # make sure that all permutations give the same hash value
767 n = 100
768 seq = [randrange(n) for i in range(n)]
769 results = set()
770 for i in range(200):
771 shuffle(seq)
772 results.add(hash(self.thetype(seq)))
773 self.assertEqual(len(results), 1)
774
775 def test_copy(self):
776 dup = self.s.copy()
777 self.assertEqual(id(self.s), id(dup))
778
779 def test_frozen_as_dictkey(self):
780 seq = list(range(10)) + list('abcdefg') + ['apple']
781 key1 = self.thetype(seq)
782 key2 = self.thetype(reversed(seq))
783 self.assertEqual(key1, key2)
784 self.assertNotEqual(id(key1), id(key2))
785 d = {}
786 d[key1] = 42
787 self.assertEqual(d[key2], 42)
788
789 def test_hash_caching(self):
790 f = self.thetype('abcdcda')
791 self.assertEqual(hash(f), hash(f))
792
793 def test_hash_effectiveness(self):
794 n = 13
795 hashvalues = set()
796 addhashvalue = hashvalues.add
797 elemmasks = [(i+1, 1<<i) for i in range(n)]
798 for i in range(2**n):
799 addhashvalue(hash(frozenset([e for e, m in elemmasks if m&i])))
800 self.assertEqual(len(hashvalues), 2**n)
801
802 def zf_range(n):
803 # https://en.wikipedia.org/wiki/Set-theoretic_definition_of_natural_numbers
804 nums = [frozenset()]
805 for i in range(n-1):
806 num = frozenset(nums)
807 nums.append(num)
808 return nums[:n]
809
810 def powerset(s):
811 for i in range(len(s)+1):
812 yield from map(frozenset, itertools.combinations(s, i))
813
814 for n in range(18):
815 t = 2 ** n
816 mask = t - 1
817 for nums in (range, zf_range):
818 u = len({h & mask for h in map(hash, powerset(nums(n)))})
819 self.assertGreater(4*u, t)
820
821 class FrozenSetSubclass(frozenset):
822 pass
823
824 class TestFrozenSetSubclass(TestFrozenSet):
825 thetype = FrozenSetSubclass
826 basetype = frozenset
827
828 def test_keywords_in_subclass(self):
829 class subclass(frozenset):
830 pass
831 u = subclass([1, 2])
832 self.assertIs(type(u), subclass)
833 self.assertEqual(set(u), {1, 2})
834 with self.assertRaises(TypeError):
835 subclass(sequence=())
836
837 class subclass_with_init(frozenset):
838 def __init__(self, arg, newarg=None):
839 self.newarg = newarg
840 u = subclass_with_init([1, 2], newarg=3)
841 self.assertIs(type(u), subclass_with_init)
842 self.assertEqual(set(u), {1, 2})
843 self.assertEqual(u.newarg, 3)
844
845 class subclass_with_new(frozenset):
846 def __new__(cls, arg, newarg=None):
847 self = super().__new__(cls, arg)
848 self.newarg = newarg
849 return self
850 u = subclass_with_new([1, 2], newarg=3)
851 self.assertIs(type(u), subclass_with_new)
852 self.assertEqual(set(u), {1, 2})
853 self.assertEqual(u.newarg, 3)
854
855 def test_constructor_identity(self):
856 s = self.thetype(range(3))
857 t = self.thetype(s)
858 self.assertNotEqual(id(s), id(t))
859
860 def test_copy(self):
861 dup = self.s.copy()
862 self.assertNotEqual(id(self.s), id(dup))
863
864 def test_nested_empty_constructor(self):
865 s = self.thetype()
866 t = self.thetype(s)
867 self.assertEqual(s, t)
868
869 def test_singleton_empty_frozenset(self):
870 Frozenset = self.thetype
871 f = frozenset()
872 F = Frozenset()
873 efs = [Frozenset(), Frozenset([]), Frozenset(()), Frozenset(''),
874 Frozenset(), Frozenset([]), Frozenset(()), Frozenset(''),
875 Frozenset(range(0)), Frozenset(Frozenset()),
876 Frozenset(frozenset()), f, F, Frozenset(f), Frozenset(F)]
877 # All empty frozenset subclass instances should have different ids
878 self.assertEqual(len(set(map(id, efs))), len(efs))
879
880
881 class SetSubclassWithSlots(set):
882 __slots__ = ('x', 'y', '__dict__')
883
884 class TestSetSubclassWithSlots(unittest.TestCase):
885 thetype = SetSubclassWithSlots
886 setUp = TestJointOps.setUp
887 test_pickling = TestJointOps.test_pickling
888
889 class FrozenSetSubclassWithSlots(frozenset):
890 __slots__ = ('x', 'y', '__dict__')
891
892 class TestFrozenSetSubclassWithSlots(TestSetSubclassWithSlots):
893 thetype = FrozenSetSubclassWithSlots
894
895 # Tests taken from test_sets.py =============================================
896
897 empty_set = set()
898
899 #==============================================================================
900
901 class TestBasicOps:
902
903 def test_repr(self):
904 if self.repr is not None:
905 self.assertEqual(repr(self.set), self.repr)
906
907 def check_repr_against_values(self):
908 text = repr(self.set)
909 self.assertStartsWith(text, '{')
910 self.assertEndsWith(text, '}')
911
912 result = text[1:-1].split(', ')
913 result.sort()
914 sorted_repr_values = [repr(value) for value in self.values]
915 sorted_repr_values.sort()
916 self.assertEqual(result, sorted_repr_values)
917
918 def test_length(self):
919 self.assertEqual(len(self.set), self.length)
920
921 def test_self_equality(self):
922 self.assertEqual(self.set, self.set)
923
924 def test_equivalent_equality(self):
925 self.assertEqual(self.set, self.dup)
926
927 def test_copy(self):
928 self.assertEqual(self.set.copy(), self.dup)
929
930 def test_self_union(self):
931 result = self.set | self.set
932 self.assertEqual(result, self.dup)
933
934 def test_empty_union(self):
935 result = self.set | empty_set
936 self.assertEqual(result, self.dup)
937
938 def test_union_empty(self):
939 result = empty_set | self.set
940 self.assertEqual(result, self.dup)
941
942 def test_self_intersection(self):
943 result = self.set & self.set
944 self.assertEqual(result, self.dup)
945
946 def test_empty_intersection(self):
947 result = self.set & empty_set
948 self.assertEqual(result, empty_set)
949
950 def test_intersection_empty(self):
951 result = empty_set & self.set
952 self.assertEqual(result, empty_set)
953
954 def test_self_isdisjoint(self):
955 result = self.set.isdisjoint(self.set)
956 self.assertEqual(result, not self.set)
957
958 def test_empty_isdisjoint(self):
959 result = self.set.isdisjoint(empty_set)
960 self.assertEqual(result, True)
961
962 def test_isdisjoint_empty(self):
963 result = empty_set.isdisjoint(self.set)
964 self.assertEqual(result, True)
965
966 def test_self_symmetric_difference(self):
967 result = self.set ^ self.set
968 self.assertEqual(result, empty_set)
969
970 def test_empty_symmetric_difference(self):
971 result = self.set ^ empty_set
972 self.assertEqual(result, self.set)
973
974 def test_self_difference(self):
975 result = self.set - self.set
976 self.assertEqual(result, empty_set)
977
978 def test_empty_difference(self):
979 result = self.set - empty_set
980 self.assertEqual(result, self.dup)
981
982 def test_empty_difference_rev(self):
983 result = empty_set - self.set
984 self.assertEqual(result, empty_set)
985
986 def test_iteration(self):
987 for v in self.set:
988 self.assertIn(v, self.values)
989 setiter = iter(self.set)
990 self.assertEqual(setiter.__length_hint__(), len(self.set))
991
992 def test_pickling(self):
993 for proto in range(pickle.HIGHEST_PROTOCOL + 1):
994 p = pickle.dumps(self.set, proto)
995 copy = pickle.loads(p)
996 self.assertEqual(self.set, copy,
997 "%s != %s" % (self.set, copy))
998
999 def test_issue_37219(self):
1000 with self.assertRaises(TypeError):
1001 set().difference(123)
1002 with self.assertRaises(TypeError):
1003 set().difference_update(123)
1004
1005 #------------------------------------------------------------------------------
1006
1007 class TestBasicOpsEmpty(TestBasicOps, unittest.TestCase):
1008 def setUp(self):
1009 self.case = "empty set"
1010 self.values = []
1011 self.set = set(self.values)
1012 self.dup = set(self.values)
1013 self.length = 0
1014 self.repr = "set()"
1015
1016 #------------------------------------------------------------------------------
1017
1018 class TestBasicOpsSingleton(TestBasicOps, unittest.TestCase):
1019 def setUp(self):
1020 self.case = "unit set (number)"
1021 self.values = [3]
1022 self.set = set(self.values)
1023 self.dup = set(self.values)
1024 self.length = 1
1025 self.repr = "{3}"
1026
1027 def test_in(self):
1028 self.assertIn(3, self.set)
1029
1030 def test_not_in(self):
1031 self.assertNotIn(2, self.set)
1032
1033 #------------------------------------------------------------------------------
1034
1035 class TestBasicOpsTuple(TestBasicOps, unittest.TestCase):
1036 def setUp(self):
1037 self.case = "unit set (tuple)"
1038 self.values = [(0, "zero")]
1039 self.set = set(self.values)
1040 self.dup = set(self.values)
1041 self.length = 1
1042 self.repr = "{(0, 'zero')}"
1043
1044 def test_in(self):
1045 self.assertIn((0, "zero"), self.set)
1046
1047 def test_not_in(self):
1048 self.assertNotIn(9, self.set)
1049
1050 #------------------------------------------------------------------------------
1051
1052 class TestBasicOpsTriple(TestBasicOps, unittest.TestCase):
1053 def setUp(self):
1054 self.case = "triple set"
1055 self.values = [0, "zero", operator.add]
1056 self.set = set(self.values)
1057 self.dup = set(self.values)
1058 self.length = 3
1059 self.repr = None
1060
1061 #------------------------------------------------------------------------------
1062
1063 class TestBasicOpsString(TestBasicOps, unittest.TestCase):
1064 def setUp(self):
1065 self.case = "string set"
1066 self.values = ["a", "b", "c"]
1067 self.set = set(self.values)
1068 self.dup = set(self.values)
1069 self.length = 3
1070
1071 def test_repr(self):
1072 self.check_repr_against_values()
1073
1074 #------------------------------------------------------------------------------
1075
1076 class TestBasicOpsBytes(TestBasicOps, unittest.TestCase):
1077 def setUp(self):
1078 self.case = "bytes set"
1079 self.values = [b"a", b"b", b"c"]
1080 self.set = set(self.values)
1081 self.dup = set(self.values)
1082 self.length = 3
1083
1084 def test_repr(self):
1085 self.check_repr_against_values()
1086
1087 #------------------------------------------------------------------------------
1088
1089 class TestBasicOpsMixedStringBytes(TestBasicOps, unittest.TestCase):
1090 def setUp(self):
1091 self.enterContext(warnings_helper.check_warnings())
1092 warnings.simplefilter('ignore', BytesWarning)
1093 self.case = "string and bytes set"
1094 self.values = ["a", "b", b"a", b"b"]
1095 self.set = set(self.values)
1096 self.dup = set(self.values)
1097 self.length = 4
1098
1099 def test_repr(self):
1100 self.check_repr_against_values()
1101
1102 #==============================================================================
1103
1104 def baditer():
1105 raise TypeError
1106 yield True
1107
1108 def gooditer():
1109 yield True
1110
1111 class TestExceptionPropagation(unittest.TestCase):
1112 """SF 628246: Set constructor should not trap iterator TypeErrors"""
1113
1114 def test_instanceWithException(self):
1115 self.assertRaises(TypeError, set, baditer())
1116
1117 def test_instancesWithoutException(self):
1118 # All of these iterables should load without exception.
1119 set([1,2,3])
1120 set((1,2,3))
1121 set({'one':1, 'two':2, 'three':3})
1122 set(range(3))
1123 set('abc')
1124 set(gooditer())
1125
1126 def test_changingSizeWhileIterating(self):
1127 s = set([1,2,3])
1128 try:
1129 for i in s:
1130 s.update([4])
1131 except RuntimeError:
1132 pass
1133 else:
1134 self.fail("no exception when changing size during iteration")
1135
1136 #==============================================================================
1137
1138 class TestSetOfSets(unittest.TestCase):
1139 def test_constructor(self):
1140 inner = frozenset([1])
1141 outer = set([inner])
1142 element = outer.pop()
1143 self.assertEqual(type(element), frozenset)
1144 outer.add(inner) # Rebuild set of sets with .add method
1145 outer.remove(inner)
1146 self.assertEqual(outer, set()) # Verify that remove worked
1147 outer.discard(inner) # Absence of KeyError indicates working fine
1148
1149 #==============================================================================
1150
1151 class TestBinaryOps(unittest.TestCase):
1152 def setUp(self):
1153 self.set = set((2, 4, 6))
1154
1155 def test_eq(self): # SF bug 643115
1156 self.assertEqual(self.set, set({2:1,4:3,6:5}))
1157
1158 def test_union_subset(self):
1159 result = self.set | set([2])
1160 self.assertEqual(result, set((2, 4, 6)))
1161
1162 def test_union_superset(self):
1163 result = self.set | set([2, 4, 6, 8])
1164 self.assertEqual(result, set([2, 4, 6, 8]))
1165
1166 def test_union_overlap(self):
1167 result = self.set | set([3, 4, 5])
1168 self.assertEqual(result, set([2, 3, 4, 5, 6]))
1169
1170 def test_union_non_overlap(self):
1171 result = self.set | set([8])
1172 self.assertEqual(result, set([2, 4, 6, 8]))
1173
1174 def test_intersection_subset(self):
1175 result = self.set & set((2, 4))
1176 self.assertEqual(result, set((2, 4)))
1177
1178 def test_intersection_superset(self):
1179 result = self.set & set([2, 4, 6, 8])
1180 self.assertEqual(result, set([2, 4, 6]))
1181
1182 def test_intersection_overlap(self):
1183 result = self.set & set([3, 4, 5])
1184 self.assertEqual(result, set([4]))
1185
1186 def test_intersection_non_overlap(self):
1187 result = self.set & set([8])
1188 self.assertEqual(result, empty_set)
1189
1190 def test_isdisjoint_subset(self):
1191 result = self.set.isdisjoint(set((2, 4)))
1192 self.assertEqual(result, False)
1193
1194 def test_isdisjoint_superset(self):
1195 result = self.set.isdisjoint(set([2, 4, 6, 8]))
1196 self.assertEqual(result, False)
1197
1198 def test_isdisjoint_overlap(self):
1199 result = self.set.isdisjoint(set([3, 4, 5]))
1200 self.assertEqual(result, False)
1201
1202 def test_isdisjoint_non_overlap(self):
1203 result = self.set.isdisjoint(set([8]))
1204 self.assertEqual(result, True)
1205
1206 def test_sym_difference_subset(self):
1207 result = self.set ^ set((2, 4))
1208 self.assertEqual(result, set([6]))
1209
1210 def test_sym_difference_superset(self):
1211 result = self.set ^ set((2, 4, 6, 8))
1212 self.assertEqual(result, set([8]))
1213
1214 def test_sym_difference_overlap(self):
1215 result = self.set ^ set((3, 4, 5))
1216 self.assertEqual(result, set([2, 3, 5, 6]))
1217
1218 def test_sym_difference_non_overlap(self):
1219 result = self.set ^ set([8])
1220 self.assertEqual(result, set([2, 4, 6, 8]))
1221
1222 #==============================================================================
1223
1224 class TestUpdateOps(unittest.TestCase):
1225 def setUp(self):
1226 self.set = set((2, 4, 6))
1227
1228 def test_union_subset(self):
1229 self.set |= set([2])
1230 self.assertEqual(self.set, set((2, 4, 6)))
1231
1232 def test_union_superset(self):
1233 self.set |= set([2, 4, 6, 8])
1234 self.assertEqual(self.set, set([2, 4, 6, 8]))
1235
1236 def test_union_overlap(self):
1237 self.set |= set([3, 4, 5])
1238 self.assertEqual(self.set, set([2, 3, 4, 5, 6]))
1239
1240 def test_union_non_overlap(self):
1241 self.set |= set([8])
1242 self.assertEqual(self.set, set([2, 4, 6, 8]))
1243
1244 def test_union_method_call(self):
1245 self.set.update(set([3, 4, 5]))
1246 self.assertEqual(self.set, set([2, 3, 4, 5, 6]))
1247
1248 def test_intersection_subset(self):
1249 self.set &= set((2, 4))
1250 self.assertEqual(self.set, set((2, 4)))
1251
1252 def test_intersection_superset(self):
1253 self.set &= set([2, 4, 6, 8])
1254 self.assertEqual(self.set, set([2, 4, 6]))
1255
1256 def test_intersection_overlap(self):
1257 self.set &= set([3, 4, 5])
1258 self.assertEqual(self.set, set([4]))
1259
1260 def test_intersection_non_overlap(self):
1261 self.set &= set([8])
1262 self.assertEqual(self.set, empty_set)
1263
1264 def test_intersection_method_call(self):
1265 self.set.intersection_update(set([3, 4, 5]))
1266 self.assertEqual(self.set, set([4]))
1267
1268 def test_sym_difference_subset(self):
1269 self.set ^= set((2, 4))
1270 self.assertEqual(self.set, set([6]))
1271
1272 def test_sym_difference_superset(self):
1273 self.set ^= set((2, 4, 6, 8))
1274 self.assertEqual(self.set, set([8]))
1275
1276 def test_sym_difference_overlap(self):
1277 self.set ^= set((3, 4, 5))
1278 self.assertEqual(self.set, set([2, 3, 5, 6]))
1279
1280 def test_sym_difference_non_overlap(self):
1281 self.set ^= set([8])
1282 self.assertEqual(self.set, set([2, 4, 6, 8]))
1283
1284 def test_sym_difference_method_call(self):
1285 self.set.symmetric_difference_update(set([3, 4, 5]))
1286 self.assertEqual(self.set, set([2, 3, 5, 6]))
1287
1288 def test_difference_subset(self):
1289 self.set -= set((2, 4))
1290 self.assertEqual(self.set, set([6]))
1291
1292 def test_difference_superset(self):
1293 self.set -= set((2, 4, 6, 8))
1294 self.assertEqual(self.set, set([]))
1295
1296 def test_difference_overlap(self):
1297 self.set -= set((3, 4, 5))
1298 self.assertEqual(self.set, set([2, 6]))
1299
1300 def test_difference_non_overlap(self):
1301 self.set -= set([8])
1302 self.assertEqual(self.set, set([2, 4, 6]))
1303
1304 def test_difference_method_call(self):
1305 self.set.difference_update(set([3, 4, 5]))
1306 self.assertEqual(self.set, set([2, 6]))
1307
1308 #==============================================================================
1309
1310 class TestMutate(unittest.TestCase):
1311 def setUp(self):
1312 self.values = ["a", "b", "c"]
1313 self.set = set(self.values)
1314
1315 def test_add_present(self):
1316 self.set.add("c")
1317 self.assertEqual(self.set, set("abc"))
1318
1319 def test_add_absent(self):
1320 self.set.add("d")
1321 self.assertEqual(self.set, set("abcd"))
1322
1323 def test_add_until_full(self):
1324 tmp = set()
1325 expected_len = 0
1326 for v in self.values:
1327 tmp.add(v)
1328 expected_len += 1
1329 self.assertEqual(len(tmp), expected_len)
1330 self.assertEqual(tmp, self.set)
1331
1332 def test_remove_present(self):
1333 self.set.remove("b")
1334 self.assertEqual(self.set, set("ac"))
1335
1336 def test_remove_absent(self):
1337 try:
1338 self.set.remove("d")
1339 self.fail("Removing missing element should have raised LookupError")
1340 except LookupError:
1341 pass
1342
1343 def test_remove_until_empty(self):
1344 expected_len = len(self.set)
1345 for v in self.values:
1346 self.set.remove(v)
1347 expected_len -= 1
1348 self.assertEqual(len(self.set), expected_len)
1349
1350 def test_discard_present(self):
1351 self.set.discard("c")
1352 self.assertEqual(self.set, set("ab"))
1353
1354 def test_discard_absent(self):
1355 self.set.discard("d")
1356 self.assertEqual(self.set, set("abc"))
1357
1358 def test_clear(self):
1359 self.set.clear()
1360 self.assertEqual(len(self.set), 0)
1361
1362 def test_pop(self):
1363 popped = {}
1364 while self.set:
1365 popped[self.set.pop()] = None
1366 self.assertEqual(len(popped), len(self.values))
1367 for v in self.values:
1368 self.assertIn(v, popped)
1369
1370 def test_update_empty_tuple(self):
1371 self.set.update(())
1372 self.assertEqual(self.set, set(self.values))
1373
1374 def test_update_unit_tuple_overlap(self):
1375 self.set.update(("a",))
1376 self.assertEqual(self.set, set(self.values))
1377
1378 def test_update_unit_tuple_non_overlap(self):
1379 self.set.update(("a", "z"))
1380 self.assertEqual(self.set, set(self.values + ["z"]))
1381
1382 #==============================================================================
1383
1384 class TestSubsets:
1385
1386 case2method = {"<=": "issubset",
1387 ">=": "issuperset",
1388 }
1389
1390 reverse = {"==": "==",
1391 "!=": "!=",
1392 "<": ">",
1393 ">": "<",
1394 "<=": ">=",
1395 ">=": "<=",
1396 }
1397
1398 def test_issubset(self):
1399 x = self.left
1400 y = self.right
1401 for case in "!=", "==", "<", "<=", ">", ">=":
1402 expected = case in self.cases
1403 # Test the binary infix spelling.
1404 result = eval("x" + case + "y", locals())
1405 self.assertEqual(result, expected)
1406 # Test the "friendly" method-name spelling, if one exists.
1407 if case in TestSubsets.case2method:
1408 method = getattr(x, TestSubsets.case2method[case])
1409 result = method(y)
1410 self.assertEqual(result, expected)
1411
1412 # Now do the same for the operands reversed.
1413 rcase = TestSubsets.reverse[case]
1414 result = eval("y" + rcase + "x", locals())
1415 self.assertEqual(result, expected)
1416 if rcase in TestSubsets.case2method:
1417 method = getattr(y, TestSubsets.case2method[rcase])
1418 result = method(x)
1419 self.assertEqual(result, expected)
1420 #------------------------------------------------------------------------------
1421
1422 class TestSubsetEqualEmpty(TestSubsets, unittest.TestCase):
1423 left = set()
1424 right = set()
1425 name = "both empty"
1426 cases = "==", "<=", ">="
1427
1428 #------------------------------------------------------------------------------
1429
1430 class TestSubsetEqualNonEmpty(TestSubsets, unittest.TestCase):
1431 left = set([1, 2])
1432 right = set([1, 2])
1433 name = "equal pair"
1434 cases = "==", "<=", ">="
1435
1436 #------------------------------------------------------------------------------
1437
1438 class TestSubsetEmptyNonEmpty(TestSubsets, unittest.TestCase):
1439 left = set()
1440 right = set([1, 2])
1441 name = "one empty, one non-empty"
1442 cases = "!=", "<", "<="
1443
1444 #------------------------------------------------------------------------------
1445
1446 class TestSubsetPartial(TestSubsets, unittest.TestCase):
1447 left = set([1])
1448 right = set([1, 2])
1449 name = "one a non-empty proper subset of other"
1450 cases = "!=", "<", "<="
1451
1452 #------------------------------------------------------------------------------
1453
1454 class TestSubsetNonOverlap(TestSubsets, unittest.TestCase):
1455 left = set([1])
1456 right = set([2])
1457 name = "neither empty, neither contains"
1458 cases = "!="
1459
1460 #==============================================================================
1461
1462 class TestOnlySetsInBinaryOps:
1463
1464 def test_eq_ne(self):
1465 # Unlike the others, this is testing that == and != *are* allowed.
1466 self.assertEqual(self.other == self.set, False)
1467 self.assertEqual(self.set == self.other, False)
1468 self.assertEqual(self.other != self.set, True)
1469 self.assertEqual(self.set != self.other, True)
1470
1471 def test_ge_gt_le_lt(self):
1472 self.assertRaises(TypeError, lambda: self.set < self.other)
1473 self.assertRaises(TypeError, lambda: self.set <= self.other)
1474 self.assertRaises(TypeError, lambda: self.set > self.other)
1475 self.assertRaises(TypeError, lambda: self.set >= self.other)
1476
1477 self.assertRaises(TypeError, lambda: self.other < self.set)
1478 self.assertRaises(TypeError, lambda: self.other <= self.set)
1479 self.assertRaises(TypeError, lambda: self.other > self.set)
1480 self.assertRaises(TypeError, lambda: self.other >= self.set)
1481
1482 def test_update_operator(self):
1483 try:
1484 self.set |= self.other
1485 except TypeError:
1486 pass
1487 else:
1488 self.fail("expected TypeError")
1489
1490 def test_update(self):
1491 if self.otherIsIterable:
1492 self.set.update(self.other)
1493 else:
1494 self.assertRaises(TypeError, self.set.update, self.other)
1495
1496 def test_union(self):
1497 self.assertRaises(TypeError, lambda: self.set | self.other)
1498 self.assertRaises(TypeError, lambda: self.other | self.set)
1499 if self.otherIsIterable:
1500 self.set.union(self.other)
1501 else:
1502 self.assertRaises(TypeError, self.set.union, self.other)
1503
1504 def test_intersection_update_operator(self):
1505 try:
1506 self.set &= self.other
1507 except TypeError:
1508 pass
1509 else:
1510 self.fail("expected TypeError")
1511
1512 def test_intersection_update(self):
1513 if self.otherIsIterable:
1514 self.set.intersection_update(self.other)
1515 else:
1516 self.assertRaises(TypeError,
1517 self.set.intersection_update,
1518 self.other)
1519
1520 def test_intersection(self):
1521 self.assertRaises(TypeError, lambda: self.set & self.other)
1522 self.assertRaises(TypeError, lambda: self.other & self.set)
1523 if self.otherIsIterable:
1524 self.set.intersection(self.other)
1525 else:
1526 self.assertRaises(TypeError, self.set.intersection, self.other)
1527
1528 def test_sym_difference_update_operator(self):
1529 try:
1530 self.set ^= self.other
1531 except TypeError:
1532 pass
1533 else:
1534 self.fail("expected TypeError")
1535
1536 def test_sym_difference_update(self):
1537 if self.otherIsIterable:
1538 self.set.symmetric_difference_update(self.other)
1539 else:
1540 self.assertRaises(TypeError,
1541 self.set.symmetric_difference_update,
1542 self.other)
1543
1544 def test_sym_difference(self):
1545 self.assertRaises(TypeError, lambda: self.set ^ self.other)
1546 self.assertRaises(TypeError, lambda: self.other ^ self.set)
1547 if self.otherIsIterable:
1548 self.set.symmetric_difference(self.other)
1549 else:
1550 self.assertRaises(TypeError, self.set.symmetric_difference, self.other)
1551
1552 def test_difference_update_operator(self):
1553 try:
1554 self.set -= self.other
1555 except TypeError:
1556 pass
1557 else:
1558 self.fail("expected TypeError")
1559
1560 def test_difference_update(self):
1561 if self.otherIsIterable:
1562 self.set.difference_update(self.other)
1563 else:
1564 self.assertRaises(TypeError,
1565 self.set.difference_update,
1566 self.other)
1567
1568 def test_difference(self):
1569 self.assertRaises(TypeError, lambda: self.set - self.other)
1570 self.assertRaises(TypeError, lambda: self.other - self.set)
1571 if self.otherIsIterable:
1572 self.set.difference(self.other)
1573 else:
1574 self.assertRaises(TypeError, self.set.difference, self.other)
1575
1576 #------------------------------------------------------------------------------
1577
1578 class TestOnlySetsNumeric(TestOnlySetsInBinaryOps, unittest.TestCase):
1579 def setUp(self):
1580 self.set = set((1, 2, 3))
1581 self.other = 19
1582 self.otherIsIterable = False
1583
1584 #------------------------------------------------------------------------------
1585
1586 class TestOnlySetsDict(TestOnlySetsInBinaryOps, unittest.TestCase):
1587 def setUp(self):
1588 self.set = set((1, 2, 3))
1589 self.other = {1:2, 3:4}
1590 self.otherIsIterable = True
1591
1592 #------------------------------------------------------------------------------
1593
1594 class TestOnlySetsOperator(TestOnlySetsInBinaryOps, unittest.TestCase):
1595 def setUp(self):
1596 self.set = set((1, 2, 3))
1597 self.other = operator.add
1598 self.otherIsIterable = False
1599
1600 #------------------------------------------------------------------------------
1601
1602 class TestOnlySetsTuple(TestOnlySetsInBinaryOps, unittest.TestCase):
1603 def setUp(self):
1604 self.set = set((1, 2, 3))
1605 self.other = (2, 4, 6)
1606 self.otherIsIterable = True
1607
1608 #------------------------------------------------------------------------------
1609
1610 class TestOnlySetsString(TestOnlySetsInBinaryOps, unittest.TestCase):
1611 def setUp(self):
1612 self.set = set((1, 2, 3))
1613 self.other = 'abc'
1614 self.otherIsIterable = True
1615
1616 #------------------------------------------------------------------------------
1617
1618 class TestOnlySetsGenerator(TestOnlySetsInBinaryOps, unittest.TestCase):
1619 def setUp(self):
1620 def gen():
1621 for i in range(0, 10, 2):
1622 yield i
1623 self.set = set((1, 2, 3))
1624 self.other = gen()
1625 self.otherIsIterable = True
1626
1627 #==============================================================================
1628
1629 class TestCopying:
1630
1631 def test_copy(self):
1632 dup = self.set.copy()
1633 dup_list = sorted(dup, key=repr)
1634 set_list = sorted(self.set, key=repr)
1635 self.assertEqual(len(dup_list), len(set_list))
1636 for i in range(len(dup_list)):
1637 self.assertTrue(dup_list[i] is set_list[i])
1638
1639 def test_deep_copy(self):
1640 dup = copy.deepcopy(self.set)
1641 ##print type(dup), repr(dup)
1642 dup_list = sorted(dup, key=repr)
1643 set_list = sorted(self.set, key=repr)
1644 self.assertEqual(len(dup_list), len(set_list))
1645 for i in range(len(dup_list)):
1646 self.assertEqual(dup_list[i], set_list[i])
1647
1648 #------------------------------------------------------------------------------
1649
1650 class TestCopyingEmpty(TestCopying, unittest.TestCase):
1651 def setUp(self):
1652 self.set = set()
1653
1654 #------------------------------------------------------------------------------
1655
1656 class TestCopyingSingleton(TestCopying, unittest.TestCase):
1657 def setUp(self):
1658 self.set = set(["hello"])
1659
1660 #------------------------------------------------------------------------------
1661
1662 class TestCopyingTriple(TestCopying, unittest.TestCase):
1663 def setUp(self):
1664 self.set = set(["zero", 0, None])
1665
1666 #------------------------------------------------------------------------------
1667
1668 class TestCopyingTuple(TestCopying, unittest.TestCase):
1669 def setUp(self):
1670 self.set = set([(1, 2)])
1671
1672 #------------------------------------------------------------------------------
1673
1674 class TestCopyingNested(TestCopying, unittest.TestCase):
1675 def setUp(self):
1676 self.set = set([((1, 2), (3, 4))])
1677
1678 #==============================================================================
1679
1680 class TestIdentities(unittest.TestCase):
1681 def setUp(self):
1682 self.a = set('abracadabra')
1683 self.b = set('alacazam')
1684
1685 def test_binopsVsSubsets(self):
1686 a, b = self.a, self.b
1687 self.assertTrue(a - b < a)
1688 self.assertTrue(b - a < b)
1689 self.assertTrue(a & b < a)
1690 self.assertTrue(a & b < b)
1691 self.assertTrue(a | b > a)
1692 self.assertTrue(a | b > b)
1693 self.assertTrue(a ^ b < a | b)
1694
1695 def test_commutativity(self):
1696 a, b = self.a, self.b
1697 self.assertEqual(a&b, b&a)
1698 self.assertEqual(a|b, b|a)
1699 self.assertEqual(a^b, b^a)
1700 if a != b:
1701 self.assertNotEqual(a-b, b-a)
1702
1703 def test_summations(self):
1704 # check that sums of parts equal the whole
1705 a, b = self.a, self.b
1706 self.assertEqual((a-b)|(a&b)|(b-a), a|b)
1707 self.assertEqual((a&b)|(a^b), a|b)
1708 self.assertEqual(a|(b-a), a|b)
1709 self.assertEqual((a-b)|b, a|b)
1710 self.assertEqual((a-b)|(a&b), a)
1711 self.assertEqual((b-a)|(a&b), b)
1712 self.assertEqual((a-b)|(b-a), a^b)
1713
1714 def test_exclusion(self):
1715 # check that inverse operations show non-overlap
1716 a, b, zero = self.a, self.b, set()
1717 self.assertEqual((a-b)&b, zero)
1718 self.assertEqual((b-a)&a, zero)
1719 self.assertEqual((a&b)&(a^b), zero)
1720
1721 # Tests derived from test_itertools.py =======================================
1722
1723 def R(seqn):
1724 'Regular generator'
1725 for i in seqn:
1726 yield i
1727
1728 class G:
1729 'Sequence using __getitem__'
1730 def __init__(self, seqn):
1731 self.seqn = seqn
1732 def __getitem__(self, i):
1733 return self.seqn[i]
1734
1735 class I:
1736 'Sequence using iterator protocol'
1737 def __init__(self, seqn):
1738 self.seqn = seqn
1739 self.i = 0
1740 def __iter__(self):
1741 return self
1742 def __next__(self):
1743 if self.i >= len(self.seqn): raise StopIteration
1744 v = self.seqn[self.i]
1745 self.i += 1
1746 return v
1747
1748 class Ig:
1749 'Sequence using iterator protocol defined with a generator'
1750 def __init__(self, seqn):
1751 self.seqn = seqn
1752 self.i = 0
1753 def __iter__(self):
1754 for val in self.seqn:
1755 yield val
1756
1757 class X:
1758 'Missing __getitem__ and __iter__'
1759 def __init__(self, seqn):
1760 self.seqn = seqn
1761 self.i = 0
1762 def __next__(self):
1763 if self.i >= len(self.seqn): raise StopIteration
1764 v = self.seqn[self.i]
1765 self.i += 1
1766 return v
1767
1768 class N:
1769 'Iterator missing __next__()'
1770 def __init__(self, seqn):
1771 self.seqn = seqn
1772 self.i = 0
1773 def __iter__(self):
1774 return self
1775
1776 class E:
1777 'Test propagation of exceptions'
1778 def __init__(self, seqn):
1779 self.seqn = seqn
1780 self.i = 0
1781 def __iter__(self):
1782 return self
1783 def __next__(self):
1784 3 // 0
1785
1786 class S:
1787 'Test immediate stop'
1788 def __init__(self, seqn):
1789 pass
1790 def __iter__(self):
1791 return self
1792 def __next__(self):
1793 raise StopIteration
1794
1795 from itertools import chain
1796 def L(seqn):
1797 'Test multiple tiers of iterators'
1798 return chain(map(lambda x:x, R(Ig(G(seqn)))))
1799
1800 class TestVariousIteratorArgs(unittest.TestCase):
1801
1802 def test_constructor(self):
1803 for cons in (set, frozenset):
1804 for s in ("123", "", range(1000), ('do', 1.2), range(2000,2200,5)):
1805 for g in (G, I, Ig, S, L, R):
1806 self.assertEqual(sorted(cons(g(s)), key=repr), sorted(g(s), key=repr))
1807 self.assertRaises(TypeError, cons , X(s))
1808 self.assertRaises(TypeError, cons , N(s))
1809 self.assertRaises(ZeroDivisionError, cons , E(s))
1810
1811 def test_inline_methods(self):
1812 s = set('november')
1813 for data in ("123", "", range(1000), ('do', 1.2), range(2000,2200,5), 'december'):
1814 for meth in (s.union, s.intersection, s.difference, s.symmetric_difference, s.isdisjoint):
1815 for g in (G, I, Ig, L, R):
1816 expected = meth(data)
1817 actual = meth(g(data))
1818 if isinstance(expected, bool):
1819 self.assertEqual(actual, expected)
1820 else:
1821 self.assertEqual(sorted(actual, key=repr), sorted(expected, key=repr))
1822 self.assertRaises(TypeError, meth, X(s))
1823 self.assertRaises(TypeError, meth, N(s))
1824 self.assertRaises(ZeroDivisionError, meth, E(s))
1825
1826 def test_inplace_methods(self):
1827 for data in ("123", "", range(1000), ('do', 1.2), range(2000,2200,5), 'december'):
1828 for methname in ('update', 'intersection_update',
1829 'difference_update', 'symmetric_difference_update'):
1830 for g in (G, I, Ig, S, L, R):
1831 s = set('january')
1832 t = s.copy()
1833 getattr(s, methname)(list(g(data)))
1834 getattr(t, methname)(g(data))
1835 self.assertEqual(sorted(s, key=repr), sorted(t, key=repr))
1836
1837 self.assertRaises(TypeError, getattr(set('january'), methname), X(data))
1838 self.assertRaises(TypeError, getattr(set('january'), methname), N(data))
1839 self.assertRaises(ZeroDivisionError, getattr(set('january'), methname), E(data))
1840
1841 class bad_eq:
1842 def __eq__(self, other):
1843 if be_bad:
1844 set2.clear()
1845 raise ZeroDivisionError
1846 return self is other
1847 def __hash__(self):
1848 return 0
1849
1850 class bad_dict_clear:
1851 def __eq__(self, other):
1852 if be_bad:
1853 dict2.clear()
1854 return self is other
1855 def __hash__(self):
1856 return 0
1857
1858 class TestWeirdBugs(unittest.TestCase):
1859 def test_8420_set_merge(self):
1860 # This used to segfault
1861 global be_bad, set2, dict2
1862 be_bad = False
1863 set1 = {bad_eq()}
1864 set2 = {bad_eq() for i in range(75)}
1865 be_bad = True
1866 self.assertRaises(ZeroDivisionError, set1.update, set2)
1867
1868 be_bad = False
1869 set1 = {bad_dict_clear()}
1870 dict2 = {bad_dict_clear(): None}
1871 be_bad = True
1872 set1.symmetric_difference_update(dict2)
1873
1874 def test_iter_and_mutate(self):
1875 # Issue #24581
1876 s = set(range(100))
1877 s.clear()
1878 s.update(range(100))
1879 si = iter(s)
1880 s.clear()
1881 a = list(range(100))
1882 s.update(range(100))
1883 list(si)
1884
1885 def test_merge_and_mutate(self):
1886 # gh-141805
1887 class X:
1888 def __hash__(self):
1889 return hash(0)
1890 def __eq__(self, o):
1891 other.clear()
1892 return False
1893
1894 other = set()
1895 other = {X() for i in range(10)}
1896 s = {0}
1897 s.update(other)
1898
1899 def test_hash_collision_concurrent_add(self):
1900 class X:
1901 def __hash__(self):
1902 return 0
1903 class Y:
1904 flag = False
1905 def __hash__(self):
1906 return 0
1907 def __eq__(self, other):
1908 if not self.flag:
1909 self.flag = True
1910 s.add(X())
1911 return self is other
1912
1913 a = X()
1914 s = set()
1915 s.add(a)
1916 s.add(X())
1917 s.remove(a)
1918 # Now the set contains a dummy entry followed by an entry
1919 # for an object with hash 0.
1920 s.add(Y())
1921 # The following operations should not crash.
1922 repr(s)
1923 list(s)
1924 set() | s
1925
1926
1927 class TestOperationsMutating:
1928 """Regression test for bpo-46615"""
1929
1930 constructor1 = None
1931 constructor2 = None
1932
1933 def make_sets_of_bad_objects(self):
1934 class Bad:
1935 def __eq__(self, other):
1936 if not enabled:
1937 return False
1938 if randrange(20) == 0:
1939 set1.clear()
1940 if randrange(20) == 0:
1941 set2.clear()
1942 return bool(randrange(2))
1943 def __hash__(self):
1944 return randrange(2)
1945 # Don't behave poorly during construction.
1946 enabled = False
1947 set1 = self.constructor1(Bad() for _ in range(randrange(50)))
1948 set2 = self.constructor2(Bad() for _ in range(randrange(50)))
1949 # Now start behaving poorly
1950 enabled = True
1951 return set1, set2
1952
1953 def check_set_op_does_not_crash(self, function):
1954 for _ in range(100):
1955 set1, set2 = self.make_sets_of_bad_objects()
1956 try:
1957 function(set1, set2)
1958 except RuntimeError as e:
1959 # Just make sure we don't crash here.
1960 self.assertIn("changed size during iteration", str(e))
1961
1962
1963 class TestBinaryOpsMutating(TestOperationsMutating):
1964
1965 def test_eq_with_mutation(self):
1966 self.check_set_op_does_not_crash(lambda a, b: a == b)
1967
1968 def test_ne_with_mutation(self):
1969 self.check_set_op_does_not_crash(lambda a, b: a != b)
1970
1971 def test_lt_with_mutation(self):
1972 self.check_set_op_does_not_crash(lambda a, b: a < b)
1973
1974 def test_le_with_mutation(self):
1975 self.check_set_op_does_not_crash(lambda a, b: a <= b)
1976
1977 def test_gt_with_mutation(self):
1978 self.check_set_op_does_not_crash(lambda a, b: a > b)
1979
1980 def test_ge_with_mutation(self):
1981 self.check_set_op_does_not_crash(lambda a, b: a >= b)
1982
1983 def test_and_with_mutation(self):
1984 self.check_set_op_does_not_crash(lambda a, b: a & b)
1985
1986 def test_or_with_mutation(self):
1987 self.check_set_op_does_not_crash(lambda a, b: a | b)
1988
1989 def test_sub_with_mutation(self):
1990 self.check_set_op_does_not_crash(lambda a, b: a - b)
1991
1992 def test_xor_with_mutation(self):
1993 self.check_set_op_does_not_crash(lambda a, b: a ^ b)
1994
1995 def test_iadd_with_mutation(self):
1996 def f(a, b):
1997 a &= b
1998 self.check_set_op_does_not_crash(f)
1999
2000 def test_ior_with_mutation(self):
2001 def f(a, b):
2002 a |= b
2003 self.check_set_op_does_not_crash(f)
2004
2005 def test_isub_with_mutation(self):
2006 def f(a, b):
2007 a -= b
2008 self.check_set_op_does_not_crash(f)
2009
2010 def test_ixor_with_mutation(self):
2011 def f(a, b):
2012 a ^= b
2013 self.check_set_op_does_not_crash(f)
2014
2015 def test_iteration_with_mutation(self):
2016 def f1(a, b):
2017 for x in a:
2018 pass
2019 for y in b:
2020 pass
2021 def f2(a, b):
2022 for y in b:
2023 pass
2024 for x in a:
2025 pass
2026 def f3(a, b):
2027 for x, y in zip(a, b):
2028 pass
2029 self.check_set_op_does_not_crash(f1)
2030 self.check_set_op_does_not_crash(f2)
2031 self.check_set_op_does_not_crash(f3)
2032
2033
2034 class TestBinaryOpsMutating_Set_Set(TestBinaryOpsMutating, unittest.TestCase):
2035 constructor1 = set
2036 constructor2 = set
2037
2038 class TestBinaryOpsMutating_Subclass_Subclass(TestBinaryOpsMutating, unittest.TestCase):
2039 constructor1 = SetSubclass
2040 constructor2 = SetSubclass
2041
2042 class TestBinaryOpsMutating_Set_Subclass(TestBinaryOpsMutating, unittest.TestCase):
2043 constructor1 = set
2044 constructor2 = SetSubclass
2045
2046 class TestBinaryOpsMutating_Subclass_Set(TestBinaryOpsMutating, unittest.TestCase):
2047 constructor1 = SetSubclass
2048 constructor2 = set
2049
2050
2051 class TestMethodsMutating(TestOperationsMutating):
2052
2053 def test_issubset_with_mutation(self):
2054 self.check_set_op_does_not_crash(set.issubset)
2055
2056 def test_issuperset_with_mutation(self):
2057 self.check_set_op_does_not_crash(set.issuperset)
2058
2059 def test_intersection_with_mutation(self):
2060 self.check_set_op_does_not_crash(set.intersection)
2061
2062 def test_union_with_mutation(self):
2063 self.check_set_op_does_not_crash(set.union)
2064
2065 def test_difference_with_mutation(self):
2066 self.check_set_op_does_not_crash(set.difference)
2067
2068 def test_symmetric_difference_with_mutation(self):
2069 self.check_set_op_does_not_crash(set.symmetric_difference)
2070
2071 def test_isdisjoint_with_mutation(self):
2072 self.check_set_op_does_not_crash(set.isdisjoint)
2073
2074 def test_difference_update_with_mutation(self):
2075 self.check_set_op_does_not_crash(set.difference_update)
2076
2077 def test_intersection_update_with_mutation(self):
2078 self.check_set_op_does_not_crash(set.intersection_update)
2079
2080 def test_symmetric_difference_update_with_mutation(self):
2081 self.check_set_op_does_not_crash(set.symmetric_difference_update)
2082
2083 def test_update_with_mutation(self):
2084 self.check_set_op_does_not_crash(set.update)
2085
2086
2087 class TestMethodsMutating_Set_Set(TestMethodsMutating, unittest.TestCase):
2088 constructor1 = set
2089 constructor2 = set
2090
2091 class TestMethodsMutating_Subclass_Subclass(TestMethodsMutating, unittest.TestCase):
2092 constructor1 = SetSubclass
2093 constructor2 = SetSubclass
2094
2095 class TestMethodsMutating_Set_Subclass(TestMethodsMutating, unittest.TestCase):
2096 constructor1 = set
2097 constructor2 = SetSubclass
2098
2099 class TestMethodsMutating_Subclass_Set(TestMethodsMutating, unittest.TestCase):
2100 constructor1 = SetSubclass
2101 constructor2 = set
2102
2103 class TestMethodsMutating_Set_Dict(TestMethodsMutating, unittest.TestCase):
2104 constructor1 = set
2105 constructor2 = dict.fromkeys
2106
2107 class TestMethodsMutating_Set_List(TestMethodsMutating, unittest.TestCase):
2108 constructor1 = set
2109 constructor2 = list
2110
2111
2112 # Application tests (based on David Eppstein's graph recipes ====================================
2113
2114 def powerset(U):
2115 """Generates all subsets of a set or sequence U."""
2116 U = iter(U)
2117 try:
2118 x = frozenset([next(U)])
2119 for S in powerset(U):
2120 yield S
2121 yield S | x
2122 except StopIteration:
2123 yield frozenset()
2124
2125 def cube(n):
2126 """Graph of n-dimensional hypercube."""
2127 singletons = [frozenset([x]) for x in range(n)]
2128 return dict([(x, frozenset([x^s for s in singletons]))
2129 for x in powerset(range(n))])
2130
2131 def linegraph(G):
2132 """Graph, the vertices of which are edges of G,
2133 with two vertices being adjacent iff the corresponding
2134 edges share a vertex."""
2135 L = {}
2136 for x in G:
2137 for y in G[x]:
2138 nx = [frozenset([x,z]) for z in G[x] if z != y]
2139 ny = [frozenset([y,z]) for z in G[y] if z != x]
2140 L[frozenset([x,y])] = frozenset(nx+ny)
2141 return L
2142
2143 def faces(G):
2144 'Return a set of faces in G. Where a face is a set of vertices on that face'
2145 # currently limited to triangles,squares, and pentagons
2146 f = set()
2147 for v1, edges in G.items():
2148 for v2 in edges:
2149 for v3 in G[v2]:
2150 if v1 == v3:
2151 continue
2152 if v1 in G[v3]:
2153 f.add(frozenset([v1, v2, v3]))
2154 else:
2155 for v4 in G[v3]:
2156 if v4 == v2:
2157 continue
2158 if v1 in G[v4]:
2159 f.add(frozenset([v1, v2, v3, v4]))
2160 else:
2161 for v5 in G[v4]:
2162 if v5 == v3 or v5 == v2:
2163 continue
2164 if v1 in G[v5]:
2165 f.add(frozenset([v1, v2, v3, v4, v5]))
2166 return f
2167
2168
2169 class TestGraphs(unittest.TestCase):
2170
2171 def test_cube(self):
2172
2173 g = cube(3) # vert --> {v1, v2, v3}
2174 vertices1 = set(g)
2175 self.assertEqual(len(vertices1), 8) # eight vertices
2176 for edge in g.values():
2177 self.assertEqual(len(edge), 3) # each vertex connects to three edges
2178 vertices2 = set(v for edges in g.values() for v in edges)
2179 self.assertEqual(vertices1, vertices2) # edge vertices in original set
2180
2181 cubefaces = faces(g)
2182 self.assertEqual(len(cubefaces), 6) # six faces
2183 for face in cubefaces:
2184 self.assertEqual(len(face), 4) # each face is a square
2185
2186 def test_cuboctahedron(self):
2187
2188 # http://en.wikipedia.org/wiki/Cuboctahedron
2189 # 8 triangular faces and 6 square faces
2190 # 12 identical vertices each connecting a triangle and square
2191
2192 g = cube(3)
2193 cuboctahedron = linegraph(g) # V( --> {V1, V2, V3, V4}
2194 self.assertEqual(len(cuboctahedron), 12)# twelve vertices
2195
2196 vertices = set(cuboctahedron)
2197 for edges in cuboctahedron.values():
2198 self.assertEqual(len(edges), 4) # each vertex connects to four other vertices
2199 othervertices = set(edge for edges in cuboctahedron.values() for edge in edges)
2200 self.assertEqual(vertices, othervertices) # edge vertices in original set
2201
2202 cubofaces = faces(cuboctahedron)
2203 facesizes = collections.defaultdict(int)
2204 for face in cubofaces:
2205 facesizes[len(face)] += 1
2206 self.assertEqual(facesizes[3], 8) # eight triangular faces
2207 self.assertEqual(facesizes[4], 6) # six square faces
2208
2209 for vertex in cuboctahedron:
2210 edge = vertex # Cuboctahedron vertices are edges in Cube
2211 self.assertEqual(len(edge), 2) # Two cube vertices define an edge
2212 for cubevert in edge:
2213 self.assertIn(cubevert, g)
2214
2215
2216 #==============================================================================
2217
2218 if __name__ == "__main__":
2219 unittest.main()