#include <iostream.h>
#include <iomanip.h>
#include <ctype.h>
#include "apvector.h"
#include "apqueue.h"
#include "randgen.h"
#include "systimer.h"
#include "apstring.h"

//	sort2.cpp
//	G. Volger
//	2.18.99
// 	Revised 3.13.00 to work with CodeWarrior IDE 4.0
//  Sorts:  Quick, Merge
//	Revised 4.1.01 - Remove debugging statements out of LoadHampton
//					 Added version constant

const apstring VERSION = "sort2.cpp v1.2";

void LoadVector(apvector<int> & a, int n, int low, int high, bool dupsOk);
// Pre: 1 <= n, low < high and (high - low + 1) >= n
//      dupsOk = true allows duplicate entries in the vector
// Post: low <= a[i] <= high, for all0 <= i <= n

void LoadHampton(apvector<int> & a, int n, int low, int high, bool dupsOk);
// Pre: 1 <= n, low < high and (high - low + 1) >= n
//      dupsOk = true allows duplicate entries in the vector
// Post: low <= a[i] <= high, for all0 <= i <= n
//	Chirs Hampton 3.30.00

void CopyVector(const apvector<int> & a, apvector<int> & b);
// Pre: vector a is initialized, a.length() == b.length()
// Post: vector b is an exact copy of vector a

void ShowVector(const apvector<int> & a, int n);
// Post: 10 elements of the vector are displayed per line

void QuickSort(apvector<int> & a, int first, int last);
// Pre: 0 <= first < last < length of vector
// Post: a[i] <= a[i+1] for all 0 <= i <= n-1

void MergeSort(apvector<int> & a, int left, int right);
// Pre: 0 <= left <= right < n
// Post: a[i] <= a[i+1] for all 0 <= i <= n-1

void Merge(apvector<int> & a, int left, int mid, int right);
// Post: Merges a[left] to a[mid] with a[mid+1 to a[right]

void SwapElements(int & x, int & y);
// Pre: x & y are locations in vector a
// Post: a[x] and a[y] values are swapped

int Partition(apvector<int> & a, int first, int last);
// Pre: 0 <= first and last < length of vector
// Post: returns pivot value's location.
//       all a[i] <= a[pivot] for i = frist to pivot-1
//       all a[i] > a[pivot] for i = pivot+1 to last

const int MAX = 10000;

int main ()
{
	cout << VERSION << endl << endl;
	RandGen();
	SysTimer watch;
	int size, low, high;
	apstring choice;
	bool dups, show;
	
	do {
		cout << "Size of vector (Max is " << MAX << ") : ";
		cin >> size;
		if (size <= 0 || size > MAX)
			cout << "Size must be positive!" << endl;
		if (size > MAX)
			cout << "Size must be less than" << MAX << "!" << endl;
	} while (size <= 0 || size > MAX);
	
	cout << "Low range of random numbers to select: ";
	cin >> low;
	do {
		cout << "High range of random numbers to select: ";
		cin >> high;
		if (high <= low)
			cout << "Must be greater than " << low << "!" << endl;
	} while (high <= low);
	
	if (high - low + 1 < size)
		dups = true;
	else
	{
		cout << "Allow duplicates (yes/no) :";
		cin >> choice;
		if (tolower(choice[0]) == 'y')
			dups = true;
		else
			dups = false;
	}
		
	cout << "Show the vector? ";
	cin >> choice;
	if (tolower(choice[0]) == 'y')
		show = true;
	else
		show = false;
			
	apvector<int> a(size), b(size);
	
	LoadHampton(a, size, low, high, dups);
	CopyVector(a, b);
	
	if (show) 
	{
		cout << "\nQuick sort test.\nBefore" << endl;
		ShowVector(a, size);
	}
	watch.start();
	QuickSort(a, 0, size-1);
	watch.stop();
	if (show) 
	{
		cout << "After" << endl;
		ShowVector(a, size);
	}
	cout << setiosflags(ios::fixed | ios::showpoint) << setprecision(6)
	     << "Quick sort Time = " << watch.elapsedTime() << endl;

	if (show) 
	{
		cout << "\nMerge sort test.\nBefore" << endl;
		ShowVector(b, size);
	}
	watch.start();
	MergeSort(b, 0, size-1);
	watch.stop();
	if (show) 
	{
		cout << "After" << endl;
		ShowVector(b, size);
	}
	cout << "Merge sort Time = " << watch.elapsedTime() << endl;

	return 0;
}


void LoadVector(apvector<int> & a, int n, int low, int high, bool dupsOk)
// Pre: 1 <= n, low < high and (high - low + 1) >= n
//      dupsOk = true allows duplicate entries in the vector
// Post: low <= a[i] <= high, for all0 <= i <= n
{
	RandGen r;
	int x;
	bool notDone;
	
	for (int i = 0; i < n; i++)
	{
		do {
			notDone = true;
			x = r.RandInt(low, high);
			if (dupsOk)
			{
				a[i] = x;
				notDone = false;
			}
			else	// No duplicates allowed here
			{
				notDone = false;
				int j = 0;
				while (j < i && !notDone)
				{
					notDone = (x == a[j++]);	// Look for a duplicate
				}
				if (!notDone)					// No duplicate - store value
				{
					a[i] = x;
					notDone = false;
				}
			}
		} while (notDone);
	}
}

void LoadHampton(apvector<int> & a, int n, int low, int high, bool dupsOk)
// Pre: 1 <= n, low < high and (high - low + 1) >= n
//      dupsOk = true allows duplicate entries in the vector
// Post: low <= a[i] <= high, for all0 <= i <= n
//	Chirs Hampton 3.30.00
{
	RandGen r;
	int step;
	
	if (dupsOk)
	{
		for (int i=0; i < n; i++)
			a[i] = r.RandInt(low, high);
	}
	else
	{
		step = (high - low) / n;
		if (step < 1) step = 1;
		
		for (int i=0, x=0; i < n; i++, x += step)					// initial values
			a[i] = x + r.RandInt(0, step-1);
			
		for (int i=0; i < n*100; i++)								// randomizer
			SwapElements(a[r.RandInt(0, n-1)], a[r.RandInt(0, n-1)]);
	}		
}

void CopyVector(const apvector<int> & a, apvector<int> & b)
// Pre: vector a is initialized, a.length() == b.length()
// Post: vector b is an exact copy of vector a
{
	for (int i = 0; i < a.length(); i++)
		b[i] = a[i];
}

void ShowVector(const apvector<int> & a, int n)
// Post: 10 elements of the vector are displayed per line
{
	for (int i = 0; i < n; i++)
	{
		cout << setiosflags(ios::left) << setw(5) << a[i];
		if (i+1 % 10 == 0)
			cout << endl;
	}
	cout << endl;
}

int Partition(apvector<int> & a, int first, int last)
// Pre: 0 <= first and last < length of vector
// Post: returns pivot value's location.
//       all a[i] <= a[pivot] for i = frist to pivot-1
//       all a[i] > a[pivot] for i = pivot+1 to last
{
	int lastSmall = first;
	int i;
	
	for (i = first+1; i <= last; i++)
	// Loop Invariant:  a[first+1]...a[lastSmall] <= a[first]
	//                  a[lastSmall+1]...a[i-1] > a[first]
	{
		if (a[i] <= a[first])
		{
			lastSmall++;
			SwapElements(a[lastSmall],a[i]);
		}
	}
	SwapElements(a[first],a[lastSmall]);	// Moves pivot to correct position
	return lastSmall;						// Final pivot location
}

void QuickSort(apvector<int> & a, int first, int last)
// Pre: 0 <= first <= last < length of vector
// Post: a[i] <= a[i+1] for all 0 <= i <= n-1
{
	// Check for a partition to sort
	// Break into two partitions. a[first] is the pivot.
}


void MergeSort(apvector<int> & a, int left, int right)
// Pre: 0 <= left <= right < n
// Post: a[i] <= a[i+1] for all 0 <= i <= n-1
{
	// Nothing to do if left == right
	// Break section into half
	// Look at both halfs again
	// Merge them back together
}

void Merge(apvector<int> & a, int left, int mid, int right)
// Post: Merges a[left] to a[mid] with a[mid+1 to a[right]
{
	apvector<int> c(a.length());
	int l = left;
	int r = mid + 1;
	int ctr = 0;
	
	while (l <= mid && r <= right)	// while there are elements in both parts
	{
		if (a[l] < a[r])
		{
			c[ctr] = a[l];
			l++;
		}
		else
		{
			c[ctr] = a[r];
			r++;
		}
		ctr++;
	}
	while (l <= mid)		// Any left here?
	{
		c[ctr] = a[l];
		ctr++;
		l++;
	}
	while (r <= right)		// Any left here?
	{
		c[ctr] = a[r];
		ctr++;
		r++;
	}
	for (int i = 0; i < ctr; i++)	// Merge them back
		a[left+i] = c[i];
}

void SwapElements(int & x, int & y)
// Pre: x & y are locations in vector a
// Post: a[x] and a[y] values are swapped
{
	int temp = x;
	x = y;
	y = temp;
}