//*******************************************************************************
// Filename: Lab2-intMergeSort-Outline.cpp
// Student Name (Author): Rex Woollard
// Student Number: XXXXXXXXX
// Student e-mail Address: woollar@AlgonquinCollege.com
// Course Name: Data Structures
// Course Number: CST8130
// Lab Section: 11
// Assignment Number and Name: Lab 2A: Sorting int Values using MergeSort and Recursion
// Due Date: September 15, 2008
// Submission Date: September 3, 2008
// Professor's Name: Rex Woollard
// Purpose:
// - Creates dynamically allocated array of random integer values
// - Sorts using bubble sort (tracking elapse time)
// - Repopulates array with same set of random values
// - Sorts using mergesort (tracking elapse time)
// - Repopulates array with same set of random values
// - Sorts using qsort() library routine (tracking elapse time)
//*******************************************************************************

#include <sys\timeb.h>	// for ftime()

#include <cstdlib>			// for rand() and srand()
#include <ctime>				// for time()

#include <iostream>
#include <iomanip>
using namespace std;


// The rand() function returns only 15 bits of randomized data. This routine generates
// up to 32 bits of fully randomized data (with a programmer defined range of values).
long LargeRandom(long lMinimum, long lMaximumValue)
	{
	return (signed long)(( (((unsigned long)rand())<<17) | (((unsigned long)rand())<<2) | (((unsigned long)rand())&0x0003) ) % ((unsigned long)(lMaximumValue - lMinimum + 1))) + lMinimum;
	}

/******************************
struct timeb {
time_t time;
unsigned short millitm;
short timezone;
short dstflag;
};
******************************/

class DataSet {
private:
	int nNumElements;
	unsigned long ulChecksumBeforeSort;
	int* panArrayOfNumbers;
	int* panWorkSpace;
	bool bDisplayArray;

	void MergeSort(int nFirst, int nLast);
	double GetCurrentTime() { timeb tb; ftime(&tb); return(double(tb.time) + double(tb.millitm)/1000.0); }

public:
	DataSet() : nNumElements(0), panArrayOfNumbers(NULL), panWorkSpace(NULL) { }
	~DataSet()
		{
		delete [] panArrayOfNumbers;
		} // C/C++ standard allows for release of pointers that might contain NULL

	void BuildAndPopulateArrayOfRandomIntegers()
		{
		delete [] panArrayOfNumbers; // may already be NULL, but that's alright according to the ANSI standard
		cout << "Array sizes less-than-or-equal-to 16 will be fully displayed\n";
		cout << "showing the recursive sequence.\n\nEnter size of array: ";
		cin >> nNumElements;
		panArrayOfNumbers = new int[nNumElements];
		ulChecksumBeforeSort = 0;

		bDisplayArray = (nNumElements <= 18);	// Flag variable will be used to suppress the display of the array when it has more than 20 elements
		// The data set will be populated with randomly generated values.
		// The value in any element can be a value from 0 to nRange - 1
		int nMinimum;
		cout << "Enter minimum value for any element: ";
		cin >> nMinimum;
		int nMaximum;
		cout << "Enter maximum value for any element: ";
		cin >> nMaximum;

		srand(115247);  // always seed the random generator with the same value to create the same sequence of random numbers so that tests are with identical random sequences
		for (int i = 0; i < nNumElements; ++i)
			ulChecksumBeforeSort += panArrayOfNumbers[i] = LargeRandom(nMinimum, nMaximum);
		}  // end PopulateArrayOfRandomIntegers()

	void DisplayArray(char* pszLabel)
		{
		if ( ! bDisplayArray)
			return;

		cout << pszLabel << ":";
		for (int i = 0; i < nNumElements; i++)
			cout << setw(4) << panArrayOfNumbers[i];
		cout << endl;
		}  // end DisplayArray()

	double MergeSort()
		{
		double dStartTime = GetCurrentTime();	// Capture the current system clock as the start time
		panWorkSpace = new int[nNumElements]; // Create temporary array which is used during Merge operations
		MergeSort(0, nNumElements-1);
		delete [] panWorkSpace;								// After returning from all recursive calls, release memory
		return GetCurrentTime()-dStartTime;		// Find the difference between the start time and current time
		}

	bool CheckIfArrayIsSorted();
	void Merge(int nLow, int nHigh, int nEndOfHigh);
	};

/////////////////////////////////////////////////////////////////////////////
// MergeSort()
// Purpose:	Starts with a data set.
//          If more than one item
//            split data set in equal halves.
//            sort right half by calling MergeSort() recursively.
//            sort left half by calling MergeSort() recursively.
//            two halves now known to be sorted, call Merge() to combine into single sorted data set.
// Inputs:  - pointer to array to be sorted
//          - pointer to workspace array created before the first call to MergeSort() (saves time by not reallocating memory repeatedly)
//          - index of left edge of data set to be sorted
//          - index of right edge of data set to be sorted
// Outputs: 
// External Inputs:
// External Outputs: 
// Version: Rex Woollard:	2006/01/11: Initial Build
//          Rex Woollard:	2006/01/21: Include exchange and comparison counts
/////////////////////////////////////////////////////////////////////////////
void DataSet::MergeSort(int nLow, int nHigh)
	{
	// TO DO: Implement recursive code
	//				Look to the online lecture on MergeSort for the algorithm to implement this
	}  // end MergeSort()

/////////////////////////////////////////////////////////////////////////////
// Merge()
// Purpose:	Starts with a data set (array) which is split by a mid-point.
//          Use a temporary array to assist in merging.
//          Copy values from two original arrays to temporary array, always choosing the smallest item
//          Copy values from temporary array back to the original arrays
// Inputs:  - pointer to array to be sorted
//          - pointer to workspace array created before the first call to MergeSort() (saves time by not reallocating memory repeatedly)
//          - index of left edge of data set to be sorted
//          - index of middle
//          - index of right edge of data set to be sorted
//          - Counters for number of Exchanges and Comparisons (sent by reference)
// Outputs: 
// External Inputs:
// External Outputs:
// Version: Rex Woollard:	2006/01/11: Initial Build
//          Rex Woollard:	2006/01/21: Include exchange and comparison counts
/////////////////////////////////////////////////////////////////////////////
void DataSet::Merge(int nLow, int nHigh, int nEndOfHigh)
	{
	int nWorkSpaceIndex = 0;
	int nLowerBound = nLow;
	int nEndOfLow = nHigh-1;

	// Loop 1: Work with both sets of data, looking for the next lowest item from each.
	while (nLow <= nEndOfLow  &&  nHigh <= nEndOfHigh) {
		if (panArrayOfNumbers[nLow] < panArrayOfNumbers[nHigh])
			panWorkSpace[nWorkSpaceIndex++] = panArrayOfNumbers[nLow++];
		else
			panWorkSpace[nWorkSpaceIndex++] = panArrayOfNumbers[nHigh++];
		}

	// Only one of Loops 2 and 3 are executed on any given pass -- it will never execute both
	// Loop 2: Copy the remaining items from the low side of the array (the high side is empty)
	while(nLow <= nEndOfLow)
		panWorkSpace[nWorkSpaceIndex++] = panArrayOfNumbers[nLow++];

	// Loop 3: Copy the remaining items from the high side of the array (the low side is empty)
	while(nHigh <= nEndOfHigh)
		panWorkSpace[nWorkSpaceIndex++] = panArrayOfNumbers[nHigh++];

	// Loop 4: Copy the now sorted values back to the original array
	int nNumItemsInRange = nEndOfHigh-nLowerBound+1;
	for(nWorkSpaceIndex=0; nWorkSpaceIndex<nNumItemsInRange; nWorkSpaceIndex++)
		panArrayOfNumbers[nLowerBound+nWorkSpaceIndex] = panWorkSpace[nWorkSpaceIndex];
	}  // end Merge()


/////////////////////////////////////////////////////////////////////////////
// CheckIfArrayIsSorted()
// Purpose: Sweeps through an array comparing adjacent items to ensure that
//          they are in ascending sequence
// Inputs:  - pointer to array to be checked
//          - size of the array
// Outputs: boolean true if the array is sorted, false if it is not
// External Inputs:
// External Outputs:
// Version: Rex Woollard: 2006/01/11: Initial Build
/////////////////////////////////////////////////////////////////////////////
bool DataSet::CheckIfArrayIsSorted()
	{
	unsigned long ulChecksumAfterSort = 0;
	int* pnScanner = panArrayOfNumbers;
	int* pnLastElement = panArrayOfNumbers + (nNumElements - 1);
	while (pnScanner < pnLastElement) {
		ulChecksumAfterSort += *pnScanner;
		if (*pnScanner > *(pnScanner + 1))
			return false;
		pnScanner++;
		}
	ulChecksumAfterSort += *pnScanner;
	if (ulChecksumAfterSort != ulChecksumBeforeSort)
		return false;
	else
		return true;
	}  // end CheckIfArrayIsSorted()


/////////////////////////////////////////////////////////////////////////////
// main()
// Purpose:
// - Creates array of randomly generated integers.
// - Sorts one array using Bubble Sort algorithm
// - Recreates array of integers with same set of randomly generated values
// - Sorts second array using Quicksort algorithm
// - Tracks exchanges, comparisons and elapse time each algorithm
// Inputs:
// Outputs:
// External Inputs:
// - size of array to be sorted
// - maximum value for any individual element
// - choice to run the sort routins again
// External Outputs:
// - displays the time taken to sort
// - with small number of elements (<= 20), displays array after each pass
// Version: Rex Woollard	2006/01/11: Initial Build
//          Rex Woollard	2006/08/29: Split array creation to a separate function
/////////////////////////////////////////////////////////////////////////////
void main()
	{
	char cSortAgain;

	do {
		DataSet dsSetOfNumbers;	
		dsSetOfNumbers.BuildAndPopulateArrayOfRandomIntegers();
		dsSetOfNumbers.DisplayArray("Unsorted array before Merge Sort");
		double dElapseTime = dsSetOfNumbers.MergeSort();
		dsSetOfNumbers.DisplayArray("Sorted after Merge Sort");
		if (dsSetOfNumbers.CheckIfArrayIsSorted())
			cout << "Array is correctly sorted." << endl;
		else
			cout << "Array is not sorted correctly." << endl;
		cout << "Sorted Array in "<< dElapseTime << " seconds" << endl;

		cout << endl << "Sort Again? (y/n): ";
		cin >> cSortAgain;
		} while (cSortAgain == 'y');
	}  // end main()