#ifdef HAVE_STDLIB_H
#include <stdlib.h>
#endif
#include <string.h>

#include <values.h>
#include <math.h>
#include <sys/types.h>
#include <errno.h>
#include "yagi.h"



typedef struct {
	int parent1,parent2 ;
	char *gene ;
	double fitness ;
	} GeneRecord ;


int population_size=0 ;
int gene_length=0 ;
int elite=1 ;
int ramp=0 ;
int PRINT=1 ;
double MX ; 
/* double pmutate=0.4 ;
double pcross=0.6 ;
double psimplex=0.4 ;
double ptrans=0.2 ; */
double pmutate=0.1 ; 
double pcross=0.9 ;
double psimplex=0.5 ;
double ptrans=0.03 ;
extern int errno;

GeneRecord *Pop1=NULL,*Pop2=NULL ;

void setprobs(double pm,double pc,double ps,double pt)
{
	pmutate=pm ;
	pcross=pc ;
	psimplex=ps;
	ptrans=pt ;
}

int GA_Free(void) 
{
	int a ;
	if (Pop1!=NULL) {
		for(a=0 ; a<population_size ;a++)
			if (Pop1[a].gene!=NULL) free(Pop1[a].gene) ;
		free((char *) Pop1) ;
	}
	if (Pop2!=NULL) {
		for(a=0 ; a<population_size ;a++)
			if (Pop2[a].gene!=NULL) free(Pop2[a].gene) ;
		free((char *) Pop2) ;
	}
	return(0);
}

int GA_Error(char *ErrorMsg) 
{
	int a ;
	if (Pop1!=NULL) {
		for(a=0 ; a<population_size ;a++)
			if (Pop1[a].gene!=NULL) free(Pop1[a].gene) ;
		free(Pop1) ;
	}
	if (Pop2!=NULL) {
		for(a=0 ; a<population_size ;a++)
			if (Pop2[a].gene!=NULL) free(Pop2[a].gene) ;
		free(Pop2) ;
	}
	fprintf(stderr,"GA_LIB Error : %s \n\n",ErrorMsg) ;
	exit(1) ;
}       

double GetMax()
{
	return(MX) ;
}

void SetPrint(int a)
{
	PRINT=a; 
}
void dump_pop1(FILE *fd,int generation,double max,double aver) 
{
	int a ;

	if (PRINT==0) return ;
	fprintf(fd,"Current contents of population: generation %d\n",generation);
	for(a=0 ; a<gene_length ; a++) fprintf(fd,"-");
	fprintf(fd,"------------------\n");
	fprintf(fd,"Par1 Par2 Fitness   Code\n");
	for(a=0 ; a<population_size ; a++)
		fprintf(fd,"%4d %4d %9.4f %s\n",Pop1[a].parent1,Pop1[a].parent2,Pop1[a].fitness,Pop1[a].gene);
	fprintf(fd,"\n Maximum %9.4f Average %9.4f\n",max,aver);
	for(a=0 ; a<gene_length ; a++) fprintf(fd,"-");
	fprintf(fd,"------------------\n\n");
}        

int Initialise(int PopSize, int GeneSize) 
{
	int a,b ;
	char c[2] ;
	
	c[1]=0 ;

	/* srandom(time(&a)); */
	ramp=0 ;
	population_size=PopSize ;
	gene_length=GeneSize+1 ;
	/* limit population size */
	if ((PopSize<20)||(PopSize>1000)) GA_Error("Bad parameters to Initialise") ;
	/* Allocate memory for population 1 */
	Pop1=(GeneRecord *)calloc(PopSize,sizeof(GeneRecord)) ;
	/* Mem alloc error */
	if (Pop1==NULL) GA_Error((char *)"Memory allocation for population 1") ;
	/* Blank population array */
	for (a=0 ; a<population_size ; a++) {
		Pop1[a].gene=NULL ;
		Pop1[a].parent1=0 ;
		Pop1[a].parent2=0 ;
		Pop1[a].fitness=0.0 ;
	}
	/* Allocate memory for genes */
	for (a=0 ; a<population_size ; a++) 
		if ((Pop1[a].gene=malloc(gene_length))==NULL) 
			GA_Error("Cannot allocate gene in population 1");
	/* Allocate memory for population 2 */
	Pop2=(GeneRecord *)calloc(PopSize,sizeof(GeneRecord)) ;
	/* Mem alloc error */
	if (Pop2==NULL) GA_Error((char *)"Memory allocation for population 1") ;
	/* Blank population array */
	for (a=0 ; a<population_size ; a++) {
		Pop2[a].gene=NULL ;
		Pop2[a].parent1=0 ;
		Pop2[a].parent2=0 ;
		Pop2[a].fitness=0.0 ;
	}
	/* Allocate memory for genes */
	for (a=0 ; a<population_size ; a++) 
		if ((Pop2[a].gene=malloc(gene_length))==NULL) 
			GA_Error("Cannot allocate gene in population 2");
	/* Initialise genes */
	for (a=0 ; a<population_size ; a++) {
		for (b=0 ; b<GeneSize ; b++) 
			/* Pop1[a].gene[b]=(char)(48+(randint()&1)) ;XXXXXXXX */
			Pop1[a].gene[b]=(char)(48+(randint()&1)) ;
		Pop1[a].gene[GeneSize]=0 ;
	}

#ifdef DEBUG
	if(errno)
	{
		fprintf(stderr,"Errno =%d in Initialise() of ga_lib.c\n", errno);
		exit(1);
	}
#endif
	return (0) ;
}

void crossover(char *s1,char *s2)
{
	int point;
	char duplic ;
	
	/* only works for strings of same length */
	if (strlen(s1)!=strlen(s2)) GA_Error((char *)"Gene length mismatch for crossover") ;
	/* choose a point and swap tails of strings */
	for (point=(randint()%(strlen(s1)-2))+1 ; point <strlen(s1) ; point++)
	{
		duplic=s1[point] ;
		s1[point]=s2[point] ;
		s2[point]=duplic ;
	} 
}

void mutate(char *s1)
{
	/* flip a bit in at random point */
	s1[randint()%strlen(s1)]^=1 ;
}       

int ga_simplex(char *s1,char *s2, char *s3)
{
	int point ;
	for (point=0 ; point <(strlen(s1)-1) ; point++ )
		if (s1[point]==s2[point]) 
			s3[point]=s1[point] ;
		else
			s3[point]=s3[point]^1 ;
	return(0);
}

void swap(int *x,int *y)
{
	int t ;
	t=*x ;
	*x=*y ;
	*y=t ;
}       

void Sort() 
{
	GeneRecord T ;
	int outer,inner,moved;
	
	for (outer=population_size-1; outer>0 ; outer--)
	{
		moved=0 ;
		for (inner=0 ; inner<outer ; inner++)
		{
			if (Pop1[inner].fitness<Pop1[inner+1].fitness)
			{
				memcpy((char *) &T,(char *) &Pop1[inner],sizeof(GeneRecord)) ;
				memcpy((char *) &Pop1[inner],(char *) &Pop1[inner+1],sizeof(GeneRecord)) ;
				memcpy((char *) &Pop1[inner+1],(char *) &T,sizeof(GeneRecord)) ;
				moved=1;
			}
		}
		if (moved==0) break ;
	}
}
	
void transloc(char *gene) 
{
	int a,point,gene_size ;
	char *dup;

	gene_size=gene_length-1 ;
	point=randint()%gene_size ;
	dup=strdup(gene) ;
	for(a=0 ; a<gene_size ; a++) gene[a]=dup[(a+point)%gene_size] ;
	free(dup);
}
	
int Selection(FILE *fd, int gen)
{
	int a,b,c,d ;
	double sigma ;
	GeneRecord *temp ;
	double minfit,maxfit ;
	sigma=0.0 ;
	minfit=MAXDOUBLE ; 
	maxfit=-minfit ;
	/* minfit=1e308; maxfit=-1e308; XXXXXXXXXXXXXXXXXXXXXX */
	for(a=0 ; a<population_size ; a++ ) 
	{
		Pop1[a].fitness=Objective(Pop1[a].gene) ;
		if (Pop1[a].fitness<minfit) minfit=Pop1[a].fitness ;
		if (Pop1[a].fitness>maxfit) maxfit=Pop1[a].fitness ;
		sigma+=Pop1[a].fitness ;
	}
	MX=maxfit ;
	Sort() ;
	dump_pop1(fd,gen,maxfit,sigma/population_size);
	for(a=0 ; a<population_size ; a++ ) 
	{
		if(minfit!=maxfit)
		{
			Pop1[a].fitness=((Pop1[a].fitness-minfit)*99.0/(maxfit-minfit))+1.0 ;
		}
	}
	ramp++ ;
	sigma=0.0 ;
	for(a=0 ; a<population_size ; a++ ) 
		sigma+=Pop1[a].fitness ;
	c=0 ;
	for(a=0 ; a<population_size ; a++ )
	{
		b=(int) (Pop1[a].fitness*population_size/sigma) ;
		for (d=0 ; d<b ; d++)
			strcpy(Pop2[c++].gene,Pop1[a].gene) ;
	}       
	for(d=c ; d<population_size ; d++)
	{
			b=randint()%population_size ;
			strcpy(Pop2[d].gene,Pop1[b].gene) ;
	}
	for(a=0 ; a<population_size ;a++)
	{
		if (randreal()<pmutate) mutate(Pop2[a].gene) ;
		if (randreal()<ptrans) transloc(Pop2[a].gene) ;
	}
	temp=Pop1 ;
	Pop1=Pop2 ;
	Pop2=temp ;
	for(a=2 ; a<population_size ; a+=2 )
	{
		b=randint()%population_size ;
		c=randint()%population_size ;
		strcpy(Pop2[a].gene,Pop1[b].gene);
		strcpy(Pop2[a+1].gene,Pop1[c].gene);
		if (randreal()<pcross)
		{
			crossover(Pop2[a].gene,Pop2[a+1].gene) ;
			Pop2[a].parent2=Pop2[a+1].parent1 ;
			Pop2[a+1].parent2=Pop2[a].parent1 ;
		} else {
			Pop2[a].parent2=Pop2[a].parent1 ;
			Pop2[a+1].parent2=Pop2[a+1].parent1 ;
		}
	}
	if (randreal()<psimplex) {
		a=randint()%population_size ;   
		b=randint()%population_size ;   
		c=randint()%population_size ;   
		if (Pop1[a].fitness<Pop1[b].fitness) 
			swap(&a,&b) ;
		if (Pop1[b].fitness<Pop1[c].fitness) 
			swap(&b,&c) ;
		if (Pop1[a].fitness<Pop1[b].fitness) 
			swap(&a,&b) ;
		ga_simplex(Pop1[a].gene,Pop1[b].gene,Pop2[c].gene);
	}
	temp=Pop1 ;
	Pop1=Pop2 ;
	Pop2=temp ;
	return 0 ;
}