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 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):
267 module = py_bisect
268
269 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):
270 module = c_bisect
271
272 #==============================================================================
273
274 class ESC[4;38;5;81mTestInsort:
275 def test_vsBuiltinSort(self, n=500):
276 from random import choice
277 for insorted in (list(), UserList()):
278 for i in range(n):
279 digit = choice("0123456789")
280 if digit in "02468":
281 f = self.module.insort_left
282 else:
283 f = self.module.insort_right
284 f(insorted, digit)
285 self.assertEqual(sorted(insorted), insorted)
286
287 def test_backcompatibility(self):
288 self.assertEqual(self.module.insort, self.module.insort_right)
289
290 def test_listDerived(self):
291 class ESC[4;38;5;81mList(ESC[4;38;5;149mlist):
292 data = []
293 def insert(self, index, item):
294 self.data.insert(index, item)
295
296 lst = List()
297 self.module.insort_left(lst, 10)
298 self.module.insort_right(lst, 5)
299 self.assertEqual([5, 10], lst.data)
300
301 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):
302 module = py_bisect
303
304 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):
305 module = c_bisect
306
307 #==============================================================================
308
309 class ESC[4;38;5;81mLenOnly:
310 "Dummy sequence class defining __len__ but not __getitem__."
311 def __len__(self):
312 return 10
313
314 class ESC[4;38;5;81mGetOnly:
315 "Dummy sequence class defining __getitem__ but not __len__."
316 def __getitem__(self, ndx):
317 return 10
318
319 class ESC[4;38;5;81mCmpErr:
320 "Dummy element that always raises an error during comparison"
321 def __lt__(self, other):
322 raise ZeroDivisionError
323 __gt__ = __lt__
324 __le__ = __lt__
325 __ge__ = __lt__
326 __eq__ = __lt__
327 __ne__ = __lt__
328
329 class ESC[4;38;5;81mTestErrorHandling:
330 def test_non_sequence(self):
331 for f in (self.module.bisect_left, self.module.bisect_right,
332 self.module.insort_left, self.module.insort_right):
333 self.assertRaises(TypeError, f, 10, 10)
334
335 def test_len_only(self):
336 for f in (self.module.bisect_left, self.module.bisect_right,
337 self.module.insort_left, self.module.insort_right):
338 self.assertRaises(TypeError, f, LenOnly(), 10)
339
340 def test_get_only(self):
341 for f in (self.module.bisect_left, self.module.bisect_right,
342 self.module.insort_left, self.module.insort_right):
343 self.assertRaises(TypeError, f, GetOnly(), 10)
344
345 def test_cmp_err(self):
346 seq = [CmpErr(), CmpErr(), CmpErr()]
347 for f in (self.module.bisect_left, self.module.bisect_right,
348 self.module.insort_left, self.module.insort_right):
349 self.assertRaises(ZeroDivisionError, f, seq, 10)
350
351 def test_arg_parsing(self):
352 for f in (self.module.bisect_left, self.module.bisect_right,
353 self.module.insort_left, self.module.insort_right):
354 self.assertRaises(TypeError, f, 10)
355
356 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):
357 module = py_bisect
358
359 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):
360 module = c_bisect
361
362 #==============================================================================
363
364 class ESC[4;38;5;81mTestDocExample:
365 def test_grades(self):
366 def grade(score, breakpoints=[60, 70, 80, 90], grades='FDCBA'):
367 i = self.module.bisect(breakpoints, score)
368 return grades[i]
369
370 result = [grade(score) for score in [33, 99, 77, 70, 89, 90, 100]]
371 self.assertEqual(result, ['F', 'A', 'C', 'C', 'B', 'A', 'A'])
372
373 def test_colors(self):
374 data = [('red', 5), ('blue', 1), ('yellow', 8), ('black', 0)]
375 data.sort(key=lambda r: r[1])
376 keys = [r[1] for r in data]
377 bisect_left = self.module.bisect_left
378 self.assertEqual(data[bisect_left(keys, 0)], ('black', 0))
379 self.assertEqual(data[bisect_left(keys, 1)], ('blue', 1))
380 self.assertEqual(data[bisect_left(keys, 5)], ('red', 5))
381 self.assertEqual(data[bisect_left(keys, 8)], ('yellow', 8))
382
383 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):
384 module = py_bisect
385
386 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):
387 module = c_bisect
388
389 #------------------------------------------------------------------------------
390
391 if __name__ == "__main__":
392 unittest.main()