package com.k13n.huffman;

import java.util.HashSet;
import java.util.NoSuchElementException;
import java.util.Set;

public class HuffmanCoder {
  private final Letter[] alphabet;
  private final Set<Node> leaves;
  private final Node root;

  public HuffmanCoder(Letter[] alphabet) {
    this.alphabet = alphabet;
    leaves = createLeavesFromAlphabet();
    root = buildHuffmanTable();
  }

  private Set<Node> createLeavesFromAlphabet() {
    Set<Node> leaves = new HashSet<>();
    for (Letter letter : alphabet)
      leaves.add(new Node(letter));
    return leaves;
  }

  private Node buildHuffmanTable() {
    Set<Node> nodes = new HashSet<Node>(leaves);
    while (nodes.size() != 1) {
      Node rightChild = extractMinFrequencyNode(nodes);
      Node leftChild = extractMinFrequencyNode(nodes);
      Node parent = Node.merge(leftChild, rightChild);
      nodes.add(parent);
    }
    Node root = nodes.iterator().next();
    return root;
  }

  private Node extractMinFrequencyNode(Set<Node> nodes) {
    double minFrequency = Double.MAX_VALUE;
    Node smallestNode = null;
    for (Node node : nodes) {
      if (node.frequency < minFrequency) {
        minFrequency = node.frequency;
        smallestNode = node;
      }
    }
    nodes.remove(smallestNode);
    return smallestNode;
  }

  public String encode(String text) {
    StringBuilder builder = new StringBuilder();
    for (int i = 0; i < text.length(); i++)
      encodeLetter(text.charAt(i), builder);
    return builder.toString();
  }

  private void encodeLetter(char letter, StringBuilder builder) {
    int offset = builder.length();
    Node leaf = getLeafOfLetter(letter);
    while (leaf != root) {
      char digit = mapSideToDigit(leaf.side);
      builder.insert(offset, digit);
      leaf = leaf.parent;
    }
  }

  public String decode(String text) {
    StringBuilder builder = new StringBuilder();
    Node currentNode = root;
    for (int i = 0; i < text.length(); i++) {
      currentNode = traverseTreeToNextDeeperNode(currentNode, text.charAt(i));
      if (currentNode.isLeave()) {
        char letter = currentNode.letter.getLetter();
        builder.append(letter);
        currentNode = root;
      }
    }
    if (currentNode != root)
      throw new IllegalArgumentException("text is malformed and can be "
          + "decoded only partially");
    return builder.toString();
  }

  private Node traverseTreeToNextDeeperNode(Node currentNode, char letter) {
    Side side = mapDigitToSide(letter);
    if (side == Side.LEFT)
      currentNode = currentNode.leftChild;
    else
      currentNode = currentNode.rightChild;
    return currentNode;
  }

  private char mapSideToDigit(Side side) {
    return side == Side.LEFT ? '0' : '1';
  }

  private Side mapDigitToSide(char digit) {
    return digit == '0' ? Side.LEFT : Side.RIGHT;
  }

  private Node getLeafOfLetter(char letter) {
    for (Node leaf : leaves)
      if (leaf.letter.getLetter() == letter)
        return leaf;
    throw new NoSuchElementException("letter '" + letter
        + "' does not belong to the alphabet");
  }

  private static enum Side {
    LEFT, RIGHT;
  }

  private static final class Node {
    final double frequency;
    final Letter letter;
    final Node leftChild, rightChild;
    Node parent;
    Side side;

    private Node(double frequency, Node leftChild, Node rightChild) {
      this.frequency = frequency;
      this.leftChild = leftChild;
      this.rightChild = rightChild;
      this.letter = null;
    }

    public Node(Letter letter) {
      this.letter = letter;
      this.leftChild = null;
      this.rightChild = null;
      this.frequency = letter.getFrequency();
    }

    public boolean isLeave() {
      return letter != null;
    }

    public static Node merge(Node leftChild, Node rightChild) {
      double frequency = leftChild.frequency + rightChild.frequency;
      Node parent = new Node(frequency, leftChild, rightChild);
      leftChild.parent = parent;
      leftChild.side = Side.LEFT;
      rightChild.parent = parent;
      rightChild.side = Side.RIGHT;
      return parent;
    }

  }

}

@@ -20,16 +20,45 @@
 ffman;%0A%0A
+import java.util.Comparator;%0A
 import j
@@ -116,16 +116,72 @@
 eption;%0A
+import java.util.PriorityQueue;%0Aimport java.util.Queue;%0A
 import j
@@ -700,50 +700,57 @@
     
-Set
+Queue
 %3CNode%3E 
-nodes
+heap
  = new
- HashSet%3CNode%3E(l
+MinFrequencyHeapFromL
 eaves
+(
 );%0A 
@@ -759,21 +759,20 @@
  while (
-nodes
+heap
 .size() 
@@ -807,92 +807,54 @@
 d = 
-extractMinFrequencyNode(nodes);%0A      Node leftChild = extractMinFrequencyNode(nodes
+heap.poll();%0A      Node leftChild = heap.poll(
 );%0A 
@@ -913,21 +913,20 @@
 ;%0A      
-nodes
+heap
 .add(par
@@ -957,29 +957,17 @@
 t = 
-nodes.iterator().next
+heap.poll
 ();%0A
@@ -1002,60 +1002,58 @@
 ate 
-Node extractMinFrequencyNode(Set%3CNode%3E nod
+Queue%3CNode%3E newMinFrequencyHeapFromLeav
 es
+(
 ) %7B%0A    
 doub
@@ -1052,104 +1052,112 @@
     
-double minFrequency = Double.MAX_VALUE;%0A    Node smallestNode = null;%0A    for (Node node : nodes
+int size = leaves.size();%0A    PriorityQueue%3CNode%3E heap = new PriorityQueue%3C%3E(size, new Comparator%3CNode%3E(
 ) %7B%0A
@@ -1166,65 +1166,108 @@
     
-if (node.frequency %3C minFrequency) %7B%0A        minF
+@Override public int compare(Node node1, Node node2) %7B%0A        return Double.compare(node1.f
 requency
  = n
@@ -1262,23 +1262,23 @@
 requency
- =
+,
  node
+2
 .frequen
@@ -1283,37 +1283,9 @@
 ency
-;%0A        smallestNode = node
+)
 ;%0A  
@@ -1299,38 +1299,33 @@
    %7D
+);
 %0A    
-nodes.remove(smallestNode
+heap.addAll(leaves
 );%0A 
@@ -1338,20 +1338,12 @@
 urn 
-smallestNode
+heap
 ;%0A  

Refactor the minimum frequency node detection