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