|
1 import unittest |
|
2 from test import test_support |
|
3 from bisect import bisect_right, bisect_left, insort_left, insort_right, insort, bisect |
|
4 from UserList import UserList |
|
5 |
|
6 class TestBisect(unittest.TestCase): |
|
7 |
|
8 precomputedCases = [ |
|
9 (bisect_right, [], 1, 0), |
|
10 (bisect_right, [1], 0, 0), |
|
11 (bisect_right, [1], 1, 1), |
|
12 (bisect_right, [1], 2, 1), |
|
13 (bisect_right, [1, 1], 0, 0), |
|
14 (bisect_right, [1, 1], 1, 2), |
|
15 (bisect_right, [1, 1], 2, 2), |
|
16 (bisect_right, [1, 1, 1], 0, 0), |
|
17 (bisect_right, [1, 1, 1], 1, 3), |
|
18 (bisect_right, [1, 1, 1], 2, 3), |
|
19 (bisect_right, [1, 1, 1, 1], 0, 0), |
|
20 (bisect_right, [1, 1, 1, 1], 1, 4), |
|
21 (bisect_right, [1, 1, 1, 1], 2, 4), |
|
22 (bisect_right, [1, 2], 0, 0), |
|
23 (bisect_right, [1, 2], 1, 1), |
|
24 (bisect_right, [1, 2], 1.5, 1), |
|
25 (bisect_right, [1, 2], 2, 2), |
|
26 (bisect_right, [1, 2], 3, 2), |
|
27 (bisect_right, [1, 1, 2, 2], 0, 0), |
|
28 (bisect_right, [1, 1, 2, 2], 1, 2), |
|
29 (bisect_right, [1, 1, 2, 2], 1.5, 2), |
|
30 (bisect_right, [1, 1, 2, 2], 2, 4), |
|
31 (bisect_right, [1, 1, 2, 2], 3, 4), |
|
32 (bisect_right, [1, 2, 3], 0, 0), |
|
33 (bisect_right, [1, 2, 3], 1, 1), |
|
34 (bisect_right, [1, 2, 3], 1.5, 1), |
|
35 (bisect_right, [1, 2, 3], 2, 2), |
|
36 (bisect_right, [1, 2, 3], 2.5, 2), |
|
37 (bisect_right, [1, 2, 3], 3, 3), |
|
38 (bisect_right, [1, 2, 3], 4, 3), |
|
39 (bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 0, 0), |
|
40 (bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 1, 1), |
|
41 (bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 1.5, 1), |
|
42 (bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 2, 3), |
|
43 (bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 2.5, 3), |
|
44 (bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 3, 6), |
|
45 (bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 3.5, 6), |
|
46 (bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 4, 10), |
|
47 (bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 5, 10), |
|
48 |
|
49 (bisect_left, [], 1, 0), |
|
50 (bisect_left, [1], 0, 0), |
|
51 (bisect_left, [1], 1, 0), |
|
52 (bisect_left, [1], 2, 1), |
|
53 (bisect_left, [1, 1], 0, 0), |
|
54 (bisect_left, [1, 1], 1, 0), |
|
55 (bisect_left, [1, 1], 2, 2), |
|
56 (bisect_left, [1, 1, 1], 0, 0), |
|
57 (bisect_left, [1, 1, 1], 1, 0), |
|
58 (bisect_left, [1, 1, 1], 2, 3), |
|
59 (bisect_left, [1, 1, 1, 1], 0, 0), |
|
60 (bisect_left, [1, 1, 1, 1], 1, 0), |
|
61 (bisect_left, [1, 1, 1, 1], 2, 4), |
|
62 (bisect_left, [1, 2], 0, 0), |
|
63 (bisect_left, [1, 2], 1, 0), |
|
64 (bisect_left, [1, 2], 1.5, 1), |
|
65 (bisect_left, [1, 2], 2, 1), |
|
66 (bisect_left, [1, 2], 3, 2), |
|
67 (bisect_left, [1, 1, 2, 2], 0, 0), |
|
68 (bisect_left, [1, 1, 2, 2], 1, 0), |
|
69 (bisect_left, [1, 1, 2, 2], 1.5, 2), |
|
70 (bisect_left, [1, 1, 2, 2], 2, 2), |
|
71 (bisect_left, [1, 1, 2, 2], 3, 4), |
|
72 (bisect_left, [1, 2, 3], 0, 0), |
|
73 (bisect_left, [1, 2, 3], 1, 0), |
|
74 (bisect_left, [1, 2, 3], 1.5, 1), |
|
75 (bisect_left, [1, 2, 3], 2, 1), |
|
76 (bisect_left, [1, 2, 3], 2.5, 2), |
|
77 (bisect_left, [1, 2, 3], 3, 2), |
|
78 (bisect_left, [1, 2, 3], 4, 3), |
|
79 (bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 0, 0), |
|
80 (bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 1, 0), |
|
81 (bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 1.5, 1), |
|
82 (bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 2, 1), |
|
83 (bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 2.5, 3), |
|
84 (bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 3, 3), |
|
85 (bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 3.5, 6), |
|
86 (bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 4, 6), |
|
87 (bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 5, 10) |
|
88 ] |
|
89 |
|
90 def test_precomputed(self): |
|
91 for func, data, elem, expected in self.precomputedCases: |
|
92 self.assertEqual(func(data, elem), expected) |
|
93 self.assertEqual(func(UserList(data), elem), expected) |
|
94 |
|
95 def test_random(self, n=25): |
|
96 from random import randrange |
|
97 for i in xrange(n): |
|
98 data = [randrange(0, n, 2) for j in xrange(i)] |
|
99 data.sort() |
|
100 elem = randrange(-1, n+1) |
|
101 ip = bisect_left(data, elem) |
|
102 if ip < len(data): |
|
103 self.failUnless(elem <= data[ip]) |
|
104 if ip > 0: |
|
105 self.failUnless(data[ip-1] < elem) |
|
106 ip = bisect_right(data, elem) |
|
107 if ip < len(data): |
|
108 self.failUnless(elem < data[ip]) |
|
109 if ip > 0: |
|
110 self.failUnless(data[ip-1] <= elem) |
|
111 |
|
112 def test_optionalSlicing(self): |
|
113 for func, data, elem, expected in self.precomputedCases: |
|
114 for lo in xrange(4): |
|
115 lo = min(len(data), lo) |
|
116 for hi in xrange(3,8): |
|
117 hi = min(len(data), hi) |
|
118 ip = func(data, elem, lo, hi) |
|
119 self.failUnless(lo <= ip <= hi) |
|
120 if func is bisect_left and ip < hi: |
|
121 self.failUnless(elem <= data[ip]) |
|
122 if func is bisect_left and ip > lo: |
|
123 self.failUnless(data[ip-1] < elem) |
|
124 if func is bisect_right and ip < hi: |
|
125 self.failUnless(elem < data[ip]) |
|
126 if func is bisect_right and ip > lo: |
|
127 self.failUnless(data[ip-1] <= elem) |
|
128 self.assertEqual(ip, max(lo, min(hi, expected))) |
|
129 |
|
130 def test_backcompatibility(self): |
|
131 self.assertEqual(bisect, bisect_right) |
|
132 |
|
133 def test_keyword_args(self): |
|
134 data = [10, 20, 30, 40, 50] |
|
135 self.assertEqual(bisect_left(a=data, x=25, lo=1, hi=3), 2) |
|
136 self.assertEqual(bisect_right(a=data, x=25, lo=1, hi=3), 2) |
|
137 self.assertEqual(bisect(a=data, x=25, lo=1, hi=3), 2) |
|
138 insort_left(a=data, x=25, lo=1, hi=3) |
|
139 insort_right(a=data, x=25, lo=1, hi=3) |
|
140 insort(a=data, x=25, lo=1, hi=3) |
|
141 self.assertEqual(data, [10, 20, 25, 25, 25, 30, 40, 50]) |
|
142 |
|
143 #============================================================================== |
|
144 |
|
145 class TestInsort(unittest.TestCase): |
|
146 |
|
147 def test_vsBuiltinSort(self, n=500): |
|
148 from random import choice |
|
149 for insorted in (list(), UserList()): |
|
150 for i in xrange(n): |
|
151 digit = choice("0123456789") |
|
152 if digit in "02468": |
|
153 f = insort_left |
|
154 else: |
|
155 f = insort_right |
|
156 f(insorted, digit) |
|
157 self.assertEqual(sorted(insorted), insorted) |
|
158 |
|
159 def test_backcompatibility(self): |
|
160 self.assertEqual(insort, insort_right) |
|
161 |
|
162 #============================================================================== |
|
163 |
|
164 |
|
165 class LenOnly: |
|
166 "Dummy sequence class defining __len__ but not __getitem__." |
|
167 def __len__(self): |
|
168 return 10 |
|
169 |
|
170 class GetOnly: |
|
171 "Dummy sequence class defining __getitem__ but not __len__." |
|
172 def __getitem__(self, ndx): |
|
173 return 10 |
|
174 |
|
175 class CmpErr: |
|
176 "Dummy element that always raises an error during comparison" |
|
177 def __cmp__(self, other): |
|
178 raise ZeroDivisionError |
|
179 |
|
180 class TestErrorHandling(unittest.TestCase): |
|
181 |
|
182 def test_non_sequence(self): |
|
183 for f in (bisect_left, bisect_right, insort_left, insort_right): |
|
184 self.assertRaises(TypeError, f, 10, 10) |
|
185 |
|
186 def test_len_only(self): |
|
187 for f in (bisect_left, bisect_right, insort_left, insort_right): |
|
188 self.assertRaises(AttributeError, f, LenOnly(), 10) |
|
189 |
|
190 def test_get_only(self): |
|
191 for f in (bisect_left, bisect_right, insort_left, insort_right): |
|
192 self.assertRaises(AttributeError, f, GetOnly(), 10) |
|
193 |
|
194 def test_cmp_err(self): |
|
195 seq = [CmpErr(), CmpErr(), CmpErr()] |
|
196 for f in (bisect_left, bisect_right, insort_left, insort_right): |
|
197 self.assertRaises(ZeroDivisionError, f, seq, 10) |
|
198 |
|
199 def test_arg_parsing(self): |
|
200 for f in (bisect_left, bisect_right, insort_left, insort_right): |
|
201 self.assertRaises(TypeError, f, 10) |
|
202 |
|
203 #============================================================================== |
|
204 |
|
205 libreftest = """ |
|
206 Example from the Library Reference: Doc/lib/libbisect.tex |
|
207 |
|
208 The bisect() function is generally useful for categorizing numeric data. |
|
209 This example uses bisect() to look up a letter grade for an exam total |
|
210 (say) based on a set of ordered numeric breakpoints: 85 and up is an `A', |
|
211 75..84 is a `B', etc. |
|
212 |
|
213 >>> grades = "FEDCBA" |
|
214 >>> breakpoints = [30, 44, 66, 75, 85] |
|
215 >>> from bisect import bisect |
|
216 >>> def grade(total): |
|
217 ... return grades[bisect(breakpoints, total)] |
|
218 ... |
|
219 >>> grade(66) |
|
220 'C' |
|
221 >>> map(grade, [33, 99, 77, 44, 12, 88]) |
|
222 ['E', 'A', 'B', 'D', 'F', 'A'] |
|
223 |
|
224 """ |
|
225 |
|
226 #------------------------------------------------------------------------------ |
|
227 |
|
228 __test__ = {'libreftest' : libreftest} |
|
229 |
|
230 def test_main(verbose=None): |
|
231 from test import test_bisect |
|
232 from types import BuiltinFunctionType |
|
233 import sys |
|
234 |
|
235 test_classes = [TestBisect, TestInsort] |
|
236 if isinstance(bisect_left, BuiltinFunctionType): |
|
237 test_classes.append(TestErrorHandling) |
|
238 |
|
239 test_support.run_unittest(*test_classes) |
|
240 test_support.run_doctest(test_bisect, verbose) |
|
241 |
|
242 # verify reference counting |
|
243 if verbose and hasattr(sys, "gettotalrefcount"): |
|
244 import gc |
|
245 counts = [None] * 5 |
|
246 for i in xrange(len(counts)): |
|
247 test_support.run_unittest(*test_classes) |
|
248 gc.collect() |
|
249 counts[i] = sys.gettotalrefcount() |
|
250 print counts |
|
251 |
|
252 if __name__ == "__main__": |
|
253 test_main(verbose=True) |