#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){
            printf("il y a %d villes\n", nv);
            // A COMPLETER
            // ....
        }
    }
    printf("Erreur de lecture 1\n");
    exit(0); // erreur de lecture
    return NULL;
}


/* 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){
    // A COMPLETER
    // ...........
    return NULL;
}


/* Code trouvé sur internet ...

void q....(int* tab, int taille) {
    // .........
    if (taille > 1){
        int pivot = tab[0];
        // .........
        tab[0] = tab[taille-1];
        tab[taille-1] = pivot;
        // ..........
        int isep = 0; // .......
        for (int i = 0; i < taille - 1; i += 1){
            int elt = tab[i];
            if (elt < pivot) {
                tab[i] = tab[isep];
                tab[isep] = elt;
            } 
        }
        // ..........
        int tmp = tab[isep];
        tab[isep] = pivot;
        tab[taille-1] = tmp;
        // 
        q......(tab, isep);
        q......(.........);
    }
} */



/* 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");
    // A COMPLETER
    // ...........pour chaque arête e sélectionnée, on doit écrire dans 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);
    // ...... et entre chaque  écriture, on doit mettre une virgule ","
    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 */

    // A FAIRE

    /* affichage des villes */

    // A FAIRE

    /* création du tableau d'arêtes */
    
    // A FAIRE

    /* algorithme de Kruskal */

    /* tri du tableau d'arêtes */
    // A FAIRE

    // composantes connexes de chaque sommet
    // A FAIRE

    // algo glouton
    // A FAIRE

    /* export geojson */
    // A FAIRE
    return 0;
}