package edu.claflin.finder.algo.huffman;

import edu.claflin.finder.algo.huffman.HuffmanNode;
import edu.claflin.finder.logic.comp.HuffComparator;
import edu.claflin.finder.struct.PrioritySet;
import java.util.PriorityQueue;

public class HuffmanCode {
    /*
    Create priority set for storing the frequencies of the nodes traversed in a graph
    Create a tree that will split up the frequencies of each node into a position into said tree
    Create function that displays the huffman string of nodes traversed throughout a given graph
    */

    /*
    * This method will build the Huffman tree by extracting the minimum frequencies of the nodes
    * and adding them to make an internal node. It does this until the priority set size reaches 1.
    * We assume that a priority set is already created and filled in the class that deals with the
    * random walker. Returns the root node so that it can be used to display the Huffman tree later on.
     */
    public HuffmanNode generateTree(PrioritySet<HuffmanNode> minheap) {
        //Creates a root node.
        HuffmanNode root = null;

        while(minheap.size() > 1) {
            /*
            * Extracts the first minimum frequency. Assigns the value to a variable so that it can be
            * added to the second minimum frequency extracted.
             */
            HuffmanNode firstFreq = minheap.peek();
            minheap.poll();

            /*
            * Extracts the second minimum frequency. Assigns the value to a variable so that it can be
            * added to the first minimum frequency extracted.
             */
            HuffmanNode secondFreq = minheap.peek();
            minheap.poll();

            //Huffman node that will be assigned the result of the sum of the two minimum frequencies.
            HuffmanNode result = new HuffmanNode();

            //Assigns the sum of the minimum frequencies to the frequency of the result Huffman node.
            result.setFreq(firstFreq.getFreq() + secondFreq.getFreq());

            //Sets the name of the result node.
            result.setName("-");

            //Sets the left child of the Huffman node as the first minimum frequency that was extracted.
            result.setLeft(firstFreq);

            //Sets the right child of the Huffman node as the second minimum frequency that was extracted.
            result.setRight(secondFreq);

            //Assign the result node to the root node.
            root = result;

            //Add the root node into the priority set.
            minheap.add(root);
        }
        return root;
    }
    //Recursive method used to display the Huffman Tree.
    //The node parameter is used as the starting node for the traversal.
    //The code parameter will be used to generate the Huffman code based on the traversal.
    //The code parameter should be set to an empty string "", as it will return a modified string
    //at the end of the traversal.
    public void showTree(HuffmanNode node, String code) {
        if(node.getLeft() == null && node.getRight() == null && node.getName() instanceof String) {
            System.out.println(node.getName() + ":" + code);
            return;
        }
        //Recursive call to explore the left child of the node.
        //Every time a left path is taken, add 0 to the Huffman code string.
        showTree(node.getLeft(), code + "0");
        //Recursive call to explore the right child of the node.
        //Every time a right path is taken, add 1 to the Huffman code string.
        showTree(node.getRight(), code + "1");
    }

}
