Back to index

python3.2  3.2.2
test_bisect.py
Go to the documentation of this file.
00001 import sys
00002 import unittest
00003 from test import support
00004 from collections import UserList
00005 
00006 # We do a bit of trickery here to be able to test both the C implementation
00007 # and the Python implementation of the module.
00008 
00009 # Make it impossible to import the C implementation anymore.
00010 sys.modules['_bisect'] = 0
00011 # We must also handle the case that bisect was imported before.
00012 if 'bisect' in sys.modules:
00013     del sys.modules['bisect']
00014 
00015 # Now we can import the module and get the pure Python implementation.
00016 import bisect as py_bisect
00017 
00018 # Restore everything to normal.
00019 del sys.modules['_bisect']
00020 del sys.modules['bisect']
00021 
00022 # This is now the module with the C implementation.
00023 import bisect as c_bisect
00024 
00025 
00026 class TestBisect(unittest.TestCase):
00027     module = None
00028 
00029     def setUp(self):
00030         self.precomputedCases = [
00031             (self.module.bisect_right, [], 1, 0),
00032             (self.module.bisect_right, [1], 0, 0),
00033             (self.module.bisect_right, [1], 1, 1),
00034             (self.module.bisect_right, [1], 2, 1),
00035             (self.module.bisect_right, [1, 1], 0, 0),
00036             (self.module.bisect_right, [1, 1], 1, 2),
00037             (self.module.bisect_right, [1, 1], 2, 2),
00038             (self.module.bisect_right, [1, 1, 1], 0, 0),
00039             (self.module.bisect_right, [1, 1, 1], 1, 3),
00040             (self.module.bisect_right, [1, 1, 1], 2, 3),
00041             (self.module.bisect_right, [1, 1, 1, 1], 0, 0),
00042             (self.module.bisect_right, [1, 1, 1, 1], 1, 4),
00043             (self.module.bisect_right, [1, 1, 1, 1], 2, 4),
00044             (self.module.bisect_right, [1, 2], 0, 0),
00045             (self.module.bisect_right, [1, 2], 1, 1),
00046             (self.module.bisect_right, [1, 2], 1.5, 1),
00047             (self.module.bisect_right, [1, 2], 2, 2),
00048             (self.module.bisect_right, [1, 2], 3, 2),
00049             (self.module.bisect_right, [1, 1, 2, 2], 0, 0),
00050             (self.module.bisect_right, [1, 1, 2, 2], 1, 2),
00051             (self.module.bisect_right, [1, 1, 2, 2], 1.5, 2),
00052             (self.module.bisect_right, [1, 1, 2, 2], 2, 4),
00053             (self.module.bisect_right, [1, 1, 2, 2], 3, 4),
00054             (self.module.bisect_right, [1, 2, 3], 0, 0),
00055             (self.module.bisect_right, [1, 2, 3], 1, 1),
00056             (self.module.bisect_right, [1, 2, 3], 1.5, 1),
00057             (self.module.bisect_right, [1, 2, 3], 2, 2),
00058             (self.module.bisect_right, [1, 2, 3], 2.5, 2),
00059             (self.module.bisect_right, [1, 2, 3], 3, 3),
00060             (self.module.bisect_right, [1, 2, 3], 4, 3),
00061             (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 0, 0),
00062             (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 1, 1),
00063             (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 1.5, 1),
00064             (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 2, 3),
00065             (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 2.5, 3),
00066             (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 3, 6),
00067             (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 3.5, 6),
00068             (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 4, 10),
00069             (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 5, 10),
00070 
00071             (self.module.bisect_left, [], 1, 0),
00072             (self.module.bisect_left, [1], 0, 0),
00073             (self.module.bisect_left, [1], 1, 0),
00074             (self.module.bisect_left, [1], 2, 1),
00075             (self.module.bisect_left, [1, 1], 0, 0),
00076             (self.module.bisect_left, [1, 1], 1, 0),
00077             (self.module.bisect_left, [1, 1], 2, 2),
00078             (self.module.bisect_left, [1, 1, 1], 0, 0),
00079             (self.module.bisect_left, [1, 1, 1], 1, 0),
00080             (self.module.bisect_left, [1, 1, 1], 2, 3),
00081             (self.module.bisect_left, [1, 1, 1, 1], 0, 0),
00082             (self.module.bisect_left, [1, 1, 1, 1], 1, 0),
00083             (self.module.bisect_left, [1, 1, 1, 1], 2, 4),
00084             (self.module.bisect_left, [1, 2], 0, 0),
00085             (self.module.bisect_left, [1, 2], 1, 0),
00086             (self.module.bisect_left, [1, 2], 1.5, 1),
00087             (self.module.bisect_left, [1, 2], 2, 1),
00088             (self.module.bisect_left, [1, 2], 3, 2),
00089             (self.module.bisect_left, [1, 1, 2, 2], 0, 0),
00090             (self.module.bisect_left, [1, 1, 2, 2], 1, 0),
00091             (self.module.bisect_left, [1, 1, 2, 2], 1.5, 2),
00092             (self.module.bisect_left, [1, 1, 2, 2], 2, 2),
00093             (self.module.bisect_left, [1, 1, 2, 2], 3, 4),
00094             (self.module.bisect_left, [1, 2, 3], 0, 0),
00095             (self.module.bisect_left, [1, 2, 3], 1, 0),
00096             (self.module.bisect_left, [1, 2, 3], 1.5, 1),
00097             (self.module.bisect_left, [1, 2, 3], 2, 1),
00098             (self.module.bisect_left, [1, 2, 3], 2.5, 2),
00099             (self.module.bisect_left, [1, 2, 3], 3, 2),
00100             (self.module.bisect_left, [1, 2, 3], 4, 3),
00101             (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 0, 0),
00102             (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 1, 0),
00103             (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 1.5, 1),
00104             (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 2, 1),
00105             (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 2.5, 3),
00106             (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 3, 3),
00107             (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 3.5, 6),
00108             (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 4, 6),
00109             (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 5, 10)
00110         ]
00111 
00112     def test_precomputed(self):
00113         for func, data, elem, expected in self.precomputedCases:
00114             self.assertEqual(func(data, elem), expected)
00115             self.assertEqual(func(UserList(data), elem), expected)
00116 
00117     def test_negative_lo(self):
00118         # Issue 3301
00119         mod = self.module
00120         self.assertRaises(ValueError, mod.bisect_left, [1, 2, 3], 5, -1, 3),
00121         self.assertRaises(ValueError, mod.bisect_right, [1, 2, 3], 5, -1, 3),
00122         self.assertRaises(ValueError, mod.insort_left, [1, 2, 3], 5, -1, 3),
00123         self.assertRaises(ValueError, mod.insort_right, [1, 2, 3], 5, -1, 3),
00124 
00125     def test_random(self, n=25):
00126         from random import randrange
00127         for i in range(n):
00128             data = [randrange(0, n, 2) for j in range(i)]
00129             data.sort()
00130             elem = randrange(-1, n+1)
00131             ip = self.module.bisect_left(data, elem)
00132             if ip < len(data):
00133                 self.assertTrue(elem <= data[ip])
00134             if ip > 0:
00135                 self.assertTrue(data[ip-1] < elem)
00136             ip = self.module.bisect_right(data, elem)
00137             if ip < len(data):
00138                 self.assertTrue(elem < data[ip])
00139             if ip > 0:
00140                 self.assertTrue(data[ip-1] <= elem)
00141 
00142     def test_optionalSlicing(self):
00143         for func, data, elem, expected in self.precomputedCases:
00144             for lo in range(4):
00145                 lo = min(len(data), lo)
00146                 for hi in range(3,8):
00147                     hi = min(len(data), hi)
00148                     ip = func(data, elem, lo, hi)
00149                     self.assertTrue(lo <= ip <= hi)
00150                     if func is self.module.bisect_left and ip < hi:
00151                         self.assertTrue(elem <= data[ip])
00152                     if func is self.module.bisect_left and ip > lo:
00153                         self.assertTrue(data[ip-1] < elem)
00154                     if func is self.module.bisect_right and ip < hi:
00155                         self.assertTrue(elem < data[ip])
00156                     if func is self.module.bisect_right and ip > lo:
00157                         self.assertTrue(data[ip-1] <= elem)
00158                     self.assertEqual(ip, max(lo, min(hi, expected)))
00159 
00160     def test_backcompatibility(self):
00161         self.assertEqual(self.module.bisect, self.module.bisect_right)
00162 
00163     def test_keyword_args(self):
00164         data = [10, 20, 30, 40, 50]
00165         self.assertEqual(self.module.bisect_left(a=data, x=25, lo=1, hi=3), 2)
00166         self.assertEqual(self.module.bisect_right(a=data, x=25, lo=1, hi=3), 2)
00167         self.assertEqual(self.module.bisect(a=data, x=25, lo=1, hi=3), 2)
00168         self.module.insort_left(a=data, x=25, lo=1, hi=3)
00169         self.module.insort_right(a=data, x=25, lo=1, hi=3)
00170         self.module.insort(a=data, x=25, lo=1, hi=3)
00171         self.assertEqual(data, [10, 20, 25, 25, 25, 30, 40, 50])
00172 
00173 class TestBisectPython(TestBisect):
00174     module = py_bisect
00175 
00176 class TestBisectC(TestBisect):
00177     module = c_bisect
00178 
00179 #==============================================================================
00180 
00181 class TestInsort(unittest.TestCase):
00182     module = None
00183 
00184     def test_vsBuiltinSort(self, n=500):
00185         from random import choice
00186         for insorted in (list(), UserList()):
00187             for i in range(n):
00188                 digit = choice("0123456789")
00189                 if digit in "02468":
00190                     f = self.module.insort_left
00191                 else:
00192                     f = self.module.insort_right
00193                 f(insorted, digit)
00194         self.assertEqual(sorted(insorted), insorted)
00195 
00196     def test_backcompatibility(self):
00197         self.assertEqual(self.module.insort, self.module.insort_right)
00198 
00199     def test_listDerived(self):
00200         class List(list):
00201             data = []
00202             def insert(self, index, item):
00203                 self.data.insert(index, item)
00204 
00205         lst = List()
00206         self.module.insort_left(lst, 10)
00207         self.module.insort_right(lst, 5)
00208         self.assertEqual([5, 10], lst.data)
00209 
00210 class TestInsortPython(TestInsort):
00211     module = py_bisect
00212 
00213 class TestInsortC(TestInsort):
00214     module = c_bisect
00215 
00216 #==============================================================================
00217 
00218 
00219 class LenOnly:
00220     "Dummy sequence class defining __len__ but not __getitem__."
00221     def __len__(self):
00222         return 10
00223 
00224 class GetOnly:
00225     "Dummy sequence class defining __getitem__ but not __len__."
00226     def __getitem__(self, ndx):
00227         return 10
00228 
00229 class CmpErr:
00230     "Dummy element that always raises an error during comparison"
00231     def __lt__(self, other):
00232         raise ZeroDivisionError
00233     __gt__ = __lt__
00234     __le__ = __lt__
00235     __ge__ = __lt__
00236     __eq__ = __lt__
00237     __ne__ = __lt__
00238 
00239 class TestErrorHandling(unittest.TestCase):
00240     module = None
00241 
00242     def test_non_sequence(self):
00243         for f in (self.module.bisect_left, self.module.bisect_right,
00244                   self.module.insort_left, self.module.insort_right):
00245             self.assertRaises(TypeError, f, 10, 10)
00246 
00247     def test_len_only(self):
00248         for f in (self.module.bisect_left, self.module.bisect_right,
00249                   self.module.insort_left, self.module.insort_right):
00250             self.assertRaises(TypeError, f, LenOnly(), 10)
00251 
00252     def test_get_only(self):
00253         for f in (self.module.bisect_left, self.module.bisect_right,
00254                   self.module.insort_left, self.module.insort_right):
00255             self.assertRaises(TypeError, f, GetOnly(), 10)
00256 
00257     def test_cmp_err(self):
00258         seq = [CmpErr(), CmpErr(), CmpErr()]
00259         for f in (self.module.bisect_left, self.module.bisect_right,
00260                   self.module.insort_left, self.module.insort_right):
00261             self.assertRaises(ZeroDivisionError, f, seq, 10)
00262 
00263     def test_arg_parsing(self):
00264         for f in (self.module.bisect_left, self.module.bisect_right,
00265                   self.module.insort_left, self.module.insort_right):
00266             self.assertRaises(TypeError, f, 10)
00267 
00268 class TestErrorHandlingPython(TestErrorHandling):
00269     module = py_bisect
00270 
00271 class TestErrorHandlingC(TestErrorHandling):
00272     module = c_bisect
00273 
00274 #==============================================================================
00275 
00276 libreftest = """
00277 Example from the Library Reference:  Doc/library/bisect.rst
00278 
00279 The bisect() function is generally useful for categorizing numeric data.
00280 This example uses bisect() to look up a letter grade for an exam total
00281 (say) based on a set of ordered numeric breakpoints: 85 and up is an `A',
00282 75..84 is a `B', etc.
00283 
00284     >>> grades = "FEDCBA"
00285     >>> breakpoints = [30, 44, 66, 75, 85]
00286     >>> from bisect import bisect
00287     >>> def grade(total):
00288     ...           return grades[bisect(breakpoints, total)]
00289     ...
00290     >>> grade(66)
00291     'C'
00292     >>> list(map(grade, [33, 99, 77, 44, 12, 88]))
00293     ['E', 'A', 'B', 'D', 'F', 'A']
00294 
00295 """
00296 
00297 #------------------------------------------------------------------------------
00298 
00299 __test__ = {'libreftest' : libreftest}
00300 
00301 def test_main(verbose=None):
00302     from test import test_bisect
00303 
00304     test_classes = [TestBisectPython, TestBisectC,
00305                     TestInsortPython, TestInsortC,
00306                     TestErrorHandlingPython, TestErrorHandlingC]
00307 
00308     support.run_unittest(*test_classes)
00309     support.run_doctest(test_bisect, verbose)
00310 
00311     # verify reference counting
00312     if verbose and hasattr(sys, "gettotalrefcount"):
00313         import gc
00314         counts = [None] * 5
00315         for i in range(len(counts)):
00316             support.run_unittest(*test_classes)
00317             gc.collect()
00318             counts[i] = sys.gettotalrefcount()
00319         print(counts)
00320 
00321 if __name__ == "__main__":
00322     test_main(verbose=True)