| 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 Range(object):
|
|---|
| 27 | """A trivial xrange()-like object without any integer width limitations."""
|
|---|
| 28 | def __init__(self, start, stop):
|
|---|
| 29 | self.start = start
|
|---|
| 30 | self.stop = stop
|
|---|
| 31 | self.last_insert = None
|
|---|
| 32 |
|
|---|
| 33 | def __len__(self):
|
|---|
| 34 | return self.stop - self.start
|
|---|
| 35 |
|
|---|
| 36 | def __getitem__(self, idx):
|
|---|
| 37 | n = self.stop - self.start
|
|---|
| 38 | if idx < 0:
|
|---|
| 39 | idx += n
|
|---|
| 40 | if idx >= n:
|
|---|
| 41 | raise IndexError(idx)
|
|---|
| 42 | return self.start + idx
|
|---|
| 43 |
|
|---|
| 44 | def insert(self, idx, item):
|
|---|
| 45 | self.last_insert = idx, item
|
|---|
| 46 |
|
|---|
| 47 |
|
|---|
| 48 | class TestBisect(unittest.TestCase):
|
|---|
| 49 | module = None
|
|---|
| 50 |
|
|---|
| 51 | def setUp(self):
|
|---|
| 52 | self.precomputedCases = [
|
|---|
| 53 | (self.module.bisect_right, [], 1, 0),
|
|---|
| 54 | (self.module.bisect_right, [1], 0, 0),
|
|---|
| 55 | (self.module.bisect_right, [1], 1, 1),
|
|---|
| 56 | (self.module.bisect_right, [1], 2, 1),
|
|---|
| 57 | (self.module.bisect_right, [1, 1], 0, 0),
|
|---|
| 58 | (self.module.bisect_right, [1, 1], 1, 2),
|
|---|
| 59 | (self.module.bisect_right, [1, 1], 2, 2),
|
|---|
| 60 | (self.module.bisect_right, [1, 1, 1], 0, 0),
|
|---|
| 61 | (self.module.bisect_right, [1, 1, 1], 1, 3),
|
|---|
| 62 | (self.module.bisect_right, [1, 1, 1], 2, 3),
|
|---|
| 63 | (self.module.bisect_right, [1, 1, 1, 1], 0, 0),
|
|---|
| 64 | (self.module.bisect_right, [1, 1, 1, 1], 1, 4),
|
|---|
| 65 | (self.module.bisect_right, [1, 1, 1, 1], 2, 4),
|
|---|
| 66 | (self.module.bisect_right, [1, 2], 0, 0),
|
|---|
| 67 | (self.module.bisect_right, [1, 2], 1, 1),
|
|---|
| 68 | (self.module.bisect_right, [1, 2], 1.5, 1),
|
|---|
| 69 | (self.module.bisect_right, [1, 2], 2, 2),
|
|---|
| 70 | (self.module.bisect_right, [1, 2], 3, 2),
|
|---|
| 71 | (self.module.bisect_right, [1, 1, 2, 2], 0, 0),
|
|---|
| 72 | (self.module.bisect_right, [1, 1, 2, 2], 1, 2),
|
|---|
| 73 | (self.module.bisect_right, [1, 1, 2, 2], 1.5, 2),
|
|---|
| 74 | (self.module.bisect_right, [1, 1, 2, 2], 2, 4),
|
|---|
| 75 | (self.module.bisect_right, [1, 1, 2, 2], 3, 4),
|
|---|
| 76 | (self.module.bisect_right, [1, 2, 3], 0, 0),
|
|---|
| 77 | (self.module.bisect_right, [1, 2, 3], 1, 1),
|
|---|
| 78 | (self.module.bisect_right, [1, 2, 3], 1.5, 1),
|
|---|
| 79 | (self.module.bisect_right, [1, 2, 3], 2, 2),
|
|---|
| 80 | (self.module.bisect_right, [1, 2, 3], 2.5, 2),
|
|---|
| 81 | (self.module.bisect_right, [1, 2, 3], 3, 3),
|
|---|
| 82 | (self.module.bisect_right, [1, 2, 3], 4, 3),
|
|---|
| 83 | (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 0, 0),
|
|---|
| 84 | (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 1, 1),
|
|---|
| 85 | (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 1.5, 1),
|
|---|
| 86 | (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 2, 3),
|
|---|
| 87 | (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 2.5, 3),
|
|---|
| 88 | (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 3, 6),
|
|---|
| 89 | (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 3.5, 6),
|
|---|
| 90 | (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 4, 10),
|
|---|
| 91 | (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 5, 10),
|
|---|
| 92 |
|
|---|
| 93 | (self.module.bisect_left, [], 1, 0),
|
|---|
| 94 | (self.module.bisect_left, [1], 0, 0),
|
|---|
| 95 | (self.module.bisect_left, [1], 1, 0),
|
|---|
| 96 | (self.module.bisect_left, [1], 2, 1),
|
|---|
| 97 | (self.module.bisect_left, [1, 1], 0, 0),
|
|---|
| 98 | (self.module.bisect_left, [1, 1], 1, 0),
|
|---|
| 99 | (self.module.bisect_left, [1, 1], 2, 2),
|
|---|
| 100 | (self.module.bisect_left, [1, 1, 1], 0, 0),
|
|---|
| 101 | (self.module.bisect_left, [1, 1, 1], 1, 0),
|
|---|
| 102 | (self.module.bisect_left, [1, 1, 1], 2, 3),
|
|---|
| 103 | (self.module.bisect_left, [1, 1, 1, 1], 0, 0),
|
|---|
| 104 | (self.module.bisect_left, [1, 1, 1, 1], 1, 0),
|
|---|
| 105 | (self.module.bisect_left, [1, 1, 1, 1], 2, 4),
|
|---|
| 106 | (self.module.bisect_left, [1, 2], 0, 0),
|
|---|
| 107 | (self.module.bisect_left, [1, 2], 1, 0),
|
|---|
| 108 | (self.module.bisect_left, [1, 2], 1.5, 1),
|
|---|
| 109 | (self.module.bisect_left, [1, 2], 2, 1),
|
|---|
| 110 | (self.module.bisect_left, [1, 2], 3, 2),
|
|---|
| 111 | (self.module.bisect_left, [1, 1, 2, 2], 0, 0),
|
|---|
| 112 | (self.module.bisect_left, [1, 1, 2, 2], 1, 0),
|
|---|
| 113 | (self.module.bisect_left, [1, 1, 2, 2], 1.5, 2),
|
|---|
| 114 | (self.module.bisect_left, [1, 1, 2, 2], 2, 2),
|
|---|
| 115 | (self.module.bisect_left, [1, 1, 2, 2], 3, 4),
|
|---|
| 116 | (self.module.bisect_left, [1, 2, 3], 0, 0),
|
|---|
| 117 | (self.module.bisect_left, [1, 2, 3], 1, 0),
|
|---|
| 118 | (self.module.bisect_left, [1, 2, 3], 1.5, 1),
|
|---|
| 119 | (self.module.bisect_left, [1, 2, 3], 2, 1),
|
|---|
| 120 | (self.module.bisect_left, [1, 2, 3], 2.5, 2),
|
|---|
| 121 | (self.module.bisect_left, [1, 2, 3], 3, 2),
|
|---|
| 122 | (self.module.bisect_left, [1, 2, 3], 4, 3),
|
|---|
| 123 | (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 0, 0),
|
|---|
| 124 | (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 1, 0),
|
|---|
| 125 | (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 1.5, 1),
|
|---|
| 126 | (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 2, 1),
|
|---|
| 127 | (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 2.5, 3),
|
|---|
| 128 | (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 3, 3),
|
|---|
| 129 | (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 3.5, 6),
|
|---|
| 130 | (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 4, 6),
|
|---|
| 131 | (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 5, 10)
|
|---|
| 132 | ]
|
|---|
| 133 |
|
|---|
| 134 | def test_precomputed(self):
|
|---|
| 135 | for func, data, elem, expected in self.precomputedCases:
|
|---|
| 136 | self.assertEqual(func(data, elem), expected)
|
|---|
| 137 | self.assertEqual(func(UserList(data), elem), expected)
|
|---|
| 138 |
|
|---|
| 139 | def test_negative_lo(self):
|
|---|
| 140 | # Issue 3301
|
|---|
| 141 | mod = self.module
|
|---|
| 142 | self.assertRaises(ValueError, mod.bisect_left, [1, 2, 3], 5, -1, 3),
|
|---|
| 143 | self.assertRaises(ValueError, mod.bisect_right, [1, 2, 3], 5, -1, 3),
|
|---|
| 144 | self.assertRaises(ValueError, mod.insort_left, [1, 2, 3], 5, -1, 3),
|
|---|
| 145 | self.assertRaises(ValueError, mod.insort_right, [1, 2, 3], 5, -1, 3),
|
|---|
| 146 |
|
|---|
| 147 | def test_large_range(self):
|
|---|
| 148 | # Issue 13496
|
|---|
| 149 | mod = self.module
|
|---|
| 150 | n = sys.maxsize
|
|---|
| 151 | try:
|
|---|
| 152 | data = xrange(n-1)
|
|---|
| 153 | except OverflowError:
|
|---|
| 154 | self.skipTest("can't create a xrange() object of size `sys.maxsize`")
|
|---|
| 155 | self.assertEqual(mod.bisect_left(data, n-3), n-3)
|
|---|
| 156 | self.assertEqual(mod.bisect_right(data, n-3), n-2)
|
|---|
| 157 | self.assertEqual(mod.bisect_left(data, n-3, n-10, n), n-3)
|
|---|
| 158 | self.assertEqual(mod.bisect_right(data, n-3, n-10, n), n-2)
|
|---|
| 159 |
|
|---|
| 160 | def test_large_pyrange(self):
|
|---|
| 161 | # Same as above, but without C-imposed limits on range() parameters
|
|---|
| 162 | mod = self.module
|
|---|
| 163 | n = sys.maxsize
|
|---|
| 164 | data = Range(0, n-1)
|
|---|
| 165 | self.assertEqual(mod.bisect_left(data, n-3), n-3)
|
|---|
| 166 | self.assertEqual(mod.bisect_right(data, n-3), n-2)
|
|---|
| 167 | self.assertEqual(mod.bisect_left(data, n-3, n-10, n), n-3)
|
|---|
| 168 | self.assertEqual(mod.bisect_right(data, n-3, n-10, n), n-2)
|
|---|
| 169 | x = n - 100
|
|---|
| 170 | mod.insort_left(data, x, x - 50, x + 50)
|
|---|
| 171 | self.assertEqual(data.last_insert, (x, x))
|
|---|
| 172 | x = n - 200
|
|---|
| 173 | mod.insort_right(data, x, x - 50, x + 50)
|
|---|
| 174 | self.assertEqual(data.last_insert, (x + 1, x))
|
|---|
| 175 |
|
|---|
| 176 | def test_random(self, n=25):
|
|---|
| 177 | from random import randrange
|
|---|
| 178 | for i in xrange(n):
|
|---|
| 179 | data = [randrange(0, n, 2) for j in xrange(i)]
|
|---|
| 180 | data.sort()
|
|---|
| 181 | elem = randrange(-1, n+1)
|
|---|
| 182 | ip = self.module.bisect_left(data, elem)
|
|---|
| 183 | if ip < len(data):
|
|---|
| 184 | self.assertTrue(elem <= data[ip])
|
|---|
| 185 | if ip > 0:
|
|---|
| 186 | self.assertTrue(data[ip-1] < elem)
|
|---|
| 187 | ip = self.module.bisect_right(data, elem)
|
|---|
| 188 | if ip < len(data):
|
|---|
| 189 | self.assertTrue(elem < data[ip])
|
|---|
| 190 | if ip > 0:
|
|---|
| 191 | self.assertTrue(data[ip-1] <= elem)
|
|---|
| 192 |
|
|---|
| 193 | def test_optionalSlicing(self):
|
|---|
| 194 | for func, data, elem, expected in self.precomputedCases:
|
|---|
| 195 | for lo in xrange(4):
|
|---|
| 196 | lo = min(len(data), lo)
|
|---|
| 197 | for hi in xrange(3,8):
|
|---|
| 198 | hi = min(len(data), hi)
|
|---|
| 199 | ip = func(data, elem, lo, hi)
|
|---|
| 200 | self.assertTrue(lo <= ip <= hi)
|
|---|
| 201 | if func is self.module.bisect_left and ip < hi:
|
|---|
| 202 | self.assertTrue(elem <= data[ip])
|
|---|
| 203 | if func is self.module.bisect_left and ip > lo:
|
|---|
| 204 | self.assertTrue(data[ip-1] < elem)
|
|---|
| 205 | if func is self.module.bisect_right and ip < hi:
|
|---|
| 206 | self.assertTrue(elem < data[ip])
|
|---|
| 207 | if func is self.module.bisect_right and ip > lo:
|
|---|
| 208 | self.assertTrue(data[ip-1] <= elem)
|
|---|
| 209 | self.assertEqual(ip, max(lo, min(hi, expected)))
|
|---|
| 210 |
|
|---|
| 211 | def test_backcompatibility(self):
|
|---|
| 212 | self.assertEqual(self.module.bisect, self.module.bisect_right)
|
|---|
| 213 |
|
|---|
| 214 | def test_keyword_args(self):
|
|---|
| 215 | data = [10, 20, 30, 40, 50]
|
|---|
| 216 | self.assertEqual(self.module.bisect_left(a=data, x=25, lo=1, hi=3), 2)
|
|---|
| 217 | self.assertEqual(self.module.bisect_right(a=data, x=25, lo=1, hi=3), 2)
|
|---|
| 218 | self.assertEqual(self.module.bisect(a=data, x=25, lo=1, hi=3), 2)
|
|---|
| 219 | self.module.insort_left(a=data, x=25, lo=1, hi=3)
|
|---|
| 220 | self.module.insort_right(a=data, x=25, lo=1, hi=3)
|
|---|
| 221 | self.module.insort(a=data, x=25, lo=1, hi=3)
|
|---|
| 222 | self.assertEqual(data, [10, 20, 25, 25, 25, 30, 40, 50])
|
|---|
| 223 |
|
|---|
| 224 | class TestBisectPython(TestBisect):
|
|---|
| 225 | module = py_bisect
|
|---|
| 226 |
|
|---|
| 227 | class TestBisectC(TestBisect):
|
|---|
| 228 | module = c_bisect
|
|---|
| 229 |
|
|---|
| 230 | #==============================================================================
|
|---|
| 231 |
|
|---|
| 232 | class TestInsort(unittest.TestCase):
|
|---|
| 233 | module = None
|
|---|
| 234 |
|
|---|
| 235 | def test_vsBuiltinSort(self, n=500):
|
|---|
| 236 | from random import choice
|
|---|
| 237 | for insorted in (list(), UserList()):
|
|---|
| 238 | for i in xrange(n):
|
|---|
| 239 | digit = choice("0123456789")
|
|---|
| 240 | if digit in "02468":
|
|---|
| 241 | f = self.module.insort_left
|
|---|
| 242 | else:
|
|---|
| 243 | f = self.module.insort_right
|
|---|
| 244 | f(insorted, digit)
|
|---|
| 245 | self.assertEqual(sorted(insorted), insorted)
|
|---|
| 246 |
|
|---|
| 247 | def test_backcompatibility(self):
|
|---|
| 248 | self.assertEqual(self.module.insort, self.module.insort_right)
|
|---|
| 249 |
|
|---|
| 250 | def test_listDerived(self):
|
|---|
| 251 | class List(list):
|
|---|
| 252 | data = []
|
|---|
| 253 | def insert(self, index, item):
|
|---|
| 254 | self.data.insert(index, item)
|
|---|
| 255 |
|
|---|
| 256 | lst = List()
|
|---|
| 257 | self.module.insort_left(lst, 10)
|
|---|
| 258 | self.module.insort_right(lst, 5)
|
|---|
| 259 | self.assertEqual([5, 10], lst.data)
|
|---|
| 260 |
|
|---|
| 261 | class TestInsortPython(TestInsort):
|
|---|
| 262 | module = py_bisect
|
|---|
| 263 |
|
|---|
| 264 | class TestInsortC(TestInsort):
|
|---|
| 265 | module = c_bisect
|
|---|
| 266 |
|
|---|
| 267 | #==============================================================================
|
|---|
| 268 |
|
|---|
| 269 |
|
|---|
| 270 | class LenOnly:
|
|---|
| 271 | "Dummy sequence class defining __len__ but not __getitem__."
|
|---|
| 272 | def __len__(self):
|
|---|
| 273 | return 10
|
|---|
| 274 |
|
|---|
| 275 | class GetOnly:
|
|---|
| 276 | "Dummy sequence class defining __getitem__ but not __len__."
|
|---|
| 277 | def __getitem__(self, ndx):
|
|---|
| 278 | return 10
|
|---|
| 279 |
|
|---|
| 280 | class CmpErr:
|
|---|
| 281 | "Dummy element that always raises an error during comparison"
|
|---|
| 282 | def __cmp__(self, other):
|
|---|
| 283 | raise ZeroDivisionError
|
|---|
| 284 |
|
|---|
| 285 | class TestErrorHandling(unittest.TestCase):
|
|---|
| 286 | module = None
|
|---|
| 287 |
|
|---|
| 288 | def test_non_sequence(self):
|
|---|
| 289 | for f in (self.module.bisect_left, self.module.bisect_right,
|
|---|
| 290 | self.module.insort_left, self.module.insort_right):
|
|---|
| 291 | self.assertRaises(TypeError, f, 10, 10)
|
|---|
| 292 |
|
|---|
| 293 | def test_len_only(self):
|
|---|
| 294 | for f in (self.module.bisect_left, self.module.bisect_right,
|
|---|
| 295 | self.module.insort_left, self.module.insort_right):
|
|---|
| 296 | self.assertRaises(AttributeError, f, LenOnly(), 10)
|
|---|
| 297 |
|
|---|
| 298 | def test_get_only(self):
|
|---|
| 299 | for f in (self.module.bisect_left, self.module.bisect_right,
|
|---|
| 300 | self.module.insort_left, self.module.insort_right):
|
|---|
| 301 | self.assertRaises(AttributeError, f, GetOnly(), 10)
|
|---|
| 302 |
|
|---|
| 303 | def test_cmp_err(self):
|
|---|
| 304 | seq = [CmpErr(), CmpErr(), CmpErr()]
|
|---|
| 305 | for f in (self.module.bisect_left, self.module.bisect_right,
|
|---|
| 306 | self.module.insort_left, self.module.insort_right):
|
|---|
| 307 | self.assertRaises(ZeroDivisionError, f, seq, 10)
|
|---|
| 308 |
|
|---|
| 309 | def test_arg_parsing(self):
|
|---|
| 310 | for f in (self.module.bisect_left, self.module.bisect_right,
|
|---|
| 311 | self.module.insort_left, self.module.insort_right):
|
|---|
| 312 | self.assertRaises(TypeError, f, 10)
|
|---|
| 313 |
|
|---|
| 314 | class TestErrorHandlingPython(TestErrorHandling):
|
|---|
| 315 | module = py_bisect
|
|---|
| 316 |
|
|---|
| 317 | class TestErrorHandlingC(TestErrorHandling):
|
|---|
| 318 | module = c_bisect
|
|---|
| 319 |
|
|---|
| 320 | #==============================================================================
|
|---|
| 321 |
|
|---|
| 322 | libreftest = """
|
|---|
| 323 | Example from the Library Reference: Doc/library/bisect.rst
|
|---|
| 324 |
|
|---|
| 325 | The bisect() function is generally useful for categorizing numeric data.
|
|---|
| 326 | This example uses bisect() to look up a letter grade for an exam total
|
|---|
| 327 | (say) based on a set of ordered numeric breakpoints: 85 and up is an `A',
|
|---|
| 328 | 75..84 is a `B', etc.
|
|---|
| 329 |
|
|---|
| 330 | >>> grades = "FEDCBA"
|
|---|
| 331 | >>> breakpoints = [30, 44, 66, 75, 85]
|
|---|
| 332 | >>> from bisect import bisect
|
|---|
| 333 | >>> def grade(total):
|
|---|
| 334 | ... return grades[bisect(breakpoints, total)]
|
|---|
| 335 | ...
|
|---|
| 336 | >>> grade(66)
|
|---|
| 337 | 'C'
|
|---|
| 338 | >>> map(grade, [33, 99, 77, 44, 12, 88])
|
|---|
| 339 | ['E', 'A', 'B', 'D', 'F', 'A']
|
|---|
| 340 |
|
|---|
| 341 | """
|
|---|
| 342 |
|
|---|
| 343 | #------------------------------------------------------------------------------
|
|---|
| 344 |
|
|---|
| 345 | __test__ = {'libreftest' : libreftest}
|
|---|
| 346 |
|
|---|
| 347 | def test_main(verbose=None):
|
|---|
| 348 | from test import test_bisect
|
|---|
| 349 |
|
|---|
| 350 | test_classes = [TestBisectPython, TestBisectC,
|
|---|
| 351 | TestInsortPython, TestInsortC,
|
|---|
| 352 | TestErrorHandlingPython, TestErrorHandlingC]
|
|---|
| 353 |
|
|---|
| 354 | test_support.run_unittest(*test_classes)
|
|---|
| 355 | test_support.run_doctest(test_bisect, verbose)
|
|---|
| 356 |
|
|---|
| 357 | # verify reference counting
|
|---|
| 358 | if verbose and hasattr(sys, "gettotalrefcount"):
|
|---|
| 359 | import gc
|
|---|
| 360 | counts = [None] * 5
|
|---|
| 361 | for i in xrange(len(counts)):
|
|---|
| 362 | test_support.run_unittest(*test_classes)
|
|---|
| 363 | gc.collect()
|
|---|
| 364 | counts[i] = sys.gettotalrefcount()
|
|---|
| 365 | print counts
|
|---|
| 366 |
|
|---|
| 367 | if __name__ == "__main__":
|
|---|
| 368 | test_main(verbose=True)
|
|---|
