test_bisect.py 12.7 KB
Newer Older
1
import sys
2 3
import unittest
from test import test_support
4
from UserList import UserList
5

6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
# We do a bit of trickery here to be able to test both the C implementation
# and the Python implementation of the module.

# Make it impossible to import the C implementation anymore.
sys.modules['_bisect'] = 0
# We must also handle the case that bisect was imported before.
if 'bisect' in sys.modules:
    del sys.modules['bisect']

# Now we can import the module and get the pure Python implementation.
import bisect as py_bisect

# Restore everything to normal.
del sys.modules['_bisect']
del sys.modules['bisect']
21

22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110
# This is now the module with the C implementation.
import bisect as c_bisect


class TestBisect(unittest.TestCase):
    module = None

    def setUp(self):
        self.precomputedCases = [
            (self.module.bisect_right, [], 1, 0),
            (self.module.bisect_right, [1], 0, 0),
            (self.module.bisect_right, [1], 1, 1),
            (self.module.bisect_right, [1], 2, 1),
            (self.module.bisect_right, [1, 1], 0, 0),
            (self.module.bisect_right, [1, 1], 1, 2),
            (self.module.bisect_right, [1, 1], 2, 2),
            (self.module.bisect_right, [1, 1, 1], 0, 0),
            (self.module.bisect_right, [1, 1, 1], 1, 3),
            (self.module.bisect_right, [1, 1, 1], 2, 3),
            (self.module.bisect_right, [1, 1, 1, 1], 0, 0),
            (self.module.bisect_right, [1, 1, 1, 1], 1, 4),
            (self.module.bisect_right, [1, 1, 1, 1], 2, 4),
            (self.module.bisect_right, [1, 2], 0, 0),
            (self.module.bisect_right, [1, 2], 1, 1),
            (self.module.bisect_right, [1, 2], 1.5, 1),
            (self.module.bisect_right, [1, 2], 2, 2),
            (self.module.bisect_right, [1, 2], 3, 2),
            (self.module.bisect_right, [1, 1, 2, 2], 0, 0),
            (self.module.bisect_right, [1, 1, 2, 2], 1, 2),
            (self.module.bisect_right, [1, 1, 2, 2], 1.5, 2),
            (self.module.bisect_right, [1, 1, 2, 2], 2, 4),
            (self.module.bisect_right, [1, 1, 2, 2], 3, 4),
            (self.module.bisect_right, [1, 2, 3], 0, 0),
            (self.module.bisect_right, [1, 2, 3], 1, 1),
            (self.module.bisect_right, [1, 2, 3], 1.5, 1),
            (self.module.bisect_right, [1, 2, 3], 2, 2),
            (self.module.bisect_right, [1, 2, 3], 2.5, 2),
            (self.module.bisect_right, [1, 2, 3], 3, 3),
            (self.module.bisect_right, [1, 2, 3], 4, 3),
            (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 0, 0),
            (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 1, 1),
            (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 1.5, 1),
            (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 2, 3),
            (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 2.5, 3),
            (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 3, 6),
            (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 3.5, 6),
            (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 4, 10),
            (self.module.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 5, 10),

            (self.module.bisect_left, [], 1, 0),
            (self.module.bisect_left, [1], 0, 0),
            (self.module.bisect_left, [1], 1, 0),
            (self.module.bisect_left, [1], 2, 1),
            (self.module.bisect_left, [1, 1], 0, 0),
            (self.module.bisect_left, [1, 1], 1, 0),
            (self.module.bisect_left, [1, 1], 2, 2),
            (self.module.bisect_left, [1, 1, 1], 0, 0),
            (self.module.bisect_left, [1, 1, 1], 1, 0),
            (self.module.bisect_left, [1, 1, 1], 2, 3),
            (self.module.bisect_left, [1, 1, 1, 1], 0, 0),
            (self.module.bisect_left, [1, 1, 1, 1], 1, 0),
            (self.module.bisect_left, [1, 1, 1, 1], 2, 4),
            (self.module.bisect_left, [1, 2], 0, 0),
            (self.module.bisect_left, [1, 2], 1, 0),
            (self.module.bisect_left, [1, 2], 1.5, 1),
            (self.module.bisect_left, [1, 2], 2, 1),
            (self.module.bisect_left, [1, 2], 3, 2),
            (self.module.bisect_left, [1, 1, 2, 2], 0, 0),
            (self.module.bisect_left, [1, 1, 2, 2], 1, 0),
            (self.module.bisect_left, [1, 1, 2, 2], 1.5, 2),
            (self.module.bisect_left, [1, 1, 2, 2], 2, 2),
            (self.module.bisect_left, [1, 1, 2, 2], 3, 4),
            (self.module.bisect_left, [1, 2, 3], 0, 0),
            (self.module.bisect_left, [1, 2, 3], 1, 0),
            (self.module.bisect_left, [1, 2, 3], 1.5, 1),
            (self.module.bisect_left, [1, 2, 3], 2, 1),
            (self.module.bisect_left, [1, 2, 3], 2.5, 2),
            (self.module.bisect_left, [1, 2, 3], 3, 2),
            (self.module.bisect_left, [1, 2, 3], 4, 3),
            (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 0, 0),
            (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 1, 0),
            (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 1.5, 1),
            (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 2, 1),
            (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 2.5, 3),
            (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 3, 3),
            (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 3.5, 6),
            (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 4, 6),
            (self.module.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 5, 10)
        ]
111 112

    def test_precomputed(self):
113 114
        for func, data, elem, expected in self.precomputedCases:
            self.assertEqual(func(data, elem), expected)
115
            self.assertEqual(func(UserList(data), elem), expected)
116

117 118 119 120 121 122 123 124
    def test_negative_lo(self):
        # Issue 3301
        mod = self.module
        self.assertRaises(ValueError, mod.bisect_left, [1, 2, 3], 5, -1, 3),
        self.assertRaises(ValueError, mod.bisect_right, [1, 2, 3], 5, -1, 3),
        self.assertRaises(ValueError, mod.insort_left, [1, 2, 3], 5, -1, 3),
        self.assertRaises(ValueError, mod.insort_right, [1, 2, 3], 5, -1, 3),

125
    def test_random(self, n=25):
126 127 128 129
        from random import randrange
        for i in xrange(n):
            data = [randrange(0, n, 2) for j in xrange(i)]
            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 144 145 146 147 148
        for func, data, elem, expected in self.precomputedCases:
            for lo in xrange(4):
                lo = min(len(data), lo)
                for hi in xrange(3,8):
                    hi = min(len(data), hi)
                    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 164
    def test_keyword_args(self):
        data = [10, 20, 30, 40, 50]
165 166 167 168 169 170
        self.assertEqual(self.module.bisect_left(a=data, x=25, lo=1, hi=3), 2)
        self.assertEqual(self.module.bisect_right(a=data, x=25, lo=1, hi=3), 2)
        self.assertEqual(self.module.bisect(a=data, x=25, lo=1, hi=3), 2)
        self.module.insort_left(a=data, x=25, lo=1, hi=3)
        self.module.insort_right(a=data, x=25, lo=1, hi=3)
        self.module.insort(a=data, x=25, lo=1, hi=3)
171 172
        self.assertEqual(data, [10, 20, 25, 25, 25, 30, 40, 50])

173 174 175 176 177 178
class TestBisectPython(TestBisect):
    module = py_bisect

class TestBisectC(TestBisect):
    module = c_bisect

179 180 181
#==============================================================================

class TestInsort(unittest.TestCase):
182
    module = None
183

184
    def test_vsBuiltinSort(self, n=500):
185
        from random import choice
186 187 188 189
        for insorted in (list(), UserList()):
            for i in xrange(n):
                digit = choice("0123456789")
                if digit in "02468":
190
                    f = self.module.insort_left
191
                else:
192
                    f = self.module.insort_right
193 194
                f(insorted, digit)
        self.assertEqual(sorted(insorted), insorted)
195

196
    def test_backcompatibility(self):
197 198
        self.assertEqual(self.module.insort, self.module.insort_right)

199 200 201 202 203 204 205 206 207 208 209
    def test_listDerived(self):
        class List(list):
            data = []
            def insert(self, index, item):
                self.data.insert(index, item)

        lst = List()
        self.module.insort_left(lst, 10)
        self.module.insort_right(lst, 5)
        self.assertEqual([5, 10], lst.data)

210 211 212 213 214
class TestInsortPython(TestInsort):
    module = py_bisect

class TestInsortC(TestInsort):
    module = c_bisect
215

216
#==============================================================================
217

218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234

class LenOnly:
    "Dummy sequence class defining __len__ but not __getitem__."
    def __len__(self):
        return 10

class GetOnly:
    "Dummy sequence class defining __getitem__ but not __len__."
    def __getitem__(self, ndx):
        return 10

class CmpErr:
    "Dummy element that always raises an error during comparison"
    def __cmp__(self, other):
        raise ZeroDivisionError

class TestErrorHandling(unittest.TestCase):
235
    module = None
236 237

    def test_non_sequence(self):
238 239
        for f in (self.module.bisect_left, self.module.bisect_right,
                  self.module.insort_left, self.module.insort_right):
240 241 242
            self.assertRaises(TypeError, f, 10, 10)

    def test_len_only(self):
243 244
        for f in (self.module.bisect_left, self.module.bisect_right,
                  self.module.insort_left, self.module.insort_right):
245 246 247
            self.assertRaises(AttributeError, f, LenOnly(), 10)

    def test_get_only(self):
248 249
        for f in (self.module.bisect_left, self.module.bisect_right,
                  self.module.insort_left, self.module.insort_right):
250 251
            self.assertRaises(AttributeError, f, GetOnly(), 10)

252
    def test_cmp_err(self):
253
        seq = [CmpErr(), CmpErr(), CmpErr()]
254 255
        for f in (self.module.bisect_left, self.module.bisect_right,
                  self.module.insort_left, self.module.insort_right):
256 257 258
            self.assertRaises(ZeroDivisionError, f, seq, 10)

    def test_arg_parsing(self):
259 260
        for f in (self.module.bisect_left, self.module.bisect_right,
                  self.module.insort_left, self.module.insort_right):
261 262
            self.assertRaises(TypeError, f, 10)

263 264 265 266 267 268
class TestErrorHandlingPython(TestErrorHandling):
    module = py_bisect

class TestErrorHandlingC(TestErrorHandling):
    module = c_bisect

269 270
#==============================================================================

271
libreftest = """
272
Example from the Library Reference:  Doc/library/bisect.rst
273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291

The bisect() function is generally useful for categorizing numeric data.
This example uses bisect() to look up a letter grade for an exam total
(say) based on a set of ordered numeric breakpoints: 85 and up is an `A',
75..84 is a `B', etc.

    >>> grades = "FEDCBA"
    >>> breakpoints = [30, 44, 66, 75, 85]
    >>> from bisect import bisect
    >>> def grade(total):
    ...           return grades[bisect(breakpoints, total)]
    ...
    >>> grade(66)
    'C'
    >>> map(grade, [33, 99, 77, 44, 12, 88])
    ['E', 'A', 'B', 'D', 'F', 'A']

"""

292
#------------------------------------------------------------------------------
293

294 295
__test__ = {'libreftest' : libreftest}

296 297
def test_main(verbose=None):
    from test import test_bisect
298

299 300 301
    test_classes = [TestBisectPython, TestBisectC,
                    TestInsortPython, TestInsortC,
                    TestErrorHandlingPython, TestErrorHandlingC]
302 303

    test_support.run_unittest(*test_classes)
304
    test_support.run_doctest(test_bisect, verbose)
305

306 307 308 309 310 311 312 313 314 315
    # verify reference counting
    if verbose and hasattr(sys, "gettotalrefcount"):
        import gc
        counts = [None] * 5
        for i in xrange(len(counts)):
            test_support.run_unittest(*test_classes)
            gc.collect()
            counts[i] = sys.gettotalrefcount()
        print counts

316 317
if __name__ == "__main__":
    test_main(verbose=True)