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

#ifdef USE_QSORT
#define test_qsort qsort
#else
extern void test_qsort(void *a, size_t n, size_t es,
					   int (*cmp) (const void *, const void *));
#endif

static const int n_values[] = { 100, 1023, 1024, 1025 } ;
#define MAX_N 1025

typedef enum
{
	SAWTOOTH, RAND, STAGGER, PLATEAU, SHUFFLE
} DIST;
#define DIST_FIRST	SAWTOOTH
#define DIST_LAST	SHUFFLE

static const char * const distname[] = {
	"SAWTOOTH", "RAND", "STAGGER", "PLATEAU", "SHUFFLE"
};

typedef enum
{
	MCOPY, MREVERSE, MFREVERSE, MBREVERSE, MSORT, MDITHER
} MODMETHOD;
#define METH_FIRST	MCOPY
#define METH_LAST	MDITHER

static const char * const methname[] = {
	"COPY", "REVERSE", "FREVERSE", "BREVERSE", "SORT", "DITHER"
};

/* per-test counter */
static long ncompares;

/* accumulate results across tests, dist-wise */
static double sumcratio_d[DIST_LAST+1];
static double maxcratio_d[DIST_LAST+1];
static int ntests_d[DIST_LAST+1];
/* accumulate results across tests, mod-method-wise */
static double sumcratio_m[METH_LAST+1];
static double maxcratio_m[METH_LAST+1];
static int ntests_m[METH_LAST+1];


static int
int_cmp(const void *a, const void *b)
{
	int		aa = *(const int *) a;
	int		bb = *(const int *) b;

	ncompares++;

	if (aa < bb)
		return -1;
	if (aa > bb)
		return 1;
	return 0;
}


static void
test_common(DIST dist, MODMETHOD meth, void *xt, size_t n, size_t sz,
			int (*cmp) (const void *, const void *))
{
	double nlogn;
	double cratio;

	ncompares = 0;
	test_qsort(xt, n, sz, cmp);
	nlogn = n * log((double) n) / log(2.0);
	cratio = ncompares / nlogn;
	sumcratio_d[dist] += cratio;
	if (cratio > maxcratio_d[dist])
		maxcratio_d[dist] = cratio;
	ntests_d[dist]++;
	sumcratio_m[meth] += cratio;
	if (cratio > maxcratio_m[meth])
		maxcratio_m[meth] = cratio;
	ntests_m[meth]++;
}


/* work on a copy of x */
static void
test_int_copy(DIST dist, int x[], int n)
{
	int		xt[MAX_N];

	memcpy(xt, x, n * sizeof(int));
	test_common(dist, MCOPY, (void *) xt, n, sizeof(int), int_cmp);
}

/* reverse the range start <= i < stop */
static void
test_int_reverse(DIST dist, MODMETHOD meth, int x[], int n, int start, int stop)
{
	int		xt[MAX_N];
	int		i;

	memcpy(xt, x, n * sizeof(int));
	for (i = start; i < stop; i++)
	{
		xt[i] = x[stop - 1 - i];
	}
	test_common(dist, meth, (void *) xt, n, sizeof(int), int_cmp);
}

/* pre-sort using a trusted sort */
static void
test_int_sort(DIST dist, int x[], int n)
{
	int		xt[MAX_N];

	memcpy(xt, x, n * sizeof(int));
	qsort((void *) xt, n, sizeof(int), int_cmp);
	test_common(dist, MSORT, (void *) xt, n, sizeof(int), int_cmp);
}

/* add i%5 to x[i] */
static void
test_int_dither(DIST dist, int x[], int n)
{
	int		xt[MAX_N];
	int		i;

	for (i = 0; i < n; i++)
	{
		xt[i] = x[i] + i%5;
	}
	test_common(dist, MDITHER, (void *) xt, n, sizeof(int), int_cmp);
}


int
main()
{
	int		x[MAX_N];
	int		i_n;
	int		n;
	int		m;
	DIST	dist;
	MODMETHOD meth;
	int		i;
	int		j;
	int		k;
	double	sumcratio;
	int		ntests;

	for (i_n = 0; i_n < sizeof(n_values)/sizeof(n_values[0]); i_n++)
	{
		n = n_values[i_n];
		for (m = 1; m < 2*n; m *= 2)
		{
			for (dist = DIST_FIRST; dist <= DIST_LAST; dist++)
			{
				switch (dist)
				{
					case SAWTOOTH:
						for (i = j = 0, k = 1; i < n; i++)
						{
							x[i] = i % m;
						}
						break;
					case RAND:
						for (i = j = 0, k = 1; i < n; i++)
						{
							x[i] = rand() % m;
						}
						break;
					case STAGGER:
						for (i = j = 0, k = 1; i < n; i++)
						{
							x[i] = (i*m + i) % n;
						}
						break;
					case PLATEAU:
						for (i = j = 0, k = 1; i < n; i++)
						{
							x[i] = i < m ? i : m;
						}
						break;
					case SHUFFLE:
						for (i = j = 0, k = 1; i < n; i++)
						{
							x[i] = (rand()%m) ? (j+=2) : (k+=2);
						}
						break;
				}
				test_int_copy(dist, x, n); /* work on a copy of x */
				test_int_reverse(dist, MREVERSE, x, n, 0, n); /* on a reversed copy */
				test_int_reverse(dist, MFREVERSE, x, n, 0, n/2);	/* front half reversed */
				test_int_reverse(dist, MBREVERSE, x, n, n/2, n);	/* back half reversed */
				test_int_sort(dist, x, n); /* an ordered copy */
				test_int_dither(dist, x, n); /* add i%5 to x[i] */
			}
		}
	}

	for (dist = DIST_FIRST; dist <= DIST_LAST; dist++)
	{
		printf("distribution %s: max cratio %g, average %g over %d tests\n",
			   distname[dist],
			   maxcratio_d[dist],
			   sumcratio_d[dist] / ntests_d[dist],
			   ntests_d[dist]);
	}

	sumcratio = 0;
	ntests = 0;

	for (meth = METH_FIRST; meth <= METH_LAST; meth++)
	{
		printf("method %s: max cratio %g, average %g over %d tests\n",
			   methname[meth],
			   maxcratio_m[meth],
			   sumcratio_m[meth] / ntests_m[meth],
			   ntests_m[meth]);
		sumcratio += sumcratio_m[meth];
		ntests += ntests_m[meth];
	}

	printf("Overall: average cratio %g over %d tests\n",
		   sumcratio / ntests,
		   ntests);

	return 0;
}
