1 import unittest

     2 from test import test_support

     3 from weakref import proxy

     4 import operator

     5 import copy

     6 import pickle

     7 import os

     8 from random import randrange, shuffle

     9 import sys

    10 import collections

    11 

    12 class PassThru(Exception):

    13     pass

    14 

    15 def check_pass_thru():

    16     raise PassThru

    17     yield 1

    18 

    19 class BadCmp:

    20     def __hash__(self):

    21         return 1

    22     def __cmp__(self, other):

    23         raise RuntimeError

    24 

    25 class ReprWrapper:

    26     'Used to test self-referential repr() calls'

    27     def __repr__(self):

    28         return repr(self.value)

    29 

    30 class HashCountingInt(int):

    31     'int-like object that counts the number of times __hash__ is called'

    32     def __init__(self, *args):

    33         self.hash_count = 0

    34     def __hash__(self):

    35         self.hash_count += 1

    36         return int.__hash__(self)

    37 

    38 class TestJointOps(unittest.TestCase):

    39     # Tests common to both set and frozenset

    40 

    41     def setUp(self):

    42         self.word = word = 'simsalabim'

    43         self.otherword = 'madagascar'

    44         self.letters = 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ'

    45         self.s = self.thetype(word)

    46         self.d = dict.fromkeys(word)

    47 

    48     def test_new_or_init(self):

    49         self.assertRaises(TypeError, self.thetype, [], 2)

    50 

    51     def test_uniquification(self):

    52         actual = sorted(self.s)

    53         expected = sorted(self.d)

    54         self.assertEqual(actual, expected)

    55         self.assertRaises(PassThru, self.thetype, check_pass_thru())

    56         self.assertRaises(TypeError, self.thetype, [[]])

    57 

    58     def test_len(self):

    59         self.assertEqual(len(self.s), len(self.d))

    60 

    61     def test_contains(self):

    62         for c in self.letters:

    63             self.assertEqual(c in self.s, c in self.d)

    64         self.assertRaises(TypeError, self.s.__contains__, [[]])

    65         s = self.thetype([frozenset(self.letters)])

    66         self.assert_(self.thetype(self.letters) in s)

    67 

    68     def test_union(self):

    69         u = self.s.union(self.otherword)

    70         for c in self.letters:

    71             self.assertEqual(c in u, c in self.d or c in self.otherword)

    72         self.assertEqual(self.s, self.thetype(self.word))

    73         self.assertEqual(type(u), self.thetype)

    74         self.assertRaises(PassThru, self.s.union, check_pass_thru())

    75         self.assertRaises(TypeError, self.s.union, [[]])

    76         for C in set, frozenset, dict.fromkeys, str, unicode, list, tuple:

    77             self.assertEqual(self.thetype('abcba').union(C('cdc')), set('abcd'))

    78             self.assertEqual(self.thetype('abcba').union(C('efgfe')), set('abcefg'))

    79             self.assertEqual(self.thetype('abcba').union(C('ccb')), set('abc'))

    80             self.assertEqual(self.thetype('abcba').union(C('ef')), set('abcef'))

    81             self.assertEqual(self.thetype('abcba').union(C('ef'), C('fg')), set('abcefg'))

    82 

    83     def test_or(self):

    84         i = self.s.union(self.otherword)

    85         self.assertEqual(self.s | set(self.otherword), i)

    86         self.assertEqual(self.s | frozenset(self.otherword), i)

    87         try:

    88             self.s | self.otherword

    89         except TypeError:

    90             pass

    91         else:

    92             self.fail("s|t did not screen-out general iterables")

    93 

    94     def test_intersection(self):

    95         i = self.s.intersection(self.otherword)

    96         for c in self.letters:

    97             self.assertEqual(c in i, c in self.d and c in self.otherword)

    98         self.assertEqual(self.s, self.thetype(self.word))

    99         self.assertEqual(type(i), self.thetype)

   100         self.assertRaises(PassThru, self.s.intersection, check_pass_thru())

   101         for C in set, frozenset, dict.fromkeys, str, unicode, list, tuple:

   102             self.assertEqual(self.thetype('abcba').intersection(C('cdc')), set('cc'))

   103             self.assertEqual(self.thetype('abcba').intersection(C('efgfe')), set(''))

   104             self.assertEqual(self.thetype('abcba').intersection(C('ccb')), set('bc'))

   105             self.assertEqual(self.thetype('abcba').intersection(C('ef')), set(''))

   106             self.assertEqual(self.thetype('abcba').intersection(C('cbcf'), C('bag')), set('b'))

   107         s = self.thetype('abcba')

   108         z = s.intersection()

   109         if self.thetype == frozenset():

   110             self.assertEqual(id(s), id(z))

   111         else:

   112             self.assertNotEqual(id(s), id(z))

   113 

   114     def test_isdisjoint(self):

   115         def f(s1, s2):

   116             'Pure python equivalent of isdisjoint()'

   117             return not set(s1).intersection(s2)

   118         for larg in '', 'a', 'ab', 'abc', 'ababac', 'cdc', 'cc', 'efgfe', 'ccb', 'ef':

   119             s1 = self.thetype(larg)

   120             for rarg in '', 'a', 'ab', 'abc', 'ababac', 'cdc', 'cc', 'efgfe', 'ccb', 'ef':

   121                 for C in set, frozenset, dict.fromkeys, str, unicode, list, tuple:

   122                     s2 = C(rarg)

   123                     actual = s1.isdisjoint(s2)

   124                     expected = f(s1, s2)

   125                     self.assertEqual(actual, expected)

   126                     self.assert_(actual is True or actual is False)

   127 

   128     def test_and(self):

   129         i = self.s.intersection(self.otherword)

   130         self.assertEqual(self.s & set(self.otherword), i)

   131         self.assertEqual(self.s & frozenset(self.otherword), i)

   132         try:

   133             self.s & self.otherword

   134         except TypeError:

   135             pass

   136         else:

   137             self.fail("s&t did not screen-out general iterables")

   138 

   139     def test_difference(self):

   140         i = self.s.difference(self.otherword)

   141         for c in self.letters:

   142             self.assertEqual(c in i, c in self.d and c not in self.otherword)

   143         self.assertEqual(self.s, self.thetype(self.word))

   144         self.assertEqual(type(i), self.thetype)

   145         self.assertRaises(PassThru, self.s.difference, check_pass_thru())

   146         self.assertRaises(TypeError, self.s.difference, [[]])

   147         for C in set, frozenset, dict.fromkeys, str, unicode, list, tuple:

   148             self.assertEqual(self.thetype('abcba').difference(C('cdc')), set('ab'))

   149             self.assertEqual(self.thetype('abcba').difference(C('efgfe')), set('abc'))

   150             self.assertEqual(self.thetype('abcba').difference(C('ccb')), set('a'))

   151             self.assertEqual(self.thetype('abcba').difference(C('ef')), set('abc'))

   152             self.assertEqual(self.thetype('abcba').difference(), set('abc'))

   153             self.assertEqual(self.thetype('abcba').difference(C('a'), C('b')), set('c'))

   154 

   155     def test_sub(self):

   156         i = self.s.difference(self.otherword)

   157         self.assertEqual(self.s - set(self.otherword), i)

   158         self.assertEqual(self.s - frozenset(self.otherword), i)

   159         try:

   160             self.s - self.otherword

   161         except TypeError:

   162             pass

   163         else:

   164             self.fail("s-t did not screen-out general iterables")

   165 

   166     def test_symmetric_difference(self):

   167         i = self.s.symmetric_difference(self.otherword)

   168         for c in self.letters:

   169             self.assertEqual(c in i, (c in self.d) ^ (c in self.otherword))

   170         self.assertEqual(self.s, self.thetype(self.word))

   171         self.assertEqual(type(i), self.thetype)

   172         self.assertRaises(PassThru, self.s.symmetric_difference, check_pass_thru())

   173         self.assertRaises(TypeError, self.s.symmetric_difference, [[]])

   174         for C in set, frozenset, dict.fromkeys, str, unicode, list, tuple:

   175             self.assertEqual(self.thetype('abcba').symmetric_difference(C('cdc')), set('abd'))

   176             self.assertEqual(self.thetype('abcba').symmetric_difference(C('efgfe')), set('abcefg'))

   177             self.assertEqual(self.thetype('abcba').symmetric_difference(C('ccb')), set('a'))

   178             self.assertEqual(self.thetype('abcba').symmetric_difference(C('ef')), set('abcef'))

   179 

   180     def test_xor(self):

   181         i = self.s.symmetric_difference(self.otherword)

   182         self.assertEqual(self.s ^ set(self.otherword), i)

   183         self.assertEqual(self.s ^ frozenset(self.otherword), i)

   184         try:

   185             self.s ^ self.otherword

   186         except TypeError:

   187             pass

   188         else:

   189             self.fail("s^t did not screen-out general iterables")

   190 

   191     def test_equality(self):

   192         self.assertEqual(self.s, set(self.word))

   193         self.assertEqual(self.s, frozenset(self.word))

   194         self.assertEqual(self.s == self.word, False)

   195         self.assertNotEqual(self.s, set(self.otherword))

   196         self.assertNotEqual(self.s, frozenset(self.otherword))

   197         self.assertEqual(self.s != self.word, True)

   198 

   199     def test_setOfFrozensets(self):

   200         t = map(frozenset, ['abcdef', 'bcd', 'bdcb', 'fed', 'fedccba'])

   201         s = self.thetype(t)

   202         self.assertEqual(len(s), 3)

   203 

   204     def test_compare(self):

   205         self.assertRaises(TypeError, self.s.__cmp__, self.s)

   206 

   207     def test_sub_and_super(self):

   208         p, q, r = map(self.thetype, ['ab', 'abcde', 'def'])

   209         self.assert_(p < q)

   210         self.assert_(p <= q)

   211         self.assert_(q <= q)

   212         self.assert_(q > p)

   213         self.assert_(q >= p)

   214         self.failIf(q < r)

   215         self.failIf(q <= r)

   216         self.failIf(q > r)

   217         self.failIf(q >= r)

   218         self.assert_(set('a').issubset('abc'))

   219         self.assert_(set('abc').issuperset('a'))

   220         self.failIf(set('a').issubset('cbs'))

   221         self.failIf(set('cbs').issuperset('a'))

   222 

   223     def test_pickling(self):

   224         for i in (0, 1, 2):

   225             p = pickle.dumps(self.s, i)

   226             dup = pickle.loads(p)

   227             self.assertEqual(self.s, dup, "%s != %s" % (self.s, dup))

   228             if type(self.s) not in (set, frozenset):

   229                 self.s.x = 10

   230                 p = pickle.dumps(self.s)

   231                 dup = pickle.loads(p)

   232                 self.assertEqual(self.s.x, dup.x)

   233 

   234     def test_deepcopy(self):

   235         class Tracer:

   236             def __init__(self, value):

   237                 self.value = value

   238             def __hash__(self):

   239                 return self.value

   240             def __deepcopy__(self, memo=None):

   241                 return Tracer(self.value + 1)

   242         t = Tracer(10)

   243         s = self.thetype([t])

   244         dup = copy.deepcopy(s)

   245         self.assertNotEqual(id(s), id(dup))

   246         for elem in dup:

   247             newt = elem

   248         self.assertNotEqual(id(t), id(newt))

   249         self.assertEqual(t.value + 1, newt.value)

   250 

   251     def test_gc(self):

   252         # Create a nest of cycles to exercise overall ref count check

   253         class A:

   254             pass

   255         s = set(A() for i in xrange(1000))

   256         for elem in s:

   257             elem.cycle = s

   258             elem.sub = elem

   259             elem.set = set([elem])

   260 

   261     def test_subclass_with_custom_hash(self):

   262         # Bug #1257731

   263         class H(self.thetype):

   264             def __hash__(self):

   265                 return int(id(self) & 0x7fffffff)

   266         s=H()

   267         f=set()

   268         f.add(s)

   269         self.assert_(s in f)

   270         f.remove(s)

   271         f.add(s)

   272         f.discard(s)

   273 

   274     def test_badcmp(self):

   275         s = self.thetype([BadCmp()])

   276         # Detect comparison errors during insertion and lookup

   277         self.assertRaises(RuntimeError, self.thetype, [BadCmp(), BadCmp()])

   278         self.assertRaises(RuntimeError, s.__contains__, BadCmp())

   279         # Detect errors during mutating operations

   280         if hasattr(s, 'add'):

   281             self.assertRaises(RuntimeError, s.add, BadCmp())

   282             self.assertRaises(RuntimeError, s.discard, BadCmp())

   283             self.assertRaises(RuntimeError, s.remove, BadCmp())

   284 

   285     def test_cyclical_repr(self):

   286         w = ReprWrapper()

   287         s = self.thetype([w])

   288         w.value = s

   289         name = repr(s).partition('(')[0]    # strip class name from repr string

   290         self.assertEqual(repr(s), '%s([%s(...)])' % (name, name))

   291 

   292     def test_cyclical_print(self):

   293         w = ReprWrapper()

   294         s = self.thetype([w])

   295         w.value = s

   296         fo = open(test_support.TESTFN, "wb")

   297         try:

   298             print >> fo, s,

   299             fo.close()

   300             fo = open(test_support.TESTFN, "rb")

   301             self.assertEqual(fo.read(), repr(s))

   302         finally:

   303             fo.close()

   304             test_support.unlink(test_support.TESTFN)

   305 

   306     def test_do_not_rehash_dict_keys(self):

   307         n = 10

   308         d = dict.fromkeys(map(HashCountingInt, xrange(n)))

   309         self.assertEqual(sum(elem.hash_count for elem in d), n)

   310         s = self.thetype(d)

   311         self.assertEqual(sum(elem.hash_count for elem in d), n)

   312         s.difference(d)

   313         self.assertEqual(sum(elem.hash_count for elem in d), n)

   314         if hasattr(s, 'symmetric_difference_update'):

   315             s.symmetric_difference_update(d)

   316         self.assertEqual(sum(elem.hash_count for elem in d), n)

   317         d2 = dict.fromkeys(set(d))

   318         self.assertEqual(sum(elem.hash_count for elem in d), n)

   319         d3 = dict.fromkeys(frozenset(d))

   320         self.assertEqual(sum(elem.hash_count for elem in d), n)

   321         d3 = dict.fromkeys(frozenset(d), 123)

   322         self.assertEqual(sum(elem.hash_count for elem in d), n)

   323         self.assertEqual(d3, dict.fromkeys(d, 123))

   324 

   325 class TestSet(TestJointOps):

   326     thetype = set

   327 

   328     def test_init(self):

   329         s = self.thetype()

   330         s.__init__(self.word)

   331         self.assertEqual(s, set(self.word))

   332         s.__init__(self.otherword)

   333         self.assertEqual(s, set(self.otherword))

   334         self.assertRaises(TypeError, s.__init__, s, 2);

   335         self.assertRaises(TypeError, s.__init__, 1);

   336 

   337     def test_constructor_identity(self):

   338         s = self.thetype(range(3))

   339         t = self.thetype(s)

   340         self.assertNotEqual(id(s), id(t))

   341 

   342     def test_hash(self):

   343         self.assertRaises(TypeError, hash, self.s)

   344 

   345     def test_clear(self):

   346         self.s.clear()

   347         self.assertEqual(self.s, set())

   348         self.assertEqual(len(self.s), 0)

   349 

   350     def test_copy(self):

   351         dup = self.s.copy()

   352         self.assertEqual(self.s, dup)

   353         self.assertNotEqual(id(self.s), id(dup))

   354 

   355     def test_add(self):

   356         self.s.add('Q')

   357         self.assert_('Q' in self.s)

   358         dup = self.s.copy()

   359         self.s.add('Q')

   360         self.assertEqual(self.s, dup)

   361         self.assertRaises(TypeError, self.s.add, [])

   362 

   363     def test_remove(self):

   364         self.s.remove('a')

   365         self.assert_('a' not in self.s)

   366         self.assertRaises(KeyError, self.s.remove, 'Q')

   367         self.assertRaises(TypeError, self.s.remove, [])

   368         s = self.thetype([frozenset(self.word)])

   369         self.assert_(self.thetype(self.word) in s)

   370         s.remove(self.thetype(self.word))

   371         self.assert_(self.thetype(self.word) not in s)

   372         self.assertRaises(KeyError, self.s.remove, self.thetype(self.word))

   373 

   374     def test_remove_keyerror_unpacking(self):

   375         # bug:  www.python.org/sf/1576657

   376         for v1 in ['Q', (1,)]:

   377             try:

   378                 self.s.remove(v1)

   379             except KeyError, e:

   380                 v2 = e.args[0]

   381                 self.assertEqual(v1, v2)

   382             else:

   383                 self.fail()

   384 

   385     def test_remove_keyerror_set(self):

   386         key = self.thetype([3, 4])

   387         try:

   388             self.s.remove(key)

   389         except KeyError as e:

   390             self.assert_(e.args[0] is key,

   391                          "KeyError should be {0}, not {1}".format(key,

   392                                                                   e.args[0]))

   393         else:

   394             self.fail()

   395 

   396     def test_discard(self):

   397         self.s.discard('a')

   398         self.assert_('a' not in self.s)

   399         self.s.discard('Q')

   400         self.assertRaises(TypeError, self.s.discard, [])

   401         s = self.thetype([frozenset(self.word)])

   402         self.assert_(self.thetype(self.word) in s)

   403         s.discard(self.thetype(self.word))

   404         self.assert_(self.thetype(self.word) not in s)

   405         s.discard(self.thetype(self.word))

   406 

   407     def test_pop(self):

   408         for i in xrange(len(self.s)):

   409             elem = self.s.pop()

   410             self.assert_(elem not in self.s)

   411         self.assertRaises(KeyError, self.s.pop)

   412 

   413     def test_update(self):

   414         retval = self.s.update(self.otherword)

   415         self.assertEqual(retval, None)

   416         for c in (self.word + self.otherword):

   417             self.assert_(c in self.s)

   418         self.assertRaises(PassThru, self.s.update, check_pass_thru())

   419         self.assertRaises(TypeError, self.s.update, [[]])

   420         for p, q in (('cdc', 'abcd'), ('efgfe', 'abcefg'), ('ccb', 'abc'), ('ef', 'abcef')):

   421             for C in set, frozenset, dict.fromkeys, str, unicode, list, tuple:

   422                 s = self.thetype('abcba')

   423                 self.assertEqual(s.update(C(p)), None)

   424                 self.assertEqual(s, set(q))

   425         for p in ('cdc', 'efgfe', 'ccb', 'ef', 'abcda'):

   426             q = 'ahi'

   427             for C in set, frozenset, dict.fromkeys, str, unicode, list, tuple:

   428                 s = self.thetype('abcba')

   429                 self.assertEqual(s.update(C(p), C(q)), None)

   430                 self.assertEqual(s, set(s) | set(p) | set(q))

   431 

   432     def test_ior(self):

   433         self.s |= set(self.otherword)

   434         for c in (self.word + self.otherword):

   435             self.assert_(c in self.s)

   436 

   437     def test_intersection_update(self):

   438         retval = self.s.intersection_update(self.otherword)

   439         self.assertEqual(retval, None)

   440         for c in (self.word + self.otherword):

   441             if c in self.otherword and c in self.word:

   442                 self.assert_(c in self.s)

   443             else:

   444                 self.assert_(c not in self.s)

   445         self.assertRaises(PassThru, self.s.intersection_update, check_pass_thru())

   446         self.assertRaises(TypeError, self.s.intersection_update, [[]])

   447         for p, q in (('cdc', 'c'), ('efgfe', ''), ('ccb', 'bc'), ('ef', '')):

   448             for C in set, frozenset, dict.fromkeys, str, unicode, list, tuple:

   449                 s = self.thetype('abcba')

   450                 self.assertEqual(s.intersection_update(C(p)), None)

   451                 self.assertEqual(s, set(q))

   452                 ss = 'abcba'

   453                 s = self.thetype(ss)

   454                 t = 'cbc'

   455                 self.assertEqual(s.intersection_update(C(p), C(t)), None)

   456                 self.assertEqual(s, set('abcba')&set(p)&set(t))

   457 

   458     def test_iand(self):

   459         self.s &= set(self.otherword)

   460         for c in (self.word + self.otherword):

   461             if c in self.otherword and c in self.word:

   462                 self.assert_(c in self.s)

   463             else:

   464                 self.assert_(c not in self.s)

   465 

   466     def test_difference_update(self):

   467         retval = self.s.difference_update(self.otherword)

   468         self.assertEqual(retval, None)

   469         for c in (self.word + self.otherword):

   470             if c in self.word and c not in self.otherword:

   471                 self.assert_(c in self.s)

   472             else:

   473                 self.assert_(c not in self.s)

   474         self.assertRaises(PassThru, self.s.difference_update, check_pass_thru())

   475         self.assertRaises(TypeError, self.s.difference_update, [[]])

   476         self.assertRaises(TypeError, self.s.symmetric_difference_update, [[]])

   477         for p, q in (('cdc', 'ab'), ('efgfe', 'abc'), ('ccb', 'a'), ('ef', 'abc')):

   478             for C in set, frozenset, dict.fromkeys, str, unicode, list, tuple:

   479                 s = self.thetype('abcba')

   480                 self.assertEqual(s.difference_update(C(p)), None)

   481                 self.assertEqual(s, set(q))

   482 

   483                 s = self.thetype('abcdefghih')

   484                 s.difference_update()

   485                 self.assertEqual(s, self.thetype('abcdefghih'))

   486 

   487                 s = self.thetype('abcdefghih')

   488                 s.difference_update(C('aba'))

   489                 self.assertEqual(s, self.thetype('cdefghih'))

   490 

   491                 s = self.thetype('abcdefghih')

   492                 s.difference_update(C('cdc'), C('aba'))

   493                 self.assertEqual(s, self.thetype('efghih'))

   494 

   495     def test_isub(self):

   496         self.s -= set(self.otherword)

   497         for c in (self.word + self.otherword):

   498             if c in self.word and c not in self.otherword:

   499                 self.assert_(c in self.s)

   500             else:

   501                 self.assert_(c not in self.s)

   502 

   503     def test_symmetric_difference_update(self):

   504         retval = self.s.symmetric_difference_update(self.otherword)

   505         self.assertEqual(retval, None)

   506         for c in (self.word + self.otherword):

   507             if (c in self.word) ^ (c in self.otherword):

   508                 self.assert_(c in self.s)

   509             else:

   510                 self.assert_(c not in self.s)

   511         self.assertRaises(PassThru, self.s.symmetric_difference_update, check_pass_thru())

   512         self.assertRaises(TypeError, self.s.symmetric_difference_update, [[]])

   513         for p, q in (('cdc', 'abd'), ('efgfe', 'abcefg'), ('ccb', 'a'), ('ef', 'abcef')):

   514             for C in set, frozenset, dict.fromkeys, str, unicode, list, tuple:

   515                 s = self.thetype('abcba')

   516                 self.assertEqual(s.symmetric_difference_update(C(p)), None)

   517                 self.assertEqual(s, set(q))

   518 

   519     def test_ixor(self):

   520         self.s ^= set(self.otherword)

   521         for c in (self.word + self.otherword):

   522             if (c in self.word) ^ (c in self.otherword):

   523                 self.assert_(c in self.s)

   524             else:

   525                 self.assert_(c not in self.s)

   526 

   527     def test_inplace_on_self(self):

   528         t = self.s.copy()

   529         t |= t

   530         self.assertEqual(t, self.s)

   531         t &= t

   532         self.assertEqual(t, self.s)

   533         t -= t

   534         self.assertEqual(t, self.thetype())

   535         t = self.s.copy()

   536         t ^= t

   537         self.assertEqual(t, self.thetype())

   538 

   539     def test_weakref(self):

   540         s = self.thetype('gallahad')

   541         p = proxy(s)

   542         self.assertEqual(str(p), str(s))

   543         s = None

   544         self.assertRaises(ReferenceError, str, p)

   545 

   546     # C API test only available in a debug build

   547     if hasattr(set, "test_c_api"):

   548         def test_c_api(self):

   549             self.assertEqual(set('abc').test_c_api(), True)

   550 

   551 class SetSubclass(set):

   552     pass

   553 

   554 class TestSetSubclass(TestSet):

   555     thetype = SetSubclass

   556 

   557 class SetSubclassWithKeywordArgs(set):

   558     def __init__(self, iterable=[], newarg=None):

   559         set.__init__(self, iterable)

   560 

   561 class TestSetSubclassWithKeywordArgs(TestSet):

   562 

   563     def test_keywords_in_subclass(self):

   564         'SF bug #1486663 -- this used to erroneously raise a TypeError'

   565         SetSubclassWithKeywordArgs(newarg=1)

   566 

   567 class TestFrozenSet(TestJointOps):

   568     thetype = frozenset

   569 

   570     def test_init(self):

   571         s = self.thetype(self.word)

   572         s.__init__(self.otherword)

   573         self.assertEqual(s, set(self.word))

   574 

   575     def test_singleton_empty_frozenset(self):

   576         f = frozenset()

   577         efs = [frozenset(), frozenset([]), frozenset(()), frozenset(''),

   578                frozenset(), frozenset([]), frozenset(()), frozenset(''),

   579                frozenset(xrange(0)), frozenset(frozenset()),

   580                frozenset(f), f]

   581         # All of the empty frozensets should have just one id()

   582         self.assertEqual(len(set(map(id, efs))), 1)

   583 

   584     def test_constructor_identity(self):

   585         s = self.thetype(range(3))

   586         t = self.thetype(s)

   587         self.assertEqual(id(s), id(t))

   588 

   589     def test_hash(self):

   590         self.assertEqual(hash(self.thetype('abcdeb')),

   591                          hash(self.thetype('ebecda')))

   592 

   593         # make sure that all permutations give the same hash value

   594         n = 100

   595         seq = [randrange(n) for i in xrange(n)]

   596         results = set()

   597         for i in xrange(200):

   598             shuffle(seq)

   599             results.add(hash(self.thetype(seq)))

   600         self.assertEqual(len(results), 1)

   601 

   602     def test_copy(self):

   603         dup = self.s.copy()

   604         self.assertEqual(id(self.s), id(dup))

   605 

   606     def test_frozen_as_dictkey(self):

   607         seq = range(10) + list('abcdefg') + ['apple']

   608         key1 = self.thetype(seq)

   609         key2 = self.thetype(reversed(seq))

   610         self.assertEqual(key1, key2)

   611         self.assertNotEqual(id(key1), id(key2))

   612         d = {}

   613         d[key1] = 42

   614         self.assertEqual(d[key2], 42)

   615 

   616     def test_hash_caching(self):

   617         f = self.thetype('abcdcda')

   618         self.assertEqual(hash(f), hash(f))

   619 

   620     def test_hash_effectiveness(self):

   621         n = 13

   622         hashvalues = set()

   623         addhashvalue = hashvalues.add

   624         elemmasks = [(i+1, 1<<i) for i in range(n)]

   625         for i in xrange(2**n):

   626             addhashvalue(hash(frozenset([e for e, m in elemmasks if m&i])))

   627         self.assertEqual(len(hashvalues), 2**n)

   628 

   629 class FrozenSetSubclass(frozenset):

   630     pass

   631 

   632 class TestFrozenSetSubclass(TestFrozenSet):

   633     thetype = FrozenSetSubclass

   634 

   635     def test_constructor_identity(self):

   636         s = self.thetype(range(3))

   637         t = self.thetype(s)

   638         self.assertNotEqual(id(s), id(t))

   639 

   640     def test_copy(self):

   641         dup = self.s.copy()

   642         self.assertNotEqual(id(self.s), id(dup))

   643 

   644     def test_nested_empty_constructor(self):

   645         s = self.thetype()

   646         t = self.thetype(s)

   647         self.assertEqual(s, t)

   648 

   649     def test_singleton_empty_frozenset(self):

   650         Frozenset = self.thetype

   651         f = frozenset()

   652         F = Frozenset()

   653         efs = [Frozenset(), Frozenset([]), Frozenset(()), Frozenset(''),

   654                Frozenset(), Frozenset([]), Frozenset(()), Frozenset(''),

   655                Frozenset(xrange(0)), Frozenset(Frozenset()),

   656                Frozenset(frozenset()), f, F, Frozenset(f), Frozenset(F)]

   657         # All empty frozenset subclass instances should have different ids

   658         self.assertEqual(len(set(map(id, efs))), len(efs))

   659 

   660 # Tests taken from test_sets.py =============================================

   661 

   662 empty_set = set()

   663 

   664 #==============================================================================

   665 

   666 class TestBasicOps(unittest.TestCase):

   667 

   668     def test_repr(self):

   669         if self.repr is not None:

   670             self.assertEqual(repr(self.set), self.repr)

   671 

   672     def test_print(self):

   673         fo = open(test_support.TESTFN, "wb")

   674         try:

   675             print >> fo, self.set,

   676             fo.close()

   677             fo = open(test_support.TESTFN, "rb")

   678             self.assertEqual(fo.read(), repr(self.set))

   679         finally:

   680             fo.close()

   681             test_support.unlink(test_support.TESTFN)

   682 

   683     def test_length(self):

   684         self.assertEqual(len(self.set), self.length)

   685 

   686     def test_self_equality(self):

   687         self.assertEqual(self.set, self.set)

   688 

   689     def test_equivalent_equality(self):

   690         self.assertEqual(self.set, self.dup)

   691 

   692     def test_copy(self):

   693         self.assertEqual(self.set.copy(), self.dup)

   694 

   695     def test_self_union(self):

   696         result = self.set | self.set

   697         self.assertEqual(result, self.dup)

   698 

   699     def test_empty_union(self):

   700         result = self.set | empty_set

   701         self.assertEqual(result, self.dup)

   702 

   703     def test_union_empty(self):

   704         result = empty_set | self.set

   705         self.assertEqual(result, self.dup)

   706 

   707     def test_self_intersection(self):

   708         result = self.set & self.set

   709         self.assertEqual(result, self.dup)

   710 

   711     def test_empty_intersection(self):

   712         result = self.set & empty_set

   713         self.assertEqual(result, empty_set)

   714 

   715     def test_intersection_empty(self):

   716         result = empty_set & self.set

   717         self.assertEqual(result, empty_set)

   718 

   719     def test_self_isdisjoint(self):

   720         result = self.set.isdisjoint(self.set)

   721         self.assertEqual(result, not self.set)

   722 

   723     def test_empty_isdisjoint(self):

   724         result = self.set.isdisjoint(empty_set)

   725         self.assertEqual(result, True)

   726 

   727     def test_isdisjoint_empty(self):

   728         result = empty_set.isdisjoint(self.set)

   729         self.assertEqual(result, True)

   730 

   731     def test_self_symmetric_difference(self):

   732         result = self.set ^ self.set

   733         self.assertEqual(result, empty_set)

   734 

   735     def checkempty_symmetric_difference(self):

   736         result = self.set ^ empty_set

   737         self.assertEqual(result, self.set)

   738 

   739     def test_self_difference(self):

   740         result = self.set - self.set

   741         self.assertEqual(result, empty_set)

   742 

   743     def test_empty_difference(self):

   744         result = self.set - empty_set

   745         self.assertEqual(result, self.dup)

   746 

   747     def test_empty_difference_rev(self):

   748         result = empty_set - self.set

   749         self.assertEqual(result, empty_set)

   750 

   751     def test_iteration(self):

   752         for v in self.set:

   753             self.assert_(v in self.values)

   754         setiter = iter(self.set)

   755         # note: __length_hint__ is an internal undocumented API,

   756         # don't rely on it in your own programs

   757         self.assertEqual(setiter.__length_hint__(), len(self.set))

   758 

   759     def test_pickling(self):

   760         p = pickle.dumps(self.set)

   761         copy = pickle.loads(p)

   762         self.assertEqual(self.set, copy,

   763                          "%s != %s" % (self.set, copy))

   764 

   765 #------------------------------------------------------------------------------

   766 

   767 class TestBasicOpsEmpty(TestBasicOps):

   768     def setUp(self):

   769         self.case   = "empty set"

   770         self.values = []

   771         self.set    = set(self.values)

   772         self.dup    = set(self.values)

   773         self.length = 0

   774         self.repr   = "set([])"

   775 

   776 #------------------------------------------------------------------------------

   777 

   778 class TestBasicOpsSingleton(TestBasicOps):

   779     def setUp(self):

   780         self.case   = "unit set (number)"

   781         self.values = [3]

   782         self.set    = set(self.values)

   783         self.dup    = set(self.values)

   784         self.length = 1

   785         self.repr   = "set([3])"

   786 

   787     def test_in(self):

   788         self.failUnless(3 in self.set)

   789 

   790     def test_not_in(self):

   791         self.failUnless(2 not in self.set)

   792 

   793 #------------------------------------------------------------------------------

   794 

   795 class TestBasicOpsTuple(TestBasicOps):

   796     def setUp(self):

   797         self.case   = "unit set (tuple)"

   798         self.values = [(0, "zero")]

   799         self.set    = set(self.values)

   800         self.dup    = set(self.values)

   801         self.length = 1

   802         self.repr   = "set([(0, 'zero')])"

   803 

   804     def test_in(self):

   805         self.failUnless((0, "zero") in self.set)

   806 

   807     def test_not_in(self):

   808         self.failUnless(9 not in self.set)

   809 

   810 #------------------------------------------------------------------------------

   811 

   812 class TestBasicOpsTriple(TestBasicOps):

   813     def setUp(self):

   814         self.case   = "triple set"

   815         self.values = [0, "zero", operator.add]

   816         self.set    = set(self.values)

   817         self.dup    = set(self.values)

   818         self.length = 3

   819         self.repr   = None

   820 

   821 #==============================================================================

   822 

   823 def baditer():

   824     raise TypeError

   825     yield True

   826 

   827 def gooditer():

   828     yield True

   829 

   830 class TestExceptionPropagation(unittest.TestCase):

   831     """SF 628246:  Set constructor should not trap iterator TypeErrors"""

   832 

   833     def test_instanceWithException(self):

   834         self.assertRaises(TypeError, set, baditer())

   835 

   836     def test_instancesWithoutException(self):

   837         # All of these iterables should load without exception.

   838         set([1,2,3])

   839         set((1,2,3))

   840         set({'one':1, 'two':2, 'three':3})

   841         set(xrange(3))

   842         set('abc')

   843         set(gooditer())

   844 

   845     def test_changingSizeWhileIterating(self):

   846         s = set([1,2,3])

   847         try:

   848             for i in s:

   849                 s.update([4])

   850         except RuntimeError:

   851             pass

   852         else:

   853             self.fail("no exception when changing size during iteration")

   854 

   855 #==============================================================================

   856 

   857 class TestSetOfSets(unittest.TestCase):

   858     def test_constructor(self):

   859         inner = frozenset([1])

   860         outer = set([inner])

   861         element = outer.pop()

   862         self.assertEqual(type(element), frozenset)

   863         outer.add(inner)        # Rebuild set of sets with .add method

   864         outer.remove(inner)

   865         self.assertEqual(outer, set())   # Verify that remove worked

   866         outer.discard(inner)    # Absence of KeyError indicates working fine

   867 

   868 #==============================================================================

   869 

   870 class TestBinaryOps(unittest.TestCase):

   871     def setUp(self):

   872         self.set = set((2, 4, 6))

   873 

   874     def test_eq(self):              # SF bug 643115

   875         self.assertEqual(self.set, set({2:1,4:3,6:5}))

   876 

   877     def test_union_subset(self):

   878         result = self.set | set([2])

   879         self.assertEqual(result, set((2, 4, 6)))

   880 

   881     def test_union_superset(self):

   882         result = self.set | set([2, 4, 6, 8])

   883         self.assertEqual(result, set([2, 4, 6, 8]))

   884 

   885     def test_union_overlap(self):

   886         result = self.set | set([3, 4, 5])

   887         self.assertEqual(result, set([2, 3, 4, 5, 6]))

   888 

   889     def test_union_non_overlap(self):

   890         result = self.set | set([8])

   891         self.assertEqual(result, set([2, 4, 6, 8]))

   892 

   893     def test_intersection_subset(self):

   894         result = self.set & set((2, 4))

   895         self.assertEqual(result, set((2, 4)))

   896 

   897     def test_intersection_superset(self):

   898         result = self.set & set([2, 4, 6, 8])

   899         self.assertEqual(result, set([2, 4, 6]))

   900 

   901     def test_intersection_overlap(self):

   902         result = self.set & set([3, 4, 5])

   903         self.assertEqual(result, set([4]))

   904 

   905     def test_intersection_non_overlap(self):

   906         result = self.set & set([8])

   907         self.assertEqual(result, empty_set)

   908 

   909     def test_isdisjoint_subset(self):

   910         result = self.set.isdisjoint(set((2, 4)))

   911         self.assertEqual(result, False)

   912 

   913     def test_isdisjoint_superset(self):

   914         result = self.set.isdisjoint(set([2, 4, 6, 8]))

   915         self.assertEqual(result, False)

   916 

   917     def test_isdisjoint_overlap(self):

   918         result = self.set.isdisjoint(set([3, 4, 5]))

   919         self.assertEqual(result, False)

   920 

   921     def test_isdisjoint_non_overlap(self):

   922         result = self.set.isdisjoint(set([8]))

   923         self.assertEqual(result, True)

   924 

   925     def test_sym_difference_subset(self):

   926         result = self.set ^ set((2, 4))

   927         self.assertEqual(result, set([6]))

   928 

   929     def test_sym_difference_superset(self):

   930         result = self.set ^ set((2, 4, 6, 8))

   931         self.assertEqual(result, set([8]))

   932 

   933     def test_sym_difference_overlap(self):

   934         result = self.set ^ set((3, 4, 5))

   935         self.assertEqual(result, set([2, 3, 5, 6]))

   936 

   937     def test_sym_difference_non_overlap(self):

   938         result = self.set ^ set([8])

   939         self.assertEqual(result, set([2, 4, 6, 8]))

   940 

   941     def test_cmp(self):

   942         a, b = set('a'), set('b')

   943         self.assertRaises(TypeError, cmp, a, b)

   944 

   945         # You can view this as a buglet:  cmp(a, a) does not raise TypeError,

   946         # because __eq__ is tried before __cmp__, and a.__eq__(a) returns True,

   947         # which Python thinks is good enough to synthesize a cmp() result

   948         # without calling __cmp__.

   949         self.assertEqual(cmp(a, a), 0)

   950 

   951         self.assertRaises(TypeError, cmp, a, 12)

   952         self.assertRaises(TypeError, cmp, "abc", a)

   953 

   954 #==============================================================================

   955 

   956 class TestUpdateOps(unittest.TestCase):

   957     def setUp(self):

   958         self.set = set((2, 4, 6))

   959 

   960     def test_union_subset(self):

   961         self.set |= set([2])

   962         self.assertEqual(self.set, set((2, 4, 6)))

   963 

   964     def test_union_superset(self):

   965         self.set |= set([2, 4, 6, 8])

   966         self.assertEqual(self.set, set([2, 4, 6, 8]))

   967 

   968     def test_union_overlap(self):

   969         self.set |= set([3, 4, 5])

   970         self.assertEqual(self.set, set([2, 3, 4, 5, 6]))

   971 

   972     def test_union_non_overlap(self):

   973         self.set |= set([8])

   974         self.assertEqual(self.set, set([2, 4, 6, 8]))

   975 

   976     def test_union_method_call(self):

   977         self.set.update(set([3, 4, 5]))

   978         self.assertEqual(self.set, set([2, 3, 4, 5, 6]))

   979 

   980     def test_intersection_subset(self):

   981         self.set &= set((2, 4))

   982         self.assertEqual(self.set, set((2, 4)))

   983 

   984     def test_intersection_superset(self):

   985         self.set &= set([2, 4, 6, 8])

   986         self.assertEqual(self.set, set([2, 4, 6]))

   987 

   988     def test_intersection_overlap(self):

   989         self.set &= set([3, 4, 5])

   990         self.assertEqual(self.set, set([4]))

   991 

   992     def test_intersection_non_overlap(self):

   993         self.set &= set([8])

   994         self.assertEqual(self.set, empty_set)

   995 

   996     def test_intersection_method_call(self):

   997         self.set.intersection_update(set([3, 4, 5]))

   998         self.assertEqual(self.set, set([4]))

   999 

  1000     def test_sym_difference_subset(self):

  1001         self.set ^= set((2, 4))

  1002         self.assertEqual(self.set, set([6]))

  1003 

  1004     def test_sym_difference_superset(self):

  1005         self.set ^= set((2, 4, 6, 8))

  1006         self.assertEqual(self.set, set([8]))

  1007 

  1008     def test_sym_difference_overlap(self):

  1009         self.set ^= set((3, 4, 5))

  1010         self.assertEqual(self.set, set([2, 3, 5, 6]))

  1011 

  1012     def test_sym_difference_non_overlap(self):

  1013         self.set ^= set([8])

  1014         self.assertEqual(self.set, set([2, 4, 6, 8]))

  1015 

  1016     def test_sym_difference_method_call(self):

  1017         self.set.symmetric_difference_update(set([3, 4, 5]))

  1018         self.assertEqual(self.set, set([2, 3, 5, 6]))

  1019 

  1020     def test_difference_subset(self):

  1021         self.set -= set((2, 4))

  1022         self.assertEqual(self.set, set([6]))

  1023 

  1024     def test_difference_superset(self):

  1025         self.set -= set((2, 4, 6, 8))

  1026         self.assertEqual(self.set, set([]))

  1027 

  1028     def test_difference_overlap(self):

  1029         self.set -= set((3, 4, 5))

  1030         self.assertEqual(self.set, set([2, 6]))

  1031 

  1032     def test_difference_non_overlap(self):

  1033         self.set -= set([8])

  1034         self.assertEqual(self.set, set([2, 4, 6]))

  1035 

  1036     def test_difference_method_call(self):

  1037         self.set.difference_update(set([3, 4, 5]))

  1038         self.assertEqual(self.set, set([2, 6]))

  1039 

  1040 #==============================================================================

  1041 

  1042 class TestMutate(unittest.TestCase):

  1043     def setUp(self):

  1044         self.values = ["a", "b", "c"]

  1045         self.set = set(self.values)

  1046 

  1047     def test_add_present(self):

  1048         self.set.add("c")

  1049         self.assertEqual(self.set, set("abc"))

  1050 

  1051     def test_add_absent(self):

  1052         self.set.add("d")

  1053         self.assertEqual(self.set, set("abcd"))

  1054 

  1055     def test_add_until_full(self):

  1056         tmp = set()

  1057         expected_len = 0

  1058         for v in self.values:

  1059             tmp.add(v)

  1060             expected_len += 1

  1061             self.assertEqual(len(tmp), expected_len)

  1062         self.assertEqual(tmp, self.set)

  1063 

  1064     def test_remove_present(self):

  1065         self.set.remove("b")

  1066         self.assertEqual(self.set, set("ac"))

  1067 

  1068     def test_remove_absent(self):

  1069         try:

  1070             self.set.remove("d")

  1071             self.fail("Removing missing element should have raised LookupError")

  1072         except LookupError:

  1073             pass

  1074 

  1075     def test_remove_until_empty(self):

  1076         expected_len = len(self.set)

  1077         for v in self.values:

  1078             self.set.remove(v)

  1079             expected_len -= 1

  1080             self.assertEqual(len(self.set), expected_len)

  1081 

  1082     def test_discard_present(self):

  1083         self.set.discard("c")

  1084         self.assertEqual(self.set, set("ab"))

  1085 

  1086     def test_discard_absent(self):

  1087         self.set.discard("d")

  1088         self.assertEqual(self.set, set("abc"))

  1089 

  1090     def test_clear(self):

  1091         self.set.clear()

  1092         self.assertEqual(len(self.set), 0)

  1093 

  1094     def test_pop(self):

  1095         popped = {}

  1096         while self.set:

  1097             popped[self.set.pop()] = None

  1098         self.assertEqual(len(popped), len(self.values))

  1099         for v in self.values:

  1100             self.failUnless(v in popped)

  1101 

  1102     def test_update_empty_tuple(self):

  1103         self.set.update(())

  1104         self.assertEqual(self.set, set(self.values))

  1105 

  1106     def test_update_unit_tuple_overlap(self):

  1107         self.set.update(("a",))

  1108         self.assertEqual(self.set, set(self.values))

  1109 

  1110     def test_update_unit_tuple_non_overlap(self):

  1111         self.set.update(("a", "z"))

  1112         self.assertEqual(self.set, set(self.values + ["z"]))

  1113 

  1114 #==============================================================================

  1115 

  1116 class TestSubsets(unittest.TestCase):

  1117 

  1118     case2method = {"<=": "issubset",

  1119                    ">=": "issuperset",

  1120                   }

  1121 

  1122     reverse = {"==": "==",

  1123                "!=": "!=",

  1124                "<":  ">",

  1125                ">":  "<",

  1126                "<=": ">=",

  1127                ">=": "<=",

  1128               }

  1129 

  1130     def test_issubset(self):

  1131         x = self.left

  1132         y = self.right

  1133         for case in "!=", "==", "<", "<=", ">", ">=":

  1134             expected = case in self.cases

  1135             # Test the binary infix spelling.