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_bisect.py < prev    next >
Encoding:
Python Source  |  2011-03-15  |  12.7 KB  |  318 lines
  1. import sys
  2. import unittest
  3. from test import test_support
  4. from UserList import UserList
  5.  
  6. # We do a bit of trickery here to be able to test both the C implementation
  7. # and the Python implementation of the module.
  8.  
  9. # Make it impossible to import the C implementation anymore.
  10. sys.modules['_bisect'] = 0
  11. # We must also handle the case that bisect was imported before.
  12. if 'bisect' in sys.modules:
  13.     del sys.modules['bisect']
  14.  
  15. # Now we can import the module and get the pure Python implementation.
  16. import bisect as py_bisect
  17.  
  18. # Restore everything to normal.
  19. del sys.modules['_bisect']
  20. del sys.modules['bisect']
  21.  
  22. # This is now the module with the C implementation.
  23. import bisect as c_bisect
  24.  
  25.  
  26. class TestBisect(unittest.TestCase):
  27.     module = None
  28.  
  29.     def setUp(self):
  30.         self.precomputedCases = [
  31.             (self.module.bisect_right, [], 1, 0),
  32.             (self.module.bisect_right, [1], 0, 0),
  33.             (self.module.bisect_right, [1], 1, 1),
  34.             (self.module.bisect_right, [1], 2, 1),
  35.             (self.module.bisect_right, [1, 1], 0, 0),
  36.             (self.module.bisect_right, [1, 1], 1, 2),
  37.             (self.module.bisect_right, [1, 1], 2, 2),
  38.             (self.module.bisect_right, [1, 1, 1], 0, 0),
  39.             (self.module.bisect_right, [1, 1, 1], 1, 3),
  40.             (self.module.bisect_right, [1, 1, 1], 2, 3),
  41.             (self.module.bisect_right, [1, 1, 1, 1], 0, 0),
  42.             (self.module.bisect_right, [1, 1, 1, 1], 1, 4),
  43.             (self.module.bisect_right, [1, 1, 1, 1], 2, 4),
  44.             (self.module.bisect_right, [1, 2], 0, 0),
  45.             (self.module.bisect_right, [1, 2], 1, 1),
  46.             (self.module.bisect_right, [1, 2], 1.5, 1),
  47.             (self.module.bisect_right, [1, 2], 2, 2),
  48.             (self.module.bisect_right, [1, 2], 3, 2),
  49.             (self.module.bisect_right, [1, 1, 2, 2], 0, 0),
  50.             (self.module.bisect_right, [1, 1, 2, 2], 1, 2),
  51.             (self.module.bisect_right, [1, 1, 2, 2], 1.5, 2),
  52.             (self.module.bisect_right, [1, 1, 2, 2], 2, 4),
  53.             (self.module.bisect_right, [1, 1, 2, 2], 3, 4),
  54.             (self.module.bisect_right, [1, 2, 3], 0, 0),
  55.             (self.module.bisect_right, [1, 2, 3], 1, 1),
  56.             (self.module.bisect_right, [1, 2, 3], 1.5, 1),
  57.             (self.module.bisect_right, [1, 2, 3], 2, 2),
  58.             (self.module.bisect_right, [1, 2, 3], 2.5, 2),
  59.             (self.module.bisect_right, [1, 2, 3], 3, 3),
  60.             (self.module.bisect_right, [1, 2, 3], 4, 3),
  61.             (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 0, 0),
  62.             (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 1, 1),
  63.             (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 1.5, 1),
  64.             (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 2, 3),
  65.             (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 2.5, 3),
  66.             (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 3, 6),
  67.             (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 3.5, 6),
  68.             (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 4, 10),
  69.             (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 5, 10),
  70.  
  71.             (self.module.bisect_left, [], 1, 0),
  72.             (self.module.bisect_left, [1], 0, 0),
  73.             (self.module.bisect_left, [1], 1, 0),
  74.             (self.module.bisect_left, [1], 2, 1),
  75.             (self.module.bisect_left, [1, 1], 0, 0),
  76.             (self.module.bisect_left, [1, 1], 1, 0),
  77.             (self.module.bisect_left, [1, 1], 2, 2),
  78.             (self.module.bisect_left, [1, 1, 1], 0, 0),
  79.             (self.module.bisect_left, [1, 1, 1], 1, 0),
  80.             (self.module.bisect_left, [1, 1, 1], 2, 3),
  81.             (self.module.bisect_left, [1, 1, 1, 1], 0, 0),
  82.             (self.module.bisect_left, [1, 1, 1, 1], 1, 0),
  83.             (self.module.bisect_left, [1, 1, 1, 1], 2, 4),
  84.             (self.module.bisect_left, [1, 2], 0, 0),
  85.             (self.module.bisect_left, [1, 2], 1, 0),
  86.             (self.module.bisect_left, [1, 2], 1.5, 1),
  87.             (self.module.bisect_left, [1, 2], 2, 1),
  88.             (self.module.bisect_left, [1, 2], 3, 2),
  89.             (self.module.bisect_left, [1, 1, 2, 2], 0, 0),
  90.             (self.module.bisect_left, [1, 1, 2, 2], 1, 0),
  91.             (self.module.bisect_left, [1, 1, 2, 2], 1.5, 2),
  92.             (self.module.bisect_left, [1, 1, 2, 2], 2, 2),
  93.             (self.module.bisect_left, [1, 1, 2, 2], 3, 4),
  94.             (self.module.bisect_left, [1, 2, 3], 0, 0),
  95.             (self.module.bisect_left, [1, 2, 3], 1, 0),
  96.             (self.module.bisect_left, [1, 2, 3], 1.5, 1),
  97.             (self.module.bisect_left, [1, 2, 3], 2, 1),
  98.             (self.module.bisect_left, [1, 2, 3], 2.5, 2),
  99.             (self.module.bisect_left, [1, 2, 3], 3, 2),
  100.             (self.module.bisect_left, [1, 2, 3], 4, 3),
  101.             (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 0, 0),
  102.             (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 1, 0),
  103.             (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 1.5, 1),
  104.             (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 2, 1),
  105.             (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 2.5, 3),
  106.             (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 3, 3),
  107.             (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 3.5, 6),
  108.             (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 4, 6),
  109.             (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 5, 10)
  110.         ]
  111.  
  112.     def test_precomputed(self):
  113.         for func, data, elem, expected in self.precomputedCases:
  114.             self.assertEqual(func(data, elem), expected)
  115.             self.assertEqual(func(UserList(data), elem), expected)
  116.  
  117.     def test_negative_lo(self):
  118.         # Issue 3301
  119.         mod = self.module
  120.         self.assertRaises(ValueError, mod.bisect_left, [1, 2, 3], 5, -1, 3),
  121.         self.assertRaises(ValueError, mod.bisect_right, [1, 2, 3], 5, -1, 3),
  122.         self.assertRaises(ValueError, mod.insort_left, [1, 2, 3], 5, -1, 3),
  123.         self.assertRaises(ValueError, mod.insort_right, [1, 2, 3], 5, -1, 3),
  124.  
  125.     def test_random(self, n=25):
  126.         from random import randrange
  127.         for i in xrange(n):
  128.             data = [randrange(0, n, 2) for j in xrange(i)]
  129.             data.sort()
  130.             elem = randrange(-1, n+1)
  131.             ip = self.module.bisect_left(data, elem)
  132.             if ip < len(data):
  133.                 self.failUnless(elem <= data[ip])
  134.             if ip > 0:
  135.                 self.failUnless(data[ip-1] < elem)
  136.             ip = self.module.bisect_right(data, elem)
  137.             if ip < len(data):
  138.                 self.failUnless(elem < data[ip])
  139.             if ip > 0:
  140.                 self.failUnless(data[ip-1] <= elem)
  141.  
  142.     def test_optionalSlicing(self):
  143.         for func, data, elem, expected in self.precomputedCases:
  144.             for lo in xrange(4):
  145.                 lo = min(len(data), lo)
  146.                 for hi in xrange(3,8):
  147.                     hi = min(len(data), hi)
  148.                     ip = func(data, elem, lo, hi)
  149.                     self.failUnless(lo <= ip <= hi)
  150.                     if func is self.module.bisect_left and ip < hi:
  151.                         self.failUnless(elem <= data[ip])
  152.                     if func is self.module.bisect_left and ip > lo:
  153.                         self.failUnless(data[ip-1] < elem)
  154.                     if func is self.module.bisect_right and ip < hi:
  155.                         self.failUnless(elem < data[ip])
  156.                     if func is self.module.bisect_right and ip > lo:
  157.                         self.failUnless(data[ip-1] <= elem)
  158.                     self.assertEqual(ip, max(lo, min(hi, expected)))
  159.  
  160.     def test_backcompatibility(self):
  161.         self.assertEqual(self.module.bisect, self.module.bisect_right)
  162.  
  163.     def test_keyword_args(self):
  164.         data = [10, 20, 30, 40, 50]
  165.         self.assertEqual(self.module.bisect_left(a=data, x=25, lo=1, hi=3), 2)
  166.         self.assertEqual(self.module.bisect_right(a=data, x=25, lo=1, hi=3), 2)
  167.         self.assertEqual(self.module.bisect(a=data, x=25, lo=1, hi=3), 2)
  168.         self.module.insort_left(a=data, x=25, lo=1, hi=3)
  169.         self.module.insort_right(a=data, x=25, lo=1, hi=3)
  170.         self.module.insort(a=data, x=25, lo=1, hi=3)
  171.         self.assertEqual(data, [10, 20, 25, 25, 25, 30, 40, 50])
  172.  
  173. class TestBisectPython(TestBisect):
  174.     module = py_bisect
  175.  
  176. class TestBisectC(TestBisect):
  177.     module = c_bisect
  178.  
  179. #==============================================================================
  180.  
  181. class TestInsort(unittest.TestCase):
  182.     module = None
  183.  
  184.     def test_vsBuiltinSort(self, n=500):
  185.         from random import choice
  186.         for insorted in (list(), UserList()):
  187.             for i in xrange(n):
  188.                 digit = choice("0123456789")
  189.                 if digit in "02468":
  190.                     f = self.module.insort_left
  191.                 else:
  192.                     f = self.module.insort_right
  193.                 f(insorted, digit)
  194.         self.assertEqual(sorted(insorted), insorted)
  195.  
  196.     def test_backcompatibility(self):
  197.         self.assertEqual(self.module.insort, self.module.insort_right)
  198.  
  199.     def test_listDerived(self):
  200.         class List(list):
  201.             data = []
  202.             def insert(self, index, item):
  203.                 self.data.insert(index, item)
  204.  
  205.         lst = List()
  206.         self.module.insort_left(lst, 10)
  207.         self.module.insort_right(lst, 5)
  208.         self.assertEqual([5, 10], lst.data)
  209.  
  210. class TestInsortPython(TestInsort):
  211.     module = py_bisect
  212.  
  213. class TestInsortC(TestInsort):
  214.     module = c_bisect
  215.  
  216. #==============================================================================
  217.  
  218.  
  219. class LenOnly:
  220.     "Dummy sequence class defining __len__ but not __getitem__."
  221.     def __len__(self):
  222.         return 10
  223.  
  224. class GetOnly:
  225.     "Dummy sequence class defining __getitem__ but not __len__."
  226.     def __getitem__(self, ndx):
  227.         return 10
  228.  
  229. class CmpErr:
  230.     "Dummy element that always raises an error during comparison"
  231.     def __cmp__(self, other):
  232.         raise ZeroDivisionError
  233.  
  234. class TestErrorHandling(unittest.TestCase):
  235.     module = None
  236.  
  237.     def test_non_sequence(self):
  238.         for f in (self.module.bisect_left, self.module.bisect_right,
  239.                   self.module.insort_left, self.module.insort_right):
  240.             self.assertRaises(TypeError, f, 10, 10)
  241.  
  242.     def test_len_only(self):
  243.         for f in (self.module.bisect_left, self.module.bisect_right,
  244.                   self.module.insort_left, self.module.insort_right):
  245.             self.assertRaises(AttributeError, f, LenOnly(), 10)
  246.  
  247.     def test_get_only(self):
  248.         for f in (self.module.bisect_left, self.module.bisect_right,
  249.                   self.module.insort_left, self.module.insort_right):
  250.             self.assertRaises(AttributeError, f, GetOnly(), 10)
  251.  
  252.     def test_cmp_err(self):
  253.         seq = [CmpErr(), CmpErr(), CmpErr()]
  254.         for f in (self.module.bisect_left, self.module.bisect_right,
  255.                   self.module.insort_left, self.module.insort_right):
  256.             self.assertRaises(ZeroDivisionError, f, seq, 10)
  257.  
  258.     def test_arg_parsing(self):
  259.         for f in (self.module.bisect_left, self.module.bisect_right,
  260.                   self.module.insort_left, self.module.insort_right):
  261.             self.assertRaises(TypeError, f, 10)
  262.  
  263. class TestErrorHandlingPython(TestErrorHandling):
  264.     module = py_bisect
  265.  
  266. class TestErrorHandlingC(TestErrorHandling):
  267.     module = c_bisect
  268.  
  269. #==============================================================================
  270.  
  271. libreftest = """
  272. Example from the Library Reference:  Doc/library/bisect.rst
  273.  
  274. The bisect() function is generally useful for categorizing numeric data.
  275. This example uses bisect() to look up a letter grade for an exam total
  276. (say) based on a set of ordered numeric breakpoints: 85 and up is an `A',
  277. 75..84 is a `B', etc.
  278.  
  279.     >>> grades = "FEDCBA"
  280.     >>> breakpoints = [30, 44, 66, 75, 85]
  281.     >>> from bisect import bisect
  282.     >>> def grade(total):
  283.     ...           return grades[bisect(breakpoints, total)]
  284.     ...
  285.     >>> grade(66)
  286.     'C'
  287.     >>> map(grade, [33, 99, 77, 44, 12, 88])
  288.     ['E', 'A', 'B', 'D', 'F', 'A']
  289.  
  290. """
  291.  
  292. #------------------------------------------------------------------------------
  293.  
  294. __test__ = {'libreftest' : libreftest}
  295.  
  296. def test_main(verbose=None):
  297.     from test import test_bisect
  298.  
  299.     test_classes = [TestBisectPython, TestBisectC,
  300.                     TestInsortPython, TestInsortC,
  301.                     TestErrorHandlingPython, TestErrorHandlingC]
  302.  
  303.     test_support.run_unittest(*test_classes)
  304.     test_support.run_doctest(test_bisect, verbose)
  305.  
  306.     # verify reference counting
  307.     if verbose and hasattr(sys, "gettotalrefcount"):
  308.         import gc
  309.         counts = [None] * 5
  310.         for i in xrange(len(counts)):
  311.             test_support.run_unittest(*test_classes)
  312.             gc.collect()
  313.             counts[i] = sys.gettotalrefcount()
  314.         print counts
  315.  
  316. if __name__ == "__main__":
  317.     test_main(verbose=True)
  318.