#include <stdlib.h>
#include <stdio.h>
#include <assert.h>

#include "skiplist.h"

static int IntCmp(const void *a, const void *b)
{
	return *(const int *)a - *(const int *)b;
}

#include <unistd.h>
#include <sys/time.h>
//#define TEST_SIZE 300000
#define TEST_SIZE 3000000
//#define TEST_SIZE 200000
//#define TEST_SIZE 1
#define RAND_RANGE 5000

static void printtime(struct timeval *a,struct timeval *z)
{
	struct timeval e;
	timersub(z, a, &e);
	printf("Elapsed: %lds %ldus\n", e.tv_sec, e.tv_usec);
}

/*
static void
calcdistance(skiplist l, skipnode a, skipnode z)
{
	int distance = 1;
	while ((a = skiplist_next(l, a)) && a != z)
		distance++;

	return distance;
}
*/

static void
testwalk(skiplist l)
{
	int i,last,cur;
	struct timeval a,z;
	skipnode si,head;

	head = skiplist_first(l);
	assert(head == skiplist_at(l, 0));
	assert(skiplist_last(l) == skiplist_at(l, TEST_SIZE - 1));
	printf("Position walk...\n");
	gettimeofday(&a,NULL);
	last = *(int *)skipnode_item(skiplist_first(l));
	for (i = 0; i < TEST_SIZE; i++)
	{
		si = skiplist_at(l, i);
		if (si)
		{
			cur = *(int *)skipnode_item(si);
			if (cur < last)
			{
				printf("Skiplist out of order at position %d (%d < %d)!\n", i, cur, last);
				usleep(50000);
			}
		/*	cur = calcdistance(l, head, si);
			if (cur != i)
			{
				printf("Position incorrect: wanted %d, got %d\n", i, cur);
			} */
		}
		else
		{
			printf("Skipnode at %d not found!\n", i);
		}
	}
	gettimeofday(&z,NULL);
	printtime(&a,&z);

	printf("Walk...\n");
	gettimeofday(&a,NULL);
	i = 0;
	last = *(int *)skipnode_item(skiplist_first(l));
	SKIPLIST_FOREACH(l, si)
	{
		cur = *(int *)skipnode_item(si);

		if (cur < last)
		{
			printf("Skiplist out of order at position %d (%d < %d)!\n", i, cur, last);
			usleep(50000);
		}
		i++;
		last = cur;
	}
	gettimeofday(&z,NULL);
	printtime(&a,&z);

	if (i != TEST_SIZE)
		printf("Walked %d values, expected %d\n", i, TEST_SIZE);

	printf("Walk backwards...\n");
	gettimeofday(&a,NULL);
	i = 0;
	last = *(int *)skipnode_item(skiplist_last(l));
	SKIPLIST_FOREACH_REVERSE(l, si)
	{
		cur = *(int *)skipnode_item(si);

		if (cur > last)
		{
			printf("Skiplist out of order at position %d (%d > %d)!\n", i, cur, last);
			usleep(50000);
		}
		i++;
		last = cur;
	}

	if (i != TEST_SIZE)
		printf("Backward-walked %d values, expected %d\n", i, TEST_SIZE);

	gettimeofday(&z,NULL);
	printtime(&a,&z);
}

int main(int argc, char *argv[])
{
	skiplist l;
	skipnode sd;
	int i,j,x,y,test_iter;
	int max = 2147483647;
	int values[TEST_SIZE];
	struct timeval a,z;
	(void)argc;
	(void)argv;

	_malloc_options = "A";

	printf("sizeof(skiplist) = %d\n", (int)sizeof(struct skipList));
	printf("sizeof(skipnode) = %d\n", (int)sizeof(struct skipNode));

	for (test_iter=0;test_iter < 4; test_iter++)
	{
		printf("Create...\n");
		gettimeofday(&a,NULL);
		l = skiplist_create(IntCmp, &max);

		for (i=0;i<TEST_SIZE;i++)
		{
#ifdef RANDOM_VALUES
			values[i] = random() % RAND_RANGE;
#else
			values[i] = i;
#endif
			skiplist_insert(l, values + i);
		}
		gettimeofday(&z,NULL);
		printtime(&a,&z);

		testwalk(l);

		gettimeofday(&a,NULL);
		printf("Incrementing random search...\n");
		for (i=0; i < TEST_SIZE; i++)
		{
			sd = skiplist_search(l, values + i);
			if (!sd)
			{
				printf("Not found! %d at pos %d\n", values[i], i);
				usleep(50000);
			}
			else if (*(int *)sd->item != values[i])
			{
				printf("Mismatch! %d != %d\n", values[i], *(int *)sd->item);
				usleep(50000);
			}
		}
		gettimeofday(&z,NULL);
		printtime(&a,&z);


		gettimeofday(&a,NULL);
		printf("Randomized reindex...\n");
		for (i=0; i < TEST_SIZE; i++)
		{
#ifdef RANDOM_VALUES
			x = random() % RAND_RANGE;
#else
			x = i;
#endif
			if (x % 2 == 0)
			{
				if (0 == skiplist_delete(l, values + i))
				{
					printf("Delete of value at %d (%d) failed :(\n", i, values[i]);
					usleep(50000);
				}
				else
				{
					skiplist_gc(l);
					values[i] = x;
					skiplist_insert(l, values + i);

					sd = skiplist_search(l, values + i);
					if (!sd)
					{
						printf("Just-reindexed item not found!\n");
						usleep(50000);
					}
					else if (*(int *)sd->item != values[i])
					{
						printf("Mismatch! %d != %d\n", values[i], *(int *)sd->item);
						usleep(50000);
					}
				}
			}
		}
		gettimeofday(&z,NULL);
		printtime(&a,&z);

		testwalk(l);

		gettimeofday(&a,NULL);
		printf("Incrementing random search after reindex...\n");
		for (i=0; i < TEST_SIZE; i++)
		{
			sd = skiplist_search(l, values + i);
			if (!sd)
			{
				printf("Value at %d (%d) not found!\n", i, values[i]);
				usleep(50000);
			}
			else if (*(int *)sd->item != values[i])
			{
				printf("Mismatch! %d != %d\n", values[i], *(int *)sd->item);
				usleep(50000);
			}
		}
		gettimeofday(&z,NULL);
		printtime(&a,&z);

		gettimeofday(&a,NULL);
		printf("Random overhead...\n");
		for (i=0; i < TEST_SIZE; i++)
		{
			y = random() % TEST_SIZE;
			if (y == values[0]) // make sure we're not optimized away
				printf("Meep\n");
		}
		gettimeofday(&z,NULL);
		printtime(&a,&z);

		gettimeofday(&a,NULL);
		printf("Random find...\n");
		for (i=0; i < TEST_SIZE; i++)
		{
			y = random() % TEST_SIZE;
		//	y = values[random() % TEST_SIZE];
			sd = skiplist_search(l, values + y);
			if (!sd)
			{
				printf("Not found!\n");
				usleep(50000);
			}
			else if (*(int *)sd->item != values[y])
			{
				printf("Mismatch! %d != %d\n", values[y], *(int *)sd->item);
				usleep(50000);
			}
		}
		gettimeofday(&z,NULL);
		printtime(&a,&z);

		printf("Destroy...\n");
		gettimeofday(&a,NULL);
		skiplist_destroy(l);
		gettimeofday(&z,NULL);
		printtime(&a,&z);

		printf("Array walk...\n");
		gettimeofday(&a,NULL);
		j = 0;
		for (i=0; i < TEST_SIZE; i++)
		{
			j += values[i];
		}
		gettimeofday(&z,NULL);
		printtime(&a,&z);
		printf("sum: %d\n", j);
	}

	return 0;
}