huffman/src/huftree.c

#include "common.h"
#include "huftree.h"
#include "buffer.h"

#include <assert.h>
#include <stdio.h>
#include <string.h>

/**
 * Trouver les deux sommets de valeur la plus faible parmi
 * tous les sommets pointés par le tableau. Place l'indice
 * du minimum dans `min` et de l'avant-dernier dans `sec`.
 */
static void _findMinimalVertices(HufVertex**, size_t, size_t* min, size_t* sec);

/**
 * Créer une nouvelle chaîne contenant la chaîne donnée
 * suffixée du caractère donné
 */
static char* _appendToString(char*, size_t, char);

/**
 * Remplit le tableau d'étiquettes données avec les étiquettes
 * des feuilles trouvées dans la sous-partie de l'arbre dont
 * le sommet donné est la racine. Toutes les étiquettes ajoutées
 * au tableau seront préfixées de la chaîne passée en paramètre
 */
static void _labelVertex(HufVertex, char**, char*, size_t);

HufTree createTree(bytecount* counts) {
    // Comptage du nombre de caractères différents dans le fichier :
    // il s'agit du nombre de feuilles dans l'arbre binaire
    size_t leaves_count = 0;

    for (size_t i = 0; i < NUM_CHARS; i++) {
        if (counts[i] > 0) {
            leaves_count++;
        }
    }

    // Allocation d'un tableau de `leaves_count` pointeurs vers sommets.
    // Initialement, ce tableau contient les feuilles du futur arbre.
    // Chaque feuille correspond à un caractère du corpus original
    HufVertex** remaining = malloc(leaves_count * sizeof(*remaining));
    size_t next_index = 0;

    for (int i = 0; i < NUM_CHARS; i++) {
        if (counts[i] > 0) {
            remaining[next_index] = malloc(sizeof(*remaining[next_index]));

            remaining[next_index]->value = i;
            remaining[next_index]->count = counts[i];
            remaining[next_index]->child_l = NULL;
            remaining[next_index]->child_r = NULL;

            next_index++;
        }
    }

    // Coeur de l'algorithme. On itère jusqu'à ce que le tableau `remaining`
    // ne contienne plus qu'un élément : la racine de l'arbre. À toute
    // itération, `remaining` pointe sur les sommets qui doivent encore
    // être traités (c-à-d les sommets sans parent), et `remaining_count`
    // est le nombre de sommets à traiter
    size_t remaining_count = leaves_count;

    while (remaining_count > 1) {
        // Recherche des deux sommets A et B de valeurs les plus faibles
        // parmi les sommets pointés par le tableau `remaining`
        size_t min_vert_index, sec_min_vert_index;

        _findMinimalVertices(
            remaining, remaining_count,
            &min_vert_index, &sec_min_vert_index
        );

        HufVertex* min_vert = remaining[min_vert_index];
        HufVertex* sec_min_vert = remaining[sec_min_vert_index];

        // Création d'un sommet parent P pour A et B
        HufVertex* parent = malloc(sizeof(*parent));

        parent->value = -1;
        parent->count = min_vert->count + sec_min_vert->count;
        parent->child_l = min_vert;
        parent->child_r = sec_min_vert;

        // Modification du tableau de pointeurs `remaining` pour
        // faire sortir A et B, faire entrer P, et réduire la longueur
        // de `remaining` de 1 sommet
        remaining[min_vert_index] = parent;
        remaining[sec_min_vert_index] = remaining[remaining_count - 1];
        remaining[remaining_count - 1] = NULL;

        remaining_count--;
    }

    HufTree tree;

    if (leaves_count == 0) {
        // Cas particulier : aucun caractère dans le fichier, dans ce
        // cas l'arbre est l'arbre vide
        tree = NULL;
    } else if (leaves_count == 1) {
        // Cas particulier : un seul type de caractère dans le fichier,
        // dans ce cas on crée un noeud artificiel et une racine. Sans
        // cette opération, on aurait un arbre avec un unique sommet et
        // donc une étiquette vide
        HufTree child_l = remaining[0];
        HufTree child_r = malloc(sizeof(*child_r));
        tree = malloc(sizeof(*tree));

        tree->value = -1;
        tree->count = -1;
        tree->child_l = child_l;
        tree->child_r = child_r;

        child_r->value = -1;
        child_r->count = -1;
        child_r->child_l = NULL;
        child_r->child_r = NULL;
    } else {
        // Sinon, la racine de l'arbre est le dernier sommet encore
        // dans le tableau `remaining`
        tree = remaining[0];
    }

    // Il est désormais possible de désallouer les pointeurs sur les
    // sommets de l'arbre, car la seule connaissance de la racine permet
    // d'accéder à tout l'arbre
    free(remaining);
    return tree;
}

void _findMinimalVertices(
    HufVertex** vertices, size_t size,
    size_t* min_index, size_t* sec_min_index
) {
    // Initialisation de telle sorte qu'initialement
    // on ait `count(min_index) < count(sec_min_index)`
    if (vertices[0]->count < vertices[1]->count) {
        *min_index = 0;
        *sec_min_index = 1;
    } else {
        *min_index = 1;
        *sec_min_index = 0;
    }

    for (size_t i = 2; i < size; i++) {
        double freq = vertices[i]->count;

        if (freq < vertices[*min_index]->count) {
            // Sommet de valeur inférieure au minimum trouvé, la valeur
            // devient le nouveau minimum, le minimum devient second minimum
            *sec_min_index = *min_index;
            *min_index = i;
        } else if (freq < vertices[*sec_min_index]->count) {
            // Sommet de valeur entre le minimum et le second minimum trouvé,
            // la valeur devient le nouveau second minimum
            *sec_min_index = i;
        }
    }
}

void writeTree(HufTree tree, WriteBuffer* buffer) {
    if (tree == NULL) {
        // Écriture de l'arbre vide dans le fichier : aucun
        // bit n'est ajouté
        return;
    }

    if (tree->child_l != NULL && tree->child_r != NULL) {
        // Bit "1" indiquant que le sommet a des enfants
        putBuffer(1, buffer);

        // Écriture du fils gauche et du fils droit
        writeTree(tree->child_l, buffer);
        writeTree(tree->child_r, buffer);
    } else {
        // Bit "0" indiquant que le sommet n'a pas d'enfants
        putBuffer(0, buffer);

        // Écriture de la valeur du sommet
        for (int i = 7; i >= 0; i--) {
            putBuffer((tree->value & (1 << i)) != 0, buffer);
        }
    }
}

HufTree readTree(ReadBuffer* buffer) {
    HufTree tree = malloc(sizeof(*tree));

    char bit = getBuffer(buffer);
    // FIXME: gérer la fin inattendue du fichier

    if (bit == 1) {
        // Sommet avec enfants
        tree->value = -1;
        tree->count = -1;
        tree->child_l = readTree(buffer);
        tree->child_r = readTree(buffer);
    } else if (bit == 0) {
        // Feuille de l'arbre
        int value = 0;

        for (int i = 7; i >= 0; i--) {
            value |= getBuffer(buffer) << i;
        }

        tree->value = value;
        tree->count = 0;
        tree->child_l = NULL;
        tree->child_r = NULL;
    }

    return tree;
}

void freeTree(HufTree tree) {
    if (tree != NULL && tree->child_l != NULL && tree->child_r != NULL) {
        freeTree(tree->child_l);
        freeTree(tree->child_r);
    }

    free(tree);
}

char** createTreeLabels(HufTree input) {
    char** labels = malloc(NUM_CHARS * sizeof(*labels));

    // Initialisation des étiquettes à NULL
    for (size_t i = 0; i < NUM_CHARS; i++) {
        labels[i] = NULL;
    }

    if (input != NULL) {
        _labelVertex(*input, labels, NULL, 0);
    }

    return labels;
}

void _labelVertex(HufVertex vertex, char** labels, char* label, size_t length) {
    if (vertex.child_l != NULL && vertex.child_r != NULL) {
        // Si le sommet a des enfants, poursuite de la récursion.
        // Étiquetage de la partie gauche avec '...0' et de la partie
        // droite avec '...1'
        _labelVertex(
            *vertex.child_l, labels,
            _appendToString(label, length, '0'),
            length + 1
        );

        _labelVertex(
            *vertex.child_r, labels,
            _appendToString(label, length, '1'),
            length + 1
        );

        // Libération de l'étiquette passée en paramètre,
        // qui a désormais été propagée dans les enfants
        free(label);
    } else {
        // Si le sommet est une feuille, étiquetage du caractère
        // associé avec l'étiquette passée en paramètre. Fin de la récursion
        if (vertex.value != -1) {
            labels[vertex.value] = label;
        }
    }
}

char* _appendToString(char* orig, size_t length, char append) {
    char* result = malloc((length + 2) * sizeof(*result));

    if (orig != NULL) {
        strcpy(result, orig);
    }

    result[length] = append;
    result[length + 1] = '\0';
    return result;
}

void freeTreeLabels(char** labels) {
    for (size_t i = 0; i < NUM_CHARS; i++) {
        free(labels[i]);
    }

    free(labels);
}