Huffman Tree

Heap.java

public class Heap<E extends Comparable> {
  private java.util.ArrayList<E> list = new java.util.ArrayList<E>();

  /** Create a default heap */
  public Heap() {
  }

  /** Create a heap from an array of objects */
  public Heap(E[] objects) {
    for (int i = 0; i < objects.length; i++)
      add(objects[i]);
  }

  /** Add a new object into the heap */
  public void add(E newObject) {
    list.add(newObject); // Append to the heap
    int currentIndex = list.size() - 1; // The index of the last node

    while (currentIndex > 0) {
      int parentIndex = (currentIndex - 1) / 2;
      // Swap if the current object is greater than its parent
      if (list.get(currentIndex).compareTo(
          list.get(parentIndex)) > 0) {
        E temp = list.get(currentIndex);
        list.set(currentIndex, list.get(parentIndex));
        list.set(parentIndex, temp);
      }
      else
        break; // the tree is a heap now

      currentIndex = parentIndex;
    }
  }

  /** Remove the root from the heap */
  public E remove() {
    if (list.size() == 0) return null;
    
    E removedObject = list.get(0);
    list.set(0, list.get(list.size() - 1));
    list.remove(list.size() - 1);

    int currentIndex = 0;
    while (currentIndex < list.size()) {
      int leftChildIndex = 2 * currentIndex + 1;
      int rightChildIndex = 2 * currentIndex + 2;
      
      // Find the maximum between two children
      if (leftChildIndex >= list.size()) break; // The tree is a heap
      int maxIndex = leftChildIndex;
      if (rightChildIndex < list.size()) {
        if (list.get(maxIndex).compareTo(
            list.get(rightChildIndex)) < 0) {
          maxIndex = rightChildIndex;
        }
      }      
      
      // Swap if the current node is less than the maximum 
      if (list.get(currentIndex).compareTo(
          list.get(maxIndex)) < 0) {
        E temp = list.get(maxIndex);
        list.set(maxIndex, list.get(currentIndex));
        list.set(currentIndex, temp);
        currentIndex = maxIndex;
      }   
      else 
        break; // The tree is a heap
    }

    return removedObject;
  }

  /** Get the number of nodes in the tree */
  public int getSize() {
    return list.size();
  }
}

HuffmanCodingAnimation.java

import javax.swing.*;
import java.awt.*;
import java.awt.event.*;

/*
 * This program enables a user to enter text and displays the Huffman coding tree based on the entered text. 
 * The display shows the weight of the subtree inside a subtree's root circle. The character is displayed at each leaf node.
 * The encoded bits are displayed for the text in the dialog box.
 * The decoded text button is used to decode a string of bits int text. 
 */

public class HuffmanCodingAnimation extends JApplet {
  /**
	 * 
	 */
  private static final long serialVersionUID = 1L;
  private TreeView treeView = new TreeView();
  private Tree tree;
  
  public HuffmanCodingAnimation(Tree final_tree) {
	tree = final_tree;
    add(new JScrollPane(treeView));
    treeView.setTree(tree);
        
    String[] codes = getCode(tree.root);
    //System.out.prinln( "\"" + text + "\"" + " is encoded to: " + encode(text, codes));
  }
  
  /** Decode the bit string into a text */
  public String decode(String bits) {
    String result = "";
    
    Node p = tree.root; // Start from the root
    for (int i = 0; i < bits.length(); i++) {
      if (bits.charAt(i) == '0') 
        p = p.left;
      else if (bits.charAt(i) == '1')
        p = p.right;
      else
        return null; // Wrong bits
      
      if (p.left == null) { // A leaf detected
        result += p.character;
        p = tree.root; // Restart from the root
      }
    }
    
    return result;
  }
  
  /** Encode the text using the codes */
  public static String encode(String text, String[] codes) {
    String result = "";
    for (int i = 0; i < text.length(); i++) 
      result += codes[text.charAt(i)];    
    return result;   
  }
  
  /** Get Huffman codes for the characters 
   * This method is called once after a Huffman tree is built
   */
  public static String[] getCode(Node root) {
    if (root == null) return null;    
    String[] codes = new String[2 * 128];
    assignCode(root, codes);
    return codes;
  }
  
  /* Recursively get codes to the leaf node */
  private static void assignCode(Node root, String[] codes) {
    if (root.left != null) {
      root.left.code = root.code + "0";
      assignCode(root.left, codes);
      
      root.right.code = root.code + "1";
      assignCode(root.right, codes);
    }
    else {
    	
      codes[(int)root.character.charAt(0)] = root.code;
    }
  }
  
  // Inner class TreeView for displaying a tree on a panel
  class TreeView extends JPanel {   
    /**
	 * 
	 */
	private static final long serialVersionUID = 1L;
	private int radius = 20; // Tree node radius
    private int vGap = 50; // Gap between two levels in a tree
    Tree tree;
    
    public TreeView() { 
    }
    
    public TreeView(Tree tree) {
      this.tree = tree;  
    }
    
    public void setTree(Tree tree) {
      this.tree = tree;
      repaint();
    }
    
    protected void paintComponent(Graphics g) {
      super.paintComponent(g);

      if (tree == null) return;
      
      if (tree.root != null) {
        // Display tree recursively    
        displayTree(g, tree.root, getWidth() / 2, 30, 
          getWidth() / 4); 
      }
    }
        
    /** Display a subtree rooted at position (x, y) */
    private void displayTree(Graphics g, Node root, 
        int x, int y, int hGap) {
      // Display the root
      g.drawOval(x - radius, y - radius, 2 * radius, 2 * radius);
      g.drawString(root.frequency + "", x - 6, y + 4);
            
      if (root.left == null) // Display the character for leaf node
        g.drawString(root.character + "", x - 6, y + 34);
        
      if (root.left != null) {
        // Draw a line to the left node
        connectLeftChild(g, x - hGap, y + vGap, x, y);
        // Draw the left subtree recursively
        displayTree(g, root.left, x - hGap, y + vGap, hGap / 2);
      }
          
      if (root.right != null) {
        // Draw a line to the right node
        connectRightChild(g, x + hGap, y + vGap, x, y);
        // Draw the right subtree recursively
        displayTree(g, root.right, x + hGap, y + vGap, hGap / 2);  
      }
    }
        
    /** Connect a parent at (x2, y2) with 
     * its left child at (x1, y1) */
    private void connectLeftChild(Graphics g, 
        int x1, int y1, int x2, int y2) { 
      double d = Math.sqrt(vGap * vGap + (x2 - x1) * (x2 - x1));
      int x11 = (int)(x1 + radius * (x2 - x1) / d);
      int y11 = (int)(y1 - radius * vGap / d);
      int x21 = (int)(x2 - radius * (x2 - x1) / d);
      int y21 = (int)(y2 + radius * vGap / d);
      g.drawLine(x11, y11, x21, y21);
      g.drawString("0", (x11 + x21) / 2 - 5, (y11 + y21) / 2);
    }
        
    /** Connect a parent at (x2, y2) with 
     * its right child at (x1, y1) */
    private void connectRightChild(Graphics g, 
        int x1, int y1, int x2, int y2) {
      double d = Math.sqrt(vGap * vGap + (x2 - x1) * (x2 - x1));
      int x11 = (int)(x1 - radius * (x1 - x2) / d);
      int y11 = (int)(y1 - radius * vGap / d);
      int x21 = (int)(x2 + radius * (x1 - x2) / d);
      int y21 = (int)(y2 + radius * vGap / d);
      g.drawLine(x11, y11, x21, y21);
      g.drawString("1", (x11 + x21) / 2 + 5, (y11 + y21) / 2);
    }
    
    public Dimension getPreferredSize() {
      return new Dimension(300, 300);
    }
  }
}

HuffmanTree.java

import java.io.*;
import java.util.HashMap;
import java.util.Map;
import java.util.Random;
import java.util.Set;

import javax.swing.JApplet;
import javax.swing.JFrame;


public class HuffmanTree {

	private Map<String, Integer> text;

	public HuffmanTree() {
		text = new HashMap<String, Integer>();
	}

	public void addElement(String c)
	{
		if( text.containsKey(c) )
		{
			text.put( c, text.get(c) + 1 );
		}
		else
		{
			text.put( c , 1 );
		}
	}
	public Node[] getList(){
		Node[] list = new Node[text.size()];

		int i = 0;
		for (String key: text.keySet()) {
			list[i] = new Node( key, text.get(key));
			i++;
		}
		return bubbleS(list);
	}

	public static String[] getCode(Node root) {
		if (root == null) return null;    
		String[] codes = new String[2 * 128];
		assignCode(root, codes);
		return codes;
	}

	public Tree encode(String text, String out_file)
	{
		for( int i = 0; i < text.length(); i++)
		{
			if( text.charAt(i) == '\n')
				addElement( "NEWLINE" );
			else if( text.charAt(i) == ' ')
				addElement( "SPACE" );
			else
				addElement( String.valueOf( text.charAt(i)) );
		}

		Tree result = buildTree();

		String[] huffman_codes = getCode( result.root );


		try{
			String huffman_encoding = "";

			for(int i=0; i< text.length(); i++)
			{
				huffman_encoding += huffman_codes[text.charAt(i)];
			}

			BufferedWriter out_huf = new BufferedWriter(new FileWriter("brisbon.huf"));
			for(Object key:this.text.keySet())
			{
				if( key.toString() == "NEWLINE")
					out_huf.write("NEWLINE"+" "+huffman_codes[  '\n'  ]+"\n");
				else if( key.toString() == "SPACE")
					out_huf.write("SPACE"+" "+huffman_codes[  ' '  ]+"\n");
				else
					out_huf.write(key+" "+huffman_codes[  key.toString().charAt(0)  ]+"\n");
			}
			out_huf.close();

			BufferedWriter out = new BufferedWriter(new FileWriter(out_file)); 
			out.write(huffman_encoding); 
			out.close(); 
		}
		catch(IOException ex)
		{
			ex.printStackTrace();
		}

		return result;
	}

	public char getASCIICode( String val )
	{
		if( val.equals( "NEWLINE" ) )
		{
			return ('\n');
		}
		else if( val.equals("SPACE") )
		{
			return (' ');
		}
		else
		{
			return val.charAt(0);
		}
	}

	public String decode(String bits, String huffman_codes_file, String out_file)
	{

		BufferedReader input;
		Map<String, Character> encoded_values = new HashMap<String, Character>();

		try {
			input = new BufferedReader(new FileReader(huffman_codes_file));

			String line = null;

			while( (line = input.readLine()) != null )
			{
				if( line != "" )
				{
					String[] values = line.split(" ");
					encoded_values.put(values[1], getASCIICode( values[0] ));
				}
			}

			input.close();

		} catch (IOException ex) {
			ex.printStackTrace();
		}

		String result = "";  
		String current_code = "";

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

			current_code += bits.charAt(i);
			if( encoded_values.containsKey(current_code) )
			{
				result += encoded_values.get(current_code);
				current_code = "";
			}
		}

		try{
			BufferedWriter out = new BufferedWriter(new FileWriter(out_file)); 
			out.write(result); 
			out.close(); 
		}
		catch(IOException ex)
		{
			ex.printStackTrace();
		}

		return result;
	}

	/* Recursively get codes to the leaf node */
	private static void assignCode(Node root, String[] codes) {
		if (root.left != null) {
			root.left.code = root.code + "0";
			assignCode(root.left, codes);

			root.right.code = root.code + "1";
			assignCode(root.right, codes);
		}
		else {
			if( root.character == "SPACE")
			{
				codes[(int)' '] = root.code;
			}
			else if( root.character == "NEWLINE")
			{
				codes[(int)'\n'] = root.code;
			}
			else
				codes[(int)root.character.charAt(0)] = root.code;
		}
	}

	public Node[] bubbleS(Node[] list) {
		int size = list.length;
		for (int iter=1; iter < size; iter++) 
		{  // count how many times
			// This next loop becomes shorter and shorter
			for (int i=0; i < size-iter; i++) 
			{
				if (list[i].frequency > list[i+1].frequency) 
				{
					// exchange elements
					Node temp = list[i];  
					list[i] = list[i+1];  
					list[i+1] = temp;
				}
			}
		}
		return list;
	}


	public Tree buildTree(){
		Node[] chars = getList();

		Heap<Tree> heap = new Heap<Tree>();

		for(int i = 0; i < chars.length; i++)
		{
			heap.add( new Tree( chars[i].character, chars[i].frequency));
		}

		//First deal with parentless nodes
		while( heap.getSize() > 1 )
		{
			Tree left = heap.remove();
			Tree right = heap.remove();

			heap.add(new Tree( left, right));
		}

		return heap.remove();
	}

	public String generateRandomFile(String file2write, int size)
	{
		int ASCII_POSSIBLE = 256;
		String result = "";
		Random gen = new Random();

		for( int i = 0; i < size; i++)
		{
			int val = gen.nextInt(ASCII_POSSIBLE);
			result += (char)(val);
		}

		try{
			BufferedWriter out = new BufferedWriter(new FileWriter(file2write)); 
			out.write(result); 
			out.close(); 
		}
		catch( IOException ex)
		{
			ex.printStackTrace();
		}

		return file2write;
	}

	public enum OPERATION {
		ENCRYPT, DECRYPT, ENCODE, DECODE, ERROR, EXIT;
	}
	
	public static boolean checkCLIArgs(String[] cli_args)
	{
		//format
		
		return false;
	}

	public static void main(String[] args) {


		OPERATION op = OPERATION.ERROR;

		if( args.length < 1)
		{
			System.err.println("Please supply valid command line arguments.");
			return;
		}

		if( !checkCLIArgs(args) )
		{
			System.err.println("Please supply valid command line arguments.");
			System.out.println("USAGE: ");
			System.out.println("\t--encode Performs an encode of the files specified");
			System.out.println("\t\t --in supplied file name to encode, if genrated, generated text will be put here");
			System.out.println("\t\t gen [Optional] generate random ascii character file");
			System.out.println("\t--decode Performs a decode of the files specified");
			System.out.println("\t\t --in supplied file name to decode");
			System.out.println("\t\t --codefile supplied file name to import huffman codes to");
			return;
		}
		else
		{


			HuffmanTree tree = new HuffmanTree();
			Tree final_tree = null;

			switch( op )
			{
			case ENCODE:

				String file2encode = null;
				try{
					if( args.length == 4 && args[3].equals( "gen" ))
					{
						file2encode = tree.generateRandomFile(args[2], 500);
					}
					else
					{
						file2encode = args[2];
					}

					BufferedReader input =  new BufferedReader(new FileReader(file2encode));

					int just_read = -1;
					String text = "";
					//Read in all characters
					while( (just_read = input.read()) != -1 )
						text += (char)just_read;

					tree.encode(text, "brisbon.new");
				}
				catch(IOException ex)
				{
					ex.printStackTrace();
				}

				break;
			case DECODE:
				String file2decode = args[2];
				String huffman_codes = args[4];
				try{
					BufferedReader input =  new BufferedReader(new FileReader(file2decode));
					int just_read = -1;

					String text = "";
					//Read in all characters
					while( (just_read = input.read()) != -1 )
						text += (char)just_read;
					input.close();

					tree.decode(text, huffman_codes, "brisbon_decompressed.txt");
				}
				catch(IOException ex)
				{
					ex.printStackTrace();
				}

				break;

			case EXIT:
				System.out.println("SHUTTING DOWN NOW!");
				return;
			}
		}
	}
}

Node.java

public class Node {
	public Node(){};
	public Node(String chara, int freq){ character = chara; frequency = freq;}
	Node left, right = null;
	String character;
	int frequency;
	String code = "";
}

Tree.java

public class Tree implements Comparable<Tree>{
	Node root;
	
    public Tree(Tree t1, Tree t2) {
        root = new Node();
        root.left = t1.root;
        root.right = t2.root;
        root.frequency = t1.root.frequency + t2.root.frequency;
      }
      
      /** Create a tree containing a leaf node */
      public Tree(String element, int frequency) {
        root = new Node(element, frequency);
      }
      
      /** Compare trees based on their weights */
      public int compareTo(Tree o) {
        if (root.frequency < o.root.frequency) // Purposely reverse the order
          return 1;
        else if (root.frequency == o.root.frequency)
          return 0;
        else
          return -1;
      }
}