import java.util.*;

public class Huffman
{
	public final static int SIZE = 256;

	protected Entry [ ] leafEntries;

    	protected PurePriorityQueue<Entry> pq;


	/**
	 *  Initializes this Huffman object.
	 *
	 */	
    	public Huffman()
	{
        	Entry entry;

        	leafEntries = new Entry [SIZE];
        	for (int i = 0; i < SIZE; i++)
        	{
	            	leafEntries [i] = new Entry();
        	    	entry = leafEntries [i];
            		entry.freq = 0;
            		entry.left = null;
            		entry.right = null;
            		entry.parent = null;
        	} // initializing leafEntries

        	pq = new Heap<Entry>();
    	} // default constructor


	/**
	 *  Updates the frequencies of the characters in line.
	 *
	 */
	public void updateFrequencies (String line)
	{
        	Entry entry;

        	for (int j = 0; j < line.length(); j++)
        	{
            		entry = leafEntries [(int)(line.charAt (j))];
            		entry.freq++;
        	} // for

        	// Account for the end-of-line marker:
        	entry = leafEntries [(int)'\r'];
        	entry.freq++;
    	} // method updateFrequencies


	/**
	 *  Creates the priority queue from the frequencies.
	 *
	 */
    	public void createPQ()
	{
        	Entry entry;

        	for (int i = 0; i < SIZE; i++)
        	{
            		entry = leafEntries [i];
            		if (entry.freq > 0)
                		pq.add (entry);
        	} // for
    	} // createPQ


	/**
	 *  Creates the Huffman tree.
	 *
	 */	
    	public void createHuffmanTree()
	{
        	Entry left,
                      right,
                      sum;

        	while (pq.size() > 1)
        	{
            		left = pq.removeMin();
            		left.code = "0";

            		right = pq.removeMin();
            		right.code = "1";

            		sum = new Entry();
            		sum.parent = null;
            		sum.freq = left.freq  + right.freq;
            		sum.left = left;
            		sum.right = right;
            		left.parent = sum;
            		right.parent = sum;

            		pq.add (sum);
        	} // while
	} // method createHuffmanTree


	/**
	 *  Calculates the Huffman codes.
	 *
	 */
	public void calculateHuffmanCodes()
	{
        	String code;

        	Entry entry;

        	for (int i = 0; i < SIZE; i++)
        	{
            		code = "";
            		entry = leafEntries [i];
            		if (entry.freq > 0)
            		{
                		while (entry.parent != null)
                 		{
                      			code = entry.code + code;  // current bit prepended to
                      			entry = entry.parent;      // code as we go up the tree
                 		} // while                		
				leafEntries [i].code = code;
            		} // if
        	} // for
	} // calculateHuffmanCodes


	/** 
    	 *  Returns, as a String object, the characters and their Huffman codes.
	 *
	 *  @return the characters and their Huffman codes.
	 *
	 */	
    	public String getCodes()
	{
        	Entry entry;

        	String codes = new String();

        	for (int i = 0; i < SIZE; i++)
        	{
            		entry = leafEntries [i];
            		if (entry.freq > 0)
                		codes += (char)i + " " + entry.code + "\n";
        	} // for
        	return codes;
	} // method getCodes


	/** 
	 *  Returns a String representation of the encoding of a specified line.
	 *
	 *  @param line - the line whose encoding is returned.
	 *
	 *  @return a String representation of the encoding of line.
	 *
	 */
    	public String getEncodedLine (String line)
	{
        	Entry entry;

        	String encodedLine = new String();

        	for (int j = 0; j < line.length(); j++)
        	{
            		entry = leafEntries [(int)(line.charAt (j))];
            		encodedLine += entry.code;
        	} // for
        	entry = leafEntries [(int)'\r'];
        	encodedLine += entry.code;
        	return encodedLine;
	} // method getEncodedLine


} // class Huffman


class Entry implements Comparable<Entry> 
{
    	int freq;

    	String code;

    	char id;

    	Entry left,
              right,
              parent;

    	public int compareTo (Entry entry) 
    	{
        	return freq - entry.freq;
    	} // compareTo

} // class Entry