0001 import unittest 0002 from test import test_support 0003 from bisect import bisect_right, bisect_left, insort_left, insort_right, insort, bisect 0004 from UserList import UserList 0005 0006 class TestBisect(unittest.TestCase): 0007 0008 precomputedCases = [ 0009 (bisect_right, [], 1, 0), 0010 (bisect_right, [1], 0, 0), 0011 (bisect_right, [1], 1, 1), 0012 (bisect_right, [1], 2, 1), 0013 (bisect_right, [1, 1], 0, 0), 0014 (bisect_right, [1, 1], 1, 2), 0015 (bisect_right, [1, 1], 2, 2), 0016 (bisect_right, [1, 1, 1], 0, 0), 0017 (bisect_right, [1, 1, 1], 1, 3), 0018 (bisect_right, [1, 1, 1], 2, 3), 0019 (bisect_right, [1, 1, 1, 1], 0, 0), 0020 (bisect_right, [1, 1, 1, 1], 1, 4), 0021 (bisect_right, [1, 1, 1, 1], 2, 4), 0022 (bisect_right, [1, 2], 0, 0), 0023 (bisect_right, [1, 2], 1, 1), 0024 (bisect_right, [1, 2], 1.5, 1), 0025 (bisect_right, [1, 2], 2, 2), 0026 (bisect_right, [1, 2], 3, 2), 0027 (bisect_right, [1, 1, 2, 2], 0, 0), 0028 (bisect_right, [1, 1, 2, 2], 1, 2), 0029 (bisect_right, [1, 1, 2, 2], 1.5, 2), 0030 (bisect_right, [1, 1, 2, 2], 2, 4), 0031 (bisect_right, [1, 1, 2, 2], 3, 4), 0032 (bisect_right, [1, 2, 3], 0, 0), 0033 (bisect_right, [1, 2, 3], 1, 1), 0034 (bisect_right, [1, 2, 3], 1.5, 1), 0035 (bisect_right, [1, 2, 3], 2, 2), 0036 (bisect_right, [1, 2, 3], 2.5, 2), 0037 (bisect_right, [1, 2, 3], 3, 3), 0038 (bisect_right, [1, 2, 3], 4, 3), 0039 (bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 0, 0), 0040 (bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 1, 1), 0041 (bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 1.5, 1), 0042 (bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 2, 3), 0043 (bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 2.5, 3), 0044 (bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 3, 6), 0045 (bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 3.5, 6), 0046 (bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 4, 10), 0047 (bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 5, 10), 0048 0049 (bisect_left, [], 1, 0), 0050 (bisect_left, [1], 0, 0), 0051 (bisect_left, [1], 1, 0), 0052 (bisect_left, [1], 2, 1), 0053 (bisect_left, [1, 1], 0, 0), 0054 (bisect_left, [1, 1], 1, 0), 0055 (bisect_left, [1, 1], 2, 2), 0056 (bisect_left, [1, 1, 1], 0, 0), 0057 (bisect_left, [1, 1, 1], 1, 0), 0058 (bisect_left, [1, 1, 1], 2, 3), 0059 (bisect_left, [1, 1, 1, 1], 0, 0), 0060 (bisect_left, [1, 1, 1, 1], 1, 0), 0061 (bisect_left, [1, 1, 1, 1], 2, 4), 0062 (bisect_left, [1, 2], 0, 0), 0063 (bisect_left, [1, 2], 1, 0), 0064 (bisect_left, [1, 2], 1.5, 1), 0065 (bisect_left, [1, 2], 2, 1), 0066 (bisect_left, [1, 2], 3, 2), 0067 (bisect_left, [1, 1, 2, 2], 0, 0), 0068 (bisect_left, [1, 1, 2, 2], 1, 0), 0069 (bisect_left, [1, 1, 2, 2], 1.5, 2), 0070 (bisect_left, [1, 1, 2, 2], 2, 2), 0071 (bisect_left, [1, 1, 2, 2], 3, 4), 0072 (bisect_left, [1, 2, 3], 0, 0), 0073 (bisect_left, [1, 2, 3], 1, 0), 0074 (bisect_left, [1, 2, 3], 1.5, 1), 0075 (bisect_left, [1, 2, 3], 2, 1), 0076 (bisect_left, [1, 2, 3], 2.5, 2), 0077 (bisect_left, [1, 2, 3], 3, 2), 0078 (bisect_left, [1, 2, 3], 4, 3), 0079 (bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 0, 0), 0080 (bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 1, 0), 0081 (bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 1.5, 1), 0082 (bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 2, 1), 0083 (bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 2.5, 3), 0084 (bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 3, 3), 0085 (bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 3.5, 6), 0086 (bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 4, 6), 0087 (bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 5, 10) 0088 ] 0089 0090 def test_precomputed(self): 0091 for func, data, elem, expected in self.precomputedCases: 0092 self.assertEqual(func(data, elem), expected) 0093 self.assertEqual(func(UserList(data), elem), expected) 0094 0095 def test_random(self, n=25): 0096 from random import randrange 0097 for i in xrange(n): 0098 data = [randrange(0, n, 2) for j in xrange(i)] 0099 data.sort() 0100 elem = randrange(-1, n+1) 0101 ip = bisect_left(data, elem) 0102 if ip < len(data): 0103 self.failUnless(elem <= data[ip]) 0104 if ip > 0: 0105 self.failUnless(data[ip-1] < elem) 0106 ip = bisect_right(data, elem) 0107 if ip < len(data): 0108 self.failUnless(elem < data[ip]) 0109 if ip > 0: 0110 self.failUnless(data[ip-1] <= elem) 0111 0112 def test_optionalSlicing(self): 0113 for func, data, elem, expected in self.precomputedCases: 0114 for lo in xrange(4): 0115 lo = min(len(data), lo) 0116 for hi in xrange(3,8): 0117 hi = min(len(data), hi) 0118 ip = func(data, elem, lo, hi) 0119 self.failUnless(lo <= ip <= hi) 0120 if func is bisect_left and ip < hi: 0121 self.failUnless(elem <= data[ip]) 0122 if func is bisect_left and ip > lo: 0123 self.failUnless(data[ip-1] < elem) 0124 if func is bisect_right and ip < hi: 0125 self.failUnless(elem < data[ip]) 0126 if func is bisect_right and ip > lo: 0127 self.failUnless(data[ip-1] <= elem) 0128 self.assertEqual(ip, max(lo, min(hi, expected))) 0129 0130 def test_backcompatibility(self): 0131 self.assertEqual(bisect, bisect_right) 0132 0133 #============================================================================== 0134 0135 class TestInsort(unittest.TestCase): 0136 0137 def test_vsBuiltinSort(self, n=500): 0138 from random import choice 0139 for insorted in (list(), UserList()): 0140 for i in xrange(n): 0141 digit = choice("0123456789") 0142 if digit in "02468": 0143 f = insort_left 0144 else: 0145 f = insort_right 0146 f(insorted, digit) 0147 self.assertEqual(sorted(insorted), insorted) 0148 0149 def test_backcompatibility(self): 0150 self.assertEqual(insort, insort_right) 0151 0152 #============================================================================== 0153 0154 0155 class LenOnly: 0156 "Dummy sequence class defining __len__ but not __getitem__." 0157 def __len__(self): 0158 return 10 0159 0160 class GetOnly: 0161 "Dummy sequence class defining __getitem__ but not __len__." 0162 def __getitem__(self, ndx): 0163 return 10 0164 0165 class CmpErr: 0166 "Dummy element that always raises an error during comparison" 0167 def __cmp__(self, other): 0168 raise ZeroDivisionError 0169 0170 class TestErrorHandling(unittest.TestCase): 0171 0172 def test_non_sequence(self): 0173 for f in (bisect_left, bisect_right, insort_left, insort_right): 0174 self.assertRaises(TypeError, f, 10, 10) 0175 0176 def test_len_only(self): 0177 for f in (bisect_left, bisect_right, insort_left, insort_right): 0178 self.assertRaises(AttributeError, f, LenOnly(), 10) 0179 0180 def test_get_only(self): 0181 for f in (bisect_left, bisect_right, insort_left, insort_right): 0182 self.assertRaises(AttributeError, f, GetOnly(), 10) 0183 0184 def test_cmp_err(self): 0185 seq = [CmpErr(), CmpErr(), CmpErr()] 0186 for f in (bisect_left, bisect_right, insort_left, insort_right): 0187 self.assertRaises(ZeroDivisionError, f, seq, 10) 0188 0189 def test_arg_parsing(self): 0190 for f in (bisect_left, bisect_right, insort_left, insort_right): 0191 self.assertRaises(TypeError, f, 10) 0192 0193 #============================================================================== 0194 0195 libreftest = """ 0196 Example from the Library Reference: Doc/lib/libbisect.tex 0197 0198 The bisect() function is generally useful for categorizing numeric data. 0199 This example uses bisect() to look up a letter grade for an exam total 0200 (say) based on a set of ordered numeric breakpoints: 85 and up is an `A', 0201 75..84 is a `B', etc. 0202 0203 >>> grades = "FEDCBA" 0204 >>> breakpoints = [30, 44, 66, 75, 85] 0205 >>> from bisect import bisect 0206 >>> def grade(total): 0207 ... return grades[bisect(breakpoints, total)] 0208 ... 0209 >>> grade(66) 0210 'C' 0211 >>> map(grade, [33, 99, 77, 44, 12, 88]) 0212 ['E', 'A', 'B', 'D', 'F', 'A'] 0213 0214 """ 0215 0216 #------------------------------------------------------------------------------ 0217 0218 __test__ = {'libreftest' : libreftest} 0219 0220 def test_main(verbose=None): 0221 from test import test_bisect 0222 from types import BuiltinFunctionType 0223 import sys 0224 0225 test_classes = [TestBisect, TestInsort] 0226 if isinstance(bisect_left, BuiltinFunctionType): 0227 test_classes.append(TestErrorHandling) 0228 0229 test_support.run_unittest(*test_classes) 0230 test_support.run_doctest(test_bisect, verbose) 0231 0232 # verify reference counting 0233 if verbose and hasattr(sys, "gettotalrefcount"): 0234 import gc 0235 counts = [None] * 5 0236 for i in xrange(len(counts)): 0237 test_support.run_unittest(*test_classes) 0238 gc.collect() 0239 counts[i] = sys.gettotalrefcount() 0240 print counts 0241 0242 if __name__ == "__main__": 0243 test_main(verbose=True) 0244
Generated by PyXR 0.9.4