#! /usr/bin/env python3

"""This is a framework for putting in your own sorting function, but
it also has hooks for profiling the sorting function by counting the
number of comparisons and swaps.

"""

import random
import sys

# count_dict = {}

comparisons = 0
swaps = 0

def main():
    ## see if the user gave a command line argument for the list length
    if len(sys.argv) > 1:
        N_MAX = int(sys.argv[1])
    else:
        N_MAX = 100
    for N in range(N_MAX):
        run_sort_algorithms(N)

def run_sort_algorithms(N):
    l_presorted = list(range(N))

    ## l_random will have random numbers with a non-fixed seed
    random.seed(None)
    l_random = [0]*N
    for i in range(len(l_random)):
        l_random[i] = random.randint(0, 100)

    ## l_random_fixed will always have the same random numbers
    random.seed(1234)
    l_random_fixed = [0]*N
    for i in range(len(l_random_fixed)):
        l_random_fixed[i] = random.randint(0, 100)
    random.seed(None)           # return the seed to be None

    ## l_turtle is designed to do quite poorly with some algorithms:
    ## it has a small value at the end
    l_turtle = list(range(1, N-1))
    l_turtle.append(0)

    ## here is the list of names of initial list layout, mapped to the
    ## actual lists
    list_name_dict = {'l_presorted' : l_presorted,
                      'l_random_fixed' : l_random_fixed,
                      'l_random' : l_random,
                      'l_turtle' : l_turtle}

    for algo in (sort_python_builtin, sort_bubble, sort_myveryown, sort_quicksort):
        run_sort_single_algorithm(algo, N, list_name_dict)

def run_sort_single_algorithm(algo, N, list_name_dict):
    reset_stats(list_name_dict)
    # print('algorithm: %s' % algo.__name__)
    for which_list in list_name_dict.keys():
        # print('list: %s' % which_list)
        l_before = list_name_dict[which_list]
        l_sorted = algo(list_name_dict[which_list], which_list)
        # print('              ', l_before, ' ----> ', l_sorted)
        # print_stats(N, algo.__name__, which_list)
    print_stats(N, algo.__name__, list_name_dict)

def sort_myveryown(l, list_type):
    ## FIXME: must insert my very own sorting function here
    return l

def sort_bubble(l, list_type):
    l2 = l[:]
    for i in range(len(l)):
        for j in range(len(l)-1):
            increment_comparisons(list_type)
            if l2[j] > l2[j+1]:
                increment_swaps(list_type)
                l2[j], l2[j+1] = l2[j+1], l2[j]
    return l2

def sort_quicksort(l, list_type):
    l2 = l[:]
    do_quicksort(l2, 0, len(l)-1, list_type)
    return l2

def do_quicksort(l, low, high, list_type):
    if low < high:
        p = do_qsort_partition(l, low, high, list_type)
        do_quicksort(l, low, p-1, list_type)
        do_quicksort(l, p+1, high, list_type)

def do_qsort_partition(l, low, high, list_type):
    pivot = l[high]
    i = low-1
    for j in range(low, high):
        increment_comparisons(list_type)
        if l[j] < pivot:
            i = i + 1
            increment_swaps(list_type)
            l[i], l[j] = l[j], l[i]
    increment_comparisons(list_type)
    if l[high] < l[i+1]:
        increment_swaps(list_type)
        l[i+1], l[high] = l[high], l[i+1]
    return i+1

def sort_python_builtin(l, list_type):
    """Use the built-in sorting function provided by Python.  Note that
    since we don't write the innards of this function, we cannot keep
    track of how many comparisons and swaps it does.  We do know that
    Python's built-in list.sort() and sorted() functions use the
    Timsort algorithm which is a modified version of merge sort which
    uses insertion sort to arrange the list of items into conveniently
    mergeable sections.  An exercise in the text discusses figuring out
    how to count comparisons in this algorithm."""
    return sorted(l)

def reset_stats(list_name_dict):
    """Resets the counts of comparisons and swaps."""
    global comparisons
    global swaps
    comparisons = {l_type: 0 for l_type in list_name_dict.keys()}
    swaps = {l_type: 0 for l_type in list_name_dict.keys()}

def increment_comparisons(list_type):
    """Increment the counter for the number of comparisons of this
    type of list."""
    global comparisons
    comparisons[list_type] += 1

def increment_swaps(list_type):
    """Increment the counter for the number of swaps of this type 
    of list."""
    global swaps
    swaps[list_type] += 1

def print_stats(N, algo_name, list_name_dict):
    """Print a line with statistics on how this algorithm performs for the
    various lists with length N"""
    global comparisons
    global swaps
    list_types = sorted(list_name_dict.keys())
    ## open the file to write out this data
    fname = algo_name + '.out'
    if N == 0:
        ## first time around we zero out the file and write a header line
        f = open(fname, 'w')
        print('Starting to write to file %s' % fname)
        f.write('## ALGO: %s\n' % algo_name)
        f.write('## COMMENT: columns are "iter", "number-of-comparisons",\n')
        f.write('## COMMENT: "number-of-swaps" for various types of lists\n')
        f.write('## iter')
        for l_type in list_types:
            f.write('   %s  ' % l_type)
        f.write('\n')
    else:
        f = open(fname, 'a')
    f.write('%5d' % N)
    for l_type in list_types:
        # print('ALGO_%s--LIST_%s--comparisons--swaps: %d %d %d'
        #       % (algo_name, l_type, N, comparisons[l_type], swaps[l_type]))
        f.write('   %5d  %5d' % (comparisons[l_type], swaps[l_type]))
    f.write('\n')               # finish this line of data
        
    f.close()

main()