prog-c/tp-huffman/binheap.c

#include "binheap.h"

/*************************/
/* Fonctions auxiliaires */
/*************************/

/* La fonction de comparaison pour les tas d'entiers */
bool fcmp_int(void *x, void *y) {
    return *(int *)x < *(int *)y;
}

/* Fonctions de navigation dans un arbre représenté par un tableau */
int left_binheap(int i) {
    return i*2+1;
}
int right_binheap(int i) {
    return i*2+2;
}
int parent_binheap(int i) {
    return (i-1)/2;
}
bool isvalid_binheap(binheap *p, int i) {
    return i < p->size_heap;
}

/* Modification de la taille du tableau */
static void grow_binheap(binheap *p) {
    p->size_array *= 2;
    p->array = realloc(p->array, p->size_array * sizeof(void *));
    if (p->array == NULL) {
        ERROR("Erreur d'allocation mémoire\n");
        exit(EXIT_FAILURE);
    }
}

static void shrink_binheap(binheap *p) {
    p->size_array /= 2;
    p->array = realloc(p->array, p->size_array * sizeof(void *));
    if (p->array == NULL) {
        ERROR("Erreur d'allocation mémoire\n");
        exit(EXIT_FAILURE);
    }
}

/************************/
/* Fonctions primitives */
/************************/

/* Création d'un tas vide */
binheap *create_binheap(bool (*fc)(void *, void *)) {
    binheap *p = malloc(sizeof(binheap));
    if (p == NULL) {
        ERROR("Erreur d'allocation mémoire\n");
        exit(EXIT_FAILURE);
    }
    p->array = malloc(1 * sizeof(void *));
    if (p->array == NULL) {
        ERROR("Erreur d'allocation mémoire\n");
        exit(EXIT_FAILURE);
    }
    p->size_array = 1;
    p->size_heap = 0;
    p->fc = fc;
    return p;
}

/* Suppression */
void delete_binheap(binheap *p) {
  if (p != NULL) {
    if (p->array != NULL) {
      free(p->array);
    }
    free(p);
  }
}

/* Test du vide */
bool isempty_binheap(binheap *p) {
    return p == NULL || p->size_heap == 0;
}

/* Récupération de la taille */
int getsize_binheap(binheap *p) {
    return p->size_heap;
}

/* Insertion d'une valeur */
void push_binheap(binheap *p, void *val) {
    if (p->size_heap == p->size_array) {
        grow_binheap(p);
    }
    p->array[p->size_heap] = val;
    p->size_heap++;
    int i = p->size_heap - 1;
    while (i > 0 && p->fc(p->array[i], p->array[parent_binheap(i)])) {
        void *temp = p->array[i];
        p->array[i] = p->array[parent_binheap(i)];
        p->array[parent_binheap(i)] = temp;
        i = parent_binheap(i);
    }
}

/* Récupération du minimum sans le retirer */
void *peekmin_binheap(binheap *p) {
    if (isempty_binheap(p)) {
        return NULL;
    }
    return p->array[0];
}

/* Récupération du minimum en le retirant */
void *popmin_binheap(binheap *p) {
    if (isempty_binheap(p)) {
        return NULL;
    }
    void *min = p->array[0];
    p->size_heap--;
    p->array[0] = p->array[p->size_heap];
    int i = 0;
    while (isvalid_binheap(p, left_binheap(i))) {
        int j = left_binheap(i);
        if (isvalid_binheap(p, right_binheap(i)) && p->fc(p->array[right_binheap(i)], p->array[j])) {
            j = right_binheap(i);
        }
        if (p->fc(p->array[j], p->array[i])) {
            void *temp = p->array[i];
            p->array[i] = p->array[j];
            p->array[j] = temp;
            i = j;
        } else {
            break;
        }
    }
    if (p->size_heap < p->size_array / 4) {
        shrink_binheap(p);
    }
    return min;
}