#!/usr/bin/env python
"""\
follow_tests.py -- Subject a search function to binary_search_tests.txt.
"""
from sys import argv
from random import *
def binary_search( A, T ):
"""\
Return i, nsteps.
i is any int such that A[i] == T, else i = None
nsteps is the number of steps it took.
"""
imin, ilimit = 0, len(A)
nsteps = 0
while imin < ilimit:
nsteps += 1
i = imin + ( ilimit - imin ) / 2
if A[i] == T: return i, nsteps
elif A[i] < T: imin = i + 1
else: ilimit = i
return None, nsteps
def linear_search( A, T ):
""" Return i, nsteps
i == first index such that A[i] == T, else i = None
nsteps is the number of steps taken.
"""
indexes = [ i for i in range( len(A) ) if A[i] == T ]
if indexes: return indexes[ 0 ], len(A)
else: return None, len(A)
def broken_search( A, T ):
""" Give the right answer four out of five times. """
if randrange(5) > 0: return linear_search( A, T )
else:
i, nsteps = linear_search( A, T )
if i == None:
return randrange( -1, len(A) + 1 ), 0
else:
if random() < .5: return None, 0
while True: # Search for a wrong answer.
i = randrange( -1, len(A)+1 )
if i < 0 or i >= len(A) or A[i] != T: return i, 0
if __name__ == "__main__":
searcher = binary_search # the search function, should return r, nsteps
FAIL = None # what searcher returns for "not found"
should_work = True # True means show details of first bug & quit.
print "Testing", searcher.__name__
print
if len( argv ) == 2:
test_file_name = argv[1]
else:
test_file_name = "tests.txt"
f = open( test_file_name )
timings = {}
# timings[nsteps] = size of smallest problem that took exactly nsteps.
while True:
try:
problem_name = f.next().rstrip()
T = int( f.next().rstrip() )
assert f.next().rstrip() == "in ["
A = []
while True:
line = f.next().rstrip()
if line[0] == "]":
break
A.append( int(line) )
is_there = ( line == "]? yes" )
assert f.next().rstrip() == ""
size = len( A )
except StopIteration:
break
result = searcher( A, T )
is_tuple = ( type(result) == tuple and len(result) == 2 )
if not is_tuple:
print "Didn't even return a 2-tuple."
else:
i, nsteps = result
if is_there and i == FAIL:
print "Didn't find it."
elif i != FAIL and ( i < 0 or i >= size ):
print "Result out of range."
elif i != FAIL and A[i] != T:
print "Found it where it ain't."
else:
count, prev_min = timings.get( nsteps, ( 0, size ) )
timings[nsteps] = count + 1, min( prev_min, size )
continue
# One of the above errors:
print "Failed", problem_name
if not should_work:
print
continue
print "A =", A
print "T =", T, ", think it's there =", is_there
if is_tuple:
print "returned i =", i, ", nsteps =", nsteps
if i != FAIL and 0 <= i < len(A):
print "A[", i, "] =", A[i]
else:
print "returned:", result
break
times = [ t for t in timings ]
times.sort()
for t in times:
count, min_size = timings[t]
print "Took", t, "steps for", count, "problems,",
print "smallest of size", min_size
print
print "That was a test of", searcher.__name__