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'));
    }
}