1import sys
2import unittest
3from test import support
4from collections import UserList
5
6py_bisect = support.import_fresh_module('bisect', blocked=['_bisect'])
7c_bisect = support.import_fresh_module('bisect', fresh=['_bisect'])
8
9class Range(object):
10    """A trivial range()-like object that has an insert() method."""
11    def __init__(self, start, stop):
12        self.start = start
13        self.stop = stop
14        self.last_insert = None
15
16    def __len__(self):
17        return self.stop - self.start
18
19    def __getitem__(self, idx):
20        n = self.stop - self.start
21        if idx < 0:
22            idx += n
23        if idx >= n:
24            raise IndexError(idx)
25        return self.start + idx
26
27    def insert(self, idx, item):
28        self.last_insert = idx, item
29
30
31class TestBisect:
32    def setUp(self):
33        self.precomputedCases = [
34            (self.module.bisect_right, [], 1, 0),
35            (self.module.bisect_right, [1], 0, 0),
36            (self.module.bisect_right, [1], 1, 1),
37            (self.module.bisect_right, [1], 2, 1),
38            (self.module.bisect_right, [1, 1], 0, 0),
39            (self.module.bisect_right, [1, 1], 1, 2),
40            (self.module.bisect_right, [1, 1], 2, 2),
41            (self.module.bisect_right, [1, 1, 1], 0, 0),
42            (self.module.bisect_right, [1, 1, 1], 1, 3),
43            (self.module.bisect_right, [1, 1, 1], 2, 3),
44            (self.module.bisect_right, [1, 1, 1, 1], 0, 0),
45            (self.module.bisect_right, [1, 1, 1, 1], 1, 4),
46            (self.module.bisect_right, [1, 1, 1, 1], 2, 4),
47            (self.module.bisect_right, [1, 2], 0, 0),
48            (self.module.bisect_right, [1, 2], 1, 1),
49            (self.module.bisect_right, [1, 2], 1.5, 1),
50            (self.module.bisect_right, [1, 2], 2, 2),
51            (self.module.bisect_right, [1, 2], 3, 2),
52            (self.module.bisect_right, [1, 1, 2, 2], 0, 0),
53            (self.module.bisect_right, [1, 1, 2, 2], 1, 2),
54            (self.module.bisect_right, [1, 1, 2, 2], 1.5, 2),
55            (self.module.bisect_right, [1, 1, 2, 2], 2, 4),
56            (self.module.bisect_right, [1, 1, 2, 2], 3, 4),
57            (self.module.bisect_right, [1, 2, 3], 0, 0),
58            (self.module.bisect_right, [1, 2, 3], 1, 1),
59            (self.module.bisect_right, [1, 2, 3], 1.5, 1),
60            (self.module.bisect_right, [1, 2, 3], 2, 2),
61            (self.module.bisect_right, [1, 2, 3], 2.5, 2),
62            (self.module.bisect_right, [1, 2, 3], 3, 3),
63            (self.module.bisect_right, [1, 2, 3], 4, 3),
64            (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 0, 0),
65            (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 1, 1),
66            (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 1.5, 1),
67            (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 2, 3),
68            (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 2.5, 3),
69            (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 3, 6),
70            (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 3.5, 6),
71            (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 4, 10),
72            (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 5, 10),
73
74            (self.module.bisect_left, [], 1, 0),
75            (self.module.bisect_left, [1], 0, 0),
76            (self.module.bisect_left, [1], 1, 0),
77            (self.module.bisect_left, [1], 2, 1),
78            (self.module.bisect_left, [1, 1], 0, 0),
79            (self.module.bisect_left, [1, 1], 1, 0),
80            (self.module.bisect_left, [1, 1], 2, 2),
81            (self.module.bisect_left, [1, 1, 1], 0, 0),
82            (self.module.bisect_left, [1, 1, 1], 1, 0),
83            (self.module.bisect_left, [1, 1, 1], 2, 3),
84            (self.module.bisect_left, [1, 1, 1, 1], 0, 0),
85            (self.module.bisect_left, [1, 1, 1, 1], 1, 0),
86            (self.module.bisect_left, [1, 1, 1, 1], 2, 4),
87            (self.module.bisect_left, [1, 2], 0, 0),
88            (self.module.bisect_left, [1, 2], 1, 0),
89            (self.module.bisect_left, [1, 2], 1.5, 1),
90            (self.module.bisect_left, [1, 2], 2, 1),
91            (self.module.bisect_left, [1, 2], 3, 2),
92            (self.module.bisect_left, [1, 1, 2, 2], 0, 0),
93            (self.module.bisect_left, [1, 1, 2, 2], 1, 0),
94            (self.module.bisect_left, [1, 1, 2, 2], 1.5, 2),
95            (self.module.bisect_left, [1, 1, 2, 2], 2, 2),
96            (self.module.bisect_left, [1, 1, 2, 2], 3, 4),
97            (self.module.bisect_left, [1, 2, 3], 0, 0),
98            (self.module.bisect_left, [1, 2, 3], 1, 0),
99            (self.module.bisect_left, [1, 2, 3], 1.5, 1),
100            (self.module.bisect_left, [1, 2, 3], 2, 1),
101            (self.module.bisect_left, [1, 2, 3], 2.5, 2),
102            (self.module.bisect_left, [1, 2, 3], 3, 2),
103            (self.module.bisect_left, [1, 2, 3], 4, 3),
104            (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 0, 0),
105            (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 1, 0),
106            (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 1.5, 1),
107            (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 2, 1),
108            (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 2.5, 3),
109            (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 3, 3),
110            (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 3.5, 6),
111            (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 4, 6),
112            (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 5, 10)
113        ]
114
115    def test_precomputed(self):
116        for func, data, elem, expected in self.precomputedCases:
117            self.assertEqual(func(data, elem), expected)
118            self.assertEqual(func(UserList(data), elem), expected)
119
120    def test_negative_lo(self):
121        # Issue 3301
122        mod = self.module
123        self.assertRaises(ValueError, mod.bisect_left, [1, 2, 3], 5, -1, 3)
124        self.assertRaises(ValueError, mod.bisect_right, [1, 2, 3], 5, -1, 3)
125        self.assertRaises(ValueError, mod.insort_left, [1, 2, 3], 5, -1, 3)
126        self.assertRaises(ValueError, mod.insort_right, [1, 2, 3], 5, -1, 3)
127
128    def test_large_range(self):
129        # Issue 13496
130        mod = self.module
131        n = sys.maxsize
132        data = range(n-1)
133        self.assertEqual(mod.bisect_left(data, n-3), n-3)
134        self.assertEqual(mod.bisect_right(data, n-3), n-2)
135        self.assertEqual(mod.bisect_left(data, n-3, n-10, n), n-3)
136        self.assertEqual(mod.bisect_right(data, n-3, n-10, n), n-2)
137
138    def test_large_pyrange(self):
139        # Same as above, but without C-imposed limits on range() parameters
140        mod = self.module
141        n = sys.maxsize
142        data = Range(0, n-1)
143        self.assertEqual(mod.bisect_left(data, n-3), n-3)
144        self.assertEqual(mod.bisect_right(data, n-3), n-2)
145        self.assertEqual(mod.bisect_left(data, n-3, n-10, n), n-3)
146        self.assertEqual(mod.bisect_right(data, n-3, n-10, n), n-2)
147        x = n - 100
148        mod.insort_left(data, x, x - 50, x + 50)
149        self.assertEqual(data.last_insert, (x, x))
150        x = n - 200
151        mod.insort_right(data, x, x - 50, x + 50)
152        self.assertEqual(data.last_insert, (x + 1, x))
153
154    def test_random(self, n=25):
155        from random import randrange
156        for i in range(n):
157            data = [randrange(0, n, 2) for j in range(i)]
158            data.sort()
159            elem = randrange(-1, n+1)
160            ip = self.module.bisect_left(data, elem)
161            if ip < len(data):
162                self.assertTrue(elem <= data[ip])
163            if ip > 0:
164                self.assertTrue(data[ip-1] < elem)
165            ip = self.module.bisect_right(data, elem)
166            if ip < len(data):
167                self.assertTrue(elem < data[ip])
168            if ip > 0:
169                self.assertTrue(data[ip-1] <= elem)
170
171    def test_optionalSlicing(self):
172        for func, data, elem, expected in self.precomputedCases:
173            for lo in range(4):
174                lo = min(len(data), lo)
175                for hi in range(3,8):
176                    hi = min(len(data), hi)
177                    ip = func(data, elem, lo, hi)
178                    self.assertTrue(lo <= ip <= hi)
179                    if func is self.module.bisect_left and ip < hi:
180                        self.assertTrue(elem <= data[ip])
181                    if func is self.module.bisect_left and ip > lo:
182                        self.assertTrue(data[ip-1] < elem)
183                    if func is self.module.bisect_right and ip < hi:
184                        self.assertTrue(elem < data[ip])
185                    if func is self.module.bisect_right and ip > lo:
186                        self.assertTrue(data[ip-1] <= elem)
187                    self.assertEqual(ip, max(lo, min(hi, expected)))
188
189    def test_backcompatibility(self):
190        self.assertEqual(self.module.bisect, self.module.bisect_right)
191
192    def test_keyword_args(self):
193        data = [10, 20, 30, 40, 50]
194        self.assertEqual(self.module.bisect_left(a=data, x=25, lo=1, hi=3), 2)
195        self.assertEqual(self.module.bisect_right(a=data, x=25, lo=1, hi=3), 2)
196        self.assertEqual(self.module.bisect(a=data, x=25, lo=1, hi=3), 2)
197        self.module.insort_left(a=data, x=25, lo=1, hi=3)
198        self.module.insort_right(a=data, x=25, lo=1, hi=3)
199        self.module.insort(a=data, x=25, lo=1, hi=3)
200        self.assertEqual(data, [10, 20, 25, 25, 25, 30, 40, 50])
201
202class TestBisectPython(TestBisect, unittest.TestCase):
203    module = py_bisect
204
205class TestBisectC(TestBisect, unittest.TestCase):
206    module = c_bisect
207
208#==============================================================================
209
210class TestInsort:
211    def test_vsBuiltinSort(self, n=500):
212        from random import choice
213        for insorted in (list(), UserList()):
214            for i in range(n):
215                digit = choice("0123456789")
216                if digit in "02468":
217                    f = self.module.insort_left
218                else:
219                    f = self.module.insort_right
220                f(insorted, digit)
221            self.assertEqual(sorted(insorted), insorted)
222
223    def test_backcompatibility(self):
224        self.assertEqual(self.module.insort, self.module.insort_right)
225
226    def test_listDerived(self):
227        class List(list):
228            data = []
229            def insert(self, index, item):
230                self.data.insert(index, item)
231
232        lst = List()
233        self.module.insort_left(lst, 10)
234        self.module.insort_right(lst, 5)
235        self.assertEqual([5, 10], lst.data)
236
237class TestInsortPython(TestInsort, unittest.TestCase):
238    module = py_bisect
239
240class TestInsortC(TestInsort, unittest.TestCase):
241    module = c_bisect
242
243#==============================================================================
244
245class LenOnly:
246    "Dummy sequence class defining __len__ but not __getitem__."
247    def __len__(self):
248        return 10
249
250class GetOnly:
251    "Dummy sequence class defining __getitem__ but not __len__."
252    def __getitem__(self, ndx):
253        return 10
254
255class CmpErr:
256    "Dummy element that always raises an error during comparison"
257    def __lt__(self, other):
258        raise ZeroDivisionError
259    __gt__ = __lt__
260    __le__ = __lt__
261    __ge__ = __lt__
262    __eq__ = __lt__
263    __ne__ = __lt__
264
265class TestErrorHandling:
266    def test_non_sequence(self):
267        for f in (self.module.bisect_left, self.module.bisect_right,
268                  self.module.insort_left, self.module.insort_right):
269            self.assertRaises(TypeError, f, 10, 10)
270
271    def test_len_only(self):
272        for f in (self.module.bisect_left, self.module.bisect_right,
273                  self.module.insort_left, self.module.insort_right):
274            self.assertRaises(TypeError, f, LenOnly(), 10)
275
276    def test_get_only(self):
277        for f in (self.module.bisect_left, self.module.bisect_right,
278                  self.module.insort_left, self.module.insort_right):
279            self.assertRaises(TypeError, f, GetOnly(), 10)
280
281    def test_cmp_err(self):
282        seq = [CmpErr(), CmpErr(), CmpErr()]
283        for f in (self.module.bisect_left, self.module.bisect_right,
284                  self.module.insort_left, self.module.insort_right):
285            self.assertRaises(ZeroDivisionError, f, seq, 10)
286
287    def test_arg_parsing(self):
288        for f in (self.module.bisect_left, self.module.bisect_right,
289                  self.module.insort_left, self.module.insort_right):
290            self.assertRaises(TypeError, f, 10)
291
292class TestErrorHandlingPython(TestErrorHandling, unittest.TestCase):
293    module = py_bisect
294
295class TestErrorHandlingC(TestErrorHandling, unittest.TestCase):
296    module = c_bisect
297
298#==============================================================================
299
300class TestDocExample:
301    def test_grades(self):
302        def grade(score, breakpoints=[60, 70, 80, 90], grades='FDCBA'):
303            i = self.module.bisect(breakpoints, score)
304            return grades[i]
305
306        result = [grade(score) for score in [33, 99, 77, 70, 89, 90, 100]]
307        self.assertEqual(result, ['F', 'A', 'C', 'C', 'B', 'A', 'A'])
308
309    def test_colors(self):
310        data = [('red', 5), ('blue', 1), ('yellow', 8), ('black', 0)]
311        data.sort(key=lambda r: r[1])
312        keys = [r[1] for r in data]
313        bisect_left = self.module.bisect_left
314        self.assertEqual(data[bisect_left(keys, 0)], ('black', 0))
315        self.assertEqual(data[bisect_left(keys, 1)], ('blue', 1))
316        self.assertEqual(data[bisect_left(keys, 5)], ('red', 5))
317        self.assertEqual(data[bisect_left(keys, 8)], ('yellow', 8))
318
319class TestDocExamplePython(TestDocExample, unittest.TestCase):
320    module = py_bisect
321
322class TestDocExampleC(TestDocExample, unittest.TestCase):
323    module = c_bisect
324
325#------------------------------------------------------------------------------
326
327if __name__ == "__main__":
328    unittest.main()
329