package text.java;
import java.util.Arrays;

public class HaffTree <T>{
    HaffNode root;
    public HaffTree(){
        root=null;
    }
    public HaffTree(HaffNode [] node){
        while(node.length>1){
            node=sort(node);
            HaffNode current=new HaffNode(node[0],node[1]);
            node[1]=current;
            node= Arrays.copyOfRange(node,1,node.length);
        }
        root=node[0];
    }
    public HaffNode[] sort(HaffNode[] node){
        for(int gap=node.length/2;gap>0;gap/=2){
            for(int i=gap;i<node.length;i++){
                int j=i;
                while (j-gap>=0&&node[j].weight<node[j-gap].weight){
                    swap(node,j,j-gap);
                    j-=gap;
                }
            }
        }
        return node;
    }
    public void swap(HaffNode [] node,int a,int b){
        HaffNode temp;
        temp=node[a];
        node[a]=node[b];
        node[b]=temp;
    }
    public String decode(String s){//解码
        String str="";
        int i=0;
        HaffNode current=root;
        while(i<s.length()) {
            while (current.leftChild != null) {
                if (s.charAt(i)=='0') current = current.leftChild;
                else current = current.rightChild;
                i++;
            }
            str+=current.data;
            current=root;
        }
        return str;
    }
}