prog-c/tp-huffman/hufftree.c

#include "hufftree.h"
#include "binheap.h"
#include "error.h"
#include <stdlib.h>

/************************************/
/* Primitives des arbres de Huffman */
/************************************/

/* Création d'une feuille */
huffnode *create_huffleaf(int byte, int freq) {
  huffnode *h = malloc(sizeof(huffnode));
  h -> freq = freq;
  h -> byte = byte;
  h -> leftchild = NULL;
  h -> rightchild = NULL;
  return h;
}

/* Fusion de deux arbres avec un nouveau noeud racine */
huffnode *merge_hufftree(huffnode *pl, huffnode *pr) {
    huffnode *h = create_huffleaf(0, pl->freq + pr->freq);
    h->leftchild = pl;
    h->rightchild = pr;
    return h;
}

/* Teste si un noeud est une feuille */
bool isleaf_huffnode(huffnode *p) {
    return p->leftchild == NULL && p->rightchild == NULL;
}

/* Retourne la valeur de l'octet correspondant à un noeud */
int getbyte_huffnode(huffnode *p) {
  if (isleaf_huffnode(p)) {
      ERROR("getbyte_huffnode: noeud feuille attendu\n");
      exit(1);
  }
  return p->byte;
}

/* Retournent les fils d'un noeud */

huffnode *getleft_huffnode(huffnode *p) {
  if (isleaf_huffnode(p)) {
      ERROR("getleft_huffnode: noeud interne attendu\n");
      exit(1);
  }
  return p->leftchild;
}
huffnode *getright_huffnode(huffnode *p) {
    if (isleaf_huffnode(p)) {
          ERROR("getright_huffnode: noeud interne attendu\n");
          exit(1);
      }
  return p->rightchild;
}

/* Libération d'un arbre */

void free_hufftree(huffnode *p) {
  if (p == NULL) return;
  free_hufftree(p -> leftchild);
  free_hufftree(p -> rightchild);
  free(p);
}

/**********************************************/
/* Fonctions manipulant les arbres de Huffman */
/**********************************************/

/* Comparaison de deux arbres */
bool compare_hufftree(void *p1, void *p2) {
    huffnode *v1 = (huffnode*)p1;
    huffnode *v2 = (huffnode*)p2;
    if (v1 == NULL || v2 == NULL) {
        ERROR("compare_hufftree: NULL pointeur\n");
        exit(1);
    }
    return v1->freq < v2->freq;
}

/* Création de l'arbre de Huffman à partir du fichier à compresser */
huffnode *datafile_to_hufftree(FILE *input) {
  /* Phase 1: création du tableau de fréquences */

    int *tab = malloc(256 * sizeof(int));
    for (int i = 0; i < 256; i++) {
        tab[i] = 0;
    }
    int c;
    while ((c = fgetc(input)) != EOF) {
        tab[c]++;
    }

    /* Phase 2: intialisation de la file de priorité à partir du tableau de
    * fréquences */

    binheap *heap = create_binheap(compare_hufftree);
    for (int i = 0; i < 256; i++) {
        if (tab[i] > 0) {
            huffnode *h = create_huffleaf(i, tab[i]);
            push_binheap(heap, h);
        }
    }
    free(tab);

    /* Phase 3: création de l'arbre de Huffman à partir de la file de priorités */

    while (getsize_binheap(heap) > 1) {
        huffnode *pl = popmin_binheap(heap);
        huffnode *pr = popmin_binheap(heap);
        huffnode *h = merge_hufftree(pl, pr);
        push_binheap(heap, h);
    }
    huffnode *root = popmin_binheap(heap);
    free(heap);
    return root;
}

/* Écriture de l'arbre de Huffman dans le futur fichier compressé */
void save_hufftree(huffnode *p, FILE *f) {
    if (isleaf_huffnode(p)) {
        fputc('L', f);
        fputc(p->byte, f);
    } else {
        fputc('N', f);
        save_hufftree(p->leftchild, f);
        save_hufftree(p->rightchild, f);
    }
}

/* Lecture de l'arbre de Huffman dans le fichier compressé */
huffnode *read_hufftree(FILE *f) {
    int c = fgetc(f);
    if (c == EOF) {
        ERROR("read_hufftree: fin de fichier inattendue\n");
        exit(1);
    }
    if (c == 'L') {
        int byte = fgetc(f);
        return create_huffleaf(byte, 0);
    } else if (c == 'N') {
        huffnode *pl = read_hufftree(f);
        huffnode *pr = read_hufftree(f);
        return merge_hufftree(pl, pr);
    } else {
        ERROR("read_hufftree: caractère inattendu\n");
        exit(1);
    }
}