#!/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__