Lib/test/test_bisect.py

   1 from test.test_support import TestFailed
   2
   3 import bisect
   4 import sys
   5
   6 nerrors = 0
   7
   8 def check_bisect(func, list, elt, expected):
   9     global nerrors
  10     got = func(list, elt)
  11     if got != expected:
  12         print >> sys.stderr, \
  13             "expected %s(%s, %s) -> %s, but got %s" % (func.__name__,
  14                                                        list,
  15                                                        elt,
  16                                                        expected,
  17                                                        got)
  18         nerrors += 1
  19
  20 # XXX optional slice arguments need tests.
  21
  22 check_bisect(bisect.bisect_right, [], 1, 0)
  23 check_bisect(bisect.bisect_right, [1], 0, 0)
  24 check_bisect(bisect.bisect_right, [1], 1, 1)
  25 check_bisect(bisect.bisect_right, [1], 2, 1)
  26 check_bisect(bisect.bisect_right, [1, 1], 0, 0)
  27 check_bisect(bisect.bisect_right, [1, 1], 1, 2)
  28 check_bisect(bisect.bisect_right, [1, 1], 2, 2)
  29 check_bisect(bisect.bisect_right, [1, 1, 1], 0, 0)
  30 check_bisect(bisect.bisect_right, [1, 1, 1], 1, 3)
  31 check_bisect(bisect.bisect_right, [1, 1, 1], 2, 3)
  32 check_bisect(bisect.bisect_right, [1, 1, 1, 1], 0, 0)
  33 check_bisect(bisect.bisect_right, [1, 1, 1, 1], 1, 4)
  34 check_bisect(bisect.bisect_right, [1, 1, 1, 1], 2, 4)
  35 check_bisect(bisect.bisect_right, [1, 2], 0, 0)
  36 check_bisect(bisect.bisect_right, [1, 2], 1, 1)
  37 check_bisect(bisect.bisect_right, [1, 2], 1.5, 1)
  38 check_bisect(bisect.bisect_right, [1, 2], 2, 2)
  39 check_bisect(bisect.bisect_right, [1, 2], 3, 2)
  40 check_bisect(bisect.bisect_right, [1, 1, 2, 2], 0, 0)
  41 check_bisect(bisect.bisect_right, [1, 1, 2, 2], 1, 2)
  42 check_bisect(bisect.bisect_right, [1, 1, 2, 2], 1.5, 2)
  43 check_bisect(bisect.bisect_right, [1, 1, 2, 2], 2, 4)
  44 check_bisect(bisect.bisect_right, [1, 1, 2, 2], 3, 4)
  45 check_bisect(bisect.bisect_right, [1, 2, 3], 0, 0)
  46 check_bisect(bisect.bisect_right, [1, 2, 3], 1, 1)
  47 check_bisect(bisect.bisect_right, [1, 2, 3], 1.5, 1)
  48 check_bisect(bisect.bisect_right, [1, 2, 3], 2, 2)
  49 check_bisect(bisect.bisect_right, [1, 2, 3], 2.5, 2)
  50 check_bisect(bisect.bisect_right, [1, 2, 3], 3, 3)
  51 check_bisect(bisect.bisect_right, [1, 2, 3], 4, 3)
  52 check_bisect(bisect.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 0, 0)
  53 check_bisect(bisect.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 1, 1)
  54 check_bisect(bisect.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 1.5, 1)
  55 check_bisect(bisect.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 2, 3)
  56 check_bisect(bisect.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 2.5, 3)
  57 check_bisect(bisect.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 3, 6)
  58 check_bisect(bisect.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 3.5, 6)
  59 check_bisect(bisect.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 4, 10)
  60 check_bisect(bisect.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 5, 10)
  61
  62 check_bisect(bisect.bisect_left, [], 1, 0)
  63 check_bisect(bisect.bisect_left, [1], 0, 0)
  64 check_bisect(bisect.bisect_left, [1], 1, 0)
  65 check_bisect(bisect.bisect_left, [1], 2, 1)
  66 check_bisect(bisect.bisect_left, [1, 1], 0, 0)
  67 check_bisect(bisect.bisect_left, [1, 1], 1, 0)
  68 check_bisect(bisect.bisect_left, [1, 1], 2, 2)
  69 check_bisect(bisect.bisect_left, [1, 1, 1], 0, 0)
  70 check_bisect(bisect.bisect_left, [1, 1, 1], 1, 0)
  71 check_bisect(bisect.bisect_left, [1, 1, 1], 2, 3)
  72 check_bisect(bisect.bisect_left, [1, 1, 1, 1], 0, 0)
  73 check_bisect(bisect.bisect_left, [1, 1, 1, 1], 1, 0)
  74 check_bisect(bisect.bisect_left, [1, 1, 1, 1], 2, 4)
  75 check_bisect(bisect.bisect_left, [1, 2], 0, 0)
  76 check_bisect(bisect.bisect_left, [1, 2], 1, 0)
  77 check_bisect(bisect.bisect_left, [1, 2], 1.5, 1)
  78 check_bisect(bisect.bisect_left, [1, 2], 2, 1)
  79 check_bisect(bisect.bisect_left, [1, 2], 3, 2)
  80 check_bisect(bisect.bisect_left, [1, 1, 2, 2], 0, 0)
  81 check_bisect(bisect.bisect_left, [1, 1, 2, 2], 1, 0)
  82 check_bisect(bisect.bisect_left, [1, 1, 2, 2], 1.5, 2)
  83 check_bisect(bisect.bisect_left, [1, 1, 2, 2], 2, 2)
  84 check_bisect(bisect.bisect_left, [1, 1, 2, 2], 3, 4)
  85 check_bisect(bisect.bisect_left, [1, 2, 3], 0, 0)
  86 check_bisect(bisect.bisect_left, [1, 2, 3], 1, 0)
  87 check_bisect(bisect.bisect_left, [1, 2, 3], 1.5, 1)
  88 check_bisect(bisect.bisect_left, [1, 2, 3], 2, 1)
  89 check_bisect(bisect.bisect_left, [1, 2, 3], 2.5, 2)
  90 check_bisect(bisect.bisect_left, [1, 2, 3], 3, 2)
  91 check_bisect(bisect.bisect_left, [1, 2, 3], 4, 3)
  92 check_bisect(bisect.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 0, 0)
  93 check_bisect(bisect.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 1, 0)
  94 check_bisect(bisect.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 1.5, 1)
  95 check_bisect(bisect.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 2, 1)
  96 check_bisect(bisect.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 2.5, 3)
  97 check_bisect(bisect.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 3, 3)
  98 check_bisect(bisect.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 3.5, 6)
  99 check_bisect(bisect.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 4, 6)
 100 check_bisect(bisect.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 5, 10)
 101
 102 def check_insort(n):
 103     global nerrors
 104     from random import choice
 105     import sys
 106     digits = "0123456789"
 107     raw = []
 108     insorted = []
 109     for i in range(n):
 110         digit = choice(digits)
 111         raw.append(digit)
 112         if digit in "02468":
 113             f = bisect.insort_left
 114         else:
 115             f = bisect.insort_right
 116         f(insorted, digit)
 117     sorted = raw[:]
 118     sorted.sort()
 119     if sorted == insorted:
 120         return
 121     print >> sys.stderr, "insort test failed: raw %s got %s" % (raw, insorted)
 122     nerrors += 1
 123
 124 check_insort(500)
 125
 126 if nerrors:
 127     raise TestFailed("%d errors in test_bisect" % nerrors)