#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <assert.h>
#include <stdbool.h>

#include "common.h"


float prim(edge* aretes, int na, int nv){
    bool* atteint = malloc(nv * sizeof(bool));
    for (int i = 0; i < nv; i+=1){
        atteint[i] = false;
    }
    // on part du sommet 0 (ou autre ...)
    atteint[0] = true;
    float ltot = 0.; /* poids de l'ACM */

    for (int tour = 1; tour < nv; tour += 1){
        // on cherche l'arete la moins couteuse permettant 
        // d'atteindre un sommet non-atteint à partir d'un sommet atteint
        int num_a = -1;
        int poids_a = -1;
        for (int i = 0; i < na; i += 1){
            edge a = aretes[i];
            if ((atteint[a.i] && !atteint[a.j]) || (atteint[a.j] && !atteint[a.i])){
                assert(!a.selected);
                if (num_a == -1 || a.d < poids_a) {
                    num_a = i; poids_a = a.d;
                }
            }
        }
        assert(num_a != -1);
        // on selectionne l'arete, et on marque le sommet atteint
        aretes[num_a].selected = true;
        atteint[aretes[num_a].i] = true;
        atteint[aretes[num_a].j] = true;
        ltot += aretes[num_a].d;
    }
    free(atteint);
    return ltot;
}


int main(int argc, char* argv[]){
    printf("Yaourtophone project ! avec l'algo de Prim\n");
    assert(argc == 3);
    
    const char* fichier_in = argv[1];
    const char* fichier_out = argv[2];


    /* lecture du fichier */
    int n;
    node* villes = lireFichier(fichier_in, &n);

    /* création du tableau d'arêtes */
    int na;
    edge* aretes = creerAretes(villes, n, &na);

    /* algorithme de Prim */
    float ltot = prim(aretes, na, n);

    printf("longueur totale : %f\n", ltot);

    /* export geojson */
    exporter(fichier_out, aretes, na, villes, n);

    // libération
    free(villes);
    free(aretes);
    return 0;
}