/*____________________________________________________________________________
matrix dynamic
par Martin Robinson
______________________________________________________________________________
preprocesseur
____________________________________________________________________________*/
#pragma once
#ifndef _MATRIX
#define _MATRIX

#include <stack>
#include <vector>
using namespace std;

//#define DEBUG
#include "debug.h"


/*____________________________________________________________________________
macro
____________________________________________________________________________*/

#define _up(INDEX,W) (INDEX-W)
#define _down(INDEX,W) (INDEX+W)
#define _left(INDEX,W) (INDEX-1)
#define _right(INDEX,W) (INDEX+1)
#define _top(INDEX,W,H) (INDEX>W-1)
#define _bottom(INDEX,W,H) (INDEX<W*H-W)
#define _borderL(INDEX,W,H) (INDEX%W>0)
#define _borderR(INDEX,W,H) (INDEX%W<W-1)
#define _x(INDEX,W) (INDEX%W)
#define _y(INDEX,W) (INDEX/W)
#define _index(X,Y,W) (X+Y*W)

/*____________________________________________________________________________
classe
____________________________________________________________________________*/

struct graph{
    char from,
         to;
    int cost;
};

const graph map[12] = {
    {'A', 'B', 5},
    {'B', 'C', 7},
    {'A', 'C', 2},
    {'A', 'E', 2},
    {'A', 'H', 3},
    {'E', 'D', 6},
    {'D', 'F', 1},
    {'F', 'C', 4},
    {'C', 'G', 2},
    {'H', 'G', 1},
    {'H', 'C', 4},
    {'B', 'D', 8}
};

//cellule
struct node{
    char index;
    int cost,
        dist;
    char    parent;
    node(char ind, int cos, int dis, char par)
    {
        index = ind;
        cost = cos;
        dist = dis;
        parent = par;
    }
};

//enpile tout les voisins
stack<node> getAllNeighbor(char from)
{
    stack<node> s;
    for (int i=0;i<12;i++)
        if (map[i].from == from)
            s.push(node(map[i].to, map[i].cost,0,map[i].from));
        else if(map[i].to == from)
            s.push(node(map[i].from, map[i].cost,0,map[i].to));
    return s;
}



//si une seule cellule avec la position donne se trouve dans la liste
vector<node>::iterator find(char pos, char from, vector<node>*list)
{
    vector<node>::iterator it = list->begin();
    while (it!=list->end())
    {
        if (it->index == pos && it->parent == from)
            return it;
        it++;
    }
    return list->end();
}

//si une seule cellule avec la destination donne se trouve dans la liste
vector<node>::iterator findBestRoute(char pos, vector<node>*list)
{
    vector<node>::iterator it = list->begin(),
                           best = list->end();
    CHAR(pos);
    while (it!=list->end())
    {
    CHAR(it->index);
        if (it->index == pos)
        {

            if (best == list->end())
                best = it;
            else if (best->cost > it->cost)
                best = it;
        }
        it++;
    }
    return best;
}


vector<node> * pathfindR(char pos, char goal, int cost, vector<node>*open)
{
    //trouve tout les chemins partant du point pos
    stack <node>neighbor = getAllNeighbor(pos);
    //pour tout les chemins trouvé
    while(!neighbor.empty())
    {
        //creer une nouvelle cellule
        node nu = neighbor.top();
        nu.cost += cost;
        //verifier si la position est déja dans la liste
        vector<node>::iterator tmp = find(nu.index,pos, open);
        if (tmp==open->end())
        {
            //si non, ajouter la node
            open->push_back(nu);
            //recursive madness
            if (nu.index != goal)
                open = pathfindR(nu.index,goal,nu.cost,open);
        }
        else if (tmp->cost > cost)
        {
            //si oui et que le cout de déplace est supperieur
            //remplacer
            *tmp = nu;
            //recursive madness
            if (nu.index != goal)
                open = pathfindR(nu.index,goal,nu.cost,open);
        }
        
        //dans le troisieme cas, on ne fait rien et 
        //passont au prochain chemin
        neighbor.pop();
    }
    //retourner la liste
    return open;

}

vector<node> * pathfind(char start, char goal)
{
    vector<node> * open = new vector<node>,
                 * closed = new vector<node>;
    vector<node>::iterator it;
    open = pathfindR(start,goal,0, open);

    it = findBestRoute(goal,open);
    while (it->index != start)
    {


        closed->push_back(*it);
        it = findBestRoute(closed->back().parent, open);
    }
    
    
    return closed;
}


#endif