#include "Beloeil-Masson-tp3-arcs.h"

using namespace std;

// Constructeur de base , initialise les variables de chaque structures

arcs::arcs(int dep, int arr, int dis){
    _dep=dep;
    _arr=arr;
    _dis=dis;
}

sommet::sommet(int id,int place,arcs tmparc){
    _place=place;
    _id=id;
    listeArcs.push_back(tmparc);
    _rel=false;
}
sommet::sommet(int id,int place){
    _place=place;
    _id=id;
    _rel=false;
}

graph::graph(){

}

graph::graph(string mon_fichier){
    ifstream File;
    File.open(mon_fichier.c_str());
    string tmp;

    if(File) {
        // On elimine la première ligne

        File >> tmp;
        while(tmp != "FIN") {
          string dep_tmp;
          dep_tmp = tmp;
          string dis_tmp;
          File >> dis_tmp;
          string arr_tmp;
          File >> arr_tmp;

          File >> tmp;

          /** Initialisation des arcs */
          arcs tmparc(atoi(dep_tmp.c_str()),atoi(arr_tmp.c_str()),atoi(dis_tmp.c_str()));
          listeArcs.push_back(tmparc);
        }

    }
    // génération des sommets
    // si ca marche pas
    /** pour chaque arc
        rajouter le premier sommet trouver avec l'arc correspondant

        pour chaque arc regarder les point d'arriver
            si ils existe pas, creer un sommet vide */


    int i=0;
    for (unsigned int j=0; j<listeArcs.size(); j++){
        bool cont=false;


        if (listeSom.size() != 0){ for (unsigned int k=0; k < listeSom.size(); k++){
                if ( listeArcs[j]._dep == listeSom[k]._id ) cont=true;

        }}
        if (cont){ // si on a trouver le sommet d'un depart ou d'une arriver
             unsigned int k=0;
             for (k=0; k < listeSom.size(); k++){
                if ( listeArcs[j]._dep == listeSom[k]._id ){
                    break;
                }
             }
             listeSom[k].listeArcs.push_back(listeArcs[j]);
        }
        if (! cont){ // si on a pas trouver de sommet on le rajoute a la liste
                sommet s1(listeArcs[j]._dep,i,listeArcs[j]);i++;
                listeSom.push_back(s1);
            }

    }


    for (unsigned int j=0; j<listeArcs.size(); j++){
        bool cont=false;
        for (unsigned int k=0; k < listeSom.size(); k++){
            if ( listeArcs[j]._arr == listeSom[k]._id ) cont=true;
        }
        if (! cont){ // si on a pas trouver le sommet d'arriver, on le rajoute
            sommet s1(listeArcs[j]._arr,i);i++;
            listeSom.push_back(s1);


        }

    }


    /*
        Pour chaque arc
            si le depart ou l'arriver : deja dans la list
                si l'arc est deja dans la list=> nexr
                sinon le rajouter
            sinon creer nouveau sommet id (dep ou arriver) place=boucle, arc=actuel
        */
    cout << "fin Constructeur " << endl;
}

void graph::setPrim(graph &g2){
    cout << " Debut de l'algorithm de Prim : " << endl;

    bool val=false,couvrant=false,val2=false;

    g2.listeSom.push_back(listeSom[0]);

    vector < arcs > arcstmp; // arc temporaire contenant les S'
    vector < arcs > arcstmp2; // arc temporaire epuré des S' d'arriver

    //couvrant
    couvrant=false;
    while (!couvrant){
        arcstmp.clear();
        arcstmp2.clear();

        // generation arc temporaire
        // arcstmp contient la liste des arretes ayant pour "debut" ou pour "fin" les sommets de S'
        // S' étant représenter par le vecteur de sommet g2.listSom
        for (unsigned int i=0; i< listeArcs.size(); i++){
            for (unsigned int j=0; j<g2.listeSom.size(); j++){
                if (listeArcs[i]._dep == g2.listeSom[j]._id){
                    arcstmp.push_back(listeArcs[i]);
                }
                if (listeArcs[i]._arr == g2.listeSom[j]._id){
                    arcstmp.push_back(listeArcs[i]);
                }
            }
        }

        // On génére un deuxieme arcstmps : arcstmp2 pour n'avoir que ceux ne génère pas de lien vers S', ( évitant ainsi les cycles)
        val=false;
        for (unsigned int i=0; i< arcstmp.size(); i++){
            for (unsigned int j=0; j<g2.listeSom.size(); j++){
                if (arcstmp[i]._dep == g2.listeSom[j]._id ){
                    val=false;
                    for (unsigned int k=0; k<g2.listeSom.size();k++){
                        if ( arcstmp[i]._arr == g2.listeSom[k]._id){
                            val=true;

                        }
                    }// fin de recherche des sommets
                    if (!val){
                        arcstmp2.push_back(arcstmp[i]);
                    }
                }// FIN DU CHECK DES "DEPART"
                if (arcstmp[i]._arr == g2.listeSom[j]._id ){
                    val=false;
                    for (unsigned int k=0; k<g2.listeSom.size();k++){
                        if ( arcstmp[i]._dep == g2.listeSom[k]._id){
                            val=true;
                        }
                    }// fin de recherche des sommets
                    if (!val){
                        arcstmp2.push_back(arcstmp[i]);
                    }
                }// FIN DU CHECK DES ""DEPART"ARRIVE"

            }
        }// FIN du parcour de arctmp

        // On recherche l'arc de poid minimum dans la liste des arcs qu'on a retenue.
        arcs min=arcstmp2[0];
        for (unsigned int i=1; i < arcstmp2.size(); i++){
            if (( arcstmp2[i]._dis < min._dis )){
                min=arcstmp2[i];
            }
        } // fin de check plus petit arctmp2

        // ajout de l'arc trouver a la liste des arcs finaux de G'
        g2.listeArcs.push_back(min);
        cout << " Arrete ajouter : " << min._dep << " " << min._arr << " || poid : " << min._dis << endl;
        int place=0;
        int tmp=0;
        // On cherche ensuite le sommet rajouter par le nouvel arcs. Et on met a jour S'
        for (unsigned int i=0; i<g2.listeSom.size();i++){
           if (min._dep == g2.listeSom[i]._id){
               tmp=g2.listeSom[i]._id;
           }
           if (min._arr == g2.listeSom[i]._id){
               tmp=g2.listeSom[i]._id;
           }
        }
        if (min._dep==tmp){
            sommet stmp(min._arr,place);
            place++;
            g2.listeSom.push_back(stmp);
        }
        if (min._arr==tmp){
            sommet stmp(min._dep,place);
            place++;
            g2.listeSom.push_back(stmp);
        }


        // Mise a jour des booleen qui marque si le sommet du graphe est relié ou non
        for (unsigned int i=0; i< g2.listeArcs.size(); i++){
            listeSom[getPlace(g2.listeArcs[i]._dep)]._rel=true;
            listeSom[getPlace(g2.listeArcs[i]._arr)]._rel=true;
        }
        val2=true;
        // Si tout les sommets sont relié, l'arbre est couvrant.
        for (unsigned int i=0; i< listeSom.size();i++){
            if( listeSom[i]._rel == false) val2=false;
        }
        if (val2){ couvrant=true;}

    }
    cout << endl<< "Fin du calcul de l'algorithme " << endl<< endl;
}

void graph::printgraph(){

    cout << "Affichage du graphe G' " << endl;
    // s'affiche dans l'ordre de creation du parseur
    int tmp=0;
    for (unsigned int i=0; i< listeArcs.size(); i++){
        tmp=tmp+listeArcs[i]._dis;
        cout << " arrete : " << listeArcs[i]._dep << "  "<< listeArcs[i]._arr << " ||  poid : " << listeArcs[i]._dis << endl;
    }
    cout << " Algorithm de Prim : Poid total : " << tmp << endl;


    }