Huffman.java

package cs2321;

import java.io.BufferedWriter;
import java.io.DataOutputStream;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.nio.file.Files;
import java.nio.file.Paths;

import cs2321.HeapPQ.PQEntry;
import cs2321.LinkedBinaryTree.Node;
import net.datastructures.*;


/*
 * The format of the compressed file includes 3 continuously parts:
 *  1. prefix tree in bit stream
 *  2. length of the original file using 4 bytes
 *  3. data coded with Huffman coding. 
 * 
 * Encoding prefix tree bit stream: 
 *   if the node is external, output 0, followed by the letter
 *   if the node is internal, output 1, followed by 
 *  		the bit stream of left subtree, then the bit stream of right subtree. 
 */
public class Huffman {
	
	/**
	 * 
	 * Compress file using Huffman code. 
	 *
	 * @param inputFile  The original data file
	 * @param outputFile  The compressed data file that should be generated. 
	 * @return the length of the data encoded with Huffman Code, don't include data for the prefix tree and length of the original file. 
	 */
	public int compress(String inputFile, String outputFile) {
		HeapPQ<Integer, LinkedBinaryTree<Character>> heap = new HeapPQ<Integer, LinkedBinaryTree<Character>>();
		FileReader reader = null;
		File f = new File(inputFile);
		//TODO: implement the compress
		
		try {
			reader = new FileReader(f); //create a new file reader
		} catch (FileNotFoundException e) {
			e.printStackTrace();
		}
		
		char[] ch = new char[(int) f.length()];
		
		try {
			reader.read(ch); //read characters into the array
		} catch (IOException e) {
			e.printStackTrace();
		}
		
		//find frequency counts
		int[] freq = new int[256];
		
		for(char character: ch) {
			freq[character]++;
		}
	
		//build the tree
		for(int i = 0; i < 256; i++) {
			if(freq[i] > 0) {
				LinkedBinaryTree<Character> tempTree = new LinkedBinaryTree<Character>();
				tempTree.addRoot((char)i);
				heap.insert(freq[i], tempTree);
			}
		}
		
		while(heap.size() > 1) {
			Entry<Integer, LinkedBinaryTree<Character>> tempEntry1 = heap.removeMin();
			Entry<Integer, LinkedBinaryTree<Character>> tempEntry2 = heap.removeMin();
			
			int freqSum = tempEntry1.getKey() + tempEntry2.getKey();
			LinkedBinaryTree<Character> tempTree = new LinkedBinaryTree<Character>();
			
			tempTree.addRoot(null);
			tempTree.addLeft(tempTree.root(), tempEntry1.getValue().root.getElement());
			tempTree.addRight(tempTree.root(), tempEntry2.getValue().root.getElement());
		
			heap.insert(freqSum,tempTree);
		}
		
		//build the code table
		String[] codeTable = new String[256];
		LinkedBinaryTree<Character> t = heap.removeMin().getValue();
		
		buildCode(codeTable, t, t.root(), "");
		
		//write the tree
		DataOutputStream writer = null;
		
		try {
			 writer = new DataOutputStream(new FileOutputStream(outputFile));
		} catch (FileNotFoundException e) {
			e.printStackTrace();
		}
		
		writePrefixTree(t, t.root, writer);
		
		return 0;
	}
	
	void buildCode(String[] codeTable, LinkedBinaryTree<Character> v, Position<Character> p, String code) {
		if(v.isExternal(p)) {
			codeTable[p.getElement()] = code;
		}
		else {
			buildCode(codeTable,v, v.left(p), code + '0');
			buildCode(codeTable, v, v.right(p), code + '1');
		}
	}
	
	void writePrefixTree(LinkedBinaryTree<Character> v, Position<Character> p, DataOutputStream writer) {
		if(v.isExternal(p)) {
			try {
				writer.write(1);
			} catch (IOException e) {
				e.printStackTrace();
			}
			
			try {
				writer.write(p.getElement());
			} catch (IllegalStateException | IOException e) {
				e.printStackTrace();
			}
		}
		else {
			try {
				writer.write(0);
			} catch (IOException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
			
			writePrefixTree(v, v.left(p), writer);
			writePrefixTree(v, v.right(p), writer);
		}
	}
	
	/**
	 * Decode the compressed data file back to the original data file. 
	 * 
	 * @param inputFile : the compressed file
	 * @param outputFile : the file that should be generated by the decode function using ascii code. 
	 */
	public void decode(String inputFile, String outputFile) {	
		//TODO: implement the decode
		return;
	}
	
	
	public static void main(String [ ] args) {
		Huffman huffman = new Huffman();
		int length;
		
		// db.txt has only two letters "ab". The length with Huffman coding should be 2. 
		length = huffman.compress("ab.txt", "ab.txt.huffman");
		System.out.println("length is " + length);
		
		// decode your newly created compress file. The generated file "ab.txt.decoded" should have same content as "ab.txt"
		huffman.decode("ab.txt.huffman", "ab.txt.decoded");
		
		
		// decode the previous correctly compressed file by instructor.  The generated file "ab.txt.decoded" should have content as "ab.txt"
		huffman.decode("ab.txt.compressed", "ab.txt.decoded");


		// You may perform the above same testing for other files, like abra.txt, gogo.txt, tinytinyTable.txt
		
	}
	
	
}