HuffmanAlgorithm.java

import java.util.ArrayList;
import java.util.*;
import java.util.HashMap;
import java.util.Map.*;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;

public class HuffmanAlgorithm {
	static String q = "aaaaabbbbbbbbbccccccccccccdddddddddddddeeeeeeeeeeeeeeeeffffffffffffffffffffffffffffffffffffffffffffff";
	static ArrayList<String> letters = new ArrayList<String>();
	static Queue<Node> que = new PriorityQueue<Node>();
	static ArrayList<Node> letterCode = new ArrayList<Node>();
	static String encoded = "";
	static String str = "";
	static Node root;
	
	public static void main(String[] args) {
		for(int i = 0;i<q.length()-1;i++) {
			letters.add(q.substring(i, i+1));
		}//added all letters to arraylist
		
		countFrequencies(letters);

		//BINARY TREE TIME!!!
		BinaryTree bt = new BinaryTree();
		root = createTree(que);
		
		//bt.printPreorder(n);
		encoded = encode(q, letterCode);
		System.out.println("Encoded: " + encoded);
		System.out.println("Decoded: " + decode(root, encoded, str));
		
	}//end main
	
	public static void getCode(Node n, String letter) {
		if(n.left==null && n.right == null) {//base case, is a leaf
			System.out.println(n.string + " : " + letter);
			letterCode.add(new Node(n.string, letter));
		}//end base 
		else {
			
			//alternative cases
			getCode(n.left, letter+"0");
			getCode(n.right, letter+"1");
			//will add on either a zero or a 1 depending on the dirction
		}
	}
	
	public static String encode(String q, ArrayList<Node> letterCode) {
		String str = "";
		for(int i = 0;i<q.length()-1;i++) {
			for(int j = 0;j<letterCode.size();j++) {
				if(q.subSequence(i, i+1).equals(letterCode.get(j).string)){
					//System.out.println(letterCode.get(i).string + " " + letterCode.get(i).dataS);
					str+=letterCode.get(j).dataS;
					
				}
			}
		}
		return str;
	}
	
	public static String decode(Node node, String encoded, String str) {
		
		int stringCount = 0;
		
		if(node.left==null && node.right==null) {
			str+=node.string;
			return decode(root, encoded, str);
		}
 
        /* then recur on left subtree */
		if(node.left!=null || node.right!=null) {
			if(encoded.length()>0) {
				if(encoded.substring(0, 1).equals("0")) {
					return decode(node.left, encoded.substring(1), str);
					//stringCount++;
				}
				else if(encoded.substring(0, 1).equals("1")) {
					return decode(node.right, encoded.substring(1), str);
					//stringCount++;
				}
			} else {
				return str;
			}
		}
		return str;
	}
	
	public static void countFrequencies(ArrayList<String> letters) {
		Map<String, Integer> hm = new HashMap<String, Integer>();
		
		for(String i:letters) {
			if(hm.containsKey(i)) {
				int val = hm.get(i);
				hm.put(i, val+1);
			} else {
				hm.put(i, 1);
			}
		}
		for(Map.Entry<String, Integer> val : hm.entrySet()) {
			//System.out.println(val.getKey() + " " + val.getValue());
			que.add(new Node(val.getKey(), val.getValue()));
		}//iterating through values and getting frequencies!
		
	}//end method
	
	public static Node createTree(Queue que) {
		while(que.size()>=2) {
			Node val1 = ((Node)que.poll());
			Node val2 = ((Node)que.poll());
			//System.out.println(val1.data+val2.data);
			Node n = new Node(null, val1.data+val2.data);
			n.left = val1;
			n.right = val2;
			que.add(n);
		}//end of while
		getCode((Node)que.peek(), "");
		return (Node)que.peek();
	}
	
	
	
}//end class