#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include "misc.hh"


bool operator < (const Position &a, const Position &b)
{
    if (a.x == b.x)
        return a.y < b.y;
    return a.x < b.x;
}

bool operator != (const Position &a, const Position &b)
{
    return (a.x != b.x) || (a.y != b.y);
}

bool operator == (const Position &a, const Position &b)
{
    return a.x == b.x && a.y == b.y;
}

bool operator < (const Tourelle &a, const Tourelle &b)
{
    return a.pos < b.pos;
}

bool Valide(Position element)
{
    return (element.x >= 0 && element.x < TAILLE_TERRAIN)
        && (element.y >= 0 && element.y < TAILLE_TERRAIN);
}

//TODO: Réécrire une version itérée de cette merde
vector<Position> Alentours(Position centre, int rayon)
{
    Position a, b;
    vector<Position> retour;
    
    a = b = centre;
    a.x += rayon;
    b.y += rayon;
    for (; a != b; a.x--, a.y++)
        if (Valide(a))
            retour.push_back(a);
    
    a = b = centre;
    a.y += rayon;
    b.x -= rayon;
    for (; a != b; a.x--, a.y--)
        if (Valide(a))
            retour.push_back(a);
    
    a = b = centre;
    a.x -= rayon;
    b.y -= rayon;
    for (; a != b; a.x++, a.y--)
        if (Valide(a))
            retour.push_back(a);
    
    a = b = centre;
    a.y -= rayon;
    b.x += rayon;
    for (; a != b; a.x++, a.y++)
        if (Valide(a))
            retour.push_back(a);

    return retour;
}

vector<Position> Bloc(Position element)
{
    Position delta[8] = {{ 0, 1}, {1,  0}, { 1, 1}, { 1, -1},
                         {-1, 0}, {0, -1}, {-1, 1}, {-1, -1}};
    vector<Position> retour;
    
    for (int index = 0; index < 8; index++)
    {
        Position voisin = element;
        
        voisin.x += delta[index].x, voisin.y += delta[index].y;
        if (Valide(voisin))
            retour.push_back(voisin);
    }
    return retour;
}

//TODO: Rendre moins MOSH cette fonction
vector<Position> Voisins(Position element)
{
    Position delta[4] = {{ 0, 1}, {1,  0},
                         {-1, 0}, {0, -1}};
    vector<Position> retour;
    
    for (int index = 0; index < 4; index++)
    {
        Position voisin = element;
        
        voisin.x += delta[index].x, voisin.y += delta[index].y;
        if (Valide(voisin))
            retour.push_back(voisin);
    }
    return retour;
}

int abs(int n)
{
    return (n < 0) ? -n : n;
}

int Distance(Position a, Position b)
{
    return abs(b.x - a.x) + abs(b.y - a.y);
}

int Distance_Carre(Position a, Position b)
{
    return Distance(a, b) * Distance(a, b);
}


Position Plus_Proche(vector<Position> &positions, Position element)
{
    Position actuel = {0xDEAD, 0xDEAD};
    
    for (size_t index = 0; index < positions.size(); index++)
        if (Distance_Carre(positions[index], element) < Distance_Carre(actuel, element))
            actuel = positions[index];
    return actuel;
}


void Exterminer(Tourelle origine)
{
    queue<Position> file;
    vector<int> ennemis = Adversaires();
    int frontiere = 0;
    
    file.push(origine.pos);
    while (!file.empty() && frontiere <= origine.portee && origine.attaque > 0)
    {
        queue<Position> suivant;
        
        while (!file.empty() && origine.attaque > 0)
        {
            Position actuel = file.front();
            vector<Position> voisins = Voisins(actuel);
            
            file.pop();
            for (size_t id = 0; id < ennemis.size(); id++)
            {
                while (Sorciers_Places(actuel, ennemis[id]) > 0 && origine.attaque)
                {
                    Tirer(origine.pos, actuel, 1);
                    origine.attaque--;
                }
            }
            for (size_t voisin = 0; voisin < voisins.size(); voisin++)
                suivant.push(voisins[voisin]);
        }
        file = suivant;
        frontiere++;
    }
}

vector<Position> Trajet(Position depart, Position arrivee)
{
    queue<Position> file;
    bool Marque[TAILLE_TERRAIN][TAILLE_TERRAIN] = {false};
    Position Parent[TAILLE_TERRAIN][TAILLE_TERRAIN];
    vector<Position> retour;
    Position element;

    file.push(depart); 
    Marque[depart.x][depart.y] = true;
    while (!file.empty())
    {
        Position actuel = file.front();
        vector<Position> voisins;
        
        file.pop();
        if (actuel == arrivee)
            break;
        voisins = Voisins(actuel);
        for (auto voisin = voisins.begin(); voisin != voisins.end(); voisin++)
        {
            if (!Marque[voisin->x][voisin->y] && Case(voisin->x, voisin->y) != CASE_TOURELLE)
            {
                Marque[voisin->x][voisin->y] = true;
                Parent[voisin->x][voisin->y] = actuel;
                file.push(*voisin);
            }
        }
    }
    element = arrivee;
    retour.push_back(arrivee);
    while (element != depart)
    {
        Position precedent = Parent[element.x][element.y];
        
        retour.push_back(precedent);
        element = precedent;
    }
    return retour;
}

