/*********************************************************************
 ***        FILE: test_sort.cpp
 ***        DATE: 08/28/2003
 ***      AUTHOR: Daniel Dementiev
 *** DESCRIPTION: This is just a template for testing different sort
 ***              methods.
 ***              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.
 ***    EXAMPLES:
 ***              a)
 ***              C:\IST238> test_sort 100
 ***                 - will generate an array of 100 integer elements and
 ***                   fill it with random numbers, then sort the array.
 ***              b)
 ***              C:\IST238> test_sort
 ***              Reading data from the standard input ... 4 5 2 5 8 1
 ***              ^D
 ***                (where the numbers are typed by the user).
 ***                - will read the numbers entered by the user. Note:
 ***                  do not forget to press Ctrl+D when you are finished
 ***                  your input.
 ***              c)
 ***              C:\IST238> test_sort < my_input_file
 ***                - will read the numbers from the specified file.
 ***                  The input file should be a pure text file with
 ***                  integer numbers. These numbers will be placed in
 ***                  the array in the same order they appear in the file.
 ***       NOTES: If you want to see the sorted array uncomment the line #45
 ***              // #define DEBUG_OUTPUT
 ***              or compile the program with the following command:
 ***              C:\IST238> cl /EHsc /DDEBUG_OUTPUT test_sort.cpp
 *********************************************************************/

#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <ctime>
using namespace std;
#include <Windows.h>

// #define DEBUG_OUTPUT

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

// -------------------------------------
// Here you need to provide a real
// function that will sort the data.
// -------------------------------------
void sort(int data[], int N)
{
	return;
}

void check_if_sorted(int data[], int N)
{
	for(int i=0;i<N-1;i++)
		if( data[i] > data[i+1] ){
			cerr<<"Error: array is not sorted!\n";
			return;
		}
	cerr<<"Array is sorted OK.\n";
}

void main(int argc, char *argv[])
{
	int *data;
	int  size;

	if( argc > 1 ){
		size = (size=atoi(argv[1])) ? size : 256;
		cout<<"Generating a random array of "<<size<<" elements ...";
		data = new int[size];
		srand((unsigned)time(NULL));
		for(int i=0;i<size;i++)
			data[i] = rand() % (size*3);
		cout<<"done\n";
	}
	else{
		cout<<"Reading data from the standard input ... ";
		int n = 256;
		int i;

		data = new int[n];
		size = 0;
		while( cin>>i ){
			data[size++] = i;
			if( size == n ){
				n += 128;
				int *tmp = new int[n];
				for(i=0;i<size;i++) tmp[i] = data[i];
				delete data;
				data = tmp;
			}
		}
		cout<<"done\n";
	}

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

	DWORD runtime = GetTickCount();

	sort(data, size);

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

	#ifdef DEBUG_OUTPUT
	cout<<"The sorted array is: ";
	print_array(data, size);
	#else
	check_if_sorted(data, size);
	#endif
}