home *** CD-ROM | disk | FTP | other *** search
/ Maximum CD 2011 July / maximum-cd-2011-07.iso / DiscContents / LibO_3.3.2_Win_x86_install_multi.exe / libreoffice1.cab / test_set.py < prev    next >
Encoding:
Python Source  |  2011-03-15  |  58.6 KB  |  1,731 lines
  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.
  1136.             result = eval("x" + case + "y", locals())
  1137.             self.assertEqual(result, expected)
  1138.             # Test the "friendly" method-name spelling, if one exists.
  1139.             if case in TestSubsets.case2method:
  1140.                 method = getattr(x, TestSubsets.case2method[case])
  1141.                 result = method(y)
  1142.                 self.assertEqual(result, expected)
  1143.  
  1144.             # Now do the same for the operands reversed.
  1145.             rcase = TestSubsets.reverse[case]
  1146.             result = eval("y" + rcase + "x", locals())
  1147.             self.assertEqual(result, expected)
  1148.             if rcase in TestSubsets.case2method:
  1149.                 method = getattr(y, TestSubsets.case2method[rcase])
  1150.                 result = method(x)
  1151.                 self.assertEqual(result, expected)
  1152. #------------------------------------------------------------------------------
  1153.  
  1154. class TestSubsetEqualEmpty(TestSubsets):
  1155.     left  = set()
  1156.     right = set()
  1157.     name  = "both empty"
  1158.     cases = "==", "<=", ">="
  1159.  
  1160. #------------------------------------------------------------------------------
  1161.  
  1162. class TestSubsetEqualNonEmpty(TestSubsets):
  1163.     left  = set([1, 2])
  1164.     right = set([1, 2])
  1165.     name  = "equal pair"
  1166.     cases = "==", "<=", ">="
  1167.  
  1168. #------------------------------------------------------------------------------
  1169.  
  1170. class TestSubsetEmptyNonEmpty(TestSubsets):
  1171.     left  = set()
  1172.     right = set([1, 2])
  1173.     name  = "one empty, one non-empty"
  1174.     cases = "!=", "<", "<="
  1175.  
  1176. #------------------------------------------------------------------------------
  1177.  
  1178. class TestSubsetPartial(TestSubsets):
  1179.     left  = set([1])
  1180.     right = set([1, 2])
  1181.     name  = "one a non-empty proper subset of other"
  1182.     cases = "!=", "<", "<="
  1183.  
  1184. #------------------------------------------------------------------------------
  1185.  
  1186. class TestSubsetNonOverlap(TestSubsets):
  1187.     left  = set([1])
  1188.     right = set([2])
  1189.     name  = "neither empty, neither contains"
  1190.     cases = "!="
  1191.  
  1192. #==============================================================================
  1193.  
  1194. class TestOnlySetsInBinaryOps(unittest.TestCase):
  1195.  
  1196.     def test_eq_ne(self):
  1197.         # Unlike the others, this is testing that == and != *are* allowed.
  1198.         self.assertEqual(self.other == self.set, False)
  1199.         self.assertEqual(self.set == self.other, False)
  1200.         self.assertEqual(self.other != self.set, True)
  1201.         self.assertEqual(self.set != self.other, True)
  1202.  
  1203.     def test_ge_gt_le_lt(self):
  1204.         self.assertRaises(TypeError, lambda: self.set < self.other)
  1205.         self.assertRaises(TypeError, lambda: self.set <= self.other)
  1206.         self.assertRaises(TypeError, lambda: self.set > self.other)
  1207.         self.assertRaises(TypeError, lambda: self.set >= self.other)
  1208.  
  1209.         self.assertRaises(TypeError, lambda: self.other < self.set)
  1210.         self.assertRaises(TypeError, lambda: self.other <= self.set)
  1211.         self.assertRaises(TypeError, lambda: self.other > self.set)
  1212.         self.assertRaises(TypeError, lambda: self.other >= self.set)
  1213.  
  1214.     def test_update_operator(self):
  1215.         try:
  1216.             self.set |= self.other
  1217.         except TypeError:
  1218.             pass
  1219.         else:
  1220.             self.fail("expected TypeError")
  1221.  
  1222.     def test_update(self):
  1223.         if self.otherIsIterable:
  1224.             self.set.update(self.other)
  1225.         else:
  1226.             self.assertRaises(TypeError, self.set.update, self.other)
  1227.  
  1228.     def test_union(self):
  1229.         self.assertRaises(TypeError, lambda: self.set | self.other)
  1230.         self.assertRaises(TypeError, lambda: self.other | self.set)
  1231.         if self.otherIsIterable:
  1232.             self.set.union(self.other)
  1233.         else:
  1234.             self.assertRaises(TypeError, self.set.union, self.other)
  1235.  
  1236.     def test_intersection_update_operator(self):
  1237.         try:
  1238.             self.set &= self.other
  1239.         except TypeError:
  1240.             pass
  1241.         else:
  1242.             self.fail("expected TypeError")
  1243.  
  1244.     def test_intersection_update(self):
  1245.         if self.otherIsIterable:
  1246.             self.set.intersection_update(self.other)
  1247.         else:
  1248.             self.assertRaises(TypeError,
  1249.                               self.set.intersection_update,
  1250.                               self.other)
  1251.  
  1252.     def test_intersection(self):
  1253.         self.assertRaises(TypeError, lambda: self.set & self.other)
  1254.         self.assertRaises(TypeError, lambda: self.other & self.set)
  1255.         if self.otherIsIterable:
  1256.             self.set.intersection(self.other)
  1257.         else:
  1258.             self.assertRaises(TypeError, self.set.intersection, self.other)
  1259.  
  1260.     def test_sym_difference_update_operator(self):
  1261.         try:
  1262.             self.set ^= self.other
  1263.         except TypeError:
  1264.             pass
  1265.         else:
  1266.             self.fail("expected TypeError")
  1267.  
  1268.     def test_sym_difference_update(self):
  1269.         if self.otherIsIterable:
  1270.             self.set.symmetric_difference_update(self.other)
  1271.         else:
  1272.             self.assertRaises(TypeError,
  1273.                               self.set.symmetric_difference_update,
  1274.                               self.other)
  1275.  
  1276.     def test_sym_difference(self):
  1277.         self.assertRaises(TypeError, lambda: self.set ^ self.other)
  1278.         self.assertRaises(TypeError, lambda: self.other ^ self.set)
  1279.         if self.otherIsIterable:
  1280.             self.set.symmetric_difference(self.other)
  1281.         else:
  1282.             self.assertRaises(TypeError, self.set.symmetric_difference, self.other)
  1283.  
  1284.     def test_difference_update_operator(self):
  1285.         try:
  1286.             self.set -= self.other
  1287.         except TypeError:
  1288.             pass
  1289.         else:
  1290.             self.fail("expected TypeError")
  1291.  
  1292.     def test_difference_update(self):
  1293.         if self.otherIsIterable:
  1294.             self.set.difference_update(self.other)
  1295.         else:
  1296.             self.assertRaises(TypeError,
  1297.                               self.set.difference_update,
  1298.                               self.other)
  1299.  
  1300.     def test_difference(self):
  1301.         self.assertRaises(TypeError, lambda: self.set - self.other)
  1302.         self.assertRaises(TypeError, lambda: self.other - self.set)
  1303.         if self.otherIsIterable:
  1304.             self.set.difference(self.other)
  1305.         else:
  1306.             self.assertRaises(TypeError, self.set.difference, self.other)
  1307.  
  1308. #------------------------------------------------------------------------------
  1309.  
  1310. class TestOnlySetsNumeric(TestOnlySetsInBinaryOps):
  1311.     def setUp(self):
  1312.         self.set   = set((1, 2, 3))
  1313.         self.other = 19
  1314.         self.otherIsIterable = False
  1315.  
  1316. #------------------------------------------------------------------------------
  1317.  
  1318. class TestOnlySetsDict(TestOnlySetsInBinaryOps):
  1319.     def setUp(self):
  1320.         self.set   = set((1, 2, 3))
  1321.         self.other = {1:2, 3:4}
  1322.         self.otherIsIterable = True
  1323.  
  1324. #------------------------------------------------------------------------------
  1325.  
  1326. class TestOnlySetsOperator(TestOnlySetsInBinaryOps):
  1327.     def setUp(self):
  1328.         self.set   = set((1, 2, 3))
  1329.         self.other = operator.add
  1330.         self.otherIsIterable = False
  1331.  
  1332. #------------------------------------------------------------------------------
  1333.  
  1334. class TestOnlySetsTuple(TestOnlySetsInBinaryOps):
  1335.     def setUp(self):
  1336.         self.set   = set((1, 2, 3))
  1337.         self.other = (2, 4, 6)
  1338.         self.otherIsIterable = True
  1339.  
  1340. #------------------------------------------------------------------------------
  1341.  
  1342. class TestOnlySetsString(TestOnlySetsInBinaryOps):
  1343.     def setUp(self):
  1344.         self.set   = set((1, 2, 3))
  1345.         self.other = 'abc'
  1346.         self.otherIsIterable = True
  1347.  
  1348. #------------------------------------------------------------------------------
  1349.  
  1350. class TestOnlySetsGenerator(TestOnlySetsInBinaryOps):
  1351.     def setUp(self):
  1352.         def gen():
  1353.             for i in xrange(0, 10, 2):
  1354.                 yield i
  1355.         self.set   = set((1, 2, 3))
  1356.         self.other = gen()
  1357.         self.otherIsIterable = True
  1358.  
  1359. #==============================================================================
  1360.  
  1361. class TestCopying(unittest.TestCase):
  1362.  
  1363.     def test_copy(self):
  1364.         dup = self.set.copy()
  1365.         dup_list = list(dup); dup_list.sort()
  1366.         set_list = list(self.set); set_list.sort()
  1367.         self.assertEqual(len(dup_list), len(set_list))
  1368.         for i in range(len(dup_list)):
  1369.             self.failUnless(dup_list[i] is set_list[i])
  1370.  
  1371.     def test_deep_copy(self):
  1372.         dup = copy.deepcopy(self.set)
  1373.         ##print type(dup), repr(dup)
  1374.         dup_list = list(dup); dup_list.sort()
  1375.         set_list = list(self.set); set_list.sort()
  1376.         self.assertEqual(len(dup_list), len(set_list))
  1377.         for i in range(len(dup_list)):
  1378.             self.assertEqual(dup_list[i], set_list[i])
  1379.  
  1380. #------------------------------------------------------------------------------
  1381.  
  1382. class TestCopyingEmpty(TestCopying):
  1383.     def setUp(self):
  1384.         self.set = set()
  1385.  
  1386. #------------------------------------------------------------------------------
  1387.  
  1388. class TestCopyingSingleton(TestCopying):
  1389.     def setUp(self):
  1390.         self.set = set(["hello"])
  1391.  
  1392. #------------------------------------------------------------------------------
  1393.  
  1394. class TestCopyingTriple(TestCopying):
  1395.     def setUp(self):
  1396.         self.set = set(["zero", 0, None])
  1397.  
  1398. #------------------------------------------------------------------------------
  1399.  
  1400. class TestCopyingTuple(TestCopying):
  1401.     def setUp(self):
  1402.         self.set = set([(1, 2)])
  1403.  
  1404. #------------------------------------------------------------------------------
  1405.  
  1406. class TestCopyingNested(TestCopying):
  1407.     def setUp(self):
  1408.         self.set = set([((1, 2), (3, 4))])
  1409.  
  1410. #==============================================================================
  1411.  
  1412. class TestIdentities(unittest.TestCase):
  1413.     def setUp(self):
  1414.         self.a = set('abracadabra')
  1415.         self.b = set('alacazam')
  1416.  
  1417.     def test_binopsVsSubsets(self):
  1418.         a, b = self.a, self.b
  1419.         self.assert_(a - b < a)
  1420.         self.assert_(b - a < b)
  1421.         self.assert_(a & b < a)
  1422.         self.assert_(a & b < b)
  1423.         self.assert_(a | b > a)
  1424.         self.assert_(a | b > b)
  1425.         self.assert_(a ^ b < a | b)
  1426.  
  1427.     def test_commutativity(self):
  1428.         a, b = self.a, self.b
  1429.         self.assertEqual(a&b, b&a)
  1430.         self.assertEqual(a|b, b|a)
  1431.         self.assertEqual(a^b, b^a)
  1432.         if a != b:
  1433.             self.assertNotEqual(a-b, b-a)
  1434.  
  1435.     def test_summations(self):
  1436.         # check that sums of parts equal the whole
  1437.         a, b = self.a, self.b
  1438.         self.assertEqual((a-b)|(a&b)|(b-a), a|b)
  1439.         self.assertEqual((a&b)|(a^b), a|b)
  1440.         self.assertEqual(a|(b-a), a|b)
  1441.         self.assertEqual((a-b)|b, a|b)
  1442.         self.assertEqual((a-b)|(a&b), a)
  1443.         self.assertEqual((b-a)|(a&b), b)
  1444.         self.assertEqual((a-b)|(b-a), a^b)
  1445.  
  1446.     def test_exclusion(self):
  1447.         # check that inverse operations show non-overlap
  1448.         a, b, zero = self.a, self.b, set()
  1449.         self.assertEqual((a-b)&b, zero)
  1450.         self.assertEqual((b-a)&a, zero)
  1451.         self.assertEqual((a&b)&(a^b), zero)
  1452.  
  1453. # Tests derived from test_itertools.py =======================================
  1454.  
  1455. def R(seqn):
  1456.     'Regular generator'
  1457.     for i in seqn:
  1458.         yield i
  1459.  
  1460. class G:
  1461.     'Sequence using __getitem__'
  1462.     def __init__(self, seqn):
  1463.         self.seqn = seqn
  1464.     def __getitem__(self, i):
  1465.         return self.seqn[i]
  1466.  
  1467. class I:
  1468.     'Sequence using iterator protocol'
  1469.     def __init__(self, seqn):
  1470.         self.seqn = seqn
  1471.         self.i = 0
  1472.     def __iter__(self):
  1473.         return self
  1474.     def next(self):
  1475.         if self.i >= len(self.seqn): raise StopIteration
  1476.         v = self.seqn[self.i]
  1477.         self.i += 1
  1478.         return v
  1479.  
  1480. class Ig:
  1481.     'Sequence using iterator protocol defined with a generator'
  1482.     def __init__(self, seqn):
  1483.         self.seqn = seqn
  1484.         self.i = 0
  1485.     def __iter__(self):
  1486.         for val in self.seqn:
  1487.             yield val
  1488.  
  1489. class X:
  1490.     'Missing __getitem__ and __iter__'
  1491.     def __init__(self, seqn):
  1492.         self.seqn = seqn
  1493.         self.i = 0
  1494.     def next(self):
  1495.         if self.i >= len(self.seqn): raise StopIteration
  1496.         v = self.seqn[self.i]
  1497.         self.i += 1
  1498.         return v
  1499.  
  1500. class N:
  1501.     'Iterator missing next()'
  1502.     def __init__(self, seqn):
  1503.         self.seqn = seqn
  1504.         self.i = 0
  1505.     def __iter__(self):
  1506.         return self
  1507.  
  1508. class E:
  1509.     'Test propagation of exceptions'
  1510.     def __init__(self, seqn):
  1511.         self.seqn = seqn
  1512.         self.i = 0
  1513.     def __iter__(self):
  1514.         return self
  1515.     def next(self):
  1516.         3 // 0
  1517.  
  1518. class S:
  1519.     'Test immediate stop'
  1520.     def __init__(self, seqn):
  1521.         pass
  1522.     def __iter__(self):
  1523.         return self
  1524.     def next(self):
  1525.         raise StopIteration
  1526.  
  1527. from itertools import chain, imap
  1528. def L(seqn):
  1529.     'Test multiple tiers of iterators'
  1530.     return chain(imap(lambda x:x, R(Ig(G(seqn)))))
  1531.  
  1532. class TestVariousIteratorArgs(unittest.TestCase):
  1533.  
  1534.     def test_constructor(self):
  1535.         for cons in (set, frozenset):
  1536.             for s in ("123", "", range(1000), ('do', 1.2), xrange(2000,2200,5)):
  1537.                 for g in (G, I, Ig, S, L, R):
  1538.                     self.assertEqual(sorted(cons(g(s))), sorted(g(s)))
  1539.                 self.assertRaises(TypeError, cons , X(s))
  1540.                 self.assertRaises(TypeError, cons , N(s))
  1541.                 self.assertRaises(ZeroDivisionError, cons , E(s))
  1542.  
  1543.     def test_inline_methods(self):
  1544.         s = set('november')
  1545.         for data in ("123", "", range(1000), ('do', 1.2), xrange(2000,2200,5), 'december'):
  1546.             for meth in (s.union, s.intersection, s.difference, s.symmetric_difference, s.isdisjoint):
  1547.                 for g in (G, I, Ig, L, R):
  1548.                     expected = meth(data)
  1549.                     actual = meth(G(data))
  1550.                     if isinstance(expected, bool):
  1551.                         self.assertEqual(actual, expected)
  1552.                     else:
  1553.                         self.assertEqual(sorted(actual), sorted(expected))
  1554.                 self.assertRaises(TypeError, meth, X(s))
  1555.                 self.assertRaises(TypeError, meth, N(s))
  1556.                 self.assertRaises(ZeroDivisionError, meth, E(s))
  1557.  
  1558.     def test_inplace_methods(self):
  1559.         for data in ("123", "", range(1000), ('do', 1.2), xrange(2000,2200,5), 'december'):
  1560.             for methname in ('update', 'intersection_update',
  1561.                              'difference_update', 'symmetric_difference_update'):
  1562.                 for g in (G, I, Ig, S, L, R):
  1563.                     s = set('january')
  1564.                     t = s.copy()
  1565.                     getattr(s, methname)(list(g(data)))
  1566.                     getattr(t, methname)(g(data))
  1567.                     self.assertEqual(sorted(s), sorted(t))
  1568.  
  1569.                 self.assertRaises(TypeError, getattr(set('january'), methname), X(data))
  1570.                 self.assertRaises(TypeError, getattr(set('january'), methname), N(data))
  1571.                 self.assertRaises(ZeroDivisionError, getattr(set('january'), methname), E(data))
  1572.  
  1573. # Application tests (based on David Eppstein's graph recipes ====================================
  1574.  
  1575. def powerset(U):
  1576.     """Generates all subsets of a set or sequence U."""
  1577.     U = iter(U)
  1578.     try:
  1579.         x = frozenset([U.next()])
  1580.         for S in powerset(U):
  1581.             yield S
  1582.             yield S | x
  1583.     except StopIteration:
  1584.         yield frozenset()
  1585.  
  1586. def cube(n):
  1587.     """Graph of n-dimensional hypercube."""
  1588.     singletons = [frozenset([x]) for x in range(n)]
  1589.     return dict([(x, frozenset([x^s for s in singletons]))
  1590.                  for x in powerset(range(n))])
  1591.  
  1592. def linegraph(G):
  1593.     """Graph, the vertices of which are edges of G,
  1594.     with two vertices being adjacent iff the corresponding
  1595.     edges share a vertex."""
  1596.     L = {}
  1597.     for x in G:
  1598.         for y in G[x]:
  1599.             nx = [frozenset([x,z]) for z in G[x] if z != y]
  1600.             ny = [frozenset([y,z]) for z in G[y] if z != x]
  1601.             L[frozenset([x,y])] = frozenset(nx+ny)
  1602.     return L
  1603.  
  1604. def faces(G):
  1605.     'Return a set of faces in G.  Where a face is a set of vertices on that face'
  1606.     # currently limited to triangles,squares, and pentagons
  1607.     f = set()
  1608.     for v1, edges in G.items():
  1609.         for v2 in edges:
  1610.             for v3 in G[v2]:
  1611.                 if v1 == v3:
  1612.                     continue
  1613.                 if v1 in G[v3]:
  1614.                     f.add(frozenset([v1, v2, v3]))
  1615.                 else:
  1616.                     for v4 in G[v3]:
  1617.                         if v4 == v2:
  1618.                             continue
  1619.                         if v1 in G[v4]:
  1620.                             f.add(frozenset([v1, v2, v3, v4]))
  1621.                         else:
  1622.                             for v5 in G[v4]:
  1623.                                 if v5 == v3 or v5 == v2:
  1624.                                     continue
  1625.                                 if v1 in G[v5]:
  1626.                                     f.add(frozenset([v1, v2, v3, v4, v5]))
  1627.     return f
  1628.  
  1629.  
  1630. class TestGraphs(unittest.TestCase):
  1631.  
  1632.     def test_cube(self):
  1633.  
  1634.         g = cube(3)                             # vert --> {v1, v2, v3}
  1635.         vertices1 = set(g)
  1636.         self.assertEqual(len(vertices1), 8)     # eight vertices
  1637.         for edge in g.values():
  1638.             self.assertEqual(len(edge), 3)      # each vertex connects to three edges
  1639.         vertices2 = set(v for edges in g.values() for v in edges)
  1640.         self.assertEqual(vertices1, vertices2)  # edge vertices in original set
  1641.  
  1642.         cubefaces = faces(g)
  1643.         self.assertEqual(len(cubefaces), 6)     # six faces
  1644.         for face in cubefaces:
  1645.             self.assertEqual(len(face), 4)      # each face is a square
  1646.  
  1647.     def test_cuboctahedron(self):
  1648.  
  1649.         # http://en.wikipedia.org/wiki/Cuboctahedron
  1650.         # 8 triangular faces and 6 square faces
  1651.         # 12 indentical vertices each connecting a triangle and square
  1652.  
  1653.         g = cube(3)
  1654.         cuboctahedron = linegraph(g)            # V( --> {V1, V2, V3, V4}
  1655.         self.assertEqual(len(cuboctahedron), 12)# twelve vertices
  1656.  
  1657.         vertices = set(cuboctahedron)
  1658.         for edges in cuboctahedron.values():
  1659.             self.assertEqual(len(edges), 4)     # each vertex connects to four other vertices
  1660.         othervertices = set(edge for edges in cuboctahedron.values() for edge in edges)
  1661.         self.assertEqual(vertices, othervertices)   # edge vertices in original set
  1662.  
  1663.         cubofaces = faces(cuboctahedron)
  1664.         facesizes = collections.defaultdict(int)
  1665.         for face in cubofaces:
  1666.             facesizes[len(face)] += 1
  1667.         self.assertEqual(facesizes[3], 8)       # eight triangular faces
  1668.         self.assertEqual(facesizes[4], 6)       # six square faces
  1669.  
  1670.         for vertex in cuboctahedron:
  1671.             edge = vertex                       # Cuboctahedron vertices are edges in Cube
  1672.             self.assertEqual(len(edge), 2)      # Two cube vertices define an edge
  1673.             for cubevert in edge:
  1674.                 self.assert_(cubevert in g)
  1675.  
  1676.  
  1677. #==============================================================================
  1678.  
  1679. def test_main(verbose=None):
  1680.     from test import test_sets
  1681.     test_classes = (
  1682.         TestSet,
  1683.         TestSetSubclass,
  1684.         TestSetSubclassWithKeywordArgs,
  1685.         TestFrozenSet,
  1686.         TestFrozenSetSubclass,
  1687.         TestSetOfSets,
  1688.         TestExceptionPropagation,
  1689.         TestBasicOpsEmpty,
  1690.         TestBasicOpsSingleton,
  1691.         TestBasicOpsTuple,
  1692.         TestBasicOpsTriple,
  1693.         TestBinaryOps,
  1694.         TestUpdateOps,
  1695.         TestMutate,
  1696.         TestSubsetEqualEmpty,
  1697.         TestSubsetEqualNonEmpty,
  1698.         TestSubsetEmptyNonEmpty,
  1699.         TestSubsetPartial,
  1700.         TestSubsetNonOverlap,
  1701.         TestOnlySetsNumeric,
  1702.         TestOnlySetsDict,
  1703.         TestOnlySetsOperator,
  1704.         TestOnlySetsTuple,
  1705.         TestOnlySetsString,
  1706.         TestOnlySetsGenerator,
  1707.         TestCopyingEmpty,
  1708.         TestCopyingSingleton,
  1709.         TestCopyingTriple,
  1710.         TestCopyingTuple,
  1711.         TestCopyingNested,
  1712.         TestIdentities,
  1713.         TestVariousIteratorArgs,
  1714.         TestGraphs,
  1715.         )
  1716.  
  1717.     test_support.run_unittest(*test_classes)
  1718.  
  1719.     # verify reference counting
  1720.     if verbose and hasattr(sys, "gettotalrefcount"):
  1721.         import gc
  1722.         counts = [None] * 5
  1723.         for i in xrange(len(counts)):
  1724.             test_support.run_unittest(*test_classes)
  1725.             gc.collect()
  1726.             counts[i] = sys.gettotalrefcount()
  1727.         print counts
  1728.  
  1729. if __name__ == "__main__":
  1730.     test_main(verbose=True)
  1731.