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 

    11 class PassThru(Exception):

    12     pass

    13 

    14 def check_pass_thru():

    15     raise PassThru

    16     yield 1

    17 

    18 class BadCmp:

    19     def __hash__(self):

    20         return 1

    21     def __cmp__(self, other):

    22         raise RuntimeError

    23 

    24 class ReprWrapper:

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

    26     def __repr__(self):

    27         return repr(self.value)

    28 

    29 class HashCountingInt(int):

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

    31     def __init__(self, *args):

    32         self.hash_count = 0

    33     def __hash__(self):

    34         self.hash_count += 1

    35         return int.__hash__(self)

    36 

    37 class TestJointOps(unittest.TestCase):

    38     # Tests common to both set and frozenset

    39 

    40     def setUp(self):

    41         self.word = word = 'simsalabim'

    42         self.otherword = 'madagascar'

    43         self.letters = 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ'

    44         self.s = self.thetype(word)

    45         self.d = dict.fromkeys(word)

    46 

    47     def test_new_or_init(self):

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

    49 

    50     def test_uniquification(self):

    51         actual = sorted(self.s)

    52         expected = sorted(self.d)

    53         self.assertEqual(actual, expected)

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

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

    56 

    57     def test_len(self):

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

    59 

    60     def test_contains(self):

    61         for c in self.letters:

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

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

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

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

    66 

    67     def test_union(self):

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

    69         for c in self.letters:

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

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

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

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

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

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

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

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

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

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

    80 

    81     def test_or(self):

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

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

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

    85         try:

    86             self.s | self.otherword

    87         except TypeError:

    88             pass

    89         else:

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

    91 

    92     def test_intersection(self):

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

    94         for c in self.letters:

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

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

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

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

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

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

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

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

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

   104 

   105     def test_and(self):

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

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

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

   109         try:

   110             self.s & self.otherword

   111         except TypeError:

   112             pass

   113         else:

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

   115 

   116     def test_difference(self):

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

   118         for c in self.letters:

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

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

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

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

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

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

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

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

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

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

   129 

   130     def test_sub(self):

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

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

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

   134         try:

   135             self.s - self.otherword

   136         except TypeError:

   137             pass

   138         else:

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

   140 

   141     def test_symmetric_difference(self):

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

   143         for c in self.letters:

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

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

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

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

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

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

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

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

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

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

   154 

   155     def test_xor(self):

   156         i = self.s.symmetric_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_equality(self):

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

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

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

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

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

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

   173 

   174     def test_setOfFrozensets(self):

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

   176         s = self.thetype(t)

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

   178 

   179     def test_compare(self):

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

   181 

   182     def test_sub_and_super(self):

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

   184         self.assert_(p < q)

   185         self.assert_(p <= q)

   186         self.assert_(q <= q)

   187         self.assert_(q > p)

   188         self.assert_(q >= p)

   189         self.failIf(q < r)

   190         self.failIf(q <= r)

   191         self.failIf(q > r)

   192         self.failIf(q >= r)

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

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

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

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

   197 

   198     def test_pickling(self):

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

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

   201             dup = pickle.loads(p)

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

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

   204                 self.s.x = 10

   205                 p = pickle.dumps(self.s)

   206                 dup = pickle.loads(p)

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

   208 

   209     def test_deepcopy(self):

   210         class Tracer:

   211             def __init__(self, value):

   212                 self.value = value

   213             def __hash__(self):

   214                 return self.value

   215             def __deepcopy__(self, memo=None):

   216                 return Tracer(self.value + 1)

   217         t = Tracer(10)

   218         s = self.thetype([t])

   219         dup = copy.deepcopy(s)

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

   221         for elem in dup:

   222             newt = elem

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

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

   225 

   226     def test_gc(self):

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

   228         class A:

   229             pass

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

   231         for elem in s:

   232             elem.cycle = s

   233             elem.sub = elem

   234             elem.set = set([elem])

   235 

   236     def test_subclass_with_custom_hash(self):

   237         # Bug #1257731

   238         class H(self.thetype):

   239             def __hash__(self):

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

   241         s=H()

   242         f=set()

   243         f.add(s)

   244         self.assert_(s in f)

   245         f.remove(s)

   246         f.add(s)

   247         f.discard(s)

   248 

   249     def test_badcmp(self):

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

   251         # Detect comparison errors during insertion and lookup

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

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

   254         # Detect errors during mutating operations

   255         if hasattr(s, 'add'):

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

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

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

   259 

   260     def test_cyclical_repr(self):

   261         w = ReprWrapper()

   262         s = self.thetype([w])

   263         w.value = s

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

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

   266 

   267     def test_cyclical_print(self):

   268         w = ReprWrapper()

   269         s = self.thetype([w])

   270         w.value = s

   271         try:

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

   273             print >> fo, s,

   274             fo.close()

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

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

   277         finally:

   278             fo.close()

   279             os.remove(test_support.TESTFN)

   280 

   281     def test_do_not_rehash_dict_keys(self):

   282         n = 10

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

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

   285         s = self.thetype(d)

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

   287         s.difference(d)

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

   289         if hasattr(s, 'symmetric_difference_update'):

   290             s.symmetric_difference_update(d)

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

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

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

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

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

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

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

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

   299 

   300 class TestSet(TestJointOps):

   301     thetype = set

   302 

   303     def test_init(self):

   304         s = self.thetype()

   305         s.__init__(self.word)

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

   307         s.__init__(self.otherword)

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

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

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

   311 

   312     def test_constructor_identity(self):

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

   314         t = self.thetype(s)

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

   316 

   317     def test_hash(self):

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

   319 

   320     def test_clear(self):

   321         self.s.clear()

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

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

   324 

   325     def test_copy(self):

   326         dup = self.s.copy()

   327         self.assertEqual(self.s, dup)

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

   329 

   330     def test_add(self):

   331         self.s.add('Q')

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

   333         dup = self.s.copy()

   334         self.s.add('Q')

   335         self.assertEqual(self.s, dup)

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

   337 

   338     def test_remove(self):

   339         self.s.remove('a')

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

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

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

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

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

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

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

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

   348 

   349     def test_remove_keyerror_unpacking(self):

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

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

   352             try:

   353                 self.s.remove(v1)

   354             except KeyError, e:

   355                 v2 = e.args[0]

   356                 self.assertEqual(v1, v2)

   357             else:

   358                 self.fail()

   359 

   360     def test_discard(self):

   361         self.s.discard('a')

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

   363         self.s.discard('Q')

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

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

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

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

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

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

   370 

   371     def test_pop(self):

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

   373             elem = self.s.pop()

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

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

   376 

   377     def test_update(self):

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

   379         self.assertEqual(retval, None)

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

   381             self.assert_(c in self.s)

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

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

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

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

   386                 s = self.thetype('abcba')

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

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

   389 

   390     def test_ior(self):

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

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

   393             self.assert_(c in self.s)

   394 

   395     def test_intersection_update(self):

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

   397         self.assertEqual(retval, None)

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

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

   400                 self.assert_(c in self.s)

   401             else:

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

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

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

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

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

   407                 s = self.thetype('abcba')

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

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

   410 

   411     def test_iand(self):

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

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

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

   415                 self.assert_(c in self.s)

   416             else:

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

   418 

   419     def test_difference_update(self):

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

   421         self.assertEqual(retval, None)

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

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

   424                 self.assert_(c in self.s)

   425             else:

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

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

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

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

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

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

   432                 s = self.thetype('abcba')

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

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

   435 

   436     def test_isub(self):

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

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

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

   440                 self.assert_(c in self.s)

   441             else:

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

   443 

   444     def test_symmetric_difference_update(self):

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

   446         self.assertEqual(retval, None)

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

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

   449                 self.assert_(c in self.s)

   450             else:

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

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

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

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

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

   456                 s = self.thetype('abcba')

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

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

   459 

   460     def test_ixor(self):

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

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

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

   464                 self.assert_(c in self.s)

   465             else:

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

   467 

   468     def test_inplace_on_self(self):

   469         t = self.s.copy()

   470         t |= t

   471         self.assertEqual(t, self.s)

   472         t &= t

   473         self.assertEqual(t, self.s)

   474         t -= t

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

   476         t = self.s.copy()

   477         t ^= t

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

   479 

   480     def test_weakref(self):

   481         s = self.thetype('gallahad')

   482         p = proxy(s)

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

   484         s = None

   485         self.assertRaises(ReferenceError, str, p)

   486 

   487     # C API test only available in a debug build

   488     if hasattr(set, "test_c_api"):

   489         def test_c_api(self):

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

   491 

   492 class SetSubclass(set):

   493     pass

   494 

   495 class TestSetSubclass(TestSet):

   496     thetype = SetSubclass

   497 

   498 class SetSubclassWithKeywordArgs(set):

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

   500         set.__init__(self, iterable)

   501 

   502 class TestSetSubclassWithKeywordArgs(TestSet):

   503 

   504     def test_keywords_in_subclass(self):

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

   506         SetSubclassWithKeywordArgs(newarg=1)

   507 

   508 class TestFrozenSet(TestJointOps):

   509     thetype = frozenset

   510 

   511     def test_init(self):

   512         s = self.thetype(self.word)

   513         s.__init__(self.otherword)

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

   515 

   516     def test_singleton_empty_frozenset(self):

   517         f = frozenset()

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

   519                frozenset(), frozenset([]), frozenset(()), frozenset(''),

   520                frozenset(xrange(0)), frozenset(frozenset()),

   521                frozenset(f), f]

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

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

   524 

   525     def test_constructor_identity(self):

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

   527         t = self.thetype(s)

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

   529 

   530     def test_hash(self):

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

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

   533 

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

   535         n = 100

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

   537         results = set()

   538         for i in xrange(200):

   539             shuffle(seq)

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

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

   542 

   543     def test_copy(self):

   544         dup = self.s.copy()

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

   546 

   547     def test_frozen_as_dictkey(self):

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

   549         key1 = self.thetype(seq)

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

   551         self.assertEqual(key1, key2)

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

   553         d = {}

   554         d[key1] = 42

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

   556 

   557     def test_hash_caching(self):

   558         f = self.thetype('abcdcda')

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

   560 

   561     def test_hash_effectiveness(self):

   562         n = 13

   563         hashvalues = set()

   564         addhashvalue = hashvalues.add

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

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

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

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

   569 

   570 class FrozenSetSubclass(frozenset):

   571     pass

   572 

   573 class TestFrozenSetSubclass(TestFrozenSet):

   574     thetype = FrozenSetSubclass

   575 

   576     def test_constructor_identity(self):

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

   578         t = self.thetype(s)

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

   580 

   581     def test_copy(self):

   582         dup = self.s.copy()

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

   584 

   585     def test_nested_empty_constructor(self):

   586         s = self.thetype()

   587         t = self.thetype(s)

   588         self.assertEqual(s, t)

   589 

   590     def test_singleton_empty_frozenset(self):

   591         Frozenset = self.thetype

   592         f = frozenset()

   593         F = Frozenset()

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

   595                Frozenset(), Frozenset([]), Frozenset(()), Frozenset(''),

   596                Frozenset(xrange(0)), Frozenset(Frozenset()),

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

   598         # All empty frozenset subclass instances should have different ids

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

   600 

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

   602 

   603 empty_set = set()

   604 

   605 #==============================================================================

   606 

   607 class TestBasicOps(unittest.TestCase):

   608 

   609     def test_repr(self):

   610         if self.repr is not None:

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

   612 

   613     def test_print(self):

   614         try:

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

   616             print >> fo, self.set,

   617             fo.close()

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

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

   620         finally:

   621             fo.close()

   622             os.remove(test_support.TESTFN)

   623 

   624     def test_length(self):

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

   626 

   627     def test_self_equality(self):

   628         self.assertEqual(self.set, self.set)

   629 

   630     def test_equivalent_equality(self):

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

   632 

   633     def test_copy(self):

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

   635 

   636     def test_self_union(self):

   637         result = self.set | self.set

   638         self.assertEqual(result, self.dup)

   639 

   640     def test_empty_union(self):

   641         result = self.set | empty_set

   642         self.assertEqual(result, self.dup)

   643 

   644     def test_union_empty(self):

   645         result = empty_set | self.set

   646         self.assertEqual(result, self.dup)

   647 

   648     def test_self_intersection(self):

   649         result = self.set & self.set

   650         self.assertEqual(result, self.dup)

   651 

   652     def test_empty_intersection(self):

   653         result = self.set & empty_set

   654         self.assertEqual(result, empty_set)

   655 

   656     def test_intersection_empty(self):

   657         result = empty_set & self.set

   658         self.assertEqual(result, empty_set)

   659 

   660     def test_self_symmetric_difference(self):

   661         result = self.set ^ self.set

   662         self.assertEqual(result, empty_set)

   663 

   664     def checkempty_symmetric_difference(self):

   665         result = self.set ^ empty_set

   666         self.assertEqual(result, self.set)

   667 

   668     def test_self_difference(self):

   669         result = self.set - self.set

   670         self.assertEqual(result, empty_set)

   671 

   672     def test_empty_difference(self):

   673         result = self.set - empty_set

   674         self.assertEqual(result, self.dup)

   675 

   676     def test_empty_difference_rev(self):

   677         result = empty_set - self.set

   678         self.assertEqual(result, empty_set)

   679 

   680     def test_iteration(self):

   681         for v in self.set:

   682             self.assert_(v in self.values)

   683         setiter = iter(self.set)

   684         # note: __length_hint__ is an internal undocumented API,

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

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

   687 

   688     def test_pickling(self):

   689         p = pickle.dumps(self.set)

   690         copy = pickle.loads(p)

   691         self.assertEqual(self.set, copy,

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

   693 

   694 #------------------------------------------------------------------------------

   695 

   696 class TestBasicOpsEmpty(TestBasicOps):

   697     def setUp(self):

   698         self.case   = "empty set"

   699         self.values = []

   700         self.set    = set(self.values)

   701         self.dup    = set(self.values)

   702         self.length = 0

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

   704 

   705 #------------------------------------------------------------------------------

   706 

   707 class TestBasicOpsSingleton(TestBasicOps):

   708     def setUp(self):

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

   710         self.values = [3]

   711         self.set    = set(self.values)

   712         self.dup    = set(self.values)

   713         self.length = 1

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

   715 

   716     def test_in(self):

   717         self.failUnless(3 in self.set)

   718 

   719     def test_not_in(self):

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

   721 

   722 #------------------------------------------------------------------------------

   723 

   724 class TestBasicOpsTuple(TestBasicOps):

   725     def setUp(self):

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

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

   728         self.set    = set(self.values)

   729         self.dup    = set(self.values)

   730         self.length = 1

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

   732 

   733     def test_in(self):

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

   735 

   736     def test_not_in(self):

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

   738 

   739 #------------------------------------------------------------------------------

   740 

   741 class TestBasicOpsTriple(TestBasicOps):

   742     def setUp(self):

   743         self.case   = "triple set"

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

   745         self.set    = set(self.values)

   746         self.dup    = set(self.values)

   747         self.length = 3

   748         self.repr   = None

   749 

   750 #==============================================================================

   751 

   752 def baditer():

   753     raise TypeError

   754     yield True

   755 

   756 def gooditer():

   757     yield True

   758 

   759 class TestExceptionPropagation(unittest.TestCase):

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

   761 

   762     def test_instanceWithException(self):

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

   764 

   765     def test_instancesWithoutException(self):

   766         # All of these iterables should load without exception.

   767         set([1,2,3])

   768         set((1,2,3))

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

   770         set(xrange(3))

   771         set('abc')

   772         set(gooditer())

   773 

   774     def test_changingSizeWhileIterating(self):

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

   776         try:

   777             for i in s:

   778                 s.update([4])

   779         except RuntimeError:

   780             pass

   781         else:

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

   783 

   784 #==============================================================================

   785 

   786 class TestSetOfSets(unittest.TestCase):

   787     def test_constructor(self):

   788         inner = frozenset([1])

   789         outer = set([inner])

   790         element = outer.pop()

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

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

   793         outer.remove(inner)

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

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

   796 

   797 #==============================================================================

   798 

   799 class TestBinaryOps(unittest.TestCase):

   800     def setUp(self):

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

   802 

   803     def test_eq(self):              # SF bug 643115

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

   805 

   806     def test_union_subset(self):

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

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

   809 

   810     def test_union_superset(self):

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

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

   813 

   814     def test_union_overlap(self):

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

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

   817 

   818     def test_union_non_overlap(self):

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

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

   821 

   822     def test_intersection_subset(self):

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

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

   825 

   826     def test_intersection_superset(self):

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

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

   829 

   830     def test_intersection_overlap(self):

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

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

   833 

   834     def test_intersection_non_overlap(self):

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

   836         self.assertEqual(result, empty_set)

   837 

   838     def test_sym_difference_subset(self):

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

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

   841 

   842     def test_sym_difference_superset(self):

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

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

   845 

   846     def test_sym_difference_overlap(self):

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

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

   849 

   850     def test_sym_difference_non_overlap(self):

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

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

   853 

   854     def test_cmp(self):

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

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

   857 

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

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

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

   861         # without calling __cmp__.

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

   863 

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

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

   866 

   867 #==============================================================================

   868 

   869 class TestUpdateOps(unittest.TestCase):

   870     def setUp(self):

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

   872 

   873     def test_union_subset(self):

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

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

   876 

   877     def test_union_superset(self):

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

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

   880 

   881     def test_union_overlap(self):

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

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

   884 

   885     def test_union_non_overlap(self):

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

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

   888 

   889     def test_union_method_call(self):

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

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

   892 

   893     def test_intersection_subset(self):

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

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

   896 

   897     def test_intersection_superset(self):

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

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

   900 

   901     def test_intersection_overlap(self):

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

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

   904 

   905     def test_intersection_non_overlap(self):

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

   907         self.assertEqual(self.set, empty_set)

   908 

   909     def test_intersection_method_call(self):

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

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

   912 

   913     def test_sym_difference_subset(self):

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

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

   916 

   917     def test_sym_difference_superset(self):

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

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

   920 

   921     def test_sym_difference_overlap(self):

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

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

   924 

   925     def test_sym_difference_non_overlap(self):

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

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

   928 

   929     def test_sym_difference_method_call(self):

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

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

   932 

   933     def test_difference_subset(self):

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

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

   936 

   937     def test_difference_superset(self):

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

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

   940 

   941     def test_difference_overlap(self):

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

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

   944 

   945     def test_difference_non_overlap(self):

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

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

   948 

   949     def test_difference_method_call(self):

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

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

   952 

   953 #==============================================================================

   954 

   955 class TestMutate(unittest.TestCase):

   956     def setUp(self):

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

   958         self.set = set(self.values)

   959 

   960     def test_add_present(self):

   961         self.set.add("c")

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

   963 

   964     def test_add_absent(self):

   965         self.set.add("d")

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

   967 

   968     def test_add_until_full(self):

   969         tmp = set()

   970         expected_len = 0

   971         for v in self.values:

   972             tmp.add(v)

   973             expected_len += 1

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

   975         self.assertEqual(tmp, self.set)

   976 

   977     def test_remove_present(self):

   978         self.set.remove("b")

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

   980 

   981     def test_remove_absent(self):

   982         try:

   983             self.set.remove("d")

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

   985         except LookupError:

   986             pass

   987 

   988     def test_remove_until_empty(self):

   989         expected_len = len(self.set)

   990         for v in self.values:

   991             self.set.remove(v)

   992             expected_len -= 1

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

   994 

   995     def test_discard_present(self):

   996         self.set.discard("c")

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

   998 

   999     def test_discard_absent(self):

  1000         self.set.discard("d")

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

  1002 

  1003     def test_clear(self):

  1004         self.set.clear()

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

  1006 

  1007     def test_pop(self):

  1008         popped = {}

  1009         while self.set:

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

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

  1012         for v in self.values:

  1013             self.failUnless(v in popped)

  1014 

  1015     def test_update_empty_tuple(self):

  1016         self.set.update(())

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

  1018 

  1019     def test_update_unit_tuple_overlap(self):

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

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

  1022 

  1023     def test_update_unit_tuple_non_overlap(self):

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

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

  1026 

  1027 #==============================================================================

  1028 

  1029 class TestSubsets(unittest.TestCase):

  1030 

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

  1032                    ">=": "issuperset",

  1033                   }

  1034 

  1035     reverse = {"==": "==",

  1036                "!=": "!=",

  1037                "<":  ">",

  1038                ">":  "<",

  1039                "<=": ">=",

  1040                ">=": "<=",

  1041               }

  1042 

  1043     def test_issubset(self):

  1044         x = self.left

  1045         y = self.right

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

  1047             expected = case in self.cases

  1048             # Test the binary infix spelling.

  1049             result = eval("x" + case + "y", locals())

  1050             self.assertEqual(result, expected)

  1051             # Test the "friendly" method-name spelling, if one exists.

  1052             if case in TestSubsets.case2method:

  1053                 method = getattr(x, TestSubsets.case2method[case])

  1054                 result = method(y)

  1055                 self.assertEqual(result, expected)

  1056 

  1057             # Now do the same for the operands reversed.

  1058             rcase = TestSubsets.reverse[case]

  1059             result = eval("y" + rcase + "x", locals())

  1060             self.assertEqual(result, expected)

  1061             if rcase in TestSubsets.case2method:

  1062                 method = getattr(y, TestSubsets.case2method[rcase])

  1063                 result = method(x)

  1064                 self.assertEqual(result, expected)

  1065 #------------------------------------------------------------------------------

  1066 

  1067 class TestSubsetEqualEmpty(TestSubsets):

  1068     left  = set()

  1069     right = set()

  1070     name  = "both empty"

  1071     cases = "==", "<=", ">="

  1072 

  1073 #------------------------------------------------------------------------------

  1074 

  1075 class TestSubsetEqualNonEmpty(TestSubsets):

  1076     left  = set([1, 2])

  1077     right = set([1, 2])

  1078     name  = "equal pair"

  1079     cases = "==", "<=", ">="

  1080 

  1081 #------------------------------------------------------------------------------

  1082 

  1083 class TestSubsetEmptyNonEmpty(TestSubsets):

  1084     left  = set()

  1085     right = set([1, 2])

  1086     name  = "one empty, one non-empty"

  1087     cases = "!=", "<", "<="

  1088 

  1089 #------------------------------------------------------------------------------

  1090 

  1091 class TestSubsetPartial(TestSubsets):

  1092     left  = set([1])

  1093     right = set([1, 2])

  1094     name  = "one a non-empty proper subset of other"

  1095     cases = "!=", "<", "<="

  1096 

  1097 #------------------------------------------------------------------------------

  1098 

  1099 class TestSubsetNonOverlap(TestSubsets):

  1100     left  = set([1])

  1101     right = set([2])

  1102     name  = "neither empty, neither contains"

  1103     cases = "!="

  1104 

  1105 #==============================================================================

  1106 

  1107 class TestOnlySetsInBinaryOps(unittest.TestCase):

  1108 

  1109     def test_eq_ne(self):

  1110         # Unlike the others, this is testing that == and != *are* allowed.

  1111         self.assertEqual(self.other == self.set, False)

  1112         self.assertEqual(self.set == self.other, False)

  1113         self.assertEqual(self.other != self.set, True)

  1114         self.assertEqual(self.set != self.other, True)

  1115 

  1116     def test_ge_gt_le_lt(self):

  1117         self.assertRaises(TypeError, lambda: self.set < self.other)

  1118         self.assertRaises(TypeError, lambda: self.set <= self.other)

  1119         self.assertRaises(TypeError, lambda: self.set > self.other)

  1120         self.assertRaises(TypeError, lambda: self.set >= self.other)

  1121 

  1122         self.assertRaises(TypeError, lambda: self.other < self.set)

  1123         self.assertRaises(TypeError, lambda: self.other <= self.set)

  1124         self.assertRaises(TypeError, lambda: self.other > self.set)

  1125         self.assertRaises(TypeError, lambda: self.other >= self.set)

  1126 

  1127     def test_update_operator(self):

  1128         try:

  1129             self.set |= self.other

  1130         except TypeError:

  1131             pass

  1132         else:

  1133             self.fail("expected TypeError")

  1134 

  1135     def test_update(self):