/*--------------------------------------------------------------------------------
//
//  Filename:    Evolution.c
//
//  Author:      Mikhail Utkin
//
//  Date:        28 Apr 2014
//
//  Description: This program reads in a population of chromosomes and their
//               fitnesses from two input files and evolves a new population
//               (one generation) and writes it out to an output file.
----------------------------------------------------------------------------------*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h> /* for pow() */

#define NO_OF_GENES 783
#define POOL_SIZE   100
#define ELITE_SIZE  10

typedef struct {
    /* fitness of a chromosome */
    double fitness;

    /* order of the chromosome in the gene pool */
    int chromosome;
} Fitness;

double Random(double lo, double hi);
int    RandomInt(int lo, int hi);
void   SortListInDescendingOrder(Fitness * list, int size);

/*------------------------------------------------------------------------*/
/*-------------------------------MAIN-------------------------------------*/
/*------------------------------------------------------------------------*/
int main(int argc, char * argv[])
{
    FILE * infptr, * outfptr; /* file pointers */

    Fitness fitness[POOL_SIZE];

    double gene_pool[POOL_SIZE][NO_OF_GENES];        /* population of chromosomes */
    double gene_pool_elite[ELITE_SIZE][NO_OF_GENES]; /* the fittest chromosomes (the elite)*/
    double Xover_Xsome[NO_OF_GENES];

    int i, j, k, no_elite_genes,
        Xsome1, Xsome2, Xover_point, Xsomes_to_breed;

    /* for Cauchy distribution */
    const double PI = 3.14159265359;

    /* gene pool elite is 10% of the pool */
    no_elite_genes = POOL_SIZE/ELITE_SIZE;
    printf("no_elite_genes = %d\n", no_elite_genes);

    /* open the data file with chromosome data in it */
    infptr = fopen("chromosomes.data", "r");

    if (infptr == NULL)
    {
        printf("CANNOT open data file \"chromosomes.data\"\n");
        printf("EXITING program!\n");
        exit(1);
    }
    else
    {
        /* read the data in from the input file and initialize the population */
        for (i = 0; i < POOL_SIZE; i++)
        {
            int temp1;
            double temp2;

            /* read the chromosome # in but don't do anything with it */
            fscanf(infptr, "%d", &temp1);

            /* read in the genes for this chromosome */
            for (j = 0; j < NO_OF_GENES; j++)
            {
                fscanf(infptr, "%lf", &temp2);
                gene_pool[i][j] = temp2;
            }
        }
    }

    /* close the chromosome input file */
    fclose(infptr);

    /* open the fitness data file */
    infptr = fopen("fitness.data", "r");

    if (infptr == NULL)
    {
        printf("CANNOT open data file \"fitness.data\"\n");
        printf("EXITING program!\n");
        exit(1);
    }
    else
    {
        /* read the data in from the input file and initialize the fitnesses */
        for (i = 0; i < POOL_SIZE; i++)
        {
            int temp1;
            double temp2;

            /* read the fitness # in but don't do anything with it */
            fscanf(infptr, "%d", &temp1);

            fscanf(infptr, "%lf", &temp2);
            fitness[i].fitness = temp2;
            fitness[i].chromosome = i;
        }
    }

    /* sort the chromosome fitnesses in descending order */
    SortListInDescendingOrder(fitness, POOL_SIZE);

    /* extract the elite from the gene pool */
    for (j = 0; j < no_elite_genes; j++)
    {
        for (k = 0; k < NO_OF_GENES; k++)
        {
            gene_pool_elite[j][k] = gene_pool[fitness[j].chromosome][k];
        }
    }

    /* place the elite back to the pool in the first no_elite_genes positions */
    for (i = 0; i < no_elite_genes; i++)
    {
        for (j = 0; j < NO_OF_GENES; j++)
        {
            gene_pool[i][j] = gene_pool_elite[i][j];
        }
    }

    /* breed the fittest chromosomes and recreate the rest of the gene pool here */
    Xsomes_to_breed = POOL_SIZE - ELITE_SIZE;

    for (i = 0; i < Xsomes_to_breed; i++)
    {
        int probability;
        double x, delta;

        /* randomly pick 2 chromosomes from the elite */
	Xsome1 = RandomInt(0, (ELITE_SIZE - 1));
	Xsome2 = RandomInt(0, (ELITE_SIZE - 1));

        /* randomly pick a crossover point */
	Xover_point  = RandomInt(0, (NO_OF_GENES - 1));

        /* cross the two chromosomes over */
        for (j = 0; j < NO_OF_GENES; j++)
	{
	    if (j < Xover_point)
	    {
	        Xover_Xsome[j] = gene_pool_elite[Xsome1][j];
            }
	    else
	    {
	        Xover_Xsome[j] = gene_pool_elite[Xsome2][j];
	    }
        }

        /* mutate the new chromosome */
	for (j = 0; j < NO_OF_GENES; j++)
	{
            /* is a gene to be mutated? 1% probability */
            probability = RandomInt(0, 99);

            if (probability == 99)
            {
                x = Random(-10.0, 10.0);
                delta = (double)(1/(PI*(1 + pow(x, 2)))); /* Cauchy distribution */
                Xover_Xsome[j] = Xover_Xsome[j] + delta;
            }
        }

        /* place the new chromosome back in the gene pool */
        for (j = 0; j < NO_OF_GENES; j++)
        {
            gene_pool[no_elite_genes + i][j] = Xover_Xsome[j];
        }
    }

    /* write out the new gene pool to a file */
    outfptr = fopen("chromosomes2.data", "w");

    if (outfptr == NULL)
    {
        printf("CANNOT open data file \"chromosomes2.data\"\n");
        printf("EXITING program!\n");
        exit(1);
    }
    else
    {
        /* read the data in from the input and initialize the population */
        for (i = 0; i < POOL_SIZE; i++)
        {
            /* write out the chromosome # to the file */
            fprintf(outfptr, "%d\t", i+1);

            /* write out the genes for this chromosome */
            for (j = 0; j < NO_OF_GENES; j++)
            {
                fprintf(outfptr, "%9lf6 ", gene_pool[i][j]);
            }

            /* write out end of line */
            fprintf(outfptr, "\n");
        }
    }

    /* close the chromosome output file */
    fclose(outfptr);

    printf("Exiting...\n");

    return 0;
}

/* return a random double number in range [lo; hi] */
double Random(double lo, double hi)
{
    double random_real_number;

    random_real_number = lo + ((double) rand()/((double) RAND_MAX + 1))*(hi - lo);

    return random_real_number;
}

/* return a random integer number in range [lo; hi] */
int RandomInt(int lo, int hi)
{
    int k;
    double d;

    d = (double) rand()/((double) RAND_MAX + 1);
    k = (int)(d*(hi - lo + 1));

    return (lo + k);
}

/* sort a static array of double variables */
void SortListInDescendingOrder(Fitness * list, int size)
{
    int lh, rh, i;
    Fitness temp;

    for(lh = 0; lh < size; lh++)
    {
        rh = lh;

        /* find the largest element in the remainder of the list */
        for(i = lh; i < size; i++)
        {
            if (list[i].fitness > list[rh].fitness)
            {
                rh = i;
            }
        }

        /* swap the current and the smallest elements */
        temp.chromosome = list[lh].chromosome;
        temp.fitness = list[lh].fitness;

        list[lh].chromosome = list[rh].chromosome;
        list[lh].fitness = list[rh].fitness;

        list[rh].chromosome = temp.chromosome;
        list[rh].fitness = temp.fitness;
    }
}