#include <iostream>
#include <fstream>
#include "struct.h"
#include "menu.h"
using namespace std;


int main()
{
    /****DECLARATIONS****/
    Matrice m;
    Matrice d;
    Dijkstra dij;
    m.nb_sommets = 7;
    d.nb_sommets = 7;
    int depart = 0;
    int current;
    bool done[m.nb_sommets];
    char * c [] = {"Charger un graphe", "Afficher le graphe charge",  "Sauvegarder un graphe en .txt", "Lancer l'algorithme", "Quitter" } ;
    Menu * menu = new Menu("Menu principal", 5, c, "CASLQ") ;
    int b=1;

    for(int i = 0; i < m.nb_sommets; i++)
        done[i] = false;

    /****Mise A Zero****/
    for(int i = 0; i < 100; i++)
    {
        for(int i2 = 0; i2 < 100; i2++)
        {
            m.matrice[i][i2] = -1;
            d.matrice[i][i2] = -1;
            dij.suite[i].liste[i2] = -1;
        }
        dij.distance[i] = -1;
        dij.suite[i].nb = 0;
    }








    while (b=1)
 {
  menu->Affiche() ;
  int r = menu->Reponse() ;
  char chn [255] ;
  char * index ;
  //Bool flag, sym = vrai ;
  char rep [3] ;
  char fichier[12] ;
  int n, i, j, t, k, p;
  FILE * f;
  int  sommet;
  int choix;
switch (r)
{
  case 0 :{

    /****OUVRIR FICHIER****/

    do
    {
        system("cls");
        cout << "Quel fichier voulez vous ouvrir ?" << endl;
        cout << "1 : G01" << endl;
        cout << "2 : G04" << endl;
        cout << "3 : G09" << endl;
        cout << "4 : G12" << endl;

        cin >> choix;
    }while(choix < 0 || choix > 4);

    char* choix_fichier;
    if(choix == 1)
        choix_fichier = "graphe.txt";
    else if(choix == 2)
        choix_fichier = "fichier2.txt";
    else if(choix == 3 || choix == 4)
        cout << "L'algorithme de Dijkstra ne marche pas dans ce programme avec des valeurs négatives." << endl;

    ifstream fichier(choix_fichier, ios::in);  // on ouvre le fichier en lecture

    if(fichier)  // si l'ouverture a réussi
    {
        int depart, arrivee, valeur;
        fichier >> m.nb_sommets;
        for (int i=0; i < m.nb_sommets ; i++)
        {
            m.matrice[i][i] = 0;
        }

        do
        {
            fichier >> depart;
            if(depart != -1)
            {
                fichier >> arrivee >> valeur;
                m.matrice[depart][arrivee] = valeur;
            }
        }while(depart != -1);

        fichier.close();  // on ferme le fichier
    }
  }//fin case0
break;
    case 3 :{
        /****LANCER DIJKSTRA****/
    // Initialisation

    system("cls");
    cout << "Quel sommet voulez-vous prendre comme point de depart ?" << endl << endl;
    cout << "Il y a " << m.nb_sommets << " sommets numerotes de 0 a " << m.nb_sommets-1 << endl;
    cin >> choix;

    depart = choix;

    current = depart;
    dij.distance[depart] = 0;
    dij.suite[depart].nb = 0;
    dij.suite[depart].liste[0] = 0;

    //On a pratiqué l'initialisation
    system("cls");
     cout << "    ";
    for(int i = 0; i < m.nb_sommets; i++)
        cout << i << "      ";
    cout << endl;

    //Déroulement de l'algorithme
    int minus;

    do
    {
        cout << endl;
        cout << current << "  ";
        for(int i = 0; i < m.nb_sommets; i++)
        {
            if(m.matrice[current][i] != -1) //S'il existe un chemin entre l'état courant et l'état "i"
            {
                if(dij.distance[i] == -1 || (dij.distance[i] != -1 && dij.distance[current] + m.matrice[current][i] < dij.distance[i]))
                // S'il n'y avait pour le moment aucune distance calculée pour aller à "i" ou si cette distance est supérieure à la nouvelle
                {
                    //On écrit celle ci plus la distance nécessaire pour arriver dans l'état courant
                    dij.distance[i] = dij.distance[current] + m.matrice[current][i];

                    //Et on met à jour le chemin complet pour y arriver.

                    for(int i2 = 0; i2 < dij.suite[i].nb; i2++)
                        dij.suite[i].liste[i2] = -1;

                    if(current == depart)
                    {
                        dij.suite[i].nb = 0;
                        dij.suite[i].liste[0] = depart;
                    }

                    else
                    {
                        dij.suite[i].nb = dij.suite[current].nb + 1;
                        for(int i_nb = 0; i_nb <= dij.suite[current].nb; i_nb++)
                        {
                            dij.suite[i].liste[i_nb] = dij.suite[current].liste[i_nb];
                        }
                        dij.suite[i].liste[dij.suite[i].nb] = current;
                    }
                }

                //et on écrit ce qu'il faut sur la console
                if(dij.distance[i] < 10)
                cout << "  " << dij.distance[i] << "," << dij.suite[i].liste[dij.suite[i].nb] << " |";
                else
                cout << " " << dij.distance[i] << "," << dij.suite[i].liste[dij.suite[i].nb] << " |";

            }
            else if(dij.distance[i] != -1)
            {
                if(dij.distance[i] < 10)
                cout << "  " << dij.distance[i] << "," << dij.suite[i].liste[dij.suite[i].nb] << " |";
                else
                cout << " " << dij.distance[i] << "," << dij.suite[i].liste[dij.suite[i].nb] << " |";
            }
            else
                cout << " ##,# |";
        }
        cout << endl;

        done[current] = true;
        //Il reste à calculer le plus court chemin dans les distances existantes que l'on ait pas déjà parcouru
        minus = -1;

        for(int i = 0; i < m.nb_sommets; i++)
        {
            if(dij.distance[i] != -1)//S'il y a une distance déjà calculée à l'état "i"
            {
                if(done[i] == false)//Et si on n'a pas déjà parcouru cette distance
                {
                    if(minus == -1)//Et si on a pas encore de distance minimale
                        minus = i;
                    else if(dij.distance[i] < dij.distance[minus])
                        minus = i;
                }
            }
        }

        current = minus; // On va maintenant dérouler l'algorithme sur le nouvel état
    }while(minus != -1);

    //On écrit maintenant les chemins et les longueurs obtenues
    cout << endl;
    cout << "Plus courts chemins : longueur" << endl;
    for(int i = 0; i < m.nb_sommets; i++)
    {
        if(i == depart)
            cout << depart << " : " << depart << endl;

        else
        {
            for(int i_nb = 0; i_nb <= dij.suite[i].nb; i_nb++)
            {
                cout << dij.suite[i].liste[i_nb] << " ";
                cout << "- ";
            }
            cout << i << " : " << dij.distance[i] << endl;
        }
    }
    }
    break;
    return 0;

}
}

}