#include <iostream>
#include <string>
#include "helpers.cpp"
using namespace std;

//Return x^n
//Run time?: O(n)
double power(double x, int n)
{
	if (n==0) //base case
	{
		return 1;
	}
	else  //recursive case
	{
		double smallResult = power(x, n - 1);
		return x * smallResult;
	}
}

//solve faster?
//Run time: O(log n)
double fastPower(double x, int n)
{
	if (n==0)
	{
		return 1;
	}
	else
	{
		double halfpow = fastPower(x, n / 2); //C++ always rounds down for integer division

		if ( n % 2 == 0 ) //n is even
		{
			return halfpow * halfpow;
		}
		else //n is odd
		{
			return x * halfpow * halfpow;
		}
	}
}


//Return nth Fibonacci number
int fib(int n)
{
	if (n<=1) //base case
	{
		return n;
	}
	else //recursive case
	{
		return fib(n - 1) + fib(n - 2);
	}
}


//Assume start <= end
void printList(double * A, int start, int end )
{
	if (start == end) //base case
	{
		cout << A[start] << endl;
	}
	else //recursive case
	{
		cout << A[start] << endl;
		printList(A, start + 1, end);
	}
}

void printReverse(double * A, int start, int end)
{
	if (start == end) //base
	{
		cout << A[start] << endl;
	}
	else  //recursive
	{
		printReverse(A, start + 1, end);
		cout << A[start] << endl;
	}
}

//Return index of smallest item in A from start to end inclusive
//Assume start <= end
int findSmallest(double* A, int start, int end)
{
	if (start == end) //base case
	{
		return start;
	}
	else  //recursive
	{
		int smallIndex = findSmallest(A, start + 1, end);
		if (A[start] < A[smallIndex])
			return start;
		else
			return smallIndex;
	}
}

//Sort A from index start to end inclusive.
//Assume start <= end.
//A recursive version of selection sort.
//O(n^2)
void sort(double* A, int start, int end)
{
	if (start == end) //base case
	{
		//Do nothing!  A one item list
		//is always sorted!!!!
		//No work!!! So much time being saved
		//By not having to type any
		//code for this base case.
	}
	else //recursive case
	{
		//Put smallest item at position start
		int smallIndex = findSmallest(A, start, end);
		swap(A[start], A[smallIndex]);

		//Recursively sort from start+1 to end
		sort(A, start + 1, end);
	}
}

//Mergesort
//Run time: O(n log n)
//This is as fast as you can possibly sort (for general purpose comparison based sorting)
void mergeSort(double* A, int start, int end)
{
	if (start == end) //base case
	{
		//do nothing.
	}
	else //recursive case
	{
		int mid = (start + end) / 2;

		mergeSort(A, start, mid); //sort left half
		mergeSort(A, mid + 1, end); //sort right half
		merge(A, start, mid, mid + 1, end);
	}
}

int main()
{
	//Challenge #4:
	cout << power(3, 4) << endl;
	cout << fastPower(3, 4) << endl;
	cout << endl;

	//Challenge #5: compute nth fibonacci number
	cout << fib(9) << endl;  //34
	cout << fib(15) << endl; //???
	cout << endl;

	double nums[] = { 13.8, 2.14, 51, 82, 3.14, 1.7, 4.89, 18, 5, 23.6, 17, 48, 5.6 };

	//Challenge #6: print the list from given range
	printList(nums, 0, 12); //13.8 2.14 51 .... 48 5.6
	cout << endl;

	//Challenge #7: print the list, but backwards
	printReverse(nums, 0, 12); //5.6 48 17 ... 2.14 13.8
	cout << endl;

	//Challenge #8: reverse order of items in list
	//Quiz:  submit solution by midnight tonight 10/29 (No loops allowed)
	//reverse(nums, 0, 12);
	//printList(nums, 0, 12); //5.6 48 17 ... 2.14 13.8

	//Challenge #9: locate minimum item in list
	cout << findSmallest(nums, 0, 12) << endl; //5 because 1.7 is at index 5
	cout << endl;

	//Challenge #10: sort the list
	//sort(nums, 0, 12);
	sort(nums, 0, 12);
	printList(nums, 0, 12); //1.7 2.14 ... 48 51
	cout << endl;

	//Stress test:
	int size = 1000000;
	double* bignums = new double[size];

	for (int i = 0; i < size; i++)
		bignums[i] = rand();

	mergeSort(bignums, 0, size - 1);
	cout << "Mergesort finished" << endl;
	//printList(bignums, 0, size - 1);

	return 0;
}