Home | History | Annotate | Download | only in test 
      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.assertTrue(elem <= data[ip])
    134             if ip > 0:
    135                 self.assertTrue(data[ip-1] < elem)
    136             ip = self.module.bisect_right(data, elem)
    137             if ip < len(data):
    138                 self.assertTrue(elem < data[ip])
    139             if ip > 0:
    140                 self.assertTrue(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.assertTrue(lo <= ip <= hi)
    150                     if func is self.module.bisect_left and ip < hi:
    151                         self.assertTrue(elem <= data[ip])
    152                     if func is self.module.bisect_left and ip > lo:
    153                         self.assertTrue(data[ip-1] < elem)
    154                     if func is self.module.bisect_right and ip < hi:
    155                         self.assertTrue(elem < data[ip])
    156                     if func is self.module.bisect_right and ip > lo:
    157                         self.assertTrue(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