| Tim Peters | 36cdad1 | 2000-12-29 02:06:45 +0000 | [diff] [blame] | 1 | from 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) |