import unittest from test import test_support from bisect import bisect_right, bisect_left, insort_left, insort_right, insort, bisect from UserList import UserList class TestBisect(unittest.TestCase): precomputedCases = [ (bisect_right, [], 1, 0), (bisect_right, [1], 0, 0), (bisect_right, [1], 1, 1), (bisect_right, [1], 2, 1), (bisect_right, [1, 1], 0, 0), (bisect_right, [1, 1], 1, 2), (bisect_right, [1, 1], 2, 2), (bisect_right, [1, 1, 1], 0, 0), (bisect_right, [1, 1, 1], 1, 3), (bisect_right, [1, 1, 1], 2, 3), (bisect_right, [1, 1, 1, 1], 0, 0), (bisect_right, [1, 1, 1, 1], 1, 4), (bisect_right, [1, 1, 1, 1], 2, 4), (bisect_right, [1, 2], 0, 0), (bisect_right, [1, 2], 1, 1), (bisect_right, [1, 2], 1.5, 1), (bisect_right, [1, 2], 2, 2), (bisect_right, [1, 2], 3, 2), (bisect_right, [1, 1, 2, 2], 0, 0), (bisect_right, [1, 1, 2, 2], 1, 2), (bisect_right, [1, 1, 2, 2], 1.5, 2), (bisect_right, [1, 1, 2, 2], 2, 4), (bisect_right, [1, 1, 2, 2], 3, 4), (bisect_right, [1, 2, 3], 0, 0), (bisect_right, [1, 2, 3], 1, 1), (bisect_right, [1, 2, 3], 1.5, 1), (bisect_right, [1, 2, 3], 2, 2), (bisect_right, [1, 2, 3], 2.5, 2), (bisect_right, [1, 2, 3], 3, 3), (bisect_right, [1, 2, 3], 4, 3), (bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 0, 0), (bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 1, 1), (bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 1.5, 1), (bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 2, 3), (bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 2.5, 3), (bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 3, 6), (bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 3.5, 6), (bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 4, 10), (bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 5, 10), (bisect_left, [], 1, 0), (bisect_left, [1], 0, 0), (bisect_left, [1], 1, 0), (bisect_left, [1], 2, 1), (bisect_left, [1, 1], 0, 0), (bisect_left, [1, 1], 1, 0), (bisect_left, [1, 1], 2, 2), (bisect_left, [1, 1, 1], 0, 0), (bisect_left, [1, 1, 1], 1, 0), (bisect_left, [1, 1, 1], 2, 3), (bisect_left, [1, 1, 1, 1], 0, 0), (bisect_left, [1, 1, 1, 1], 1, 0), (bisect_left, [1, 1, 1, 1], 2, 4), (bisect_left, [1, 2], 0, 0), (bisect_left, [1, 2], 1, 0), (bisect_left, [1, 2], 1.5, 1), (bisect_left, [1, 2], 2, 1), (bisect_left, [1, 2], 3, 2), (bisect_left, [1, 1, 2, 2], 0, 0), (bisect_left, [1, 1, 2, 2], 1, 0), (bisect_left, [1, 1, 2, 2], 1.5, 2), (bisect_left, [1, 1, 2, 2], 2, 2), (bisect_left, [1, 1, 2, 2], 3, 4), (bisect_left, [1, 2, 3], 0, 0), (bisect_left, [1, 2, 3], 1, 0), (bisect_left, [1, 2, 3], 1.5, 1), (bisect_left, [1, 2, 3], 2, 1), (bisect_left, [1, 2, 3], 2.5, 2), (bisect_left, [1, 2, 3], 3, 2), (bisect_left, [1, 2, 3], 4, 3), (bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 0, 0), (bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 1, 0), (bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 1.5, 1), (bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 2, 1), (bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 2.5, 3), (bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 3, 3), (bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 3.5, 6), (bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 4, 6), (bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 5, 10) ] def test_precomputed(self): for func, data, elem, expected in self.precomputedCases: self.assertEqual(func(data, elem), expected) self.assertEqual(func(UserList(data), elem), expected) def test_random(self, n=25): from random import randrange for i in xrange(n): data = [randrange(0, n, 2) for j in xrange(i)] data.sort() elem = randrange(-1, n+1) ip = bisect_left(data, elem) if ip < len(data): self.failUnless(elem <= data[ip]) if ip > 0: self.failUnless(data[ip-1] < elem) ip = bisect_right(data, elem) if ip < len(data): self.failUnless(elem < data[ip]) if ip > 0: self.failUnless(data[ip-1] <= elem) def test_optionalSlicing(self): for func, data, elem, expected in self.precomputedCases: for lo in xrange(4): lo = min(len(data), lo) for hi in xrange(3,8): hi = min(len(data), hi) ip = func(data, elem, lo, hi) self.failUnless(lo <= ip <= hi) if func is bisect_left and ip < hi: self.failUnless(elem <= data[ip]) if func is bisect_left and ip > lo: self.failUnless(data[ip-1] < elem) if func is bisect_right and ip < hi: self.failUnless(elem < data[ip]) if func is bisect_right and ip > lo: self.failUnless(data[ip-1] <= elem) self.assertEqual(ip, max(lo, min(hi, expected))) def test_backcompatibility(self): self.assertEqual(bisect, bisect_right) def test_keyword_args(self): data = [10, 20, 30, 40, 50] self.assertEqual(bisect_left(a=data, x=25, lo=1, hi=3), 2) self.assertEqual(bisect_right(a=data, x=25, lo=1, hi=3), 2) self.assertEqual(bisect(a=data, x=25, lo=1, hi=3), 2) insort_left(a=data, x=25, lo=1, hi=3) insort_right(a=data, x=25, lo=1, hi=3) insort(a=data, x=25, lo=1, hi=3) self.assertEqual(data, [10, 20, 25, 25, 25, 30, 40, 50]) #============================================================================== class TestInsort(unittest.TestCase): def test_vsBuiltinSort(self, n=500): from random import choice for insorted in (list(), UserList()): for i in xrange(n): digit = choice("0123456789") if digit in "02468": f = insort_left else: f = insort_right f(insorted, digit) self.assertEqual(sorted(insorted), insorted) def test_backcompatibility(self): self.assertEqual(insort, insort_right) #============================================================================== class LenOnly: "Dummy sequence class defining __len__ but not __getitem__." def __len__(self): return 10 class GetOnly: "Dummy sequence class defining __getitem__ but not __len__." def __getitem__(self, ndx): return 10 class CmpErr: "Dummy element that always raises an error during comparison" def __cmp__(self, other): raise ZeroDivisionError class TestErrorHandling(unittest.TestCase): def test_non_sequence(self): for f in (bisect_left, bisect_right, insort_left, insort_right): self.assertRaises(TypeError, f, 10, 10) def test_len_only(self): for f in (bisect_left, bisect_right, insort_left, insort_right): self.assertRaises(TypeError, f, LenOnly(), 10) def test_get_only(self): for f in (bisect_left, bisect_right, insort_left, insort_right): self.assertRaises(TypeError, f, GetOnly(), 10) def test_cmp_err(self): seq = [CmpErr(), CmpErr(), CmpErr()] for f in (bisect_left, bisect_right, insort_left, insort_right): self.assertRaises(ZeroDivisionError, f, seq, 10) def test_arg_parsing(self): for f in (bisect_left, bisect_right, insort_left, insort_right): self.assertRaises(TypeError, f, 10) #============================================================================== libreftest = """ Example from the Library Reference: Doc/lib/libbisect.tex The bisect() function is generally useful for categorizing numeric data. This example uses bisect() to look up a letter grade for an exam total (say) based on a set of ordered numeric breakpoints: 85 and up is an `A', 75..84 is a `B', etc. >>> grades = "FEDCBA" >>> breakpoints = [30, 44, 66, 75, 85] >>> from bisect import bisect >>> def grade(total): ... return grades[bisect(breakpoints, total)] ... >>> grade(66) 'C' >>> map(grade, [33, 99, 77, 44, 12, 88]) ['E', 'A', 'B', 'D', 'F', 'A'] """ #------------------------------------------------------------------------------ __test__ = {'libreftest' : libreftest} def test_main(verbose=None): from test import test_bisect from types import BuiltinFunctionType import sys test_classes = [TestBisect, TestInsort] if isinstance(bisect_left, BuiltinFunctionType): test_classes.append(TestErrorHandling) test_support.run_unittest(*test_classes) test_support.run_doctest(test_bisect, verbose) # verify reference counting if verbose and hasattr(sys, "gettotalrefcount"): import gc counts = [None] * 5 for i in xrange(len(counts)): test_support.run_unittest(*test_classes) gc.collect() counts[i] = sys.gettotalrefcount() print counts if __name__ == "__main__": test_main(verbose=True)