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

int	PopulationSize = 100;
int	ElitePercentage = 1;
int	Generation = 0;
selectionStrategy	SelectionStrategy = RankingSelection;
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();

individual	*get_ith_individual(i) { return &Parent[i]; }

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) fitness(p);
		sum += p->fitness;
	}
	qsort(Parent,PopulationSize,sizeof(individual),compare_fit);
	if (log_mem_size <= Generation) {
		newm = log_mem_size + 1024;
		logmem = (double *)realloc(BestFitness,
			sizeof(double) * newm * 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;
	}
	init_table();
	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 *selection()
{
	int	i;
	double	x = drand48();
	for (i = 0; i < PopulationSize; i ++) if (Roulette[i] > x) break;
	return	Parent + i;
}
static int compare_int(a,b) int *a, *b; { return (*a < *b); }
static void crossover(p1,p2,id)
individual	*p1, *p2;
int	id;
{
	int	i, j, k;
	int	a[NTasks], b[NTasks/2];
	Task	*ac, *bc;
	individual	*c1 = Children + id, *c2 = Children + id + 1;
	for (i = 0; i < NTasks; i ++) a[i] = i;
	for (i = 0; i < NTasks / 2; i ++) {
		j = (lrand48() % (NTasks - i)) + i;
		if (j != i) { k = a[j]; a[j] = a[i]; a[i] = k; }
	}
	for (i = 0; i < NTasks / 2; i ++) {
		ac = p1->chromosome.task + a[i];
		for (j = 0; j < NTasks; j ++) {
			bc = p2->chromosome.task + j;
			if (ac->job == bc->job
			 && ac->machine == bc->machine) break;
		}
		b[i] = j;
	}
	qsort(a, NTasks/2, sizeof(int), compare_int);
	qsort(b, NTasks/2, sizeof(int), compare_int);
	memcpy(&c1->chromosome,&p1->chromosome,sizeof(gene));
	for (i = 0; i < NTasks/2; i ++)
		c1->chromosome.task[a[i]] = p2->chromosome.task[b[i]];
	c1->modified = True;
	if (id + 1 < PopulationSize) {
		memcpy(&c2->chromosome,&p2->chromosome,sizeof(gene));
		for (i = 0; i < NTasks/2; i ++)
			c2->chromosome.task[b[i]] = p1->chromosome.task[a[i]];
		c2->modified = True;
	}
}
static void mutate(ind)
individual	*ind;
{
	int	i, j, n, k;
	Task	c;
	i = lrand48() % NTasks;
	do j = lrand48() % NTasks;
	while (i == j);
	c = ind->chromosome.task[i];
	if (i < j) for (k = i; k < j; k++)
		ind->chromosome.task[k] = ind->chromosome.task[k+1];
	else for (k = i; k > j; k --)
		ind->chromosome.task[k] = ind->chromosome.task[k-1];
	ind->chromosome.task[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 = selection();
		p2 = selection();
		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();
}