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

struct noeud_s {
    bool interne;               /* le noeud est-il interne */
    char c;                     /* si l'arbre est une feuille */
    struct noeud_s* gauche;     /* le fils gauche */
    struct noeud_s* droite;     /* le fils droite */
};
typedef struct noeud_s *arbre;

arbre cree_feuille(char c);
arbre cree_noeud(arbre gauche, arbre droite);

/********************************
 *    Fonctions d'affichage     *
 ********************************/

void affiche_arbre_aux(arbre da, char *prefixe, int l, int lrn) {
  /* Fonction auxiliaire récursive pour l'affichage d'un arbre.
     Affiche le sous-arbre da, qui est :
     + la racine si lrn == 2
     + un fils gauche si lrn == 0
     + un fils droit si lrn == 1.
     Chaque ligne d'affichage est précédée du préfixe prefixe de longueur
     l.
  */
  if (!da->interne) {
    if (lrn == 0) { /* fils gauche */
      printf("%s├─ : %c\n", prefixe, da->c);
    } else if (lrn == 1) { /* fils droit */
      printf("%s└─ : %c\n", prefixe, da->c);
    } else { /* racine */
      printf("%s%c\n", prefixe, da->c);
    }
  } else {
    if (lrn == 0) { /* fils gauche */
      printf("%s├─┐\n", prefixe);
    } else if (lrn == 1) { /* fils droit */
      printf("%s└─┐\n", prefixe);
    } else { /* racine */
      printf("┐%s\n", prefixe);
    }
    int new_l = l;  /* racine */
    if (lrn == 0) { /* fils gauche */
      strcat(prefixe, "│ ");
      new_l = l + 4;
    } else if (lrn == 1) { /* fils droit */
      strcat(prefixe, "  ");
      new_l = l + 2;
    }
    affiche_arbre_aux(da->gauche, prefixe, new_l, 0);
    affiche_arbre_aux(da->droite, prefixe, new_l, 1);
    prefixe[l] = '\0';
  }
}

void affiche_arbre(arbre da) {
  /* Affiche l'arbre da */
  char prefixe[101];
  prefixe[0] = '\0';
  affiche_arbre_aux(da, prefixe, 0, 2);
}

arbre cree_feuille(char c) {
  /* Crée une feuille d'un arbre de Huffman, contenant le caractère c */
  arbre res = (arbre)malloc(sizeof(struct noeud_s));
  res->interne = false;
  res->c = c;
  return res;
}

arbre cree_noeud(arbre gauche, arbre droite) {
  /* Crée un noeud interne d'un arbre de Huffman, le sous-arbre gauche
     est gauche et le sous-arbre droite est droite. */
  arbre res = (arbre)malloc(sizeof(struct noeud_s));
  res->interne = 1;
  res->gauche = gauche;
  res->droite = droite;
  return res;
}

arbre exemple_1() {
    return cree_noeud(cree_noeud(cree_feuille('a'), cree_feuille('b')),
                      cree_noeud(cree_noeud(cree_feuille('c'), cree_feuille('d')),
                                 cree_noeud(cree_feuille('e'), cree_feuille('f'))));
}

int main() {
    affiche_arbre(exemple_1());
    return 0;
}

/* Q1. Définir un type list_arbre permettant de stocker une liste de
   couples (arbres, entiers) */

/* Q2. Définir une fonction huffman, prenant en argument une chaîne de
   caractères s et retournant l'arbre de Huffman associé à s. */

/* Q3. Définir un type list_bool permettant de stocker une liste de
   booléens. */

/* Q4. Définir une fonction table_encodage, prenant en argument un
   arbre de Huffman et lui associant sa table d'encodage, à savoir un
   tableau indicé par les 256 caractères et contenant dans sa case
   d'indice i la liste des booléens correspondant à l'encodage du
   caractère i. */

/* Q4. Définir une fonction encode prenant en paramètres un arbre de
   Huffman et une chaîne de caractères et retournant une liste de
   booléens qui est l'encodage de la chaîne de caractères au moyen de
   l'arbre de Huffman. Définir une fonction decode prenant en
   paramètres un arbre de Huffman et une liste de booléens et
   retournant une chaîne de caractères qui est le décodage de la liste
   de booléens au moyen de l'arbre de Huffman.  */