/*********************************************************************
 ***        FILE: test_struct_sort_1.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

// -------------------------------------------------------------
// Definitions and Declarations of the data we will sort


const unsigned int string_size = 256;

struct TRecord {
	char word[string_size];
	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;
}


// My data will be located in this array
TRecord *data;

// -------------------------------------------------------------
// Definitions the index type

class TIndex {
	private:
		int value;
	public:
		TIndex() { value=0; };
		TIndex(int v) {value=v; };
		operator =(int v) { return (value=v); };
		operator int() const { return value; };
		friend ostream& operator<<(ostream &out, const TIndex &i);
};

bool operator>(const TIndex &i, const TIndex &j)
{
	return data[i] > data[j];
}

ostream& operator<<(ostream &out, const TIndex &i)
{
	out<<i.value;
	return out;
}

// -------------------------------------------------------------
void print_array(TIndex a[], int N)
{
	for(int i=0;i<N;i++){
		cout<<setw(6)<<a[i]<<": ";
		print(data[a[i]]);
	}

	cout<<endl;
}


// -------------------------------------
template <class Element>
inline void exch(Element &a, Element &b)
{
  Element t = a;
  a = b;
  b = a;
}


// -------------------------------------
// 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 bsort(Element data[], int N)
{
   int p, i;
   for(p=N-1;p>0;p--)
      for(i=0;i<p;i++)
         if( data[i] > data[i+1] )
            exch(data[i], data[i+1]);
}



void main(int argc, char *argv[])
{
	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<<"Size of each element is "<<sizeof(TRecord)<<" bytes\n";
		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, string_size-1);
			data[i].word[string_size-1] = 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";
	}
	else{
		cerr<<"Error: you have to set the size of the array to sort\n";
	}

	TIndex *index = new TIndex[size];
	for(i=0;i<size;i++) index[i] = i;

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

	DWORD runtime = GetTickCount();

	bsort(index, size);

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

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

	delete data;
}