// Joel Yang
// CSE 143 DD with Xunmei Liu
// HuffmanTree implements the Huffman algorithm:
// https://en.wikipedia.org/wiki/Huffman_coding
// It can build trees in two different ways, one being
// through a frequency array and one being through
// a preordered, standard file. It can also do the opposite;
// writing trees to a standard file. It can also decode
// files given an encoded file.

package Homework8;

import java.io.*;
import java.util.*;

// creates a "Huffman tree", using the algorithm as described above.
public class HuffmanTree {
    public HuffmanNode overallRoot;
    private Queue<HuffmanNode> freqQueue;

    // constructs a "Huffman tree" given an array of frequencies
    public HuffmanTree(int[] count) {
        freqQueue = new PriorityQueue<>();
        fillQueue(count);
        buildTree();
        overallRoot = freqQueue.remove();
    }

    // fills queue with "Huffman nodes" given our frequencies for each character.
    // includes pseudo end-of-file character, whose 'character' is 1 + the highest
    // character passed through the frequency array, and whose 'frequency' is, logically,
    // 1.
    private void fillQueue(int[] count) {
        for (int i = 0; i < count.length; i++) {
            if (count[i] > 0) {
                freqQueue.add(new HuffmanNode(i, count[i]));
            }
        }
        freqQueue.add(new HuffmanNode(count.length, 1));
    }

    // recursively creates our final "Huffman tree"
    private void buildTree() {
        if (freqQueue.size() > 1) {
            HuffmanNode front1 = freqQueue.remove();
            HuffmanNode front2 = freqQueue.remove();
            HuffmanNode root = new HuffmanNode(front1.freq + front2.freq);
            root.left = front1;
            root.right = front2;
            freqQueue.add(root);
            buildTree();
        }
    }

    // writes tree to an output file / stream in standard (preorder) format
    public void write(PrintStream output) {
        write(output, overallRoot, "");
    }

    // loosely based on hw7
    private void write(PrintStream output, HuffmanNode root, String freqString) {
        if (isCharacter(root)) {
            output.println(root.character);
            output.println(freqString);
        } else {
            write(output, root.left, freqString + "0");
            write(output, root.right, freqString + "1");
        }
    }

    // alternate constructor: reconstructs a "Huffman tree" from a file,
    // assuming input is stored in standard (preorder) format
    public HuffmanTree(Scanner input) {
        overallRoot = loadRead(input);
    }

    // parses through input
    private HuffmanNode loadRead(Scanner input) {
        HuffmanNode current = new HuffmanNode(-1);
        while (input.hasNextLine()) {
            int n = Integer.parseInt(input.nextLine());
            String code = input.nextLine();
            current = read(current, n, code);
        }
        return current;
    }

    // via loadRead; builds one pathway to one leaf from our original root
    private HuffmanNode read(HuffmanNode root, int n, String code) {
        if (root == null) {
            root = new HuffmanNode(-1);
        }
        if (code.isEmpty()) {
            root.character = n;
        } else {
            if (code.charAt(0) == '0') {
                root.left = read(root.left, n, code.substring(1));
            } else {
                root.right = read(root.right, n, code.substring(1));
            }
        }
        return root;
    }

    // reads individual bits from the input stream, writing them to the output.
    // stops upon encountering the pseudo end-of-file character mentioned below.
    // said character is not written to the output. assumes that the input is encoded
    // legally for this particular program.
    public void decode(BitInputStream input, PrintStream output, int eof) {
        HuffmanNode current = new HuffmanNode(-1);
        boolean reachedEndOfFile = false;
        while (!reachedEndOfFile) {
            current = overallRoot;
            int character = getCharacter(current, input);
            if (character == eof) {
                reachedEndOfFile = true;
            } else {
                output.write(character);
            }
        }
    }

    // recursively grabs individual characters using our tree and a bit stream
    private int getCharacter(HuffmanNode root, BitInputStream input) {
        if (isCharacter(root)) {
            return root.character;
        } else {
            if (input.readBit() == 0) {
                return getCharacter(root.left, input);
            } else {
                return getCharacter(root.right, input);
            }
        }
    }

    // returns true if node has a valid character, aka is a leaf
    private boolean isCharacter(HuffmanNode root) {
        return root.left == null && root.right == null;
    }
}