"""
CS 101 class example
Tests timing of linear vs. binary search
"""

import random
import time

def generate_list(list_size):
    """Return a list of random integers of the given size"""
    data = []
    
    for i in range(list_size):
        data.append(random.randint(0, list_size*10))
    
    return data

def linear_test(data, num_queries, largest):
    """
    Given an unsorted list 'data', perform 'num_queries' checks to
    see whether a random integer between 0 and 'largest' is
    contained in 'data'.

    Return the total time taken.
    """
    
    # we'll count them for fun, but won't do anything with the count
    count = 0 
    
    begin = time.time()
    
    for i in range(num_queries):
        # just check to see if a random number is in there
        random_num = random.randint(0, largest)
        
        if linearSearch(random_num, data) >= 0:
            count += 1
            
    return time.time() - begin


def binary_test(data, num_queries, largest):
    """
    Given a sorted list 'data', perform 'num_queries' checks
    using binary search to see whether a random integer
    between 0 and 'largest' is contained in 'data'.

    Return the total time taken.
    """
    
    # we'll count them for fun, but won't do anything with the count
    count = 0 
    
    begin = time.time()
    
    for i in range(num_queries):
        # just check to see if a random number is in there
        random_num = random.randint(0, largest)
        
        if binarySearch(random_num, data) >= 0:
            count += 1
            
    return time.time() - begin

def linearSearch(target, t):
    """
    Returns index of target in list t or -1 if not found
    """
    n = len(t)
    for i in range(n):
        if t[i] == target:
            return i # return location where found
    return -1 # target not found

def binarySearch(target, t):
    """
    Return location of target in sorted list t
    or -1 if not found
    """
    lo = 0
    hi = len(t)-1
    while lo <= hi:
        mid = lo + (hi-lo)//2
        if t[mid] == target:
            return mid
        elif t[mid] < target:
            lo = mid+1
        else: # t[mid] > target
            hi = mid-1
    return -1

def speed_test(set_size, num_queries):
    """Print timing for creating and querying of linear and binary search"""
    # generate random list
    begin = time.time()
    list_data = generate_list(set_size)
    print("List creation took %f seconds" % (time.time()-begin))
        
    print("--")
    
    # time multiple calls to linear search
    elapsed = linear_test(list_data, num_queries, set_size*10)
    print("%d Linear searches took %f seconds" % (num_queries, elapsed))

    # time multiple calls to binary search
    list_data.sort()
    elapsed = binary_test(list_data, num_queries, set_size*10)
    print("%d Binary searches took %f seconds" % (num_queries, elapsed))




def speed_data(num_queries, list_size_min, list_size_max, step_size):
    """
    Print a table of runtimes for querying lists of
    different sizes.
    """
    print("size\tlinear\tbinary")
    
    for list_size in range(list_size_min, list_size_max, step_size):
        # generate random list
        list_data = generate_list(list_size)
    
        # time the list querying
        linear_elapsed = linear_test(list_data, num_queries, list_size*10)

        # time the list querying
        binary_elapsed = binary_test(list_data, num_queries, list_size*10)
        
        print("%d\t%f\t%f" % (list_size, linear_elapsed, binary_elapsed))


#speed_test(100000, 1000)
#speed_data(1000, 10000, 100000, 5000)