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