Home | History | Annotate | Download | only in test 
      1 import sys
      2 import unittest
      3 from test import support
      4 from collections import UserList
      5 
      6 py_bisect = support.import_fresh_module('bisect', blocked=['_bisect'])
      7 c_bisect = support.import_fresh_module('bisect', fresh=['_bisect'])
      8 
      9 class Range(object):
     10     """A trivial range()-like object that has an insert() method."""
     11     def __init__(self, start, stop):
     12         self.start = start
     13         self.stop = stop
     14         self.last_insert = None
     15 
     16     def __len__(self):
     17         return self.stop - self.start
     18 
     19     def __getitem__(self, idx):
     20         n = self.stop - self.start
     21         if idx < 0:
     22             idx += n
     23         if idx >= n:
     24             raise IndexError(idx)
     25         return self.start + idx
     26 
     27     def insert(self, idx, item):
     28         self.last_insert = idx, item
     29 
     30 
     31 class TestBisect:
     32     def setUp(self):
     33         self.precomputedCases = [
     34             (self.module.bisect_right, [], 1, 0),
     35             (self.module.bisect_right, [1], 0, 0),
     36             (self.module.bisect_right, [1], 1, 1),
     37             (self.module.bisect_right, [1], 2, 1),
     38             (self.module.bisect_right, [1, 1], 0, 0),
     39             (self.module.bisect_right, [1, 1], 1, 2),
     40             (self.module.bisect_right, [1, 1], 2, 2),
     41             (self.module.bisect_right, [1, 1, 1], 0, 0),
     42             (self.module.bisect_right, [1, 1, 1], 1, 3),
     43             (self.module.bisect_right, [1, 1, 1], 2, 3),
     44             (self.module.bisect_right, [1, 1, 1, 1], 0, 0),
     45             (self.module.bisect_right, [1, 1, 1, 1], 1, 4),
     46             (self.module.bisect_right, [1, 1, 1, 1], 2, 4),
     47             (self.module.bisect_right, [1, 2], 0, 0),
     48             (self.module.bisect_right, [1, 2], 1, 1),
     49             (self.module.bisect_right, [1, 2], 1.5, 1),
     50             (self.module.bisect_right, [1, 2], 2, 2),
     51             (self.module.bisect_right, [1, 2], 3, 2),
     52             (self.module.bisect_right, [1, 1, 2, 2], 0, 0),
     53             (self.module.bisect_right, [1, 1, 2, 2], 1, 2),
     54             (self.module.bisect_right, [1, 1, 2, 2], 1.5, 2),
     55             (self.module.bisect_right, [1, 1, 2, 2], 2, 4),
     56             (self.module.bisect_right, [1, 1, 2, 2], 3, 4),
     57             (self.module.bisect_right, [1, 2, 3], 0, 0),
     58             (self.module.bisect_right, [1, 2, 3], 1, 1),
     59             (self.module.bisect_right, [1, 2, 3], 1.5, 1),
     60             (self.module.bisect_right, [1, 2, 3], 2, 2),
     61             (self.module.bisect_right, [1, 2, 3], 2.5, 2),
     62             (self.module.bisect_right, [1, 2, 3], 3, 3),
     63             (self.module.bisect_right, [1, 2, 3], 4, 3),
     64             (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 0, 0),
     65             (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 1, 1),
     66             (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 1.5, 1),
     67             (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 2, 3),
     68             (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 2.5, 3),
     69             (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 3, 6),
     70             (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 3.5, 6),
     71             (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 4, 10),
     72             (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 5, 10),
     73 
     74             (self.module.bisect_left, [], 1, 0),
     75             (self.module.bisect_left, [1], 0, 0),
     76             (self.module.bisect_left, [1], 1, 0),
     77             (self.module.bisect_left, [1], 2, 1),
     78             (self.module.bisect_left, [1, 1], 0, 0),
     79             (self.module.bisect_left, [1, 1], 1, 0),
     80             (self.module.bisect_left, [1, 1], 2, 2),
     81             (self.module.bisect_left, [1, 1, 1], 0, 0),
     82             (self.module.bisect_left, [1, 1, 1], 1, 0),
     83             (self.module.bisect_left, [1, 1, 1], 2, 3),
     84             (self.module.bisect_left, [1, 1, 1, 1], 0, 0),
     85             (self.module.bisect_left, [1, 1, 1, 1], 1, 0),
     86             (self.module.bisect_left, [1, 1, 1, 1], 2, 4),
     87             (self.module.bisect_left, [1, 2], 0, 0),
     88             (self.module.bisect_left, [1, 2], 1, 0),
     89             (self.module.bisect_left, [1, 2], 1.5, 1),
     90             (self.module.bisect_left, [1, 2], 2, 1),
     91             (self.module.bisect_left, [1, 2], 3, 2),
     92             (self.module.bisect_left, [1, 1, 2, 2], 0, 0),
     93             (self.module.bisect_left, [1, 1, 2, 2], 1, 0),
     94             (self.module.bisect_left, [1, 1, 2, 2], 1.5, 2),
     95             (self.module.bisect_left, [1, 1, 2, 2], 2, 2),
     96             (self.module.bisect_left, [1, 1, 2, 2], 3, 4),
     97             (self.module.bisect_left, [1, 2, 3], 0, 0),
     98             (self.module.bisect_left, [1, 2, 3], 1, 0),
     99             (self.module.bisect_left, [1, 2, 3], 1.5, 1),
    100             (self.module.bisect_left, [1, 2, 3], 2, 1),
    101             (self.module.bisect_left, [1, 2, 3], 2.5, 2),
    102             (self.module.bisect_left, [1, 2, 3], 3, 2),
    103             (self.module.bisect_left, [1, 2, 3], 4, 3),
    104             (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 0, 0),
    105             (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 1, 0),
    106             (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 1.5, 1),
    107             (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 2, 1),
    108             (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 2.5, 3),
    109             (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 3, 3),
    110             (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 3.5, 6),
    111             (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 4, 6),
    112             (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 5, 10)
    113         ]
    114 
    115     def test_precomputed(self):
    116         for func, data, elem, expected in self.precomputedCases:
    117             self.assertEqual(func(data, elem), expected)
    118             self.assertEqual(func(UserList(data), elem), expected)
    119 
    120     def test_negative_lo(self):
    121         # Issue 3301
    122         mod = self.module
    123         self.assertRaises(ValueError, mod.bisect_left, [1, 2, 3], 5, -1, 3)
    124         self.assertRaises(ValueError, mod.bisect_right, [1, 2, 3], 5, -1, 3)
    125         self.assertRaises(ValueError, mod.insort_left, [1, 2, 3], 5, -1, 3)
    126         self.assertRaises(ValueError, mod.insort_right, [1, 2, 3], 5, -1, 3)
    127 
    128     def test_large_range(self):
    129         # Issue 13496
    130         mod = self.module
    131         n = sys.maxsize
    132         data = range(n-1)
    133         self.assertEqual(mod.bisect_left(data, n-3), n-3)
    134         self.assertEqual(mod.bisect_right(data, n-3), n-2)
    135         self.assertEqual(mod.bisect_left(data, n-3, n-10, n), n-3)
    136         self.assertEqual(mod.bisect_right(data, n-3, n-10, n), n-2)
    137 
    138     def test_large_pyrange(self):
    139         # Same as above, but without C-imposed limits on range() parameters
    140         mod = self.module
    141         n = sys.maxsize
    142         data = Range(0, n-1)
    143         self.assertEqual(mod.bisect_left(data, n-3), n-3)
    144         self.assertEqual(mod.bisect_right(data, n-3), n-2)
    145         self.assertEqual(mod.bisect_left(data, n-3, n-10, n), n-3)
    146         self.assertEqual(mod.bisect_right(data, n-3, n-10, n), n-2)
    147         x = n - 100
    148         mod.insort_left(data, x, x - 50, x + 50)
    149         self.assertEqual(data.last_insert, (x, x))
    150         x = n - 200
    151         mod.insort_right(data, x, x - 50, x + 50)
    152         self.assertEqual(data.last_insert, (x + 1, x))
    153 
    154     def test_random(self, n=25):
    155         from random import randrange
    156         for i in range(n):
    157             data = [randrange(0, n, 2) for j in range(i)]
    158             data.sort()
    159             elem = randrange(-1, n+1)
    160             ip = self.module.bisect_left(data, elem)
    161             if ip < len(data):
    162                 self.assertTrue(elem <= data[ip])
    163             if ip > 0:
    164                 self.assertTrue(data[ip-1] < elem)
    165             ip = self.module.bisect_right(data, elem)
    166             if ip < len(data):
    167                 self.assertTrue(elem < data[ip])
    168             if ip > 0:
    169                 self.assertTrue(data[ip-1] <= elem)
    170 
    171     def test_optionalSlicing(self):
    172         for func, data, elem, expected in self.precomputedCases:
    173             for lo in range(4):
    174                 lo = min(len(data), lo)
    175                 for hi in range(3,8):
    176                     hi = min(len(data), hi)
    177                     ip = func(data, elem, lo, hi)
    178                     self.assertTrue(lo <= ip <= hi)
    179                     if func is self.module.bisect_left and ip < hi:
    180                         self.assertTrue(elem <= data[ip])
    181                     if func is self.module.bisect_left and ip > lo:
    182                         self.assertTrue(data[ip-1] < elem)
    183                     if func is self.module.bisect_right and ip < hi:
    184                         self.assertTrue(elem < data[ip])
    185                     if func is self.module.bisect_right and ip > lo:
    186                         self.assertTrue(data[ip-1] <= elem)
    187                     self.assertEqual(ip, max(lo, min(hi, expected)))
    188 
    189     def test_backcompatibility(self):
    190         self.assertEqual(self.module.bisect, self.module.bisect_right)
    191 
    192     def test_keyword_args(self):
    193         data = [10, 20, 30, 40, 50]
    194         self.assertEqual(self.module.bisect_left(a=data, x=25, lo=1, hi=3), 2)
    195         self.assertEqual(self.module.bisect_right(a=data, x=25, lo=1, hi=3), 2)
    196         self.assertEqual(self.module.bisect(a=data, x=25, lo=1, hi=3), 2)
    197         self.module.insort_left(a=data, x=25, lo=1, hi=3)
    198         self.module.insort_right(a=data, x=25, lo=1, hi=3)
    199         self.module.insort(a=data, x=25, lo=1, hi=3)
    200         self.assertEqual(data, [10, 20, 25, 25, 25, 30, 40, 50])
    201 
    202 class TestBisectPython(TestBisect, unittest.TestCase):
    203     module = py_bisect
    204 
    205 class TestBisectC(TestBisect, unittest.TestCase):
    206     module = c_bisect
    207 
    208 #==============================================================================
    209 
    210 class TestInsort:
    211     def test_vsBuiltinSort(self, n=500):
    212         from random import choice
    213         for insorted in (list(), UserList()):
    214             for i in range(n):
    215                 digit = choice("0123456789")
    216                 if digit in "02468":
    217                     f = self.module.insort_left
    218                 else:
    219                     f = self.module.insort_right
    220                 f(insorted, digit)
    221             self.assertEqual(sorted(insorted), insorted)
    222 
    223     def test_backcompatibility(self):
    224         self.assertEqual(self.module.insort, self.module.insort_right)
    225 
    226     def test_listDerived(self):
    227         class List(list):
    228             data = []
    229             def insert(self, index, item):
    230                 self.data.insert(index, item)
    231 
    232         lst = List()
    233         self.module.insort_left(lst, 10)
    234         self.module.insort_right(lst, 5)
    235         self.assertEqual([5, 10], lst.data)
    236 
    237 class TestInsortPython(TestInsort, unittest.TestCase):
    238     module = py_bisect
    239 
    240 class TestInsortC(TestInsort, unittest.TestCase):
    241     module = c_bisect
    242 
    243 #==============================================================================
    244 
    245 class LenOnly:
    246     "Dummy sequence class defining __len__ but not __getitem__."
    247     def __len__(self):
    248         return 10
    249 
    250 class GetOnly:
    251     "Dummy sequence class defining __getitem__ but not __len__."
    252     def __getitem__(self, ndx):
    253         return 10
    254 
    255 class CmpErr:
    256     "Dummy element that always raises an error during comparison"
    257     def __lt__(self, other):
    258         raise ZeroDivisionError
    259     __gt__ = __lt__
    260     __le__ = __lt__
    261     __ge__ = __lt__
    262     __eq__ = __lt__
    263     __ne__ = __lt__
    264 
    265 class TestErrorHandling:
    266     def test_non_sequence(self):
    267         for f in (self.module.bisect_left, self.module.bisect_right,
    268                   self.module.insort_left, self.module.insort_right):
    269             self.assertRaises(TypeError, f, 10, 10)
    270 
    271     def test_len_only(self):
    272         for f in (self.module.bisect_left, self.module.bisect_right,
    273                   self.module.insort_left, self.module.insort_right):
    274             self.assertRaises(TypeError, f, LenOnly(), 10)
    275 
    276     def test_get_only(self):
    277         for f in (self.module.bisect_left, self.module.bisect_right,
    278                   self.module.insort_left, self.module.insort_right):
    279             self.assertRaises(TypeError, f, GetOnly(), 10)
    280 
    281     def test_cmp_err(self):
    282         seq = [CmpErr(), CmpErr(), CmpErr()]
    283         for f in (self.module.bisect_left, self.module.bisect_right,
    284                   self.module.insort_left, self.module.insort_right):
    285             self.assertRaises(ZeroDivisionError, f, seq, 10)
    286 
    287     def test_arg_parsing(self):
    288         for f in (self.module.bisect_left, self.module.bisect_right,
    289                   self.module.insort_left, self.module.insort_right):
    290             self.assertRaises(TypeError, f, 10)
    291 
    292 class TestErrorHandlingPython(TestErrorHandling, unittest.TestCase):
    293     module = py_bisect
    294 
    295 class TestErrorHandlingC(TestErrorHandling, unittest.TestCase):
    296     module = c_bisect
    297 
    298 #==============================================================================
    299 
    300 class TestDocExample:
    301     def test_grades(self):
    302         def grade(score, breakpoints=[60, 70, 80, 90], grades='FDCBA'):
    303             i = self.module.bisect(breakpoints, score)
    304             return grades[i]
    305 
    306         result = [grade(score) for score in [33, 99, 77, 70, 89, 90, 100]]
    307         self.assertEqual(result, ['F', 'A', 'C', 'C', 'B', 'A', 'A'])
    308 
    309     def test_colors(self):
    310         data = [('red', 5), ('blue', 1), ('yellow', 8), ('black', 0)]
    311         data.sort(key=lambda r: r[1])
    312         keys = [r[1] for r in data]
    313         bisect_left = self.module.bisect_left
    314         self.assertEqual(data[bisect_left(keys, 0)], ('black', 0))
    315         self.assertEqual(data[bisect_left(keys, 1)], ('blue', 1))
    316         self.assertEqual(data[bisect_left(keys, 5)], ('red', 5))
    317         self.assertEqual(data[bisect_left(keys, 8)], ('yellow', 8))
    318 
    319 class TestDocExamplePython(TestDocExample, unittest.TestCase):
    320     module = py_bisect
    321 
    322 class TestDocExampleC(TestDocExample, unittest.TestCase):
    323     module = c_bisect
    324 
    325 #------------------------------------------------------------------------------
    326 
    327 if __name__ == "__main__":
    328     unittest.main()
    329