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());
		}
	}

}

@@ -151,92 +151,660 @@
 %7B%0A%0A%09
-public static Map%3CCharacter, String%3E create(final PriorityQueue%3CCharEntry%3E queue) %7B%0A
+/**%0A%09 * Return a map of characters to the code that should be used for the character.%0A%09 * %0A%09 * @param queue%0A%09 *        Characters ordered by the frequency with which they occur.%0A%09 * @return Mapping from character to its encoding.%0A%09 */%0A%09public static Map%3CCharacter, String%3E create(final PriorityQueue%3CCharEntry%3E queue) %7B%0A%0A%09%09final CharEntry root = createTree(queue);%0A%0A%09%09final Map%3CCharacter, String%3E codes = new HashMap%3C%3E();%0A%0A%09%09traverseTreeAndStoreHuffmanCodes(%22%22, codes, root);%0A%0A%09%09return codes;%0A%09%7D%0A%0A%09/**%0A%09 * Create encoding tree that can be used to generate huffman codes.%0A%09 */%0A%09private static CharEntry createTree(final PriorityQueue%3CCharEntry%3E queue) %7B
 %0A%09%09w
@@ -1052,120 +1052,178 @@
 %0A%0A%09%09
-final Map%3CCharacter, String%3E codes = new HashMap%3C%3E();%0A%0A%09%09traverse(%22%22, codes, queue.poll());%0A%0A%09%09return codes;%0A%09%7D%0A
+return queue.poll();%0A%09%7D%0A%0A%09/**%0A%09 * Recursively traverse the encoding tree and update %3Ctt%3Ecodes%3C/tt%3E with the character and its encoding (based on%0A%09 * this traversal).%0A%09 */
 %0A%09pr
@@ -1248,16 +1248,40 @@
 traverse
+TreeAndStoreHuffmanCodes
 (final S
@@ -1441,32 +1441,56 @@
 se %7B%0A%09%09%09traverse
+TreeAndStoreHuffmanCodes
 (string + %220%22, c
@@ -1529,16 +1529,40 @@
 traverse
+TreeAndStoreHuffmanCodes
 (string 

refactor (encoding): extract to new method