/* ************************************* */
/* Genetic Programming                   */
/* Originally programmed by Yves Hwang   */
/* Modified by several students          */
/* Modified by T. braunl, Sep. 2004      */
/*************************************** */

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
#include <ctype.h>

#include "gp.h"

#define MAX_LOOPS 2000

#define PERCENTAGE_GROUPA 0.15
#define PERCENTAGE_GROUPB 0.2
#define PERCENTAGE_GROUPC 0.25
#define PERCENTAGE_GROUPD 0.4

#define PROB_GROUPA 0.35
#define PROB_GROUPB 0.3
#define PROB_GROUPC 0.2
#define PROB_GROUPD 0.15

#define DEBUG 0

int POP, EVO;


/* Compare function for sorting out the fitness values. */
int comfunc (const void *a, const void *b) {
	Fitness x, y;
	x = (Fitness) malloc (sizeof (struct t_fitness) );
	y = (Fitness) malloc (sizeof (struct t_fitness) );
	x = *(Fitness *) a;
	y = *(Fitness *) b;
	if (x->fitness_value == y->fitness_value) return 0;
	if (x->fitness_value < y->fitness_value) return 1;
	else return -1;
}


// Sort the trees according to their fitness values. In this case, the higher the fitness values, the better
void SortTrees(Genetic genetic) {
	int i;
	Tree t[MAXPOP]; // Temporary storage
	int n_nodes[MAXPOP];

	for (i=0;i<POP;i++) t[i] = initTree();
	for (i=0;i<POP;i++) genetic->fitness[i]->position = i;

	qsort (genetic->fitness, POP, sizeof (struct t_fitness *), comfunc);
	// Puts the tree with the corresponding fitness value into the temporary storage
	for (i=0;i<POP;i++) {
		t[i] = genetic->t[genetic->fitness[i]->position];
		n_nodes[i] = genetic->n_nodes[genetic->fitness[i]->position];
	}
	// Now, putting it back
	for (i=0;i<POP;i++) {
		genetic->t[i] = t[i];
		genetic->n_nodes[i] = n_nodes[i];
	}
}

/* Evolution strategy: Split up population into 4 parts with each group having a separate probability. Next, pick an element
in the group. All elements in the group have equal probability */
int GetRandomElement (int cur_population) {
	int a;
	double x, percentage_group, percentage_offset;

	x = (double)rand()/RAND_MAX;
	if (x<PROB_GROUPA) {
		// Adding a small number since converting to int can lose information
		percentage_group = PERCENTAGE_GROUPA+0.001;
		percentage_offset = 0.0;
	}
	else if (x<PROB_GROUPB+PROB_GROUPA) {
		percentage_group = PERCENTAGE_GROUPB+0.001;
		percentage_offset = PERCENTAGE_GROUPA+0.001;
	}
	else if (x<PROB_GROUPC+PROB_GROUPB+PROB_GROUPA) {
		percentage_group = PERCENTAGE_GROUPC+0.001;
		percentage_offset = PERCENTAGE_GROUPA + PERCENTAGE_GROUPB+0.001;
	}
	else {
		percentage_group = PERCENTAGE_GROUPD+0.001;
		percentage_offset = PERCENTAGE_GROUPA + PERCENTAGE_GROUPB + PERCENTAGE_GROUPC+0.001;
	}

	// Generating a random element in the respective group + the group offset
	// i.e. a = rand()%n_elements_in_group + group_offset
	a = rand()%( (int)(percentage_group*(double)cur_population) ) +
	    ( (int)(percentage_offset * (double)cur_population) );
	return a;
}

int main( int argc, char** argv )
{
	int i, j, k, compare, show, cur_population; // Number of trees in the population that have not been cut off
	int a, b; // The tree no that will be crossed over
	int execute[MAXPOP]; // Check to see to execute the tree or not. i.e. Account for duplicates
	int n_carriedover; // Number of trees carried over to the next evolution
	float fitness, fit;
	char file_string[20], sysstring[30];
	FILE *best_solution, *cur_solution, *fitness_file;
	Genetic genetic;
	Tree original_tree[MAXPOP], temp_tree[MAXPOP];
	Node temp_node;
	
	if (argc<3) 
    { printf("Usage: GP <population_size> <number_generations> [show]\n");
      printf("       default: 10 10\n\n");
      POP=10; EVO=10; show=1;
    }
    else
    { sscanf(argv[1], "%d", &POP);
	  if (POP%2==1)   POP++;  // make sure to use even number
	  if (POP>MAXPOP) { printf("Max. population size is %d\n", MAXPOP); exit(1); }
	  if (POP<10)     { printf("Min. population size is %d\n", 10); exit(1); }
	  cur_population = POP; // Number of trees in the population that have not been cut off

      sscanf(argv[2], "%d", &EVO);
      printf("Genetic Prog. Engine: Pop.Size: %d, Num.Gen.: %d\n", POP, EVO);
	
      show = (argc>3); // display simulation, otherwise run minimised (default)
    }
    
	system ("mkdir Evolution");
	best_solution = fopen ("optimal.lsp", "w");
	if (best_solution == NULL) { printf("Error opening solution file!!\n"); exit(1); }
	fclose(best_solution);

    srand(time(NULL)); // init random number generator
	printf("Init genetic trees\n");
	genetic = initGeneticTrees();
	printf("Generate random trees\n");
	for (i=0;i<POP;i++) {
		generateRandomTree(genetic->t[i]);
	}

	printf("\n----------PRINTING INITIAL TREES------------\n\n");
	for (i=0;i<POP;i++) {
		printf("Tree %d: ",i);
		printTree (genetic->t[i], "runme.lsp");
	}

	// LOOP OVER GENERATIONS
	for(i=0;i<EVO;i++)
	{ printf("\n\n*********************** GENERATION NO. %d *****************************\n", i);
		for (j=0;j<POP;j++) execute[j] = true; // Set to execute all lisp programs first
		// Checking for duplicates.
		for (j=0;j<POP;j++) {
			for (k=j+1;k<POP;k++) {
				compare = true;
				CompareTree (genetic->t[j]->root, genetic->t[k]->root, &compare);
				// If they are the same, set the execute array element to false
				if (compare) {
					execute[k] = false;
					// Also make the non-executing program have low fitness
					genetic->fitness[k]->fitness_value = -100.0;
				}
			}
		}

		// LOOP OVER INDIVIDUALS
		for(j=0; j<cur_population; j++)
		{ printf("\n\n--------------- Gen.%d Prog.%d ----------------\n", i,j);
		  printTree (genetic->t[j], "runme.lsp");

		  // If it is a duplicate, make sure that it is not put through the simulator. Saves time!
		  if (!execute[j]) { printf("Program not executed. Duplicate!\n"); continue; }
		  
          fitness = 0.0;
          for(k=1;k<=4;k++)
		  { //sprintf(worldgen, "WorldGen area.wld 2000 %d", (k+1)*300);
			//system(worldgen);
			if (show) sprintf(sysstring, "Search%d.sim -r 0", k);
              else    sprintf(sysstring, "Search%d.sim -r 0 -m", k);
            system(sysstring);
			// The simulator writes the fitness to a file, 'fitness'.
			fitness_file = fopen("fitness.txt", "r");
			if (fitness_file == NULL) { printf("Error opening fitness file in main_gp!\n"); exit(1); }
			fscanf(fitness_file, "%f", &fit);
			fitness += fit;
		    fclose(fitness_file);
          }
          if (fitness < 0.0) fitness = 0.0; // If fitness is negative, it means eyebot has gone further away

          genetic->fitness[j]->position = j;
		  genetic->fitness[j]->fitness_value = fitness;
          printf("THE FITNESS FOR TREE %d = %f\n", j,genetic->fitness[j]->fitness_value);
		}
		SortTrees(genetic); // Sort the trees according to their fitness
		printf("\n");

		// Prints the trees at each generation (sorted according to fitness). So I can track their progress
		sprintf(file_string, "Evolution/evolution%d.lsp",i);
		cur_solution = fopen (file_string, "w");
		if (cur_solution == NULL) { printf("Error opening cur_solution file!!\n"); exit(1); }
		fprintf(cur_solution, "Generation %d\n\n",i);
		fclose(cur_solution);

		for (j=0; j<cur_population; j++)
        { printf("Tree %d: ",j);
          printOptimalTree (genetic->t[j], file_string, genetic->fitness[j]->fitness_value);
          printf("\n");
          printf("Fitness is %f\n\n",genetic->fitness[j]->fitness_value);
		}
		printf("\n");

		printf("Optimal solution is:\n");
		printOptimalTree(genetic->t[0], "optimal.lsp", genetic->fitness[0]->fitness_value);
		printf("\n");

		// Find the starting location of the duplicates
		for (cur_population=0;cur_population<POP;cur_population++) {
			if (execute[j] == false) break;
		}
		for (j=0;j<POP;j++) temp_tree[j] = initTree();
		for (j=0;j<POP;j++) original_tree[j] = initTree();
		// Keep a copy of the orginal tree
		if (DEBUG) printf("copy trees 0 to %d\n", POP-1);
        for (j=0;j<POP;j++) CopyNode(&original_tree[j]->root, genetic->t[j]->root);

		/* Carry over the best PERCENTAGE of the previous generation. This ensures the LISP program would
		not get worse */
		n_carriedover = (int)(POP * (PERCENTAGE+0.001));
		if (n_carriedover%2 == 1) n_carriedover++; // make sure to use an even number
		if (DEBUG) printf("copy best trees 0 to %d\n", n_carriedover-1);
        for (j=0;j<n_carriedover;j++) CopyNode(&temp_tree[j]->root, genetic->t[j]->root);

		/* For each generation, split up the trees into 4 parts... After a group is selected, another random number is
		generated to see which element of the group is selected. Each element in the group will have the
		same probability. The probabilities of each group being selected is defined above */

		for (j=n_carriedover;j<POP-1;j+=2)
		{	a = GetRandomElement (cur_population);
			do { b = GetRandomElement (cur_population);
			} while (a==b);
			CrossOver (genetic->t[a], genetic->t[b]);
			// Store the crossed over trees to a temporary location
		    if (DEBUG) printf("copy for crossover no. %d (%d,%d)\n", j,a,b);
			CopyNode(&temp_tree[j]->root, genetic->t[a]->root);
			CopyNode(&temp_tree[j+1]->root, genetic->t[b]->root);
			// Restore the trees to the orginal state
			temp_node = genetic->t[a]->root;
		    if (DEBUG) printf("copy back a\n");
			CopyNode(&genetic->t[a]->root, original_tree[a]->root);
			free(temp_node);
			temp_node = genetic->t[b]->root;
		    if (DEBUG) printf("copy back b\n");
			CopyNode(&genetic->t[b]->root, original_tree[b]->root);
			free(temp_node);
		}
		// Copy over the temporary tree back to the genetic data structure
		for (j=0;j<POP;j++)
		{   temp_node = genetic->t[j]->root;
			CopyNode(&genetic->t[j]->root, temp_tree[j]->root);
			DeleteNode(temp_node);
		}

		for (j=0;j<POP;j++)
        { DeleteNode(temp_tree[j]->root);
          DeleteNode(original_tree[j]->root);
        }

		// Prints the next set of trees that had undergone the crossovers
		printf("\n\n\n----------NEW GENERATION %d TREES------------\n",i+1);
		for (j=0;j<cur_population;j++)
		{	printf("Tree %d: ",j);
			printTree (genetic->t[j], "runme.lsp");
		}
	}
	return 0;
}