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

/* noeud : identifiant entre 0 et N-1 */
typedef int nodeID;

/* représente une ville */
struct node_s {
    char nom[100]; // nom
    float x; // longitude
    float y; // latitude
    int hab; // nombre d'habitants
};

typedef struct node_s node;

/* représente une liaison possible */
struct edge_s {
    nodeID i;
    nodeID j;
    float  d;
    bool selected; // pour l'algorithme de Kruskal (ou Prim)
};

typedef struct edge_s edge;

/* import : lit le fichier filename contenant des descriptions
de villes et alloue dans le tas un tableau de n villes 
NB : n est renvoyé via le pointeur n */
node* lireFichier(const char* filename, int* n) {
    FILE* f = fopen(filename, "r");
    if (f != NULL) {
        int nv;
        if (fscanf(f, "%d\n", &nv) == 1){
            node* villes = malloc(nv * sizeof(node));
            for (int i = 0; i < nv; i += 1) {
                node v;
                if (fscanf(f, "%s %d %f %f\n", v.nom, &v.hab, &v.x, &v.y) == 4) {
                    villes[i] = v;
                } else {
                    printf("Erreur de lecture 2\n");
                    exit(0); // erreur de lecture
                    return NULL;
                }
            }
            fclose(f);
            *n = nv;
            return villes;
        }
    }
    printf("Erreur de lecture 1\n");
    exit(0); // erreur de lecture
    return NULL;
}

float dist(node n, node m) {
    return 107 * sqrt(pow(n.x-m.x,2) + pow(n.y-m.y,2));
}

/* crée l'ensemble des arêtes susceptibles de relier les villes 
les arêtes sont allouées dans le tas. Leur nombre na est 
renvoyé via pointeur */
edge* creerAretes(node* villes, int nv, int* na){
    *na = (nv * (nv - 1)) / 2;
    edge* aretes = (edge*) malloc(*na * sizeof(edge));
    assert(aretes != NULL);
    int c = 0;
    for (int i = 0; i < nv; i += 1){
        for (int j = i + 1; j < nv; j += 1){
            aretes[c].i = i;
            aretes[c].j = j;
            aretes[c].d = dist(villes[i], villes[j]);
            aretes[c].selected = false;
            c += 1;
        }
    }
    return aretes;
}

//* 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;
        }
    }
}

/* export : écrit dant le fichier filename les informations nécessaires 
à l'affichage des arêtes sélectionnées au format geojson */
void exporter(const char* filename, edge* aretes, int na, node* villes, int nv){
    FILE* f = fopen(filename, "w");
    fprintf(f,"{\"type\": \"FeatureCollection\",\"features\": [\n");
    bool first = true;
    for (int i = 0; i < na; i += 1) {
        edge e = aretes[i];
        if (e.selected) {
            if (!first) {
                fprintf(f, ",");
            }
            fprintf(f, "{\"type\": \"Feature\", \"geometry\": {\"type\": \"LineString\",");
            fprintf(f,  "\"coordinates\": [[%f, %f], [%f, %f]]}}\n", 
                    villes[e.i].x, villes[e.i].y, villes[e.j].x, villes[e.j].y);
            first = false;
        }
    }
    fprintf(f,"]}");
    fclose(f);
}


int main(){
    printf("Yaourtophone project !\n");

    const char* fichier_in = "villes20.txt";
    const char* fichier_out = "villes20.geojson";

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

    /* affichage des villes */
    for (int i = 0; i < n; i++) {
        node v = villes[i];
        printf("ville%d : %s (%d hab) %f %f\n", i, v.nom, v.hab, v.x, v.y);
    }

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

    /* algorithme de Kruskal */

     /* tri du tableau d'arêtes */
    quicksort(aretes, na);

    /* affichage des arètes */
    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(n * sizeof(int)); 
    for (int i = 0; i < n; i += 1){
        cc[i] = i;
    }

    // algo glouton
    int nselected = 0;
    float ltot = 0.0; // pour 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;
            printf("arête choisie : %s-%s (%f)\n", villes[e.i].nom, villes[e.j].nom, e.d);
            fusion(cc, n, cc[e.i], cc[e.j]);
            nselected += 1;
            if (nselected == n - 1) { // optim : c'est fini
                break;
            }
        }
    }

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

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

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