#include <stdlib.h>
#include <stdio.h>
#include "tree.h"
#define DEBUG 0

static void addNode(Node *, Node );
static void traverseNode(Node, FILE *);
static void isParentFull(Node *);

char lname[16][20]={"psd-front", "psd-back", "psd-left", "psd-right",
			"obj-size", "obj-pos", "low", "high", "msd",
			"turn-left", "turn-right", "move-forw", "move-back",
			"PROGN2", "IF_LESS", "WHILE_LESS"};

Node initNode(Sym_Type type, int sym, int n_children)
{
	Node n;
	int i;

	n = (Node)malloc(sizeof(struct t_node));
	n->symbol = sym;
	n->sym_t = type;
	if ( type== func) n->capacity = NOT_FULL;
	else n->capacity = FULL;
	n->n_children = n_children;
	n->n_active_children = 0;
	n->parent = (Node)0; // null node

	n->children = (Node *)malloc(sizeof(Node) * n_children);
	for(i=0; i< n_children; i++)
		n->children[i] = (Node)malloc(sizeof(struct t_node));
	/* initialise the children nodes to NULL*/
	for(i=0; i< n_children; i++)
		n->children[i] = (Node)0;

	return n;
}

Tree initTree(void)
{
	Tree t;

	t = (Tree)malloc(sizeof(struct parse_tree) );
	t->root = (struct t_node *)0; // null root node
	t->depth = 0;

	return t;
}

// Print tree to file
void printTree(Tree t, char *string)
{
	FILE *f;

	f = fopen(string, "w");
	//check for the existence of root node
	if (t->root == NULL)
	{ printf("ERROR: root node is NULL\n");
        return;
	}
	traverseNode(t->root, f);
    fprintf(f,"\n");
    printf("\n");
	fclose(f);
}

// Same as printTree except this one appends to the file.
void printOptimalTree (Tree t, char *string, double fitness) {
	FILE *f;

	f = fopen(string, "a");
	if (f==NULL) { fprintf(stderr,"Error opening file in printOptimalTree!!\n"); exit(1); }
	if (t->root == NULL) { fprintf(stderr,"ERROR: root node is NULL\n"); exit(1); }
	traverseNode(t->root, f);
	fprintf(f, "\n");
	fprintf(f, "Fitness = %f\n\n",fitness);
	fclose(f);
}

static void traverseNode(Node t, FILE *f)
{	int i;
	if(t == NULL)
	{ fprintf(stderr,"ERROR: node is null\n");
	  return;
	}
	if (t->symbol >= LIST_START) // "pretty printing" bracket
	{ fprintf(f," ( "); printf(" (");}

	fprintf(f," %s", lname[t->symbol]);
	printf(" %s", lname[t->symbol]); // print on console as well

	if (t->symbol < LIST_START) { if (DEBUG) printf("TRAVERSE: terminal found\n"); return; }
	else // a function...
	{
		for(i=0;i<t->n_children;i++) traverseNode(t->children[i], f);
		fprintf(f, " ) ");
		printf(" ) "); // print on console as well
	}
}

/* Calculate depth does not return the depth of the tree but rather the number of LIST statements in the tree.
Depth of the tree is not needed and is now redundant. Calculating the number of LIST statements also helps to make
the CrossOver function easier. This is because the randomly generated point can be used to indicate which LIST statment
that would be crossed over. NOTE: Make sure max_depth is initialised to 0 first!!!!!! I can't error check this */
void CalculateDepth (Node n, int *max_depth) {
	int i;

	if (n->symbol < LIST_START);
	else {
		(*max_depth)++; // DON'T FORGET THE BRACKETS!!!!
		switch (n->symbol) {
			case IF_LESS:
				for (i=0;i<4;i++) CalculateDepth (n->children[i], max_depth); break;
			case WHILE_LESS:
				for (i=0;i<3;i++) CalculateDepth (n->children[i], max_depth); break;
			case PROGN2:
				for (i=0;i<2;i++) CalculateDepth (n->children[i], max_depth); break;
			default: fprintf(stderr,"ERROR: Invalid symbol!\n"); exit(1);
		}
	}
}

/* This function moves to LIST statment #listno. Once it reaches there, it returns that LIST statement in the form of a
Tree structure as t. Why return it as a Tree? Because it is easier to initialise... This function is similar to the function
CalculateDepth, coded above. NOTE: Tree has to be initialised first. cur_position also needs to be initialised to 0.
I don't know how to terminate the function straight after the correct LIST is found */
void MovetoList (Node n, int listno, int *cur_position, Tree t) {
	int i;

	if (t==NULL) { fprintf(stderr,"ERROR: Tree is not initialised!!\n"); exit(1); }
	// Not really needed since if listno = 0 then crossing over the whole function!!
	if (*cur_position == listno && listno == 0) CopyNode(&t->root, n);

	if (n->symbol < LIST_START);
	else {
		(*cur_position)++;
		if (*cur_position == listno) CopyNode(&t->root, n); // Found the correct LIST statement.
		switch (n->symbol) {
			case IF_LESS:
				for (i=0;i<4;i++) MovetoList (n->children[i], listno, cur_position, t); break;
			case WHILE_LESS:
				for (i=0;i<3;i++) MovetoList (n->children[i], listno, cur_position, t); break;
			case PROGN2:
				for (i=0;i<2;i++) MovetoList (n->children[i], listno, cur_position, t); break;
			default: fprintf(stderr,"ERROR: Invalid listno specified!\n"); exit(1);
		}
	}
}

/* Replaces the leaf of node1 with node2 at the point defined by listno and switch_point. switch_point defines which leaf
of the LIST statement to replace. Once again, cur_position needs to be initialised to 0!!!!!. */
void ReplaceTree (Node n1, Node n2, int listno, int switch_point, int *cur_position) {
	int i;
	Node temp_node;

	if (n1==NULL || n2==NULL) { fprintf(stderr, "ERROR: One of the trees not initialised!!\n"); exit(1); }
	// Not really needed since if listno = 0 then won't even call this function at all!!
	if (*cur_position == 0 && listno == 0) {
		// Saves the pointer position of n1, swicth pointer position to n2 then delete n1 i.e. temp_node
		temp_node = n1;
		n1 = n2;
		DeleteNode(temp_node);
	}
	// Doesn't quite work when listno = 0, but can bypass!

	if (n1->symbol < LIST_START);
	else {
		(*cur_position)++;
		if (*cur_position == listno) {
			temp_node = n1->children[switch_point];
			n1->children[switch_point] = n2; // Made the switch
			DeleteNode(temp_node);
		}
		switch (n1->symbol) {
			case IF_LESS:
				for (i=0;i<4;i++) ReplaceTree(n1->children[i], n2, listno, switch_point, cur_position); break;
			case WHILE_LESS:
				for (i=0;i<3;i++) ReplaceTree(n1->children[i], n2, listno, switch_point, cur_position); break;
			case PROGN2:
				for (i=0;i<2;i++) ReplaceTree(n1->children[i], n2, listno, switch_point, cur_position); break;
			default: fprintf(stderr,"ERROR: Invalid crossover point specified! Symbol is %s\n",lname[n1->symbol]); exit(1);
		}
	}
}

// Checks to see if n1 and n2 (including their children, etc) are the same. compare MUST be initialised to true!!!!!
void CompareTree (Node n1, Node n2, int *compare) {
	int i;
	if (n1->symbol != n2->symbol) *compare = false;
	if (n1->n_children != n2->n_children) *compare = false;
	else {
		for (i=0;i<n1->n_children;i++) CompareTree (n1->children[i], n2->children[i], compare);
	}
}

/* This function is a lot like CompareTree except that if the Tree contains a LIST statement, it comparing will automatically
return a false. i.e. We want to allow all LIST statements (even duplicates) to be executed */
void Compare (Node n1, Node n2, int *compare) {
	if (n1->symbol >= LIST_START || n2->symbol >= LIST_START) *compare = false;
	else	{
		if (n1->symbol == n2->symbol) *compare = true;
		else *compare = false;
	}
}

void add2Tree(Tree t, int symbol)
{
	Node n;

	if (DEBUG) printf("add2Trtee: %s (%d)\n", lname[symbol], symbol);
	if (symbol == IF_LESS)
	{	n = initNode(func, symbol, 4); // IF_LESS has 4 children
		if (DEBUG) printf("FUNC created -> 4 children\n");
	}
	else if(symbol == WHILE_LESS)
	{	n = initNode(func, symbol, 3); // WHILE_LESS has children
		if (DEBUG) printf("FUNC created -> 3 children\n");
	}
	else if(symbol == PROGN2)
	{	n = initNode(func, symbol, 2); // PROGN2 has 2 children
		if (DEBUG) printf("FUNC created -> 2 children\n");
	}
	else if(symbol<= LIST_START) // redundant: error checking
	{	n =  initNode(term, symbol, 0);
		if (DEBUG) printf("TERM created -> 0 children\n");
	}
	else { fprintf(stderr,"ERROR!! Invalid symbol\n"); exit(1); }
	// the capacity of the root node must not be full!!
	if(t->root != NULL)
	{
		if(t->root->capacity !=FULL)
			addNode( &(t->root), n);
		else if (DEBUG) printf("ROOT NODE IS FULL\n");
	}
	else addNode( &(t->root), n);
}

static void isParentFull(Node *t)
{
	Node base;
	int count=0, i;
	base = *t;

	if(base->parent== NULL) return;
	for(i=0;i<base->parent->n_children;i++)
	{
		// base itself...
		if(base->parent->children[i] != NULL)
		{
			if(base->parent->children[i]->capacity == FULL)
				count++;
		}
	}
	if(count == base->parent->n_active_children && count==base->parent->n_children)
		base->parent->capacity = FULL;
	else base->parent->capacity = NOT_FULL;

	isParentFull(&(base->parent));
}

static void addNode(Node *t, Node n)
{
	Node base;
	int i;
	base = *t;
	/* If it's a null tree, just add it here */
	if ( base == NULL )
	{
		*t = n;
		base=n;
		if (DEBUG) printf("node added\n");
		if(base->parent!=NULL)
		{
			if (DEBUG) printf("base->parent!=NULL\n");
			// CHECK: number of active children less than the number of children
			if (base->parent->n_active_children < base->parent->n_children)
			{
				if (DEBUG) printf("base->parent->n_active_chidren < base->parent->n_c\n");
				base->parent->n_active_children+=1;
				if (DEBUG) printf("base->parent->n_active = %d\n",base->parent->n_active_children);
				isParentFull(&(base));
			}
			else { printf("Adding too many children\n"); exit(1); }
		}
		else if (DEBUG) printf("Parent is null, INIT\n");
		return;
	}
	else
	{
		if (DEBUG) printf("else base!=NULL\n");
		n->parent=base;
		if (DEBUG) printf("n->parent=base\n");
		if(base->n_children!=0) //has children
		{
			for(i=0;i<base->n_children;i++)
			{
				if(base->children[i]!= NULL)
				{
				if (DEBUG) printf("child found at %d\n", i);
					/* if the children is a function, recall add position*/
					if(base->children[i]->capacity!=FULL)
					{
						if(base->children[i]->sym_t == func)
						{
						if (DEBUG) printf("func found, passing n add2node\n");
							n->parent=base->children[i];
							addNode(&(base->children[i]), n);
							return;
						}
						// maybe redudant because terminals r always full
						else if(base->children[i]->sym_t == term)
						{
							if (DEBUG) printf("term found at child!\n");

						}
						else { fprintf(stderr,"ERROR: fatal error in tree .. not term nor func\n"); exit(1); }
					}
				}
				else
				{
					if (DEBUG) printf("null found! child spot is %d\n", i);
					addNode(&(base->children[i]), n);							      return;
				}

			}

		}
		else //has no children
		{ fprintf(stderr,"ERROR: has no children.. error!\n"); exit(1);
		}
	}
}

void DeleteNode (Node n) {
	int i;
	if (n == NULL) { fprintf(stderr,"Error! Deleting an empty node!\n"); exit(1); }
	for (i=0;i<n->n_children;i++) DeleteNode (n->children[i]);
	free(n);
}

/* Make a replica of n2 into n1. Putting the * in front of n1 is ridiculous, but is needed to make it work! Don't know why...
Maybe the compiler is broken?! Thats why Yves had to do something like this in some of his functions */
void CopyNode (Node *n1, Node n2) {
	int i;

	if (n2==NULL) { fprintf(stderr,"CopyNode: Error! Copying a NULL node!!\n"); exit(1); }
	*n1 = initNode(n2->sym_t, n2->symbol, n2->n_children);

	if (*n1 == NULL) { fprintf(stderr,"Error creating node!\n"); exit(1); }
	for (i=0;i<n2->n_children;i++) 	CopyNode(&(*n1)->children[i], n2->children[i]);
}

void PrintNode (Node n1) {
	int i;
	if (n1==NULL) { fprintf(stderr,"Error! Printing a NULL node!!\n"); exit(1); }
	printf("%s ",lname[n1->symbol]);
	for (i=0;i<n1->n_children;i++) {
		PrintNode(n1->children[i]);
	}
}