#include	<stdio.h>
#include	<stdlib.h>
#include	"ga.h"
#include	"gene.h"
#define	True	1
#define	False	0

typedef struct {
	gene	chromosome;
	double	fitness;
	int	modified;
} individual;

int	PopulationSize = 100;
int	ElitePercentage = 1;
int	Generation = 0;
selectionStrategy	SelectionStrategy = RankingSelection;
cityArrangement	CityArrangement = RandomArrangement;
double	MutationRate = 0.8;
double	CrossoverRate = 0.5;
individual	*Parent = NULL, *Children = NULL;
double	MaxFitness, MinFitness, *BestFitness = NULL, *AverageFitness;
static	double	*Roulette = NULL;
extern	double	drand48();
extern	gene	*random_gene();
extern	double	fitness();

gene	*get_ith_gene(i) { return &(Parent[i].chromosome); }

forall_gene(proc,data)
void	(*proc)(), *data;
{
	int	i;
	for (i = 0; i < PopulationSize; i ++)
		(*proc)(&Parent[i].chromosome,data);
}
static int compare_fit(x,y)
#ifdef ANSI
const void *x, *y;
#else
void	*x, *y;
#endif
{
	double	xf = ((individual *)x)->fitness,
		yf = ((individual *)y)->fitness;
	return (xf > yf)? -1 : ((xf < yf)? 1 : 0);
}
static void evaluate()
{
	int	i, newm;
	individual	*p;
	double	sum = 0., *logmem;
	static	int	log_mem_size = 0;
	for (i = 0, p = Parent; i < PopulationSize; i ++, p++) {
		if (p->modified) {
			p->fitness = fitness(&(p->chromosome));
			p->modified = False;
		}
		sum += p->fitness;
	}
	qsort(Parent,PopulationSize,sizeof(individual),compare_fit);
	if (log_mem_size <= Generation) {
		logmem = (double *)realloc(BestFitness,
			sizeof(double) * (newm = log_mem_size + 1024) * 2);
		if (logmem) {
			BestFitness = logmem;
			AverageFitness = logmem + newm;
			for (i = Generation-1; i >= 0; i --)
				AverageFitness[i] = logmem[log_mem_size+i];
			log_mem_size = newm;
		} else Generation --;
	}
	sum /= PopulationSize;
	if (Generation == 0) {
		MaxFitness = Parent->fitness;
		MinFitness = sum;
	} else {
		if (MaxFitness < Parent->fitness) MaxFitness = Parent->fitness;
		if (MinFitness > sum) MinFitness = sum;
	}
	BestFitness[Generation] = Parent->fitness;
	AverageFitness[Generation] = sum;
	displayMonitor();
}
reset_population()
{
	int	i;
	static	int	oldsize = 0;
	static	individual	*Population = NULL;
	Generation = 0;
	if (oldsize != PopulationSize) {
		Parent = Population = (individual *)realloc(Population,
			sizeof(individual) * PopulationSize * 2
			+ sizeof(double) * PopulationSize);
		if (!Parent) {
			show_message("No enough memory.");
			return False;
		}
		Children = Parent + PopulationSize;
		Roulette = (double *)(Children + PopulationSize);
		oldsize = PopulationSize;
	}
	switch (CityArrangement) {
		case RandomArrangement: random_arrange(); break;
		case DoubleCircleC: double_circle(0.15,0.45); break;
		case DoubleCircleG: double_circle(0.35,0.45);
	}
	for (i = 0; i < PopulationSize; i ++) {
		memcpy(&Parent[i].chromosome,random_gene(),sizeof(gene));
		Parent[i].modified = True;
	}
	evaluate();
}

static void roulette_init()
{
	int	i;
	double	sum = 0.;
	for (i = 0; i < PopulationSize; i ++)
		Roulette[i] = sum += Parent[i].fitness;
	for (i = 0; i < PopulationSize; i ++) Roulette[i] /= sum;
}
#define	RankingBias	0.9
static void ranking_init()
{
	int	i;
	double	sum = 0., r = 1.;
	for (i = 0; i < PopulationSize; i ++)
		Roulette[i] = sum += (r *= RankingBias);
	for (i = 0; i < PopulationSize; i ++) Roulette[i] /= sum;
}
static void selection_init()
{
	switch (SelectionStrategy) {
		case RouletteSelection: roulette_init(); break;
		case RankingSelection: ranking_init();
	}
}
static individual *select()
{
	int	i;
	double	x = drand48();
	for (i = 0; i < PopulationSize; i ++) if (Roulette[i] > x) break;
	return	Parent + i;
}
static void crossover(p1,p2,id)
individual	*p1, *p2;
int	id;
{
	int	i, j, k, m, mi, mj;
	individual	*c1 = Children + id, *c2 = Children + id + 1;
	char	*p1g = (char *)(&(p1->chromosome)),
		*p2g = (char *)(&(p2->chromosome)),
		*c1g = (char *)(&(c1->chromosome)),
		*c2g = (char *)(&(c2->chromosome));
	for (i = m = 0; i < NCities; i ++) {
		for (j = 0; j < NCities && p1g[i] != p2g[j]; j ++);
		for (k = 1; k < NCities-j && p1g[i+k] == p2g[j+k]; k ++);
		if (m < k) { m = k; mi = i; mj = j; }
	}
	if (m < 2) {
		memcpy(c1,p1,sizeof(individual));
		if (id+1 < PopulationSize) memcpy(c2,p2,sizeof(individual));
	} else {
		if (mi > 0) memcpy(c1g,p1g,mi);
		memcpy(c1g+mi,p2g+mj,k);
		memcpy(c1g+mi+k,p1g+mi+k,NCities-mi-k);
		c1->modified = True;
		if (id+1 < PopulationSize) {
			memcpy(c2g,p2g,mj);
 			memcpy(c2g+mj,p1g+mi,k);
			memcpy(c2g+mj+k,p2g+mj+k,NCities-mj-k);
			c2->modified = True;
		}
	}
}
static void mutate(ind)
individual	*ind;
{
	int	i = lrand48(), j, n = i, k;
	i = i % (NCities - 1) + 1;
	do j = lrand48() % (NCities - 1) + 1;
	while (i == j);
	if (i > j) { k = i; i = j; j = k; }
	if ((n / (NCities - 1)) & 1) {
		char	buf[NCities];
		n = j - i + 1;
		memcpy(buf,ind->chromosome.city+i,n);
		for (k = 0; k < n; k ++)
			ind->chromosome.city[i+k] = buf[n-k-1];
	} else {
		char	c = ind->chromosome.city[i];
		for (k = i; k < j; k++)
			ind->chromosome.city[k] = ind->chromosome.city[k+1];
		ind->chromosome.city[j] = c;
	}
	ind->modified = True;
}
one_generation()
{
	int	i, n_elite = PopulationSize * ElitePercentage / 100;
	int	n = PopulationSize - n_elite;
	individual	*p1, *p2, *x;
	Generation ++;
	if (n_elite) memcpy(Children,Parent,sizeof(individual)*n_elite);
	selection_init();
	for (i = n_elite; i < PopulationSize; i += 2) {
		p1 = select();
		p2 = select();
		if (drand48() < CrossoverRate) crossover(p1,p2,i);
		else {
			memcpy(Children+i,p1,sizeof(individual));
			if (i+1 < PopulationSize)
			memcpy(Children+i+1,p2,sizeof(individual));
		}
		if (drand48() < MutationRate) mutate(Children+i);
		if (i+1 < PopulationSize
		 && drand48() < MutationRate) mutate(Children+i+1);
	}
	x = Parent; Parent = Children; Children = x;
	evaluate();
	visualize();
}