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

//------------------------------------------
// MACROS, CONSTANTES, VARIABLES GLOBALES
//------------------------------------------

// Taille de l'alphabet (lettres de A à Z)
#define NBSYMB 26

// Symbole hors alphabet pour peres
#define STAR '*'

// Compatibilité: UTF-8 = ASCII sur 127 positifs
typedef unsigned char uchar;

// Structure de quadruplet 
typedef struct tquad {
  uchar symb;             // Le symbole
  float freq;             // Sa fréquence
  struct tquad *fg, *fd;  // Fils gauche et droit
} tquad;

// Structure de noeud : référence d'un quadruplet
typedef tquad *tnoeud;    

// Structure de tas: les éléments du tableau sont
// des noeuds, i.e. des pointeurs vers des quadruplets.
// Dimensionné pour les 26 lettres majuscules au max.
typedef struct {
  tnoeud T[NBSYMB + 1]; // Tableau 1-indicé
  size_t taille;        // Nombre d'éléments dans le tas
} ttas;



//////////////////////////////////////////////////
// DEBUT DE LA PARTIE A COMPLETER
//////////////////////////////////////////////////

//------------------------------------
// FRÉQUENCES DES SYMBOLES DU TEXTE
//------------------------------------

//***************************************************
// Q1. Crée et renvoie la table des fréquences
// des NBSYMB considérés.
// < 10 lignes de code.
//***************************************************
float *CalculerFrequences(const char *texte) {



}

//------------------------------------
// GESTION DES NŒUDS ET ARBRES
//------------------------------------

//***************************************************
// Q2. Crée une référence vers un noeud  
// < 10 lignes de code.
//***************************************************
tnoeud CreerNoeud(uchar symb, float freq, tnoeud fg, tnoeud fd) {




}

// Libère les noeuds de l'arbre constitué
// par leur chainage
void LibererArbre(tnoeud noeud) {
  if (noeud != NULL) {
    LibererArbre(noeud->fg);
    LibererArbre(noeud->fd);
    free(noeud);
  }
}

//------------------------------------
// GESTION DU TAS
//------------------------------------

// Échange deux éléments d'un tableau
void Echanger(tnoeud T[], size_t i, size_t j) {
  tnoeud temp = T[i];
  T[i] = T[j];
  T[j] = temp;
}

//***************************************************
// Q3. Maintient la propriété de tas min depuis la
// position ipere jusqu'à ifin
// ≈ 15 lignes de code.
//***************************************************
void Tamiser(tnoeud T[], size_t ipere, size_t ifin) {



}

//***********************************************
// Q4. Crée un tas: valuation = fréquences F
// ≈ 10 lignes de code.
//***********************************************
void Entasser(ttas *tas, const float F[NBSYMB]) {




}

//************************************************
// Q5. Rétablit la propriété APO: remonte le dernier
// élément sur la branche qui le relie à la racine
// < 10 lignes de code.
//************************************************
void Remonter(ttas tas, size_t i) {




}

//**************************************************
// Q6. Rajoute un élément à la fin du tas puis rétablit
// la propriété APO
// < 10 lignes de code.
//**************************************************
void InsererDansTas(ttas *tas, tnoeud nouveau) {


}

//------------------------------------
// CONSTRUCTION DE L'ARBRE DE HUFFMAN
//------------------------------------

//**************************************************
// Q7. Renvoie le premier terme du tas, le remplace
// par le dernier et tamise
// < 10 lignes de code.
//**************************************************
tnoeud ExtraireRacine(ttas *tas) {



}

//**************************************************
// Q8. Construit l'arbre de Huffman à partir du tas
// < 10 lignes de code.
//**************************************************
tnoeud ConstruireArbreHuffman(ttas *tas) {




}


//////////////////////////////////////////////////
// FIN DE LA PARTIE A COMPLETER
//////////////////////////////////////////////////

//------------------------------------
// GÉNÉRATION DES CODES DE HUFFMAN
//------------------------------------

void GenererCodes(tnoeud racine, char *code, size_t profondeur, char *codes[NBSYMB]) {
  if (racine == NULL) return;

  if (racine->fg == NULL && racine->fd == NULL) {
    code[profondeur] = '\0';
    size_t i = racine->symb - 'A';
    codes[i] = malloc((profondeur + 1) * sizeof(codes[i][0]));
    strcpy(codes[i], code);
    return;
  }

  code[profondeur] = '0';
  GenererCodes(racine->fg, code, profondeur + 1, codes);

  code[profondeur] = '1';
  GenererCodes(racine->fd, code, profondeur + 1, codes);
}

void CodeHuffman(tnoeud racine, char *codes[NBSYMB]) {
  char buffer[NBSYMB];
  for (int i = 0; i < NBSYMB; i++) codes[i] = NULL;
  GenererCodes(racine, buffer, 0, codes);
}

//------------------------------------
// AFFICHAGE
//------------------------------------

void AfficherCodes(char *codes[NBSYMB]) {
  for (int i = 0; i < NBSYMB; i++) {
    if (codes[i] != NULL)
      printf("%c: %s\n", i + 'A', codes[i]);
  }
}

//------------------------------------
// PROGRAMME PRINCIPAL
//------------------------------------

int main(int argc, char *argv[]) {
  if (argc < 2) {
    fprintf(stderr, "Usage: %s TEXTEENMAJUSCULES\n", argv[0]);
    return 1;
  }

  // Le texte saisi sur la ligne de commande
  const char *texte = argv[1];

  // Initialisation du tableau des fréquences
  float *F = CalculerFrequences(texte);

  // Initialisation du tas
  ttas tas = {.taille = 0};
  Entasser(&tas, F);

  // Construction de l'arbre de Huffman
  tnoeud arbre = ConstruireArbreHuffman(&tas);

  // Extraction des codes grâce à l'arbre 
  char *codes[NBSYMB] = {0};
  CodeHuffman(arbre, codes);

  // Affichage des codes
  AfficherCodes(codes);

  // Libération de la mémoire
  LibererArbre(arbre);
  for (int i = 0; i < NBSYMB; i++)
    free(codes[i]);

  return 0;
}