#include <string.h>
#include <time.h>
#include <stdlib.h>
#include <math.h>
#include <stdio.h>
#include <float.h>

#ifndef RAND_MAX
#define RAND_MAX 32767
#endif;

#ifndef MAX_NUMBER
#define MAX_NUMBER 0xffffff
#endif;

struct Solution{
	int *a;
	int *Z;
	int *ZDelta;
	double F;
	double **SF;
	double **SFDelta;
	double *WCV;
	double **C;
	int num;
	double TWCV;
	double TWCVDelta;
	double **d;
	double e;
	int *change;
	double *dmax;
	double *dmin;
	int *kmin;
	int *kmax;
	double *dsum;
	int used;
};

void FGKA();
void Init();
void Selection();
void Mutation();
void KMO();
void Eval(int);
void AccumulateUpdate(int, int, int, int);
void IncrementalUpdate(int);
void CopySolution(struct Solution *, struct Solution *);
double* gather(double*,int);
int Distribution(double*, int);
char* getline(FILE*);
int LoadData (const char*);
int Export(const char*);

int* match1;
int* match2;
double **X; //Pattern
struct Solution *S;
struct Solution SO;

int K = 0; // Cluster number
int N = 0; // Pattern number
int D = 0; // Feature number
int M = 0; // Population number
double TWCV;
double TWCVMax;

int G = 0;  // Maximum number of Generation
float mp;   //mutation Probability
int *origin;
FILE* outputfile;

void main(int argc,char **argv)
{
	char filename[30];

	printf("\nPlease input the file name for processing: ");
	scanf("%s", filename);
	strcat(filename,"\0");
	printf("\nPlease enter the number of Clusters: ");
	scanf("%d",&K);
	printf("\nPlease enter the number of Populations: ");
	scanf("%d",&M);
	printf("\nPlease enter the number of maximum generations: ");
	scanf("%d",&G);
	printf("\nPlease enter the mutation probability: ");
	scanf("%f",&mp);

	if ( LoadData(filename) == -1 ) exit(1);

//	for(i=0; i<10; i++)
        FGKA();

	Export(filename);

	free(X);

}

void FGKA()
{
	int tim1, tim2;
	int n, i, m;

	tim1 = time(0);

	SO.TWCV = MAX_NUMBER;
	Init();

	for(i=0; i<G; i++)
	{
		Selection();

		Mutation();

		KMO();

		for(m=0; m<M; m++)
		{
			if(SO.TWCV > S[m].TWCV)
			{
				SO.TWCV = S[m].TWCV;
				for(n=0; n<N; n++)
					SO.a[n] = S[m].a[n];
			}
		}

		tim2 = time(0);
		printf("iteration %d\t%f\t%d\n",i, SO.TWCV, tim2 - tim1);
	}

//	fprintf(outputfile,"%f\n", SO.TWCV);
	//	printf("TWCV: %f\t%f\n", Twcv(SO.a), SO.TWCV);

	tim2 = time(0);
	printf("%d", tim2 - tim1);
	free(S);

}

void Init()
{
	int n, m, k, d;

	TWCVMax = 0;

	S = (struct Solution*)malloc((size_t)M*sizeof(struct Solution));
	match1 = (int*)malloc((size_t)M*sizeof(int));
	match2 = (int*)malloc((size_t)M*sizeof(int));

//	srand( (unsigned)time( NULL ));
	srand(100);

	for(m = 0; m < M; m++)
	{
		SO.a = (int*)malloc((size_t)N*sizeof(int));
		S[m].a = (int*)malloc((size_t)N*sizeof(int));
		S[m].Z = (int*)malloc((size_t)K*sizeof(int));
		S[m].ZDelta = (int*)malloc((size_t)K*sizeof(int));
		S[m].WCV = (double*)malloc((size_t)K*sizeof(double));
		S[m].SF = (double**)malloc((size_t)K*sizeof(double*));
		S[m].SFDelta = (double**)malloc((size_t)K*sizeof(double*));
		S[m].change = (int*)malloc((size_t)K*sizeof(int));
		S[m].dsum = (double*)malloc((size_t)N*sizeof(double));
		S[m].dmax = (double*)malloc((size_t)N*sizeof(double));
		S[m].dmin = (double*)malloc((size_t)N*sizeof(double));
		S[m].kmax = (int*)malloc((size_t)N*sizeof(int));
		S[m].kmin = (int*)malloc((size_t)N*sizeof(int));
		S[m].C = (double**)malloc((size_t)K*sizeof(double*));
		S[m].d = (double**)malloc((size_t)N*sizeof(double*));
		S[m].used =0;

		for (k = 0; k < K; k++)
  		{
			S[m].C[k] =(double*)malloc((size_t)D*sizeof(double));
			S[m].SF[k] = (double*)malloc((size_t)D*sizeof(double));
			S[m].SFDelta[k] = (double*)malloc((size_t)D*sizeof(double));
			S[m].change[k] = 0;
			S[m].ZDelta[k] = 0;
			for(d=0; d<D; d++)
			{
				S[m].SFDelta[k][d] = 0;
			}
  		}

		for(n = 0; n < N; n++)
		{
			S[m].d[n] = (double*)malloc((size_t)K*sizeof(double));
			S[m].a[n] =  (int)(((double)rand()/RAND_MAX) * K);
			if(S[m].a[n] == K) S[m].a[n] --;
		}
		Eval(m);

		if(SO.TWCV > S[m].TWCV)
		{
			SO.TWCV = S[m].TWCV;
			for(n=0; n<N; n++)
				SO.a[n] = S[m].a[n];
		}


	}

}


void Selection()
{
    double Fmin = 0;
	double *psb;
	double Fsum = 0;
	int i, m, temp, count;
	int flag =0;
	struct Solution *Sprime;

	for(m=0; m<M; m++)
	{
		if (S[m].num == K)
		{
			flag = 1;
			S[m].F = 1.5 * TWCVMax - S[m].TWCV;
			if(Fmin > S[m].F)
				Fmin = S[m].F;
			Fsum = Fsum + S[m].F;
		}
	}

	if(flag == 0)
		Fmin =1;

	for(m=0; m<M; m++)
	{
		if (S[m].num != K)
		{
			S[m].F = S[m].e * Fmin;
			Fsum = Fsum + S[m].F;
		}
	}
	psb = (double*)malloc((size_t)M*sizeof(double));

	for(m=0; m<M; m++)
	{
		psb[m] = S[m].F / Fsum;
	}
	psb = gather(psb, M);

	Sprime = (struct Solution*)malloc((size_t)M*sizeof(struct Solution));
//	Sprime = S;

	for(m=0; m<M; m++)
		Sprime[m] = S[m];

	count = 0;
	for(m=0; m<M; m++)
	{
		temp = Distribution(psb, M);
		if(Sprime[temp].used == 0)
		{
			S[m] = Sprime[temp];
			Sprime[temp].used = 1;
		}
		else
		{
			match1[count] = m;
			match2[count] = temp;
			count ++;
		}
	}

	i = 0;
	for(m=0; m<M; m++)
	{
		if(Sprime[m].used == 0 && i<count)
		{
			CopySolution(&Sprime[m], &Sprime[match2[i]]);
			S[match1[i]] = Sprime[m];
			S[match1[i]].used = 0;
			i ++;
		}
		Sprime[m].used = 0;
	}
	free(Sprime);
	free(psb);
}


void Mutation()
{
	double *p;
	int m, n, k, olda, count=0;

	p = (double*)malloc((size_t)K*sizeof(double));

//	srand( (unsigned)time( NULL ));
//	srand(200);

	for(m=0; m<M; m++)
	{
		for(n=0; n<N; n++)
		{
			if( (double)rand()/RAND_MAX < mp)
			{

				for(k=0; k<K; k++ )
				{
					p[k] = (1.5 * S[m].dmax[n] - S[m].d[n][k] +0.5) / S[m].dsum[n];
				}

				olda = S[m].a[n];

				p = gather(p, K);
				S[m].a[n] = Distribution(p, K);

				if(S[m].a[n] != olda)
				{
					AccumulateUpdate(m, n, olda, S[m].a[n]);
					count++;
				}
			}
		}

		IncrementalUpdate(m);
	}

//	fprintf(outputfile, "%d allels changed, %f percent has been changed in Mutation \n",count, count/(float)(M*N));
	free(p);
}

void KMO()
{
	int m, n, olda;
	int count=0;

	for(m=0; m<M; m++)
	{
		if (S[m].num == K)
		{
			for(n=0; n<N; n++)
			{

				olda = S[m].a[n];
				S[m].a[n] = S[m].kmin[n];

				if(S[m].a[n] != olda)
				{
					AccumulateUpdate(m, n, olda, S[m].a[n]);
					count ++;
				}

			}
			IncrementalUpdate(m);
		}
	}
// fprintf(outputfile, "%d allels changed, %f percent has been changed in KMO\n",count, count/(float)(M*N));
}


double* gather(double *psb, int distNumber)
{
	double *DistK;
	int i;

	DistK = (double*)malloc((size_t)distNumber*sizeof(double));

	DistK[0] = psb[0];
	for(i= 1; i< distNumber; i++)
	{
		DistK[i] = DistK[i-1] + psb[i];
	}
	return DistK;
}

int Distribution(double *DistK, int distNumber)
{
	double index;
	int i;

	index = ((double)rand()/RAND_MAX);

	for( i =0; i<distNumber; i++)
	{
		if ( index < DistK[i])
			return i;
	}
	return distNumber -1;
}


void CopySolution(struct Solution *t, struct Solution *f)
{
	int n,k,d;

	t->F = f->F;
	t->num = f->num;
	t->used = f->used;
	t->TWCV = f->TWCV;
	t->TWCVDelta = f->TWCVDelta;
	t->e = f->e;

	for(n=0; n<N; n++)
	{
		t->a[n] = f->a[n];
		t->dsum[n] = f->dsum[n];
		t->dmax[n] = f->dmax[n];
		t->dmin[n] = f->dmin[n];
		t->kmin[n] = f->kmin[n];
		t->kmax[n] = f->kmax[n];
		for (k=0; k<K; k++)
		{
			t->d[n][k] = f->d[n][k];
		}

	}

	for(k=0; k<K; k++)
	{
		t->Z[k] = f->Z[k];
		t->ZDelta[k] = f->ZDelta[k];
		t->WCV[k] = f->WCV[k];
		t->change[k] = f->change[k];

		for (d=0; d<D; d++)
		{
			t->SF[k][d] = f->SF[k][d];
			t->SFDelta[k][d] = f->SFDelta[k][d];
			t->C[k][d] = f->C[k][d];
		}
	}

}

void AccumulateUpdate(int m, int n, int olda, int newa)
{

	int k1, k2, d;
	S[m].change[olda] = 1;
	S[m].change[newa] = 1;
	k1 = olda;
	k2 = newa;
	S[m].ZDelta[k1]--;
	S[m].ZDelta[k2]++;