#include "api.hh"
#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
using namespace std;

#define Map vector<vector<etat_case>> 


struct EPosition{  // Enhanced position
    int colonne;
    int ligne;
    int niveau;
    position mama_pos;

    bool operator<(const EPosition& other){
        int diffx = (colonne - mama_pos.colonne), diffy = (ligne - mama_pos.ligne);
        int dist_sq = diffx * diffx + diffy * diffy;

        int other_diffx = (other.colonne - other.mama_pos.colonne), other_diffy = (other.ligne - other.mama_pos.ligne);
        int other_dist_sq = other_diffx * other_diffx + other_diffy * other_diffy;
        return dist_sq < other_dist_sq;
    }
};

struct as_path{
    vector<position> cur;
    int cost;

    bool operator<(as_path& other){
        return cost < other.cost;
    }
};


#pragma region Constantes
const int CONQUETE_NIDS = 0;
const int RECHERCHE_PAIN = 1;
const vector<pair<int, int>> DIR = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
#pragma endregion

#pragma region Variables
int player_id;
// Map map(HAUTEUR, vector<etat_case>(LARGEUR));  // do we really need this?
vector<position> nids(0);
vector<position> nids_obtenus(0);
int current_phase;
map<int, vector<direction>> paths;
map<direction, pair<int, int>> MDIR;
#pragma endregion



vector<position> sort_by_distance(vector<position>& pos, position& mama_pos){
    
    vector<EPosition> ep(pos.size());
    for(int i = 0; i < pos.size(); i++){
        ep.at(i) = {pos.at(i).colonne, pos.at(i).ligne, pos.at(i).niveau, mama_pos};
    }

    sort(ep.begin(), ep.end());

    vector<position> ret(pos.size());
    for(int i = 0; i < pos.size(); i++){
        ret.at(i) = {ep.at(i).colonne, ep.at(i).ligne, ep.at(i).niveau};
    }
    return ret;
}



bool can_exit_1st_phase(){
    // 1. Tous les nids sont occupes
    int counter = 0;
    for(position nid_p : nids){
        etat_nid etat = info_nid(nid_p);
        if(!(etat == JOUEUR_0 || etat == JOUEUR_1)){
            counter++;
        }
    }
    if(counter == 0){
        return true;
    }

    
    // 2. Atteint la 20eme tour
    if(tour_actuel() > 20){
        return true;
    }


    return false;
}


void search_nest_path(troupe tr){
    vector<position> nids_sorted = sort_by_distance(nids, tr.maman);

        position target;
        for(position nid_p : nids_sorted){
            if(info_nid(nid_p) == LIBRE){
                target = nid_p;
                break;
            }
        }

        debug_poser_pigeon(target, PIGEON_BLEU);

        direction cur_dir = tr.dir;
        pair<int, int> opposite = MDIR.at(cur_dir);
        opposite.first *= -1; opposite.second *= -1;

        for(pair<int, int> p : DIR){
            position new_case = {tr.maman.colonne + p.first, tr.maman.ligne + p.second, tr.maman.niveau};
            if(p != opposite){
                vector<direction> dirs = trouver_chemin(new_case, target);
                if(dirs.size() > 0){
                    paths.at(tr.id) = dirs;
                    break;
                }
            }
        }
}


void search_bread_path(troupe tr){
    vector<position> br = pains();
    if(br.size() > 0){

        vector<position> sorted_breads = sort_by_distance(br, tr.maman);
        position target = sorted_breads.at(0);
        debug_poser_pigeon(target, PIGEON_BLEU);

        direction cur_dir = tr.dir;
        pair<int, int> opposite = MDIR.at(cur_dir);
        opposite.first *= -1; opposite.second *= -1;

        for(pair<int, int> p : DIR){
            position new_case = {tr.maman.colonne + p.first, tr.maman.ligne + p.second, tr.maman.niveau};
            if(p != opposite){
                vector<direction> dirs = trouver_chemin(tr.maman, new_case);
                if(dirs.size() > 0){
                    paths.at(tr.id) = dirs;
                    break;
                }
            }
        }
    }
}



// Fonction appelée au début de la partie.
void partie_init(void)
{
    player_id = moi();
    current_phase = CONQUETE_NIDS;
    MDIR[NORD] = make_pair(0, 1);
    MDIR[SUD] = make_pair(0, -1);
    MDIR[EST] = make_pair(1, 0);
    MDIR[OUEST] = make_pair(-1, 0);


    for(troupe tr : troupes_joueur(player_id)){
        paths[tr.id] = vector<direction>(0);
    }

    #pragma region Charge la carte
    for(int y = 0; y < HAUTEUR; y++){
        for(int x = 0; x < LARGEUR; x++){
            position pos = {y, x, 0};
            // map.at(y).at(x) = info_case(pos);
            // ajoute au tableau si c'est un nid
            if(info_case(pos).contenu == NID){
                nids.push_back(pos);
            }
        }
    }
    #pragma endregion
}


// Fonction appelée à chaque tour.
void jouer_tour(void)
{
    for(troupe tr : troupes_joueur(player_id)){
        debug_poser_pigeon(tr.maman, PIGEON_JAUNE);
        if(current_phase == CONQUETE_NIDS){

            
            if(can_exit_1st_phase()){  // exit 1st phase
                current_phase = RECHERCHE_PAIN;
                paths.at(tr.id).clear();
            }else{  // continue
                search_nest_path(tr);

                if(paths.at(tr.id).size() > 0){ // if instructions left
                    erreur can_continue = OK;
                    while(can_continue == OK && paths.at(tr.id).size() > 0){
                        can_continue = avancer(tr.id, paths.at(tr.id).at(0));
                        paths.at(tr.id).erase(paths.at(tr.id).begin());
                    }
                }
            }
            
        }

        if(current_phase == RECHERCHE_PAIN){
            debug_poser_pigeon({0, 0, 0}, PIGEON_ROUGE);
            debug_poser_pigeon({39, 39, 0}, PIGEON_BLEU);
            debug_poser_pigeon({0, 39, 0}, PIGEON_JAUNE);


            paths.at(tr.id).clear();
            search_bread_path(tr);


            if(paths.at(tr.id).size() > 0){ // if instructions left
                erreur can_continue = OK;
                while(can_continue == OK && paths.at(tr.id).size() > 0){
                    can_continue = avancer(tr.id, paths.at(tr.id).at(0));
                    paths.at(tr.id).erase(paths.at(tr.id).begin());
                }
            }
        }
     
    }

    for(troupe tr : troupes_joueur(player_id)){
        if(tr.pts_action > 2){
            grandir(tr.id);
        }
    }
    

}

// Fonction appelée à la fin de la partie.
void partie_fin(void)
{
    // TODO
    
    
}


