1import sys
2import unittest
3from test import test_support
4from UserList import UserList
5
6# We do a bit of trickery here to be able to test both the C implementation
7# and the Python implementation of the module.
8
9# Make it impossible to import the C implementation anymore.
10sys.modules['_bisect'] = 0
11# We must also handle the case that bisect was imported before.
12if 'bisect' in sys.modules:
13    del sys.modules['bisect']
14
15# Now we can import the module and get the pure Python implementation.
16import bisect as py_bisect
17
18# Restore everything to normal.
19del sys.modules['_bisect']
20del sys.modules['bisect']
21
22# This is now the module with the C implementation.
23import bisect as c_bisect
24
25
26class Range(object):
27    """A trivial xrange()-like object without any integer width limitations."""
28    def __init__(self, start, stop):
29        self.start = start
30        self.stop = stop
31        self.last_insert = None
32
33    def __len__(self):
34        return self.stop - self.start
35
36    def __getitem__(self, idx):
37        n = self.stop - self.start
38        if idx < 0:
39            idx += n
40        if idx >= n:
41            raise IndexError(idx)
42        return self.start + idx
43
44    def insert(self, idx, item):
45        self.last_insert = idx, item
46
47
48class TestBisect(unittest.TestCase):
49    module = None
50
51    def setUp(self):
52        self.precomputedCases = [
53            (self.module.bisect_right, [], 1, 0),
54            (self.module.bisect_right, [1], 0, 0),
55            (self.module.bisect_right, [1], 1, 1),
56            (self.module.bisect_right, [1], 2, 1),
57            (self.module.bisect_right, [1, 1], 0, 0),
58            (self.module.bisect_right, [1, 1], 1, 2),
59            (self.module.bisect_right, [1, 1], 2, 2),
60            (self.module.bisect_right, [1, 1, 1], 0, 0),
61            (self.module.bisect_right, [1, 1, 1], 1, 3),
62            (self.module.bisect_right, [1, 1, 1], 2, 3),
63            (self.module.bisect_right, [1, 1, 1, 1], 0, 0),
64            (self.module.bisect_right, [1, 1, 1, 1], 1, 4),
65            (self.module.bisect_right, [1, 1, 1, 1], 2, 4),
66            (self.module.bisect_right, [1, 2], 0, 0),
67            (self.module.bisect_right, [1, 2], 1, 1),
68            (self.module.bisect_right, [1, 2], 1.5, 1),
69            (self.module.bisect_right, [1, 2], 2, 2),
70            (self.module.bisect_right, [1, 2], 3, 2),
71            (self.module.bisect_right, [1, 1, 2, 2], 0, 0),
72            (self.module.bisect_right, [1, 1, 2, 2], 1, 2),
73            (self.module.bisect_right, [1, 1, 2, 2], 1.5, 2),
74            (self.module.bisect_right, [1, 1, 2, 2], 2, 4),
75            (self.module.bisect_right, [1, 1, 2, 2], 3, 4),
76            (self.module.bisect_right, [1, 2, 3], 0, 0),
77            (self.module.bisect_right, [1, 2, 3], 1, 1),
78            (self.module.bisect_right, [1, 2, 3], 1.5, 1),
79            (self.module.bisect_right, [1, 2, 3], 2, 2),
80            (self.module.bisect_right, [1, 2, 3], 2.5, 2),
81            (self.module.bisect_right, [1, 2, 3], 3, 3),
82            (self.module.bisect_right, [1, 2, 3], 4, 3),
83            (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 0, 0),
84            (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 1, 1),
85            (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 1.5, 1),
86            (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 2, 3),
87            (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 2.5, 3),
88            (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 3, 6),
89            (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 3.5, 6),
90            (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 4, 10),
91            (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 5, 10),
92
93            (self.module.bisect_left, [], 1, 0),
94            (self.module.bisect_left, [1], 0, 0),
95            (self.module.bisect_left, [1], 1, 0),
96            (self.module.bisect_left, [1], 2, 1),
97            (self.module.bisect_left, [1, 1], 0, 0),
98            (self.module.bisect_left, [1, 1], 1, 0),
99            (self.module.bisect_left, [1, 1], 2, 2),
100            (self.module.bisect_left, [1, 1, 1], 0, 0),
101            (self.module.bisect_left, [1, 1, 1], 1, 0),
102            (self.module.bisect_left, [1, 1, 1], 2, 3),
103            (self.module.bisect_left, [1, 1, 1, 1], 0, 0),
104            (self.module.bisect_left, [1, 1, 1, 1], 1, 0),
105            (self.module.bisect_left, [1, 1, 1, 1], 2, 4),
106            (self.module.bisect_left, [1, 2], 0, 0),
107            (self.module.bisect_left, [1, 2], 1, 0),
108            (self.module.bisect_left, [1, 2], 1.5, 1),
109            (self.module.bisect_left, [1, 2], 2, 1),
110            (self.module.bisect_left, [1, 2], 3, 2),
111            (self.module.bisect_left, [1, 1, 2, 2], 0, 0),
112            (self.module.bisect_left, [1, 1, 2, 2], 1, 0),
113            (self.module.bisect_left, [1, 1, 2, 2], 1.5, 2),
114            (self.module.bisect_left, [1, 1, 2, 2], 2, 2),
115            (self.module.bisect_left, [1, 1, 2, 2], 3, 4),
116            (self.module.bisect_left, [1, 2, 3], 0, 0),
117            (self.module.bisect_left, [1, 2, 3], 1, 0),
118            (self.module.bisect_left, [1, 2, 3], 1.5, 1),
119            (self.module.bisect_left, [1, 2, 3], 2, 1),
120            (self.module.bisect_left, [1, 2, 3], 2.5, 2),
121            (self.module.bisect_left, [1, 2, 3], 3, 2),
122            (self.module.bisect_left, [1, 2, 3], 4, 3),
123            (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 0, 0),
124            (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 1, 0),
125            (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 1.5, 1),
126            (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 2, 1),
127            (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 2.5, 3),
128            (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 3, 3),
129            (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 3.5, 6),
130            (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 4, 6),
131            (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 5, 10)
132        ]
133
134    def test_precomputed(self):
135        for func, data, elem, expected in self.precomputedCases:
136            self.assertEqual(func(data, elem), expected)
137            self.assertEqual(func(UserList(data), elem), expected)
138
139    def test_negative_lo(self):
140        # Issue 3301
141        mod = self.module
142        self.assertRaises(ValueError, mod.bisect_left, [1, 2, 3], 5, -1, 3),
143        self.assertRaises(ValueError, mod.bisect_right, [1, 2, 3], 5, -1, 3),
144        self.assertRaises(ValueError, mod.insort_left, [1, 2, 3], 5, -1, 3),
145        self.assertRaises(ValueError, mod.insort_right, [1, 2, 3], 5, -1, 3),
146
147    def test_large_range(self):
148        # Issue 13496
149        mod = self.module
150        n = sys.maxsize
151        try:
152            data = xrange(n-1)
153        except OverflowError:
154            self.skipTest("can't create a xrange() object of size `sys.maxsize`")
155        self.assertEqual(mod.bisect_left(data, n-3), n-3)
156        self.assertEqual(mod.bisect_right(data, n-3), n-2)
157        self.assertEqual(mod.bisect_left(data, n-3, n-10, n), n-3)
158        self.assertEqual(mod.bisect_right(data, n-3, n-10, n), n-2)
159
160    def test_large_pyrange(self):
161        # Same as above, but without C-imposed limits on range() parameters
162        mod = self.module
163        n = sys.maxsize
164        data = Range(0, n-1)
165        self.assertEqual(mod.bisect_left(data, n-3), n-3)
166        self.assertEqual(mod.bisect_right(data, n-3), n-2)
167        self.assertEqual(mod.bisect_left(data, n-3, n-10, n), n-3)
168        self.assertEqual(mod.bisect_right(data, n-3, n-10, n), n-2)
169        x = n - 100
170        mod.insort_left(data, x, x - 50, x + 50)
171        self.assertEqual(data.last_insert, (x, x))
172        x = n - 200
173        mod.insort_right(data, x, x - 50, x + 50)
174        self.assertEqual(data.last_insert, (x + 1, x))
175
176    def test_random(self, n=25):
177        from random import randrange
178        for i in xrange(n):
179            data = [randrange(0, n, 2) for j in xrange(i)]
180            data.sort()
181            elem = randrange(-1, n+1)
182            ip = self.module.bisect_left(data, elem)
183            if ip < len(data):
184                self.assertTrue(elem <= data[ip])
185            if ip > 0:
186                self.assertTrue(data[ip-1] < elem)
187            ip = self.module.bisect_right(data, elem)
188            if ip < len(data):
189                self.assertTrue(elem < data[ip])
190            if ip > 0:
191                self.assertTrue(data[ip-1] <= elem)
192
193    def test_optionalSlicing(self):
194        for func, data, elem, expected in self.precomputedCases:
195            for lo in xrange(4):
196                lo = min(len(data), lo)
197                for hi in xrange(3,8):
198                    hi = min(len(data), hi)
199                    ip = func(data, elem, lo, hi)
200                    self.assertTrue(lo <= ip <= hi)
201                    if func is self.module.bisect_left and ip < hi:
202                        self.assertTrue(elem <= data[ip])
203                    if func is self.module.bisect_left and ip > lo:
204                        self.assertTrue(data[ip-1] < elem)
205                    if func is self.module.bisect_right and ip < hi:
206                        self.assertTrue(elem < data[ip])
207                    if func is self.module.bisect_right and ip > lo:
208                        self.assertTrue(data[ip-1] <= elem)
209                    self.assertEqual(ip, max(lo, min(hi, expected)))
210
211    def test_backcompatibility(self):
212        self.assertEqual(self.module.bisect, self.module.bisect_right)
213
214    def test_keyword_args(self):
215        data = [10, 20, 30, 40, 50]
216        self.assertEqual(self.module.bisect_left(a=data, x=25, lo=1, hi=3), 2)
217        self.assertEqual(self.module.bisect_right(a=data, x=25, lo=1, hi=3), 2)
218        self.assertEqual(self.module.bisect(a=data, x=25, lo=1, hi=3), 2)
219        self.module.insort_left(a=data, x=25, lo=1, hi=3)
220        self.module.insort_right(a=data, x=25, lo=1, hi=3)
221        self.module.insort(a=data, x=25, lo=1, hi=3)
222        self.assertEqual(data, [10, 20, 25, 25, 25, 30, 40, 50])
223
224class TestBisectPython(TestBisect):
225    module = py_bisect
226
227class TestBisectC(TestBisect):
228    module = c_bisect
229
230#==============================================================================
231
232class TestInsort(unittest.TestCase):
233    module = None
234
235    def test_vsBuiltinSort(self, n=500):
236        from random import choice
237        for insorted in (list(), UserList()):
238            for i in xrange(n):
239                digit = choice("0123456789")
240                if digit in "02468":
241                    f = self.module.insort_left
242                else:
243                    f = self.module.insort_right
244                f(insorted, digit)
245            self.assertEqual(sorted(insorted), insorted)
246
247    def test_backcompatibility(self):
248        self.assertEqual(self.module.insort, self.module.insort_right)
249
250    def test_listDerived(self):
251        class List(list):
252            data = []
253            def insert(self, index, item):
254                self.data.insert(index, item)
255
256        lst = List()
257        self.module.insort_left(lst, 10)
258        self.module.insort_right(lst, 5)
259        self.assertEqual([5, 10], lst.data)
260
261class TestInsortPython(TestInsort):
262    module = py_bisect
263
264class TestInsortC(TestInsort):
265    module = c_bisect
266
267#==============================================================================
268
269
270class LenOnly:
271    "Dummy sequence class defining __len__ but not __getitem__."
272    def __len__(self):
273        return 10
274
275class GetOnly:
276    "Dummy sequence class defining __getitem__ but not __len__."
277    def __getitem__(self, ndx):
278        return 10
279
280class CmpErr:
281    "Dummy element that always raises an error during comparison"
282    def __cmp__(self, other):
283        raise ZeroDivisionError
284
285class TestErrorHandling(unittest.TestCase):
286    module = None
287
288    def test_non_sequence(self):
289        for f in (self.module.bisect_left, self.module.bisect_right,
290                  self.module.insort_left, self.module.insort_right):
291            self.assertRaises(TypeError, f, 10, 10)
292
293    def test_len_only(self):
294        for f in (self.module.bisect_left, self.module.bisect_right,
295                  self.module.insort_left, self.module.insort_right):
296            self.assertRaises(AttributeError, f, LenOnly(), 10)
297
298    def test_get_only(self):
299        for f in (self.module.bisect_left, self.module.bisect_right,
300                  self.module.insort_left, self.module.insort_right):
301            self.assertRaises(AttributeError, f, GetOnly(), 10)
302
303    def test_cmp_err(self):
304        seq = [CmpErr(), CmpErr(), CmpErr()]
305        for f in (self.module.bisect_left, self.module.bisect_right,
306                  self.module.insort_left, self.module.insort_right):
307            self.assertRaises(ZeroDivisionError, f, seq, 10)
308
309    def test_arg_parsing(self):
310        for f in (self.module.bisect_left, self.module.bisect_right,
311                  self.module.insort_left, self.module.insort_right):
312            self.assertRaises(TypeError, f, 10)
313
314class TestErrorHandlingPython(TestErrorHandling):
315    module = py_bisect
316
317class TestErrorHandlingC(TestErrorHandling):
318    module = c_bisect
319
320#==============================================================================
321
322libreftest = """
323Example from the Library Reference:  Doc/library/bisect.rst
324
325The bisect() function is generally useful for categorizing numeric data.
326This example uses bisect() to look up a letter grade for an exam total
327(say) based on a set of ordered numeric breakpoints: 85 and up is an `A',
32875..84 is a `B', etc.
329
330    >>> grades = "FEDCBA"
331    >>> breakpoints = [30, 44, 66, 75, 85]
332    >>> from bisect import bisect
333    >>> def grade(total):
334    ...           return grades[bisect(breakpoints, total)]
335    ...
336    >>> grade(66)
337    'C'
338    >>> map(grade, [33, 99, 77, 44, 12, 88])
339    ['E', 'A', 'B', 'D', 'F', 'A']
340
341"""
342
343#------------------------------------------------------------------------------
344
345__test__ = {'libreftest' : libreftest}
346
347def test_main(verbose=None):
348    from test import test_bisect
349
350    test_classes = [TestBisectPython, TestBisectC,
351                    TestInsortPython, TestInsortC,
352                    TestErrorHandlingPython, TestErrorHandlingC]
353
354    test_support.run_unittest(*test_classes)
355    test_support.run_doctest(test_bisect, verbose)
356
357    # verify reference counting
358    if verbose and hasattr(sys, "gettotalrefcount"):
359        import gc
360        counts = [None] * 5
361        for i in xrange(len(counts)):
362            test_support.run_unittest(*test_classes)
363            gc.collect()
364            counts[i] = sys.gettotalrefcount()
365        print counts
366
367if __name__ == "__main__":
368    test_main(verbose=True)
369