/*
**  gp
**
**   genetic programming stuff
**
*/

/* 
**   Scott "Jerry" Lawrence
**   2000 January 23
**   j@absynth.com
*/

/*
** $Id: gp.c,v 1.6 2000/02/08 22:30:33 sdlpci Exp sdlpci $
**
** $Log: gp.c,v $
 * Revision 1.6  2000/02/08  22:30:33  sdlpci
 * lessened verbosity
 *
 * Revision 1.5  2000/02/08  01:13:48  sdlpci
 * population size is a variable now.
 *
 * Revision 1.4  2000/02/07  22:19:48  sdlpci
 * added more notes
 *
 * Revision 1.3  2000/01/25  17:37:01  sdlpci
 * added indent parameter to line_dump.
 * changed "infanticide" to "euthanasia"
 *
 * Revision 1.3  2000/01/25  17:37:01  sdlpci
 * added indent parameter to line_dump.
 * changed "infanticide" to "euthanasia"
 *
 * Revision 1.2  2000/01/25  05:18:13  sdlpci
 * added more gp code.
 *
 * Revision 1.1  2000/01/24  16:37:49  sdlpci
 * Initial revision
 *
*/

#include <stdio.h>
#include <stdlib.h>   /* for malloc/free */
#include <string.h>   /* for memset      */
#include "map.h"
#include "gp_strct.h"
#include "gp.h"
#include "gp_run.h"
#include "gpc_io.h"
#include "util.h"

#define POP_SIZE (10)
int population_size = 0;


GP_INDIVIDUAL ** population = NULL;

/*******************************************************************************
** creation/destruction features
*/

// setup the initial population
void gp_initial_population(void)
{
    int c;

    gp_genocide();

    population = (GP_INDIVIDUAL **) malloc(sizeof (GP_INDIVIDUAL *) * POP_SIZE);
    population_size = POP_SIZE;

    for(c=0 ; c<POP_SIZE ; c++)
    {
	population[c] = (GP_INDIVIDUAL *) malloc (sizeof (GP_INDIVIDUAL));
	if (population[c])
	{
	    population[c]->dna        = gp_line_gen();
	    population[c]->fitness    = 0;
	    population[c]->generation = 0;
	    population[c]->state      = GP_STATE_NEWBORN;

	    //gp_line_dump(population[c]->dna, 2);
	    //printf ("\n\n");
	}
    }
}


// kill & free a single individual
void gp_euthanasia(GP_INDIVIDUAL * i)
{
    if (!i) return;

    if (i->dna)
	gp_line_free(i->dna);
    free(i);
}


// kill & free all individuals
void gp_genocide(void)
{
    int p;
    if (population == NULL) return;
    for (p=0 ; p<POP_SIZE ; p++)
    {
	gp_euthanasia(population[p]);
    }
    free(population);
    population_size = 0;
}


// determine the fitness of an individual
void gp_fitness(GP_INDIVIDUAL * i)
{
    if (!i) return;
    if (i->state == GP_STATE_ADULT) return;

    i->fitness = 0;
    i->state = GP_STATE_ADULT;
}


GP_INDIVIDUAL * gp_individual_clone(GP_INDIVIDUAL * i)
{
    GP_INDIVIDUAL * t;
    if (!i) return NULL;

    t = (GP_INDIVIDUAL *) malloc(sizeof(GP_INDIVIDUAL));
    if (!t) return NULL;

    t->dna        = gp_line_clone(i->dna);
    t->fitness    = i->fitness;
    t->generation = i->generation;
    t->state      = i->state;

    return(t);
}

/*******************************************************************************
** crossover features
*/

// gotta love recursion...
GP_LINE * gp_find_id(GP_LINE * line, int id)
{
    GP_LINE * temp;

    if (!line) return NULL;
    if (line->id == id)  return line;

    temp = gp_find_id(line->line_then, id);
    if (temp == NULL)
	temp = gp_find_id(line->line_else, id);

    return temp;
}

GP_LINE * gp_line_random_node(GP_LINE * line)
{
    int nnodes  = gp_enumerate_line(line, 0);
    int thisone = random_int(0, nnodes);

    return gp_find_id(line, thisone);
}

void gp_line_swap(GP_LINE * l1, GP_LINE * l2)
{
    GP_LINE * ltemp;
    int itemp;

    if (!l1 || !l2) return;

    itemp=l1->id;          l1->id=l2->id;                  l2->id=itemp;
    itemp=l1->type;        l1->type=l2->type;              l2->type=itemp;
    itemp=l1->cond_type;   l1->cond_type=l2->cond_type;    l2->cond_type=itemp;
    itemp=l1->cond_value;  l1->cond_value=l2->cond_value;  l2->cond_value=itemp;
    itemp=l1->direction;   l1->direction=l2->direction;    l2->direction=itemp;

    ltemp=l1->line_then;   l1->line_then=l2->line_then;    l2->line_then=ltemp;
    ltemp=l1->line_else;   l1->line_else=l2->line_else;    l2->line_else=ltemp;
}


// one point destructive crossover
void gp_line_crossover_1pt_dest(GP_INDIVIDUAL * p1, GP_INDIVIDUAL * p2)
{
    if (!p1 || !p2) return;
    if (!p1->dna || !p2->dna) return;

    // swap some bits
    gp_line_swap(gp_line_random_node(p1->dna), gp_line_random_node(p2->dna));
    p1->state = GP_STATE_NEWBORN;
    p2->state = GP_STATE_NEWBORN;
}

// one point destructive crossover
void gp_line_crossover_npt_dest(GP_INDIVIDUAL * p1, GP_INDIVIDUAL * p2, int pt)
{
    while (pt--)
	gp_line_crossover_1pt_dest(p1, p2);
}


/*******************************************************************************
** misc features
*/

static int gp_compare(void * a, void * b)
{
    GP_INDIVIDUAL * ai = a;
    GP_INDIVIDUAL * bi = b;
    return (ai->fitness - bi->fitness);
}

void gp_population_sort(void)
{
    // just use the standard qsort for now
    qsort(population, population_size, sizeof(GP_INDIVIDUAL), gp_compare);
}

/*******************************************************************************
** mutation features
*/

void gp_line_mutate(GP_LINE * l)
{
    GP_LINE * temp;
    int r = random_int(0, 100);
    if (!l) return;

    if (r < 25) {
	// random direction
	l->direction  = random_int(0, 4);

    } else if (r < 50) {
	// random conditional type
	l->cond_type  = random_int(0, 5);

    } else if (r < 75) {
	// random value
	l->cond_value = random_int(1, 6);

    } else if (r < 25) {
	temp = l->line_then;
	l->line_then = l->line_else;
	l->line_else = temp;
    }
    
}



/*******************************************************************************
** dump features
*/

void gp_dump_ind(GP_INDIVIDUAL * i)
{
    if (!i) return;
    printf ("%d %d %d ", i->fitness, i->generation, i->state);
    gp_line_dump(i->dna, 2);
}

void gp_dump_pop(void)
{
    int i;

    for (i=0 ; i<POP_SIZE ; i++)
    {
	printf("%d: ", i);
	gp_dump_ind(population[i]);
    }
}


/*******************************************************************************
** sys features
*/

// initialize the whole thing...
void gp_setup(void)
{
    gp_initial_population();
    //population = gpc_load_population(population, &population_size);
    gpc_save_population(population);
}


// de-init the whole thing...
void gp_upset(void)
{
    gp_genocide();
}

void gp_run(INTMAP * map)
{
    int g;
    int i;
    int p;
    int last;
    GP_INDIVIDUAL * p1;
    GP_INDIVIDUAL * p2;
    GP_INDIVIDUAL ** np = NULL;

    for (g=0 ; g<100 ; g++)
    {
	printf("generation %d\n", g);

	// determine fitnesses.
	for (i=0; i<population_size ; i++)
	{
	    if(population[i]->state == GP_STATE_NEWBORN)
	    {
		gpr_run(population[i], map);
	    } 
	}
	gp_population_sort();

	if(1)
	{
	    gpr_run(population[0], map);
	    printf("------\n");
	    gp_dump_ind(population[0]);
	    printf("------\n");
	    map_dump(map);
	}

	// checkpoint it every so often
	//if ((g%10) == g)
	//   gpc_save_population(population);

	np = (GP_INDIVIDUAL **) malloc( sizeof(GP_INDIVIDUAL *) 
                                        * population_size );

	if (!np)
	{
	    printf("SE:  bad malloc error.\n");
	    exit(1);
	}

	// compose the next generation population.
	for (p=0 ; p<population_size/4 ; p++)
	{
	    // top 25% -- copy them over
	    np[p] = gp_individual_clone(population[p]);
	}
	last = p;

	for (p = last ; p < population_size/2 ; p++)
	{
	    // next 25% -- breed random elements
	    p1 = gp_individual_clone(population[random_int(0, population_size/2)]);
	    p2 = gp_individual_clone(population[random_int(0, population_size/2)]);
	    gp_line_crossover_npt_dest(p1, p2, 2);
	    np[p++] = p1;
	    np[p] = p2;
	}
	last = p;
	
	for (p = last ; p < population_size-(population_size/4) ; p++)
	{
	    // next 25% -- breed random elements
	    p1 = gp_individual_clone(population[random_int(0, population_size)]);
	    p2 = gp_individual_clone(population[random_int(0, population_size)]);
	    gp_line_crossover_npt_dest(p1, p2, 2);
	    np[p++] = p1;
	    np[p] = p2;
	}
	last = p;
	
	for (p = last ; p < population_size ; p++)
	{
	    // last 25% -- mutate elements
	    np[p] = gp_individual_clone(population[random_int(0, population_size)]);
	    // three mutations. why not.
	    gp_line_mutate(np[p]->dna);
	    gp_line_mutate(np[p]->dna);
	    gp_line_mutate(np[p]->dna);
	    np[p]->state = GP_STATE_NEWBORN;
	}
    }
}