#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <string.h>
#include "test.h"
#include "dictionary.h"
#include "bst.h"

void tIntArrayPrint(int a[], int n) {
	printf("{");
	if (n > 0) {
		int i = 0;
		printf("%d", a[0]);
		for (i = 1; i < n; i++) {
			printf(", %d", a[i]);
		}
	}
	printf("}\n");
}

void tIntArrayAddressPrint(int a[], int n) {
	printf("{");
	if (n > 0) {
		int i = 0;
		printf("%d", &a[0]);
		for (i = 1; i < n; i++) {
			printf(", %d", &a[i]);
		}
	}
	printf("}\n");
}

void tVoidArrayPrint(void** a, int n, void (*printFunction)(void*)) {
	printf("{");
	if (n > 0) {
		int i = 0;
		(*printFunction)(a[0]);
		for (i = 1; i < n; i++) {
			printf(", ");
			(*printFunction)(a[i]);
		}
	}
	printf("}\n");
}

void tbPre(const BSTNodePtr x, ListPtr l) {
	if (x != NULL) {
		listAppend(l, x->key);
		tbPre(x->left, l);
		tbPre(x->right, l);
	}
}

void tbPost(const BSTNodePtr x, ListPtr l) {
	if (x != NULL) {
		tbPost(x->left, l);
		tbPost(x->right, l);
		listAppend(l, x->key);
	}
}

void tbIn(const BSTNodePtr x, ListPtr l) {
	if (x != NULL) {
		tbIn(x->left, l);
		listAppend(l, x->key);
		tbIn(x->right, l);
	}
}

int tbIntCompare(void* a, void* b) {
	return *((int*)a) - *((int*)b);
}

void tbIntPrint(void* x) {
	printf("%d", *((int*)x));
}

void tdIntPrint(void* x) {
	printf("%d", x);
}

int tbTest1(int a[], int b[], int n, 
			void (*tbOrder)(const BSTNodePtr, ListPtr),
			const char* s) {
	int result = 0;
	BSTPtr t = bstInit(tbIntCompare);
	ListPtr l = listInit();
	int i = 0;

	for (i = 0; i < n; i++)
		bstInsert(t, &a[i], &a[i]);

	(*tbOrder)(t->root, l);
	/* listPrint(l, tbIntPrint); */
	for (i = 0; i < n; i++) {
		result += (*((int*)listGet(l, i)) == b[i]);
	}

#ifdef _TVERBOSE
	printf("Testing bstInsert (using %s print)\n", s);
	printf("Expected: ");
	tIntArrayPrint(b, n);
	printf("Actual: ");
	listPrint(l, tbIntPrint);
	printf("Test %s", (result == n) ? "passed" : "failed");
	printf(" (%d points).\n", (result == n) ? n : 0);
	printf("--\n");
	return (result == n) ? n : 0;
#elif
	return (result == n) ? n : 0;
#endif
}

int tbTest4(int a[], int b[], int n) {
	int result = 0;
	BSTPtr t = bstInit(tbIntCompare);
	int i = 0;

	for (i = 0; i < n; i++)
		bstInsert(t, &a[i], &b[i]);

	for (i = 0; i < n; i++) {
		result += (bstRetrieve(t, &a[i]) == &b[i]);
	}

#ifdef _TVERBOSE
	printf("Testing bstRetrieve\n");
	printf("Expected: ");
	tIntArrayPrint(b, n);
	printf("Actual: ");
	{
		int** c = calloc(n, sizeof(int*));
		for (i = 0; i < n; i++) {
			c[i] = bstRetrieve(t, &a[i]);
		}
		tVoidArrayPrint(c, n, tbIntPrint);
	}
	printf("Test %s", (result == n) ? "passed" : "failed");
	printf(" (%d points).\n", (result == n) ? n : 0);
	printf("--\n");
	return (result == n) ? n : 0;
#elif
	return (result == n) ? n : 0;
#endif
}

int testBST(void) {
	int score = 0;

	int a[] = { 8, 5, 10, 4, 6, 7, 9, 12, 3, 11 };
	int aPre[] = { 8, 5, 4, 3, 6, 7, 10, 9, 12, 11 };
	int aPost[] = { 3, 4, 7, 6, 5, 9, 11, 12, 10, 8 };
	int aIn[] = { 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 };
	int b[] = { 28, 25, 30, 24, 26, 27, 29, 32, 23, 31 };

	score += tbTest1(a, aPre, 10, tbPre, "preorder");
	score += tbTest1(a, aPost, 10, tbPost, "postorder");
	score += tbTest1(a, aIn, 10, tbIn, "inorder");

	score += tbTest4(a, b, 10);
	score += tbTest4(b, a, 10);

	return score;
}

void tdStringPrint(void* x) {
	printf("%s", stringToCString(x));
}

void tdCStringPrint(void* x) {
	printf("%s", x);
}

void tdListToArray(ListPtr l, void** a) {
	int i;
	for (i = 0; i != listSize(l); i++) {
		a[i] = listGet(l, i);
	}
}

void tdInsertionSort(void** a, int n, int (*compare)(void*, void*)) {
	int j = 1;
	while (j < n) {
		void* k = a[j];
		int i = j - 1;
		while (i != -1 && (*compare)(a[i], k) > 0) {
			a[i+1] = a[i];
			i--;
		}
		a[i+1] = k;
		j++;
	}
}

void tdArraySort(void** a, int n, int (*compare)(void*, void*)) {
	tdInsertionSort(a, n, compare);
}

int tdArrayAreEqual(void** a, void** b, int n,
					int (*compare)(void*, void*)) {
	int result = 1;
	int i;
	for (i = 0; (i < n) && result; i++) {
		if ((*compare)(a[i], b[i]) != 0)
			result = 0;
	}
	return result;
}

int tdTest1(char **e[], int f[], int n) {
	int result = 0;
	int tempResult = 0;
	int i;
	DictionaryPtr d = dictionaryInit();
	ListPtr l;

	for (i = 0; i < n; i++) {
		int j;
		for (j = 1; j < f[i]; j++) {
			dictionaryPut(d, stringInit(e[i][0]), stringInit(e[i][j]));
		}
	}

	for (i = 0; i < n; i++) {
		int j;
		StringPtr *t1 = calloc(f[i]-1, sizeof(StringPtr));
		char **t2 = calloc(f[i]-1, sizeof(char*));
		l = dictionaryGetDefinitions(d, stringInit(e[i][0]));
		tdListToArray(l, t1);
		for (j = 0; j < f[i]-1; j++) {
			t2[j] = stringToCString(t1[j]);
		}

		tdArraySort(t2, listSize(l), strcmp);
		tempResult = (tdArrayAreEqual(
			e[i]+1, t2, f[i]-1, strcmp)) ? 5 : 0;
		result += tempResult;

#ifdef _TVERBOSE
		printf("Testing Dictionary\n");
		printf("Expected: ");
		tVoidArrayPrint(e[i]+1, listSize(l), tdCStringPrint);
		printf("Actual: ");
		tVoidArrayPrint(t2, listSize(l), tdCStringPrint);
		printf("Test %s", (tempResult) ? "passed" : "failed");
		printf(" (%d points).\n", (tempResult) ? tempResult : 0);
		printf("--\n");
#endif
	}

	return result;
}

int testDictionary(void) {
	int score = 0;
	char *e3[] = { "a", "b", "c" };
	char *e4[] = { "d", "e", "f", "g" };
	char *e5[] = { "h", "i", "j", "k", "l" };
	char *e6[] = { "m", "n", "o", "p", "q", "r" };
	char *e7[] = { "s", "t", "u", "v", "w", "x", "y" };

	char **e[] = { e4, e3, e6, e5, e7 };
	int f[] = { 4, 3, 6, 5, 7 };

	score += tdTest1(e, f, 5);

	return score;
}