class Lettre{
    public Lettre(char l, int f){ this.l=l; this.f=f; }
    public char getL(){ return l; }
    public int getF(){ return f; }
    public String toString(){
        return this.l+" => "+this.f;
    }
    public void add(int i){ this.f+=i; }
    private char l;
    private int f; // le nombre d'apparitions
}
class HuffArbre /* un arbre binaire */{
    public HuffArbre(Lettre l){this.feuille=l;}
    public HuffArbre(HuffArbre droite, HuffArbre gauche){
        this.droite=droite; this.gauche=gauche;
    }
    public String toString(){
        if (this.feuille!=null){
            return "Feuille("+this.feuille+")";
        }else{
            return "Branche("+this.droite+", "+this.gauche+")\n";
        }
    }
    public void add(HuffArbre a){
        if (this.feuille!=null){
            this.feuille.add(a.count());
        }else{
            System.out.println("tey null");
        }
    }
    public char getL(){
        if (this.feuille!=null){
            return this.feuille.getL();
        }else{
            return this.droite.getL();
        }
    }
    public int count(){
        if (this.feuille!=null){
            return this.feuille.getF();
        }else{
            return this.droite.count()+this.gauche.count();
        }
    }
    public String getSeq(char c){
        if (this.feuille != null){
            if (this.feuille.getL() == c){
                return "";
            }else{
                return "ERR";
            }
        }else{
            String outb, outa = this.droite.getSeq(c);
            if (outa.equals("ERR")){
                outb=this.gauche.getSeq(c);
                if (outb.equals("ERR")){
                    return "ERR";
                }else{
                    return outb.concat("1");
                }
            }else
                return outa.concat("0");
        }
    }
    private Lettre feuille;
    private HuffArbre droite;
    private HuffArbre gauche;
}
class HuffArbreList extends java.util.LinkedList<HuffArbre>{
    public HuffArbreList(){
    }
    public HuffArbreList(String str){
        for (int i=0;i<str.length();i++){
            this.insertSorted(new HuffArbre(new Lettre(str.charAt(i), 1)));
        }
    }
    public void insertSorted(HuffArbre e){
        int i=0, s=this.size();
        while (i<s && cmp(this.get(i), e)) i++;
        this.add(i, e);
    }
    public boolean cmp(HuffArbre a, HuffArbre b){
        if (this.sortLetter){
            return a.getL() <= b.getL();
        }else{
            return a.count() <= b.count();
        }
    }
    public HuffArbreList grouper(){
        HuffArbre e1, e2;
        HuffArbreList l=new HuffArbreList();
        l.sortLetter=false;
        e1=this.removeFirst();
        int s=this.size();
        for (int i=0;i<s;i++){
            e2=this.removeFirst();
            if (e1.getL()==e2.getL()){
                e1.add(e2);
            }else{
                l.insertSorted(e1);
                e1=e2;
            }
        }
        l.add(e1);
        return l;
    }
    public void faireArbre(){
      if (this.size()==1) return;
      HuffArbre e1, e2;
      e1=this.removeFirst();
      e2=this.removeFirst();
      this.insertSorted(new HuffArbre(e1, e2));
      faireArbre();
    }
    public boolean sortLetter=true;
}
public class Main {
    public static void main(String[] args) {
        HuffArbreList liste=new HuffArbreList("test ok arbre test");
        liste=liste.grouper();
        liste.faireArbre();
        HuffArbre arbre=liste.removeFirst();
        System.out.println(arbre);
        System.out.println(arbre.getSeq('t'));
    }
}

let ( @@ ) f g x = f (g x);;
type lettre = {l:char; f:int;};;
type huff = Feuille of lettre | Branche of huff * huff;;
type huffL = huff list;;
type binarySeg = bool list;;
let rec count = function
| Feuille l -> l.f
| Branche (h1, h2) -> count h1 + count h2;;
let rec getFC = function
| Feuille l -> l.l
| Branche (h1, h2) -> getFC h1;;
let cmp f h1 h2 =((f h1) < (f h2));;
let insert cmp huff huffL=
let rec insert acc = function
| [] -> List.rev (huff::acc)
| hd::lt -> if cmp huff hd
    then List.rev_append acc (huff::hd::lt)
    else insert (hd::acc) lt
in insert [] huffL;;
let string2huffL cmp str =
    let strget=String.get str
    in let rec f acc = function n -> if n = -1 then acc
    else f (insert cmp (Feuille({l=strget n;f=1})) acc) (n-1)
    in f [] ((String.length str)-1);;
let grouper fa fb = match (fa, fb) with
    | (Feuille la, Feuille lb) ->
        (if la.l = lb.l then Feuille ({l=la.l;f=la.f + lb.f})
        else Branche (fa, fb))
    | _ -> Branche (fa, fb);;
let grouperL cmp grouper2 liste=
let rec f acc = function
| [] -> acc
| hd1::hd2::lt ->
    if (getFC hd1) = (getFC hd2)
    then f acc ((grouper2 hd1 hd2)::lt)
    else f (insert cmp hd1 acc) (hd2::lt)
| hd1::[] -> insert cmp hd1 acc
in f [] liste;;
let rec grouperA cmp = function
| hd::[] -> hd
| hd1::hd2::lt -> grouperA cmp ( insert cmp (grouper hd1 hd2) lt)
| _ -> failwith "?? grouperA ??";;
let getArbreForString chaine =
    grouperA (cmp count) (grouperL (cmp count) grouper
    (string2huffL (cmp (int_of_char @@ getFC)) chaine)) ;;
let getBinarySeq arbre c =
    let rec f = function
    | Branche (ba, bb) ->
        let (boola, seq)= f ba in
        if boola
            then (boola, true::seq)
            else
                let (boolb, seq)= f bb
                in (boolb, false::seq)
    | Feuille (fa) -> (fa.l=c, [])
    in f arbre;;

#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;
}