import java.util.Hashtable;
import java.util.Enumeration;

public class Huffman {
    private FreqTab ft;
    private HuffTree ht;
    private CodeTab ct;
    
    public Huffman (String sample) {
	ft = new FreqTab (sample);
	ht = HuffTree.buildHuffTree (ft);
	ct = new CodeTab (ht);
    }
    
    public String encode (String s) {
	// traverse the string and look up each character
	
	String result = "";
      	for (int i=0; i<s.length(); i++) {
	    result += ct.getEntry (s.charAt (i));
	}
	return result;
    }
    
    public String decode (String s) {
	String result = "";
	HuffTree tree = ht;
	
	// use the characters in the code to determine a path
	// through the tree
	for (int i=0; i<s.length(); i++) {
	    if (s.charAt(i) == '1') {
		tree = tree.left;
	    } else {
		tree = tree.right;
	    }
	    
	    // when you get to a leaf, append the corresponding
	    // character and start again at the root
	    if (tree.isLeaf ()) {
		result += tree.c;
		tree = ht;
	    }
	}
	// this method assumes the string is well-formed; it does
	// no error-checking (although it should)
	return result;
    }
}

class FreqTab {
    public Hashtable freqs;
    
    // constructor
    public FreqTab (String sample) {
	freqs = new Hashtable ();
	for (int i=0; i<sample.length(); i++) {
	    incrementFreq (sample.charAt (i));
	}
    }
    
    // incrementFreq: finds the element of the freq that corresponds
    // the the given character and increments it
    public void incrementFreq (char c) {
	Character key = new Character (c);
        Integer i = (Integer) freqs.get (key);
        if (i == null) {
            freqs.put (key, new Integer (1));
        } else {
            Integer j = new Integer (i.intValue() + 1);
            freqs.put (key, j);
        }
    }
    
    // getFreq: finds the element of the freq that corresponds
    // the the given character and returns it
    public int getFreq (char c) {
	Character key = new Character (c);
        Integer i = (Integer) freqs.get (key);
        if (i == null) {
            return 0;
        } else {
            return i.intValue();
        }
    }
    
    // print: prints the contents of the frequency table
    public void print () {
	Enumeration e = freqs.keys ();
        while (e.hasMoreElements ()) {
            Character key = (Character) e.nextElement ();
	    System.out.println (key + "\t" + getFreq(key.charValue()));
        }
    }
}

class HuffTree implements Comparable {
    int freq;
    char c;
    HuffTree left, right;
    
    public HuffTree (int freq, char c, HuffTree left, HuffTree right) {
	this.freq = freq;
	this.c = c;
	this.left = left;
	this.right = right;
    }
    
    public static HuffTree buildHuffTree (FreqTab ft) {
	Heap heap = new Heap ();
	
	// traverse the FreqTab and add singletons to the Heap
	Enumeration e = ft.freqs.keys ();
        while (e.hasMoreElements ()) {
            Character key = (Character) e.nextElement ();
	    char c = key.charValue();
	    int count = ft.getFreq (c);
	    heap.insert (new HuffTree (count, c, null, null));
        }
	
	// remove HuffTrees from the Heap and join them into subtrees
	while (!heap.isEmpty ()) {
	    HuffTree left = (HuffTree) heap.remove ();
	    HuffTree right = (HuffTree) heap.remove ();
	    int total = left.freq + right.freq;
	    HuffTree parent = new HuffTree (total, '.', left, right);
	    
	    // when there is only one big tree, exit the loop
	    if (heap.isEmpty ()) return parent;
	    heap.insert (parent);
	}
	return null;
    }
    
    public boolean isLeaf () {  return (left == null && right == null);  }
    
    public String toString () {  return "{" + c + "," + freq + "}";  }
    
    public int compareTo (Comparable other) {
	int a = this.freq;
	int b = ((HuffTree) other).freq;
	
	// the winner is the item with the lower frequency
	if (a>b) return -1;
	if (a<b) return 1;
	return 0;
    }
}

class CodeTab {
    Hashtable codes;
    
    public CodeTab (HuffTree ht) {
	codes = new Hashtable ();
	getCodesFromTree (ht, "");
    }
    
    private void getCodesFromTree (HuffTree tree, String path) {
	// path is the prefix of the code we've seen so far
	
	// when we get to a leaf node, add it to the code table
	if (tree == null) return;	
	if (tree.isLeaf ()) addEntry (tree.c, path);
	
	// have you checked the children?
	getCodesFromTree (tree.left, path + '1');
	getCodesFromTree (tree.right, path + '0');
    }
    
    public void addEntry (char c, String code) {
	Character key = new Character (c);
	codes.put (key, code);
    }
    
    public String getEntry (char c) {
	Character key = new Character (c);
	return (String) codes.get (key);
    }
    
    // print: prints the contents of the code table
    public void print () {
	Enumeration e = codes.keys ();
        while (e.hasMoreElements ()) {
            Character key = (Character) e.nextElement ();
	    System.out.println (key + "\t" + getEntry(key.charValue()));
        }
    }
}