#include <iostream.h>
#include <fstream.h>
#include <ctype.h>
#include <iomanip.h>
#include <console.h>		// PC Users comment out this line
#include <sioux.h>			// PC Users comment out this line
#include "apstring.h"
#include "apvector.h"
#include "randgen.h"
#include "systimer.h"

// sort1.cpp
// 2.15.99
// Revised 3.13.00 to work for CodeWarrior IDE 4.0
// Modified - added comments for PC users
// G. Volger
// Revised 3.6.03 - fixed warnings from case statement
// Changed rando.h to randgen.h
// Gave more comments for PC users
// G. Volger

typedef int DataType;

struct Item {
	Item() : key(0) {}	// Default constructor
	int key;
	DataType data;
};
typedef apvector<Item> TheArray;

void InitCounters();
// post: sets the global move and compare counters to zero

apstring GetSortName();
// post: returns the name of the sort to be used
//       Selection, Insertion or Exchange

int GetSize();
// post: returns the size of vector to sort

apstring GetStateofVector();
// post: returns the initial state of the vector's values
//       ordered, random or inverted

void LoadArray(TheArray & a, int size, const apstring & state);
// pre: size the length of the vector to create
//      state is the vector's starting state: ordered, random or inverted
// post: a is sized and filled appropriately

void Sort(TheArray & a, const apstring & sortName);
// pre: vector is sized and filled
//      sortName is the sort to be used: Selection, Insertion or Exchange

void Swap(Item & x, Item & y);
// pre: x and y are initialied values
// post: x nows as the value of y, and y has the old value of x

void Move(Item & x, const Item & y);
// pre: x and y are initialied values
// post: y is copied into x

bool Compare (const Item &x, const Item &y);
// pre: x and y are initialied values
// post: returns true if x < y, otherwise false

void SelectionSort(TheArray & a);
// pre: vector is sized and filled
// post: vector is sorted from least to greatest

void InsertionSort(TheArray & a);
// pre: vector is sized and filled
// post: vector is sorted from least to greatest

void ExchangeSort(TheArray & a);
// pre: vector is sized and filled
// post: vector is sorted from least to greatest

void ShowResults(const apstring & sortName, int size, 	// Debugging function
                 const apstring & state);
// pre: sortName is the name of sort used; Slection, Insertion or Exchange
//      size is the length of the vector
//      state is the vector's starting state: ordered, random or inverted
// post: Global move and compare counters are displayed about this sort
//       along with the global time in seconds

void ShowVector(const TheArray & a);
// pre: vector is sized and filled
// post: values of the vector are displayed on the screen, 10 locations per line

void SetWindowSize();		// PC Users comment out this line
// post: positions & sizes window

void Pause();				// Debugging function
// post: Suspends execution, and waits for user to type Return (Enter for PC folks)


int moveCtr, compCtr, dataWeightSize;	// Global variables
double theTime;

const int MAX = 10000;					// Maximum size of vector allowed
const char * FILENAME = "file10k.fil";

int main()
{
	TheArray a;
	apstring response;
	char r;
	
	SetWindowSize();		// PC Users comment out this line
	do{
		InitCounters();
		clrscr();			// PC Users comment out this line
		apstring sortName = GetSortName();
		int size = GetSize();
		apstring state = GetStateofVector();
		LoadArray(a, size, state);
//		ShowVector(a);		// Debugging call - make sure vector is loaded properly!
		Sort(a, sortName);
//		ShowVector(a);		// Debugging call - make sure the sort works!
		ShowResults(sortName, size, state);
		do{
			cout << "Enter another trial? ";
			cin >> response;
			r = tolower(response[0]);
			if (r != 'y' && r != 'n')
				cout <<"Illegal input" <<endl;
		} while (r != 'y' && r != 'n');
		a.resize(0);
	} while (r != 'n');
	return 0;
}

void InitCounters()
// post: sets the global move and compare counters to zero
{
	moveCtr = 0;
	compCtr = 0;
}

apstring GetSortName()
// post: returns the name of the sort to be used
//       Selection, Insertion or Exchange
{
	int choice;
	do{
		cout << "(1) Straight Insertion" << endl;
		cout << "(2) Straight Selection" << endl;
		cout << "(3) Bubble Sort with flag" << endl;
		cout <<"Choice: ";
		cin >>choice;
		if (choice < 1 || choice > 3)
			cout << "Illegal entry\n" << endl;
	} while (choice < 1 || choice > 3);
	switch (choice)
	{
		case 1:	return "Insertion";
		case 2:	return "Selection";
		case 3:	return "Exchange";
	}
	return "JUNK";
}

int GetSize()
// post: returns the size of vector to sort
{
	int size;
	do{
		cout << "\n\nEnter size of vector (2 - " << MAX << "): ";
		cin >> size;
		if (size < 2 || size > MAX)
			cout << "Illegal size\n" <<endl;
	}while (size < 2 || size > MAX);
	return size;
}

apstring GetStateofVector()
// post: returns the initial state of the vector's values
//       ordered, random or inverted
{
	int choice;
	do{ 
		cout << "\n\n(1)\tOrder" << endl;
		cout << "(2)\tRandom" << endl;
		cout << "(3)\tInverted" << endl;
		cout << "Choice: ";
		cin >> choice;
		if (choice < 1 || choice > 3)
			cout << "Illegal entry\n" <<endl;
	} while (choice < 1 || choice > 3);
	switch (choice)
	{
		case 1: return "ordered";
		case 2: return "random";
		case 3: return "inverted";
	}
	return "JUNK";
}

void LoadArray(TheArray & a, int size, const apstring & state)
// pre: size the length of the vector to create
//      state is the vector's starting state: ordered, random or inverted
// post: a is sized and filled appropriately
{
	a.resize(size);
	int i;
	ifstream in;
	switch (state[0])
	{
		case 'o': for (i = 0; i < size; i++)
					a[i].key = i;
				  break;
		case 'i': for (i = 0; i < size; i++)
					a[i].key = size - i;
				  break;
		case 'r': in.open(FILENAME);
				  if (in.fail())
				  {
				  	cout << "The file " << FILENAME << " could not be found" << endl;
				  	break;
				  }
				  for (i = 0; i < size; i++)
				  {
				  	if (!(in >> a[i].key))
				  		cout << "Input failed from file: " << FILENAME << endl;
				  }
				  in.close();
				  break;
		default:  cout << "Vector cannot be loaded" << endl;
				  break;
	}
}

void Sort(TheArray & a, const apstring & sortName)
// pre: vector is sized and filled
//      sortName is the sort to be used: Selection, Insertion or Exchange
{
	cout << "\nSorting..." << endl;
	switch (sortName[0])
	{
		case 'I': InsertionSort(a);
				  break;
		case 'S': SelectionSort(a);
				  break;
		case 'E': ExchangeSort(a);
				  break;
	}
}

void Swap(Item &x, Item &y)
// pre: x and y are initialied values
// post: x nows as the value of y, and y has the old value of x
//       Side effect: Global move counter is incremented by three
{
	Item temp = x;
	x = y;
	y = temp;
	moveCtr += 3;
}

void Move(Item & x, const Item & y)
// pre: x and y are initialied values
// post: y is copied into x
//       Side effect: Global move counter is incremented by one
{
	x = y;
	moveCtr++;
}

bool Compare (const Item & x, const Item & y)
// pre: x and y are initialied values
// post: returns true if x < y, otherwise false
//       Side effect: Global compare counter is incremented by one
{
	compCtr++;
	return x.key < y.key;
}

void SelectionSort(TheArray & a)
// pre: vector is sized and filled
// post: vector is sorted from least to greatest
//       Side effect: Global timer is computed for the execution time of this sort
{
	SysTimer stopWatch;
	stopWatch.reset();
	stopWatch.start();
		
	// Code for the Selection sort goes here
	// Remember to call the Move or Swap function to exchange data,
	// and the Compare function to compare keys
	// Outer Loop invariant is
	
	stopWatch.stop();
	theTime = stopWatch.elapsedTime();
}

void InsertionSort(TheArray & a)
// pre: vector is sized and filled
// post: vector is sorted from least to greatest
//       Side effect: Global timer is computed for the execution time of this sort
{
	SysTimer stopWatch;
	stopWatch.reset();
	stopWatch.start();
	
	// Code for the Insertion sort goes here
	// Remember to call the Move or Swap function to exchange data,
	// and the Compare function to compare keys
	// Outer Loop invariant is
	
	stopWatch.stop();
	theTime = stopWatch.elapsedTime();
}

void ExchangeSort(TheArray  & a)
// pre: vector is sized and filled
// post: vector is sorted from least to greatest
//       Side effect: Global timer is computed for the execution time of this sort
{
	SysTimer stopWatch;
	stopWatch.reset();
	stopWatch.start();
	
	// Code for the Exchange sort with a flag goes here
	// Remember to call the Move or Swap function to exchange data,
	// and the Compare function to compare keys
	// Outer Loop invariant is

	stopWatch.stop();
	theTime = stopWatch.elapsedTime();
}

void ShowResults(const apstring & sortName, int size,
				 const apstring & state)
// pre: sortName is the name of sort used; Slection, Insertion or Exchange
//      size is the length of the vector
//      state is the vector's starting state: ordered, random or inverted
// post: Global move and compare counters are displayed about this sort
//       along with the global time in seconds
{
	clrscr();
	cout << "Sorting " << size << " records in a vector that is originally "
		 << state << "." << endl
		 << "Using the " << sortName << "." << endl
		 << "Number of moves = " << moveCtr << endl
		 << "Number of comparisons = " << compCtr << endl
		 << setprecision(6) << setiosflags(ios::fixed | ios::showpoint)
		 << "Time elapsed was " << theTime << "\n\n" << endl;
}

void ShowVector(const TheArray & a)
// pre: vector is sized and filled
// post: values of the vector are displayed on the screen, 10 locations per line
{
	cout << "\nThe contents of the vector are" << setiosflags(ios::right) << endl;
	for (int i = 0; i < a.length(); i++)
	{
		cout << setw(7) << a[i].key;
		if ((i + 1) % 10 == 0)
			cout << endl;
	}
	cout << "\n" << endl;
}

void Pause()
// post: Suspends execution, and waits for user to type Return (Enter for PC folks)
{
	cout << "Hit return to continue...";
	cin.ignore();
}


// PC Users comment out this function
void SetWindowSize()
// post: positions & sizes window
{
	SIOUXSettings.toppixel = 42;
	SIOUXSettings.leftpixel = 6;
	SIOUXSettings.rows = 55;
	SIOUXSettings.columns = 128;
}