HuffmanTree

				
//**************************************
// Name: HuffmanTree
// Description:Generates Huffman codes

//
//This code is copyrighted and has// limited warranties.Please see http://www.Planet-Source-Code.com/vb/scripts/ShowCode.asp?txtCodeId=7054&lngWId=2//for details.//**************************************

import java.util.*;
import java.io.*;
public class HuffmanTree {
	private HuffNode root;
	private ArrayList<Character> ListOfChars;
	public HuffmanTree(Map<Character, Integer> counts) {	/* 	This constructor constructs the huffman tree and
	 															fills all the characters in an ArrayList */
		if(counts==null) {
			throw new IllegalArgumentException();
		}
		FillSet(counts);
		PriorityQueue<HuffNode> q=new PriorityQueue<HuffNode>(counts.size());
		for(char c:counts.keySet()) {
			q.add(new HuffNode(c,counts.get(c)));
		}
		add(q);
	}
	public Map<Character, String> createEncodings() {//This method creates encodings for all characters
		Map<Character, String> map=new TreeMap<Character, String>();
		for(int i=0;i<ListOfChars.size();i++) {
			map.put(ListOfChars.get(i),encode(root,ListOfChars.get(i)));
		}
		return map;
	}
	// This method compresses the input
	public void compress(InputStream input, BitOutputStream output) throws IOException {
		if(input==null||output==null) {
			throw new IllegalArgumentException();
		}
		Map<Character, String> map=this.createEncodings();
		System.out.println(map);
		int c=input.read();
		while(c!=-1) {
			String code=map.get((char)c);
			output.writeBits(code);
			c=input.read();
		}
		output.close();
	}
	// This method decompresses the input
	public void decompress(BitInputStream input, OutputStream output) throws IOException {
		String s=""+input.readBit();
		while(decode(s,this.root)==-1) {
			s=s+input.readBit();
		}
		while(decode(s,this.root)!=-1) {
			output.write(decode(s,this.root));
			s=""+input.readBit();
			while(decode(s,this.root)==-1&&!s.contains("-1")) {
				s=s+input.readBit();
			}
		}
		output.close();
	}
	// This method decodes the compressed character into the original one
	private int decode(String s,HuffNode node) {
		if(node.left==null||node.right==null) {
			return node.c;
		}
		else if(s.startsWith("0")) {
			return decode(s.substring(1),node.left);
		}
		else if(s.startsWith("1")) {
			return decode(s.substring(1),node.right);
		}
		else {
			return -1;
		}
	}
	private String encode(HuffNode node,char c) { //This method creates an encoding for a given character
		if(node.c==c&&(node.left==null||node.right==null)) {
			return "";
		}
		else if(node.c!=c&&(node.left==null||node.right==null)) {
			return null;
		}
		String s1="0"+encode(node.left, c);
		String s2="1"+encode(node.right,c);
		if(s1.contains("null")) {
			return s2;
		}
		else if(s2.contains("null")) {
			return s1;
		}
		else {
			return null;
		}
	}
	private void FillSet(Map<Character, Integer> counts) {//This method fills all the characters in an ArrayList
		ListOfChars=new ArrayList<Character>();
		for(char c:counts.keySet()) {
			ListOfChars.add(c);
		}
	}
	private void add(PriorityQueue<HuffNode> q) { // This method creates the huffman tree
		while(q.size()>1) {
			HuffNode temp1=q.remove();
			HuffNode temp2=q.remove();
			HuffNode total=new HuffNode(temp1.count+temp2.count);
			total.left=temp1;
			total.right=temp2;
			q.add(total);
		}
		root=q.remove();
	}
	private class HuffNode implements Comparable<HuffNode> { // Class for the HuffNode
		private static final char default_char='~';
		private char c;
		private int count;
		private HuffNode left;
		private HuffNode right;
		// Constructor taking a character and an integer
		private HuffNode(char c,int count) {
			this.c=c;
			this.count=count;
			this.left=null;
			this.right=null;
		}
		// Constructor taking an integer
		private HuffNode(int count) {
			this.c=default_char;
			this.count=count;
			this.left=null;
			this.right=null;
		}
		public int compareTo(HuffNode node) {
			return this.count-node.count;
		}
	}
}