1import sys
2import unittest
3from test.support import import_helper
4from collections import UserList
5
6
7py_bisect = import_helper.import_fresh_module('bisect', blocked=['_bisect'])
8c_bisect = import_helper.import_fresh_module('bisect', fresh=['_bisect'])
9
10class 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
32class 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
260class TestBisectPython(TestBisect, unittest.TestCase):
261    module = py_bisect
262
263class TestBisectC(TestBisect, unittest.TestCase):
264    module = c_bisect
265
266#==============================================================================
267
268class 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
295class TestInsortPython(TestInsort, unittest.TestCase):
296    module = py_bisect
297
298class TestInsortC(TestInsort, unittest.TestCase):
299    module = c_bisect
300
301#==============================================================================
302
303class LenOnly:
304    "Dummy sequence class defining __len__ but not __getitem__."
305    def __len__(self):
306        return 10
307
308class GetOnly:
309    "Dummy sequence class defining __getitem__ but not __len__."
310    def __getitem__(self, ndx):
311        return 10
312
313class 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
323class 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
350class TestErrorHandlingPython(TestErrorHandling, unittest.TestCase):
351    module = py_bisect
352
353class TestErrorHandlingC(TestErrorHandling, unittest.TestCase):
354    module = c_bisect
355
356#==============================================================================
357
358class 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
377class TestDocExamplePython(TestDocExample, unittest.TestCase):
378    module = py_bisect
379
380class TestDocExampleC(TestDocExample, unittest.TestCase):
381    module = c_bisect
382
383#------------------------------------------------------------------------------
384
385if __name__ == "__main__":
386    unittest.main()
387