Practice Paper

HuffmanTree.java

package huffman;

import java.util.Map;

public class HuffmanTree {

    HuffmanTree left, right;
    Character symbol;

    public HuffmanTree() {
        left = null;
        right = null;
        symbol = null;
    }

    /**
     * Convenience method to check if a node has a left branch
     * 
     * @return true if the node has a left branch, false otherwise
     */
    private boolean hasLeft() {
        return left != null;
    }

    /**
     * Convenience method to check if a node has a right branch
     * 
     * @return true if the node has a right branch, false otherwise
     */
    private boolean hasRight() {
        return left != null;
    }

    /**
     * Convenience method to check if a node is a leaf node.
     * 
     * @return true if the node is a leaf node, false otherwise
     */
    private boolean isLeaf() {
        return right == null && left == null;
    }

    /**
     * Check if the tree is empty, i.e. contains no symbols.
     * 
     * @return true if the tree is empty, false otherwise
     */
    public boolean isEmpty() {
        return right == null && left == null && symbol == null;
    }

    /**
     * Clear the tree from its content. All symbols are removed from the tree and
     * the tree is then empty.
     */
    public void clear() {
        left = null;
        right = null;
        symbol = null;
    }

    /**
     * Build a Huffman tree from an encoding. The encoding is a Map of the form:
     * {'A':"000",'B':"001",'C':"010",'D':"011",'E':"10",'F':"11"}
     * 
     * @param encoding
     */
    public void setCoding(Map<Character, String> encoding) {
        this.clear();
        for (Character key : encoding.keySet()) {
            String code = encoding.get(key);
            System.out.println(code);
            insert(key, code);
        }
    }

    /**
     * Convenience method to insert a symbol into the Huffman tree given a path
     * (e.g. "0010").
     * 
     * @param key
     *            the symbol to be inserted into the tree
     * @param code
     *            the path to insert the symbol into the tree.
     */           
    private void insert(Character key, String code) {
        if (isEmpty()) {
            if (!code.isEmpty()) {
                if (code.charAt(0) == '0') { // insert left
                    left = new HuffmanTree();
                    left.insert(key, code.substring(1));
                } else if (code.charAt(0) == '1') { // insert right
                    right = new HuffmanTree();
                    right.insert(key, code.substring(1));
                } else { // not binary
                    throw new IllegalArgumentException();
                }
            } else { // arrived at a end of coding word and at a leaf
                symbol = key;
            }
        } else {
            if (code.isEmpty()) { // end of coding word but not at a leaf so error
                throw new IllegalArgumentException();
            } else if (code.charAt(0) == '0') { // insert left
                if (hasLeft()) { // branch has been created previously
                    left.insert(key, code.substring(1));
                } else { // no branch exists yet
                    left = new HuffmanTree();
                    left.insert(key, code.substring(1));
                }
            } else if (code.charAt(0) == '1') { // insert right
                if (hasRight()) { // branch has been created previously
                    right.insert(key, code.substring(1));
                } else { // no branch exists yet
                    right = new HuffmanTree();
                    right.insert(key, code.substring(1));
                }
            } else { // not binary
                throw new IllegalArgumentException();
            }
        }

        ////////////////////////////////////////////////////////////
        ///////////////// WRITE YOUR SOLUTION HERE /////////////////
        ////////////////////////////////////////////////////////////

    }
}