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