// ptree2.cpp 
//by John Ahlschwede

#include "grammar.h"

const int popSize = 512;
time_t	bench;
int genCount = 0;

void initializePop(node *[]);	
void mutate(node *);
void findFitness4Pop(node*[],int[]);
void reproduce(node*[], int fitness[]);
int findIndex(int fitness[], int minIndex, int maxIndex);
void generation(node*[]);	
void outputBest(node *pop[], int fitness[]);

//currently this does a test run of a tournament with 16 members in the population
/*void main()
{

	int timedrun[5];

	for(int runNum=0; runNum<5; runNum++) //does 5 runs of tourney
	{

		time_t start=time(NULL);

		srand(time(NULL));


		int fitRating[popSize];
		for(int i=0; i<popSize; i++)
			fitRating[i]=-1;
		node *NODES[popSize];

		initializePop(NODES);

		findFitness4Pop(NODES,fitRating);


		timedrun[runNum]=time(NULL)-start;
		cout << endl << endl << "Whole run: " << timedrun[runNum];

	}

	cout << endl << endl;

	for(int p=0; p<5; p++)
	{
		cout << endl << "Time " << p << " " << timedrun[p];
	}
	cout << endl << endl << "Average time: " << (timedrun[0]+timedrun[1]+timedrun[2]+timedrun[3]+timedrun[4])/5;

	cout << endl << endl << "Press any key" << flush;

	getch();
	
	return;
}*/



//this main lets a user play against the "optimal" algorithm
/*void main()
{
	optimalPlayer opti;
	
	board gameSpace;
	gameSpace.boardInit();
	gameSpace.playGame(new livePlayer, &opti);
	gameSpace.printResults();

}*/


void main()
{

	srand(time(NULL));
	bench = time(NULL);

	int fitRating[popSize];
	for(int i=0; i<popSize; i++)
		fitRating[i]=-1;

	node *NODES[popSize];
	
	initializePop(NODES);

	for(int j = 0; j<150; j++)
		generation(NODES);
	
	return;
}


void generation(node *pop[])
{
	genCount++;
	int fitRating[popSize];
	for(int i=0; i<popSize; i++)
		fitRating[i]=-1;
	
	findFitness4Pop(pop,fitRating);
	
	outputBest(pop, fitRating);

	reproduce(pop, fitRating);

}



void initializePop(node *pop[])	
{
	node dummy;

	for(int j = 0; j < popSize; j++)
	{
		pop[j] = dummy.make_new(0);
		pop[j]->grow(0);
	}
}







void mutate(node *solution)
{
	if(rand()%200 == 42) //one chance in 200
	{
		node *temp = solution->findNode(rand()%20);
		if(temp != NULL)
			temp->grow(0);
	}

}



void findFitness4Pop(node *pop[],int rating[])
{
	optimalPlayer opti;
	board theGame;

	for(int i=0; i < popSize; i++)
	{
		theGame.boardInit();
		theGame.playGame(pop[i], &opti);
		rating[i]=theGame.getCups()[7];
		theGame.boardInit();
		theGame.playGame(&opti, pop[i]);
		rating[i]+=theGame.getCups()[0];

	}

}






void reproduce(node *pop[], int fitness[])
{
	node *temp[popSize];
	node *tree2add = NULL;
	node *addHere = NULL;

	for(int i=0; i<popSize; i++)
	{
		temp[i] = pop[i];
		pop[i] = NULL;
	}

	
	//Elitism.  The below copies over the best solution to the next generation
	int best = 0;
	for(int p=1; p<popSize; p++)
		if(fitness[p] > fitness[best])
			best = p;
	pop[0] = temp[best]->copyNode();

	
	
	
	for(int j=1; j<popSize; j++)
	{
		pop[j] = temp[findIndex(fitness, 0, popSize - 1)]->copyNode();

		if((rand() % 10) < 9) // do crossover
		{
			tree2add = temp[findIndex(fitness, 0, popSize - 1)]->findNode(rand()%20);
			addHere = pop[j]->findNode(rand() % 20);
			if((tree2add != NULL) && (addHere != NULL))
				addHere->addTree(tree2add->copyNode());
		}
		
		mutate(pop[j]);
	}



	for(int k=0; k<popSize; k++)
	{
		delete temp[k];
	}

}


int findIndex(int fitness[], int minIndex, int maxIndex)
{
	int total = 0;
	int chosen = 0;
	int search = 0;

	for(int i=minIndex; i < maxIndex; i++)
	{
		total += fitness[i];
	}

	chosen = (rand()%total) + 1;

	for(int j=minIndex; j < maxIndex; j++)
	{
		search += fitness[j];
		if(search >= chosen)
			return j;

	}

	return 0;
}


void outputBest(node *pop[], int fitness[])
{
	int best = 0; // index of highest fitness individual
	int worst = 0; // index of lowest fitness individual
	int totalFitness = 0; // sum of all fitness values
	int largest = 0; // index of individual with most nodes
	int smallest = 0; // index of individual with fewest nodes
	int totalSize = 0; // sum of size of all individuals
	int theSize = 0; // used to hold size value for each individual
	int largestValue = pop[0]->countSize();
	int smallestValue = pop[0]->countSize();



	for(int i=0; i < popSize; i++)
	{
		if(fitness[i] > fitness[best])
			best = i;

		if(fitness[i] < fitness[worst])
			worst = i;

		theSize = pop[i]->countSize();

		totalSize += theSize;

		totalFitness += fitness[i];

		if(theSize < smallestValue)
		{
			smallest = i;
			smallestValue = theSize;
		}

		if(theSize > largestValue)
		{
			largest = i;
			largestValue = theSize;
		}
	}

	
	cout << endl << endl << "Generation : " << genCount  << flush;
	cout << endl << "Fitness of Best : " << fitness[best];

	optimalPlayer opti;
	board theGame;
	theGame.boardInit();
	theGame.playGame(pop[best], &opti);
	cout << endl << "Best individual's score, going first : " << theGame.getCups()[7];
	theGame.boardInit();
	theGame.playGame(&opti, pop[best]);
	cout << endl << "Best individual's score, going second : " << theGame.getCups()[0];

	cout << endl << "Fitness of Worst : " << fitness[worst];

	theGame.boardInit();
	theGame.playGame(pop[worst], &opti);
	cout << endl << "Worst individual's score, going first : " << theGame.getCups()[7];
	theGame.boardInit();
	theGame.playGame(&opti, pop[worst]);
	cout << endl << "Worst individual's score, going second : " << theGame.getCups()[0];

	cout << endl << "Fitness of Smallest : " << fitness[smallest];

	theGame.boardInit();
	theGame.playGame(pop[smallest], &opti);
	cout << endl << "Smallest individual's score, going first : " << theGame.getCups()[7];
	theGame.boardInit();
	theGame.playGame(&opti, pop[smallest]);
	cout << endl << "Smallest individual's score, going second : " << theGame.getCups()[0];
		
	cout << endl << "Fitness of Largest : " << fitness[largest];

	theGame.boardInit();
	theGame.playGame(pop[largest], &opti);
	cout << endl << "Largest individual's score, going first : " << theGame.getCups()[7];
	theGame.boardInit();
	theGame.playGame(&opti, pop[largest]);
	cout << endl << "Largest individual's score, going second : " << theGame.getCups()[0];
	
	
	cout << endl << "Average Fitness : " << totalFitness / popSize;
	cout << endl << "Size of Best Individual : " << pop[best]->countSize();
	cout << endl << "Size of Worst Individual : " << pop[worst]->countSize();
	cout << endl << "Size of Largest Individual : " << largestValue;
	cout << endl << "Size of Smallest Individual : " << smallestValue;
	cout << endl << "Average Size : " << totalSize / popSize;


		
	cout << endl << "time : " << (time(NULL) - bench) << endl << endl;
	pop[best]->print();
	cout << flush;
	bench = time(NULL);

}