#ifndef MATRIXPATHFINDER_H
#define MATRIXPATHFINDER_H

#include <vector>
#include <map>
//#include <list>
//#include <multiset>
#include "AbstractCase.h"
#include "Point2D.h"

#include "MemoryManager/debugNew.h"


#define MPFLIST vector

namespace ground{
	/**
	 * classe permettant d'effectuer un pathfinding sur une matrice de cases.
	 * 
	 * lors d'une recherche de chemin, si aucun chemin n'a été trouvé, le pathFinder calcule un chemin approché, qui permet 
	 * d'avoir un point d'arrivé proche de celui souhaité au depart (mais néanmoins different...)
	 *
	 * Cette classe peut aussi utiliser un masque stencil ou une increment map pour augmenter la vitesse de recherche de chemin.
	 * Le masque stencil consiste en une matrice de booleen de la taille de la carte, autorisant ou pas le passage sur les cases.
	 * ceci permet d'accelerer la recherche en limitant l'espace de recherche lorsque le terrain est complexe et qu'on a effectuée une
	 * pre recherche de chemin à l'aide du graph de zones par exemple. on peut aussi l'utiliser pour bloque temporairement des cases
	 * tu terrain sur lequelles on ne souhaite pas passer à un moment donnée (presence d'une autre unité ou autre...)
	 * neanmoins, l'utilisation du masque peut poser probleme car il bloque effectivement le passage sur les cases, ainsi, on peut
	 * ne plus trouver de chemin alors qu'il en existe un car le masque bloque ce chemin.
	 * Pour resoudre ce probleme, il est preferable d'utiliser une increment map. Une increment map est une matrice de rééles
	 * augmentant le cout des cases. Ainsi, une cases sur laquelle on a peut de chances de passer aura un cout fortement augmenter 
	 * dans l'increment map, ce qui permet de ne la traiter qu'en dernier recours. Ceci permet d'accelerer le calcule de chemin non
	 * pas en limitant l'espace de recherche mais en orientant tres fortement le calcule pour arriver le plus vite possible au 
	 * resultat. ceci est un peut moins performant que l'utilisation d'un masque, mais on ne perd le risque de ne plus trouver
	 * un chemin existant.
	 */
	class MatrixPathFinder
	{
	private:
		/**
		 * ma matrice de case absraites sur laquel sera effectué le pathfinding
		 */
		AbstractCase*** matrix;
		/**
		 * matrice de booleen servant de masque stencil pour definir si une case est passable ou pas.
		 * peut etre utilisé par exemple pour bloquer les emplacement ou se trouve une unitée arretée.
		 */
		bool ** stencil;

		/**
		 * matrice servant à appliquer un increment au cout des cases de la matrice (utiliser pour limiter
		 * la recherche du pathfinder par le graph)
		 */
		float** incrementMap;
		/**
		 * structure servant à stocker les informations sur les noeuds
		 */
		struct Node{
			/**
			 * pointeur sur la case (aces un s à la fin car sinon le compilateur le repere comme un mot clé)
			 */
			AbstractCase * cases;
			/**
			 * position de la case
			 */
			Point2D position;
			/**
			 * cout relatif de la case (avec heuristique)
			 */
			float cost;
			/**
			 * cout ne prenant pas en compte l'heuristique
			 */
			float costWithoutHeuristic;
			/**
			 * le noeud precedent dans le chemin.
			 */
			Node * previous;
			/**
			 * booleen permettant de savoir si le noeud a été entierement traité ou pas.
			 */
			bool terminated;
			/**
			 * booleen permettant de savoir si le noeud a été initialisé ou pas.
			 */
			bool initialised;
		};

		/**
		 * booleen permettant de savoir si un chemin a été trouvé ou pas.
		 */
		bool pathFound;
		/**
		 * booleen permettant de definir si le pathFinder utilise le masque stencil ou pas.
		 */
		bool useStencil;
		/**
		 * booleen permettant de savoir si le pathfinder utilise une increment map ou pas.
		 */
		bool useIncrementMap;
		/** 
		 * la largeur de la matrice de cases.
		 */
		int width;
		/**
		 * la heuteur de la matrice de cases.
		 */
		int height;

		/**
		 * la list contenant les points en cours de traitement de l'algorithme A*
		 */ 
		std::multimap<float,Node*> opened;

		/**
		 * matrice de booleen permettant de savoir si une case a été entierement traitée.
		 */
		Node ** nodes;

		/**
		 * nombre de point dont l'analyse est terminée (pour effectuer des stats)
		 */
		int nbTerminated;

		/**
		 * methode permettant de recuperer le noeud ayant le cout le plus faible dans la liste opened.
		 * @return Node * : le noeud ayant le cout le plus faible dans la liste des opened. retourne NULL si la liste
		 * est vide.
		 */
		Node * getLowestCostNode();

		/**
		 * methode ajoutant un noeud dans la liste des opened
		 * @param node : le noeud à ajouter dans la liste des opened.
		 */
		void addNodeInOpenedList(Node * node);

		/**
		 * methode de calcul de l'heuristique.
		 *
		 * @param current : le point en cours de traitement.
		 * @param position : la position de la case ou est rendu le calcul (voisin de current
		 * @param destination : le point de dstination du chemin.
		 * @return float : la valeur de l'heuristique.
		 */
		float heuristic(Point2D& current, Point2D& position, Point2D& destination);

		/**
		 * methode créeant le chemin trouvé par le pathFinder a partir du dernier noeud traité.
		 * @param last : le dernier noeud traité par l'algorithme de pathFinder.
		 * @param start : le point de depart du chemin.
		 */
		void buildPath(Node * last, Point2D& start);

		/**
		 * methode servant a nettoyer la memoire utilisée par la liste des noeud en cours de traitement.
		 */
		void clearOpenedList();

	protected:
		/**
		 * le chemin trouvé par le pathfinder.
		 */
		std::vector<Point2D> path;
	public:
		/**
		 * constructeur par defaut.
		 */
		MatrixPathFinder(void);
		/**
		 * destructeur par defaut.
		 */
		virtual ~MatrixPathFinder(void);

		/**
		 * methode permettant de definir la matrice sur laquel tournera le pathfinder.
		 * @param matrix : la matrice de cases sur lequel tournera la pathfinder;
		 * @param width : la largeur de la matrice.
		 * @param height : la heuteur de la matrice.
		 */
		void setMatrix(AbstractCase*** matrix, int width, int height);

		/**
		 * methode permettant de definir un masque stencil pour le pathFinder.
		 *
		 * Le masque stencil permet de definire pour chaque case si celle ci est passante ou pas. Une case
		 * du masque stencil a false rend la case non passante, quelle que soit la valeure retourné par
		 * la methode AbstractCase::isTraversable() de la case.
		 * @param stencil : le masque stencil à appliquer au pathFinder
		 */ 
		void setStencil(bool** stencil);

		/**
		 * methode permettant d'activer ou desactiver le masque stencil du pathFinder
		 * @param use : true pour activer le masque stencil, false pour le desactiver.
		 */
		void enableStencil(bool use);

		/**
		 * methode permettant de savoir si le masque stencil est activé.
		 * @return bool : true si le masque stencil est active, false sinon.
		 */ 
		bool isStencilEnabled();

		/**
		 * methode permettant de definir la matrice utilisée comme increment map
		 * @param matrix : la matrice utilise
		 */
		void setIncrementMap(float** matrix);

		/**
		 * methode permettant d'activer/desactiver l'utilisation d'une increment map
		 * @param use : true pour utiliser l'increment map, false sinon
		 */
		void enableIncrementMap(bool use);

		/**
		 * methode permettant de savoir si le pathfinder utilise une increment map ou pas.
		 * @return bool : true si l'utilisation d'une increment map est activée, false sinon.
		 */
		bool isIncrementMapEnabled();

		/**
		 * methode permettant de savoir si le pathfinder a trouvé un chemin ou pas.
		 * @return bool : true si le path finder a trouvé un chemin, false sinon.
		 */
		bool haveFoundPath();

		/**
		 * methode permettant de recuperer le dernier chemin analysé.
		 * @return st::vector<Point2D> : le dernier analysé.
		 */
		std::vector<Point2D> getPath();

		/**
		 * methode permettant d'analyser le terrain pour chercher un chemin entre les points begin et end.
		 *
		 * Si le pathFinder trouve un chemin, la methode haveFoiundPath() retournera true, sinon elle retournera false.
		 * @param begin : le point de depart du chemin
		 * @param end : le point d'arrivée du chemin.
		 */
		void findPath(Point2D begin, Point2D end);

	};
};// namespace terrain

#include "MemoryManager/debugNewOff.h"


#endif
