public class HuffmannTree {
	
	// name of node (-> char represented by node)
	private int name;
	// weight of huffmann-tree
	private int weight;
	// right subtree
	private HuffmannTree right;
	// left subtree
	private HuffmannTree left;

	
	/**
	 * To construct a new empty HT (subtrees are null and weight is 0).
	 */
	public HuffmannTree(){
		right = null;
		left = null;
		weight = 0;
	}
	
	/**
	 * To construct a leaf of the HT with given name (subtrees are empty HTs).
	 * 
	 * @param name
	 * 			name of leaf		
	 */
	public HuffmannTree(int name){
		this.name = name;
		right = new HuffmannTree();
		left = new HuffmannTree();
	}
	
	/**
	 * To construct a new HT with 2 given subtrees.
	 * 
	 * @param left
	 * 			left subtree
	 * @param right
	 * 			right subtree
	 */
	public HuffmannTree(HuffmannTree left, HuffmannTree 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 !isEmpty() && left.isEmpty() && right.isEmpty();
	}
	
	/**
	 * To check if HT is lighter than another one.
	 * 
	 * @param tree
	 * 			other tree to check
	 * @return
	 * 			true, if actual HT is lighter than given HT
	 */
	public boolean lighter(HuffmannTree tree){
		return this.weight() < tree.weight();
	}
	
	public int weight(){
		return weight;
	}
	
	public int getName(){
		return name;
	}
	
	public void setName(int name){
		this.name = name;
	}
	
	public HuffmannTree left(){
		return left;
	}
	
	public HuffmannTree right(){
		return right;
	}
}



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();
	}
}


private HuffmannTree createHuffmannTree(BitString[] codes){
		HuffmannTree result = new HuffmannTree();
		for (int i = 0 ; i < codes.length ; i++){
			BitString actChar = codes[i];
			HuffmannTree actTree = result;
			String temp = actChar.toString();
			for (int j = 0 ; j < actChar.getLength() ; j++){
				if (temp.charAt(j) == 0){
					if (actTree.isEmpty()){
						actTree = new HuffmannTree();
						actTree = actTree.left();
					}
					else
						actTree = actTree.left();
				}
				else{
					if (actTree.isEmpty()){
						actTree = new HuffmannTree();
						actTree = actTree.right();
					}
					else
						actTree = actTree.right();
				}
			}
			actTree.setName((char)i);
		}
		return result;
	}