#include "GraphBuilder.h"

#include <math.h>
//#include <vector>
#ifndef NDEBUG
	#define NDEBUG
	#include <list>
	#undef NDEBUG
#else
	#include <list>
#endif
#include <map>
#include "Case.h"

#ifdef WIN32
#include <windows.h>
#endif
#include <GL/glut.h>
#include <GL/GL.h>

#include "MemoryManager/debugNew.h"


using namespace ground;
using namespace std;

GraphBuilder::GraphBuilder(void)
{
	ident = NULL;
	width = 0;
	height = 0;
}

GraphBuilder::~GraphBuilder(void)
{
	clearGraph();
}



void GraphBuilder::computeZones(Case*** matrix,int width,int height){
	clearGraph();
	// on detruit le tableau d'identifiant precedent.
	if (ident != NULL){
		for (int i = 0; i < this->width; i++){
			delete[] ident[i];
		}
		delete[] ident;
	}
	this->width = width;
	this->height = height;
	// creation du tableau d'identifiants
	ident = new int*[width];
	for(int i = 0; i < width; i++){
		ident[i] = new int[height];
		for (int j = 0; j < height; j++){
			ident[i][j] = -1;
		}
	}
	// le compteur de carré de taille 1
	int unitSquareNumber = 0;
	// l'identifiant de depart est 0
	int currentIdent = 0;
	// booleen permettant de savoir si on a fini l'analyse
	bool terminated = false;
	// on parcours la matrice pour tester chaque point.
	for (int x = 0; x < width && !terminated; x++){
		for (int y = 0; y < height && !terminated; y++){
			Square bestSquare;
			bestSquare.size = -1;
			// on parcourt toute la matrice pour trouver le carré de taille maximum
			for (int i = 0; i < width; i++){
				for (int j = 0; j < height; j++){
					// on test si la case est une case valide.
					// C.A.D : case passable et non utilisé
					if (matrix[i][j]->isPassable() && ident[i][j] == -1){
						// la case est utilisable
						// on initialise la taille du carré a 0
						int size = 0;
						// on test pour chaque taille de carré
						while(isValidSquare(matrix,i,j,size+1)){
							// ce carré la marchait : on passe au suivant
							size++;
						}
						// on a trouvé un carré valide
						// est-il plus grand que le precedent ?
						if (bestSquare.size < size){
							// il est plus grand
							bestSquare.x = i;
							bestSquare.y = j;
							bestSquare.size = size;
						}
					}
				}
			}
			if (bestSquare.size == -1){
				// on a pas trouvé de carré valide dans la map... elle est donc remplie, on
				// peut terminer l'analyse
				terminated = true;
			}else{
				// on a trouvé un carré qui bloquait : on le finalise en l'identifiant
				if (matrix[bestSquare.x][bestSquare.y]->isPassable()){
					identifySquare(currentIdent,bestSquare.x,bestSquare.y,bestSquare.size);
					// on ajoute le nouveau carré au graph
					SquareNode * node = new SquareNode();
					float size = (bestSquare.size+1)/2.0f;
					node->setPosition(Point2D(bestSquare.x+size,bestSquare.y+size));
					node->setSize(bestSquare.size);
					node->setGroundType(matrix[bestSquare.x][bestSquare.y]->getGroundType());
					graph.push_back(node);
					// on passe à l'identifiant suivant.
					currentIdent++;
					if (bestSquare.size == 0){
						unitSquareNumber++;
					}
				}
			}
		}
	}
	createGraph(matrix);

	// on detruit le tableau d'identifiants
	if (ident != NULL){
		for (int i = 0; i < this->width; i++){
			delete[] ident[i];
		}
		delete[] ident;
	}
	ident = NULL;
}

bool GraphBuilder::isValidSquare(Case*** matrix, int x, int y, int size){
	// on test si on sort des limites de la carte
	if (x + size >= width ||y + size >= height){
		// on sort des limites de la carte
		return false;
	}
	Case * base = matrix[x][y];
	// on test à la fois le coté droit et le bas
	for (int i = 0; i <= size; i++){
		// on recupere la case du coté droit
		Case * droite = matrix[x+size][y+i];
		// on recupere la case du bas.
		Case * bas = matrix[x+i][y+size];
		// si la case n'est pas du même type ou qu'elle n'est pas passable ou qu'elle est deja assignée
		if (droite->getGroundType() != base->getGroundType() || !droite->isPassable()||
			bas->getGroundType() != base->getGroundType() || !bas->isPassable()||
			ident[x+size][y+i] != -1 || ident[x+i][y+size] != -1){
			// on retourne faux.
			return false;
		}
	}
	// aucune des condition d'erreure n'a été trouvée : c'est donc valide
	return true;
}

void GraphBuilder::identifySquare(int identVal,int x, int y, int size){
	int xFin = x+size;
	int yFin = y+size;
	ident[x][y] = identVal;
	// pour chaque case du carré
	for(int i = x; i <= xFin; i++){
		for (int j = y; j <= yFin; j++){
			// on definit l'identifiant.
			ident[i][j] = identVal;
		}
	}
}

void GraphBuilder::createGraph(Case*** matrix){
	// pour chaque noeud
	for (vector<SquareNode*>::iterator it = graph.begin(); it != graph.end(); ++it){
		SquareNode* node = *it;
		int x = (int)node->getPosition().getX() - (node->getSize())/2.0f;
		int y = (int)node->getPosition().getY() - (node->getSize())/2.0f;
		int size = node->getSize();
		// on trouve ses voisins
		foundNeighbour(node);
		// et on donne a chaque cases du carré le liens vers le noeud.
		for(int i = x; i <= x+size; i++){
			for(int j = y; j <= y+size; j++){
				matrix[i][j]->setSquareNode(node);
			}
		}
	}
}

void GraphBuilder::foundNeighbour(SquareNode* node){
	int size = (int)node->getSize();
	int x = (int)node->getPosition().getX() - size/2.0f;
	int y = (int)node->getPosition().getY() - size/2.0f;
	// on parcourt la ligne du haut
	// on test si la ligne est bien dans la map
	if (y-1 >= 0){
		// on parcourt la ligne
		for (int i = x-1;i < x+size+2; i++){
			// on test si le X est bien dans la map et si la case est identifiée
			// (les cases infranchissable ne sont pas identifiée)
			if (i >= 0 && i < width && ident[i][y-1] != -1){
				SquareNode * voisin = graph[ident[i][y-1]];
				//printf("lien avec le voisin %d\n",ident[i][y-1]);
				SquareArc* arc = node->addNeighbour(voisin);
				if (arc != NULL){
					arc->computeFactors();
				}
			}
		}
	}
	// on parcourt la ligne du bas
	if (y+size+1 < height){
		// on parcourt la ligne
		for (int i = x-1;i < x+size+2; i++){
			// on test si le X est bien dans la map et si la case est identifiée
			// (les cases infranchissable ne sont pas identifiée)
			if (i >= 0 && i < width && ident[i][y+size+1] != -1){
				SquareNode * voisin = graph[ident[i][y+size+1]];
				SquareArc* arc = node->addNeighbour(voisin);
				if (arc != NULL){
					arc->computeFactors();
				}
			}
		}
	}
	// on parcourt la ligne de gauche
	if (x-1 >= 0){
		for (int i = y; i <= y + size; i++){
			if (i >= 0 && i < height && ident[x-1][i] != -1){
				SquareNode * voisin = graph[ident[x-1][i]];
				SquareArc* arc = node->addNeighbour(voisin);
				if (arc != NULL){
					arc->computeFactors();
				}
			}
		}
	}
	// on parcourt la ligne de droite
	if (x+size+1 < width){
		for (int i = y; i <= y + size; i++){
			if (i >= 0 && i < height && ident[x+size+1][i] != -1){
				SquareNode * voisin = graph[ident[x+size+1][i]];
				SquareArc* arc = node->addNeighbour(voisin);
				if (arc != NULL){
					arc->computeFactors();
				}
			}
		}
	}
}

void GraphBuilder::clearGraph(){
	// on delete chaque noeud
	for (vector<SquareNode*>::iterator it = graph.begin(); it != graph.end(); ++it){
		delete *it;
	}
	graph.clear();
}

void GraphBuilder::saveToFile(std::string file){
	// on tente d'ouvrire le fichier en ecriture
	FILE * fichier = fopen(file.c_str(),"w");
	if (fichier != NULL){
		// le fichier est bien ouvert
		// on parcourt tout le vecteur du graph
		for(vector<SquareNode*>::iterator it = graph.begin(); it != graph.end(); ++it){
			// pour chaque node :
			SquareNode * node = *it;
			// on ecrit ses coordonnée dans le fichier.
			// on sauvegarde les coordonnée avec la position du noeud non pas
			// au centre mais dans le coins du carré pour pouvoir traiter le graph
			// par la suite de la même facon qu'il a été crée.
			int size = node->getSize();
			int x = (int)node->getPosition().getX()-size/2.0f;
			int y = (int)node->getPosition().getY()-size/2.0f;
			fprintf(fichier,"%d %d %d\n",x,y,size);
		}
	}else{
		// on a pas reusi à ouvrire le fichier en ecriture
		fprintf(stderr,"Impossible d'ouvrire le fichier \"%s\" en ecriture\n",file.c_str());
	}
	fclose(fichier);
}
void GraphBuilder::loadFromFile(std::string file, Case*** matrix, int width, int height){
	this->width = width;
	this->height = height;
	clearGraph();
	// on detruit le tableau d'identifiants
	if (ident != NULL){
		for (int i = 0; i < this->width; i++){
			delete[] ident[i];
		}
		delete[] ident;
	}
	// creation du nouveau tableau d'identifiants
	ident = new int*[width];
	for(int i = 0; i < width; i++){
		ident[i] = new int[height];
		for (int j = 0; j < height; j++){
			ident[i][j] = -1;
		}
	}
	// on ouvre le fichier
	FILE * fichier = fopen(file.c_str(),"r");
	char buffer[255];
	int currentIdent = 0;
	// test si le fichier est bien ouvert
	if (fichier != NULL){
		// tant qu'on est pas à la fin du fichier on lit...
		while(!feof(fichier)){
			// on recupere une ligne
			fgets(buffer,255,fichier);
			int x;
			int y;
			int size;
			// et on lit ses informations
			sscanf(buffer,"%d %d %d",&x,&y,&size);
			// on les transforme en node
			SquareNode * node = new SquareNode();
			// on ajoute le node au vecteur
			graph.push_back(node);
			// et on gere la matrice d'identifiants
			identifySquare(currentIdent,x,y,size);
			// puis on remet les coordonnée du carré comme il faut pour le traitement suivant
			float halfSize = (size+1)/2.0f;
			node->setPosition(Point2D(x+halfSize,y+halfSize));
			node->setSize(size);
			node->setGroundType(matrix[x][y]->getGroundType());
			currentIdent++;
		}
		// on a fini de lire le fichier : on crée le graph
		createGraph(matrix);
	}else{
		fprintf(stderr,"impossible d'ouvrir le fichier \"%s\" en lecture\n",file.c_str());
	}
	fclose(fichier);
	// on detruit le tableau d'identifiants
	if (ident != NULL){
		for (int i = 0; i < this->width; i++){
			delete[] ident[i];
		}
		delete[] ident;
		ident = NULL;
	}
}

Graph * GraphBuilder::createGraph(){
	// l'utilisateur devra detruire le graph crée avec delete.
	SquareGraph* newGraph = new SquareGraph();
	newGraph->setNodes(graph);
	return newGraph;
}

void GraphBuilder::setupPonderationMatrix(float** matrix, vector<GraphNode*>& path){
	// on initialise la matrice à une forte valeur pour toutes les cases
	for (int i = 0; i < width; i++){
		for (int j = 0; j < height; j++){
			matrix[i][j] = 9999.0f;
		}
	}
	// la file des noeud du graph en attente de traitement
	std::list<SquareNode*> waiting;
	// l'ensemble des noeud deja traité ou ajouté dans la list
	map<void*,SquareNode*> finished;
	// on ajoute tout les points du chemin dans la list des noeud en attente
	for (vector<GraphNode*>::iterator it = path.begin(); it != path.end(); ++it){
		SquareNode * node = static_cast<SquareNode*>(*it);
		waiting.push_front(node);
		finished[node] = node;
	}
	// compteur servant a savoir combient de noeud du niveau courant sont present dans la liste
	int count = waiting.size();
	// variable servant à definire la distance des noeud par rapport au chemin.
	int level = 0;
	// tant que la file en attente n'est pas vide et que la distance max n'est pas atteinte
	int nbNode = 0;
	while (!waiting.empty() && level <= 2){
		nbNode++;
		// on recupere la tete de file
		SquareNode* node = waiting.back();
		waiting.pop_back();
		// on definit le cout du noeud dans la matrice
		int size = node->getSize();
		int x = node->getPosition().getX() - (size)/2.0f;
		int y = node->getPosition().getY() - (size)/2.0f;
		for(int i = x; i <= x + size; i++){
			for (int j = y; j <= y + size; j++){
				matrix[i][j] = (level) * 5;
			}
		}
		// on recupere les arcs du noeud
		vector<GraphArc*>& arcs = node->getNeighbours();
		for (vector<GraphArc*>::iterator arcIt = arcs.begin(); arcIt != arcs.end(); arcIt++){
			SquareNode* extremity = (SquareNode*)(*arcIt)->getOtherSide(node);
			// on regarde si ce noeud a deja été traité (en regardant dans la matrice le cout de la case)
			if (finished.find(extremity) == finished.end()){
				// le noeud n'a pas été traité : on l'ajoute à la file.
				waiting.push_front(extremity);
				finished[extremity] = extremity;
			}
		}
		count--;
		// on regarde si on a traité tout les noeud du niveau courant
		if (count <= 0){
			// on a traité tout les noeud du niveau courant : on passe au niveau suivant
			level++;
			count = waiting.size();
		}
	}
}

void GraphBuilder::drawGraph(int caseSize){
	glPushAttrib(GL_TEXTURE_BIT);
	glDisable(GL_TEXTURE_2D);
	glLineWidth(3);
	for(vector<SquareNode*>::iterator it = graph.begin(); it != graph.end(); ++it){
		SquareNode * node = *it;
		node->drawDebug(caseSize);
	}
	glLineWidth(1);
	glPopAttrib();
}

