#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct huffarbre {
    char l;
    int n;
    struct huffarbre *g, *d;
};
struct hal {
    struct huffarbre *ha;
    struct hal *next;
};
void sort_chaine(char * liste, int l){
    int i, j; char a;
    for (i=0;i<l;i++)
        for (j=i+1;j<l;j++)
            if (liste[i] > liste[j]){
                a=liste[i]; liste[i]=liste[j]; liste[j]=a;
            }
}
void ajouter(struct huffarbre * ha, struct hal * li, struct hal **pred){
    if (li->ha == NULL){
        li->ha = ha;
    }else{
        if (ha->n < li->ha->n){
            struct hal *li2 = malloc(sizeof(struct hal));
            li2->ha=ha;
            li2->next = li;
            if (*pred) (*pred)->next=li2;
            else *pred = li2;
        }else if (li->next == NULL){
            li->next = malloc(sizeof(struct hal));
            li->next->next=NULL;
            li->next->ha=ha;
        }else{
            ajouter(ha, li->next, &li);
        }
    }
}
void arbreliste ( char * chaine, int l, struct hal ** li){
    struct hal *first=NULL;
    int i, j;
    struct huffarbre *ha;
    for (i=0;i<l;i++){
        j=i;
        while (chaine[i]==chaine[j] && j<l) j++;
        ha = malloc(sizeof (struct huffarbre));
        ha->l=chaine[i]; ha->n=j-i; ha->g=NULL; ha->d=NULL;
        ajouter(ha, *li, &first);
        if (first) (*li)=first;
        i=j-1;
    }
}
void reduire_arbre(struct hal *first, struct huffarbre **arbre){
    struct hal *a, *b, *of;
    struct huffarbre *ha;
    of = first; // original first
    while (1){
        a=first;
        b=first->next; first=b->next;
        ha = malloc(sizeof (struct huffarbre));
        ha->l=0;
        ha->n=a->ha->n + b->ha->n;
        ha->g = a->ha; ha->d = b->ha;
        if (first==NULL) break;
        ajouter(ha, first, &first);
    }
    while (of){
        a=of;
        of=of->next;
        free(a);
    }
    *arbre = ha;
}
// affichage de la liste
void affliste(struct hal *li){
    struct hal *it_li;
    for (it_li = li; it_li!=NULL; it_li=it_li->next){
        printf("%c, %d\n", it_li->ha->l, it_li->ha->n);
    }
}
// affichage de l'arbre
void affarbre(struct huffarbre *ha, int t){
    int i;
    for (i=0;i<t-1;i++) printf("  |");
    if (t!=0) printf("---");
    if (ha->l){
        printf("%c, %d\n", ha->l, ha->n);
    }else{
        printf("\n");
        t++;
        affarbre(ha->d, t);
        affarbre(ha->g, t);
    }
}
// liberation de la memoire
void freearbre(struct huffarbre *ha){
    if (!ha->l){
        freearbre(ha->g);
        freearbre(ha->d);
    }
    free(ha);
}
// on recupere le code du caractere c, dans *chaine a partir du bit b, au format binaire. renvoie le nombre de bits utilises
int getbinarychainefor(struct huffarbre *ha, char c, char * chaine, int b){
    int l;
    if (ha->l){
        if (c==ha->l){
            return b;
        }else{
            return 0;
        }
    }else{
        if (b%8==0) *(chaine + b/8) = 0;
        if (l=getbinarychainefor(ha->g, c, chaine, b+1)){
            *(chaine + b/8)|=1 << (b%8);
            return l;
        }else if (l=getbinarychainefor(ha->d, c, chaine, b+1)){
            return l;
        }else{
            return 0;
        }
    }
}
// on recupere le code de la chaine *chaine, dans *out, au format binaire. renvoie le nombre de bits utilises
int getbinarychainefromString(struct huffarbre *ha, char * chaine, char *out){
    int l=strlen(chaine);
    int i, j=0;
    for (i=0;i<l;i++){
        j=getbinarychainefor(ha, chaine[i], out, j);
    }
    return j;
}
int main(){
    char chaine[]="test ok arbre test";
    int l=strlen(chaine);
    struct hal *li=malloc(sizeof(struct hal));
    struct huffarbre *ha;
    li->next=NULL; li->ha=NULL;
    sort_chaine(chaine, l);
    arbreliste(chaine, l, &li);
    //affliste(li);
    reduire_arbre(li, &ha);
    //affarbre(ha, 0);
// l'affichage des resultats du test
    l=getbinarychainefromString(ha, "ttb", chaine);
    printf("taille : %d\n", l);
    for (;l>0;l-=8){
        printf("%hhx", *(chaine+(l-1)/8));
    }
    printf("\n");
    freearbre(ha);
    return 0;
}