Commit | Line | Data |
---|---|---|
920dae64 AT |
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 | #============================================================================== | |
134 | ||
135 | class TestInsort(unittest.TestCase): | |
136 | ||
137 | def test_vsBuiltinSort(self, n=500): | |
138 | from random import choice | |
139 | for insorted in (list(), UserList()): | |
140 | for i in xrange(n): | |
141 | digit = choice("0123456789") | |
142 | if digit in "02468": | |
143 | f = insort_left | |
144 | else: | |
145 | f = insort_right | |
146 | f(insorted, digit) | |
147 | self.assertEqual(sorted(insorted), insorted) | |
148 | ||
149 | def test_backcompatibility(self): | |
150 | self.assertEqual(insort, insort_right) | |
151 | ||
152 | #============================================================================== | |
153 | ||
154 | ||
155 | class LenOnly: | |
156 | "Dummy sequence class defining __len__ but not __getitem__." | |
157 | def __len__(self): | |
158 | return 10 | |
159 | ||
160 | class GetOnly: | |
161 | "Dummy sequence class defining __getitem__ but not __len__." | |
162 | def __getitem__(self, ndx): | |
163 | return 10 | |
164 | ||
165 | class CmpErr: | |
166 | "Dummy element that always raises an error during comparison" | |
167 | def __cmp__(self, other): | |
168 | raise ZeroDivisionError | |
169 | ||
170 | class TestErrorHandling(unittest.TestCase): | |
171 | ||
172 | def test_non_sequence(self): | |
173 | for f in (bisect_left, bisect_right, insort_left, insort_right): | |
174 | self.assertRaises(TypeError, f, 10, 10) | |
175 | ||
176 | def test_len_only(self): | |
177 | for f in (bisect_left, bisect_right, insort_left, insort_right): | |
178 | self.assertRaises(AttributeError, f, LenOnly(), 10) | |
179 | ||
180 | def test_get_only(self): | |
181 | for f in (bisect_left, bisect_right, insort_left, insort_right): | |
182 | self.assertRaises(AttributeError, f, GetOnly(), 10) | |
183 | ||
184 | def test_cmp_err(self): | |
185 | seq = [CmpErr(), CmpErr(), CmpErr()] | |
186 | for f in (bisect_left, bisect_right, insort_left, insort_right): | |
187 | self.assertRaises(ZeroDivisionError, f, seq, 10) | |
188 | ||
189 | def test_arg_parsing(self): | |
190 | for f in (bisect_left, bisect_right, insort_left, insort_right): | |
191 | self.assertRaises(TypeError, f, 10) | |
192 | ||
193 | #============================================================================== | |
194 | ||
195 | libreftest = """ | |
196 | Example from the Library Reference: Doc/lib/libbisect.tex | |
197 | ||
198 | The bisect() function is generally useful for categorizing numeric data. | |
199 | This example uses bisect() to look up a letter grade for an exam total | |
200 | (say) based on a set of ordered numeric breakpoints: 85 and up is an `A', | |
201 | 75..84 is a `B', etc. | |
202 | ||
203 | >>> grades = "FEDCBA" | |
204 | >>> breakpoints = [30, 44, 66, 75, 85] | |
205 | >>> from bisect import bisect | |
206 | >>> def grade(total): | |
207 | ... return grades[bisect(breakpoints, total)] | |
208 | ... | |
209 | >>> grade(66) | |
210 | 'C' | |
211 | >>> map(grade, [33, 99, 77, 44, 12, 88]) | |
212 | ['E', 'A', 'B', 'D', 'F', 'A'] | |
213 | ||
214 | """ | |
215 | ||
216 | #------------------------------------------------------------------------------ | |
217 | ||
218 | __test__ = {'libreftest' : libreftest} | |
219 | ||
220 | def test_main(verbose=None): | |
221 | from test import test_bisect | |
222 | from types import BuiltinFunctionType | |
223 | import sys | |
224 | ||
225 | test_classes = [TestBisect, TestInsort] | |
226 | if isinstance(bisect_left, BuiltinFunctionType): | |
227 | test_classes.append(TestErrorHandling) | |
228 | ||
229 | test_support.run_unittest(*test_classes) | |
230 | test_support.run_doctest(test_bisect, verbose) | |
231 | ||
232 | # verify reference counting | |
233 | if verbose and hasattr(sys, "gettotalrefcount"): | |
234 | import gc | |
235 | counts = [None] * 5 | |
236 | for i in xrange(len(counts)): | |
237 | test_support.run_unittest(*test_classes) | |
238 | gc.collect() | |
239 | counts[i] = sys.gettotalrefcount() | |
240 | print counts | |
241 | ||
242 | if __name__ == "__main__": | |
243 | test_main(verbose=True) |