//Name: Janet Guntly
//File: Sort.h
//Class: CS 253, Section 1A
//Due Date: 11/08/07
//Description: Variables and function prototypes for a Sorting class
//				that includes insertion sort, merge sort, and heap sort

#ifndef SORT_H
#define SORT_H

template <class dataType>
class Sort
{
private:
	dataType * data;
	int size;
	int heapSize;
public:
	//Default constructor for the Sort class
	Sort();

	Sort(dataType * dataArray, int newSize);
	
	//Copy constructor for the Sort class
	Sort(const Sort & aSort);
	
	//Destructor for the Sort class
	~Sort();

	//Pre: None
	//Post: Returns the size of the array
	int getSize();

	//Pre: None
	//Post: Changes the size variable to a new value, newSize
	void setSize(int newSize);

	//Pre: None
	//Post: Returns a pointer to the first element of the data array
	dataType *& getData();

	//Pre: newSize is the intended size of the new data array, newSize >= 0
	//Post: Creates a new data array of size newSize and deletes the old one
	void createNewArray(int n);

	//Pre: first is the index of the first element in the array to be sorted, first >=0,
	//		last is the index of the last element in the array to be sorted, last >= first
	//Post: Recursively sorts the data array using the merge() function
	void mergeSort(int first, int last);

	//Pre: first >= 0, middle >= first, last >= middle
	//Post: Merges the subarrays into the data array in sorted order
	void merge(int first, int middle, int last);

	//Pre: None
	//Post: Sorts the data array using the insertion sort algorithm
	void insertionSort();

	//Pre: None
	//Post: Fills the data array with random numbers with values 1 to size * 5
	void fillArrayRand();

	//Pre: The data array is sorted
	//Post: Creates a new array that is reverse sorted for worst case of
	//		insertion sort and deletes the old array
	void reverseArray();

	//Pre: The data array is sorted
	//Post: Creates a new data array that is half sorted and half reverse sorted
	//		for the worst case of merge sort and deletes the old array
	void halfSortHalfReverseArray();

	//Pre: None
	//Post: Displays the contents of the data array for use in testing
	//		the sorting functions
	void display();
	
	//Pre: None
	//Post: Swaps a and b
	void swap(dataType & a, dataType & b);
	
	//Pre: index is the root of the subarray to be heapified
	//Post: The subarray with root at index is a max-heap
	void maxHeapify(int index);
	
	//Pre: None
	//Post: Turns the data array into a max-heap data structure
	void buildMaxHeap();
	
	//Pre: None
	//Post: Sorts the data array using the HeapSort algorithm by making use of the buildMaxHeap
	//		function to create a max-heap and maxHeapify to ensure the integrity of the heap
	void heapSort();
};

#include "Sort.hpp"

#endif