package nyc.angus.huffman.sort;

import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

public class HuffmanEncodingFactory {

	public static Map<Character, String> create(final PriorityQueue<CharEntry> queue) {

		while (queue.size() > 1) {
			final CharEntry a = queue.poll();
			final CharEntry b = queue.poll();

			final CharEntry parent = new CharEntry(a, b, a.getFrequency() + b.getFrequency());
			queue.add(parent);
		}

		assert queue.size() == 1;

		final Map<Character, String> codes = new HashMap<>();

		traverse("", codes, queue.poll());

		return codes;
	}

	private static void traverse(final String string, final Map<Character, String> codes, final CharEntry entry) {
		if (entry.getChar() != null) {
			codes.put(entry.getChar(), string);
		} else {
			traverse(string + "0", codes, entry.getLeftChild());
			traverse(string + "1", codes, entry.getRightChild());
		}
	}

}

package nyc.angus.huffman.sort;

import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

public class HuffmanEncodingFactory {

	/**
	 * Return a map of characters to the code that should be used for the character.
	 * 
	 * @param queue
	 *        Characters ordered by the frequency with which they occur.
	 * @return Mapping from character to its encoding.
	 */
	public static Map<Character, String> create(final PriorityQueue<CharEntry> queue) {

		final CharEntry root = createTree(queue);

		final Map<Character, String> codes = new HashMap<>();

		traverseTreeAndStoreHuffmanCodes("", codes, root);

		return codes;
	}

	/**
	 * Create encoding tree that can be used to generate huffman codes.
	 */
	private static CharEntry createTree(final PriorityQueue<CharEntry> queue) {
		while (queue.size() > 1) {
			final CharEntry a = queue.poll();
			final CharEntry b = queue.poll();

			final CharEntry parent = new CharEntry(a, b, a.getFrequency() + b.getFrequency());
			queue.add(parent);
		}

		assert queue.size() == 1;

		return queue.poll();
	}

	/**
	 * Recursively traverse the encoding tree and update <tt>codes</tt> with the character and its encoding (based on
	 * this traversal).
	 */
	private static void traverseTreeAndStoreHuffmanCodes(final String string, final Map<Character, String> codes, final CharEntry entry) {
		if (entry.getChar() != null) {
			codes.put(entry.getChar(), string);
		} else {
			traverseTreeAndStoreHuffmanCodes(string + "0", codes, entry.getLeftChild());
			traverseTreeAndStoreHuffmanCodes(string + "1", codes, entry.getRightChild());
		}
	}

}

refactor (encoding): extract to new method