# include <stdio.h>
# include <stdlib.h>

struct Arc {
  int depart;
  int arrivee;
  int valeur;
};

void pile_vers_tableau(struct Pile *pile, struct Arc *tableau) {
  int i, t = taille_pile(pile);

  for(i = 0 ; i < t ; i++)
    tableau[i] = depiler(pile);
}

void tableau_vers_pile(struct Arc *tableau, int taille, struct Pile *pile) {
  while(taille > 0)
    empiler(tableau[--taille], pile);
}

int nombre_sommets, nombre_arcs, *sommets_rencontres;
struct Arc *arcs;
struct Pile *arcs_retenus = NULL, *arcs_possibles = NULL;

/*
 * Lit le fichier et remplit les variables globales.
 */
void lire_fichier(const char *nom_fichier) {
  FILE *fichier = fopen(nom_fichier, "r");
  char tampon[101] = "";
  int i;

  fscanf(fichier, "%d\n", &nombre_sommets);
  fscanf(fichier, "%d\n", &nombre_arcs);

  arcs           = malloc(nombre_arcs * sizeof(struct Arc));
  arcs_possibles = malloc(nombre_arcs * sizeof(struct Arc));
  arcs_retenus   = malloc(nombre_arcs * sizeof(struct Arc));

  for(i = 0 ; i < nombre_arcs ; i++) {
    fgets(tampon, 100, fichier);

    sscanf(tampon, "%d %d %d\n", &(arcs[i].depart), &(arcs[i].arrivee), &(arcs[i].valeur));
  }
}

int est_arc_avec_sommet(int sommet, struct Arc arc) {
//if(arc.depart == -1 && arc.arrivee == -1 && arc.valeur == -1) return 0;
  return (arc.depart == sommet || arc.arrivee == sommet) ? 1 : 0;
}

/*
 * Vérifie la présence d'un circuit dans le graphe non orienté.
int existe_circuit(int sommet) {
  int i;

  if(sommets_rencontres[sommet] == 1) {
    printf("%d", sommet);
    return 1;
  }

  sommets_rencontres[sommet] = 1;

  for(i = 0 ; i < nombre_arcs ; i++)
    if(est_arc_avec_sommet(sommet, arcs_retenus[i])) {
      if(existe_circuit(i)) {
        printf("%d", i);
        return 1;
      }
      printf("Le sommet %d forme un arc avec %d, le sommet est %d.\n", arcs_retenus[i].depart, arcs_retenus[i].arrivee, sommet);
    }

  sommets_rencontres[sommet] = -1;

  return 0;
}

void trier() {
  int i;

  for(i = 0 ; i < nombre_arcs ; i++)
    printf("%d %d %d\n", arcs[i].depart, arcs[i].arrivee, arcs[i].valeur);
}
*/

/*
int partitionner(int p, int r) {
    struct Arc pivot = arcs[p];
    int i = p-1, j = r+1;
    struct Arc temp;
    while (1) {
        do
            j--;
        while (arcs[j].valeur > pivot.valeur);
        do
            i++;
        while (arcs[i].valeur < pivot.valeur);
        if (i < j) {
            temp = arcs_possibles[i];
            arcs[i] = arcs_possibles[j];
            arcs_possibles[j] = temp;
        }
        else
            return j;
    }
}

void quickSort(int p, int r) {
    int q;
    if (p < r) {
        q = partitionner(p, r);
        quickSort(p, q);
        quickSort(q+1, r);
    }
}
*/

int main(void) {
  int i, j, k;
  int sommet_actuel = 0;

  lire_fichier("G01.txt");

  /* quickSort(0, nombre_arcs-1); */

//if(existe_circuit(0)) printf("circuit.");

  /*
  for(i = 0, j = 0 ; i < nombre_arcs ; i++) {
    arcs_retenus[j] = arcs[i];
    if(existe_circuit(arcs[i].depart))
      j--;
    else
      printf("%d\n", i);
    j++;

    for(k = 0 ; k < nombre_sommets ; k++)
      sommets_rencontres[k] = -1;
  }

  for( ; j >= 0 ; j--)
    printf("%d %d\n", arcs_retenus[j].depart, arcs_retenus[j].arrivee);

  trier();
  */

  struct Arc arc;
  arc.depart = 42;
  arc.arrivee = 1337;
  arc.valeur = 12;
  printf("bug");
  empiler(arc, arcs_retenus);
  printf("bug");
  int t = taille_pile(arcs_retenus);
  printf("bug");
  struct Arc *tbl = malloc(t * sizeof(struct Arc));
  printf("bug");
  pile_vers_tableau(arcs_retenus, tbl);
  printf("bug");
  tableau_vers_pile(tbl, t, arcs_retenus);
  printf("Taille de la pile : %d\n", taille_pile(arcs_retenus));


  /* Pour chaque sommet, on ajoute les arrêtes au tableau des possibilités,
   * à chaque itération, on ajoute au tableau final les arrêtes les plus
   * courtes.
   */

  /*
  while(1) {
    for(i = 0 ; i < nombre_arcs ; i++) {
      if(est_arc_avec_sommet(sommet_actuel, arcs[i])) {
        empiler(arcs[i], arcs_possibles);
      }
    }

  }*/

  if(arcs) free(arcs);

  return EXIT_SUCCESS;
}