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

/* Initialises the genetic structure which holds all the trees and their respective fitness */
Genetic initGeneticTrees (void) {
	int i;
	Genetic gp;
	gp = (Genetic) malloc (sizeof (struct t_gp) );
	for (i=0;i<POP;i++) {
		gp->t[i] = initTree();
		gp->fitness[i] = (Fitness) malloc (sizeof (struct t_fitness) );
	}
	return gp;
}

void generateRandomTree(Tree t)
{	symtype n;

	if (DEBUG) printf("Random start\n");
	t->depth = 0;
	n  = (symtype) (STA_START + rand()%STA_NUM); // generate statement
	add2Tree(t, n);

	if (t->root->symbol == PROGN2)
	{ if (DEBUG) printf("Random PROGN2\n");
	  t->depth = 1;
	  n = (symtype) (STA_START + rand()% STA_ATOM_NUM);  // atom only
	  add2Tree(t, n);
          n = (symtype) (STA_START + rand()% STA_ATOM_NUM);  // atom only
	  add2Tree(t, n);
	}

	if (t->root->symbol == IF_LESS)
	{ if (DEBUG) printf("Random IF\n");
	  t->depth = 1;
	  n = (symtype) (VAL_START + rand()% VAL_NUM);  // 1. value
	  add2Tree(t,n);
	  n = (symtype) (VAL_START + rand()% VAL_NUM);  // 2. value
	  add2Tree(t,n);
	  n = (symtype) (STA_START + rand()% STA_ATOM_NUM);  // then statement
	  add2Tree(t,n);
	  n = (symtype) (STA_START + rand()% STA_ATOM_NUM);  // else statement
	  add2Tree(t,n);
	}

	if (t->root->symbol == WHILE_LESS)
	{ if (DEBUG) printf("Random WHILE\n");
	  t->depth = 1;
	  n = (symtype) (VAL_START + rand()% VAL_NUM);  // 1. value
	  add2Tree(t,n);
	  n = (symtype) (VAL_START + rand()% VAL_NUM);  // 2. value
	  add2Tree(t,n);
	  n = (symtype) (STA_START + rand()% STA_ATOM_NUM);  // do statement
	  add2Tree(t,n);
	}
}

/* This function does the crossover between tree1 and tree2.
Returns true if the crossover is successful, else false. Will return false if the type checking fails.
i.e. Trying to crossover a STATEMENT with a VALUE. If the crossover doesn't succeed, nothing happens. */
int CrossOver (Tree tree1, Tree tree2) {
	// pos = LIST number; switch = leaf position
	// synbol_type used for type checking i.e. if node is a statement or value
	int k, l, cur_position, pos1, pos2, switch1, switch2, symbol_type1, symbol_type2;
	int return_val;
	Tree n1, n2, n1_cross, n2_cross;
	Node temp_node;

	k = 0;
	l = 0;
	CalculateDepth(tree1->root, &k);
	if (k==0) pos1=0; // If depth is 0 then need to replace the whole tree
	else pos1 = rand()%(k+1);
	CalculateDepth(tree2->root, &l);
	if (l==0) pos2=0;
	else pos2 = rand()%(l+1);

	// Move to the required position and store the crossover point into n1
	cur_position=0;
	n1 = initTree();
	MovetoList(tree1->root,pos1,&cur_position,n1);
	cur_position=0;
	n2 = initTree();
	MovetoList(tree2->root,pos2,&cur_position,n2);

	if (DEBUG) {
		printf("\n\nCutting some trees!!\n");
		printf("Cutting from TREE LIST %d\n",pos1);
		printf("Cutting from TREE LIST %d\n",pos2);
		printTree (n1, "runme.lsp");
		printTree (n2, "runme.lsp");
	}

	n1_cross = initTree();
	n2_cross = initTree();
	if (pos1==0) {
		CopyNode(&n1_cross->root, n1->root);
		symbol_type1 = STATEMENT;
		DeleteNode(n1->root);
	}
	else {
		switch (n1->root->symbol) {
			// symbol_type represents the start of the statements in the respective LIST statement
			case IF_LESS: switch1 = rand()%4; symbol_type1 = 2; break;
			case WHILE_LESS: switch1 = rand()%3; symbol_type1 = 2; break;
			case PROGN2: switch1 = rand()%2; symbol_type1 = 0; break;
			default: fprintf(stderr,"ERROR: Invalid symbol!!"); exit(1);
		}
		CopyNode(&n1_cross->root, n1->root->children[switch1]);
		DeleteNode(n1->root);
		// Checks to see if n1_cross is a STATEMENT or VALUE
		if (switch1 >= symbol_type1) symbol_type1 = STATEMENT;
		else symbol_type1 = VALUE;
	}
	if (pos2==0) {
		CopyNode(&n2_cross->root, n2->root);
		symbol_type2 = STATEMENT;
		DeleteNode(n2->root);
	}
	else {
		switch (n2->root->symbol) {
			case IF_LESS: switch2 = rand()%4; symbol_type2 = 2; break;
			case WHILE_LESS: switch2 = rand()%3; symbol_type2 = 2; break;
			case PROGN2: switch2 = rand()%2; symbol_type2 = 0; break;
			default: fprintf(stderr,"ERROR: Invalid symbol!!"); exit(1);
		}
		CopyNode(&n2_cross->root, n2->root->children[switch2]);
		DeleteNode(n2->root);
		if (switch2 >= symbol_type2) symbol_type2 = STATEMENT;
		else symbol_type2 = VALUE;
	}

	if (DEBUG) { printTree (n1_cross, "runme.lsp"); printf("\n"); }
	
	if (symbol_type1 == symbol_type2) { // Only perform crossover if types match
		if (pos1==0)  {
			// Save pointer position, switch pointer, delete old tree
			temp_node = tree1->root;
			tree1->root = n2_cross->root;
			DeleteNode(temp_node);
		}
		else {
			cur_position = 0;
			ReplaceTree(tree1->root, n2_cross->root, pos1, switch1, &cur_position);
		}
		if (pos2==0)  {
			temp_node = tree2->root;
			tree2->root = n1_cross->root;
			DeleteNode(temp_node);
		}
		else {
			cur_position = 0;
			ReplaceTree(tree2->root, n1_cross->root, pos2, switch2, &cur_position);
		}
		return_val = true;
	} else return_val = false;

	return return_val;
}