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 check_repr_against_values(self): 691 text = repr(self.set) 692 self.assertTrue(text.startswith('{')) 693 self.assertTrue(text.endswith('}')) 694 695 result = text[1:-1].split(', ') 696 result.sort() 697 sorted_repr_values = [repr(value) for value in self.values] 698 sorted_repr_values.sort() 699 self.assertEqual(result, sorted_repr_values) 700 701 def test_print(self): 702 fo = open(test_support.TESTFN, "wb") 703 try: 704 print >> fo, self.set, 705 fo.close() 706 fo = open(test_support.TESTFN, "rb") 707 self.assertEqual(fo.read(), repr(self.set)) 708 finally: 709 fo.close() 710 test_support.unlink(test_support.TESTFN) 711 712 def test_length(self): 713 self.assertEqual(len(self.set), self.length) 714 715 def test_self_equality(self): 716 self.assertEqual(self.set, self.set) 717 718 def test_equivalent_equality(self): 719 self.assertEqual(self.set, self.dup) 720 721 def test_copy(self): 722 self.assertEqual(self.set.copy(), self.dup) 723 724 def test_self_union(self): 725 result = self.set | self.set 726 self.assertEqual(result, self.dup) 727 728 def test_empty_union(self): 729 result = self.set | empty_set 730 self.assertEqual(result, self.dup) 731 732 def test_union_empty(self): 733 result = empty_set | self.set 734 self.assertEqual(result, self.dup) 735 736 def test_self_intersection(self): 737 result = self.set & self.set 738 self.assertEqual(result, self.dup) 739 740 def test_empty_intersection(self): 741 result = self.set & empty_set 742 self.assertEqual(result, empty_set) 743 744 def test_intersection_empty(self): 745 result = empty_set & self.set 746 self.assertEqual(result, empty_set) 747 748 def test_self_isdisjoint(self): 749 result = self.set.isdisjoint(self.set) 750 self.assertEqual(result, not self.set) 751 752 def test_empty_isdisjoint(self): 753 result = self.set.isdisjoint(empty_set) 754 self.assertEqual(result, True) 755 756 def test_isdisjoint_empty(self): 757 result = empty_set.isdisjoint(self.set) 758 self.assertEqual(result, True) 759 760 def test_self_symmetric_difference(self): 761 result = self.set ^ self.set 762 self.assertEqual(result, empty_set) 763 764 def test_empty_symmetric_difference(self): 765 result = self.set ^ empty_set 766 self.assertEqual(result, self.set) 767 768 def test_self_difference(self): 769 result = self.set - self.set 770 self.assertEqual(result, empty_set) 771 772 def test_empty_difference(self): 773 result = self.set - empty_set 774 self.assertEqual(result, self.dup) 775 776 def test_empty_difference_rev(self): 777 result = empty_set - self.set 778 self.assertEqual(result, empty_set) 779 780 def test_iteration(self): 781 for v in self.set: 782 self.assertIn(v, self.values) 783 setiter = iter(self.set) 784 # note: __length_hint__ is an internal undocumented API, 785 # don't rely on it in your own programs 786 self.assertEqual(setiter.__length_hint__(), len(self.set)) 787 788 def test_pickling(self): 789 p = pickle.dumps(self.set) 790 copy = pickle.loads(p) 791 self.assertEqual(self.set, copy, 792 "%s != %s" % (self.set, copy)) 793 794 #------------------------------------------------------------------------------ 795 796 class TestBasicOpsEmpty(TestBasicOps): 797 def setUp(self): 798 self.case = "empty set" 799 self.values = [] 800 self.set = set(self.values) 801 self.dup = set(self.values) 802 self.length = 0 803 self.repr = "set([])" 804 805 #------------------------------------------------------------------------------ 806 807 class TestBasicOpsSingleton(TestBasicOps): 808 def setUp(self): 809 self.case = "unit set (number)" 810 self.values = [3] 811 self.set = set(self.values) 812 self.dup = set(self.values) 813 self.length = 1 814 self.repr = "set([3])" 815 816 def test_in(self): 817 self.assertIn(3, self.set) 818 819 def test_not_in(self): 820 self.assertNotIn(2, self.set) 821 822 #------------------------------------------------------------------------------ 823 824 class TestBasicOpsTuple(TestBasicOps): 825 def setUp(self): 826 self.case = "unit set (tuple)" 827 self.values = [(0, "zero")] 828 self.set = set(self.values) 829 self.dup = set(self.values) 830 self.length = 1 831 self.repr = "set([(0, 'zero')])" 832 833 def test_in(self): 834 self.assertIn((0, "zero"), self.set) 835 836 def test_not_in(self): 837 self.assertNotIn(9, self.set) 838 839 #------------------------------------------------------------------------------ 840 841 class TestBasicOpsTriple(TestBasicOps): 842 def setUp(self): 843 self.case = "triple set" 844 self.values = [0, "zero", operator.add] 845 self.set = set(self.values) 846 self.dup = set(self.values) 847 self.length = 3 848 self.repr = None 849 850 #------------------------------------------------------------------------------ 851 852 class TestBasicOpsString(TestBasicOps): 853 def setUp(self): 854 self.case = "string set" 855 self.values = ["a", "b", "c"] 856 self.set = set(self.values) 857 self.dup = set(self.values) 858 self.length = 3 859 860 def test_repr(self): 861 self.check_repr_against_values() 862 863 #------------------------------------------------------------------------------ 864 865 class TestBasicOpsUnicode(TestBasicOps): 866 def setUp(self): 867 self.case = "unicode set" 868 self.values = [u"a", u"b", u"c"] 869 self.set = set(self.values) 870 self.dup = set(self.values) 871 self.length = 3 872 873 def test_repr(self): 874 self.check_repr_against_values() 875 876 #------------------------------------------------------------------------------ 877 878 class TestBasicOpsMixedStringUnicode(TestBasicOps): 879 def setUp(self): 880 self.case = "string and bytes set" 881 self.values = ["a", "b", u"a", u"b"] 882 self.set = set(self.values) 883 self.dup = set(self.values) 884 self.length = 4 885 886 def test_repr(self): 887 with test_support.check_warnings(): 888 self.check_repr_against_values() 889 890 #============================================================================== 891 892 def baditer(): 893 raise TypeError 894 yield True 895 896 def gooditer(): 897 yield True 898 899 class TestExceptionPropagation(unittest.TestCase): 900 """SF 628246: Set constructor should not trap iterator TypeErrors""" 901 902 def test_instanceWithException(self): 903 self.assertRaises(TypeError, set, baditer()) 904 905 def test_instancesWithoutException(self): 906 # All of these iterables should load without exception. 907 set([1,2,3]) 908 set((1,2,3)) 909 set({'one':1, 'two':2, 'three':3}) 910 set(xrange(3)) 911 set('abc') 912 set(gooditer()) 913 914 def test_changingSizeWhileIterating(self): 915 s = set([1,2,3]) 916 try: 917 for i in s: 918 s.update([4]) 919 except RuntimeError: 920 pass 921 else: 922 self.fail("no exception when changing size during iteration") 923 924 #============================================================================== 925 926 class TestSetOfSets(unittest.TestCase): 927 def test_constructor(self): 928 inner = frozenset([1]) 929 outer = set([inner]) 930 element = outer.pop() 931 self.assertEqual(type(element), frozenset) 932 outer.add(inner) # Rebuild set of sets with .add method 933 outer.remove(inner) 934 self.assertEqual(outer, set()) # Verify that remove worked 935 outer.discard(inner) # Absence of KeyError indicates working fine 936 937 #============================================================================== 938 939 class TestBinaryOps(unittest.TestCase): 940 def setUp(self): 941 self.set = set((2, 4, 6)) 942 943 def test_eq(self): # SF bug 643115 944 self.assertEqual(self.set, set({2:1,4:3,6:5})) 945 946 def test_union_subset(self): 947 result = self.set | set([2]) 948 self.assertEqual(result, set((2, 4, 6))) 949 950 def test_union_superset(self): 951 result = self.set | set([2, 4, 6, 8]) 952 self.assertEqual(result, set([2, 4, 6, 8])) 953 954 def test_union_overlap(self): 955 result = self.set | set([3, 4, 5]) 956 self.assertEqual(result, set([2, 3, 4, 5, 6])) 957 958 def test_union_non_overlap(self): 959 result = self.set | set([8]) 960 self.assertEqual(result, set([2, 4, 6, 8])) 961 962 def test_intersection_subset(self): 963 result = self.set & set((2, 4)) 964 self.assertEqual(result, set((2, 4))) 965 966 def test_intersection_superset(self): 967 result = self.set & set([2, 4, 6, 8]) 968 self.assertEqual(result, set([2, 4, 6])) 969 970 def test_intersection_overlap(self): 971 result = self.set & set([3, 4, 5]) 972 self.assertEqual(result, set([4])) 973 974 def test_intersection_non_overlap(self): 975 result = self.set & set([8]) 976 self.assertEqual(result, empty_set) 977 978 def test_isdisjoint_subset(self): 979 result = self.set.isdisjoint(set((2, 4))) 980 self.assertEqual(result, False) 981 982 def test_isdisjoint_superset(self): 983 result = self.set.isdisjoint(set([2, 4, 6, 8])) 984 self.assertEqual(result, False) 985 986 def test_isdisjoint_overlap(self): 987 result = self.set.isdisjoint(set([3, 4, 5])) 988 self.assertEqual(result, False) 989 990 def test_isdisjoint_non_overlap(self): 991 result = self.set.isdisjoint(set([8])) 992 self.assertEqual(result, True) 993 994 def test_sym_difference_subset(self): 995 result = self.set ^ set((2, 4)) 996 self.assertEqual(result, set([6])) 997 998 def test_sym_difference_superset(self): 999 result = self.set ^ set((2, 4, 6, 8)) 1000 self.assertEqual(result, set([8])) 1001 1002 def test_sym_difference_overlap(self): 1003 result = self.set ^ set((3, 4, 5)) 1004 self.assertEqual(result, set([2, 3, 5, 6])) 1005 1006 def test_sym_difference_non_overlap(self): 1007 result = self.set ^ set([8]) 1008 self.assertEqual(result, set([2, 4, 6, 8])) 1009 1010 def test_cmp(self): 1011 a, b = set('a'), set('b') 1012 self.assertRaises(TypeError, cmp, a, b) 1013 1014 # You can view this as a buglet: cmp(a, a) does not raise TypeError, 1015 # because __eq__ is tried before __cmp__, and a.__eq__(a) returns True, 1016 # which Python thinks is good enough to synthesize a cmp() result 1017 # without calling __cmp__. 1018 self.assertEqual(cmp(a, a), 0) 1019 1020 self.assertRaises(TypeError, cmp, a, 12) 1021 self.assertRaises(TypeError, cmp, "abc", a) 1022 1023 #============================================================================== 1024 1025 class TestUpdateOps(unittest.TestCase): 1026 def setUp(self): 1027 self.set = set((2, 4, 6)) 1028 1029 def test_union_subset(self): 1030 self.set |= set([2]) 1031 self.assertEqual(self.set, set((2, 4, 6))) 1032 1033 def test_union_superset(self): 1034 self.set |= set([2, 4, 6, 8]) 1035 self.assertEqual(self.set, set([2, 4, 6, 8])) 1036 1037 def test_union_overlap(self): 1038 self.set |= set([3, 4, 5]) 1039 self.assertEqual(self.set, set([2, 3, 4, 5, 6])) 1040 1041 def test_union_non_overlap(self): 1042 self.set |= set([8]) 1043 self.assertEqual(self.set, set([2, 4, 6, 8])) 1044 1045 def test_union_method_call(self): 1046 self.set.update(set([3, 4, 5])) 1047 self.assertEqual(self.set, set([2, 3, 4, 5, 6])) 1048 1049 def test_intersection_subset(self): 1050 self.set &= set((2, 4)) 1051 self.assertEqual(self.set, set((2, 4))) 1052 1053 def test_intersection_superset(self): 1054 self.set &= set([2, 4, 6, 8]) 1055 self.assertEqual(self.set, set([2, 4, 6])) 1056 1057 def test_intersection_overlap(self): 1058 self.set &= set([3, 4, 5]) 1059 self.assertEqual(self.set, set([4])) 1060 1061 def test_intersection_non_overlap(self): 1062 self.set &= set([8]) 1063 self.assertEqual(self.set, empty_set) 1064 1065 def test_intersection_method_call(self): 1066 self.set.intersection_update(set([3, 4, 5])) 1067 self.assertEqual(self.set, set([4])) 1068 1069 def test_sym_difference_subset(self): 1070 self.set ^= set((2, 4)) 1071 self.assertEqual(self.set, set([6])) 1072 1073 def test_sym_difference_superset(self): 1074 self.set ^= set((2, 4, 6, 8)) 1075 self.assertEqual(self.set, set([8])) 1076 1077 def test_sym_difference_overlap(self): 1078 self.set ^= set((3, 4, 5)) 1079 self.assertEqual(self.set, set([2, 3, 5, 6])) 1080 1081 def test_sym_difference_non_overlap(self): 1082 self.set ^= set([8]) 1083 self.assertEqual(self.set, set([2, 4, 6, 8])) 1084 1085 def test_sym_difference_method_call(self): 1086 self.set.symmetric_difference_update(set([3, 4, 5])) 1087 self.assertEqual(self.set, set([2, 3, 5, 6])) 1088 1089 def test_difference_subset(self): 1090 self.set -= set((2, 4)) 1091 self.assertEqual(self.set, set([6])) 1092 1093 def test_difference_superset(self): 1094 self.set -= set((2, 4, 6, 8)) 1095 self.assertEqual(self.set, set([])) 1096 1097 def test_difference_overlap(self): 1098 self.set -= set((3, 4, 5)) 1099 self.assertEqual(self.set, set([2, 6])) 1100 1101 def test_difference_non_overlap(self): 1102 self.set -= set([8]) 1103 self.assertEqual(self.set, set([2, 4, 6])) 1104 1105 def test_difference_method_call(self): 1106 self.set.difference_update(set([3, 4, 5])) 1107 self.assertEqual(self.set, set([2, 6])) 1108 1109 #============================================================================== 1110 1111 class TestMutate(unittest.TestCase): 1112 def setUp(self): 1113 self.values = ["a", "b", "c"] 1114 self.set = set(self.values) 1115 1116 def test_add_present(self): 1117 self.set.add("c") 1118 self.assertEqual(self.set, set("abc")) 1119 1120 def test_add_absent(self): 1121 self.set.add("d") 1122 self.assertEqual(self.set, set("abcd")) 1123 1124 def test_add_until_full(self): 1125 tmp = set() 1126 expected_len = 0 1127 for v in self.values: 1128 tmp.add(v) 1129 expected_len += 1 1130 self.assertEqual(len(tmp), expected_len) 1131 self.assertEqual(tmp, self.set) 1132 1133 def test_remove_present(self): 1134 self.set.remove("b") 1135 self.assertEqual(self.set, set("ac")) 1136 1137 def test_remove_absent(self): 1138 try: 1139 self.set.remove("d") 1140 self.fail("Removing missing element should have raised LookupError") 1141 except LookupError: 1142 pass 1143 1144 def test_remove_until_empty(self): 1145 expected_len = len(self.set) 1146 for v in self.values: 1147 self.set.remove(v) 1148 expected_len -= 1 1149 self.assertEqual(len(self.set), expected_len) 1150 1151 def test_discard_present(self): 1152 self.set.discard("c") 1153 self.assertEqual(self.set, set("ab")) 1154 1155 def test_discard_absent(self): 1156 self.set.discard("d") 1157 self.assertEqual(self.set, set("abc")) 1158 1159 def test_clear(self): 1160 self.set.clear() 1161 self.assertEqual(len(self.set), 0) 1162 1163 def test_pop(self): 1164 popped = {} 1165 while self.set: 1166 popped[self.set.pop()] = None 1167 self.assertEqual(len(popped), len(self.values)) 1168 for v in self.values: 1169 self.assertIn(v, popped) 1170 1171 def test_update_empty_tuple(self): 1172 self.set.update(()) 1173 self.assertEqual(self.set, set(self.values)) 1174 1175 def test_update_unit_tuple_overlap(self): 1176 self.set.update(("a",)) 1177 self.assertEqual(self.set, set(self.values)) 1178 1179 def test_update_unit_tuple_non_overlap(self): 1180 self.set.update(("a", "z")) 1181 self.assertEqual(self.set, set(self.values + ["z"])) 1182 1183 #============================================================================== 1184 1185 class TestSubsets(unittest.TestCase): 1186 1187 case2method = {"<=": "issubset", 1188 ">=": "issuperset", 1189 } 1190 1191 reverse = {"==": "==", 1192 "!=": "!=", 1193 "<": ">", 1194 ">": "<", 1195 "<=": ">=", 1196 ">=": "<=", 1197 } 1198 1199 def test_issubset(self): 1200 x = self.left 1201 y = self.right 1202 for case in "!=", "==", "<", "<=", ">", ">=": 1203 expected = case in self.cases 1204 # Test the binary infix spelling. 1205 result = eval("x" + case + "y", locals()) 1206 self.assertEqual(result, expected) 1207 # Test the "friendly" method-name spelling, if one exists. 1208 if case in TestSubsets.case2method: 1209 method = getattr(x, TestSubsets.case2method[case]) 1210 result = method(y) 1211 self.assertEqual(result, expected) 1212 1213 # Now do the same for the operands reversed. 1214 rcase = TestSubsets.reverse[case] 1215 result = eval("y" + rcase + "x", locals()) 1216 self.assertEqual(result, expected) 1217 if rcase in TestSubsets.case2method: 1218 method = getattr(y, TestSubsets.case2method[rcase]) 1219 result = method(x) 1220 self.assertEqual(result, expected) 1221 #------------------------------------------------------------------------------ 1222 1223 class TestSubsetEqualEmpty(TestSubsets): 1224 left = set() 1225 right = set() 1226 name = "both empty" 1227 cases = "==", "<=", ">=" 1228 1229 #------------------------------------------------------------------------------ 1230 1231 class TestSubsetEqualNonEmpty(TestSubsets): 1232 left = set([1, 2]) 1233 right = set([1, 2]) 1234 name = "equal pair" 1235 cases = "==", "<=", ">=" 1236 1237 #------------------------------------------------------------------------------ 1238 1239 class TestSubsetEmptyNonEmpty(TestSubsets): 1240 left = set() 1241 right = set([1, 2]) 1242 name = "one empty, one non-empty" 1243 cases = "!=", "<", "<=" 1244 1245 #------------------------------------------------------------------------------ 1246 1247 class TestSubsetPartial(TestSubsets): 1248 left = set([1]) 1249 right = set([1, 2]) 1250 name = "one a non-empty proper subset of other" 1251 cases = "!=", "<", "<=" 1252 1253 #------------------------------------------------------------------------------ 1254 1255 class TestSubsetNonOverlap(TestSubsets): 1256 left = set([1]) 1257 right = set([2]) 1258 name = "neither empty, neither contains" 1259 cases = "!=" 1260 1261 #============================================================================== 1262 1263 class TestOnlySetsInBinaryOps(unittest.TestCase): 1264 1265 def test_eq_ne(self): 1266 # Unlike the others, this is testing that == and != *are* allowed. 1267 self.assertEqual(self.other == self.set, False) 1268 self.assertEqual(self.set == self.other, False) 1269 self.assertEqual(self.other != self.set, True) 1270 self.assertEqual(self.set != self.other, True) 1271 1272 def test_ge_gt_le_lt(self): 1273 self.assertRaises(TypeError, lambda: self.set < self.other) 1274 self.assertRaises(TypeError, lambda: self.set <= self.other) 1275 self.assertRaises(TypeError, lambda: self.set > self.other) 1276 self.assertRaises(TypeError, lambda: self.set >= self.other) 1277 1278 self.assertRaises(TypeError, lambda: self.other < self.set) 1279 self.assertRaises(TypeError, lambda: self.other <= self.set) 1280 self.assertRaises(TypeError, lambda: self.other > self.set) 1281 self.assertRaises(TypeError, lambda: self.other >= self.set) 1282 1283 def test_update_operator(self): 1284 try: 1285 self.set |= self.other 1286 except TypeError: 1287 pass 1288 else: 1289 self.fail("expected TypeError") 1290 1291 def test_update(self): 1292 if self.otherIsIterable: 1293 self.set.update(self.other) 1294 else: 1295 self.assertRaises(TypeError, self.set.update, self.other) 1296 1297 def test_union(self): 1298 self.assertRaises(TypeError, lambda: self.set | self.other) 1299 self.assertRaises(TypeError, lambda: self.other | self.set) 1300 if self.otherIsIterable: 1301 self.set.union(self.other) 1302 else: 1303 self.assertRaises(TypeError, self.set.union, self.other) 1304 1305 def test_intersection_update_operator(self): 1306 try: 1307 self.set &= self.other 1308 except TypeError: 1309 pass 1310 else: 1311 self.fail("expected TypeError") 1312 1313 def test_intersection_update(self): 1314 if self.otherIsIterable: 1315 self.set.intersection_update(self.other) 1316 else: 1317 self.assertRaises(TypeError, 1318 self.set.intersection_update, 1319 self.other) 1320 1321 def test_intersection(self): 1322 self.assertRaises(TypeError, lambda: self.set & self.other) 1323 self.assertRaises(TypeError, lambda: self.other & self.set) 1324 if self.otherIsIterable: 1325 self.set.intersection(self.other) 1326 else: 1327 self.assertRaises(TypeError, self.set.intersection, self.other) 1328 1329 def test_sym_difference_update_operator(self): 1330 try: 1331 self.set ^= self.other 1332 except TypeError: 1333 pass 1334 else: 1335 self.fail("expected TypeError") 1336 1337 def test_sym_difference_update(self): 1338 if self.otherIsIterable: 1339 self.set.symmetric_difference_update(self.other) 1340 else: 1341 self.assertRaises(TypeError, 1342 self.set.symmetric_difference_update, 1343 self.other) 1344 1345 def test_sym_difference(self): 1346 self.assertRaises(TypeError, lambda: self.set ^ self.other) 1347 self.assertRaises(TypeError, lambda: self.other ^ self.set) 1348 if self.otherIsIterable: 1349 self.set.symmetric_difference(self.other) 1350 else: 1351 self.assertRaises(TypeError, self.set.symmetric_difference, self.other) 1352 1353 def test_difference_update_operator(self): 1354 try: 1355 self.set -= self.other 1356 except TypeError: 1357 pass 1358 else: 1359 self.fail("expected TypeError") 1360 1361 def test_difference_update(self): 1362 if self.otherIsIterable: 1363 self.set.difference_update(self.other) 1364 else: 1365 self.assertRaises(TypeError, 1366 self.set.difference_update, 1367 self.other) 1368 1369 def test_difference(self): 1370 self.assertRaises(TypeError, lambda: self.set - self.other) 1371 self.assertRaises(TypeError, lambda: self.other - self.set) 1372 if self.otherIsIterable: 1373 self.set.difference(self.other) 1374 else: 1375 self.assertRaises(TypeError, self.set.difference, self.other) 1376 1377 #------------------------------------------------------------------------------ 1378 1379 class TestOnlySetsNumeric(TestOnlySetsInBinaryOps): 1380 def setUp(self): 1381 self.set = set((1, 2, 3)) 1382 self.other = 19 1383 self.otherIsIterable = False 1384 1385 #------------------------------------------------------------------------------ 1386 1387 class TestOnlySetsDict(TestOnlySetsInBinaryOps): 1388 def setUp(self): 1389 self.set = set((1, 2, 3)) 1390 self.other = {1:2, 3:4} 1391 self.otherIsIterable = True 1392 1393 #------------------------------------------------------------------------------ 1394 1395 class TestOnlySetsOperator(TestOnlySetsInBinaryOps): 1396 def setUp(self): 1397 self.set = set((1, 2, 3)) 1398 self.other = operator.add 1399 self.otherIsIterable = False 1400 1401 def test_ge_gt_le_lt(self): 1402 with test_support.check_py3k_warnings(): 1403 super(TestOnlySetsOperator, self).test_ge_gt_le_lt() 1404 1405 #------------------------------------------------------------------------------ 1406 1407 class TestOnlySetsTuple(TestOnlySetsInBinaryOps): 1408 def setUp(self): 1409 self.set = set((1, 2, 3)) 1410 self.other = (2, 4, 6) 1411 self.otherIsIterable = True 1412 1413 #------------------------------------------------------------------------------ 1414 1415 class TestOnlySetsString(TestOnlySetsInBinaryOps): 1416 def setUp(self): 1417 self.set = set((1, 2, 3)) 1418 self.other = 'abc' 1419 self.otherIsIterable = True 1420 1421 #------------------------------------------------------------------------------ 1422 1423 class TestOnlySetsGenerator(TestOnlySetsInBinaryOps): 1424 def setUp(self): 1425 def gen(): 1426 for i in xrange(0, 10, 2): 1427 yield i 1428 self.set = set((1, 2, 3)) 1429 self.other = gen() 1430 self.otherIsIterable = True 1431 1432 #============================================================================== 1433 1434 class TestCopying(unittest.TestCase): 1435 1436 def test_copy(self): 1437 dup = list(self.set.copy()) 1438 self.assertEqual(len(dup), len(self.set)) 1439 for el in self.set: 1440 self.assertIn(el, dup) 1441 pos = dup.index(el) 1442 self.assertIs(el, dup.pop(pos)) 1443 self.assertFalse(dup) 1444 1445 def test_deep_copy(self): 1446 dup = copy.deepcopy(self.set) 1447 self.assertSetEqual(dup, self.set) 1448 1449 #------------------------------------------------------------------------------ 1450 1451 class TestCopyingEmpty(TestCopying): 1452 def setUp(self): 1453 self.set = set() 1454 1455 #------------------------------------------------------------------------------ 1456 1457 class TestCopyingSingleton(TestCopying): 1458 def setUp(self): 1459 self.set = set(["hello"]) 1460 1461 #------------------------------------------------------------------------------ 1462 1463 class TestCopyingTriple(TestCopying): 1464 def setUp(self): 1465 self.set = set(["zero", 0, None]) 1466 1467 #------------------------------------------------------------------------------ 1468 1469 class TestCopyingTuple(TestCopying): 1470 def setUp(self): 1471 self.set = set([(1, 2)]) 1472 1473 #------------------------------------------------------------------------------ 1474 1475 class TestCopyingNested(TestCopying): 1476 def setUp(self): 1477 self.set = set([((1, 2), (3, 4))]) 1478 1479 #============================================================================== 1480 1481 class TestIdentities(unittest.TestCase): 1482 def setUp(self): 1483 self.a = set('abracadabra') 1484 self.b = set('alacazam') 1485 1486 def test_binopsVsSubsets(self): 1487 a, b = self.a, self.b 1488 self.assertTrue(a - b < a) 1489 self.assertTrue(b - a < b) 1490 self.assertTrue(a & b < a) 1491 self.assertTrue(a & b < b) 1492 self.assertTrue(a | b > a) 1493 self.assertTrue(a | b > b) 1494 self.assertTrue(a ^ b < a | b) 1495 1496 def test_commutativity(self): 1497 a, b = self.a, self.b 1498 self.assertEqual(a&b, b&a) 1499 self.assertEqual(a|b, b|a) 1500 self.assertEqual(a^b, b^a) 1501 if a != b: 1502 self.assertNotEqual(a-b, b-a) 1503 1504 def test_summations(self): 1505 # check that sums of parts equal the whole 1506 a, b = self.a, self.b 1507 self.assertEqual((a-b)|(a&b)|(b-a), a|b) 1508 self.assertEqual((a&b)|(a^b), a|b) 1509 self.assertEqual(a|(b-a), a|b) 1510 self.assertEqual((a-b)|b, a|b) 1511 self.assertEqual((a-b)|(a&b), a) 1512 self.assertEqual((b-a)|(a&b), b) 1513 self.assertEqual((a-b)|(b-a), a^b) 1514 1515 def test_exclusion(self): 1516 # check that inverse operations show non-overlap 1517 a, b, zero = self.a, self.b, set() 1518 self.assertEqual((a-b)&b, zero) 1519 self.assertEqual((b-a)&a, zero) 1520 self.assertEqual((a&b)&(a^b), zero) 1521 1522 # Tests derived from test_itertools.py ======================================= 1523 1524 def R(seqn): 1525 'Regular generator' 1526 for i in seqn: 1527 yield i 1528 1529 class G: 1530 'Sequence using __getitem__' 1531 def __init__(self, seqn): 1532 self.seqn = seqn 1533 def __getitem__(self, i): 1534 return self.seqn[i] 1535 1536 class I: 1537 'Sequence using iterator protocol' 1538 def __init__(self, seqn): 1539 self.seqn = seqn 1540 self.i = 0 1541 def __iter__(self): 1542 return self 1543 def next(self): 1544 if self.i >= len(self.seqn): raise StopIteration 1545 v = self.seqn[self.i] 1546 self.i += 1 1547 return v 1548 1549 class Ig: 1550 'Sequence using iterator protocol defined with a generator' 1551 def __init__(self, seqn): 1552 self.seqn = seqn 1553 self.i = 0 1554 def __iter__(self): 1555 for val in self.seqn: 1556 yield val 1557 1558 class X: 1559 'Missing __getitem__ and __iter__' 1560 def __init__(self, seqn): 1561 self.seqn = seqn 1562 self.i = 0 1563 def next(self): 1564 if self.i >= len(self.seqn): raise StopIteration 1565 v = self.seqn[self.i] 1566 self.i += 1 1567 return v 1568 1569 class N: 1570 'Iterator missing next()' 1571 def __init__(self, seqn): 1572 self.seqn = seqn 1573 self.i = 0 1574 def __iter__(self): 1575 return self 1576 1577 class E: 1578 'Test propagation of exceptions' 1579 def __init__(self, seqn): 1580 self.seqn = seqn 1581 self.i = 0 1582 def __iter__(self): 1583 return self 1584 def next(self): 1585 3 // 0 1586 1587 class S: 1588 'Test immediate stop' 1589 def __init__(self, seqn): 1590 pass 1591 def __iter__(self): 1592 return self 1593 def next(self): 1594 raise StopIteration 1595 1596 from itertools import chain, imap 1597 def L(seqn): 1598 'Test multiple tiers of iterators' 1599 return chain(imap(lambda x:x, R(Ig(G(seqn))))) 1600 1601 class TestVariousIteratorArgs(unittest.TestCase): 1602 1603 def test_constructor(self): 1604 for cons in (set, frozenset): 1605 for s in ("123", "", range(1000), ('do', 1.2), xrange(2000,2200,5)): 1606 for g in (G, I, Ig, S, L, R): 1607 self.assertSetEqual(cons(g(s)), set(g(s))) 1608 self.assertRaises(TypeError, cons , X(s)) 1609 self.assertRaises(TypeError, cons , N(s)) 1610 self.assertRaises(ZeroDivisionError, cons , E(s)) 1611 1612 def test_inline_methods(self): 1613 s = set('november') 1614 for data in ("123", "", range(1000), ('do', 1.2), xrange(2000,2200,5), 'december'): 1615 for meth in (s.union, s.intersection, s.difference, s.symmetric_difference, s.isdisjoint): 1616 for g in (G, I, Ig, L, R): 1617 expected = meth(data) 1618 actual = meth(G(data)) 1619 if isinstance(expected, bool): 1620 self.assertEqual(actual, expected) 1621 else: 1622 self.assertSetEqual(actual, expected) 1623 self.assertRaises(TypeError, meth, X(s)) 1624 self.assertRaises(TypeError, meth, N(s)) 1625 self.assertRaises(ZeroDivisionError, meth, E(s)) 1626 1627 def test_inplace_methods(self): 1628 for data in ("123", "", range(1000), ('do', 1.2), xrange(2000,2200,5), 'december'): 1629 for methname in ('update', 'intersection_update', 1630 'difference_update', 'symmetric_difference_update'): 1631 for g in (G, I, Ig, S, L, R): 1632 s = set('january') 1633 t = s.copy() 1634 getattr(s, methname)(list(g(data))) 1635 getattr(t, methname)(g(data)) 1636 self.assertSetEqual(s, t) 1637 1638 self.assertRaises(TypeError, getattr(set('january'), methname), X(data)) 1639 self.assertRaises(TypeError, getattr(set('january'), methname), N(data)) 1640 self.assertRaises(ZeroDivisionError, getattr(set('january'), methname), E(data)) 1641 1642 class bad_eq: 1643 def __eq__(self, other): 1644 if be_bad: 1645 set2.clear() 1646 raise ZeroDivisionError 1647 return self is other 1648 def __hash__(self): 1649 return 0 1650 1651 class bad_dict_clear: 1652 def __eq__(self, other): 1653 if be_bad: 1654 dict2.clear() 1655 return self is other 1656 def __hash__(self): 1657 return 0 1658 1659 class TestWeirdBugs(unittest.TestCase): 1660 def test_8420_set_merge(self): 1661 # This used to segfault 1662 global be_bad, set2, dict2 1663 be_bad = False 1664 set1 = {bad_eq()} 1665 set2 = {bad_eq() for i in range(75)} 1666 be_bad = True 1667 self.assertRaises(ZeroDivisionError, set1.update, set2) 1668 1669 be_bad = False 1670 set1 = {bad_dict_clear()} 1671 dict2 = {bad_dict_clear(): None} 1672 be_bad = True 1673 set1.symmetric_difference_update(dict2) 1674 1675 # Application tests (based on David Eppstein's graph recipes ==================================== 1676 1677 def powerset(U): 1678 """Generates all subsets of a set or sequence U.""" 1679 U = iter(U) 1680 try: 1681 x = frozenset([U.next()]) 1682 for S in powerset(U): 1683 yield S 1684 yield S | x 1685 except StopIteration: 1686 yield frozenset() 1687 1688 def cube(n): 1689 """Graph of n-dimensional hypercube.""" 1690 singletons = [frozenset([x]) for x in range(n)] 1691 return dict([(x, frozenset([x^s for s in singletons])) 1692 for x in powerset(range(n))]) 1693 1694 def linegraph(G): 1695 """Graph, the vertices of which are edges of G, 1696 with two vertices being adjacent iff the corresponding 1697 edges share a vertex.""" 1698 L = {} 1699 for x in G: 1700 for y in G[x]: 1701 nx = [frozenset([x,z]) for z in G[x] if z != y] 1702 ny = [frozenset([y,z]) for z in G[y] if z != x] 1703 L[frozenset([x,y])] = frozenset(nx+ny) 1704 return L 1705 1706 def faces(G): 1707 'Return a set of faces in G. Where a face is a set of vertices on that face' 1708 # currently limited to triangles,squares, and pentagons 1709 f = set() 1710 for v1, edges in G.items(): 1711 for v2 in edges: 1712 for v3 in G[v2]: 1713 if v1 == v3: 1714 continue 1715 if v1 in G[v3]: 1716 f.add(frozenset([v1, v2, v3])) 1717 else: 1718 for v4 in G[v3]: 1719 if v4 == v2: 1720 continue 1721 if v1 in G[v4]: 1722 f.add(frozenset([v1, v2, v3, v4])) 1723 else: 1724 for v5 in G[v4]: 1725 if v5 == v3 or v5 == v2: 1726 continue 1727 if v1 in G[v5]: 1728 f.add(frozenset([v1, v2, v3, v4, v5])) 1729 return f 1730 1731 1732 class TestGraphs(unittest.TestCase): 1733 1734 def test_cube(self): 1735 1736 g = cube(3) # vert --> {v1, v2, v3} 1737 vertices1 = set(g) 1738 self.assertEqual(len(vertices1), 8) # eight vertices 1739 for edge in g.values(): 1740 self.assertEqual(len(edge), 3) # each vertex connects to three edges 1741 vertices2 = set(v for edges in g.values() for v in edges) 1742 self.assertEqual(vertices1, vertices2) # edge vertices in original set 1743 1744 cubefaces = faces(g) 1745 self.assertEqual(len(cubefaces), 6) # six faces 1746 for face in cubefaces: 1747 self.assertEqual(len(face), 4) # each face is a square 1748 1749 def test_cuboctahedron(self): 1750 1751 # http://en.wikipedia.org/wiki/Cuboctahedron 1752 # 8 triangular faces and 6 square faces 1753 # 12 indentical vertices each connecting a triangle and square 1754 1755 g = cube(3) 1756 cuboctahedron = linegraph(g) # V( --> {V1, V2, V3, V4} 1757 self.assertEqual(len(cuboctahedron), 12)# twelve vertices 1758 1759 vertices = set(cuboctahedron) 1760 for edges in cuboctahedron.values(): 1761 self.assertEqual(len(edges), 4) # each vertex connects to four other vertices 1762 othervertices = set(edge for edges in cuboctahedron.values() for edge in edges) 1763 self.assertEqual(vertices, othervertices) # edge vertices in original set 1764 1765 cubofaces = faces(cuboctahedron) 1766 facesizes = collections.defaultdict(int) 1767 for face in cubofaces: 1768 facesizes[len(face)] += 1 1769 self.assertEqual(facesizes[3], 8) # eight triangular faces 1770 self.assertEqual(facesizes[4], 6) # six square faces 1771 1772 for vertex in cuboctahedron: 1773 edge = vertex # Cuboctahedron vertices are edges in Cube 1774 self.assertEqual(len(edge), 2) # Two cube vertices define an edge 1775 for cubevert in edge: 1776 self.assertIn(cubevert, g) 1777 1778 1779 #============================================================================== 1780 1781 def test_main(verbose=None): 1782 test_classes = ( 1783 TestSet, 1784 TestSetSubclass, 1785 TestSetSubclassWithKeywordArgs, 1786 TestFrozenSet, 1787 TestFrozenSetSubclass, 1788 TestSetOfSets, 1789 TestExceptionPropagation, 1790 TestBasicOpsEmpty, 1791 TestBasicOpsSingleton, 1792 TestBasicOpsTuple, 1793 TestBasicOpsTriple, 1794 TestBinaryOps, 1795 TestUpdateOps, 1796 TestMutate, 1797 TestSubsetEqualEmpty, 1798 TestSubsetEqualNonEmpty, 1799 TestSubsetEmptyNonEmpty, 1800 TestSubsetPartial, 1801 TestSubsetNonOverlap, 1802 TestOnlySetsNumeric, 1803 TestOnlySetsDict, 1804 TestOnlySetsOperator, 1805 TestOnlySetsTuple, 1806 TestOnlySetsString, 1807 TestOnlySetsGenerator, 1808 TestCopyingEmpty, 1809 TestCopyingSingleton, 1810 TestCopyingTriple, 1811 TestCopyingTuple, 1812 TestCopyingNested, 1813 TestIdentities, 1814 TestVariousIteratorArgs, 1815 TestGraphs, 1816 TestWeirdBugs, 1817 ) 1818 1819 test_support.run_unittest(*test_classes) 1820 1821 # verify reference counting 1822 if verbose and hasattr(sys, "gettotalrefcount"): 1823 import gc 1824 counts = [None] * 5 1825 for i in xrange(len(counts)): 1826 test_support.run_unittest(*test_classes) 1827 gc.collect() 1828 counts[i] = sys.gettotalrefcount() 1829 print counts 1830 1831 if __name__ == "__main__": 1832 test_main(verbose=True) 1833
