# lab12.py
# Walker M. White (wmw2)
# November 20, 2012
"""Lab module for timing execution."""
import sorting
import random
import time

def times():
    """Determine and print how long it takes to create a Date object."""
    # Store in timestart the time at which the statement is executed.
    timestart = time.time()
        
    # Store in timeend the time at which the statement is executed.
    timeend= time.time()
        
    print 'Time timestart, in seconds: ' + str(timestart)
    print 'Time timestart, in milliseconds: ' + str(int(round(timestart*1000)))
    print ''
    print 'Time timeend, in seconds: ' + str(timeend)
    print 'Time timeend, in milliseconds: ' + str(int(round(timeend*1000)))


def testsorts(m=10000):
    """Execute selection sort and insertion sort m times
    on a lisr of 5000 elements. Print timing results.
    
    Precondition: m >= 0."""
    b = [0]*m       # List to sort
    
    # Run selection sort m times and print the results
    print 'Running selection sort on list of ' + str(m) + ' elements'

    fill_rand(b)
    timestart= time.time()
    sorting.selection_sort(b)
    timeend= time.time()
    diff = int(round((timeend-timestart)*1000))

    print 'Time for selection sort: '+str(diff)+' ms'

    # Run insertion sort m times and print the results
    print 'Running insertion sort on list of ' + str(m) + ' elements'

    fill_rand(b)
    timestart= time.time()
    sorting.insertion_sort(b,0,len(b)-1)
    timeend= time.time()
    diff = int(round((timeend-timestart)*1000))

    print 'Time for insertion sort: '+str(diff)+' ms'


def fill_rand(b):
    """Fill list b with random integers in [0,1000000)."""
    # inv: have filled in b[0..i-1]
    i = 0
    while (i != len(b)):
        b[i]= random.randint(0,1000000)
        i = i+1


def fill_neg(b):
    """Fill list b: put -i in b[i]."""
    # inv: have filled in b[0..i-1]
    i = 0
    while (i != len(b)):
        b[i] = -i
        i = i+1


def fill_pos(b):
    """Fill list b: put i in b[i]."""
    # inv: have filled in b[0..i-1]
    i = 0
    while i != len(b):
        b[i] = i
        i = i+1


def testsorts2(m=10000):
    """Execute selection sort and quicksort m times
    on a list of 75000 elements. Print timing results.
    
    Precondition: m >= 0"""
    b = [0]*m       # List to sort
    
    # Run selection sort m times and print the results
    print 'Running selection sort on list of ' + str(m) + ' elements'

    fill_rand(b)
    timestart = time.time()
    sorting.selection_sort(b)
    timeend= time.time()
    diff = int(round((timeend-timestart)*1000))

    print 'Time for selection sort: '+str(diff)+' ms'

    # Run insertion sort m times and print the results
    print 'Running quicksort on list of ' + str(m) + ' elements'

    fill_rand(b)
    timestart = time.time()
    sorting.quicksort(b,0,len(b)-1)
    timeend= time.time()
    diff = int(round((timeend-timestart)*1000))

    print 'Time for quicksort: '+str(diff)+' ms'


def testsearches(m=100):
    """Execute linear search and binary search m times
    on a list of 100000 elements. Print results

    Precondition: m >= 0."""
    b = [0]*1000000   # List to search
    
    print 'Populating sorted list'
    fill_pos(b)
    
    # Run linear search m times and print the results
    print 'Running linear search ' + str(m) + ' times'
       

    timestart= time.time()
    # inv: have done iterations 0..i-1
    i = 0
    # inv: linear_search has been called i times.
    while i < m:
        answer = sorting.linear_search(b, len(b))
        i = i+1
    timeend= time.time()
    diff = int(round((timeend-timestart)*1000))

    print 'Time for linear search: '+str(diff)+' ms'

    # Run binary search m times and print the results
    print 'Running binary search ' + str(m) + ' times'
       
    fill_pos(b);

    timestart= time.time()
    # inv: have done iterations 0..i-1
    i = 0
    # inv: binary_search has been called i times.
    while i < m:
        answer = sorting.binary_search(b, len(b))
        i = i+1
    timeend= time.time()
    diff = int(round((timeend-timestart)*1000))

    print 'Time for binary search: '+str(diff)+' ms'