package huffman;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;

public class Main {
    public static void main(String[] args) {
        HuffmanEncoder he = new HuffmanEncoder("illiad.txt");
        String encoded = he.getEncoded();
        //String unencoded = he.unencode();

        //System.out.println(encoded);
        //System.out.println(unencoded);

        try {
            BufferedWriter bw = new BufferedWriter(new FileWriter(new File("output.txt")));
            bw.append(encoded);
            bw.close();
        } catch (IOException e) {
            // TODO Auto-generated catch block
            e.printStackTrace();
        }

        he.printTree();
    }
}

class HuffmanEncoder {
    Node<Character> home;
    HashMap<Character, String> dict;
    HashMap<String, Character> un_dict;
    String encoded;

    public HuffmanEncoder(String filename) {
        String total_text = "";
        HashMap<Character, Integer> char_table = new HashMap<Character, Integer>();
        try {
            BufferedReader br = new BufferedReader(new FileReader(new File(filename)));
            int i = 0;
            int count = 0;
            while ((i = br.read()) != -1) {
                count++;
                char c = (char)i;
                if (!char_table.containsKey(c))
                    char_table.put(c, 0);
                char_table.replace(c, char_table.get(c) + 1);
                total_text += Character.toString(c);
                if (count % 100000 == 0) {
                    System.out.println(count);
                }
            }
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        } catch (IOException e) {
            e.printStackTrace();
        }
        getDict(char_table);
        dict = home.getDict();
        un_dict = new HashMap<String, Character>();
        for (Entry<Character, String> e : dict.entrySet())
            un_dict.put(e.getValue(), e.getKey());

        encoded = "";
        for (char c : total_text.toCharArray())
            encoded += dict.get(c);
    }

    public String getEncoded() {
        return this.encoded;
    }

    public void printTree() {
        home.printNode(0);
    }

    public String unencode() {
        String unencoded = "";
        String curr = "";
        for (char c : encoded.toCharArray()) {
            curr += c;
            if (un_dict.containsKey(curr)) {
                unencoded += un_dict.get(curr);
                curr = "";
            }
        }
        return unencoded;
    }

    public void getDict(HashMap<Character, Integer> char_table) {
        List<Entry<Character, Integer>> freq_list = sortChars(char_table);
        List<Node<Character>> queue = new ArrayList<Node<Character>>();

        for(Entry<Character, Integer> e : freq_list)
            queue.add(new Node<Character>(e.getKey(), e.getValue()));

        while (queue.size() > 1) {
            Node<Character> b = queue.get(queue.size() - 1);
            queue.remove(queue.size() - 1);
            Node<Character> a = queue.get(queue.size() - 1);
            queue.remove(queue.size() - 1);
            Node<Character> new_node = new Node<Character>(a,b);
            queue.add(new_node);
            queue = sortQueue(queue);
        }
        home = queue.get(0);
    }

    public List<Entry<Character, Integer>> sortChars(HashMap<Character, Integer> char_table){
        Comparator<Entry<Character, Integer>> valueComparator = new Comparator<Entry<Character,Integer>>() {
            @Override
            public int compare(Entry<Character, Integer> e1, Entry<Character, Integer> e2) {
                return -Integer.compare(e1.getValue(), e2.getValue());
            }
        };
        List<Entry<Character, Integer>> listOfEntries = new ArrayList<Entry<Character, Integer>>(char_table.entrySet());
        Collections.sort(listOfEntries, valueComparator);
        return listOfEntries;
    }

    public List<Node<Character>> sortQueue(List<Node<Character>> queue){
        Comparator<Node<Character>> valueComparator = new Comparator<Node<Character>>() {
            @Override
            public int compare(Node<Character> e1, Node<Character> e2) {
                return -Integer.compare(e1.weight, e2.weight);
            }
        };
        Collections.sort(queue, valueComparator);
        return queue;
    }
}

class Node<T> {
    T value = null;
    int weight;
    Node<T> parent = null;
    Node<T> a = null;
    Node<T> b = null;
    String encoding = "";

    public Node(T value, int weight) {
        this.value = value;
        this.weight = weight;
    }

    public Node(Node<T> a, Node<T> b) {
        this.a = a;
        a.parent = this;
        this.b = b;
        b.parent = this;
        this.weight = a.weight + b.weight;
    }

    public String getEncoding(String e) {
        String s = "";
        if (parent != null) {
            if (parent.a == this)
                s += "1";
            else
                s += "0";
            s = this.parent.getEncoding(e) + s;
        }
        return s;
    }

    public HashMap<T, String> getDict() {
        HashMap<T, String> dict = new HashMap<T, String>();
        if (value != null) {
            dict.put(value, this.getEncoding(""));
        }else {
            dict.putAll(a.getDict());
            dict.putAll(b.getDict());
        }
        return dict;
    }

    //testing
    public void printNode(int t) {
        for (int i = 0; i < t; i++)
            System.out.print("\t");
        System.out.print("(E=" + this.getEncoding(""));
        if (this.value == null)
            System.out.print(", W="+ this.weight +")\n");
        else
            System.out.print(", V="+this.weight+")\n");
        if (this.a != null)
            a.printNode(t + 1);
        if (this.b != null)
            b.printNode(t + 1);
    }
}