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