1 import sys
2 import unittest
3 from test.support import import_helper
4 from collections import UserList
5
6
7 py_bisect = import_helper.import_fresh_module('bisect', blocked=['_bisect'])
8 c_bisect = import_helper.import_fresh_module('bisect', fresh=['_bisect'])
9
10 class ESC[4;38;5;81mRange(ESC[4;38;5;149mobject):
11 """A trivial range()-like object that has an insert() method."""
12 def __init__(self, start, stop):
13 self.start = start
14 self.stop = stop
15 self.last_insert = None
16
17 def __len__(self):
18 return self.stop - self.start
19
20 def __getitem__(self, idx):
21 n = self.stop - self.start
22 if idx < 0:
23 idx += n
24 if idx >= n:
25 raise IndexError(idx)
26 return self.start + idx
27
28 def insert(self, idx, item):
29 self.last_insert = idx, item
30
31
32 class ESC[4;38;5;81mTestBisect:
33 def setUp(self):
34 self.precomputedCases = [
35 (self.module.bisect_right, [], 1, 0),
36 (self.module.bisect_right, [1], 0, 0),
37 (self.module.bisect_right, [1], 1, 1),
38 (self.module.bisect_right, [1], 2, 1),
39 (self.module.bisect_right, [1, 1], 0, 0),
40 (self.module.bisect_right, [1, 1], 1, 2),
41 (self.module.bisect_right, [1, 1], 2, 2),
42 (self.module.bisect_right, [1, 1, 1], 0, 0),
43 (self.module.bisect_right, [1, 1, 1], 1, 3),
44 (self.module.bisect_right, [1, 1, 1], 2, 3),
45 (self.module.bisect_right, [1, 1, 1, 1], 0, 0),
46 (self.module.bisect_right, [1, 1, 1, 1], 1, 4),
47 (self.module.bisect_right, [1, 1, 1, 1], 2, 4),
48 (self.module.bisect_right, [1, 2], 0, 0),
49 (self.module.bisect_right, [1, 2], 1, 1),
50 (self.module.bisect_right, [1, 2], 1.5, 1),
51 (self.module.bisect_right, [1, 2], 2, 2),
52 (self.module.bisect_right, [1, 2], 3, 2),
53 (self.module.bisect_right, [1, 1, 2, 2], 0, 0),
54 (self.module.bisect_right, [1, 1, 2, 2], 1, 2),
55 (self.module.bisect_right, [1, 1, 2, 2], 1.5, 2),
56 (self.module.bisect_right, [1, 1, 2, 2], 2, 4),
57 (self.module.bisect_right, [1, 1, 2, 2], 3, 4),
58 (self.module.bisect_right, [1, 2, 3], 0, 0),
59 (self.module.bisect_right, [1, 2, 3], 1, 1),
60 (self.module.bisect_right, [1, 2, 3], 1.5, 1),
61 (self.module.bisect_right, [1, 2, 3], 2, 2),
62 (self.module.bisect_right, [1, 2, 3], 2.5, 2),
63 (self.module.bisect_right, [1, 2, 3], 3, 3),
64 (self.module.bisect_right, [1, 2, 3], 4, 3),
65 (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 0, 0),
66 (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 1, 1),
67 (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 1.5, 1),
68 (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 2, 3),
69 (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 2.5, 3),
70 (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 3, 6),
71 (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 3.5, 6),
72 (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 4, 10),
73 (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 5, 10),
74
75 (self.module.bisect_left, [], 1, 0),
76 (self.module.bisect_left, [1], 0, 0),
77 (self.module.bisect_left, [1], 1, 0),
78 (self.module.bisect_left, [1], 2, 1),
79 (self.module.bisect_left, [1, 1], 0, 0),
80 (self.module.bisect_left, [1, 1], 1, 0),
81 (self.module.bisect_left, [1, 1], 2, 2),
82 (self.module.bisect_left, [1, 1, 1], 0, 0),
83 (self.module.bisect_left, [1, 1, 1], 1, 0),
84 (self.module.bisect_left, [1, 1, 1], 2, 3),
85 (self.module.bisect_left, [1, 1, 1, 1], 0, 0),
86 (self.module.bisect_left, [1, 1, 1, 1], 1, 0),
87 (self.module.bisect_left, [1, 1, 1, 1], 2, 4),
88 (self.module.bisect_left, [1, 2], 0, 0),
89 (self.module.bisect_left, [1, 2], 1, 0),
90 (self.module.bisect_left, [1, 2], 1.5, 1),
91 (self.module.bisect_left, [1, 2], 2, 1),
92 (self.module.bisect_left, [1, 2], 3, 2),
93 (self.module.bisect_left, [1, 1, 2, 2], 0, 0),
94 (self.module.bisect_left, [1, 1, 2, 2], 1, 0),
95 (self.module.bisect_left, [1, 1, 2, 2], 1.5, 2),
96 (self.module.bisect_left, [1, 1, 2, 2], 2, 2),
97 (self.module.bisect_left, [1, 1, 2, 2], 3, 4),
98 (self.module.bisect_left, [1, 2, 3], 0, 0),
99 (self.module.bisect_left, [1, 2, 3], 1, 0),
100 (self.module.bisect_left, [1, 2, 3], 1.5, 1),
101 (self.module.bisect_left, [1, 2, 3], 2, 1),
102 (self.module.bisect_left, [1, 2, 3], 2.5, 2),
103 (self.module.bisect_left, [1, 2, 3], 3, 2),
104 (self.module.bisect_left, [1, 2, 3], 4, 3),
105 (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 0, 0),
106 (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 1, 0),
107 (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 1.5, 1),
108 (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 2, 1),
109 (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 2.5, 3),
110 (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 3, 3),
111 (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 3.5, 6),
112 (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 4, 6),
113 (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 5, 10)
114 ]
115
116 def test_precomputed(self):
117 for func, data, elem, expected in self.precomputedCases:
118 self.assertEqual(func(data, elem), expected)
119 self.assertEqual(func(UserList(data), elem), expected)
120
121 def test_negative_lo(self):
122 # Issue 3301
123 mod = self.module
124 self.assertRaises(ValueError, mod.bisect_left, [1, 2, 3], 5, -1, 3)
125 self.assertRaises(ValueError, mod.bisect_right, [1, 2, 3], 5, -1, 3)
126 self.assertRaises(ValueError, mod.insort_left, [1, 2, 3], 5, -1, 3)
127 self.assertRaises(ValueError, mod.insort_right, [1, 2, 3], 5, -1, 3)
128
129 def test_large_range(self):
130 # Issue 13496
131 mod = self.module
132 n = sys.maxsize
133 data = range(n-1)
134 self.assertEqual(mod.bisect_left(data, n-3), n-3)
135 self.assertEqual(mod.bisect_right(data, n-3), n-2)
136 self.assertEqual(mod.bisect_left(data, n-3, n-10, n), n-3)
137 self.assertEqual(mod.bisect_right(data, n-3, n-10, n), n-2)
138
139 def test_large_pyrange(self):
140 # Same as above, but without C-imposed limits on range() parameters
141 mod = self.module
142 n = sys.maxsize
143 data = Range(0, n-1)
144 self.assertEqual(mod.bisect_left(data, n-3), n-3)
145 self.assertEqual(mod.bisect_right(data, n-3), n-2)
146 self.assertEqual(mod.bisect_left(data, n-3, n-10, n), n-3)
147 self.assertEqual(mod.bisect_right(data, n-3, n-10, n), n-2)
148 x = n - 100
149 mod.insort_left(data, x, x - 50, x + 50)
150 self.assertEqual(data.last_insert, (x, x))
151 x = n - 200
152 mod.insort_right(data, x, x - 50, x + 50)
153 self.assertEqual(data.last_insert, (x + 1, x))
154
155 def test_random(self, n=25):
156 from random import randrange
157 for i in range(n):
158 data = [randrange(0, n, 2) for j in range(i)]
159 data.sort()
160 elem = randrange(-1, n+1)
161 ip = self.module.bisect_left(data, elem)
162 if ip < len(data):
163 self.assertTrue(elem <= data[ip])
164 if ip > 0:
165 self.assertTrue(data[ip-1] < elem)
166 ip = self.module.bisect_right(data, elem)
167 if ip < len(data):
168 self.assertTrue(elem < data[ip])
169 if ip > 0:
170 self.assertTrue(data[ip-1] <= elem)
171
172 def test_optionalSlicing(self):
173 for func, data, elem, expected in self.precomputedCases:
174 for lo in range(4):
175 lo = min(len(data), lo)
176 for hi in range(3,8):
177 hi = min(len(data), hi)
178 ip = func(data, elem, lo, hi)
179 self.assertTrue(lo <= ip <= hi)
180 if func is self.module.bisect_left and ip < hi:
181 self.assertTrue(elem <= data[ip])
182 if func is self.module.bisect_left and ip > lo:
183 self.assertTrue(data[ip-1] < elem)
184 if func is self.module.bisect_right and ip < hi:
185 self.assertTrue(elem < data[ip])
186 if func is self.module.bisect_right and ip > lo:
187 self.assertTrue(data[ip-1] <= elem)
188 self.assertEqual(ip, max(lo, min(hi, expected)))
189
190 def test_backcompatibility(self):
191 self.assertEqual(self.module.bisect, self.module.bisect_right)
192
193 def test_keyword_args(self):
194 data = [10, 20, 30, 40, 50]
195 self.assertEqual(self.module.bisect_left(a=data, x=25, lo=1, hi=3), 2)
196 self.assertEqual(self.module.bisect_right(a=data, x=25, lo=1, hi=3), 2)
197 self.assertEqual(self.module.bisect(a=data, x=25, lo=1, hi=3), 2)
198 self.module.insort_left(a=data, x=25, lo=1, hi=3)
199 self.module.insort_right(a=data, x=25, lo=1, hi=3)
200 self.module.insort(a=data, x=25, lo=1, hi=3)
201 self.assertEqual(data, [10, 20, 25, 25, 25, 30, 40, 50])
202
203 def test_lookups_with_key_function(self):
204 mod = self.module
205
206 # Invariant: Index with a keyfunc on an array
207 # should match the index on an array where
208 # key function has already been applied.
209
210 keyfunc = abs
211 arr = sorted([2, -4, 6, 8, -10], key=keyfunc)
212 precomputed_arr = list(map(keyfunc, arr))
213 for x in precomputed_arr:
214 self.assertEqual(
215 mod.bisect_left(arr, x, key=keyfunc),
216 mod.bisect_left(precomputed_arr, x)
217 )
218 self.assertEqual(
219 mod.bisect_right(arr, x, key=keyfunc),
220 mod.bisect_right(precomputed_arr, x)
221 )
222
223 keyfunc = str.casefold
224 arr = sorted('aBcDeEfgHhiIiij', key=keyfunc)
225 precomputed_arr = list(map(keyfunc, arr))
226 for x in precomputed_arr:
227 self.assertEqual(
228 mod.bisect_left(arr, x, key=keyfunc),
229 mod.bisect_left(precomputed_arr, x)
230 )
231 self.assertEqual(
232 mod.bisect_right(arr, x, key=keyfunc),
233 mod.bisect_right(precomputed_arr, x)
234 )
235
236 def test_insort(self):
237 from random import shuffle
238 mod = self.module
239
240 # Invariant: As random elements are inserted in
241 # a target list, the targetlist remains sorted.
242 keyfunc = abs
243 data = list(range(-10, 11)) + list(range(-20, 20, 2))
244 shuffle(data)
245 target = []
246 for x in data:
247 mod.insort_left(target, x, key=keyfunc)
248 self.assertEqual(
249 sorted(target, key=keyfunc),
250 target
251 )
252 target = []
253 for x in data:
254 mod.insort_right(target, x, key=keyfunc)
255 self.assertEqual(
256 sorted(target, key=keyfunc),
257 target
258 )
259
260 def test_insort_keynotNone(self):
261 x = []
262 y = {"a": 2, "b": 1}
263 for f in (self.module.insort_left, self.module.insort_right):
264 self.assertRaises(TypeError, f, x, y, key = "b")
265
266 def test_lt_returns_non_bool(self):
267 class ESC[4;38;5;81mA:
268 def __init__(self, val):
269 self.val = val
270 def __lt__(self, other):
271 return "nonempty" if self.val < other.val else ""
272
273 data = [A(i) for i in range(100)]
274 i1 = self.module.bisect_left(data, A(33))
275 i2 = self.module.bisect_right(data, A(33))
276 self.assertEqual(i1, 33)
277 self.assertEqual(i2, 34)
278
279 def test_lt_returns_notimplemented(self):
280 class ESC[4;38;5;81mA:
281 def __init__(self, val):
282 self.val = val
283 def __lt__(self, other):
284 return NotImplemented
285 def __gt__(self, other):
286 return self.val > other.val
287
288 data = [A(i) for i in range(100)]
289 i1 = self.module.bisect_left(data, A(40))
290 i2 = self.module.bisect_right(data, A(40))
291 self.assertEqual(i1, 40)
292 self.assertEqual(i2, 41)
293
294 class ESC[4;38;5;81mTestBisectPython(ESC[4;38;5;149mTestBisect, ESC[4;38;5;149munittestESC[4;38;5;149m.ESC[4;38;5;149mTestCase):
295 module = py_bisect
296
297 class ESC[4;38;5;81mTestBisectC(ESC[4;38;5;149mTestBisect, ESC[4;38;5;149munittestESC[4;38;5;149m.ESC[4;38;5;149mTestCase):
298 module = c_bisect
299
300 #==============================================================================
301
302 class ESC[4;38;5;81mTestInsort:
303 def test_vsBuiltinSort(self, n=500):
304 from random import choice
305 for insorted in (list(), UserList()):
306 for i in range(n):
307 digit = choice("0123456789")
308 if digit in "02468":
309 f = self.module.insort_left
310 else:
311 f = self.module.insort_right
312 f(insorted, digit)
313 self.assertEqual(sorted(insorted), insorted)
314
315 def test_backcompatibility(self):
316 self.assertEqual(self.module.insort, self.module.insort_right)
317
318 def test_listDerived(self):
319 class ESC[4;38;5;81mList(ESC[4;38;5;149mlist):
320 data = []
321 def insert(self, index, item):
322 self.data.insert(index, item)
323
324 lst = List()
325 self.module.insort_left(lst, 10)
326 self.module.insort_right(lst, 5)
327 self.assertEqual([5, 10], lst.data)
328
329 class ESC[4;38;5;81mTestInsortPython(ESC[4;38;5;149mTestInsort, ESC[4;38;5;149munittestESC[4;38;5;149m.ESC[4;38;5;149mTestCase):
330 module = py_bisect
331
332 class ESC[4;38;5;81mTestInsortC(ESC[4;38;5;149mTestInsort, ESC[4;38;5;149munittestESC[4;38;5;149m.ESC[4;38;5;149mTestCase):
333 module = c_bisect
334
335 #==============================================================================
336
337 class ESC[4;38;5;81mLenOnly:
338 "Dummy sequence class defining __len__ but not __getitem__."
339 def __len__(self):
340 return 10
341
342 class ESC[4;38;5;81mGetOnly:
343 "Dummy sequence class defining __getitem__ but not __len__."
344 def __getitem__(self, ndx):
345 return 10
346
347 class ESC[4;38;5;81mCmpErr:
348 "Dummy element that always raises an error during comparison"
349 def __lt__(self, other):
350 raise ZeroDivisionError
351 __gt__ = __lt__
352 __le__ = __lt__
353 __ge__ = __lt__
354 __eq__ = __lt__
355 __ne__ = __lt__
356
357 class ESC[4;38;5;81mTestErrorHandling:
358 def test_non_sequence(self):
359 for f in (self.module.bisect_left, self.module.bisect_right,
360 self.module.insort_left, self.module.insort_right):
361 self.assertRaises(TypeError, f, 10, 10)
362
363 def test_len_only(self):
364 for f in (self.module.bisect_left, self.module.bisect_right,
365 self.module.insort_left, self.module.insort_right):
366 self.assertRaises(TypeError, f, LenOnly(), 10)
367
368 def test_get_only(self):
369 for f in (self.module.bisect_left, self.module.bisect_right,
370 self.module.insort_left, self.module.insort_right):
371 self.assertRaises(TypeError, f, GetOnly(), 10)
372
373 def test_cmp_err(self):
374 seq = [CmpErr(), CmpErr(), CmpErr()]
375 for f in (self.module.bisect_left, self.module.bisect_right,
376 self.module.insort_left, self.module.insort_right):
377 self.assertRaises(ZeroDivisionError, f, seq, 10)
378
379 def test_arg_parsing(self):
380 for f in (self.module.bisect_left, self.module.bisect_right,
381 self.module.insort_left, self.module.insort_right):
382 self.assertRaises(TypeError, f, 10)
383
384 class ESC[4;38;5;81mTestErrorHandlingPython(ESC[4;38;5;149mTestErrorHandling, ESC[4;38;5;149munittestESC[4;38;5;149m.ESC[4;38;5;149mTestCase):
385 module = py_bisect
386
387 class ESC[4;38;5;81mTestErrorHandlingC(ESC[4;38;5;149mTestErrorHandling, ESC[4;38;5;149munittestESC[4;38;5;149m.ESC[4;38;5;149mTestCase):
388 module = c_bisect
389
390 #==============================================================================
391
392 class ESC[4;38;5;81mTestDocExample:
393 def test_grades(self):
394 def grade(score, breakpoints=[60, 70, 80, 90], grades='FDCBA'):
395 i = self.module.bisect(breakpoints, score)
396 return grades[i]
397
398 result = [grade(score) for score in [33, 99, 77, 70, 89, 90, 100]]
399 self.assertEqual(result, ['F', 'A', 'C', 'C', 'B', 'A', 'A'])
400
401 def test_colors(self):
402 data = [('red', 5), ('blue', 1), ('yellow', 8), ('black', 0)]
403 data.sort(key=lambda r: r[1])
404 keys = [r[1] for r in data]
405 bisect_left = self.module.bisect_left
406 self.assertEqual(data[bisect_left(keys, 0)], ('black', 0))
407 self.assertEqual(data[bisect_left(keys, 1)], ('blue', 1))
408 self.assertEqual(data[bisect_left(keys, 5)], ('red', 5))
409 self.assertEqual(data[bisect_left(keys, 8)], ('yellow', 8))
410
411 class ESC[4;38;5;81mTestDocExamplePython(ESC[4;38;5;149mTestDocExample, ESC[4;38;5;149munittestESC[4;38;5;149m.ESC[4;38;5;149mTestCase):
412 module = py_bisect
413
414 class ESC[4;38;5;81mTestDocExampleC(ESC[4;38;5;149mTestDocExample, ESC[4;38;5;149munittestESC[4;38;5;149m.ESC[4;38;5;149mTestCase):
415 module = c_bisect
416
417 #------------------------------------------------------------------------------
418
419 if __name__ == "__main__":
420 unittest.main()