#include "ga.h"
#include "../includes/globals.h"
#include <stdlib.h>
#include <malloc.h>
#include <stdio.h>
#include "../WalkSat/WalkSat.h"
#include "ga_param.h" 

void printSolution(int hasSolution){
	int i;
	int j;
	if(hasSolution == 0){
		printf("Solution: Fail\n");
		return;
	}
	printf("Solution: (");
	for(i=0; i<numberOfLiterals; i++){
		if(literals[i].value<0){
			j=-literals[i].literalNumber;
		}
		else{
			j=literals[i].literalNumber;
		}
		printf(" %d", j);
	}
	printf(" )\n");
}



void initializeGeneticAlgorithm(){
	int i;
	int j;
	solutionFound = 0;
	srandom(RANDOM_SEED);
	currentGeneration = (GENE*) malloc(sizeof(GENE)*POPULATION_SIZE);
	nextGeneration = (GENE*) malloc(sizeof(GENE)*POPULATION_SIZE);
	functionUse_literalsSize = (int*) malloc(sizeof(int)*numberOfLiterals);
	bestSolution = (int*) malloc(sizeof(int)*numberOfLiterals);
	bestSolutionValue = 0;
	for(i=0;i<POPULATION_SIZE;i++){
		currentGeneration[i].assignment = (char*)malloc(sizeof(char)*numberOfLiterals);
		nextGeneration[i].assignment = (char*)malloc(sizeof(char)*numberOfLiterals);
		for(j=0;j<numberOfLiterals;j++){
			if(random()%2 == 0){
				currentGeneration[i].assignment[j]=1;
			}
			else{
				currentGeneration[i].assignment[j]=0;
			}
		}
		calculateFitness(&currentGeneration[i]);
	}
}


int clausesSatisfied(GENE* gene){
	int i;
	int j;
	int counter=0;
	for(i=0;i<numberOfClauses;i++){
		for(j=0;j<clauses[i].literalCount;j++){
			int lit = clauses[i].literals[j];
			if(lit>0){
				if(gene->assignment[lit-1]>0){
					counter++;
					break;
				}
			}
			else{
				if(gene->assignment[abs(lit)-1]<=0){
					counter++;
					break;
				}
	
			}
		}	
	}
	if(counter > bestSolutionValue){
		bestSolutionValue = counter;
		for(i=0; i<numberOfLiterals; i++){
			if(gene->assignment[i] > 0){
				bestSolution[i] = 1;
			}
			else{
				bestSolution[i] = -1;
			}
		}
	}
	if(counter == numberOfClauses){
		solutionFound = 1;
		for(i=0; i<numberOfLiterals;i++){
			if(gene->assignment[i] > 0){
				literals[i].value = 1;
			}
			else{
				literals[i].value = -1;
			}
		}
	}
	return counter;
}

int literalsToSatisfyMostUnsatisfied(GENE* gene, int* tabuList){
	int i;
	int j;
	int max;
	int maxValue;
	int maxV;
	int maxValueV;
	for(i=0;i<numberOfLiterals;i++){
		functionUse_literalsSize[i]=0;
	}
	for(i=0;i<numberOfClauses;i++){
		int satisfied = 0;
		for(j=0;j<clauses[i].literalCount;j++){
			int lit = clauses[i].literals[j];
			if(lit>0){
				if(gene->assignment[lit-1]>0){
					satisfied=1;
					break;
				}
			}
			else{
				if(gene->assignment[abs(lit)-1]<=0){
					satisfied=1;
					break;
				}
	
			}
		}	
		if(satisfied == 0){
			for(j=0;j<clauses[i].literalCount;j++){
				int lit = clauses[i].literals[j];
				functionUse_literalsSize[abs(lit)-1]++;
	
			}	
		}
	}
	max = -1;
	maxValue=0;//functionUse_literalsSize[0];
	maxV = 0;
	maxValueV = functionUse_literalsSize[0];
	for(i=0;i<numberOfLiterals;i++){
		if(maxValue < functionUse_literalsSize[i]){
			int tabu=0;
			for(j=0;j<TABU_SIZE;j++){
				if(i==tabuList[j]){
					tabu=1;
					break;	
				}
			}
			if(tabu==0){
				max=i;
				maxValue = functionUse_literalsSize[i];
			}
		}
		if(VIOLATE_TABU_IF_REQD == 1){
			if(maxValueV < functionUse_literalsSize[i]){
				maxValueV = functionUse_literalsSize[i];
				maxV=i;
			}
		}
				
	}
	if((max == -1) && (VIOLATE_TABU_IF_REQD == 1)){
		return maxV;
	}
	return max;
}

void calculateFitness(GENE* gene){
	gene->fitness = clausesSatisfied(gene);
	//gene->fitness *= gene->fitness;
}

void mutateGene(GENE* gene){
	int flipCount = random()%numberOfLiterals;
	int i;
	for(i=0;i<flipCount;i++){
		int val = random()%numberOfLiterals; 
		gene->assignment[val] = gene->assignment[val]==1?0:1;
	}
	calculateFitness(gene);
}

void crossGenes(GENE* parent1, GENE* parent2, GENE* child1, GENE* child2){
	int i;
	for(i=0;i<numberOfLiterals;i++){
		if(random()%2 == 0){
			child1->assignment[i]=parent1->assignment[i];
			child2->assignment[i]=parent2->assignment[i];
		}
		else{
			child1->assignment[i]=parent2->assignment[i];
			child2->assignment[i]=parent1->assignment[i];
		}
	}
	calculateFitness(child1);
	calculateFitness(child2);
}

void copyGenes(GENE* parent1, GENE* parent2, GENE* child1, GENE* child2){
	int i;
	for(i=0;i<numberOfLiterals;i++){
			child1->assignment[i]=parent1->assignment[i];
			child2->assignment[i]=parent2->assignment[i];
	}
	calculateFitness(child1);
	calculateFitness(child2);
}

int localSearch(GENE* gene){
	if(HEURISTIC == TABU_SEARCH){
		return localSearchTabu(gene);
	}
	else if(HEURISTIC == WALK_SAT){
		return localSearchWalkSat(gene);
	}
}

int localSearchWalkSat(GENE* gene){
	//assign the gene into a structure 
	int i;
	int flips;
	int retries;
	for(i=0; i<numberOfLiterals; i++){
		if(gene->assignment[i] > 0){
			functionUse_literalsSize[i]=(i+1);
		}
		else{
			functionUse_literalsSize[i]=-(i+1);
		}
	}
	
	if(WalkSat(RAND_PROB, RETRIES_FACTOR * numberOfLiterals, 1,  &flips, &retries, functionUse_literalsSize)>0){
		for(i=0;i<numberOfLiterals;i++){
			literals[i].value = functionUse_literalsSize[i]>0?1:-1;	
		}
		solutionFound = 1;
		return 1;
	}
	else{
		for(i=0;i<numberOfLiterals;i++){
			gene->assignment[i] = functionUse_literalsSize[i]>0?1:0;
		}
		calculateFitness(gene);
		return 0;
	}
}



int localSearchTabu(GENE* gene){
	int tabuList[TABU_SIZE];
	int tabuPosition=0;
	int currentFitness = gene->fitness;
	int bestFlip = currentFitness;
	int bestLiteral = -1;
	int i;
	for(i=0;i<TABU_SIZE;i++){
		tabuList[i]=-1;
	}
	//find the literal which can be flipped for maximum gain...
	for(i=0; i<RETRIES_FACTOR * numberOfLiterals; i++){
		int rand = literalsToSatisfyMostUnsatisfied(gene, tabuList);
		if(rand == -1){
			break;
		}
		tabuList[tabuPosition]=rand;
		tabuPosition = (tabuPosition+1)%TABU_SIZE;
		if(gene->assignment[rand] > 0){
			gene->assignment[rand] = 0;
		}
		else{
			gene->assignment[rand] = 1;
		}
	}
	calculateFitness(gene);
	return solutionFound;
}

int localSearchWithRandomFlipsTabu(GENE* gene){
	int tabuList[TABU_SIZE];
	int tabuPosition=0;
	int currentFitness = gene->fitness;
	int bestFlip = currentFitness;
	int bestLiteral = -1;
	int i;
	for(i=0;i<TABU_SIZE;i++){
		tabuList[i]=-1;
	}
	//find the literal which can be flipped for maximum gain...
	for(i=0; i< 5 * RETRIES_FACTOR * numberOfLiterals; i++){
		int rand;
		if((1.0*random()/RAND_MAX) < RAND_PROB){
			rand = literalsToSatisfyMostUnsatisfied(gene, tabuList);
		}
		else{
			rand = random()%numberOfLiterals;
		}
		if(rand == -1){
			break;
		}
		if(gene->assignment[rand] > 0){
			gene->assignment[rand] = 0;
		}
		else{
			gene->assignment[rand] = 1;
		}
	}
	calculateFitness(gene);
	return solutionFound;
}

int runGeneticAlgorithm(){
	initializeGeneticAlgorithm();
	int generation;
	int genes;
	int i;
	for(generation=0; generation<TOTAL_GENERATIONS; generation++){
		int totalSum = 0;
		int maxFitness = 0;
		GENE* fittestGene;
		/* Generate Compliments... */
		//printf("Fitness: ");
		for(i=0;i<POPULATION_SIZE;i++){
			totalSum+=currentGeneration[i].fitness;
			//printf(" %d ",currentGeneration[i].fitness);
			if(currentGeneration[i].fitness > maxFitness){
				maxFitness = currentGeneration[i].fitness;
				fittestGene = &currentGeneration[i];
			}
		}
		//printf("\n");
		printf("Starting Level %d at fitness %d\n",generation+1, maxFitness);
		printf("Local Search Leads to");
		if(localSearch(fittestGene)){
			printf(" right answer..\n");
			return 1;
		}
		printf(" %d\n",fittestGene->fitness);
		totalSum+=fittestGene->fitness-maxFitness;
		for(genes=0;genes<POPULATION_SIZE-1;genes+=1){
			GENE* parent1 = NULL;
			GENE* parent2 = NULL;
			int randomVal = random()%totalSum;
			int randomVal2 = random()%totalSum;
			for(i=0;i<POPULATION_SIZE;i++){
				if(randomVal>=0){
					randomVal-=currentGeneration[i].fitness;
					if(randomVal <= 0){
						parent1 = &currentGeneration[i];	
					}
				}
				if(randomVal2>=0){
					randomVal2-=currentGeneration[i].fitness;
					if(randomVal2 <= 0){
						parent2 = &currentGeneration[i];	
					}
				}
			}
			if(parent1 == parent2){
				genes-=1;
				continue;
			}
			//if(genes < POPULATION_SIZE/10){
			//	copyGenes(parent1, parent2, &nextGeneration[genes], &nextGeneration[genes+1]);
			//}
			//else{
				crossGenes(parent1, parent2, &nextGeneration[genes], &nextGeneration[genes+1]);
			//}
		}
		for(i=0;i<MUTATE;i++){
			int random1 = random()%POPULATION_SIZE;
			mutateGene(&nextGeneration[random1]);
		}
		if(solutionFound == 1){
			return 1;
		}
		GENE* temp = currentGeneration;
		currentGeneration = nextGeneration;
		nextGeneration = temp;
	}
	printf("Entering Local Search Mode...\n");
	for(i=0;i<numberOfLiterals;i++){
		if(bestSolution[i]==1){
			nextGeneration[0].assignment[i] = 1;
		}
		else{
			nextGeneration[0].assignment[i] = 0;
		}
	}
	calculateFitness(&nextGeneration[0]);
	if(localSearchWithRandomFlipsTabu(&nextGeneration[0])){
		return 1;
	}
	printf("Best Achieved %d\n",bestSolutionValue);
	FILE* f = fopen("/tmp/BEST_SOL","w");
	for(i=0;i<numberOfLiterals;i++){
		fprintf(f,"%d ",bestSolution[i]*(i+1));
	}
	fprintf(f,"\n");
	fclose(f);
	if(solutionFound == 1){
		return 1;
	}
	return 0;
}


int runGA(int argc, char** argv){
	if(argc != 9){
		printf("Usage: ./SatSolverGA <file> <POP_SIZE> <MUTATE_NUMBER> <TABU_SIZE> <tabu|walk> <RETRIES_FACTOR> <FLIP_PROB> <SEED>\n");
		exit(1);
	}
	POPULATION_SIZE = atoi(argv[2]);
	MUTATE = atoi(argv[3]);
	TABU_SIZE = atoi(argv[4]);
	HEURISTIC = strcmp(argv[5], "tabu")==0?TABU_SEARCH:WALK_SAT;
	RETRIES_FACTOR = atoi(argv[6]);
	RAND_PROB = atof(argv[7]);
	RANDOM_SEED = atoi(argv[8]);
	int returned = runGeneticAlgorithm();
	printSolution(returned);
}