/***************************************************************************
 *   Copyright (C) 2006 by Alex Brandt                                     *
 *   alunduil@alunduil.com                                                 *
 *                                                                         *
 *   This program is free software; you can redistribute it and/or modify  *
 *   it under the terms of the GNU General Public License as published by  *
 *   the Free Software Foundation; version 2 of the License.               *
 *                                                                         *
 *   This program is distributed in the hope that it will be useful.       *
 *   but WITHOUT ANY WARRANTY: without even the implied warranty of        *
 *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the         *
 *   GNU General Public License for more details.                          *
 *                                                                         *
 *   You should have received a copy of the GNU General Public License     *
 *   along with this program; if not, write to the                         *
 *   Free Software Foundation, Inc..                                       *
 *   59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.              *
 ***************************************************************************/

/*
Pieces of this code were adopted from the examples at http://yagni.com/combsort/#cpp-combsort
*/

#include <iostream>
#include <cstdlib>
#include <fstream>
#include <getopt.h>
#include <string.h>
#include <sstream>
#include <time.h>

#include "sorts.h"

using namespace std;

void usage(char *argv[]);

void help(char *argv[]);

template<typename Type>
Type string_cast(const string &stringToCast);

template<typename Type>
string cast2String(const Type &item);

int random(int ceiling);

void scramble(int a[], int aSize);

void makeScrambledArray(int a[], int size);

int main(int argc, char *argv[])
{

	int				index;				// Index of the option after getopt.

	string			sortAlgorithm = "";	// Algorithm to sort by.

	unsigned int	numElements = 0,	// Number of elements in the list.
					numTrials = 1;		// Number of trials to perform.

	while (true)
	{
		int			option_index = 0;	// Position in the long options array.

		static struct option long_options[] =
		{
			{"number", 1, 0, 0},
			{"sort", 1, 0, 0},
			{"trials", 1, 0, 0},
			{"help", 0, 0, 0},
			{0, 0, 0, 0}
		};								// Array of long options.

		/*
		Try to read the command-line options, and if any problems arise it was
		probably a typo on the command-line. This being the case we should
		print the usage rules for the program, and quit.
		*/

		try
		{
			index = getopt_long(argc, argv, "t:n:s:h", long_options, &option_index);
		}
		catch (...)
		{
			usage(argv);
			return EXIT_SUCCESS;
		}

		/*
		If getopt finished its stuff break out of the infinite loop.
		*/

		if (index == -1)
			break;

		/*
		Parse the options and perform their necessary actions.
		*/

		switch (index)
		{
			case 0:
				/*
				The long options parsing (kind of nasty, but it works).
				*/
				if (!strcmp(long_options[option_index].name, "number"))
					numElements = string_cast<unsigned int>(cast2String(optarg));
				else if (!strcmp(long_options[option_index].name, "sort"))
					sortAlgorithm = optarg;
				else if (!strcmp(long_options[option_index].name, "trials"))
					numTrials = string_cast<unsigned int>(cast2String(optarg));
				else if (!strcmp(long_options[option_index].name, "help"))
				{
					help(argv);
					return EXIT_SUCCESS;
				}
				else
				{
					usage(argv);
					return EXIT_SUCCESS;
				}
				break;
			case 'n':
				numElements = string_cast<unsigned int>(cast2String(optarg));
				break;
			case 't':
				numTrials = string_cast<unsigned int>(cast2String(optarg));
				break;
			case 's':
				sortAlgorithm = optarg;
				break;
			case 'h':
				help(argv);
				return EXIT_SUCCESS;
			default:
				usage(argv);
				return EXIT_SUCCESS;
		}
	}

	if (optind > argc || sortAlgorithm == "" || numElements == 0)
	{
		usage(argv);
		return EXIT_SUCCESS;
	}

	int				*itemList = new int[numElements];

	double			seconds,			// Number of seconds the sort took.
					totalTime = 0;		// Total time for all runs.

	for (unsigned int i = 0; i < numTrials; i++)
	{
		makeScrambledArray(itemList, numElements);

		if (sortAlgorithm == "comb")
		{
			clock_t startTime = clock();
			combsort(itemList, numElements);
			clock_t stopTime = clock();
			seconds = static_cast<double>(stopTime - startTime)/CLOCKS_PER_SEC;
		}
		else if (sortAlgorithm == "quick")
		{
			clock_t startTime = clock();
			quicksort(itemList, numElements);
			clock_t stopTime = clock();
			seconds = static_cast<double>(stopTime - startTime)/CLOCKS_PER_SEC;
		}
		else if (sortAlgorithm == "bubble")
		{
			clock_t startTime = clock();
			bubblesort(itemList, numElements);
			clock_t stopTime = clock();
			seconds = static_cast<double>(stopTime - startTime)/CLOCKS_PER_SEC;
		}
		else
		{
			usage(argv);
			return EXIT_FAILURE;
		}
		totalTime += seconds;
	}

	cout << "The average time to run the " << sortAlgorithm << "sort is " << totalTime/numTrials << "(s)" << endl;

	delete [] itemList;

	return EXIT_SUCCESS;
}

void usage(char *argv[])
{
	cout << "usage: " << argv[0] << " -n <number of elements> -s <sort algorithm> [-t <number of trials>] [-h]" << endl;
	return;
}

void help(char *argv[])
{
	cout << "Usage: " << argv[0] << " [options]                                              " << endl;
	cout << "Performs the specified sorting algorithm on the data in the file passed. Can be " << endl;
	cout << "used to obtain timing information for these algorithms by using the shell script" << endl;
	cout << "'time'.                                                                         " << endl;
	cout << endl;
	cout << "Mandatory options for short options are mandatory for long options as well.     " << endl;
	cout << endl;
	cout << "-n , --number=NUMBER               Lets the script know how big of an array to  " << endl;
	cout << "-t , --trials=NUMBER               Lets the script know the number of runs to   " << endl;
	cout << "                                   perform and average over.                    " << endl;
	cout << "-s , --sort=SORT                   Specifies the sort algorithm to be used in   " << endl;
	cout << "                                   in this run. SORT can be any of the          " << endl;
	cout << "                                   following: comb, quick, bubble.              " << endl;
	cout << "-h , --help                        Displays this help menu.                     " << endl;
	return;
}

template<typename Type>
Type string_cast(const string &stringToCast) {
    stringstream stringStream;  // Instantiate a string stream.

    stringStream << stringToCast;
    stringStream.seekg(0, ios::beg);

    Type item;                  // Instantiate a variable of type to cast.

    stringStream >> item;
    return item;
}

template<typename Type>
string cast2String(const Type &item) {

    stringstream stringStream;  // Instantiate a string stream.

    stringStream << item;
    stringStream.seekg(0, ios::beg);

    string stringCasting;       // Instantiate a string to put things in.

    while ( !stringStream.eof() ) {
        stringCasting += static_cast<char>(stringStream.get());
    }
    return stringCasting;
}

int random(int ceiling)
{
	return static_cast<int>((static_cast<float>(rand())/RAND_MAX) * ceiling);
}

void scramble(int a[], int aSize)
{
	for (int i = 0; i < aSize; i++)
		std::swap(a[i], a[random(aSize)]);
	return;
}
void makeScrambledArray(int a[], int size)
{
	for (int i = 0; i < size; i++)
		a[i] = i;
	scramble(a, size);
	return;
}