Lib/test/test_bisect.py

   1 import unittest
   2 from test import test_support
   3 from bisect import bisect_right, bisect_left, insort_left, insort_right, insort, bisect
   4
   5 class TestBisect(unittest.TestCase):
   6
   7     precomputedCases = [
   8         (bisect_right, [], 1, 0),
   9         (bisect_right, [1], 0, 0),
  10         (bisect_right, [1], 1, 1),
  11         (bisect_right, [1], 2, 1),
  12         (bisect_right, [1, 1], 0, 0),
  13         (bisect_right, [1, 1], 1, 2),
  14         (bisect_right, [1, 1], 2, 2),
  15         (bisect_right, [1, 1, 1], 0, 0),
  16         (bisect_right, [1, 1, 1], 1, 3),
  17         (bisect_right, [1, 1, 1], 2, 3),
  18         (bisect_right, [1, 1, 1, 1], 0, 0),
  19         (bisect_right, [1, 1, 1, 1], 1, 4),
  20         (bisect_right, [1, 1, 1, 1], 2, 4),
  21         (bisect_right, [1, 2], 0, 0),
  22         (bisect_right, [1, 2], 1, 1),
  23         (bisect_right, [1, 2], 1.5, 1),
  24         (bisect_right, [1, 2], 2, 2),
  25         (bisect_right, [1, 2], 3, 2),
  26         (bisect_right, [1, 1, 2, 2], 0, 0),
  27         (bisect_right, [1, 1, 2, 2], 1, 2),
  28         (bisect_right, [1, 1, 2, 2], 1.5, 2),
  29         (bisect_right, [1, 1, 2, 2], 2, 4),
  30         (bisect_right, [1, 1, 2, 2], 3, 4),
  31         (bisect_right, [1, 2, 3], 0, 0),
  32         (bisect_right, [1, 2, 3], 1, 1),
  33         (bisect_right, [1, 2, 3], 1.5, 1),
  34         (bisect_right, [1, 2, 3], 2, 2),
  35         (bisect_right, [1, 2, 3], 2.5, 2),
  36         (bisect_right, [1, 2, 3], 3, 3),
  37         (bisect_right, [1, 2, 3], 4, 3),
  38         (bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 0, 0),
  39         (bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 1, 1),
  40         (bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 1.5, 1),
  41         (bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 2, 3),
  42         (bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 2.5, 3),
  43         (bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 3, 6),
  44         (bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 3.5, 6),
  45         (bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 4, 10),
  46         (bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 5, 10),
  47
  48         (bisect_left, [], 1, 0),
  49         (bisect_left, [1], 0, 0),
  50         (bisect_left, [1], 1, 0),
  51         (bisect_left, [1], 2, 1),
  52         (bisect_left, [1, 1], 0, 0),
  53         (bisect_left, [1, 1], 1, 0),
  54         (bisect_left, [1, 1], 2, 2),
  55         (bisect_left, [1, 1, 1], 0, 0),
  56         (bisect_left, [1, 1, 1], 1, 0),
  57         (bisect_left, [1, 1, 1], 2, 3),
  58         (bisect_left, [1, 1, 1, 1], 0, 0),
  59         (bisect_left, [1, 1, 1, 1], 1, 0),
  60         (bisect_left, [1, 1, 1, 1], 2, 4),
  61         (bisect_left, [1, 2], 0, 0),
  62         (bisect_left, [1, 2], 1, 0),
  63         (bisect_left, [1, 2], 1.5, 1),
  64         (bisect_left, [1, 2], 2, 1),
  65         (bisect_left, [1, 2], 3, 2),
  66         (bisect_left, [1, 1, 2, 2], 0, 0),
  67         (bisect_left, [1, 1, 2, 2], 1, 0),
  68         (bisect_left, [1, 1, 2, 2], 1.5, 2),
  69         (bisect_left, [1, 1, 2, 2], 2, 2),
  70         (bisect_left, [1, 1, 2, 2], 3, 4),
  71         (bisect_left, [1, 2, 3], 0, 0),
  72         (bisect_left, [1, 2, 3], 1, 0),
  73         (bisect_left, [1, 2, 3], 1.5, 1),
  74         (bisect_left, [1, 2, 3], 2, 1),
  75         (bisect_left, [1, 2, 3], 2.5, 2),
  76         (bisect_left, [1, 2, 3], 3, 2),
  77         (bisect_left, [1, 2, 3], 4, 3),
  78         (bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 0, 0),
  79         (bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 1, 0),
  80         (bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 1.5, 1),
  81         (bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 2, 1),
  82         (bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 2.5, 3),
  83         (bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 3, 3),
  84         (bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 3.5, 6),
  85         (bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 4, 6),
  86         (bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 5, 10)
  87     ]
  88
  89     def test_precomputed(self):
  90         for func, data, elem, expected in self.precomputedCases:
  91             self.assertEqual(func(data, elem), expected)
  92
  93     def test_random(self, n=25):
  94         from random import randrange
  95         for i in xrange(n):
  96             data = [randrange(0, n, 2) for j in xrange(i)]
  97             data.sort()
  98             elem = randrange(-1, n+1)
  99             ip = bisect_left(data, elem)
 100             if ip < len(data):
 101                 self.failUnless(elem <= data[ip])
 102             if ip > 0:
 103                 self.failUnless(data[ip-1] < elem)
 104             ip = bisect_right(data, elem)
 105             if ip < len(data):
 106                 self.failUnless(elem < data[ip])
 107             if ip > 0:
 108                 self.failUnless(data[ip-1] <= elem)
 109
 110     def test_optionalSlicing(self):
 111         for func, data, elem, expected in self.precomputedCases:
 112             for lo in xrange(4):
 113                 lo = min(len(data), lo)
 114                 for hi in xrange(3,8):
 115                     hi = min(len(data), hi)
 116                     ip = func(data, elem, lo, hi)
 117                     self.failUnless(lo <= ip <= hi)
 118                     if func is bisect_left and ip < hi:
 119                         self.failUnless(elem <= data[ip])
 120                     if func is bisect_left and ip > lo:
 121                         self.failUnless(data[ip-1] < elem)
 122                     if func is bisect_right and ip < hi:
 123                         self.failUnless(elem < data[ip])
 124                     if func is bisect_right and ip > lo:
 125                         self.failUnless(data[ip-1] <= elem)
 126                     self.assertEqual(ip, max(lo, min(hi, expected)))
 127
 128     def test_backcompatibility(self):
 129         self.assertEqual(bisect, bisect_right)
 130
 131 #==============================================================================
 132
 133 class TestInsort(unittest.TestCase):
 134
 135     def test_vsListSort(self, n=500):
 136         from random import choice
 137         digits = "0123456789"
 138         raw = []
 139         insorted = []
 140         for i in range(n):
 141             digit = choice(digits)
 142             raw.append(digit)
 143             if digit in "02468":
 144                 f = insort_left
 145             else:
 146                 f = insort_right
 147             f(insorted, digit)
 148         sorted = raw[:]
 149         sorted.sort()
 150         self.assertEqual(sorted, insorted)
 151
 152     def test_backcompatibility(self):
 153         self.assertEqual(insort, insort_right)
 154
 155 #==============================================================================
 156
 157 libreftest = """
 158 Example from the Library Reference:  Doc/lib/libbisect.tex
 159
 160 The bisect() function is generally useful for categorizing numeric data.
 161 This example uses bisect() to look up a letter grade for an exam total
 162 (say) based on a set of ordered numeric breakpoints: 85 and up is an `A',
 163 75..84 is a `B', etc.
 164
 165     >>> grades = "FEDCBA"
 166     >>> breakpoints = [30, 44, 66, 75, 85]
 167     >>> from bisect import bisect
 168     >>> def grade(total):
 169     ...           return grades[bisect(breakpoints, total)]
 170     ...
 171     >>> grade(66)
 172     'C'
 173     >>> map(grade, [33, 99, 77, 44, 12, 88])
 174     ['E', 'A', 'B', 'D', 'F', 'A']
 175
 176 The bisect module can be used with the Queue module to implement
 177 a priority queue (example courtesy of Fredrik Lundh):
 178
 179 >>> import Queue, bisect
 180 >>> class PriorityQueue(Queue.Queue):
 181 ...     def _put(self, item):
 182 ...         bisect.insort(self.queue, item)
 183 ...
 184 >>> queue = PriorityQueue(0)
 185 >>> queue.put((2, "second"))
 186 >>> queue.put((1, "first"))
 187 >>> queue.put((3, "third"))
 188 >>> queue.get()
 189 (1, 'first')
 190 >>> queue.get()
 191 (2, 'second')
 192
 193 """
 194
 195 #==============================================================================
 196
 197 def makeAllTests():
 198     suite = unittest.TestSuite()
 199     for klass in (TestBisect,
 200                   TestInsort
 201                   ):
 202         suite.addTest(unittest.makeSuite(klass))
 203     return suite
 204
 205 #------------------------------------------------------------------------------
 206
 207 __test__ = {'libreftest' : libreftest}
 208
 209 def test_main(verbose=None):
 210     from test import test_bisect
 211     suite = makeAllTests()
 212     test_support.run_suite(suite)
 213     test_support.run_doctest(test_bisect, verbose)
 214
 215 if __name__ == "__main__":
 216     test_main(verbose=True)
 217