Huffman.java

import java.util.*;

public class Huffman {

    static String charCode;

    public static void main(String[] args) {
        String text = "ABA11$A";

        System.out.println("string: " + text);

        HashMap<String, Integer> frequencies = new HashMap<String, Integer>();

        for (int i=0; i < text.length(); i++) {
            String character = text.substring(i, (i+1));
            if (frequencies.containsKey(character)) {
                frequencies.put(character, frequencies.get(character)+1);
            } else {
                frequencies.put(character, 1);
            }
        }

        //System.out.println("frequencies: " + frequencies);

        ArrayList<BinaryNode> charNodes = new ArrayList<BinaryNode>();
        frequencies.forEach((k, v) -> charNodes.add(new BinaryNode(k,v)));

        for (int i = 0; i < charNodes.size()-1; i++) 
        { 
            int min_idx = i; 
            for (int j = i+1; j < charNodes.size(); j++) 
                if (charNodes.get(j).data < charNodes.get(min_idx).data) 
                    min_idx = j; 
            BinaryNode temp = charNodes.get(min_idx); 
            charNodes.set(min_idx,charNodes.get(i));
            charNodes.set(i, temp); 
        } 

        BinaryTree tree = new BinaryTree();

        while (charNodes.size() > 1) {
            BinaryNode one = charNodes.get(0);
            BinaryNode two = charNodes.get(1);
            BinaryNode newNode = new BinaryNode(one.data + two.data);
            tree.makeRoot(newNode, one, two);
            charNodes.remove(0);
            charNodes.remove(0);
            int j = 0;
            while(j < charNodes.size() && newNode.data > charNodes.get(j).data){
                j+=1;
            }
            charNodes.add(j, newNode);
        } 

        BinaryNode root = charNodes.get(0);
        tree.root = root;

        System.out.println("\nhuffman tree:");
        tree.showValues(root);

        HashMap<String, String> codes = new HashMap<String, String>();

        for (String j : frequencies.keySet()) {
            charCode = "";
            getCode(root, j);
            codes.put(j, charCode);
        }

        System.out.println("\ncodes: " + codes);

        String e = "";
        for (int i=0; i < text.length(); i++) {
            e += codes.get(text.substring(i,i+1));
        }
        System.out.println("\nencoded: " + e);

        String d = decode(tree, e);
        System.out.println("\ndecoded: " + d);

    }

    public static boolean getCode (BinaryNode root, String c) {
        if (root.character != null && root.character.equals(c)) { 
            return true; 
        }
        if (root.left == null && root.right == null) { 
            return false; 
        }
        if (root.left != null) {
            charCode += "0";
            boolean temp1 = getCode(root.left, c);
            if (!temp1) {
                charCode = charCode.substring(0, (charCode.length()-1));
                if (root.right != null) {
                    charCode += "1";
                    boolean temp2 = getCode(root.right, c);
                    if (!temp2) {
                        charCode = charCode.substring(0, (charCode.length()-1));
                        return false; 
                    } else { 
                        return true; 
                    } 
                } else { 
                    return false; 
                } 
            } else { 
                return true; 
            }
        }

        return false;

    }

    public static String decode (BinaryTree tree, String s) {
        String result = ""; 
        int i = 0;
        BinaryNode temp = tree.root;

        while (i < s.length()) {
            String charString = s.substring(i, i+1);

            if (charString.equals("0")) {
                temp = temp.left;
            }
            else if (charString.equals("1")) {
                temp = temp.right;
            }

            if (temp.character != null) {
                result += temp.character;
                temp = tree.root;
            }

            i += 1;
        }
        return result;
    }

}