1import sys 2import unittest 3from test import support 4from collections import UserList 5 6py_bisect = support.import_fresh_module('bisect', blocked=['_bisect']) 7c_bisect = support.import_fresh_module('bisect', fresh=['_bisect']) 8 9class 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 31class 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 202class TestBisectPython(TestBisect, unittest.TestCase): 203 module = py_bisect 204 205class TestBisectC(TestBisect, unittest.TestCase): 206 module = c_bisect 207 208#============================================================================== 209 210class 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 237class TestInsortPython(TestInsort, unittest.TestCase): 238 module = py_bisect 239 240class TestInsortC(TestInsort, unittest.TestCase): 241 module = c_bisect 242 243#============================================================================== 244 245class LenOnly: 246 "Dummy sequence class defining __len__ but not __getitem__." 247 def __len__(self): 248 return 10 249 250class GetOnly: 251 "Dummy sequence class defining __getitem__ but not __len__." 252 def __getitem__(self, ndx): 253 return 10 254 255class 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 265class 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 292class TestErrorHandlingPython(TestErrorHandling, unittest.TestCase): 293 module = py_bisect 294 295class TestErrorHandlingC(TestErrorHandling, unittest.TestCase): 296 module = c_bisect 297 298#============================================================================== 299 300class 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 319class TestDocExamplePython(TestDocExample, unittest.TestCase): 320 module = py_bisect 321 322class TestDocExampleC(TestDocExample, unittest.TestCase): 323 module = c_bisect 324 325#------------------------------------------------------------------------------ 326 327if __name__ == "__main__": 328 unittest.main() 329