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

#include "common.h"

/* tri */
void quicksort(edge* tab, int taille) {
    // trie en place les éléments de tab 
    if (taille > 1){
        edge pivot = tab[0];
        // on place le pivot en fin de tableau (échange)
        tab[0] = tab[taille-1];
        tab[taille-1] = pivot;
        // on partitionne
        int isep = 0; // indice de séparation
        for (int i = 0; i < taille - 1; i += 1){
            edge elt = tab[i]; // élément à insérer
            if (elt.d < pivot.d) {
                tab[i] = tab[isep];
                tab[isep] = elt;
                isep += 1; // FAIRE AVANCER LE SEPARATEUR
            }
        }
        // on place le pivot à l'emplacement sep
        edge tmp = tab[isep];
        tab[isep] = pivot;
        tab[taille-1] = tmp;
        // on trie récursivement
        quicksort(tab, isep);
        quicksort(&(tab[isep+1]), taille - isep - 1);
    }
}

/* fusionne deux composantes connexes */
void fusion(int* cc, int n, int c0, int c1) {
    for (int i = 0; i < n; i += 1){
        if (cc[i] == c1){
            cc[i] = c0;
        }
    }
}

/* implémente l'ago de Kruskal : trie et sélectionne les arêtes 
renvoie le poids minimal */
float kruskal(edge* aretes, int na, int nv) {
    /* tri du tableau d'arêtes */
    quicksort(aretes, na);

    /*for (int i = 0; i < na; i += 1){
        edge e = aretes[i];
        printf("%d-%d (%f)\n", e.i, e.j, e.d);
    }*/

    // composantes connexes de chaque sommet
    int* cc = (int*) malloc(nv * sizeof(int)); 
    for (int i = 0; i < nv; i += 1){
        cc[i] = i;
    }

    // algo glouton
    int nselected = 0;
    float ltot = 0.0; /* poids de l'ACM */
    for (int i = 0; i < na; i += 1){
        edge e = aretes[i];
        if (cc[e.i] != cc[e.j]) {
            aretes[i].selected = true;
            ltot += aretes[i].d;
            fusion(cc, nv, cc[e.i], cc[e.j]);
            nselected += 1;
            if (nselected == nv - 1) { // optim : c'est fini
                break;
            }
        }
    }
    free(cc);
    return ltot;
}

int main(int argc, char* argv[]){
    printf("Yaourtophone project ! avec l'algo de Kruskal\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 Kruskal */
    float ltot = kruskal(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;
}