#include <iostream>
#include <string>
#include <sstream>
#include <time.h>
#include <stdlib.h>
#include <windows.h>
#include <cstdlib>//Didn't have these.
#include <ctime> //Didn't have these. Page 289

using namespace std;


 template <class Type>
class arraySort{
protected:
	//Type arr[75];
	Type *arr;
	int count;
	int length;

public:
	arraySort();
	void add(const Type& value);
	virtual void sort() = 0;
	void print();

private:
	//void gotoxy( short x, short y);
};

template <class Type>
arraySort<Type>::arraySort(){
	count = 0;
	arr = new Type[75];
}

template <class Type>
void arraySort<Type>::add(const Type& value){
	//int temp = 0;
	//for(int i = 0; i < 75; i++){
	//temp = (rand() % 20);
	arr[count] = value;
	//}
	count++;

		//for (int i = 0; i < 75; i++){
			//temp = (rand() % 20);
}

void gotoxy(short x, short y) {
	HANDLE hStdout = GetStdHandle(STD_OUTPUT_HANDLE);
	COORD position = { x, y };
	SetConsoleCursorPosition( hStdout, position );
}

template <class Type>
void arraySort<Type>::print(){
	system("cls");
	for(int i = 0; i < 75; i++){
		gotoxy(i,arr[i]);
		cout <<"*";
		Sleep(10);
	}//
	//Sleep(10);
}

/*
	clear screen
	for i=0 to 74
	{
		gotoxy(i,arr[i])
		print *
	}
*/

//template <class Type>
//void arraySort<Type>::print(short index, short value){
//	system("cls");
//	gotoxy(index,value);
//	cout <<"*";
//	Sleep(10);
//
//}//



template <class Type>
class insertionSort : public arraySort<Type> {
public:
	void sort();
};//end class insertionSort

template <class Type>
void insertionSort<Type>::sort(){//

	for (int i = 0; i < 75; i++){
	//{print(i, arr[i]);}
	//****print();
	}
int firstOutOfOrder;
int location;
Type temp;

for (firstOutOfOrder = 1; firstOutOfOrder < 75; firstOutOfOrder++)
	if(arr[firstOutOfOrder] < arr[firstOutOfOrder - 1]){
		temp = arr[firstOutOfOrder];
		location = firstOutOfOrder;

		do{
			arr[location] = arr[location - 1];
			//print(location, arr[location]);
			print();
			location--;
		}while(location > 0 && arr[location - 1] > temp);
		arr[location] = temp;
		//print(location, arr[location]);
		//print();
	}
}//end method iSort

//The heapSort class, which inherits off the arraySort base class
template <class Type>
class heapSort : public arraySort<Type> {
public:
	void sort();

private:
	void heapify(int low, int high);
	void buildHeap();
};//end class heapSort

template <class Type>
void heapSort<Type>::sort(){//write this may havfe to add paraments, call print() at beginning and often
								//get code from book
	for (int i = 0; i < 75; i++){
	//{print(i, arr[i]);}
	print();
	}
int lastOutOfOrder;
Type temp;
buildHeap();
for (lastOutOfOrder = 75 - 1; lastOutOfOrder >=0; lastOutOfOrder--){
	temp = arr[lastOutOfOrder];
	arr[lastOutOfOrder] = arr[0];
	//print(lastOutOfOrder,arr[lastOutOfOrder]);
	print();
	arr[0] = temp;
	heapify(0, lastOutOfOrder - 1);
}//end for

}//end method hSort

template <class Type>
void heapSort<Type>::heapify(int low, int high){//write this may havfe to add paraments, call print() at beginning and often
									//get code from book
	int largeIndex;
	Type temp = arr[low];
	largeIndex = 2*low + 1;
	while(largeIndex <= high)
	{
		if(largeIndex < high)
			if(arr[largeIndex] < arr[largeIndex + 1]){
				largeIndex = largeIndex + 1;
				//print(largeIndex, arr[largeIndex]);
				print();
			}
		if(temp > arr[largeIndex])
			break;
		else
		{
			arr[low] = arr[largeIndex];
			//print(low, arr[low]);
			print();
			low = largeIndex;
			largeIndex = 2*low + 1;
		}
	}//end while
	arr[low] = temp;
	//print(low, arr[low]);
	print();

}

template <class Type>
void heapSort<Type>::buildHeap(){

	int index;
	for(index = 75/2 + 1; index >= 0; index--)
		heapify(index, 75-1);
}





int main(){

	insertionSort<int> insS;
	heapSort<int> heapS;
	int selection;
	int temp;
	srand(time(0));
	for (int i = 0; i < 75; i++){
			temp = (rand() % 20);
			insS.add(temp);
			heapS.add(temp);
	}//end for
	cout << "Enter 1 for Insertion Sort, 2 for Heap Sort, 3 to quit:" << endl;
	cin >> selection;
	if (selection == 1)
		//do insertion Sort
		insS.sort();
	if (selection == 2)
		//do heapSort
		heapS.sort();
	if (selection == 3)
		cout << "The answer to everything is 42. Exiting program" << endl;
	//}
	system("pause");
	return 0;
}