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