Lib/test/test_set.py

   1
   2 import unittest
   3 from test import test_support
   4 import gc
   5 import weakref
   6 import operator
   7 import copy
   8 import pickle
   9 from random import randrange, shuffle
  10 import sys
  11 import collections
  12
  13 class PassThru(Exception):
  14     pass
  15
  16 def check_pass_thru():
  17     raise PassThru
  18     yield 1
  19
  20 class BadCmp:
  21     def __hash__(self):
  22         return 1
  23     def __cmp__(self, other):
  24         raise RuntimeError
  25
  26 class ReprWrapper:
  27     'Used to test self-referential repr() calls'
  28     def __repr__(self):
  29         return repr(self.value)
  30
  31 class HashCountingInt(int):
  32     'int-like object that counts the number of times __hash__ is called'
  33     def __init__(self, *args):
  34         self.hash_count = 0
  35     def __hash__(self):
  36         self.hash_count += 1
  37         return int.__hash__(self)
  38
  39 class TestJointOps(unittest.TestCase):
  40     # Tests common to both set and frozenset
  41
  42     def setUp(self):
  43         self.word = word = 'simsalabim'
  44         self.otherword = 'madagascar'
  45         self.letters = 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ'
  46         self.s = self.thetype(word)
  47         self.d = dict.fromkeys(word)
  48
  49     def test_new_or_init(self):
  50         self.assertRaises(TypeError, self.thetype, [], 2)
  51         self.assertRaises(TypeError, set().__init__, a=1)
  52
  53     def test_uniquification(self):
  54         actual = sorted(self.s)
  55         expected = sorted(self.d)
  56         self.assertEqual(actual, expected)
  57         self.assertRaises(PassThru, self.thetype, check_pass_thru())
  58         self.assertRaises(TypeError, self.thetype, [[]])
  59
  60     def test_len(self):
  61         self.assertEqual(len(self.s), len(self.d))
  62
  63     def test_contains(self):
  64         for c in self.letters:
  65             self.assertEqual(c in self.s, c in self.d)
  66         self.assertRaises(TypeError, self.s.__contains__, [[]])
  67         s = self.thetype([frozenset(self.letters)])
  68         self.assertIn(self.thetype(self.letters), s)
  69
  70     def test_union(self):
  71         u = self.s.union(self.otherword)
  72         for c in self.letters:
  73             self.assertEqual(c in u, c in self.d or c in self.otherword)
  74         self.assertEqual(self.s, self.thetype(self.word))
  75         self.assertEqual(type(u), self.thetype)
  76         self.assertRaises(PassThru, self.s.union, check_pass_thru())
  77         self.assertRaises(TypeError, self.s.union, [[]])
  78         for C in set, frozenset, dict.fromkeys, str, unicode, list, tuple:
  79             self.assertEqual(self.thetype('abcba').union(C('cdc')), set('abcd'))
  80             self.assertEqual(self.thetype('abcba').union(C('efgfe')), set('abcefg'))
  81             self.assertEqual(self.thetype('abcba').union(C('ccb')), set('abc'))
  82             self.assertEqual(self.thetype('abcba').union(C('ef')), set('abcef'))
  83             self.assertEqual(self.thetype('abcba').union(C('ef'), C('fg')), set('abcefg'))
  84
  85         # Issue #6573
  86         x = self.thetype()
  87         self.assertEqual(x.union(set([1]), x, set([2])), self.thetype([1, 2]))
  88
  89     def test_or(self):
  90         i = self.s.union(self.otherword)
  91         self.assertEqual(self.s | set(self.otherword), i)
  92         self.assertEqual(self.s | frozenset(self.otherword), i)
  93         try:
  94             self.s | self.otherword
  95         except TypeError:
  96             pass
  97         else:
  98             self.fail("s|t did not screen-out general iterables")
  99
 100     def test_intersection(self):
 101         i = self.s.intersection(self.otherword)
 102         for c in self.letters:
 103             self.assertEqual(c in i, c in self.d and c in self.otherword)
 104         self.assertEqual(self.s, self.thetype(self.word))
 105         self.assertEqual(type(i), self.thetype)
 106         self.assertRaises(PassThru, self.s.intersection, check_pass_thru())
 107         for C in set, frozenset, dict.fromkeys, str, unicode, list, tuple:
 108             self.assertEqual(self.thetype('abcba').intersection(C('cdc')), set('cc'))
 109             self.assertEqual(self.thetype('abcba').intersection(C('efgfe')), set(''))
 110             self.assertEqual(self.thetype('abcba').intersection(C('ccb')), set('bc'))
 111             self.assertEqual(self.thetype('abcba').intersection(C('ef')), set(''))
 112             self.assertEqual(self.thetype('abcba').intersection(C('cbcf'), C('bag')), set('b'))
 113         s = self.thetype('abcba')
 114         z = s.intersection()
 115         if self.thetype == frozenset():
 116             self.assertEqual(id(s), id(z))
 117         else:
 118             self.assertNotEqual(id(s), id(z))
 119
 120     def test_isdisjoint(self):
 121         def f(s1, s2):
 122             'Pure python equivalent of isdisjoint()'
 123             return not set(s1).intersection(s2)
 124         for larg in '', 'a', 'ab', 'abc', 'ababac', 'cdc', 'cc', 'efgfe', 'ccb', 'ef':
 125             s1 = self.thetype(larg)
 126             for rarg in '', 'a', 'ab', 'abc', 'ababac', 'cdc', 'cc', 'efgfe', 'ccb', 'ef':
 127                 for C in set, frozenset, dict.fromkeys, str, unicode, list, tuple:
 128                     s2 = C(rarg)
 129                     actual = s1.isdisjoint(s2)
 130                     expected = f(s1, s2)
 131                     self.assertEqual(actual, expected)
 132                     self.assertTrue(actual is True or actual is False)
 133
 134     def test_and(self):
 135         i = self.s.intersection(self.otherword)
 136         self.assertEqual(self.s & set(self.otherword), i)
 137         self.assertEqual(self.s & frozenset(self.otherword), i)
 138         try:
 139             self.s & self.otherword
 140         except TypeError:
 141             pass
 142         else:
 143             self.fail("s&t did not screen-out general iterables")
 144
 145     def test_difference(self):
 146         i = self.s.difference(self.otherword)
 147         for c in self.letters:
 148             self.assertEqual(c in i, c in self.d and c not in self.otherword)
 149         self.assertEqual(self.s, self.thetype(self.word))
 150         self.assertEqual(type(i), self.thetype)
 151         self.assertRaises(PassThru, self.s.difference, check_pass_thru())
 152         self.assertRaises(TypeError, self.s.difference, [[]])
 153         for C in set, frozenset, dict.fromkeys, str, unicode, list, tuple:
 154             self.assertEqual(self.thetype('abcba').difference(C('cdc')), set('ab'))
 155             self.assertEqual(self.thetype('abcba').difference(C('efgfe')), set('abc'))
 156             self.assertEqual(self.thetype('abcba').difference(C('ccb')), set('a'))
 157             self.assertEqual(self.thetype('abcba').difference(C('ef')), set('abc'))
 158             self.assertEqual(self.thetype('abcba').difference(), set('abc'))
 159             self.assertEqual(self.thetype('abcba').difference(C('a'), C('b')), set('c'))
 160
 161     def test_sub(self):
 162         i = self.s.difference(self.otherword)
 163         self.assertEqual(self.s - set(self.otherword), i)
 164         self.assertEqual(self.s - frozenset(self.otherword), i)
 165         try:
 166             self.s - self.otherword
 167         except TypeError:
 168             pass
 169         else:
 170             self.fail("s-t did not screen-out general iterables")
 171
 172     def test_symmetric_difference(self):
 173         i = self.s.symmetric_difference(self.otherword)
 174         for c in self.letters:
 175             self.assertEqual(c in i, (c in self.d) ^ (c in self.otherword))
 176         self.assertEqual(self.s, self.thetype(self.word))
 177         self.assertEqual(type(i), self.thetype)
 178         self.assertRaises(PassThru, self.s.symmetric_difference, check_pass_thru())
 179         self.assertRaises(TypeError, self.s.symmetric_difference, [[]])
 180         for C in set, frozenset, dict.fromkeys, str, unicode, list, tuple:
 181             self.assertEqual(self.thetype('abcba').symmetric_difference(C('cdc')), set('abd'))
 182             self.assertEqual(self.thetype('abcba').symmetric_difference(C('efgfe')), set('abcefg'))
 183             self.assertEqual(self.thetype('abcba').symmetric_difference(C('ccb')), set('a'))
 184             self.assertEqual(self.thetype('abcba').symmetric_difference(C('ef')), set('abcef'))
 185
 186     def test_xor(self):
 187         i = self.s.symmetric_difference(self.otherword)
 188         self.assertEqual(self.s ^ set(self.otherword), i)
 189         self.assertEqual(self.s ^ frozenset(self.otherword), i)
 190         try:
 191             self.s ^ self.otherword
 192         except TypeError:
 193             pass
 194         else:
 195             self.fail("s^t did not screen-out general iterables")
 196
 197     def test_equality(self):
 198         self.assertEqual(self.s, set(self.word))
 199         self.assertEqual(self.s, frozenset(self.word))
 200         self.assertEqual(self.s == self.word, False)
 201         self.assertNotEqual(self.s, set(self.otherword))
 202         self.assertNotEqual(self.s, frozenset(self.otherword))
 203         self.assertEqual(self.s != self.word, True)
 204
 205     def test_setOfFrozensets(self):
 206         t = map(frozenset, ['abcdef', 'bcd', 'bdcb', 'fed', 'fedccba'])
 207         s = self.thetype(t)
 208         self.assertEqual(len(s), 3)
 209
 210     def test_compare(self):
 211         self.assertRaises(TypeError, self.s.__cmp__, self.s)
 212
 213     def test_sub_and_super(self):
 214         p, q, r = map(self.thetype, ['ab', 'abcde', 'def'])
 215         self.assertTrue(p < q)
 216         self.assertTrue(p <= q)
 217         self.assertTrue(q <= q)
 218         self.assertTrue(q > p)
 219         self.assertTrue(q >= p)
 220         self.assertFalse(q < r)
 221         self.assertFalse(q <= r)
 222         self.assertFalse(q > r)
 223         self.assertFalse(q >= r)
 224         self.assertTrue(set('a').issubset('abc'))
 225         self.assertTrue(set('abc').issuperset('a'))
 226         self.assertFalse(set('a').issubset('cbs'))
 227         self.assertFalse(set('cbs').issuperset('a'))
 228
 229     def test_pickling(self):
 230         for i in range(pickle.HIGHEST_PROTOCOL + 1):
 231             p = pickle.dumps(self.s, i)
 232             dup = pickle.loads(p)
 233             self.assertEqual(self.s, dup, "%s != %s" % (self.s, dup))
 234             if type(self.s) not in (set, frozenset):
 235                 self.s.x = 10
 236                 p = pickle.dumps(self.s)
 237                 dup = pickle.loads(p)
 238                 self.assertEqual(self.s.x, dup.x)
 239
 240     def test_deepcopy(self):
 241         class Tracer:
 242             def __init__(self, value):
 243                 self.value = value
 244             def __hash__(self):
 245                 return self.value
 246             def __deepcopy__(self, memo=None):
 247                 return Tracer(self.value + 1)
 248         t = Tracer(10)
 249         s = self.thetype([t])
 250         dup = copy.deepcopy(s)
 251         self.assertNotEqual(id(s), id(dup))
 252         for elem in dup:
 253             newt = elem
 254         self.assertNotEqual(id(t), id(newt))
 255         self.assertEqual(t.value + 1, newt.value)
 256
 257     def test_gc(self):
 258         # Create a nest of cycles to exercise overall ref count check
 259         class A:
 260             pass
 261         s = set(A() for i in xrange(1000))
 262         for elem in s:
 263             elem.cycle = s
 264             elem.sub = elem
 265             elem.set = set([elem])
 266
 267     def test_subclass_with_custom_hash(self):
 268         # Bug #1257731
 269         class H(self.thetype):
 270             def __hash__(self):
 271                 return int(id(self) & 0x7fffffff)
 272         s=H()
 273         f=set()
 274         f.add(s)
 275         self.assertIn(s, f)
 276         f.remove(s)
 277         f.add(s)
 278         f.discard(s)
 279
 280     def test_badcmp(self):
 281         s = self.thetype([BadCmp()])
 282         # Detect comparison errors during insertion and lookup
 283         self.assertRaises(RuntimeError, self.thetype, [BadCmp(), BadCmp()])
 284         self.assertRaises(RuntimeError, s.__contains__, BadCmp())
 285         # Detect errors during mutating operations
 286         if hasattr(s, 'add'):
 287             self.assertRaises(RuntimeError, s.add, BadCmp())
 288             self.assertRaises(RuntimeError, s.discard, BadCmp())
 289             self.assertRaises(RuntimeError, s.remove, BadCmp())
 290
 291     def test_cyclical_repr(self):
 292         w = ReprWrapper()
 293         s = self.thetype([w])
 294         w.value = s
 295         name = repr(s).partition('(')[0]    # strip class name from repr string
 296         self.assertEqual(repr(s), '%s([%s(...)])' % (name, name))
 297
 298     def test_cyclical_print(self):
 299         w = ReprWrapper()
 300         s = self.thetype([w])
 301         w.value = s
 302         fo = open(test_support.TESTFN, "wb")
 303         try:
 304             print >> fo, s,
 305             fo.close()
 306             fo = open(test_support.TESTFN, "rb")
 307             self.assertEqual(fo.read(), repr(s))
 308         finally:
 309             fo.close()
 310             test_support.unlink(test_support.TESTFN)
 311
 312     def test_do_not_rehash_dict_keys(self):
 313         n = 10
 314         d = dict.fromkeys(map(HashCountingInt, xrange(n)))
 315         self.assertEqual(sum(elem.hash_count for elem in d), n)
 316         s = self.thetype(d)
 317         self.assertEqual(sum(elem.hash_count for elem in d), n)
 318         s.difference(d)
 319         self.assertEqual(sum(elem.hash_count for elem in d), n)
 320         if hasattr(s, 'symmetric_difference_update'):
 321             s.symmetric_difference_update(d)
 322         self.assertEqual(sum(elem.hash_count for elem in d), n)
 323         d2 = dict.fromkeys(set(d))
 324         self.assertEqual(sum(elem.hash_count for elem in d), n)
 325         d3 = dict.fromkeys(frozenset(d))
 326         self.assertEqual(sum(elem.hash_count for elem in d), n)
 327         d3 = dict.fromkeys(frozenset(d), 123)
 328         self.assertEqual(sum(elem.hash_count for elem in d), n)
 329         self.assertEqual(d3, dict.fromkeys(d, 123))
 330
 331     def test_container_iterator(self):
 332         # Bug #3680: tp_traverse was not implemented for set iterator object
 333         class C(object):
 334             pass
 335         obj = C()
 336         ref = weakref.ref(obj)
 337         container = set([obj, 1])
 338         obj.x = iter(container)
 339         del obj, container
 340         gc.collect()
 341         self.assertTrue(ref() is None, "Cycle was not collected")
 342
 343 class TestSet(TestJointOps):
 344     thetype = set
 345
 346     def test_init(self):
 347         s = self.thetype()
 348         s.__init__(self.word)
 349         self.assertEqual(s, set(self.word))
 350         s.__init__(self.otherword)
 351         self.assertEqual(s, set(self.otherword))
 352         self.assertRaises(TypeError, s.__init__, s, 2);
 353         self.assertRaises(TypeError, s.__init__, 1);
 354
 355     def test_constructor_identity(self):
 356         s = self.thetype(range(3))
 357         t = self.thetype(s)
 358         self.assertNotEqual(id(s), id(t))
 359
 360     def test_hash(self):
 361         self.assertRaises(TypeError, hash, self.s)
 362
 363     def test_clear(self):
 364         self.s.clear()
 365         self.assertEqual(self.s, set())
 366         self.assertEqual(len(self.s), 0)
 367
 368     def test_copy(self):
 369         dup = self.s.copy()
 370         self.assertEqual(self.s, dup)
 371         self.assertNotEqual(id(self.s), id(dup))
 372
 373     def test_add(self):
 374         self.s.add('Q')
 375         self.assertIn('Q', self.s)
 376         dup = self.s.copy()
 377         self.s.add('Q')
 378         self.assertEqual(self.s, dup)
 379         self.assertRaises(TypeError, self.s.add, [])
 380
 381     def test_remove(self):
 382         self.s.remove('a')
 383         self.assertNotIn('a', self.s)
 384         self.assertRaises(KeyError, self.s.remove, 'Q')
 385         self.assertRaises(TypeError, self.s.remove, [])
 386         s = self.thetype([frozenset(self.word)])
 387         self.assertIn(self.thetype(self.word), s)
 388         s.remove(self.thetype(self.word))
 389         self.assertNotIn(self.thetype(self.word), s)
 390         self.assertRaises(KeyError, self.s.remove, self.thetype(self.word))
 391
 392     def test_remove_keyerror_unpacking(self):
 393         # bug:  www.python.org/sf/1576657
 394         for v1 in ['Q', (1,)]:
 395             try:
 396                 self.s.remove(v1)
 397             except KeyError, e:
 398                 v2 = e.args[0]
 399                 self.assertEqual(v1, v2)
 400             else:
 401                 self.fail()
 402
 403     def test_remove_keyerror_set(self):
 404         key = self.thetype([3, 4])
 405         try:
 406             self.s.remove(key)
 407         except KeyError as e:
 408             self.assertTrue(e.args[0] is key,
 409                          "KeyError should be {0}, not {1}".format(key,
 410                                                                   e.args[0]))
 411         else:
 412             self.fail()
 413
 414     def test_discard(self):
 415         self.s.discard('a')
 416         self.assertNotIn('a', self.s)
 417         self.s.discard('Q')
 418         self.assertRaises(TypeError, self.s.discard, [])
 419         s = self.thetype([frozenset(self.word)])
 420         self.assertIn(self.thetype(self.word), s)
 421         s.discard(self.thetype(self.word))
 422         self.assertNotIn(self.thetype(self.word), s)
 423         s.discard(self.thetype(self.word))
 424
 425     def test_pop(self):
 426         for i in xrange(len(self.s)):
 427             elem = self.s.pop()
 428             self.assertNotIn(elem, self.s)
 429         self.assertRaises(KeyError, self.s.pop)
 430
 431     def test_update(self):
 432         retval = self.s.update(self.otherword)
 433         self.assertEqual(retval, None)
 434         for c in (self.word + self.otherword):
 435             self.assertIn(c, self.s)
 436         self.assertRaises(PassThru, self.s.update, check_pass_thru())
 437         self.assertRaises(TypeError, self.s.update, [[]])
 438         for p, q in (('cdc', 'abcd'), ('efgfe', 'abcefg'), ('ccb', 'abc'), ('ef', 'abcef')):
 439             for C in set, frozenset, dict.fromkeys, str, unicode, list, tuple:
 440                 s = self.thetype('abcba')
 441                 self.assertEqual(s.update(C(p)), None)
 442                 self.assertEqual(s, set(q))
 443         for p in ('cdc', 'efgfe', 'ccb', 'ef', 'abcda'):
 444             q = 'ahi'
 445             for C in set, frozenset, dict.fromkeys, str, unicode, list, tuple:
 446                 s = self.thetype('abcba')
 447                 self.assertEqual(s.update(C(p), C(q)), None)
 448                 self.assertEqual(s, set(s) | set(p) | set(q))
 449
 450     def test_ior(self):
 451         self.s |= set(self.otherword)
 452         for c in (self.word + self.otherword):
 453             self.assertIn(c, self.s)
 454
 455     def test_intersection_update(self):
 456         retval = self.s.intersection_update(self.otherword)
 457         self.assertEqual(retval, None)
 458         for c in (self.word + self.otherword):
 459             if c in self.otherword and c in self.word:
 460                 self.assertIn(c, self.s)
 461             else:
 462                 self.assertNotIn(c, self.s)
 463         self.assertRaises(PassThru, self.s.intersection_update, check_pass_thru())
 464         self.assertRaises(TypeError, self.s.intersection_update, [[]])
 465         for p, q in (('cdc', 'c'), ('efgfe', ''), ('ccb', 'bc'), ('ef', '')):
 466             for C in set, frozenset, dict.fromkeys, str, unicode, list, tuple:
 467                 s = self.thetype('abcba')
 468                 self.assertEqual(s.intersection_update(C(p)), None)
 469                 self.assertEqual(s, set(q))
 470                 ss = 'abcba'
 471                 s = self.thetype(ss)
 472                 t = 'cbc'
 473                 self.assertEqual(s.intersection_update(C(p), C(t)), None)
 474                 self.assertEqual(s, set('abcba')&set(p)&set(t))
 475
 476     def test_iand(self):
 477         self.s &= set(self.otherword)
 478         for c in (self.word + self.otherword):
 479             if c in self.otherword and c in self.word:
 480                 self.assertIn(c, self.s)
 481             else:
 482                 self.assertNotIn(c, self.s)
 483
 484     def test_difference_update(self):
 485         retval = self.s.difference_update(self.otherword)
 486         self.assertEqual(retval, None)
 487         for c in (self.word + self.otherword):
 488             if c in self.word and c not in self.otherword:
 489                 self.assertIn(c, self.s)
 490             else:
 491                 self.assertNotIn(c, self.s)
 492         self.assertRaises(PassThru, self.s.difference_update, check_pass_thru())
 493         self.assertRaises(TypeError, self.s.difference_update, [[]])
 494         self.assertRaises(TypeError, self.s.symmetric_difference_update, [[]])
 495         for p, q in (('cdc', 'ab'), ('efgfe', 'abc'), ('ccb', 'a'), ('ef', 'abc')):
 496             for C in set, frozenset, dict.fromkeys, str, unicode, list, tuple:
 497                 s = self.thetype('abcba')
 498                 self.assertEqual(s.difference_update(C(p)), None)
 499                 self.assertEqual(s, set(q))
 500
 501                 s = self.thetype('abcdefghih')
 502                 s.difference_update()
 503                 self.assertEqual(s, self.thetype('abcdefghih'))
 504
 505                 s = self.thetype('abcdefghih')
 506                 s.difference_update(C('aba'))
 507                 self.assertEqual(s, self.thetype('cdefghih'))
 508
 509                 s = self.thetype('abcdefghih')
 510                 s.difference_update(C('cdc'), C('aba'))
 511                 self.assertEqual(s, self.thetype('efghih'))
 512
 513     def test_isub(self):
 514         self.s -= set(self.otherword)
 515         for c in (self.word + self.otherword):
 516             if c in self.word and c not in self.otherword:
 517                 self.assertIn(c, self.s)
 518             else:
 519                 self.assertNotIn(c, self.s)
 520
 521     def test_symmetric_difference_update(self):
 522         retval = self.s.symmetric_difference_update(self.otherword)
 523         self.assertEqual(retval, None)
 524         for c in (self.word + self.otherword):
 525             if (c in self.word) ^ (c in self.otherword):
 526                 self.assertIn(c, self.s)
 527             else:
 528                 self.assertNotIn(c, self.s)
 529         self.assertRaises(PassThru, self.s.symmetric_difference_update, check_pass_thru())
 530         self.assertRaises(TypeError, self.s.symmetric_difference_update, [[]])
 531         for p, q in (('cdc', 'abd'), ('efgfe', 'abcefg'), ('ccb', 'a'), ('ef', 'abcef')):
 532             for C in set, frozenset, dict.fromkeys, str, unicode, list, tuple:
 533                 s = self.thetype('abcba')
 534                 self.assertEqual(s.symmetric_difference_update(C(p)), None)
 535                 self.assertEqual(s, set(q))
 536
 537     def test_ixor(self):
 538         self.s ^= set(self.otherword)
 539         for c in (self.word + self.otherword):
 540             if (c in self.word) ^ (c in self.otherword):
 541                 self.assertIn(c, self.s)
 542             else:
 543                 self.assertNotIn(c, self.s)
 544
 545     def test_inplace_on_self(self):
 546         t = self.s.copy()
 547         t |= t
 548         self.assertEqual(t, self.s)
 549         t &= t
 550         self.assertEqual(t, self.s)
 551         t -= t
 552         self.assertEqual(t, self.thetype())
 553         t = self.s.copy()
 554         t ^= t
 555         self.assertEqual(t, self.thetype())
 556
 557     def test_weakref(self):
 558         s = self.thetype('gallahad')
 559         p = weakref.proxy(s)
 560         self.assertEqual(str(p), str(s))
 561         s = None
 562         self.assertRaises(ReferenceError, str, p)
 563
 564     # C API test only available in a debug build
 565     if hasattr(set, "test_c_api"):
 566         def test_c_api(self):
 567             self.assertEqual(set().test_c_api(), True)
 568
 569 class SetSubclass(set):
 570     pass
 571
 572 class TestSetSubclass(TestSet):
 573     thetype = SetSubclass
 574
 575 class SetSubclassWithKeywordArgs(set):
 576     def __init__(self, iterable=[], newarg=None):
 577         set.__init__(self, iterable)
 578
 579 class TestSetSubclassWithKeywordArgs(TestSet):
 580
 581     def test_keywords_in_subclass(self):
 582         'SF bug #1486663 -- this used to erroneously raise a TypeError'
 583         SetSubclassWithKeywordArgs(newarg=1)
 584
 585 class TestFrozenSet(TestJointOps):
 586     thetype = frozenset
 587
 588     def test_init(self):
 589         s = self.thetype(self.word)
 590         s.__init__(self.otherword)
 591         self.assertEqual(s, set(self.word))
 592
 593     def test_singleton_empty_frozenset(self):
 594         f = frozenset()
 595         efs = [frozenset(), frozenset([]), frozenset(()), frozenset(''),
 596                frozenset(), frozenset([]), frozenset(()), frozenset(''),
 597                frozenset(xrange(0)), frozenset(frozenset()),
 598                frozenset(f), f]
 599         # All of the empty frozensets should have just one id()
 600         self.assertEqual(len(set(map(id, efs))), 1)
 601
 602     def test_constructor_identity(self):
 603         s = self.thetype(range(3))
 604         t = self.thetype(s)
 605         self.assertEqual(id(s), id(t))
 606
 607     def test_hash(self):
 608         self.assertEqual(hash(self.thetype('abcdeb')),
 609                          hash(self.thetype('ebecda')))
 610
 611         # make sure that all permutations give the same hash value
 612         n = 100
 613         seq = [randrange(n) for i in xrange(n)]
 614         results = set()
 615         for i in xrange(200):
 616             shuffle(seq)
 617             results.add(hash(self.thetype(seq)))
 618         self.assertEqual(len(results), 1)
 619
 620     def test_copy(self):
 621         dup = self.s.copy()
 622         self.assertEqual(id(self.s), id(dup))
 623
 624     def test_frozen_as_dictkey(self):
 625         seq = range(10) + list('abcdefg') + ['apple']
 626         key1 = self.thetype(seq)
 627         key2 = self.thetype(reversed(seq))
 628         self.assertEqual(key1, key2)
 629         self.assertNotEqual(id(key1), id(key2))
 630         d = {}
 631         d[key1] = 42
 632         self.assertEqual(d[key2], 42)
 633
 634     def test_hash_caching(self):
 635         f = self.thetype('abcdcda')
 636         self.assertEqual(hash(f), hash(f))
 637
 638     def test_hash_effectiveness(self):
 639         n = 13
 640         hashvalues = set()
 641         addhashvalue = hashvalues.add
 642         elemmasks = [(i+1, 1<<i) for i in range(n)]
 643         for i in xrange(2**n):
 644             addhashvalue(hash(frozenset([e for e, m in elemmasks if m&i])))
 645         self.assertEqual(len(hashvalues), 2**n)
 646
 647 class FrozenSetSubclass(frozenset):
 648     pass
 649
 650 class TestFrozenSetSubclass(TestFrozenSet):
 651     thetype = FrozenSetSubclass
 652
 653     def test_constructor_identity(self):
 654         s = self.thetype(range(3))
 655         t = self.thetype(s)
 656         self.assertNotEqual(id(s), id(t))
 657
 658     def test_copy(self):
 659         dup = self.s.copy()
 660         self.assertNotEqual(id(self.s), id(dup))
 661
 662     def test_nested_empty_constructor(self):
 663         s = self.thetype()
 664         t = self.thetype(s)
 665         self.assertEqual(s, t)
 666
 667     def test_singleton_empty_frozenset(self):
 668         Frozenset = self.thetype
 669         f = frozenset()
 670         F = Frozenset()
 671         efs = [Frozenset(), Frozenset([]), Frozenset(()), Frozenset(''),
 672                Frozenset(), Frozenset([]), Frozenset(()), Frozenset(''),
 673                Frozenset(xrange(0)), Frozenset(Frozenset()),
 674                Frozenset(frozenset()), f, F, Frozenset(f), Frozenset(F)]
 675         # All empty frozenset subclass instances should have different ids
 676         self.assertEqual(len(set(map(id, efs))), len(efs))
 677
 678 # Tests taken from test_sets.py =============================================
 679
 680 empty_set = set()
 681
 682 #==============================================================================
 683
 684 class TestBasicOps(unittest.TestCase):
 685
 686     def test_repr(self):
 687         if self.repr is not None:
 688             self.assertEqual(repr(self.set), self.repr)
 689
 690     def test_print(self):
 691         fo = open(test_support.TESTFN, "wb")
 692         try:
 693             print >> fo, self.set,
 694             fo.close()
 695             fo = open(test_support.TESTFN, "rb")
 696             self.assertEqual(fo.read(), repr(self.set))
 697         finally:
 698             fo.close()
 699             test_support.unlink(test_support.TESTFN)
 700
 701     def test_length(self):
 702         self.assertEqual(len(self.set), self.length)
 703
 704     def test_self_equality(self):
 705         self.assertEqual(self.set, self.set)
 706
 707     def test_equivalent_equality(self):
 708         self.assertEqual(self.set, self.dup)
 709
 710     def test_copy(self):
 711         self.assertEqual(self.set.copy(), self.dup)
 712
 713     def test_self_union(self):
 714         result = self.set | self.set
 715         self.assertEqual(result, self.dup)
 716
 717     def test_empty_union(self):
 718         result = self.set | empty_set
 719         self.assertEqual(result, self.dup)
 720
 721     def test_union_empty(self):
 722         result = empty_set | self.set
 723         self.assertEqual(result, self.dup)
 724
 725     def test_self_intersection(self):
 726         result = self.set & self.set
 727         self.assertEqual(result, self.dup)
 728
 729     def test_empty_intersection(self):
 730         result = self.set & empty_set
 731         self.assertEqual(result, empty_set)
 732
 733     def test_intersection_empty(self):
 734         result = empty_set & self.set
 735         self.assertEqual(result, empty_set)
 736
 737     def test_self_isdisjoint(self):
 738         result = self.set.isdisjoint(self.set)
 739         self.assertEqual(result, not self.set)
 740
 741     def test_empty_isdisjoint(self):
 742         result = self.set.isdisjoint(empty_set)
 743         self.assertEqual(result, True)
 744
 745     def test_isdisjoint_empty(self):
 746         result = empty_set.isdisjoint(self.set)
 747         self.assertEqual(result, True)
 748
 749     def test_self_symmetric_difference(self):
 750         result = self.set ^ self.set
 751         self.assertEqual(result, empty_set)
 752
 753     def checkempty_symmetric_difference(self):
 754         result = self.set ^ empty_set
 755         self.assertEqual(result, self.set)
 756
 757     def test_self_difference(self):
 758         result = self.set - self.set
 759         self.assertEqual(result, empty_set)
 760
 761     def test_empty_difference(self):
 762         result = self.set - empty_set
 763         self.assertEqual(result, self.dup)
 764
 765     def test_empty_difference_rev(self):
 766         result = empty_set - self.set
 767         self.assertEqual(result, empty_set)
 768
 769     def test_iteration(self):
 770         for v in self.set:
 771             self.assertIn(v, self.values)
 772         setiter = iter(self.set)
 773         # note: __length_hint__ is an internal undocumented API,
 774         # don't rely on it in your own programs
 775         self.assertEqual(setiter.__length_hint__(), len(self.set))
 776
 777     def test_pickling(self):
 778         p = pickle.dumps(self.set)
 779         copy = pickle.loads(p)
 780         self.assertEqual(self.set, copy,
 781                          "%s != %s" % (self.set, copy))
 782
 783 #------------------------------------------------------------------------------
 784
 785 class TestBasicOpsEmpty(TestBasicOps):
 786     def setUp(self):
 787         self.case   = "empty set"
 788         self.values = []
 789         self.set    = set(self.values)
 790         self.dup    = set(self.values)
 791         self.length = 0
 792         self.repr   = "set([])"
 793
 794 #------------------------------------------------------------------------------
 795
 796 class TestBasicOpsSingleton(TestBasicOps):
 797     def setUp(self):
 798         self.case   = "unit set (number)"
 799         self.values = [3]
 800         self.set    = set(self.values)
 801         self.dup    = set(self.values)
 802         self.length = 1
 803         self.repr   = "set([3])"
 804
 805     def test_in(self):
 806         self.assertIn(3, self.set)
 807
 808     def test_not_in(self):
 809         self.assertNotIn(2, self.set)
 810
 811 #------------------------------------------------------------------------------
 812
 813 class TestBasicOpsTuple(TestBasicOps):
 814     def setUp(self):
 815         self.case   = "unit set (tuple)"
 816         self.values = [(0, "zero")]
 817         self.set    = set(self.values)
 818         self.dup    = set(self.values)
 819         self.length = 1
 820         self.repr   = "set([(0, 'zero')])"
 821
 822     def test_in(self):
 823         self.assertIn((0, "zero"), self.set)
 824
 825     def test_not_in(self):
 826         self.assertNotIn(9, self.set)
 827
 828 #------------------------------------------------------------------------------
 829
 830 class TestBasicOpsTriple(TestBasicOps):
 831     def setUp(self):
 832         self.case   = "triple set"
 833         self.values = [0, "zero", operator.add]
 834         self.set    = set(self.values)
 835         self.dup    = set(self.values)
 836         self.length = 3
 837         self.repr   = None
 838
 839 #==============================================================================
 840
 841 def baditer():
 842     raise TypeError
 843     yield True
 844
 845 def gooditer():
 846     yield True
 847
 848 class TestExceptionPropagation(unittest.TestCase):
 849     """SF 628246:  Set constructor should not trap iterator TypeErrors"""
 850
 851     def test_instanceWithException(self):
 852         self.assertRaises(TypeError, set, baditer())
 853
 854     def test_instancesWithoutException(self):
 855         # All of these iterables should load without exception.
 856         set([1,2,3])
 857         set((1,2,3))
 858         set({'one':1, 'two':2, 'three':3})
 859         set(xrange(3))
 860         set('abc')
 861         set(gooditer())
 862
 863     def test_changingSizeWhileIterating(self):
 864         s = set([1,2,3])
 865         try:
 866             for i in s:
 867                 s.update([4])
 868         except RuntimeError:
 869             pass
 870         else:
 871             self.fail("no exception when changing size during iteration")
 872
 873 #==============================================================================
 874
 875 class TestSetOfSets(unittest.TestCase):
 876     def test_constructor(self):
 877         inner = frozenset([1])
 878         outer = set([inner])
 879         element = outer.pop()
 880         self.assertEqual(type(element), frozenset)
 881         outer.add(inner)        # Rebuild set of sets with .add method
 882         outer.remove(inner)
 883         self.assertEqual(outer, set())   # Verify that remove worked
 884         outer.discard(inner)    # Absence of KeyError indicates working fine
 885
 886 #==============================================================================
 887
 888 class TestBinaryOps(unittest.TestCase):
 889     def setUp(self):
 890         self.set = set((2, 4, 6))
 891
 892     def test_eq(self):              # SF bug 643115
 893         self.assertEqual(self.set, set({2:1,4:3,6:5}))
 894
 895     def test_union_subset(self):
 896         result = self.set | set([2])
 897         self.assertEqual(result, set((2, 4, 6)))
 898
 899     def test_union_superset(self):
 900         result = self.set | set([2, 4, 6, 8])
 901         self.assertEqual(result, set([2, 4, 6, 8]))
 902
 903     def test_union_overlap(self):
 904         result = self.set | set([3, 4, 5])
 905         self.assertEqual(result, set([2, 3, 4, 5, 6]))
 906
 907     def test_union_non_overlap(self):
 908         result = self.set | set([8])
 909         self.assertEqual(result, set([2, 4, 6, 8]))
 910
 911     def test_intersection_subset(self):
 912         result = self.set & set((2, 4))
 913         self.assertEqual(result, set((2, 4)))
 914
 915     def test_intersection_superset(self):
 916         result = self.set & set([2, 4, 6, 8])
 917         self.assertEqual(result, set([2, 4, 6]))
 918
 919     def test_intersection_overlap(self):
 920         result = self.set & set([3, 4, 5])
 921         self.assertEqual(result, set([4]))
 922
 923     def test_intersection_non_overlap(self):
 924         result = self.set & set([8])
 925         self.assertEqual(result, empty_set)
 926
 927     def test_isdisjoint_subset(self):
 928         result = self.set.isdisjoint(set((2, 4)))
 929         self.assertEqual(result, False)
 930
 931     def test_isdisjoint_superset(self):
 932         result = self.set.isdisjoint(set([2, 4, 6, 8]))
 933         self.assertEqual(result, False)
 934
 935     def test_isdisjoint_overlap(self):
 936         result = self.set.isdisjoint(set([3, 4, 5]))
 937         self.assertEqual(result, False)
 938
 939     def test_isdisjoint_non_overlap(self):
 940         result = self.set.isdisjoint(set([8]))
 941         self.assertEqual(result, True)
 942
 943     def test_sym_difference_subset(self):
 944         result = self.set ^ set((2, 4))
 945         self.assertEqual(result, set([6]))
 946
 947     def test_sym_difference_superset(self):
 948         result = self.set ^ set((2, 4, 6, 8))
 949         self.assertEqual(result, set([8]))
 950
 951     def test_sym_difference_overlap(self):
 952         result = self.set ^ set((3, 4, 5))
 953         self.assertEqual(result, set([2, 3, 5, 6]))
 954
 955     def test_sym_difference_non_overlap(self):
 956         result = self.set ^ set([8])
 957         self.assertEqual(result, set([2, 4, 6, 8]))
 958
 959     def test_cmp(self):
 960         a, b = set('a'), set('b')
 961         self.assertRaises(TypeError, cmp, a, b)
 962
 963         # You can view this as a buglet:  cmp(a, a) does not raise TypeError,
 964         # because __eq__ is tried before __cmp__, and a.__eq__(a) returns True,
 965         # which Python thinks is good enough to synthesize a cmp() result
 966         # without calling __cmp__.
 967         self.assertEqual(cmp(a, a), 0)
 968
 969         self.assertRaises(TypeError, cmp, a, 12)
 970         self.assertRaises(TypeError, cmp, "abc", a)
 971
 972 #==============================================================================
 973
 974 class TestUpdateOps(unittest.TestCase):
 975     def setUp(self):
 976         self.set = set((2, 4, 6))
 977
 978     def test_union_subset(self):
 979         self.set |= set([2])
 980         self.assertEqual(self.set, set((2, 4, 6)))
 981
 982     def test_union_superset(self):
 983         self.set |= set([2, 4, 6, 8])
 984         self.assertEqual(self.set, set([2, 4, 6, 8]))
 985
 986     def test_union_overlap(self):
 987         self.set |= set([3, 4, 5])
 988         self.assertEqual(self.set, set([2, 3, 4, 5, 6]))
 989
 990     def test_union_non_overlap(self):
 991         self.set |= set([8])
 992         self.assertEqual(self.set, set([2, 4, 6, 8]))
 993
 994     def test_union_method_call(self):
 995         self.set.update(set([3, 4, 5]))
 996         self.assertEqual(self.set, set([2, 3, 4, 5, 6]))
 997
 998     def test_intersection_subset(self):
 999         self.set &= set((2, 4))
1000         self.assertEqual(self.set, set((2, 4)))
1001
1002     def test_intersection_superset(self):
1003         self.set &= set([2, 4, 6, 8])
1004         self.assertEqual(self.set, set([2, 4, 6]))
1005
1006     def test_intersection_overlap(self):
1007         self.set &= set([3, 4, 5])
1008         self.assertEqual(self.set, set([4]))
1009
1010     def test_intersection_non_overlap(self):
1011         self.set &= set([8])
1012         self.assertEqual(self.set, empty_set)
1013
1014     def test_intersection_method_call(self):
1015         self.set.intersection_update(set([3, 4, 5]))
1016         self.assertEqual(self.set, set([4]))
1017
1018     def test_sym_difference_subset(self):
1019         self.set ^= set((2, 4))
1020         self.assertEqual(self.set, set([6]))
1021
1022     def test_sym_difference_superset(self):
1023         self.set ^= set((2, 4, 6, 8))
1024         self.assertEqual(self.set, set([8]))
1025
1026     def test_sym_difference_overlap(self):
1027         self.set ^= set((3, 4, 5))
1028         self.assertEqual(self.set, set([2, 3, 5, 6]))
1029
1030     def test_sym_difference_non_overlap(self):
1031         self.set ^= set([8])
1032         self.assertEqual(self.set, set([2, 4, 6, 8]))
1033
1034     def test_sym_difference_method_call(self):
1035         self.set.symmetric_difference_update(set([3, 4, 5]))
1036         self.assertEqual(self.set, set([2, 3, 5, 6]))
1037
1038     def test_difference_subset(self):
1039         self.set -= set((2, 4))
1040         self.assertEqual(self.set, set([6]))
1041
1042     def test_difference_superset(self):
1043         self.set -= set((2, 4, 6, 8))
1044         self.assertEqual(self.set, set([]))
1045
1046     def test_difference_overlap(self):
1047         self.set -= set((3, 4, 5))
1048         self.assertEqual(self.set, set([2, 6]))
1049
1050     def test_difference_non_overlap(self):
1051         self.set -= set([8])
1052         self.assertEqual(self.set, set([2, 4, 6]))
1053
1054     def test_difference_method_call(self):
1055         self.set.difference_update(set([3, 4, 5]))
1056         self.assertEqual(self.set, set([2, 6]))
1057
1058 #==============================================================================
1059
1060 class TestMutate(unittest.TestCase):
1061     def setUp(self):
1062         self.values = ["a", "b", "c"]
1063         self.set = set(self.values)
1064
1065     def test_add_present(self):
1066         self.set.add("c")
1067         self.assertEqual(self.set, set("abc"))
1068
1069     def test_add_absent(self):
1070         self.set.add("d")
1071         self.assertEqual(self.set, set("abcd"))
1072
1073     def test_add_until_full(self):
1074         tmp = set()
1075         expected_len = 0
1076         for v in self.values:
1077             tmp.add(v)
1078             expected_len += 1
1079             self.assertEqual(len(tmp), expected_len)
1080         self.assertEqual(tmp, self.set)
1081
1082     def test_remove_present(self):
1083         self.set.remove("b")
1084         self.assertEqual(self.set, set("ac"))
1085
1086     def test_remove_absent(self):
1087         try:
1088             self.set.remove("d")
1089             self.fail("Removing missing element should have raised LookupError")
1090         except LookupError:
1091             pass
1092
1093     def test_remove_until_empty(self):
1094         expected_len = len(self.set)
1095         for v in self.values:
1096             self.set.remove(v)
1097             expected_len -= 1
1098             self.assertEqual(len(self.set), expected_len)
1099
1100     def test_discard_present(self):
1101         self.set.discard("c")
1102         self.assertEqual(self.set, set("ab"))
1103
1104     def test_discard_absent(self):
1105         self.set.discard("d")
1106         self.assertEqual(self.set, set("abc"))
1107
1108     def test_clear(self):
1109         self.set.clear()
1110         self.assertEqual(len(self.set), 0)
1111
1112     def test_pop(self):
1113         popped = {}
1114         while self.set:
1115             popped[self.set.pop()] = None
1116         self.assertEqual(len(popped), len(self.values))
1117         for v in self.values:
1118             self.assertIn(v, popped)
1119
1120     def test_update_empty_tuple(self):
1121         self.set.update(())
1122         self.assertEqual(self.set, set(self.values))
1123
1124     def test_update_unit_tuple_overlap(self):
1125         self.set.update(("a",))
1126         self.assertEqual(self.set, set(self.values))
1127
1128     def test_update_unit_tuple_non_overlap(self):
1129         self.set.update(("a", "z"))
1130         self.assertEqual(self.set, set(self.values + ["z"]))
1131
1132 #==============================================================================
1133
1134 class TestSubsets(unittest.TestCase):
1135
1136     case2method = {"<=": "issubset",
1137                    ">=": "issuperset",
1138                   }
1139
1140     reverse = {"==": "==",
1141                "!=": "!=",
1142                "<":  ">",
1143                ">":  "<",
1144                "<=": ">=",
1145                ">=": "<=",
1146               }
1147
1148     def test_issubset(self):
1149         x = self.left
1150         y = self.right
1151         for case in "!=", "==", "<", "<=", ">", ">=":
1152             expected = case in self.cases
1153             # Test the binary infix spelling.
1154             result = eval("x" + case + "y", locals())
1155             self.assertEqual(result, expected)
1156             # Test the "friendly" method-name spelling, if one exists.
1157             if case in TestSubsets.case2method:
1158                 method = getattr(x, TestSubsets.case2method[case])
1159                 result = method(y)
1160                 self.assertEqual(result, expected)
1161
1162             # Now do the same for the operands reversed.
1163             rcase = TestSubsets.reverse[case]
1164             result = eval("y" + rcase + "x", locals())
1165             self.assertEqual(result, expected)
1166             if rcase in TestSubsets.case2method:
1167                 method = getattr(y, TestSubsets.case2method[rcase])
1168                 result = method(x)
1169                 self.assertEqual(result, expected)
1170 #------------------------------------------------------------------------------
1171
1172 class TestSubsetEqualEmpty(TestSubsets):
1173     left  = set()
1174     right = set()
1175     name  = "both empty"
1176     cases = "==", "<=", ">="
1177
1178 #------------------------------------------------------------------------------
1179
1180 class TestSubsetEqualNonEmpty(TestSubsets):
1181     left  = set([1, 2])
1182     right = set([1, 2])
1183     name  = "equal pair"
1184     cases = "==", "<=", ">="
1185
1186 #------------------------------------------------------------------------------
1187
1188 class TestSubsetEmptyNonEmpty(TestSubsets):
1189     left  = set()
1190     right = set([1, 2])
1191     name  = "one empty, one non-empty"
1192     cases = "!=", "<", "<="
1193
1194 #------------------------------------------------------------------------------
1195
1196 class TestSubsetPartial(TestSubsets):
1197     left  = set([1])
1198     right = set([1, 2])
1199     name  = "one a non-empty proper subset of other"
1200     cases = "!=", "<", "<="
1201
1202 #------------------------------------------------------------------------------
1203
1204 class TestSubsetNonOverlap(TestSubsets):
1205     left  = set([1])
1206     right = set([2])
1207     name  = "neither empty, neither contains"
1208     cases = "!="
1209
1210 #==============================================================================
1211
1212 class TestOnlySetsInBinaryOps(unittest.TestCase):
1213
1214     def test_eq_ne(self):
1215         # Unlike the others, this is testing that == and != *are* allowed.
1216         self.assertEqual(self.other == self.set, False)
1217         self.assertEqual(self.set == self.other, False)
1218         self.assertEqual(self.other != self.set, True)
1219         self.assertEqual(self.set != self.other, True)
1220
1221     def test_ge_gt_le_lt(self):
1222         self.assertRaises(TypeError, lambda: self.set < self.other)
1223         self.assertRaises(TypeError, lambda: self.set <= self.other)
1224         self.assertRaises(TypeError, lambda: self.set > self.other)
1225         self.assertRaises(TypeError, lambda: self.set >= self.other)
1226
1227         self.assertRaises(TypeError, lambda: self.other < self.set)
1228         self.assertRaises(TypeError, lambda: self.other <= self.set)
1229         self.assertRaises(TypeError, lambda: self.other > self.set)
1230         self.assertRaises(TypeError, lambda: self.other >= self.set)
1231
1232     def test_update_operator(self):
1233         try:
1234             self.set |= self.other
1235         except TypeError:
1236             pass
1237         else:
1238             self.fail("expected TypeError")
1239
1240     def test_update(self):
1241         if self.otherIsIterable:
1242             self.set.update(self.other)
1243         else:
1244             self.assertRaises(TypeError, self.set.update, self.other)
1245
1246     def test_union(self):
1247         self.assertRaises(TypeError, lambda: self.set | self.other)
1248         self.assertRaises(TypeError, lambda: self.other | self.set)
1249         if self.otherIsIterable:
1250             self.set.union(self.other)
1251         else:
1252             self.assertRaises(TypeError, self.set.union, self.other)
1253
1254     def test_intersection_update_operator(self):
1255         try:
1256             self.set &= self.other
1257         except TypeError:
1258             pass
1259         else:
1260             self.fail("expected TypeError")
1261
1262     def test_intersection_update(self):
1263         if self.otherIsIterable:
1264             self.set.intersection_update(self.other)
1265         else:
1266             self.assertRaises(TypeError,
1267                               self.set.intersection_update,
1268                               self.other)
1269
1270     def test_intersection(self):
1271         self.assertRaises(TypeError, lambda: self.set & self.other)
1272         self.assertRaises(TypeError, lambda: self.other & self.set)
1273         if self.otherIsIterable:
1274             self.set.intersection(self.other)
1275         else:
1276             self.assertRaises(TypeError, self.set.intersection, self.other)
1277
1278     def test_sym_difference_update_operator(self):
1279         try:
1280             self.set ^= self.other
1281         except TypeError:
1282             pass
1283         else:
1284             self.fail("expected TypeError")
1285
1286     def test_sym_difference_update(self):
1287         if self.otherIsIterable:
1288             self.set.symmetric_difference_update(self.other)
1289         else:
1290             self.assertRaises(TypeError,
1291                               self.set.symmetric_difference_update,
1292                               self.other)
1293
1294     def test_sym_difference(self):
1295         self.assertRaises(TypeError, lambda: self.set ^ self.other)
1296         self.assertRaises(TypeError, lambda: self.other ^ self.set)
1297         if self.otherIsIterable:
1298             self.set.symmetric_difference(self.other)
1299         else:
1300             self.assertRaises(TypeError, self.set.symmetric_difference, self.other)
1301
1302     def test_difference_update_operator(self):
1303         try:
1304             self.set -= self.other
1305         except TypeError:
1306             pass
1307         else:
1308             self.fail("expected TypeError")
1309
1310     def test_difference_update(self):
1311         if self.otherIsIterable:
1312             self.set.difference_update(self.other)
1313         else:
1314             self.assertRaises(TypeError,
1315                               self.set.difference_update,
1316                               self.other)
1317
1318     def test_difference(self):
1319         self.assertRaises(TypeError, lambda: self.set - self.other)
1320         self.assertRaises(TypeError, lambda: self.other - self.set)
1321         if self.otherIsIterable:
1322             self.set.difference(self.other)
1323         else:
1324             self.assertRaises(TypeError, self.set.difference, self.other)
1325
1326 #------------------------------------------------------------------------------
1327
1328 class TestOnlySetsNumeric(TestOnlySetsInBinaryOps):
1329     def setUp(self):
1330         self.set   = set((1, 2, 3))
1331         self.other = 19
1332         self.otherIsIterable = False
1333
1334 #------------------------------------------------------------------------------
1335
1336 class TestOnlySetsDict(TestOnlySetsInBinaryOps):
1337     def setUp(self):
1338         self.set   = set((1, 2, 3))
1339         self.other = {1:2, 3:4}
1340         self.otherIsIterable = True
1341
1342 #------------------------------------------------------------------------------
1343
1344 class TestOnlySetsOperator(TestOnlySetsInBinaryOps):
1345     def setUp(self):
1346         self.set   = set((1, 2, 3))
1347         self.other = operator.add
1348         self.otherIsIterable = False
1349
1350     def test_ge_gt_le_lt(self):
1351         with test_support.check_py3k_warnings():
1352             super(TestOnlySetsOperator, self).test_ge_gt_le_lt()
1353
1354 #------------------------------------------------------------------------------
1355
1356 class TestOnlySetsTuple(TestOnlySetsInBinaryOps):
1357     def setUp(self):
1358         self.set   = set((1, 2, 3))
1359         self.other = (2, 4, 6)
1360         self.otherIsIterable = True
1361
1362 #------------------------------------------------------------------------------
1363
1364 class TestOnlySetsString(TestOnlySetsInBinaryOps):
1365     def setUp(self):
1366         self.set   = set((1, 2, 3))
1367         self.other = 'abc'
1368         self.otherIsIterable = True
1369
1370 #------------------------------------------------------------------------------
1371
1372 class TestOnlySetsGenerator(TestOnlySetsInBinaryOps):
1373     def setUp(self):
1374         def gen():
1375             for i in xrange(0, 10, 2):
1376                 yield i
1377         self.set   = set((1, 2, 3))
1378         self.other = gen()
1379         self.otherIsIterable = True
1380
1381 #==============================================================================
1382
1383 class TestCopying(unittest.TestCase):
1384
1385     def test_copy(self):
1386         dup = list(self.set.copy())
1387         self.assertEqual(len(dup), len(self.set))
1388         for el in self.set:
1389             self.assertIn(el, dup)
1390             pos = dup.index(el)
1391             self.assertIs(el, dup.pop(pos))
1392         self.assertFalse(dup)
1393
1394     def test_deep_copy(self):
1395         dup = copy.deepcopy(self.set)
1396         self.assertSetEqual(dup, self.set)
1397
1398 #------------------------------------------------------------------------------
1399
1400 class TestCopyingEmpty(TestCopying):
1401     def setUp(self):
1402         self.set = set()
1403
1404 #------------------------------------------------------------------------------
1405
1406 class TestCopyingSingleton(TestCopying):
1407     def setUp(self):
1408         self.set = set(["hello"])
1409
1410 #------------------------------------------------------------------------------
1411
1412 class TestCopyingTriple(TestCopying):
1413     def setUp(self):
1414         self.set = set(["zero", 0, None])
1415
1416 #------------------------------------------------------------------------------
1417
1418 class TestCopyingTuple(TestCopying):
1419     def setUp(self):
1420         self.set = set([(1, 2)])
1421
1422 #------------------------------------------------------------------------------
1423
1424 class TestCopyingNested(TestCopying):
1425     def setUp(self):
1426         self.set = set([((1, 2), (3, 4))])
1427
1428 #==============================================================================
1429
1430 class TestIdentities(unittest.TestCase):
1431     def setUp(self):
1432         self.a = set('abracadabra')
1433         self.b = set('alacazam')
1434
1435     def test_binopsVsSubsets(self):
1436         a, b = self.a, self.b
1437         self.assertTrue(a - b < a)
1438         self.assertTrue(b - a < b)
1439         self.assertTrue(a & b < a)
1440         self.assertTrue(a & b < b)
1441         self.assertTrue(a | b > a)
1442         self.assertTrue(a | b > b)
1443         self.assertTrue(a ^ b < a | b)
1444
1445     def test_commutativity(self):
1446         a, b = self.a, self.b
1447         self.assertEqual(a&b, b&a)
1448         self.assertEqual(a|b, b|a)
1449         self.assertEqual(a^b, b^a)
1450         if a != b:
1451             self.assertNotEqual(a-b, b-a)
1452
1453     def test_summations(self):
1454         # check that sums of parts equal the whole
1455         a, b = self.a, self.b
1456         self.assertEqual((a-b)|(a&b)|(b-a), a|b)
1457         self.assertEqual((a&b)|(a^b), a|b)
1458         self.assertEqual(a|(b-a), a|b)
1459         self.assertEqual((a-b)|b, a|b)
1460         self.assertEqual((a-b)|(a&b), a)
1461         self.assertEqual((b-a)|(a&b), b)
1462         self.assertEqual((a-b)|(b-a), a^b)
1463
1464     def test_exclusion(self):
1465         # check that inverse operations show non-overlap
1466         a, b, zero = self.a, self.b, set()
1467         self.assertEqual((a-b)&b, zero)
1468         self.assertEqual((b-a)&a, zero)
1469         self.assertEqual((a&b)&(a^b), zero)
1470
1471 # Tests derived from test_itertools.py =======================================
1472
1473 def R(seqn):
1474     'Regular generator'
1475     for i in seqn:
1476         yield i
1477
1478 class G:
1479     'Sequence using __getitem__'
1480     def __init__(self, seqn):
1481         self.seqn = seqn
1482     def __getitem__(self, i):
1483         return self.seqn[i]
1484
1485 class I:
1486     'Sequence using iterator protocol'
1487     def __init__(self, seqn):
1488         self.seqn = seqn
1489         self.i = 0
1490     def __iter__(self):
1491         return self
1492     def next(self):
1493         if self.i >= len(self.seqn): raise StopIteration
1494         v = self.seqn[self.i]
1495         self.i += 1
1496         return v
1497
1498 class Ig:
1499     'Sequence using iterator protocol defined with a generator'
1500     def __init__(self, seqn):
1501         self.seqn = seqn
1502         self.i = 0
1503     def __iter__(self):
1504         for val in self.seqn:
1505             yield val
1506
1507 class X:
1508     'Missing __getitem__ and __iter__'
1509     def __init__(self, seqn):
1510         self.seqn = seqn
1511         self.i = 0
1512     def next(self):
1513         if self.i >= len(self.seqn): raise StopIteration
1514         v = self.seqn[self.i]
1515         self.i += 1
1516         return v
1517
1518 class N:
1519     'Iterator missing next()'
1520     def __init__(self, seqn):
1521         self.seqn = seqn
1522         self.i = 0
1523     def __iter__(self):
1524         return self
1525
1526 class E:
1527     'Test propagation of exceptions'
1528     def __init__(self, seqn):
1529         self.seqn = seqn
1530         self.i = 0
1531     def __iter__(self):
1532         return self
1533     def next(self):
1534         3 // 0
1535
1536 class S:
1537     'Test immediate stop'
1538     def __init__(self, seqn):
1539         pass
1540     def __iter__(self):
1541         return self
1542     def next(self):
1543         raise StopIteration
1544
1545 from itertools import chain, imap
1546 def L(seqn):
1547     'Test multiple tiers of iterators'
1548     return chain(imap(lambda x:x, R(Ig(G(seqn)))))
1549
1550 class TestVariousIteratorArgs(unittest.TestCase):
1551
1552     def test_constructor(self):
1553         for cons in (set, frozenset):
1554             for s in ("123", "", range(1000), ('do', 1.2), xrange(2000,2200,5)):
1555                 for g in (G, I, Ig, S, L, R):
1556                     self.assertSetEqual(cons(g(s)), set(g(s)))
1557                 self.assertRaises(TypeError, cons , X(s))
1558                 self.assertRaises(TypeError, cons , N(s))
1559                 self.assertRaises(ZeroDivisionError, cons , E(s))
1560
1561     def test_inline_methods(self):
1562         s = set('november')
1563         for data in ("123", "", range(1000), ('do', 1.2), xrange(2000,2200,5), 'december'):
1564             for meth in (s.union, s.intersection, s.difference, s.symmetric_difference, s.isdisjoint):
1565                 for g in (G, I, Ig, L, R):
1566                     expected = meth(data)
1567                     actual = meth(G(data))
1568                     if isinstance(expected, bool):
1569                         self.assertEqual(actual, expected)
1570                     else:
1571                         self.assertSetEqual(actual, expected)
1572                 self.assertRaises(TypeError, meth, X(s))
1573                 self.assertRaises(TypeError, meth, N(s))
1574                 self.assertRaises(ZeroDivisionError, meth, E(s))
1575
1576     def test_inplace_methods(self):
1577         for data in ("123", "", range(1000), ('do', 1.2), xrange(2000,2200,5), 'december'):
1578             for methname in ('update', 'intersection_update',
1579                              'difference_update', 'symmetric_difference_update'):
1580                 for g in (G, I, Ig, S, L, R):
1581                     s = set('january')
1582                     t = s.copy()
1583                     getattr(s, methname)(list(g(data)))
1584                     getattr(t, methname)(g(data))
1585                     self.assertSetEqual(s, t)
1586
1587                 self.assertRaises(TypeError, getattr(set('january'), methname), X(data))
1588                 self.assertRaises(TypeError, getattr(set('january'), methname), N(data))
1589                 self.assertRaises(ZeroDivisionError, getattr(set('january'), methname), E(data))
1590
1591 # Application tests (based on David Eppstein's graph recipes ====================================
1592
1593 def powerset(U):
1594     """Generates all subsets of a set or sequence U."""
1595     U = iter(U)
1596     try:
1597         x = frozenset([U.next()])
1598         for S in powerset(U):
1599             yield S
1600             yield S | x
1601     except StopIteration:
1602         yield frozenset()
1603
1604 def cube(n):
1605     """Graph of n-dimensional hypercube."""
1606     singletons = [frozenset([x]) for x in range(n)]
1607     return dict([(x, frozenset([x^s for s in singletons]))
1608                  for x in powerset(range(n))])
1609
1610 def linegraph(G):
1611     """Graph, the vertices of which are edges of G,
1612     with two vertices being adjacent iff the corresponding
1613     edges share a vertex."""
1614     L = {}
1615     for x in G:
1616         for y in G[x]:
1617             nx = [frozenset([x,z]) for z in G[x] if z != y]
1618             ny = [frozenset([y,z]) for z in G[y] if z != x]
1619             L[frozenset([x,y])] = frozenset(nx+ny)
1620     return L
1621
1622 def faces(G):
1623     'Return a set of faces in G.  Where a face is a set of vertices on that face'
1624     # currently limited to triangles,squares, and pentagons
1625     f = set()
1626     for v1, edges in G.items():
1627         for v2 in edges:
1628             for v3 in G[v2]:
1629                 if v1 == v3:
1630                     continue
1631                 if v1 in G[v3]:
1632                     f.add(frozenset([v1, v2, v3]))
1633                 else:
1634                     for v4 in G[v3]:
1635                         if v4 == v2:
1636                             continue
1637                         if v1 in G[v4]:
1638                             f.add(frozenset([v1, v2, v3, v4]))
1639                         else:
1640                             for v5 in G[v4]:
1641                                 if v5 == v3 or v5 == v2:
1642                                     continue
1643                                 if v1 in G[v5]:
1644                                     f.add(frozenset([v1, v2, v3, v4, v5]))
1645     return f
1646
1647
1648 class TestGraphs(unittest.TestCase):
1649
1650     def test_cube(self):
1651
1652         g = cube(3)                             # vert --> {v1, v2, v3}
1653         vertices1 = set(g)
1654         self.assertEqual(len(vertices1), 8)     # eight vertices
1655         for edge in g.values():
1656             self.assertEqual(len(edge), 3)      # each vertex connects to three edges
1657         vertices2 = set(v for edges in g.values() for v in edges)
1658         self.assertEqual(vertices1, vertices2)  # edge vertices in original set
1659
1660         cubefaces = faces(g)
1661         self.assertEqual(len(cubefaces), 6)     # six faces
1662         for face in cubefaces:
1663             self.assertEqual(len(face), 4)      # each face is a square
1664
1665     def test_cuboctahedron(self):
1666
1667         # http://en.wikipedia.org/wiki/Cuboctahedron
1668         # 8 triangular faces and 6 square faces
1669         # 12 indentical vertices each connecting a triangle and square
1670
1671         g = cube(3)
1672         cuboctahedron = linegraph(g)            # V( --> {V1, V2, V3, V4}
1673         self.assertEqual(len(cuboctahedron), 12)# twelve vertices
1674
1675         vertices = set(cuboctahedron)
1676         for edges in cuboctahedron.values():
1677             self.assertEqual(len(edges), 4)     # each vertex connects to four other vertices
1678         othervertices = set(edge for edges in cuboctahedron.values() for edge in edges)
1679         self.assertEqual(vertices, othervertices)   # edge vertices in original set
1680
1681         cubofaces = faces(cuboctahedron)
1682         facesizes = collections.defaultdict(int)
1683         for face in cubofaces:
1684             facesizes[len(face)] += 1
1685         self.assertEqual(facesizes[3], 8)       # eight triangular faces
1686         self.assertEqual(facesizes[4], 6)       # six square faces
1687
1688         for vertex in cuboctahedron:
1689             edge = vertex                       # Cuboctahedron vertices are edges in Cube
1690             self.assertEqual(len(edge), 2)      # Two cube vertices define an edge
1691             for cubevert in edge:
1692                 self.assertIn(cubevert, g)
1693
1694
1695 #==============================================================================
1696
1697 def test_main(verbose=None):
1698     test_classes = (
1699         TestSet,
1700         TestSetSubclass,
1701         TestSetSubclassWithKeywordArgs,
1702         TestFrozenSet,
1703         TestFrozenSetSubclass,
1704         TestSetOfSets,
1705         TestExceptionPropagation,
1706         TestBasicOpsEmpty,
1707         TestBasicOpsSingleton,
1708         TestBasicOpsTuple,
1709         TestBasicOpsTriple,
1710         TestBinaryOps,
1711         TestUpdateOps,
1712         TestMutate,
1713         TestSubsetEqualEmpty,
1714         TestSubsetEqualNonEmpty,
1715         TestSubsetEmptyNonEmpty,
1716         TestSubsetPartial,
1717         TestSubsetNonOverlap,
1718         TestOnlySetsNumeric,
1719         TestOnlySetsDict,
1720         TestOnlySetsOperator,
1721         TestOnlySetsTuple,
1722         TestOnlySetsString,
1723         TestOnlySetsGenerator,
1724         TestCopyingEmpty,
1725         TestCopyingSingleton,
1726         TestCopyingTriple,
1727         TestCopyingTuple,
1728         TestCopyingNested,
1729         TestIdentities,
1730         TestVariousIteratorArgs,
1731         TestGraphs,
1732         )
1733
1734     test_support.run_unittest(*test_classes)
1735
1736     # verify reference counting
1737     if verbose and hasattr(sys, "gettotalrefcount"):
1738         import gc
1739         counts = [None] * 5
1740         for i in xrange(len(counts)):
1741             test_support.run_unittest(*test_classes)
1742             gc.collect()
1743             counts[i] = sys.gettotalrefcount()
1744         print counts
1745
1746 if __name__ == "__main__":
1747     test_main(verbose=True)