#include "types.h"
#include "main.h"
#include <cmath>
#include <ctime>
#include <iostream>
using namespace std;

/*
//Ces deux includes sont necessaires pour avoir accès à 
//srand et rand sous dev-c++
#include <stdio.h>
#include <stdlib.h>
*/

int main(void)
{
	int i, j;
	t_Point debut, fin;
	srand(time(NULL));
	// Initialisation des points de depart et d'arrivée du chemin
	debut.x = rand() % worldSize;
	debut.y = rand() % worldSize;
	fin.x = rand() % worldSize;
	fin.y = rand() % worldSize;
	cout << "Depart de (" << debut.x << "," << debut.y << ")" << endl;
	cout << "Arrivee a (" << fin.x << "," << fin.y << ")" << endl;
	// Création génération initiale, aleatoire
	t_Indiv parents[nbIndiv], enfants[nbIndiv];
	for(i = 0; i < nbIndiv; i++)
	{
		for(j = 0; j < nbGenes; j++)
		{
			parents[i].genes[j] = rand() % 4;
		}
		parents[i].longueur = eval(parents[i], debut, fin);
	}
	tri(parents);
	cout << "Gen0 " << parents[0].longueur << endl;
	// Convergence vers une solution idéale, mise en oeuvre de la genetique
	for(i = 0; i < nbGen; i++)
	{
		//Selection. Les nbIndiv - sqrt(nbIndiv) moins bon seront eradiqués
		tri(parents);

		cout << "Gen" << i << " " << parents[0].longueur << endl;
		//Reproduction deux à deux des meilleurs elements
		//Evaluation intégrée
		int nbIndivGen = 0;
		int nbSurvivants = (int)sqrt((float)nbIndiv);
		j = 0;
		while(nbIndivGen < nbIndiv)
		{
			// Equivalent de la reproduction du programme avec lui-même
			enfants[nbIndivGen] = parents[j];
			nbIndivGen++;
			// Reproduction sexuée
			for(int k = j+1; k < nbSurvivants; k++)
			{
				enfants[nbIndivGen] = reproduction(parents[j], parents[k], debut, fin);
				enfants[nbIndivGen].longueur = eval(enfants[nbIndivGen], debut, fin);
				nbIndivGen++;
				enfants[nbIndivGen] = reproduction(parents[k], parents[j], debut, fin);
				enfants[nbIndivGen].longueur = eval(enfants[nbIndivGen], debut, fin);
				nbIndivGen++;
			}
			j++;
		}

		//Transition : les enfants deviennent parents
		for(int i = 0; i < nbIndiv; i++)
			parents[i] = enfants[i];
	}
}

int eval(t_Indiv indiv, t_Point deb, t_Point fin)
{
	t_Point tmp = deb;
	int i = 0, distRestante;
	while(!(tmp.x == fin.x && tmp.y == fin.y) && i < nbGenes)
	{
		switch(indiv.genes[i])
		{
			case 0:
				tmp.x += 1;
				break;
			case 1:
				tmp.x -= 1;
				break;
			case 2:
				tmp.y  += 1;
				break;
			case 3:
				tmp.y -= 1;
		}
		if(tmp.x > worldSize) tmp.x = worldSize;
		if(tmp.x < 0) tmp.x = 0;
		if(tmp.y > worldSize) tmp.y = worldSize;
		if(tmp.y < 0) tmp.y = 0;
		i++;
	}
	if(i == nbGenes)
	{
		i += abs(tmp.x - fin.x) + abs(tmp.y - fin.y);
	}
	return i;
}

void tri(t_Indiv generation[nbIndiv])
{
	// Tri bulle, suboptimal mais rapide à implementé
	t_Indiv tmp;
	int nbPerm = 1;
	while(nbPerm > 0)
	{
		nbPerm = 0;
		for(int i = 0; i < nbIndiv - 1; i++)
		{
			if(generation[i].longueur > generation[i + 1].longueur)
			{
				nbPerm++;
				tmp = generation[i];
				generation[i] = generation[i + 1];
				generation[i + 1] = tmp;
			}
		}
	}
}

t_Indiv reproduction(t_Indiv pere, t_Indiv mere, t_Point debut, t_Point fin)
{
	int geneRencontre[2] = {-1, -1}, i, j, tmpGene[2] = {-1, -1}; // Le gène à laquelle se fera la rencontre
	// Creation de tableaux de points
	t_Point coordsPere[pere.longueur], coordsMere[mere.longueur];
	coordsPere[0] = debut;
	for(i = 1; i < pere.longueur; i++) {
		coordsPere[i] = coordsPere[i - 1];
		switch(pere.genes[i])
		{
			case 0:
				coordsPere[i].x += 1;
				break;
			case 1:
				coordsPere[i].x -= 1;
				break;
			case 2:
				coordsPere[i].y += 1;
				break;
			case 3:
				coordsPere[i].y -= 1;
		}
		if(coordsPere[i].x > worldSize) coordsPere[i].x = worldSize;
		if(coordsPere[i].x < 0) coordsPere[i].x = 0;
		if(coordsPere[i].y > worldSize) coordsPere[i].y = worldSize;
		if(coordsPere[i].y < 0) coordsPere[i].y = 0;
	}
	coordsMere[0] = debut;
	for(i = 1; i < mere.longueur; i++) {
		coordsMere[i] = coordsMere[i - 1];
		switch(pere.genes[i])
		{
			case 0:
				coordsMere[i].x += 1;
				break;
			case 1:
				coordsMere[i].x -= 1;
				break;
			case 2:
				coordsMere[i].y += 1;
				break;
			case 3:
				coordsMere[i].y -= 1;
		}
		if(coordsMere[i].x > worldSize) coordsMere[i].x = worldSize;
		if(coordsMere[i].x < 0) coordsMere[i].x = 0;
		if(coordsMere[i].y > worldSize) coordsMere[i].y = worldSize;
		if(coordsMere[i].y < 0) coordsMere[i].y = 0;
	}
	//Recherche du raccord optimal
	for(i=0; i < pere.longueur; i++)
	{
		for(j = mere.longueur -1; j >-1 && tmpGene[0] == -1; j--)
		{
			if(coordsPere[i].x == coordsMere[j].x && coordsPere[i].y == coordsMere[j].y)
			{
				tmpGene[0] = i;
				tmpGene[1] = j;
			}
			if((j - i) > geneRencontre[1] - geneRencontre[0])
			{
				geneRencontre[0] = tmpGene[0];
				geneRencontre[1] = tmpGene[1];
			}
		}
	}
	// Création du fils, sans mutation
	t_Indiv fils;
	for(i = 0; i < geneRencontre[0]; i++)
		fils.genes[i] = pere.genes[i];
	for(i = geneRencontre[1]; i < mere.longueur; i++)
		fils.genes[i - geneRencontre[1] + geneRencontre[0]] = mere.genes[i];
	fils.longueur = geneRencontre[0] + (mere.longueur - geneRencontre[1]);

	// Essai de mutation => Verdict : tip top !
	for(int i=0; i < nbGenes; i++)
	{
		if(rand() % 100 == 1)
		{
			fils.genes[i] += rand() % 4;
			fils.genes[i] %= 4;
		}
	}
	return fils;
}