// Huffman.java

import java.io.File;
import java.io.FileReader;
import java.io.BufferedReader;
import java.io.PrintWriter;

class HuffmanTree {
    // probability various lower-case letters appear:
    static double probabilities [] = {
        0.08167, // a
        0.01492, // b
        0.02782, // c
        0.04253, // d
        0.12702, // e
        0.02228, // f
        0.02015, // g
        0.06094, // h
        0.06966, // i
        0.00153, // j
        0.00772, // k
        0.04025, // l
        0.02406, // m
        0.06749, // n
        0.07507, // o
        0.01929, // p
        0.00095, // q
        0.05987, // r
        0.06327, // s
        0.09056, // t
        0.02758, // u
        0.00978, // v
        0.0236,  // w
        0.0015,  // x
        0.01974, // y
        0.00074  // z
    };

    // return the probability of a given character
    private static double probability(char letter) {
        return probabilities[letter - 'a'];
    }

    // a node in our tree combines up 
    private class Node {
        char letter;
        double prob;
        Node left;
        Node right;
    }

    // store the code as an array of strings
    private String[] codes;

    // build the tree and everything here
    HuffmanTree() {
        // make a priority queue of nodes
        MinHeap<Node> nodes = new MinHeap<Node>(26);

        // make a Node for each of the letters, and put them in a priority queue
        for (char c = 'a'; c <= 'z'; c++) {
            Node node = new Node();
            node.letter = c;
            node.prob = probability(c);
            node.left = node.right = null;
            nodes.insert(node, node.prob);
        }

        // while there is more than one node
        while (nodes.getCount() > 1) {
            // remove 2 nodes with the least priority
            Node a = nodes.dequeue();
            Node b = nodes.dequeue();

            // make a new node linking these two
            Node link = new Node();
            link.letter = 0;
            link.prob = a.prob + b.prob;
            link.left = a;
            link.right = b;

            // insert it into the queue
            nodes.insert(link, link.prob);
        }

        // the tree is now complete, so we can find the code for each letter
        Node root = nodes.dequeue();
        codes = new String[26];
        fillInCodes(root, "");

        // print the code
        System.out.println("Huffman code: ");
        for (int i = 0; i < 26; i++) {
            System.out.println((char) (i + 'a') + ": " + codes[i]);
        }
    }

    void fillInCodes(Node node, String word) {
        // if null return
        if (node == null) {
            return;
        }

        // if it has a letter, assign the code
        if (node.letter != 0) {
            codes[node.letter - 'a'] = word;
        }

        // now recurse to the left and right
        fillInCodes(node.left, word + "0");
        fillInCodes(node.right, word + "1");
    }

    // compress some text using the huffman code
    String compress(char letter) {
        return codes[letter - 'a'];
    }
}

public class Huffman {
    // perform the main program
    public static void main(String args[]) {
        // check parameters
        if (args.length != 2) {
            System.out.println("Please pass input file and output file.");
            return;
        }

        // make the encoding
        HuffmanTree code = new HuffmanTree();

        try {
            // open the input file
            File fin = new File(args[0]);
            FileReader fr = new FileReader(fin);
            BufferedReader reader = new BufferedReader(fr);

            // open the output file
            File fout = new File(args[1]);
            PrintWriter writer = new PrintWriter(fout);

            int c = 0;
            while ((c = reader.read()) != -1) {
                char character = (char) c;

                // pass newlines, encode everything else
                if(c == '\n') {
                    writer.print("\n");
                } else {
                    // compress the character
                    String word = code.compress(character);

                    // write it to the output (not actually in binary)
                    writer.print(word);
                }
            }

            // close the files
            reader.close();
            writer.close();

        } catch (Exception e) {
            System.out.println("Could not perform I/O");
        }
    }
}