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 Range(object): 27 """A trivial xrange()-like object without any integer width limitations.""" 28 def __init__(self, start, stop): 29 self.start = start 30 self.stop = stop 31 self.last_insert = None 32 33 def __len__(self): 34 return self.stop - self.start 35 36 def __getitem__(self, idx): 37 n = self.stop - self.start 38 if idx < 0: 39 idx += n 40 if idx >= n: 41 raise IndexError(idx) 42 return self.start + idx 43 44 def insert(self, idx, item): 45 self.last_insert = idx, item 46 47 48 class TestBisect(unittest.TestCase): 49 module = None 50 51 def setUp(self): 52 self.precomputedCases = [ 53 (self.module.bisect_right, [], 1, 0), 54 (self.module.bisect_right, [1], 0, 0), 55 (self.module.bisect_right, [1], 1, 1), 56 (self.module.bisect_right, [1], 2, 1), 57 (self.module.bisect_right, [1, 1], 0, 0), 58 (self.module.bisect_right, [1, 1], 1, 2), 59 (self.module.bisect_right, [1, 1], 2, 2), 60 (self.module.bisect_right, [1, 1, 1], 0, 0), 61 (self.module.bisect_right, [1, 1, 1], 1, 3), 62 (self.module.bisect_right, [1, 1, 1], 2, 3), 63 (self.module.bisect_right, [1, 1, 1, 1], 0, 0), 64 (self.module.bisect_right, [1, 1, 1, 1], 1, 4), 65 (self.module.bisect_right, [1, 1, 1, 1], 2, 4), 66 (self.module.bisect_right, [1, 2], 0, 0), 67 (self.module.bisect_right, [1, 2], 1, 1), 68 (self.module.bisect_right, [1, 2], 1.5, 1), 69 (self.module.bisect_right, [1, 2], 2, 2), 70 (self.module.bisect_right, [1, 2], 3, 2), 71 (self.module.bisect_right, [1, 1, 2, 2], 0, 0), 72 (self.module.bisect_right, [1, 1, 2, 2], 1, 2), 73 (self.module.bisect_right, [1, 1, 2, 2], 1.5, 2), 74 (self.module.bisect_right, [1, 1, 2, 2], 2, 4), 75 (self.module.bisect_right, [1, 1, 2, 2], 3, 4), 76 (self.module.bisect_right, [1, 2, 3], 0, 0), 77 (self.module.bisect_right, [1, 2, 3], 1, 1), 78 (self.module.bisect_right, [1, 2, 3], 1.5, 1), 79 (self.module.bisect_right, [1, 2, 3], 2, 2), 80 (self.module.bisect_right, [1, 2, 3], 2.5, 2), 81 (self.module.bisect_right, [1, 2, 3], 3, 3), 82 (self.module.bisect_right, [1, 2, 3], 4, 3), 83 (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 0, 0), 84 (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 1, 1), 85 (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 1.5, 1), 86 (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 2, 3), 87 (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 2.5, 3), 88 (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 3, 6), 89 (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 3.5, 6), 90 (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 4, 10), 91 (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 5, 10), 92 93 (self.module.bisect_left, [], 1, 0), 94 (self.module.bisect_left, [1], 0, 0), 95 (self.module.bisect_left, [1], 1, 0), 96 (self.module.bisect_left, [1], 2, 1), 97 (self.module.bisect_left, [1, 1], 0, 0), 98 (self.module.bisect_left, [1, 1], 1, 0), 99 (self.module.bisect_left, [1, 1], 2, 2), 100 (self.module.bisect_left, [1, 1, 1], 0, 0), 101 (self.module.bisect_left, [1, 1, 1], 1, 0), 102 (self.module.bisect_left, [1, 1, 1], 2, 3), 103 (self.module.bisect_left, [1, 1, 1, 1], 0, 0), 104 (self.module.bisect_left, [1, 1, 1, 1], 1, 0), 105 (self.module.bisect_left, [1, 1, 1, 1], 2, 4), 106 (self.module.bisect_left, [1, 2], 0, 0), 107 (self.module.bisect_left, [1, 2], 1, 0), 108 (self.module.bisect_left, [1, 2], 1.5, 1), 109 (self.module.bisect_left, [1, 2], 2, 1), 110 (self.module.bisect_left, [1, 2], 3, 2), 111 (self.module.bisect_left, [1, 1, 2, 2], 0, 0), 112 (self.module.bisect_left, [1, 1, 2, 2], 1, 0), 113 (self.module.bisect_left, [1, 1, 2, 2], 1.5, 2), 114 (self.module.bisect_left, [1, 1, 2, 2], 2, 2), 115 (self.module.bisect_left, [1, 1, 2, 2], 3, 4), 116 (self.module.bisect_left, [1, 2, 3], 0, 0), 117 (self.module.bisect_left, [1, 2, 3], 1, 0), 118 (self.module.bisect_left, [1, 2, 3], 1.5, 1), 119 (self.module.bisect_left, [1, 2, 3], 2, 1), 120 (self.module.bisect_left, [1, 2, 3], 2.5, 2), 121 (self.module.bisect_left, [1, 2, 3], 3, 2), 122 (self.module.bisect_left, [1, 2, 3], 4, 3), 123 (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 0, 0), 124 (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 1, 0), 125 (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 1.5, 1), 126 (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 2, 1), 127 (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 2.5, 3), 128 (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 3, 3), 129 (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 3.5, 6), 130 (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 4, 6), 131 (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 5, 10) 132 ] 133 134 def test_precomputed(self): 135 for func, data, elem, expected in self.precomputedCases: 136 self.assertEqual(func(data, elem), expected) 137 self.assertEqual(func(UserList(data), elem), expected) 138 139 def test_negative_lo(self): 140 # Issue 3301 141 mod = self.module 142 self.assertRaises(ValueError, mod.bisect_left, [1, 2, 3], 5, -1, 3), 143 self.assertRaises(ValueError, mod.bisect_right, [1, 2, 3], 5, -1, 3), 144 self.assertRaises(ValueError, mod.insort_left, [1, 2, 3], 5, -1, 3), 145 self.assertRaises(ValueError, mod.insort_right, [1, 2, 3], 5, -1, 3), 146 147 def test_large_range(self): 148 # Issue 13496 149 mod = self.module 150 n = sys.maxsize 151 try: 152 data = xrange(n-1) 153 except OverflowError: 154 self.skipTest("can't create a xrange() object of size `sys.maxsize`") 155 self.assertEqual(mod.bisect_left(data, n-3), n-3) 156 self.assertEqual(mod.bisect_right(data, n-3), n-2) 157 self.assertEqual(mod.bisect_left(data, n-3, n-10, n), n-3) 158 self.assertEqual(mod.bisect_right(data, n-3, n-10, n), n-2) 159 160 def test_large_pyrange(self): 161 # Same as above, but without C-imposed limits on range() parameters 162 mod = self.module 163 n = sys.maxsize 164 data = Range(0, n-1) 165 self.assertEqual(mod.bisect_left(data, n-3), n-3) 166 self.assertEqual(mod.bisect_right(data, n-3), n-2) 167 self.assertEqual(mod.bisect_left(data, n-3, n-10, n), n-3) 168 self.assertEqual(mod.bisect_right(data, n-3, n-10, n), n-2) 169 x = n - 100 170 mod.insort_left(data, x, x - 50, x + 50) 171 self.assertEqual(data.last_insert, (x, x)) 172 x = n - 200 173 mod.insort_right(data, x, x - 50, x + 50) 174 self.assertEqual(data.last_insert, (x + 1, x)) 175 176 def test_random(self, n=25): 177 from random import randrange 178 for i in xrange(n): 179 data = [randrange(0, n, 2) for j in xrange(i)] 180 data.sort() 181 elem = randrange(-1, n+1) 182 ip = self.module.bisect_left(data, elem) 183 if ip < len(data): 184 self.assertTrue(elem <= data[ip]) 185 if ip > 0: 186 self.assertTrue(data[ip-1] < elem) 187 ip = self.module.bisect_right(data, elem) 188 if ip < len(data): 189 self.assertTrue(elem < data[ip]) 190 if ip > 0: 191 self.assertTrue(data[ip-1] <= elem) 192 193 def test_optionalSlicing(self): 194 for func, data, elem, expected in self.precomputedCases: 195 for lo in xrange(4): 196 lo = min(len(data), lo) 197 for hi in xrange(3,8): 198 hi = min(len(data), hi) 199 ip = func(data, elem, lo, hi) 200 self.assertTrue(lo <= ip <= hi) 201 if func is self.module.bisect_left and ip < hi: 202 self.assertTrue(elem <= data[ip]) 203 if func is self.module.bisect_left and ip > lo: 204 self.assertTrue(data[ip-1] < elem) 205 if func is self.module.bisect_right and ip < hi: 206 self.assertTrue(elem < data[ip]) 207 if func is self.module.bisect_right and ip > lo: 208 self.assertTrue(data[ip-1] <= elem) 209 self.assertEqual(ip, max(lo, min(hi, expected))) 210 211 def test_backcompatibility(self): 212 self.assertEqual(self.module.bisect, self.module.bisect_right) 213 214 def test_keyword_args(self): 215 data = [10, 20, 30, 40, 50] 216 self.assertEqual(self.module.bisect_left(a=data, x=25, lo=1, hi=3), 2) 217 self.assertEqual(self.module.bisect_right(a=data, x=25, lo=1, hi=3), 2) 218 self.assertEqual(self.module.bisect(a=data, x=25, lo=1, hi=3), 2) 219 self.module.insort_left(a=data, x=25, lo=1, hi=3) 220 self.module.insort_right(a=data, x=25, lo=1, hi=3) 221 self.module.insort(a=data, x=25, lo=1, hi=3) 222 self.assertEqual(data, [10, 20, 25, 25, 25, 30, 40, 50]) 223 224 class TestBisectPython(TestBisect): 225 module = py_bisect 226 227 class TestBisectC(TestBisect): 228 module = c_bisect 229 230 #============================================================================== 231 232 class TestInsort(unittest.TestCase): 233 module = None 234 235 def test_vsBuiltinSort(self, n=500): 236 from random import choice 237 for insorted in (list(), UserList()): 238 for i in xrange(n): 239 digit = choice("0123456789") 240 if digit in "02468": 241 f = self.module.insort_left 242 else: 243 f = self.module.insort_right 244 f(insorted, digit) 245 self.assertEqual(sorted(insorted), insorted) 246 247 def test_backcompatibility(self): 248 self.assertEqual(self.module.insort, self.module.insort_right) 249 250 def test_listDerived(self): 251 class List(list): 252 data = [] 253 def insert(self, index, item): 254 self.data.insert(index, item) 255 256 lst = List() 257 self.module.insort_left(lst, 10) 258 self.module.insort_right(lst, 5) 259 self.assertEqual([5, 10], lst.data) 260 261 class TestInsortPython(TestInsort): 262 module = py_bisect 263 264 class TestInsortC(TestInsort): 265 module = c_bisect 266 267 #============================================================================== 268 269 270 class LenOnly: 271 "Dummy sequence class defining __len__ but not __getitem__." 272 def __len__(self): 273 return 10 274 275 class GetOnly: 276 "Dummy sequence class defining __getitem__ but not __len__." 277 def __getitem__(self, ndx): 278 return 10 279 280 class CmpErr: 281 "Dummy element that always raises an error during comparison" 282 def __cmp__(self, other): 283 raise ZeroDivisionError 284 285 class TestErrorHandling(unittest.TestCase): 286 module = None 287 288 def test_non_sequence(self): 289 for f in (self.module.bisect_left, self.module.bisect_right, 290 self.module.insort_left, self.module.insort_right): 291 self.assertRaises(TypeError, f, 10, 10) 292 293 def test_len_only(self): 294 for f in (self.module.bisect_left, self.module.bisect_right, 295 self.module.insort_left, self.module.insort_right): 296 self.assertRaises(AttributeError, f, LenOnly(), 10) 297 298 def test_get_only(self): 299 for f in (self.module.bisect_left, self.module.bisect_right, 300 self.module.insort_left, self.module.insort_right): 301 self.assertRaises(AttributeError, f, GetOnly(), 10) 302 303 def test_cmp_err(self): 304 seq = [CmpErr(), CmpErr(), CmpErr()] 305 for f in (self.module.bisect_left, self.module.bisect_right, 306 self.module.insort_left, self.module.insort_right): 307 self.assertRaises(ZeroDivisionError, f, seq, 10) 308 309 def test_arg_parsing(self): 310 for f in (self.module.bisect_left, self.module.bisect_right, 311 self.module.insort_left, self.module.insort_right): 312 self.assertRaises(TypeError, f, 10) 313 314 class TestErrorHandlingPython(TestErrorHandling): 315 module = py_bisect 316 317 class TestErrorHandlingC(TestErrorHandling): 318 module = c_bisect 319 320 #============================================================================== 321 322 libreftest = """ 323 Example from the Library Reference: Doc/library/bisect.rst 324 325 The bisect() function is generally useful for categorizing numeric data. 326 This example uses bisect() to look up a letter grade for an exam total 327 (say) based on a set of ordered numeric breakpoints: 85 and up is an `A', 328 75..84 is a `B', etc. 329 330 >>> grades = "FEDCBA" 331 >>> breakpoints = [30, 44, 66, 75, 85] 332 >>> from bisect import bisect 333 >>> def grade(total): 334 ... return grades[bisect(breakpoints, total)] 335 ... 336 >>> grade(66) 337 'C' 338 >>> map(grade, [33, 99, 77, 44, 12, 88]) 339 ['E', 'A', 'B', 'D', 'F', 'A'] 340 341 """ 342 343 #------------------------------------------------------------------------------ 344 345 __test__ = {'libreftest' : libreftest} 346 347 def test_main(verbose=None): 348 from test import test_bisect 349 350 test_classes = [TestBisectPython, TestBisectC, 351 TestInsortPython, TestInsortC, 352 TestErrorHandlingPython, TestErrorHandlingC] 353 354 test_support.run_unittest(*test_classes) 355 test_support.run_doctest(test_bisect, verbose) 356 357 # verify reference counting 358 if verbose and hasattr(sys, "gettotalrefcount"): 359 import gc 360 counts = [None] * 5 361 for i in xrange(len(counts)): 362 test_support.run_unittest(*test_classes) 363 gc.collect() 364 counts[i] = sys.gettotalrefcount() 365 print counts 366 367 if __name__ == "__main__": 368 test_main(verbose=True) 369
