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_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.assertTrue(elem <= data[ip])
 134             if ip > 0:
 135                 self.assertTrue(data[ip-1] < elem)
 136             ip = self.module.bisect_right(data, elem)
 137             if ip < len(data):
 138                 self.assertTrue(elem < data[ip])
 139             if ip > 0:
 140                 self.assertTrue(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.assertTrue(lo <= ip <= hi)
 150                     if func is self.module.bisect_left and ip < hi:
 151                         self.assertTrue(elem <= data[ip])
 152                     if func is self.module.bisect_left and ip > lo:
 153                         self.assertTrue(data[ip-1] < elem)
 154                     if func is self.module.bisect_right and ip < hi:
 155                         self.assertTrue(elem < data[ip])
 156                     if func is self.module.bisect_right and ip > lo:
 157                         self.assertTrue(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)