huffman/inc/huftree.h

/**
 * @file
 * @brief Représentation mémoire des arbres binaires de Huffman.
 *
 * Définir une structure permettant de représenter en mémoire les
 * arbres binaires de Huffman et des fonctions permettant de manipuler
 * ces arbres.
 */

#ifndef __HUFFMAN_HUFTREE_H_INCLUDED__
#define __HUFFMAN_HUFTREE_H_INCLUDED__

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

#include "common.h"

//! \{
typedef struct WriteBuffer WriteBuffer;
typedef struct ReadBuffer ReadBuffer;
//! \}

/**
 * @brief Sommet d'un arbre binaire de Huffman.
 *
 * Sommet possédant éventuellement une valeur (caractère associé),
 * un effectif d'apparition (nombre d'occurences du caractère dans la source)
 * et un sommet enfant à gauche et/ou à droite.
 */
typedef struct HufVertex {
    /**
     * Caractère associé au sommet, ou -1 si aucun caractère
     * n'est associé (par exemple pour les sommets internes).
     */
    unsigned int value;

    /**
     * Effectif du caractère associé au sommet, ou -1 si aucun
     * caractère n'est associé.
     */
    bytecount count;

    /**
     * Sommet enfant à gauche, ou NULL si ce sommet n'a pas d'enfant
     * à gauche.
     */
    struct HufVertex* child_l;

    /**
     * Sommet enfant à droite, ou NULL si ce sommet n'a pas d'enfant
     * à droite.
     */
    struct HufVertex* child_r;
} HufVertex;

/**
 * @brief Arbre binaire de Huffman (pointeur vers un @c HufVertex)
 */
typedef HufVertex* HufTree;

/**
 * @brief Construire un arbre de Huffman.
 *
 * Lire les effectifs de caractères dans @p counts et en déduire
 * un arbre binaire de Huffman. Le résultat doit être libéré avec
 * la fonction @c freeTree.
 * @param counts Comptes des caractères.
 * @return Arbre construit.
 */
HufTree createTree(bytecount* counts);

/**
 * @brief Écrire un arbre dans le tampon d'écriture donné.
 *
 * Écrire une représentation binaire de l'arbre @p tree
 * dans le tampon @p buffer.
 * @param tree Arbre à représenter.
 * @param buffer Tampon cible.
 */
void writeTree(HufTree tree, WriteBuffer* buffer);

/**
 * @brief Lire un arbre depuis le tampon de lecture donné.
 *
 * Reconstruire un arbre de Huffman à partir du tampon de lecture
 * @p buffer. Le résultat doit être libéré avec la fonction @c freeTree.
 * @return L'arbre reconstruit.
 */
HufTree readTree(ReadBuffer* buffer);

/**
 * @brief Libérer la mémoire occupée par un arbre.
 * @param tree Arbre à libérer.
 */
void freeTree(HufTree tree);

/**
 * @brief Créer la clé de codage à partir d'un arbre de Huffman.
 *
 * Associer à chaque feuille de l'arbre une étiquette unique basée sur
 * sa position dans l'arbre. Aucune étiquette n'est ainsi préfixe d'une
 * autre. Le tableau renvoyé associe chaque caractère ASCII à son préfixe
 * ou à NULL s'il n'est pas présent dans l'arbre. Le résultat doit être
 * libéré avec @c freeTreeLabels.
 *
 * @param tree Arbre source de la clé de codage.
 * @return Clé générée.
 */
char** createTreeLabels(HufTree tree);

/**
 * @brief Libérer la mémoire occupée par une clé de codage.
 * @param labels Clé à libérer.
 */
void freeTreeLabels(char** labels);

#endif // __HUFFMAN_HUFTREE_H_INCLUDED__