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