/******************************************************************************

Eric Baumer
Quick sort assignment solution.
BHCSI 2003

******************************************************************************/

#include <fstream.h>
#include <stdlib.h>
#include <time.h>

#define LIST_LENGTH	1000

enum enumPivot_point
{
    PIVOT_FIRST,
    PIVOT_LAST,
    PIVOT_MIDDLE,
    PIVOT_MEDIAN_OF_THREE
};

bool ReadListFromFile(int list[], char filename[]);
bool WriteListToFile(int list[], char filename[]);
void GenerateListRandomly(int list[]);
int  RandomNumber(int arg_seed = 0);
void Quicksort(int list[], enumPivot_point pivot_method);
void DoSorting(int list[], int start_index, int end_index, 
               enumPivot_point pivot_method);
void Swap(int &x, int &y);

int main(int argc, char *argv[])
{
    // list to hold numbers to sort
	int to_sort[LIST_LENGTH];

    if (argc > 1)
    // there was a command line argument
    {        
        // use it as a file name to read the list from
        if ( !ReadListFromFile(to_sort, argv[1]) )
        {
            cout << "Error reading from file.  "
                 << "Using randomly generated list instead\n";
            GenerateListRandomly(to_sort);
        }
        else
        {
            cout << "Using list in input file " << argv[1] << ".\n";
        }
    }
    else
    // there was no command line argument
    {
        cout << "Using randomly generated list.\n";
        // generate the list randomly
        GenerateListRandomly(to_sort);
    }

    // write the unsorted list to an output file
    if ( !WriteListToFile(to_sort, "unsorted.out") )
    {
        cout << "Error writing to file.\n";
    }
    else
    {
        cout << "Unsorted listed written to unsorted.out.\n";
    }

    // get the pivot method from the user
    int pivot_method;
    cout << "What is the desired pivot selection method?\n"
         << "1 - First\n2 - Last\n3 - Middle\n4 - Median of 3\n"
         << "Enter the number of the desired method. >";
    cin >> pivot_method;

    // sort using the selected pivot method
    Quicksort(to_sort, (enumPivot_point)(pivot_method - 1));

    // write the sorted list to an output file
    if ( !WriteListToFile(to_sort, "sorted.out") )
    {
        cout << "Error writing to file.\n";
    }
    else
    {
        cout << "Sorted list written to sorted.out.\n";
    }

    return 0;
}

bool ReadListFromFile(int list[], char filename[])
{
    ifstream input;
    input.open(filename);

	// Bad File
    if (!input)
    {
        cout << "Could not open file to read from.\n";
        return false;
    }

	// Read in the values.
    for (int i = 0; i < LIST_LENGTH; i++)
    {
        if ( input.eof() )
        {
            cout << "End of file found before expected, not enough numbers.\n";
            return false;
        }

        input >> list[i];
    }

    input.close();

    return true;
}

bool WriteListToFile(int list[], char filename[])
{
    ofstream output;
    output.open(filename);

	// Bad output file.
    if (!output)
    {
        cout << "Could not open file to write to.\n";
    }

	// Write out each array value to the output file.
    for (int i = 0; i < LIST_LENGTH; i++)
    {
        output << list[i] << endl;;
    }

    output.close();

    return true;
}

void GenerateListRandomly(int list[])
{
    for (int i = 0; i < LIST_LENGTH; i++)
    {
        list[i] = RandomNumber();
    }
}

int RandomNumber(int arg_seed)
{
    // local_seed stores the last random number generated so that it may be 
    // used as a seed for the next random number
    static int local_seed = time(NULL);

    if (arg_seed == 0)
    {
        srand( local_seed );
        local_seed = rand();
    }
    else
    {
        srand( arg_seed );
        local_seed = rand();
    }

    return local_seed;
}

// This is an interface function that lets the using code supply only
// information that the using code would know and care about.  DoSorting 
// determines the rest of the necessary information.
void Quicksort(int list[], enumPivot_point pivot_method)
{
    DoSorting(list, 0, LIST_LENGTH - 1, pivot_method);
}

void DoSorting(int list[], int start_index, int end_index, 
               enumPivot_point pivot_method)
{
    int lower_index = start_index,
        upper_index = end_index, 
        pivot_index = start_index,
        swap;

	// Pick partition based on the proper method.
    switch (pivot_method)
    {
        case PIVOT_FIRST:
            pivot_index = start_index;
        break;

        case PIVOT_LAST:
            pivot_index = end_index;
        break;

        case PIVOT_MIDDLE:
            pivot_index = (start_index + end_index) / 2;
        break;

        case PIVOT_MEDIAN_OF_THREE:
            pivot_index = (start_index + end_index) / 2;
            if (list[pivot_index] < list[start_index] &&
                list[start_index] < list[end_index])
            // first element is median and therefore pivot
            {
                pivot_index = start_index;
            }
            else if (list[pivot_index] < list[end_index] &&
                     list[end_index] < list[start_index])
            // last element is median and therefore pivot
            {
                pivot_index = end_index;
            }
            // otherwise, the middle is median and therefore pivot
        break;
    }

	// Perform the partition
    while (lower_index != upper_index)
    {
        while (lower_index < pivot_index)
        {
			// Swap if numbers are out of order.
            if (list[lower_index] > list[pivot_index])
            {
                Swap(list[lower_index], list[pivot_index]);
                Swap(lower_index, pivot_index);
            }

			// Advance the lower_index.
            else
            {
                lower_index++;
            }
        }
        lower_index = pivot_index;

        while (upper_index > pivot_index)
        {
			// Swap if the numbers are out of order.
            if (list[upper_index] < list[pivot_index])
            {
                Swap(list[upper_index], list[pivot_index]);
                Swap(upper_index, pivot_index);
            }

			// Advance the upper_index.
            else
            {
                upper_index--;
            }
        }
        upper_index = pivot_index;
    }

	// Take care of both recursive cases.
    if (start_index < pivot_index)
    {
        DoSorting(list, start_index, pivot_index - 1, pivot_method);
    }
    if (end_index > pivot_index)
    {
        DoSorting(list, pivot_index + 1, end_index, pivot_method);
    }
}

void Swap(int &x, int &y)
{
    int swap = x;
    x = y;
    y = swap;
}