#include <iostream>
#include <string>
#include <chrono>
#include "mysterySort.h"
using namespace std;

/*
//static array declaration
double A[10];


//dynamic array declaration
double* A;
A = new double[10];
*/

//Print out items in X from start to end
//Let n = end - start + 1
//Run time: O(n)
template <class T>
void display(T * X, int start, int end)
{
	for (int i = start; i <= end; i++)
	{
		cout << X[i] << endl;
	}
}

//Run time: O(n)
void randomFill(double* X, int start, int end, int maxNum)
{
	for (int i = start; i <= end; i++)
	{
		X[i] = rand() % maxNum;
		X[i]++;
	}
}


//Locate position of value key within given
//search range.  Return the index location.
//Return -1 if key is not present in given
//range.
//Run time: O(n)
//Templated function:
template <class THING>
int find(THING * X, int start, int end, THING key)
{
	for (int i = start; i <= end; i++)
	{
		if (X[i] == key)
			return i;
	}
	return -1;
}

//Return index of smallest value
//in given range.
//Run time: O(n)
template <class T>
int findSmallest(T * X, int start, int end)
{
	int smallSeenSoFarIndex = start;

	for (int i = start; i <= end; i++)
	{
		if (X[i] < X[smallSeenSoFarIndex])
			smallSeenSoFarIndex = i;
	}
	return smallSeenSoFarIndex;
}

//Run time: O(n^2)
template <class T>
void selectionSort(T * X, int start, int end)
{
	for (int i = start; i <= end; i++) //n loops
	{
		//Body run time: O(n)
		int smallIndex = findSmallest(X, i, end);
		swap(X[i], X[smallIndex]);
	}
}

int main()
{
	double* A;
	//An array of 10 doubles.
	A = new double[10];

	A[0] = 3.14;
	A[1] = 2.7;
	A[2] = 1.6;
	A[3] = 186282;
	A[4] = 6.6;
	A[5] = 15;
	A[6] = 17;
	A[7] = 11;
	A[8] = 9.3;
	A[9] = 7.4;

	//Selection Sort: O(n^2)
	selectionSort(A, 0, 9);
	display(A, 0, 9);
	cout << endl;

	//Templated functions
	string* B;
	B = new string[5];
	B[0] = "interesting";
	B[1] = "war";
	B[2] = "creatine";
	B[3] = "anotherOne";
	B[4] = "oneMore";

	selectionSort(B, 0, 4);
	display(B, 0, 4);

	cout << find(B, 0, 4, string("war")) << endl; //1
	cout << find(B, 0, 4, string("interesting")) << endl; //0
	cout << find(B, 0, 4, string("oneMore")) << endl; //4
	cout << find(B, 0, 4, string("nothing")) << endl; //-1

	//Stress Test
	int big = 1000000;
	double* D = new double[big];

	for (int i = 0; i < big; i++)
		D[i] = rand();


	auto start = chrono::high_resolution_clock::now();
	//selectionSort(D, 0, big - 1);
	mergeSort(D, 0, big - 1);
	auto finish = chrono::high_resolution_clock::now();

	chrono::duration<double> elapsed = finish - start;
	cout << "Algorithm took: " << elapsed.count() << endl;
	
	
	//display(D, 0, big - 1);

	//Linear Search: O(n)
	cout << find(A, 0, 9, 6.6) << endl;  //4
	cout << find(A, 2, 7, 17.0) << endl; //6
	cout << find(A, 3, 7, 3.14) << endl; //-1 (it's not there)


	//Binary Search:


	return 0;
}


///Timing code
/*
auto start = chrono::high_resolution_clock::now();
//method to time...
auto finish = chrono::high_resolution_clock::now();

chrono::duration<double> elapsed = finish - start;
cout << "Algorithm took: " << elapsed.count() << endl;
*/


/*
	///QUIZ
	double* C = new double[4];
	C[0] = 5;
	C[1] = 15;
	C[2] = 3;
	c[3] = 2;

	cout << addEmUp(C, 0, 3) << endl; //25
	cout << addEmUp(C, 2, 3) << endl; //5
	cout << addEmUp(C, 0, 2) << endl; //23
*/