/*
 * MIT License
 * 
 * Copyright (c) 2017 wen.gu <454727014@qq.com>
 * 
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 * 
 * The above copyright notice and this permission notice shall be included in all
 * copies or substantial portions of the Software.
 * 
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 * SOFTWARE.
 */
 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

#include "maze_genetic.h"
#include "maze_map.h"

/************************************************************************
 * macro
 ************************************************************************/
#define LOGE printf
/************************************************************************
 * inner function
 ************************************************************************/

static int randInt(int x, int y)
{ 
    return rand() % (y - x + 1) + x; 
}

static double randFloat() 
{ 
    return (rand()) / (double)(RAND_MAX + 1.0); 
}


static void updateFitnessScore(population_t* population)
{
    int i;
    int pop_size = population->pop_size;
    int move_steps[CHROMOSOME_LENGTH];
    genome_t* genome = NULL;
    int chromosome_length = population->chromosome_length;

    int fittest_genome = 0;
    double best_fitness_score = 0;
    double total_fitness_score = 0;


    //update the fitness scores and keep a check on fittest so far
    for (i = 0; i < pop_size; ++i)
    {
        genome = &(population->genomes[i]);
        //decode each genomes chromosome into a vector of directions
        genomeDecode(genome, move_steps, chromosome_length);

        //get it's fitness score
        genome->fitness = mazeTestPlay(move_steps, chromosome_length);

        
        //update total
        total_fitness_score += genome->fitness;

        //if this is the fittest genome found so far, store results
        if (genome->fitness > best_fitness_score)
        {
            best_fitness_score = genome->fitness;

            fittest_genome = i;

            //Has we found the exit of maze?
            if (genome->fitness == 1)
            {
                //is so, stop the run
                population->is_running = 0;
            }
        }

    }//next genome

    population->fittest_genome = fittest_genome;
    population->best_fitness_score = best_fitness_score;
    population->total_fitness_score = total_fitness_score;
}

genome_t* rouletteWheelSelection(population_t* population)
{
    double fSlice = randFloat() * population->total_fitness_score;
    double total = 0.0;
    genome_t* genomes = population->genomes;
    int pop_size = population->pop_size;

    int	selected_genome = 0;

    for (int i = 0; i < pop_size; ++i)
    {

        total += genomes[i].fitness;

        if (total > fSlice)
        {
            selected_genome = i;
            break;
        }
    }

    return &genomes[selected_genome];
}

int geneCompare(gene_t gene1[], gene_t gene2[], int chromosome_length)
{
    int ret = 1;
    int i;

    for (i = 0; i < chromosome_length; i++)
    {
        if (gene2[i] != gene1[i])
        {
            ret = 0;
            break;
        }
    }

    return ret;    
}

void geneticCrossover(gene_t mum[], gene_t dad[], gene_t baby1[], gene_t baby2[],double crossover_rate, int chromosome_length)
{
    //just return parents as offspring dependent on the rate
    //or if parents are the same
    if ((randFloat() > crossover_rate) || (geneCompare(dad, mum, chromosome_length)))
    {
        baby1 = mum;
        baby2 = dad;

        return;
    }

    //determine a crossover point
    int cp = randInt(0, chromosome_length - 1);

    //swap the bits
    for (int i = 0; i < cp; ++i)
    {
        baby1[i] = mum[i];
        baby2[i] = dad[i];
    }

    for (int i = cp; i < chromosome_length; ++i)
    {
        baby1[i] = dad[i] ;
        baby2[i] = mum[i];
    }
}

void geneMutate(gene_t gene, int gene_length, double mutation_rate)
{
    int i;

    for (i = 0; i < gene_length; i++)
    {
        //do we flip this bit?
        if (randFloat() < mutation_rate)
        {
            //flip the bit
            gene ^= ((1 << (i - 1)));
        }
    }
}

void geneticMutate(gene_t genes[], int chromosome_length, double mutation_rate)
{
    int i;
    for (i = 0; i < chromosome_length; i++)
    {
        geneMutate(genes[i], GENE_LENGTH, mutation_rate);
    }//next bit
}
/************************************************************************
 * API
 ************************************************************************/

void genomeInitialize(genome_t* genome, int chromosome_length)
{
    gene_t* genes = genome->genes;

    

    if (genes)
    {
        int i = 0;
        for (; i < chromosome_length; i++)
        {
            genes[i] = randInt(0, 3); /** generate random number range 0 - 3 */
        }

        genome->fitness = 0;
    }
    else
    {
        LOGE("alloc chromosome failed\n");
    }
}


void genomeDecode(genome_t* genome, int move_steps[], int chromosome_length)
{
    gene_t* genes = genome->genes;

    if (genes)
    {
        int i;
        for (i = 0; i < chromosome_length; i++)
        {
            move_steps[i] = genes[i];
        }
    }
}


void populationInitialize(population_t* population, int pop_size,
                          int gene_length, int chromosome_length,
                          double crossover_rate, double mutation_rate)
{
    int i;
    for (i = 0; i < pop_size; i++)
    {
        genome_t* genome = &(population->genomes[i]);
        genomeInitialize(genome, chromosome_length);
    }

    population->pop_size = pop_size;
    population->gene_length = gene_length;
    population->chromosome_length = chromosome_length;
    population->crossover_rate = crossover_rate;
    population->mutation_rate = mutation_rate;
    population->best_fitness_score = 0.0;
    population->fittest_genome = 0;
    population->generation = 0;
    population->is_running = 1;
}

unsigned int populationEpoch(population_t* population)
{
    updateFitnessScore(population);

    if (population->is_running == 1)
    {
        //Now to create a new population
        int baby_count = 0;
        int pop_size = population->pop_size;
        int chromosome_length = population->chromosome_length;

        genome_t* org_genomes = population->genomes;
    
        //create some storage for the baby genomes 
        genome_t baby_genomes[POPULATION_SIZE]; /** the population of genomes */

        while (baby_count < pop_size)
        {
            //select 2 parents
            genome_t* mum = rouletteWheelSelection(population);
            genome_t* dad = rouletteWheelSelection(population);

            //operator - crossover
            genome_t baby1, baby2;
            geneticCrossover(mum->genes, dad->genes, baby1.genes, baby2.genes, population->crossover_rate, chromosome_length);

            //operator - mutate
            geneticMutate(baby1.genes, chromosome_length, population->mutation_rate);
            geneticMutate(baby2.genes, chromosome_length, population->mutation_rate);

            //add to new population
            baby_genomes[baby_count++] = baby1;
            baby_genomes[baby_count++] = baby2;
        }

        //copy babies back into starter population
        memcpy(org_genomes, baby_genomes, sizeof(genome_t) * POPULATION_SIZE);

        //increment the generation counter
        population->generation++;
    }
 
    return (population->is_running == 1) ? 0 : 1;
}