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)