#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 = 0;
int	Generation = 0;
selectionStrategy	SelectionStrategy = RouletteSelection;
codingMethod		CodingMethod = BinaryCoding;
double	MutationRate = 0.01;
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();

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();
}
static void set_graycode(code)
unsigned char	code[];
{
	int	i, j, n;
	int	inv[256];
	inv[0] = 0;
	for (i = 0, n = 1; i < 256; n *= 2, i += n)
	for (j = 0; j < n; j ++) inv[j+n] = inv[n-1-j] + n;
#ifdef DEBUG
	for (i = 0; i < 256; i ++) {
		for (j = 0, n = 0x80; j < 8; j ++, n >>= 1)
			putchar((inv[i]&n)?'1':'0');
		putchar((i%8==7)?'\n':' ');
	}
#endif
	for (i = 0; i < 256; i ++) code[inv[i]] = i;
}
short short_int_value(x)
short	x;
{
	static unsigned char graycode[256] = { 0xff };
	switch (CodingMethod) {
		case BinaryCoding: case IntegerCoding:
		return x;
		case GrayCoding:
		if (graycode[0] == 0xff) set_graycode(graycode);
		return (short)((int)
		 ((graycode[((unsigned short)x) >> 8] << 8)
		 | graycode[((unsigned short)x) & 0xff]) - MAXVALUE - 1);
	}
}
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;
	}
	for (i = 0; i < PopulationSize; i ++) {
		Parent[i].chromosome = *random_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	p = lrand48() % (sizeof(gene) * 8 - 1) + 1;
	int	byte = p / 8, bit = p % 8 - 1, k, n;
	individual	*c1 = Children + id, *c2 = Children + id + 1;
	unsigned char
		*p1g = (unsigned char *)(&(p1->chromosome)),
		*p2g = (unsigned char *)(&(p2->chromosome)),
		*c1g = (unsigned char *)(&(c1->chromosome)),
		*c2g = (unsigned char *)(&(c2->chromosome));
	static unsigned char	mask[] = {
		0x7f, 0x3f, 0x1f, 0x0f, 0x07, 0x03, 0x01
	};
	if (id+1 < PopulationSize) c2g = NULL;
	if (byte > 0) {
		memcpy(c1g,p1g,byte);
		if (c2g) memcpy(c2g,p2g,byte);
	}
	k = byte;
	if (bit >= 0 && CodingMethod != IntegerCoding) {
		c1g[k] = (p1g[k] & ~mask[bit]) | (p2g[k] & mask[bit]);
		if (c2g) c2g[k] = (p2g[k] & ~mask[bit]) | (p1g[k] & mask[bit]);
		k ++;
	}
	n = sizeof(gene) - k;
	if (n > 0) { memcpy(c1g+k,p2g+k,n); if (c2g) memcpy(c2g+k,p1g+k,n); }
	c1->modified = True; if (c2g) c2->modified = True;
}
static void bit_mutation(ind)
individual	*ind;
{
	int	p = lrand48() % (sizeof(gene) * 8);
	unsigned char	*g = (unsigned char *)(&(ind->chromosome));
	static unsigned char    mask[] = {
		0x80, 0x40, 0x20, 0x10, 0x08, 0x04, 0x02, 0x01
	};
	g[p / 8] ^= mask[p % 8];
}
static void integer_mutation(ind)
individual	*ind;
{
	int	p = lrand48();
	unsigned char	*g = (unsigned char *)(&(ind->chromosome));
	g[(p / 128) % sizeof(gene)] += (p % 128) - 64;
}
static void mutate(ind)
individual	*ind;
{
	switch (CodingMethod) {
		case BinaryCoding: case GrayCoding:
		bit_mutation(ind); break;
		case IntegerCoding:
		integer_mutation(ind); break;
	}
	ind->modified = True;
}
one_generation()
{
	int	i, n_elite = PopulationSize * ElitePercentage / 100;
	individual	*p1, *p2, *x;
	Generation ++;
	if (n_elite) memcpy(Children,Parent,sizeof(individual)*n_elite);
	selection_init(n_elite);
	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();
}