#include "Wakim Odier tp1.h"

//Fonction initialisation à faire.
/** Fonction */
/** Entrées :
int i (valeur à placer dans value)
list_Node* l (maillon précédent, NULL si inexistant)    */
/** Sortie : list_Node* (Pointeur vers le nouveau maillon)  */
/** Utilité : Crée un maillon de type list_Node pour une liste chainée  */
list_Node* new_Node(int i, list_Node* l)
{
    list_Node* lnew = (list_Node*) malloc(sizeof(list_Node)); // allocation de l'espace
    lnew->value = i; //initialisation des variables
    lnew->next = NULL;
    lnew->arc = NULL;
    if(!l) // vérification du prev
    {
        return lnew;
    }
    else
    {
        l->next = lnew;
    }
    return lnew;
}

/** Fonction */
/** Entrées :
int nbS (Permet de savoir combien d'éléments nous devons avoir dans notre liste chainée)*/
/** Sortie : list_Node* un pointeur vers la tête de la chaine*/
/** Utilité : Crée une liste chainée de nbS élèments facilement*/
list_Node* cree_list(int nbS)
{
    list_Node *lhead;
    if(nbS <= 0) return NULL; // vérification des entrées
    else
    {
        list_Node *l;
        lhead = l = new_Node(0, NULL);
        for(int i=1; i<nbS; i++) // boucle de création pour la chaine
        {
            l = new_Node(i, l); // crée et chaine
        }
    }
    return lhead;
}

/** Fonction */
/** Entrées :
list_Node* l (un pointeur vers la tête de la liste qu'on veut supprimer)*/
/** Sortie : void*/
/** Utilité : Libère l'espace mémoire occupé par une chaine*/
void free_list(list_Node* l)
{
     if(!l) return;
     if(l->next) free_list(l->next);// récursivité sur next
     if(l->arc) free_list(l->arc);// récursivité sur arc
     if(!(l->arc) && !(l->next)) free(l);// libération d'un élèment
     return;
}

/** Fonction */
/** Entrées :
list_Node* G (la chaine dans laquelle on cherche un élèment)
int ext (valeur que l'on cherche) */
/** Sortie : list_Node* l'élèment que l'on cherchait*/
/** Utilité : rechercher un élèment en particulier dans une chaine*/
list_Node* recherche(list_Node* G, int ext)
{
    list_Node *l = G;
    if(!G || ext<0) return NULL; // vérification des entrées
    else
    {
        while(l && l->value != ext) // parcourt la liste à la recherche de notre valeur
        {
            l = l->next;
        }
    }
    return l;
}

/** Fonction */
/** Entrées :
list_Node* l élèment auquel on veut ajouter un arc
int ext (une des valeurs pour l'arc)
int val (la seconde valeur pour l'arc)*/
/** Sortie : bool (retourne false si il y a une erreur) */
/** Utilité : crée un arc*/
bool add_arc(list_Node* l, int ext, int val)
{
    if(!l || ext<0) return false;// vérification des entrées
    else
    {
        list_Node* ltemp = l;
        while(ltemp->arc) // boucle pour se placer correctement
        {
            ltemp = ltemp->arc;
        }
        ltemp->arc = new_Node(ext, NULL); // création de l'arc
        ltemp->arc->next = new_Node(val, NULL); // création de l'arc
    }
    return true;
}

/** Fonction */
/** Entrées :
string nom (fichier contenant le graph)*/
/** Sortie : list_Node* un pointeur vers la SDD contenant les données*/
/** Utilité : lire un graph dans le mode succ*/
list_Node* lecture_graphe_succ (string nom)
{
    list_Node* G;
    ifstream fichier(nom.c_str(), ios::in); // ouverture du fichier
    if(fichier) // si on ouvre correctement
    {
        int nbSommets, extremiteI, extremiteT, valeurArc;
        list_Node* l;
        fichier >> nbSommets;
        G = cree_list(nbSommets); // création de la liste qui contient notre graphe
        fichier >> extremiteI;
        while(extremiteI != -1) // permet de lire tout le fichier
        {
            fichier >> extremiteT;
            fichier >> valeurArc;

            if(!(l = recherche(G,extremiteI))) return false; // on stocke dans la SDD

            if(!(add_arc(l,extremiteT, valeurArc))) return false; // on stocke dans la SDD


            fichier >> extremiteI;
        }
    }
    else // pas de fichier, pas de lecture
    {
        return NULL;
    }
    return G;
}

/** Fonction */
/** Entrées :
string nom (nom du fichier contenant le graph)*/
/** Sortie : list_Node* un pointeur vers la SDD contenant les données*/
/** Utilité : lire un grap dans le mode prev*/
list_Node* lecture_graphe_prev (string nom)
{
    list_Node* G;
    ifstream fichier(nom.c_str(), ios::in);
    if(fichier)
    {
        int nbSommets, extremiteI, extremiteT, valeurArc;
        list_Node* l;
        fichier >> nbSommets;
        G = cree_list(nbSommets); // création de la chaine contenant le graph

        fichier >> extremiteI;
        while(extremiteI != -1) // permet de lire tout le fichier
        {
            fichier >> extremiteT;
            fichier >> valeurArc;

            if(!(l = recherche(G,extremiteT))) return false; // on stocke dans la SDD
            if(!add_arc(l,extremiteI, valeurArc)) return false; // on stocke dans la SDD

            fichier >> extremiteI;
        }
    }
    else
    {
        return NULL;
    }
    return G;
}

/** Fonction */
/** Entrées :
list_Node* G (la SDD contenant un graphe) */
/** Sortie : void */
/** Utilité : affiche un graphe, permet la vérification de la lecture facilement*/
void aff_graphe(list_Node* G)
{
    if(!G) return;

    list_Node* l = G;
    list_Node* larc;
    while(l) // permet de parcourir toute la liste
    {
        printf("Sommet : %d \n", l->value);
        larc = l;
        while(larc->arc) // affichage de tous les arcs
        {
            larc = larc->arc;
            printf(" %d %d %d \n", l->value, larc->value, larc->next->value);
        }

        l = l->next;
    }
}
/** Fonction */
/** Entrées :
list_Node* Ghead (la SDD des résultats de belleman dans laquel on copie)
list_Nade* lhead (la SDD des résultats de bellman qu'on veut copier)*/
/** Sortie : void*/
/** Utilité : affiche et sauvegarde une SDD Bellman*/
list_Node* lbell_equal(list_Node* lhead, list_Node* Ghead)
{
    if(!lhead) return NULL;
    list_Node* l = lhead;
    list_Node* G = Ghead;
    list_Node* tp;
    int nbS = 1;
    while(l->next)
        {
            nbS++;
            l = l->next;
        }
    l = lhead;
    G =  cree_list(nbS);
    tp = G;
    while(l) // fin de l'initialisation de la SDD
        {
            if(!(add_arc(G, 0, 0))) return NULL; //ajout des arcs (ici le couple longueur, pivot)
            G = G->next;
            l = l->next;

        }
    G = tp;
    l = lhead;
    while(l)
    {
        G->value = l->value;
        G->arc->value = l->arc->value;
        G->arc->next->value = l->arc->next->value;
        G = G->next;
        l = l->next;
    }
    return tp;
}
/**------------- BELLMAN -----------*/

/** Fonction */
/** Entrées :
list_Node* G (le graphe)
int source (le sommet de départ pour l'algorithme)
string name (nom du fichier pour la sauvegarde)*/
/** Sortie : void */
/** Utilité : copie*/
void bellman(list_Node* G, int source, string name)
{
    list_Node* l = G;
    if(!G || source <0) // vérification des entrées
    {
        return;
    }
    else
    {
        int nbS=1, somme=1;
        list_Node* lbellhead;
        list_Node* lbell;
        list_Node* lbelltemp;
        bool test = true;
        while(l->next)
        {
            nbS++;
            l = l->next;
        }
        if(source > nbS-1 || source < 0) return; // vérification de la variable source
        lbellhead =  cree_list(nbS);
        lbelltemp = lbell = lbellhead;

        lbell = G;
        while(lbell) // calcule du max pour avoir une valeur d'infini, on ajoutes toutes les valeurs positives des arcs + 1 pour être sûr qu'on ne peut pas avoir un trajet plus long
        {
            lbelltemp = lbell;
            while(lbelltemp->arc)
            {
                if (lbelltemp->arc->next->value >= 0)
                {
                    somme = somme + lbelltemp->arc->next->value;
                }
                lbelltemp = lbelltemp->arc;
            }
            lbell = lbell->next;
        }

        lbell = lbellhead;
        while(lbell) // fin de l'initialisation de la SDD
        {
            if(!(add_arc(lbell, somme, source))) return; //ajout des arcs (ici le couple longueur, pivot)
            lbell = lbell->next;

        }
        lbell = lbellhead;
        lbell = recherche(lbellhead, source);
        lbell->arc->value = 0; // initialisation très importante du trajet le plus court pour notre point de départ
        list_Node* resultat = NULL; // pour stocker le résultat de l'étape précédente
        list_Node* tp; // tête de la chaine contenant le résultat de l'étape précèdente
        for(int i=0 ; i<nbS && test == true; i++) // boucle de l'algorithme de Bellman
        {
            lbell = lbellhead;
            free_list(resultat);
            tp = resultat = lbell_equal(lbell, resultat);// permet de ne pas utiliser les résultat de l'étape en court pour cette même étape
            test = false;
            while(resultat) // parcourt la totalité de la SDD contenant Bellman
            {
                lbelltemp = recherche(G, resultat->value); //on récupère les arcs ayant pour arrivée le point pour lequel on veut calculer le trajet le ^plus court
                while(lbelltemp->arc) // permet de parcourir toutes les possibilités
                {
                    l = recherche(tp, lbelltemp->arc->value); // on se place pour avoir les valeur de Pi de l'occurence précèdente
                    if(resultat->arc->value > l->arc->value + lbelltemp->arc->next->value && l->arc->value!=somme) // si on trouve un trajet plus court
                    {
                        lbell = recherche(lbellhead, resultat->value); // on se positionne
                        lbell->arc->value = l->arc->value + lbelltemp->arc->next->value; // mise à jour de la longueur
                        lbell->arc->next->value = lbelltemp->arc->value; // mise à jour du pivot
                        test = true; // permet de savoir si on a eu une modification ou non, permet de stopper bellman avant sa fin théorique maximale
                    }
                    lbelltemp = lbelltemp->arc;
                }
                resultat = resultat->next;
            }
            aff_bellman(lbellhead, i, somme, name); // Sauvegarde de l'étape
        }
        free_list(resultat);
        free_list(tp);
        free_list(lbellhead); // libération de la SDD de bellman, on pourait la retourner si on le voulait mais ce n'est pas utile dans notre cas de figure
    }


    return;
}

/** Fonction */
/** Entrées :
list_Node* G (la SDD des résultats de belleman)
int step (numéro de l'étape)
int somme (trajet max = infinity)
string name (nom du fichier pour la sauvegarde)*/
/** Sortie : void*/
/** Utilité : affiche et sauvegarde une SDD Bellman*/
void aff_bellman(list_Node* G, int step, int somme, string name)
{
    if(!G) return;
    name = name + "R.txt"; // le nom du fichier de sauvegarde
    ofstream fichier(name.c_str(), ios::app); // le fichier
    if(fichier)
    {
        list_Node* l = G;
        fichier << "step : " << step << endl; // écriture
        printf("step : %d \n", step);
        while(l) // permet le parcours de la totalité de la SDD de bellman
        {
            if(l->arc->value == somme)
            {
                fichier << "Pi(" << l->value << ") : (infinity, " << l->arc->next->value << ") " << endl; // écriture
                printf("Pi(%d) : (infinity, %d) \n", l->value, l->arc->next->value);
            }
            else
            {
                fichier << "Pi(" << l->value << ") : (" << l->arc->value << ", " << l->arc->next->value << ") " << endl; // écriture
                printf("Pi(%d) : (%d, %d) \n", l->value, l->arc->value, l->arc->next->value);
            }

            l = l->next;
        }
    }
    else return; // pas de fichier pas de résultat !
}