import java.io.File;

import java.io.FileInputStream;

import java.io.FileOutputStream;

import java.io.IOException;

import java.io.InputStream;

import java.io.OutputStream;

import java.util.PriorityQueue;



/**

 * Lab 7: Huffman tree

 * 

 * A class to provides methods for huffman tree based un/compression of

 * text-files

 */

public class Huffman {



	/**

	 * The translation table used to compress/uncompress the last file.

	 * 

	 * This table is represented by an array of BitStrings, where table[i]

	 * holdes the BitString for the i-th character.

	 * 

	 * You may use an array with 256 entries even if not every character occures

	 * in the inputfile.

	 */

	private BitString[] table;



	/**

	 * This method opens and compresses the file inFilename and saves the

	 * results in the file outFilename.

	 * 

	 * IMPORTANT: This method is for your testing only. It is ready to use (if

	 * Huffman::compress(String, OutputStream) is implemented).

	 * 

	 * You can modify it.

	 * 

	 * @param inFilename

	 *            the file to compress

	 * @param outFilename

	 *            the result file

	 * @throws IOException

	 */

	public void compress(String inFilename, String outFilename) throws IOException {

		File outFile = new File(outFilename);

		if (!outFile.exists())

			outFile.createNewFile();

		compress(inFilename, new FileOutputStream(outFile));

	}



	/**

	 * This method performs the compression of the file inFilename. It writes

	 * the results to the OutputStream out.

	 * 

	 * IMPORTANT: We use this method for testing your solution. Don't modify the

	 * signature of this method.

	 * 

	 * Implement a Huffman Tree based compression. First write the used code

	 * table into the file as described in the task, followed by the compressd

	 * data. You may use the class HuffmanStreamWriter here. This class

	 * proviedes methods to write down the table and for writing BitStrings into

	 * the OutputStream.

	 * 

	 * @param inFilename

	 *            the file to compress

	 * @param out

	 *            outputStram to wirte the results

	 * @throws IOException

	 */

	public void compress(String inFilename, OutputStream out) throws IOException {

		// initialize storage for HuffmanTree-creation

		PriorityQueue<HuffmanTree> queue = new PriorityQueue<HuffmanTree>(256, new HuffmanComparator());

		// initialize InputStream

		HuffmanStreamReader reader = new HuffmanStreamReader(new FileInputStream(inFilename));

		// get counter of chars

		int[] count = getOccurence(reader);

		// for each possible ascii-code

		for (int i = 0; i < 256; i++) {

			// check if char is contained in file

			if (count[i] != 0){

				// create HuffmanTree only containing char and it's count

				HuffmanTree temp = new HuffmanTree((char) i, count[i]);

				// add it to storage

				queue.add(temp);

			}

		}

		// while there are more than 1 HuffmanTree in storage

		while (queue.size() > 1) {

			// get best HuffmanTree

			HuffmanTree first = queue.poll();

			// get second-best HuffmannTree

			HuffmanTree second = queue.poll();

			// create new HuffmanTree (both currently best HuffmanTree's as subtrees)

			HuffmanTree tempTree = new HuffmanTree(first, second);

			// add newly created HuffmanTree to storage

			queue.offer(tempTree);

		}

		// get last remaining HuffmanTree of storage

		HuffmanTree result = queue.poll();

		// read codetable out of the resulting HuffmanTree

		table = result.encode(new BitString[256], new BitString());

		// initialize HuffmanStreamWriter

		HuffmanStreamWriter writer = new HuffmanStreamWriter(out);

		// write codetable

		writer.writeCodeTable(table);

		// initialize buffer and iteration-variable

		BitString buffer = new BitString();

		int bit;

		// while end of InputStream isn't reached

		while ((bit = reader.readBit()) != -1) {

			// if next bit equals "0" append false/0 to buffer

			if (bit == 0)

				buffer.append(false);

			// otherwise next bit equals "1" -> append true/1 to buffer

			else

				buffer.append(true);

			// for every BitString in codetable

			for (int i = 0 ; i < table.length ; i++){

				// check if matching BitString is found and break for-loop if yes

				if (buffer.toString().compareTo(table[i].toString()) == 0){

					// if matching BitString found write it to OutputStream

					writer.write(table[i]);

					// and reset buffer

					buffer = new BitString();

				}

			}

		}

		// write EoF-Code to end of file

		writer.write(table[0]);

		// close all open streams

		writer.close();

		reader.close();

		out.close();

	}



	/**

	 * To count the occurence of every char in a stream.

	 * 

	 * @param stream

	 *            	stream to count chars in

	 * @return 

	 * 				int-array containing counter for every char (index = ascii-code)

	 * @throws IOException

	 */

	private int[] getOccurence(InputStream stream) throws IOException {

		// initialize result-array

		int[] result = new int[256];

		// set every counter to 0

		for (int i = 0 ; i < result.length ; i++){

			result[i] = 0;

		}

		// while end of stream isn't reached

		while (stream.available() > 0) {

			// read next char

			int newChar = stream.read();

			// check if char is valid

			if (newChar == (char) 0)

				throw new InvalidCharacterException();

			// if got valid char increase counter in array

			else

				result[newChar]++;

		}

		// set counter of EoF-Code to 1 (according to task)

		result[0] = 1;

		// return counter-array

		return result;

	}



	/**

	 * This method opens and uncompresses the file inFilename and saves the

	 * results in the file outFilename.

	 * 

	 * IMPORTANT: This method is for your testing only. It is ready to use (if

	 * Huffman::uncompress(String, OutputStream) is implemented).

	 * 

	 * You can modify it.

	 * 

	 * @param inFilename

	 *            the file to uncompress

	 * @param outFilename

	 *            the result file

	 * @throws IOException

	 */

	public void uncompress(String inFilename, String outFilename) throws IOException {

		File outFile = new File(outFilename);

		if (!outFile.exists())

			outFile.createNewFile();

		uncompress(inFilename, new FileOutputStream(outFile));

	}



	/**

	 * This method performs the uncompression of the file inFilename. It writes

	 * the results to the OutputStream out.

	 * 

	 * IMPORTANT: We use this method for testing your solution. Don't modify the

	 * signature of this method.

	 * 

	 * Implement a Huffman Tree based uncompression. The used code table is

	 * stored at the begin of the file. You can use the class

	 * HuffmanStreamReader to get the table. This class also offers methods to

	 * read a file bit by bit.

	 * 

	 * @param inFilename

	 *            the file to uncompress

	 * @param out

	 *            outputStram to wirte the results

	 * @throws IOException

	 */

	public void uncompress(String inFilename, OutputStream out) throws IOException {

		// initialize HuffmanStreamReader

		HuffmanStreamReader stream = new HuffmanStreamReader(new FileInputStream(inFilename));

		// read codetable

		table = stream.getCodeTable();

		// initialize buffer and iteration-variable

		BitString buffer = new BitString();

		int bit;

		// while contains bits

		while ((bit = stream.readBit()) != -1){

			// if next bit equals "0" -> append false/0 to result-BitString

			if (bit == 0)

				buffer.append(false);

			// else next bit equals "1" -> append true/1 to result-BitString

			else

				buffer.append(true);

			// for every BitString in codetable

			for (int i = 0 ; i < table.length ; i++){

				// check if matching BitString is found

				if (buffer.toString().compareTo(table[i].toString()) == 0){

					// write found ascii-code to OutputStream

					out.write(i);

					// and reset buffer

					buffer = new BitString();

				}

			}

		}

		// close all open streams

		stream.close();

		out.close();

	}



	/**

	 * This method returns the code table used by the last compress/uncompress

	 * operation.

	 * 

	 * @return the code table

	 */

	public BitString[] getCodeTable() {

		return table;

	}

}

--------------------------------------------------------------------------------------------
public class HuffmanTree{

	// name of node (-> char represented by node)
	public int name;
	// weight of huffmann-tree
	public int weight = 0;
	// right subtree
	public HuffmanTree right = null;
	// left subtree
	public HuffmanTree left = null;

	/**
	 * To construct a new empty HT (subtrees are null and weight is 0).
	 */
	public HuffmanTree() {
	}

	/**
	 * To construct a leaf of the HT with given name (subtrees are empty HTs).
	 * 
	 * @param name
	 *            name of leaf
	 */
	public HuffmanTree(int name, int weight) {
		this.name = name;
		this.weight = weight;
		right = new HuffmanTree();
		left = new HuffmanTree();
	}

	/**
	 * To construct a new HT with 2 given subtrees.
	 * 
	 * @param left
	 *            left subtree
	 * @param right
	 *            right subtree
	 */
	public HuffmanTree(HuffmanTree left, HuffmanTree right) {
		// set left subtree
		this.left = left;
		// set right subtree
		this.right = right;
		// update weight (sum of weights of both subtrees)
		this.weight = left.weight + right.weight;
	}

	/**
	 * To check if HT is empty or not.
	 * 
	 * @return 
	 * 			true, if both subtrees are null
	 */
	public boolean isEmpty() {
		return left == null && right == null;
	}

	/**
	 * To check if HT is a leaf.
	 * 
	 * @return 
	 * 			true, if actual HT is non-empty, but both subtrees are
	 */
	public boolean isLeaf() {
		return !this.isEmpty() && left.isEmpty() && right.isEmpty();
	}

	/**
	 * To traverse the HT writing result into a codetable
	 * 
	 * @param codeTable
	 * 					to codetable to fill codes in
	 * @param path
	 * 					path in HT = code of char
	 * @return
	 * 					filled codetable
	 */
	public BitString[] encode(BitString[] codeTable, BitString path) {
		// check if leaf is reached
		if (isLeaf()) {
			// if yes fill in code of char represented by leaf
			codeTable[name] = path;
			return codeTable;
		}
		// recursively traverse right subtree
		right.encode(codeTable, path.clone().append(true));
		// and left subtree
		left.encode(codeTable, path.clone().append(false));
		return codeTable;
	}
}

--------------------------------------------------------------------------------------------
public class BitString implements Cloneable {
	private byte[] string;

	private int length;

	/**
	 * Creates a new BitString filled with the length bits from data.
	 * 
	 * @param data
	 *            input data
	 * @param length
	 *            the length of the new BitString
	 */
	public BitString(byte[] data, int length) {
		if (length < 1)
			throw new IllegalArgumentException("length must be bigger than 0");
		if (data == null)
			throw new IllegalArgumentException("data may not be null");
		if ((length - 1) / 8 + 1 > data.length)
			throw new IllegalArgumentException(
					"data contains not enough elements for length: " + length);

		string = new byte[(length - 1) / 8 + 1];
		for (int i = 0; i < string.length - 1; i++)
			string[i] = data[i];
		this.length = length;
		// set unused bits in last byte to zero!
		if (length % 8 == 0) {
			// no unused bits
			string[string.length - 1] = data[string.length - 1];
		} else {
			// apply bitmask
			byte mask = (byte) (255 << (8 - length % 8));
			string[string.length - 1] = (byte) (data[string.length - 1] & mask);
		}
	}

	/**
	 * Creates an empty BitString
	 */
	public BitString() {
		this.length = 0;
	}

	/**
	 * Append a bit to the BitString
	 * 
	 * @param the
	 *            bit to append to string
	 * @return returns the complete BitString (this)
	 */
	public BitString append(boolean bit) {
		if (this.length % 8 == 0) {
			this.grow(1);
		}
		if (bit) {
			// set bit
			string[length / 8] = (byte) (string[length / 8] | (1 << (7 - length % 8)));
		}
		length++;
		return this;
	}

	/**
	 * Clones the BitString
	 * 
	 * @see java.lang.Object#clone()
	 */
	public BitString clone() {
		return string == null ? new BitString() : new BitString(string.clone(),
				length);
	}

	/**
	 * Returns the BitString as byte array
	 * 
	 * @return byte array or null if no bits are in BitString
	 */
	public byte[] getByteArray() {
		return (this.string == null) ? null : this.string.clone();
	}

	/**
	 * Returns the BitString as an boolean array
	 * 
	 * @return boolean array or null if no bits are in BitString
	 */
	public boolean[] getBitArray() {
		// return "empty array"
		if (this.length == 0)
			return null;

		// build array
		boolean[] result = new boolean[this.length];
		int bitShift = 7;
		int arrayPos = 0;
		int resultPos = 0;
		for (int i = 0; i < this.length; i++) {
			result[resultPos++] = (string[arrayPos] & 1 << bitShift) != 0;
			if (--bitShift < 0) {
				bitShift = 7;
				arrayPos++;
			}
		}
		return result;
	}

	/**
	 * Returns the cirrent length of the BitString (in bits)
	 * 
	 * @return the length of the BitString in bits
	 */
	public int getLength() {
		return this.length;
	}

	/**
	 * Allocates more space for bits
	 * 
	 * @param size
	 */
	private void grow(int size) {
		if (this.string == null) {
			this.string = new byte[size];
		} else {
			// create new array
			byte[] newString = new byte[this.string.length + size];
			// copy old content
			for (int i = 0; i < this.string.length; i++)
				newString[i] = this.string[i];
			// replace array
			this.string = newString;
		}
	}

	/**
	 * Returns a '0', '1' string
	 * 
	 * @see java.lang.Object#toString()
	 */
	public String toString() {
		StringBuffer buffer = new StringBuffer();
		int bitShift = 7;
		int arrayPos = 0;
		for (int i = 0; i < this.length; i++) {
			buffer.append((string[arrayPos] & 1 << bitShift) != 0 ? "1" : "0");
			if (--bitShift < 0) {
				bitShift = 7;
				arrayPos++;
			}
		}
		return buffer.toString();
	}
}
--------------------------------------------------------------------------------------------
import java.io.IOException;

import java.io.InputStream;



public class HuffmanStreamReader extends InputStream {



	private BitString[] codeTable;



	private InputStream stream;



	private int buffer;



	private int bitsInBuffer;



	/**

	 * Construts a new HuffmanStreamReader upon a given InputStream

	 * 

	 * This Reader tries to read a code table from the Stream.

	 * 

	 * @param stream

	 *            the InputStream

	 * @throws IOException

	 */

	public HuffmanStreamReader(InputStream stream) throws IOException {

		super();

		this.stream = stream;

		this.readCodeTable();

	}



	/**

	 * Reads the code table

	 * 

	 * @throws IOException

	 */

	private void readCodeTable() throws IOException {

		codeTable = new BitString[256];

		int character, codeLength, byteLength;

		character = this.read();

		codeLength = this.read();

		// read table entry by entry

		do {

			byteLength = (codeLength - 1) / 8 + 1;

			byte[] bytes = new byte[byteLength];



			for (int i = 0; i < byteLength; i++)

				bytes[i] = (byte) this.read();

			codeTable[character] = new BitString(bytes, codeLength);



			character = this.read();

			codeLength = this.read();

		} while (character != -1 && codeLength != 0);



	}



	/**

	 * Returns the code table

	 * 

	 * @return the code table

	 */

	public BitString[] getCodeTable() {

		return this.codeTable;

	}



	/**

	 * @see java.io.InputStream#read()

	 */

	public int read() throws IOException {

		return this.stream.read();

	}



	/**

	 * Reads and returns a bit (as integer) from the stream

	 * 

	 * @return the int value of the current bit or -1 if end of stream is

	 *         reached.

	 * @throws IOException

	 */

	public int readBit() throws IOException {

		if (this.bitsInBuffer == 0) {

			this.buffer = this.read();

			if (this.buffer == -1)

				return -1;

			this.bitsInBuffer = 8;

		}

		return (this.buffer >> (this.bitsInBuffer-- - 1)) & 1;

	}



}


--------------------------------------------------------------------------------------------
import java.io.IOException;

import java.io.OutputStream;



public class HuffmanStreamWriter extends OutputStream {

	private int buffer = 0;



	private int bufferOffset = 0;



	private OutputStream stream;



	/**

	 * Construct a new HuffmanStreamWriter upon a given OutputStream.

	 * 

	 * @param stream

	 *            the used OutputStream

	 */

	public HuffmanStreamWriter(OutputStream stream) {

		super();

		this.stream = stream;

	}



	/**

	 * Writes a bit to the file.

	 * 

	 * Note: Bits ar bufferd until a byte is complete.

	 * 

	 * @param bit

	 *            the bit to wirte

	 * @throws IOException

	 */

	private void writeBit(int bit) throws IOException {

		// append bit to buffer

		buffer |= (bit & 1) << (7 - bufferOffset++);

		if (bufferOffset == 8) {

			flushBitBuffer();

		}

	}



	/**

	 * Forces the bitBuffer to be flushed even if byte is inclomplete: - There

	 * must be atleast one bit to be flushed - Missing Bits ar filled with zeros

	 * 

	 * @throws IOException

	 */

	public void flushBitBuffer() throws IOException {

		if (bufferOffset != 0) {

			this.write(buffer);

			// reset buffer & offset

			bufferOffset = 0;

			buffer = 0;

		}

	}



	/**

	 * Writes a BitString Object to the OutputStream

	 * 

	 * @param bitString

	 *            to wirte

	 * @throws IOException

	 */

	public void write(BitString bitString) throws IOException {

		for (boolean bit : bitString.getBitArray()) {

			this.writeBit(bit ? 1 : 0);

		}

	}



	/**

	 * Flushes BitBuffer and closes the stream.

	 * 

	 * To ensure that no bits are "left in buffer" this method should be called

	 * after all write operations are finished.

	 * 

	 * @see java.io.OutputStream#close()

	 */

	public void close() throws IOException {

		// pad buffer with zeros and flush it

		this.flushBitBuffer();

		// execute super method

		super.close();

	}



	/**

	 * Writes a BitString[] representing the code table to the stream.

	 * 

	 * @param table

	 *            to write.

	 * @throws IOException

	 */

	public void writeCodeTable(BitString[] table) throws IOException {

		for (int i = 0; i < table.length; i++) {

			if (table[i] != null) {

				this.write(i);

				this.write(table[i].getLength());

				this.write(table[i]);

				this.flushBitBuffer();

			}

		}

		// write end of table

		this.write((char) 0);

		this.write((char) 0);

	}



	/**

	 * @see java.io.OutputStream#write(int)

	 */

	public void write(int character) throws IOException {

		stream.write(character);

	}

}


--------------------------------------------------------------------------------------------