/*-------------------------------------------------------------*/
/* Written by J. Katajainen and J. L. Träff                    */
/* February & March, 1997                                      */
/*                                                             */
/* Compiled at DIKU as follows:                                */
/* %gcc -O4 -o test ftestbed.c -lm                             */
/*-------------------------------------------------------------*/

/* At DIKU: */

#define random() CombTaus()
#define srandom(s) setrangen2(s,s)
#define frandom() frand()

#define false 0
#define true 1

#define element float

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>

#include "random.c"
#include "linearprobingsort.c"
#include "linearprobingsort.in-place.c"
#include "linearprobingsort.in-place.adaptive.c"
#include "bucketsort.c"
#include "quicksort.c"
#include "heapsort.bottom-up.c"

/* timers */

clock_t c_start, c_stop;

static void generate(char type, element a[], int n, unsigned long seed)
{	
	int i,j;
        float s;

	switch (type) {
	case 'i':
		printf("Generating an increasing sequence of %d numbers ...\n",n);
		for (i=0; i<n; i++) a[i] = (element) i;
		break;
	case 'd':
		printf("Generating an decreasing sequence of %d numbers ...\n",n);
		for (i=0; i<n; i++) a[n-i-1] = (element) i;
		break;
        case 'z':
                printf("Generating %d numbers all equal to zero ...\n",n);
                for (i=0; i<n; i++) a[i] = (element) 0;
                break;
        case 'e':
                printf("Generating %d exponentially distributed random numbers ...\n",n);
                for (i=0; i<n; i++) {
			s =  -log(1-frandom()); 
			a[i] = (element) s;}
                break;
	case 'n':
		printf("Generating %d normally distributed random numbers ...\n",n);
		for (i=0; i<n; i++) {
			s = 0.0;
			for (j=0; j<12; j++) s += frandom();
			a[i] = (element) s - 6.0;}
		break;
	default:
		printf("Generating %d uniformly distributed random numbers ...\n",n);
		srandom(seed);
		for (i=0; i<n; i++) a[i] = frandom();
		break;
	}
}

static int sorted(char type, element a[], int n)
{	
	int i;

	switch (type) {
	case 'i':
	case 'd':
		for (i=0; i<n; i++) if (a[i]!= (element) i) return false;
		break;
	default:
		for (i=0; i<n-1; i++) if (a[i]>a[i+1]) return false;
		break;
	}
	return true;
}

static void show(element a[], int n)
{	
	int i;
	for (i=0; i<n; i++) printf("%d ",a[i]);
	printf("\n");
}

main(int argc, char *argv[])
{
	unsigned long seed;
	char type;

	int i, n, u;
	element *a, *b;
	int *c, *d;

	/* parse options */

	if (argc==1||argc>4) {
		fprintf(stderr,"Usage: %s <n> [<type>] [<seed>]\n",argv[0]);
		fprintf(stderr,"       where <type> is one of the following\n");
                fprintf(stderr,"       'u' uniformly distributed numbers (default)\n");
                fprintf(stderr,"       'n' normally distributed numbers\n");
                fprintf(stderr,"       'e' exponentially distributed numbers\n");
                fprintf(stderr,"       'i' increasing sequence of numbers\n");
                fprintf(stderr,"       'd' decreasing sequence of numbers\n");
                fprintf(stderr,"       'z' all zeros.\n");
		exit(1); 
	}
	else {
		n = atoi(argv[1]);
		if (argc>=3) type = argv[2][0];
		else type = 'u';
		if (argc==4) seed = atoi(argv[3]);
		else seed = 1;
	}

	a = (element *) malloc(n*sizeof(element));
	u = 1.6*n;  /* 2.4*n would be safe but more time-consuming */
	b = (element *) malloc(u*sizeof(element));
	c = (int *) malloc(n*sizeof(int));
	d = (int *) malloc(n*sizeof(int));


	/* Experiments */

	printf("\nLINEAR PROBING SORT:\n");
	generate(type,a,n,seed);
	c_start = clock();
	linear_probing_sort(a,b,n,u);
	c_stop = clock();
	if (!sorted(type,a,n))
		printf("*** Sorting error ***\n");
	printf("CPU time (ms): %ld\n",(c_stop-c_start)/1000);

	printf("\nIN-PLACE LINEAR PROBING SORT:\n");
	generate(type,a,n,seed);
	c_start = clock();
	in_place_linear_probing_sort(a,n);
	c_stop = clock();
	if (!sorted(type,a,n))
		printf("*** Sorting error ***\n");
	printf("CPU time (ms): %ld\n",(c_stop-c_start)/1000);

	printf("\nADAPTIVE IN-PLACE LINEAR PROBING SORT:\n");
	generate(type,a,n,seed);
	c_start = clock();
	adaptive_in_place_linear_probing_sort(a,n);
	c_stop = clock();
	if (!sorted(type,a,n))
		printf("*** Sorting error ***\n");
	printf("CPU time (ms): %ld\n",(c_stop-c_start)/1000);

	printf("\nBUCKETSORT:\n");
	generate(type,a,n,seed);
	c_start = clock();
	bucketsort(a,b,c,d,n);
	c_stop = clock();
	if (!sorted(type,a,n))
		printf("*** Sorting error ***\n");
	printf("CPU time (ms): %ld\n",(c_stop-c_start)/1000);

	printf("\nQUICKSORT:\n");
	generate(type,a,n,seed);
	c_start = clock();
	quicksort(a,n);
	c_stop = clock();
	if (!sorted(type,a,n))
		printf("*** Sorting error ***\n");
	printf("CPU time (ms): %ld\n",(c_stop-c_start)/1000);

	printf("\nBOTTOM-UP HEAPSORT:\n");
	generate(type,a,n,seed);
	c_start = clock();
	bottom_up_heapsort(a,n);
	c_stop = clock();
	if (!sorted(type,a,n))
		printf("*** Sorting error ***\n");
	printf("CPU time (ms): %ld\n",(c_stop-c_start)/1000);
}