/*
*  (C) Copyright by Ariel Faigon, 1996
*  Released under the GNU GPL (General Public License) version 2
*  or any later version (http://www.gnu.org/licenses/licenses.html)
*/
#define _CRT_RAND_S
#include	<limits.h>
#include	<assert.h>
#include	<stdio.h>
#include	<stdlib.h>
#include	<string.h>
#include	<errno.h>
#include	<time.h>
#include	<windows.h>

#include	"sort.h"

static void	printarray ();

KEY_T	*ain;	// Pointer to input (unsorted) array
KEY_T	*aout;	// Pointer to reference (sorted) array
KEY_T	*a;	// Pointer to the array to be sorted

int main(int argc, char* argv[])
{
	int		i, len;
	int	max = INT_MAX;   // default
	LARGE_INTEGER	start_time, end_time;
	LARGE_INTEGER li;
	double PCFreq = 0.0;

	switch (argc) {
	case 3:
		max = atoi(argv[2]);
	case 2:
		len = atoi(argv[1]);
		if (len > 0) break;

	default:
		fprintf(stderr,"Usage:  %s array_length [range]\n", argv[0]);
		exit (1);
	}

	if ((ain = (KEY_T *)malloc((len+1)*sizeof(KEY_T))) == NULL) {
		char message[100];
		strerror_s(message, 100, errno);
		fprintf(stderr, "ain=malloc() failed: %s\n", message);
		exit (1);
	}
	if ((aout = (KEY_T *)malloc((len+1)*sizeof(KEY_T))) == NULL) {
		char message[100];
		strerror_s(message, 100, errno);
		fprintf(stderr, "aout=malloc() failed: %s\n", message);
		exit (1);
	}
	if ((a = (KEY_T *)malloc((len+1)*sizeof(KEY_T))) == NULL) {
		char message[100];
		strerror_s(message, 100, errno);
		fprintf(stderr, "a=malloc() failed: %s\n", message);
		exit (1);
	}

	QueryPerformanceFrequency(&li);
	PCFreq = (double)(li.QuadPart)/1000.0;

	a[len] = (KEY_T)INT_MAX;		// Sentinel value to mark end of array
	aout[len] = (KEY_T)INT_MAX;	// Sentinel value to mark end of array

	for (i = 0; i < len; i++)	// Fill array with random values
	{
		unsigned int r;
		rand_s(&r);
		ain[i] = (KEY_T)((r % (max + 1)) - max/2);
		//ain[i] = len-i;
	}

	memcpy(aout, ain, sizeof(KEY_T)*len);	// copy input to output array

	// sort the output array with with a reference sort routine
	shellsort(aout, len);
/*
#ifdef DEBUG
	puts("=== Unsorted array:");
	printarray(ain, len); puts("\n");
#endif
*/
	setvbuf(stdout, NULL, _IONBF, 100);

	printf("Benchmarking & verifying sort funcs on %u element array\n", len);

	QueryPerformanceCounter(&start_time);

	//
	// Sort the array
	//
	
	for (i = 0; i < 1000; i++)
	{
		memcpy(a, ain, sizeof(KEY_T)*len);    // initialize array to be sorted
		//sedgesort(a, len); 
		//dualPivotQuicksort(a,0,len);
		flashsort(a, len, 0.1);
	}

	QueryPerformanceCounter(&end_time);
	
	printf("%f milliseconds.\n", (end_time.QuadPart - start_time.QuadPart)/PCFreq);

	// Check that array is sorted
	if (!sorted(a, len)) {
		printf("Array is not sorted!\n");
	}

	// And is the same as reference sorted array
	if(!array_eq(a, aout, len)) {
		printf("Array not equal to reference array!\n");
	}

	//printarray(a, len); puts("\n");

	printf("Hit any key to exit\n");
	getc(stdin);
	return 0;
}

/*
|  static void  printarray (array, len)
|  KEY_T  array[];
|  int  len;
|
|  Abstract:	Print out array[0..len-1].
*/
static void printarray (register KEY_T  array[], register int len)
{
	register int	i;

	for (i = 0; i < len; i++)
		printf("%f ", array[i]);
}