[Python-checkins] CVS: python/dist/src/Lib/test test_bisect.py,NONE,1.1

[Tim Peters]

Update of /cvsroot/python/python/dist/src/Lib/test
In directory usw-pr-cvs1:/tmp/cvs-serv26508/python/dist/src/Lib/test

Added Files:
	test_bisect.py 
Log Message:
Fred, THIS NEEDS DOCS!  The function docstrings tell the tale.
Christmas present to myself:  the bisect module didn't define what
happened if the new element was already in the list.  It so happens
that it inserted the new element "to the right" of all equal elements.
Since it wasn't defined, among other bad implications it was a mystery
how to use bisect to determine whether an element was already in the
list (I've seen code that *assumed* "to the right" without justification).
Added new methods bisect_left and insort_left that insert "to the left"
instead; made the old names bisect and insort aliases for the new names
bisect_right and insort_right; beefed up docstrings to explain what
these actually do; and added a std test for the bisect module.


--- NEW FILE: test_bisect.py ---
from test_support import TestFailed

import bisect
import sys

nerrors = 0

def check_bisect(func, list, elt, expected):
    global nerrors
    got = func(list, elt)
    if got != expected:
        print >> sys.stderr, \
            "expected %s(%s, %s) -> %s, but got %s" % (func.__name__,
                                                       list,
                                                       elt,
                                                       expected,
                                                       got)
        nerrors += 1

# XXX optional slice arguments need tests.

check_bisect(bisect.bisect_right, [], 1, 0)
check_bisect(bisect.bisect_right, [1], 0, 0)
check_bisect(bisect.bisect_right, [1], 1, 1)
check_bisect(bisect.bisect_right, [1], 2, 1)
check_bisect(bisect.bisect_right, [1, 1], 0, 0)
check_bisect(bisect.bisect_right, [1, 1], 1, 2)
check_bisect(bisect.bisect_right, [1, 1], 2, 2)
check_bisect(bisect.bisect_right, [1, 1, 1], 0, 0)
check_bisect(bisect.bisect_right, [1, 1, 1], 1, 3)
check_bisect(bisect.bisect_right, [1, 1, 1], 2, 3)
check_bisect(bisect.bisect_right, [1, 1, 1, 1], 0, 0)
check_bisect(bisect.bisect_right, [1, 1, 1, 1], 1, 4)
check_bisect(bisect.bisect_right, [1, 1, 1, 1], 2, 4)
check_bisect(bisect.bisect_right, [1, 2], 0, 0)
check_bisect(bisect.bisect_right, [1, 2], 1, 1)
check_bisect(bisect.bisect_right, [1, 2], 1.5, 1)
check_bisect(bisect.bisect_right, [1, 2], 2, 2)
check_bisect(bisect.bisect_right, [1, 2], 3, 2)
check_bisect(bisect.bisect_right, [1, 1, 2, 2], 0, 0)
check_bisect(bisect.bisect_right, [1, 1, 2, 2], 1, 2)
check_bisect(bisect.bisect_right, [1, 1, 2, 2], 1.5, 2)
check_bisect(bisect.bisect_right, [1, 1, 2, 2], 2, 4)
check_bisect(bisect.bisect_right, [1, 1, 2, 2], 3, 4)
check_bisect(bisect.bisect_right, [1, 2, 3], 0, 0)
check_bisect(bisect.bisect_right, [1, 2, 3], 1, 1)
check_bisect(bisect.bisect_right, [1, 2, 3], 1.5, 1)
check_bisect(bisect.bisect_right, [1, 2, 3], 2, 2)
check_bisect(bisect.bisect_right, [1, 2, 3], 2.5, 2)
check_bisect(bisect.bisect_right, [1, 2, 3], 3, 3)
check_bisect(bisect.bisect_right, [1, 2, 3], 4, 3)
check_bisect(bisect.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 0, 0)
check_bisect(bisect.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 1, 1)
check_bisect(bisect.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 1.5, 1)
check_bisect(bisect.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 2, 3)
check_bisect(bisect.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 2.5, 3)
check_bisect(bisect.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 3, 6)
check_bisect(bisect.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 3.5, 6)
check_bisect(bisect.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 4, 10)
check_bisect(bisect.bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 5, 10)

check_bisect(bisect.bisect_left, [], 1, 0)
check_bisect(bisect.bisect_left, [1], 0, 0)
check_bisect(bisect.bisect_left, [1], 1, 0)
check_bisect(bisect.bisect_left, [1], 2, 1)
check_bisect(bisect.bisect_left, [1, 1], 0, 0)
check_bisect(bisect.bisect_left, [1, 1], 1, 0)
check_bisect(bisect.bisect_left, [1, 1], 2, 2)
check_bisect(bisect.bisect_left, [1, 1, 1], 0, 0)
check_bisect(bisect.bisect_left, [1, 1, 1], 1, 0)
check_bisect(bisect.bisect_left, [1, 1, 1], 2, 3)
check_bisect(bisect.bisect_left, [1, 1, 1, 1], 0, 0)
check_bisect(bisect.bisect_left, [1, 1, 1, 1], 1, 0)
check_bisect(bisect.bisect_left, [1, 1, 1, 1], 2, 4)
check_bisect(bisect.bisect_left, [1, 2], 0, 0)
check_bisect(bisect.bisect_left, [1, 2], 1, 0)
check_bisect(bisect.bisect_left, [1, 2], 1.5, 1)
check_bisect(bisect.bisect_left, [1, 2], 2, 1)
check_bisect(bisect.bisect_left, [1, 2], 3, 2)
check_bisect(bisect.bisect_left, [1, 1, 2, 2], 0, 0)
check_bisect(bisect.bisect_left, [1, 1, 2, 2], 1, 0)
check_bisect(bisect.bisect_left, [1, 1, 2, 2], 1.5, 2)
check_bisect(bisect.bisect_left, [1, 1, 2, 2], 2, 2)
check_bisect(bisect.bisect_left, [1, 1, 2, 2], 3, 4)
check_bisect(bisect.bisect_left, [1, 2, 3], 0, 0)
check_bisect(bisect.bisect_left, [1, 2, 3], 1, 0)
check_bisect(bisect.bisect_left, [1, 2, 3], 1.5, 1)
check_bisect(bisect.bisect_left, [1, 2, 3], 2, 1)
check_bisect(bisect.bisect_left, [1, 2, 3], 2.5, 2)
check_bisect(bisect.bisect_left, [1, 2, 3], 3, 2)
check_bisect(bisect.bisect_left, [1, 2, 3], 4, 3)
check_bisect(bisect.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 0, 0)
check_bisect(bisect.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 1, 0)
check_bisect(bisect.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 1.5, 1)
check_bisect(bisect.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 2, 1)
check_bisect(bisect.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 2.5, 3)
check_bisect(bisect.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 3, 3)
check_bisect(bisect.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 3.5, 6)
check_bisect(bisect.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 4, 6)
check_bisect(bisect.bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 5, 10)

def check_insort(n):
    global nerrors
    from random import choice
    import sys
    digits = "0123456789"
    raw = []
    insorted = []
    for i in range(n):
        digit = choice(digits)
        raw.append(digit)
        if digit in "02468":
            f = bisect.insort_left
        else:
            f = bisect.insort_right
        f(insorted, digit)
    sorted = raw[:]
    sorted.sort()
    if sorted == insorted:
        return
    print >> sys.stderr, "insort test failed: raw %s got %s" % (raw, insorted)
    nerrors += 1

check_insort(500)

if nerrors:
    raise TestFailed("%d errors in test_bisect" % nerrors)