Lib/test/test_bisect.py

   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_random(self, n=25):
 118         from random import randrange
 119         for i in xrange(n):
 120             data = [randrange(0, n, 2) for j in xrange(i)]
 121             data.sort()
 122             elem = randrange(-1, n+1)
 123             ip = self.module.bisect_left(data, elem)
 124             if ip < len(data):
 125                 self.failUnless(elem <= data[ip])
 126             if ip > 0:
 127                 self.failUnless(data[ip-1] < elem)
 128             ip = self.module.bisect_right(data, elem)
 129             if ip < len(data):
 130                 self.failUnless(elem < data[ip])
 131             if ip > 0:
 132                 self.failUnless(data[ip-1] <= elem)
 133
 134     def test_optionalSlicing(self):
 135         for func, data, elem, expected in self.precomputedCases:
 136             for lo in xrange(4):
 137                 lo = min(len(data), lo)
 138                 for hi in xrange(3,8):
 139                     hi = min(len(data), hi)
 140                     ip = func(data, elem, lo, hi)
 141                     self.failUnless(lo <= ip <= hi)
 142                     if func is self.module.bisect_left and ip < hi:
 143                         self.failUnless(elem <= data[ip])
 144                     if func is self.module.bisect_left and ip > lo:
 145                         self.failUnless(data[ip-1] < elem)
 146                     if func is self.module.bisect_right and ip < hi:
 147                         self.failUnless(elem < data[ip])
 148                     if func is self.module.bisect_right and ip > lo:
 149                         self.failUnless(data[ip-1] <= elem)
 150                     self.assertEqual(ip, max(lo, min(hi, expected)))
 151
 152     def test_backcompatibility(self):
 153         self.assertEqual(self.module.bisect, self.module.bisect_right)
 154
 155     def test_keyword_args(self):
 156         data = [10, 20, 30, 40, 50]
 157         self.assertEqual(self.module.bisect_left(a=data, x=25, lo=1, hi=3), 2)
 158         self.assertEqual(self.module.bisect_right(a=data, x=25, lo=1, hi=3), 2)
 159         self.assertEqual(self.module.bisect(a=data, x=25, lo=1, hi=3), 2)
 160         self.module.insort_left(a=data, x=25, lo=1, hi=3)
 161         self.module.insort_right(a=data, x=25, lo=1, hi=3)
 162         self.module.insort(a=data, x=25, lo=1, hi=3)
 163         self.assertEqual(data, [10, 20, 25, 25, 25, 30, 40, 50])
 164
 165 class TestBisectPython(TestBisect):
 166     module = py_bisect
 167
 168 class TestBisectC(TestBisect):
 169     module = c_bisect
 170
 171 #==============================================================================
 172
 173 class TestInsort(unittest.TestCase):
 174     module = None
 175
 176     def test_vsBuiltinSort(self, n=500):
 177         from random import choice
 178         for insorted in (list(), UserList()):
 179             for i in xrange(n):
 180                 digit = choice("0123456789")
 181                 if digit in "02468":
 182                     f = self.module.insort_left
 183                 else:
 184                     f = self.module.insort_right
 185                 f(insorted, digit)
 186         self.assertEqual(sorted(insorted), insorted)
 187
 188     def test_backcompatibility(self):
 189         self.assertEqual(self.module.insort, self.module.insort_right)
 190
 191 class TestInsortPython(TestInsort):
 192     module = py_bisect
 193
 194 class TestInsortC(TestInsort):
 195     module = c_bisect
 196
 197 #==============================================================================
 198
 199
 200 class LenOnly:
 201     "Dummy sequence class defining __len__ but not __getitem__."
 202     def __len__(self):
 203         return 10
 204
 205 class GetOnly:
 206     "Dummy sequence class defining __getitem__ but not __len__."
 207     def __getitem__(self, ndx):
 208         return 10
 209
 210 class CmpErr:
 211     "Dummy element that always raises an error during comparison"
 212     def __cmp__(self, other):
 213         raise ZeroDivisionError
 214
 215 class TestErrorHandling(unittest.TestCase):
 216     module = None
 217
 218     def test_non_sequence(self):
 219         for f in (self.module.bisect_left, self.module.bisect_right,
 220                   self.module.insort_left, self.module.insort_right):
 221             self.assertRaises(TypeError, f, 10, 10)
 222
 223     def test_len_only(self):
 224         for f in (self.module.bisect_left, self.module.bisect_right,
 225                   self.module.insort_left, self.module.insort_right):
 226             self.assertRaises(AttributeError, f, LenOnly(), 10)
 227
 228     def test_get_only(self):
 229         for f in (self.module.bisect_left, self.module.bisect_right,
 230                   self.module.insort_left, self.module.insort_right):
 231             self.assertRaises(AttributeError, f, GetOnly(), 10)
 232
 233     def test_cmp_err(self):
 234         seq = [CmpErr(), CmpErr(), CmpErr()]
 235         for f in (self.module.bisect_left, self.module.bisect_right,
 236                   self.module.insort_left, self.module.insort_right):
 237             self.assertRaises(ZeroDivisionError, f, seq, 10)
 238
 239     def test_arg_parsing(self):
 240         for f in (self.module.bisect_left, self.module.bisect_right,
 241                   self.module.insort_left, self.module.insort_right):
 242             self.assertRaises(TypeError, f, 10)
 243
 244 class TestErrorHandlingPython(TestErrorHandling):
 245     module = py_bisect
 246
 247 class TestErrorHandlingC(TestErrorHandling):
 248     module = c_bisect
 249
 250 #==============================================================================
 251
 252 libreftest = """
 253 Example from the Library Reference:  Doc/library/bisect.rst
 254
 255 The bisect() function is generally useful for categorizing numeric data.
 256 This example uses bisect() to look up a letter grade for an exam total
 257 (say) based on a set of ordered numeric breakpoints: 85 and up is an `A',
 258 75..84 is a `B', etc.
 259
 260     >>> grades = "FEDCBA"
 261     >>> breakpoints = [30, 44, 66, 75, 85]
 262     >>> from bisect import bisect
 263     >>> def grade(total):
 264     ...           return grades[bisect(breakpoints, total)]
 265     ...
 266     >>> grade(66)
 267     'C'
 268     >>> map(grade, [33, 99, 77, 44, 12, 88])
 269     ['E', 'A', 'B', 'D', 'F', 'A']
 270
 271 """
 272
 273 #------------------------------------------------------------------------------
 274
 275 __test__ = {'libreftest' : libreftest}
 276
 277 def test_main(verbose=None):
 278     from test import test_bisect
 279
 280     test_classes = [TestBisectPython, TestBisectC,
 281                     TestInsortPython, TestInsortC,
 282                     TestErrorHandlingPython, TestErrorHandlingC]
 283
 284     test_support.run_unittest(*test_classes)
 285     test_support.run_doctest(test_bisect, verbose)
 286
 287     # verify reference counting
 288     if verbose and hasattr(sys, "gettotalrefcount"):
 289         import gc
 290         counts = [None] * 5
 291         for i in xrange(len(counts)):
 292             test_support.run_unittest(*test_classes)
 293             gc.collect()
 294             counts[i] = sys.gettotalrefcount()
 295         print counts
 296
 297 if __name__ == "__main__":
 298     test_main(verbose=True)