Lib/test/test_set.py

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