/*********************************************************************
 ***        FILE: test_struct_sort.cpp
 ***        DATE: 09/28/2003
 ***      AUTHOR: Daniel Dementiev
 *** DESCRIPTION: This is just an example if the template sort.
 ***              It can be executed without any parameter and then
 ***              it reads the integer array to sort from the standard
 ***              input, or you can provide an integer number as
 ***              the program argument. In the last case the program
 ***              will generate a random array of the specified size
 ***              then will sort it.
 ***              To execute the file you need to have a "dictionary
 ***              file" - a text file with some words in it. You can
 ***              either use the one from the web-site or any one of
 ***              your own.
 ***              To execute the program run:
 ***              ...> test_struct_sort N [filename]
 ***              where N - is the size of the array to generate
 ***              and filename - is the name of the dictionary file.
 ***              The second argument is optional, if it's not specified
 ***              the program is looking for file named 'dict.txt'
 ***              Example:
 ***              ...> test_struct_sort 12000
 ***              ...> test_struct_sort 100 test_struct_sort.cpp
 *********************************************************************/

#include <iostream.h>
#include <fstream.h>
#include <iomanip.h>
#include <stdlib.h>
#include <time.h>
#include <windows.h>

//#define DEBUG_OUTPUT

struct TRecord {
	char word[16];
	int  value;
};

int operator>(const TRecord &a, const TRecord &b)
{
	return a.value > b.value;
}

void print(const TRecord &a)
{
	cout<<setw(18)<<a.word<<setw(8)<<a.value<<endl;
}

// -------------------------------------
// This function prints an integer array
// "data" of the size "N"
// -------------------------------------
void print_array(TRecord data[], int N)
{
	for(int i=0;i<N;i++){
		cout<<setw(6)<<i<<": ";
		print(data[i]);
	}

	cout<<endl;
}


// -------------------------------------
// This function sorts an array of elements
// of any type using the Bubble sort method
// Make sure you have operator ">" defined
// for these elements.
// -------------------------------------
template <class Element>
void isort(Element data[], int N)
{
	int     i, j;
	Element s;
	for(i=1;i<N;i++){
		s = data[i];
		for(j=i-1; j>=0 && data[j]>s; j--){
			data[j+1] = data[j];
		}
		if( j < i-1 ) data[j+1] = s;
	}
}

void main(int argc, char *argv[])
{
	TRecord *data;
	int      size, i;
	char     word[32], fname[256]="dict.txt";
	ifstream inp;

	if( argc > 1 ){
		if( argc > 2 ){ strncpy(fname, argv[2], 255); fname[255]=0; }
		cout<<"Using file '"<<fname<<"' as a dictionary\n";
		inp.open(fname);
		if( inp.fail() ){
		   cerr<<"Error: cannot open the dictionary file '"<<fname<<"'\n";
		   exit(1);
		}
		size = (size=atoi(argv[1])) ? size : 256;
		cout<<"Generating a random array of "<<size<<" elements ...";

		data = new TRecord[size];
		srand((unsigned)time(NULL));
		i = 0;
		while( inp>>word && i<size){
			strncpy(data[i].word, word, 15);
			data[i].word[16] = 0;
			data[i].value = rand() % (size*3);
			i++;
		}
		for( ;i<size;i++){
			strcpy(data[i].word, data[rand()%i].word);
			data[i].value = rand() % (size*3);
		}
		inp.close();
		cout<<"done\n";
	}

	#ifdef DEBUG_OUTPUT
	cout<<"The original array is: \n";
	print_array(data, size);
	#endif

	DWORD runtime = GetTickCount();

	isort(data, size);

	runtime = GetTickCount() - runtime;
	cout<<"Runtime is "<<runtime<<" msec\n";

	#ifdef DEBUG_OUTPUT
	cout<<"The sorted array is: \n";
	print_array(data, size);
	#endif

	delete data;
}