#include	<stdio.h>
#include	"ga.h"

#define	PopulationSize	200
#define	CrossoverRate	0.8
#define	MutationRate	0.1

extern	double	drand48(),fitness();

individual	Population[PopulationSize*2];
individual	*Parent = Population, *Children = Population+PopulationSize;
unsigned long	Generation;
static void evaluate()
{
	int	i, k;
	double	best;
	static	double	TheBest = -1.;
	for (i = 0; i < PopulationSize; i ++) if (Parent[i].modified) {
		Parent[i].fitness = fitness(&Parent[i].chromosome);
		Parent[i].modified = False;
	}
	k = 0; best = Parent[0].fitness;
	for (i = 1; i < PopulationSize; i ++) if (Parent[i].fitness > best) {
		best = Parent[i].fitness; k = i;
	}
	if (best > TheBest) {
		printf("%d: %g ",Generation,best);
		print_gene(&Parent[k].chromosome);
		TheBest = best;
	}
}
static double	Roulette[PopulationSize];
static void selection_init()
{
	int	i;
	double	sum = 0.;
	for (i = 0; i < PopulationSize; i ++)
		Roulette[i] = sum += Parent[i].fitness;
}
static individual *select()
{
	int	i;
	double	r = (double)drand48() * Roulette[PopulationSize-1];
	for (i = 0; i < PopulationSize; i ++)
		if (Roulette[i] > r) break;
	if (i >= PopulationSize) i = PopulationSize - 1;
	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) {
		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 mutate(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];
}
main()
{
	int	i;
	individual	*p1, *p2, *x;
	for (i = 0; i < PopulationSize; i ++) {
		memcpy(&Population[i].chromosome,random_gene(),sizeof(gene));
		Population[i].modified = True;
	}
	evaluate();
	for (Generation = 0; !TerminatingCondition(); Generation ++) {
		selection_init();
		for (i = 0; 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();
	}
}