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

/* ============================================================ */
/*                     Début du code fourni                     */
/* ============================================================ */

/* Définition d'un type d'arbre.
 * On maintiendra l'invariant de structure suivant :
 * - le champ gauche est non NULL si et seulement le champ droite est non NULL
 * - les champs gauche et droite sont non NULL ssi le caractère c est \0
 * Autrement dit, un noeud de l'arbre est :
 * - soit un noeud interne, auquel cas où les champs gauche et droite sont non NULL et alors le caractère c est \0;
 * - soit une feuille, auquel cas le champs c n'est pas \0 et les champs gauche et droite sont NULL.
 * */
struct arbre_ {
    char            c;
    struct arbre_ * gauche;
    struct arbre_ * droite;
};
typedef struct arbre_* arbre;

/* Fonction d'affichage, en ligne, d'un tel arbre */
void affiche_arbre(arbre a) {
    if (a->droite != NULL) {
        printf("(");
        affiche_arbre(a->gauche);
        printf(",");
        affiche_arbre(a->droite);
        printf(")");
    } else {
        printf("%c", a->c);
    }
}

/* Définition d'une liste de couples : arbre * frequence.
 * On maintiendra l'invariant de structure suivant : la liste est triée par ordre croissant sur le champs freq */
struct list_ {
    int           freq;
    arbre         elem;
    struct list_* next;
};
typedef struct list_* list ;

/* Fonction d'affichage d'une liste de couples : arbre * frequence */
void affiche_liste(list l) {
    for (list cursor = l; cursor != NULL; cursor = cursor -> next) {
        printf("%d : ", cursor->freq);
        affiche_arbre(cursor->elem);
        printf("\n");
    }
}

/* Fonction de création de liste */
list alloc_maillon(arbre a, int freq) {
    list res = (list) malloc(sizeof(struct list_));
    res->freq = freq;
    res->elem = a;
    res->next = NULL;
    return res;
}

/* Fonction d'insertion triée d'un nouveau couple (arbre, fréquence) dans une liste triée.
 * Attention cette fonction prend en argument un pointeur vers la liste. */
void insere_trie(arbre a, int freq, list* pl) {
    list* pp    = pl;
    list cursor = *pl;
    while (cursor != NULL && cursor->freq < freq) {
        cursor = cursor->next;
        pp = &((*pp)->next);
    }
    list nv_maillon = alloc_maillon(a, freq);
    (*pp) = nv_maillon;
    nv_maillon->next = cursor;
}

/* ============================================================ */
/*                      Fin du code fourni                      */
/* ============================================================ */

/* Fonction de création d'un arbre réduit à une feuille, contenant le caractère c */
arbre feuille(char c) {
    /* À compléter, penser à enlever les deux lignes ci-dessous */
    printf("Non implémentée\n");
    assert(false);
}

/* Fonction de création d'un noeud interne, dont le fils gauche est g, le fils
 * droit est d */
arbre noeud(arbre g, arbre d) {
    /* À compléter, penser à enlever les deux lignes ci-dessous */
    printf("Non implémentée\n");
    assert(false);
}

/* Fonction permettant la suppression du couple (arbre, fréquence) de fréquence
 * minimale dans la liste pointée par pl */
void supprime_min(list* pl) {
    /* À compléter, penser à enlever les deux lignes ci-dessous */
    printf("Non implémentée\n");
    assert(false);
}

/* Retourne une liste triée, par ordre croissant de fréquences, d'arbres réduits à une feuille qui sont les caractère du mot w */
list init_huffman(char* w) {
    /* À compléter, penser à enlever les deux lignes ci-dessous */
    printf("Non implémentée\n");
    assert(false);
}

/* Retourne l'arbre de Huffman pour des fréquences de lettres qui sont le nombre d'occurrences dans w */
arbre huffman(char* w) {
    /* À compléter, penser à enlever les deux lignes ci-dessous */
    printf("Non implémentée\n");
    assert(false);
}

int main() {
    arbre a = huffman("this is an example of a huffman tree");
    affiche_arbre(a);
}