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

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

/*____________________________________________________________________________
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
____________________________________________________________________________*/

//enpile tout les voisins
stack<int> getAllNeighbor(int i, int w, int h)
{
    stack<int> s;
    if (_top(i,w,h))
        s.push(_up(i,w));
    if (_bottom(i,w,h))
        s.push(_down(i,w));
    if (_borderL(i,w,h))
        s.push(_left(i,w));
    if (_borderR(i,w,h))
        s.push(_right(i,w));
    return s;
}

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

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


vector<node> * pathfindR(char * m, int pos, int goal, int w, int h, int cost, vector<node>*open)
{
    //trouve tout les chemins partant du point pos
    stack <int>neighbor = getAllNeighbor(pos,w,h);
    //pour tout les chemins trouvé
    while(!neighbor.empty())
    {
        //creer une nouvelle cellule
        node nu(neighbor.top(), cost, 0, pos);
        //verifier si la position est déja dans la liste
        vector<node>::iterator tmp = find(neighbor.top(), open);
        if (tmp==open->end())
        {
            //si non, ajouter la node
            open->push_back(nu);
            //recursive madness
            if (nu.pos != goal)
                open = pathfindR(m, nu.pos,goal,w,h,cost+1,open);
        }
        else if (tmp->cost > cost)
        {
            //si oui et que le cout de déplace est supperieur
            //remplacer
            *tmp = nu;
            //recursive madness
            if (nu.pos != goal)
                open = pathfindR(m, nu.pos,goal,w,h,cost+1,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 * m, int start, int goal, int w, int h)
{
    vector<node> * open = new vector<node>;
    open = pathfindR(m,start,goal,w,h,1, open);
    return open;
}


#endif