Inital commitHEADmaster

9 files changed, 950 insertions, 0 deletions

diff --git a/projects/project4_huffman_tree/BinaryNode.java b/projects/project4_huffman_tree/BinaryNode.java
new file mode 100644
index 0000000..d498b8e
--- /dev/null
+++ b/projects/project4_huffman_tree/BinaryNode.java
@@ -0,0 +1,100 @@
+
+public class BinaryNode<T> implements BinaryNodeInterface<T>
+{
+	private T data;
+	private BinaryNode<T> left;
+	private BinaryNode<T> right;
+	
+	public BinaryNode(T dataPortion, BinaryNode<T> leftChild, BinaryNode<T> rightChild)
+	{
+		data = dataPortion;
+		left = leftChild;
+		right = rightChild;
+	}
+	
+	public BinaryNode(T dataPortion)
+	{
+		this(dataPortion, null, null);
+	}
+	
+	public BinaryNode()
+	{
+		this(null);
+	}
+	
+	public T getData()
+	{
+		return data;
+	}
+	
+	public void setData(T newData)
+	{
+		data = newData;
+	}
+	
+	public BinaryNodeInterface<T> getLeftChild()
+	{
+		return left;
+	}
+	
+	public BinaryNodeInterface<T> getRightChild()
+	{
+		return right;
+	}
+	
+	public void setLeftChild(BinaryNodeInterface<T> leftChild)
+	{
+		left = (BinaryNode<T>) leftChild;
+	}
+	
+	public void setRightChild(BinaryNodeInterface<T> rightChild)
+	{
+		right = (BinaryNode<T>) rightChild;
+	}
+	
+	public boolean hasLeftChild()
+	{
+		return left != null;
+	}
+	
+	public boolean hasRightChild()
+	{
+		return right != null;
+	}
+	
+	public boolean isLeaf()
+	{
+		return left == null && right == null;
+	}
+	
+	public int getNumberOfNodes()
+	{
+		int leftNumber = 0;
+		int rightNumber = 0;
+		
+		if(left != null)
+			leftNumber = left.getNumberOfNodes();
+		
+		if(right != null)
+			rightNumber = right.getNumberOfNodes();
+		
+		return 1 + leftNumber + rightNumber;
+	}
+	
+	public int getHeight()
+	{
+		return getHeight(this);
+	}
+	
+	private int getHeight(BinaryNode<T> node)
+	{
+		int height = 0;
+		
+		if(node != null)
+		{
+			height = 1 + Math.max(getHeight(node.left), getHeight(node.right));
+		}
+		
+		return height;
+	}
+}
diff --git a/projects/project4_huffman_tree/BinaryNodeInterface.java b/projects/project4_huffman_tree/BinaryNodeInterface.java
new file mode 100644
index 0000000..f3ac7c1
--- /dev/null
+++ b/projects/project4_huffman_tree/BinaryNodeInterface.java
@@ -0,0 +1,15 @@
+
+public interface BinaryNodeInterface<T>
+{
+	public T getData();
+	public void setData(T newData);
+	public BinaryNodeInterface<T> getLeftChild();
+	public BinaryNodeInterface<T> getRightChild();
+	public void setLeftChild(BinaryNodeInterface<T> leftChild);
+	public void setRightChild(BinaryNodeInterface<T> rightChild);
+	public boolean hasLeftChild();
+	public boolean hasRightChild();
+	public boolean isLeaf();
+	public int getNumberOfNodes();
+	public int getHeight();
+}
diff --git a/projects/project4_huffman_tree/CompressDecompress.java b/projects/project4_huffman_tree/CompressDecompress.java
new file mode 100644
index 0000000..56b69e6
--- /dev/null
+++ b/projects/project4_huffman_tree/CompressDecompress.java
@@ -0,0 +1,189 @@
+/**
+ * It is okay to use ArrayList class but you are not allowed to use any other
+ * predefined class supplied by Java.
+ */
+import java.util.ArrayList;
+
+public class CompressDecompress
+{
+	/**
+	 * Get a string representing a Huffman tree where its root node is root
+	 * @param root the root node of a Huffman tree
+	 * @return a string representing a Huffman tree
+	 */
+	public static String getTreeString(final BinaryNodeInterface<Character> root)
+	{
+		String output = getTreeStringHelper(root);
+
+		return output;	// Do not forget to change this line!!!
+	}
+	private static String getTreeStringHelper(final BinaryNodeInterface<Character> root)
+	{
+		//System.out.println("\n finding ");
+		String output = "";
+		if(root != null)
+		{
+			if(root.hasLeftChild() || root.hasRightChild())
+			{
+				//System.out.println("Found non-leaf node Right:" + root.hasRightChild() + " left: " + root.hasLeftChild());
+				output += "I";
+				output += getTreeStringHelper(root.getLeftChild());
+				output += getTreeStringHelper(root.getRightChild());
+				return output;
+			}
+			else
+			{
+				//System.out.println("Found a leaf node!");
+				output += "L"+root.getData();
+				return output;
+			}
+		}
+		else
+		{
+			return output;
+		}
+		// if(root.hasLeftChild())
+		// {
+		// 	//System.out.println("Finding left child");
+		// 	output += getTreeStringHelper(root.getLeftChild());
+		// }
+		// if(root.hasRightChild())
+		// {
+		// 	//System.out.println("Finding right child");
+		// 	output += getTreeStringHelper(root.getRightChild());
+		// }
+		// return output;
+	}
+
+	/**
+	 * Compress the message using Huffman tree represented by treeString
+	 * @param root the root node of a Huffman tree
+	 * @param message the message to be compressed
+	 * @return a string representing compressed message.
+	 */
+	public static String compress(final BinaryNodeInterface<Character> root, final String message)
+	{
+		// TO DO
+		//System.out.println("Got tree: " + getTreeString(root));
+		return compressHelper(root,message);
+		//return "";	// Do not forget to change this line!!!
+	}
+	private static String compressHelper(final BinaryNodeInterface<Character> root, final String message)
+	{
+		String output = "";
+		if(message.isEmpty())
+		{
+			return output;
+		}
+		else
+		{
+			output += getStringForChar(root,message.charAt(0));
+			output += compressHelper(root,message.substring(1));
+			return output;
+		}
+	}
+	private static String getStringForChar(BinaryNodeInterface<Character> root, char c)
+	{
+		return getStringForCharHelper(root,c,"");
+	}
+	private static String getStringForCharHelper(BinaryNodeInterface<Character> root,char c, String p)
+	{
+		if(root == null)
+			return "";
+		if(root.getData() != null && root.getData().equals(new Character(c)))
+		{
+			return p;
+		}
+		String output = "";
+		if(root.hasLeftChild())
+		{
+			output = getStringForCharHelper(root.getLeftChild(),c,p+"0");
+		}
+		if(root.hasRightChild() && output == "")
+		{
+			output = getStringForCharHelper(root.getRightChild(),c,p+"1");
+		}
+		return output;
+	}
+	/**
+	 * Decompress the message using Huffman tree represented by treeString
+	 * @param treeString the string represents the Huffman tree of the
+	 * compressed message
+	 * @param message the compressed message to be decompressed
+	 * @return a string representing decompressed message
+	 */
+	public static String decompress(final String treeString, final String message)
+	{
+		//First, create a tree out of treeString
+		BinaryNode<Character> node = getTreeFor(treeString);
+		//Then find the output from this string
+		String output = "";
+		for(int i = 0; i < message.length();)
+		{
+			BinaryNodeInterface tmp = node;
+			while(!tmp.isLeaf())
+			{
+				if(message.charAt(i) == '0')
+				{
+					tmp = tmp.getLeftChild();
+				}
+				else if(message.charAt(i) == '1')
+				{
+					tmp = tmp.getRightChild();
+				}
+				i++;
+			}
+			output += tmp.getData();
+		}
+		return output;	// Do not forget to change this line!!!
+	}
+	private static BinaryNode<Character> getTreeFor(String pre)
+	{
+		if(pre.isEmpty())
+		{
+			return null;
+		}
+		char type = pre.charAt(0);
+		BinaryNode<Character> root = new BinaryNode<Character>(null,null,null);
+		if(type == 'I')
+		{
+			int length = 0;
+			if(!root.hasLeftChild())
+			{
+				length = treeLength(pre.substring(1));
+				String lefttree = pre.substring(1,length+1);
+				root.setLeftChild(getTreeFor(lefttree));
+			}
+			if(!root.hasRightChild())
+			{
+				String righttree = pre.substring(length+1);
+				root.setRightChild(getTreeFor(righttree));
+			}
+			return root;
+		}
+		else if(type == 'L')
+		{
+			root.setData(pre.charAt(1));
+			return root;
+		}
+		return root;
+	}
+	private static int treeLength(String s) //Figure out how long the string should be
+	{
+		int output = 1;
+		for(int i = 0; i < output; i++)
+		{
+			if(s.charAt(i) == 'I')
+			{
+				output += 2;
+			}
+			if(s.charAt(i) == 'L')
+			{
+				output += 1;
+				i++;
+			}
+		}
+		return output;
+	}
+	
+}
diff --git a/projects/project4_huffman_tree/CompressDecompressGUI.java b/projects/project4_huffman_tree/CompressDecompressGUI.java
new file mode 100644
index 0000000..20ecbd0
--- /dev/null
+++ b/projects/project4_huffman_tree/CompressDecompressGUI.java
@@ -0,0 +1,217 @@
+import java.awt.BorderLayout;
+import java.awt.Color;
+import java.awt.Font;
+import java.awt.GridLayout;
+import java.awt.event.KeyEvent;
+import java.awt.event.KeyListener;
+
+import javax.swing.JFrame;
+import javax.swing.JLabel;
+import javax.swing.JPanel;
+import javax.swing.JScrollPane;
+import javax.swing.JTextArea;
+import javax.swing.border.TitledBorder;
+
+@SuppressWarnings("serial")
+public class CompressDecompressGUI extends JFrame
+{
+	JPanel inputTextAreaPanel;
+	JPanel outputTreePanel;
+	JPanel outputCompressPanel;
+	JPanel outputDecompressPanel;
+	JPanel inputTextPanel;
+	JPanel treeTextPanel;
+	JPanel outputTextPanel;
+	
+	JTextArea inputTextArea;
+	JTextArea outputTreeArea;
+	JTextArea outputCompressArea;
+	JTextArea outputDecompressArea;
+	
+	JScrollPane inputTextPane;
+	JScrollPane outputTreePane;
+	JScrollPane compressPane;
+	JScrollPane decompressPane;
+	
+	JLabel inputNumberOfCharactersLabel;
+	JLabel inputNumberOfBytesLabel;
+	JLabel treeNumberOfCharactersLabel;
+	JLabel treeNumberOfBytesLabel;
+	JLabel outputNumberOfBytesLabel;
+	JLabel outputTotalNumberOfBytesLabel;
+	JLabel compressLabel;
+	KeyListener kListener;
+	
+	public CompressDecompressGUI()
+	{
+		setLayout(new GridLayout(2,2));
+		
+		setTextAreasAndPanels();
+	}
+
+	private void setTextAreasAndPanels()
+	{
+		Font monoFont = new Font("Monospaced", Font.BOLD, 14);
+		
+		// Input Text
+		
+		inputTextAreaPanel = new JPanel();
+		inputTextAreaPanel.setBackground(Color.WHITE);
+		inputTextAreaPanel.setLayout(new BorderLayout());
+		inputTextAreaPanel.setBorder(new TitledBorder("Type Your Message Here"));
+		
+		inputTextArea = new JTextArea();
+		inputTextArea.setEditable(true);
+		inputTextArea.setLineWrap(true);
+		inputTextArea.setFont(monoFont);
+		kListener = new InputKeyEvent();
+		inputTextArea.addKeyListener(kListener);
+		inputTextPane = new JScrollPane(inputTextArea);
+		inputTextAreaPanel.add(inputTextPane);
+		inputTextPanel = new JPanel();
+		inputTextPanel.setLayout(new GridLayout(2,1));
+		inputNumberOfCharactersLabel = new JLabel("Number of Characters: 0");
+		inputNumberOfBytesLabel = new JLabel("Number of Bytes: 0");
+		inputTextPanel.add(inputNumberOfCharactersLabel);
+		inputTextPanel.add(inputNumberOfBytesLabel);
+		inputTextAreaPanel.add(inputTextPanel, BorderLayout.SOUTH);
+		
+		// Output Tree
+		
+		outputTreePanel = new JPanel();
+		outputTreePanel.setBackground(Color.WHITE);
+		outputTreePanel.setLayout(new BorderLayout());
+		outputTreePanel.setBorder(new TitledBorder("Tree Structure"));
+		outputTreeArea = new JTextArea();
+		outputTreeArea.setEditable(false);
+		outputTreeArea.setLineWrap(true);
+		outputTreeArea.setFont(monoFont);
+		outputTreePane = new JScrollPane(outputTreeArea);
+		outputTreePanel.add(outputTreePane);
+		treeTextPanel = new JPanel();
+		treeTextPanel.setLayout(new GridLayout(2,1));
+		treeNumberOfCharactersLabel = new JLabel("Number of Characters: 0");
+		treeNumberOfBytesLabel = new JLabel("Number of Bytes: 0");
+		treeTextPanel.add(treeNumberOfCharactersLabel);
+		treeTextPanel.add(treeNumberOfBytesLabel);
+		outputTreePanel.add(treeTextPanel, BorderLayout.SOUTH);
+		
+		// Compressed Output
+		
+		outputCompressPanel = new JPanel();
+		outputCompressPanel.setBackground(Color.WHITE);
+		outputCompressPanel.setLayout(new BorderLayout());
+		outputCompressPanel.setBorder(new TitledBorder("Compressed Message"));
+		outputCompressArea = new JTextArea();
+		outputCompressArea.setEditable(false);
+		outputCompressArea.setLineWrap(true);
+		outputCompressArea.setFont(monoFont);
+		compressPane = new JScrollPane(outputCompressArea);
+		outputCompressPanel.add(compressPane);
+		outputTextPanel = new JPanel();
+		outputTextPanel.setLayout(new GridLayout(3,1));
+		outputNumberOfBytesLabel = new JLabel("Number of Bytes: 0");
+		outputTotalNumberOfBytesLabel = new JLabel("Total Number of Bytes: 0");
+		compressLabel = new JLabel("Compressed to 100% of the original size");
+		outputTextPanel.add(outputNumberOfBytesLabel);
+		outputTextPanel.add(outputTotalNumberOfBytesLabel);
+		outputTextPanel.add(compressLabel);
+		outputCompressPanel.add(outputTextPanel, BorderLayout.SOUTH);
+		
+		// Decompress Output
+		
+		outputDecompressPanel = new JPanel();
+		outputDecompressPanel.setBackground(Color.WHITE);
+		outputDecompressPanel.setLayout(new BorderLayout());
+		outputDecompressPanel.setBorder(new TitledBorder("Decompress Message"));
+		outputDecompressArea = new JTextArea();
+		outputDecompressArea.setEditable(false);
+		outputDecompressArea.setLineWrap(true);
+		outputDecompressArea.setFont(monoFont);
+		decompressPane = new JScrollPane(outputDecompressArea);
+		outputDecompressPanel.add(decompressPane);
+		
+		add(inputTextAreaPanel);
+		add(outputTreePanel);
+		add(outputCompressPanel);
+		add(outputDecompressPanel);
+	}
+	
+	private class InputKeyEvent implements KeyListener
+	{
+		public void keyPressed(KeyEvent arg0)
+		{
+		}
+
+		public void keyReleased(KeyEvent arg0)
+		{
+			/* Obtain the string from inputTextArea and
+			 * calculate the number of bytes from its length.
+			 * Assuming that we use unicode which is two bytes
+			 * per character.
+			 */
+			String str = inputTextArea.getText();
+			
+			int inputStringLength = str.length();
+			int inputStringBytes = str.length() * 2;
+			inputNumberOfCharactersLabel.setText("Number of Characters: " + inputStringLength);
+			inputNumberOfBytesLabel.setText("Number of Bytes: " + inputStringBytes);
+			
+			/* Generate Huffman tree from the input string
+			 * and obtain the root node of the Huffman tree.			
+			 */
+			HuffmanTree ht = new HuffmanTree(str);
+			BinaryNodeInterface<Character> root = ht.getRootNode();
+			
+			/* Generate a string representing the Huffman tree rooted
+			 * at root and display the string on outputTreeArea.
+			 */
+			String treeString = CompressDecompress.getTreeString(root);
+			outputTreeArea.setText(treeString);
+			
+			int treeStringLength = treeString.length();
+			int treeStringBytes = treeStringLength * 2;
+			
+			treeNumberOfCharactersLabel.setText("Number of Characters: " + treeStringLength);
+			treeNumberOfBytesLabel.setText("Number of Bytes: " + treeStringBytes);
+			
+			/* Compress the input string (str) using the Huffman tree rooted at
+			 * root. The result is a new string containing just 0s and 1s. Then
+			 * display the result on outputCompressArea.
+			 */
+			String compressedString = CompressDecompress.compress(root, str);
+			outputCompressArea.setText(compressedString);
+			int numBytes = compressedString.length() / 8;
+			if(compressedString.length() % 8 != 0)
+			{
+				numBytes++;
+			}
+			outputNumberOfBytesLabel.setText("Number of Bytes: " +  numBytes);
+			outputTotalNumberOfBytesLabel.setText("Total Number of Bytes: " + (numBytes + treeStringBytes));
+			float percentCompression = (float) (numBytes + treeStringBytes) / inputStringBytes * 100; 
+			compressLabel.setText("Compressed to " + String.format("%.2f", percentCompression) + "% of the original size");
+			
+			/* Decompress the compressed string (compressedString) using
+			 * the string representing the Huffman tree (treeString). The
+			 * result is a new string which should be exactly the same
+			 * as the input string (str). Then display the result string
+			 * on outputDecompressArea.
+			 */
+			String decompressedString = CompressDecompress.decompress(treeString, compressedString);
+			outputDecompressArea.setText(decompressedString);
+		}
+
+		public void keyTyped(KeyEvent arg0)
+		{
+		}
+	}
+	
+	public static void main(String[] args)
+	{
+		JFrame frame = new CompressDecompressGUI();
+		frame.setSize(700,600);
+		frame.setTitle("Huffman Tree - Compression / Decompression");
+		frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
+		frame.setVisible(true);
+	}
+}
\ No newline at end of file
diff --git a/projects/project4_huffman_tree/CompressDecompressTester.java b/projects/project4_huffman_tree/CompressDecompressTester.java
new file mode 100644
index 0000000..eeae7ca
--- /dev/null
+++ b/projects/project4_huffman_tree/CompressDecompressTester.java
@@ -0,0 +1,159 @@
+
+public class CompressDecompressTester
+{
+	public static void main(String[] args)
+	{
+		int numErrors = 0;
+		
+		// Test getTreeString()
+		
+		System.out.print("Testing the method getTreeString() with an empty tree: ");
+		if(CompressDecompress.getTreeString(null) != "")
+		{
+			System.out.println("FAIL");
+			System.out.println("CompressDecompress.getTreeString(null) shoudl return an empty string (\"\").");
+			System.out.println("But your method getTreeString(null) returns " + CompressDecompress.getTreeString(null) + ".\n");
+			numErrors++;
+		}
+		else
+		{
+			System.out.println("PASS\n");
+		}
+		
+		System.out.println("A two node tree was constructed (from nodes) using the following statements:");
+		System.out.println("   BinaryNodeInterface<Character> nodeA = new BinaryNode<Character>('a');");
+		System.out.println("   BinaryNodeInterface<Character> twoNodeTreeRoot = new BinaryNode<Character>(null, (BinaryNode<Character>) nodeA, null);");
+		System.out.print("Testing the method getTreeString() with two node tree: ");
+		BinaryNodeInterface<Character> nodeA = new BinaryNode<Character>('a');
+		BinaryNodeInterface<Character> twoNodeTreeRoot = new BinaryNode<Character>(null, (BinaryNode<Character>) nodeA, null);
+		if(!CompressDecompress.getTreeString(twoNodeTreeRoot).equals("ILa"))
+		{
+			System.out.println("FAIL");
+			System.out.println("The method getTreeString(twoNodeTreeRoot) should return ILa.");
+			System.out.println("But your method getTreeString(twoNodeTreeRoot) returns " + CompressDecompress.getTreeString(twoNodeTreeRoot) + ".\n");
+			numErrors++;
+		}
+		else
+		{
+			System.out.println("PASS\n");
+		}
+		
+		System.out.println("A nine node tree was constructed (from nodes) using the following statements:");
+		System.out.println("   BinaryNodeInterface<Character> nodeA = new BinaryNode<Character>('a');");
+		System.out.println("   BinaryNodeInterface<Character> nodeB = new BinaryNode<Character>('b');");
+		System.out.println("   BinaryNodeInterface<Character> nodeC = new BinaryNode<Character>('c');");
+		System.out.println("   BinaryNodeInterface<Character> nodeD = new BinaryNode<Character>('d');");
+		System.out.println("   BinaryNodeInterface<Character> nodeE = new BinaryNode<Character>('e');");
+		System.out.println("   BinaryNodeInterface<Character> nodeAB = new BinaryNode<Character>(null, (BinaryNode<Character>) nodeA, (BinaryNode<Character>) nodeB);");
+		System.out.println("   BinaryNodeInterface<Character> nodeCD = new BinaryNode<Character>(null, (BinaryNode<Character>) nodeC, (BinaryNode<Character>) nodeD);");
+		System.out.println("   BinaryNodeInterface<Character> nodeABCD = new BinaryNode<Character>(null, (BinaryNode<Character>) nodeAB, (BinaryNode<Character>) nodeCD);");
+		System.out.println("   BinaryNodeInterface<Character> nodeABCDE = new BinaryNode<Character>(null, (BinaryNode<Character>) nodeABCD, (BinaryNode<Character>) nodeE);");
+		System.out.print("Testing the method getTreeString() with nine node tree: ");
+		BinaryNodeInterface<Character> nodeB = new BinaryNode<Character>('b');
+		BinaryNodeInterface<Character> nodeC = new BinaryNode<Character>('c');
+		BinaryNodeInterface<Character> nodeD = new BinaryNode<Character>('d');
+		BinaryNodeInterface<Character> nodeE = new BinaryNode<Character>('e');
+		BinaryNodeInterface<Character> nodeAB = new BinaryNode<Character>(null, (BinaryNode<Character>) nodeA, (BinaryNode<Character>) nodeB);
+		BinaryNodeInterface<Character> nodeCD = new BinaryNode<Character>(null, (BinaryNode<Character>) nodeC, (BinaryNode<Character>) nodeD);
+		BinaryNodeInterface<Character> nodeABCD = new BinaryNode<Character>(null, (BinaryNode<Character>) nodeAB, (BinaryNode<Character>) nodeCD);
+		BinaryNodeInterface<Character> nodeABCDE = new BinaryNode<Character>(null, (BinaryNode<Character>) nodeABCD, (BinaryNode<Character>) nodeE);
+		if(!CompressDecompress.getTreeString(nodeABCDE).equals("IIILaLbILcLdLe"))
+		{
+			System.out.println("FAIL");
+			System.out.println("The method getTreeString(nodeABCDE) should return IIILaLbILcLdLe.");
+			System.out.println("But your method getTreeString(nodeABCDE) returns " + CompressDecompress.getTreeString(nodeABCDE) + ".\n");
+			numErrors++;
+		}
+		else
+		{
+			System.out.println("PASS\n");
+		}
+		
+		// Test compress()
+		
+		System.out.print("Testing the method compress with an empty input string: ");
+		if(!CompressDecompress.compress(null, "").equals(""))
+		{
+			System.out.println("FAIL");
+			System.out.println("CompressDecompress.compress(null,\"\") shoudl return an empty string (\"\").");
+			System.out.println("But your method compress(null,\"\") returns " + CompressDecompress.compress(null,"") + ".\n");
+			numErrors++;
+		}
+		else
+		{
+			System.out.println("PASS");
+		}
+		
+		System.out.print("Testing the method compress using two node tree from previous test and the input string is \"aaaa\": ");
+		if(!CompressDecompress.compress(twoNodeTreeRoot, "aaaa").equals("0000"))
+		{
+			System.out.println("FAIL");
+			System.out.println("CompressDecompress.compress(twoNodeTreeRoot,\"aaaa\") should return \"0000\".");
+			System.out.println("But your method compress(twoNodeTreeRoot,\"aaaa\") returns " + CompressDecompress.compress(twoNodeTreeRoot,"aaaa") + ".");
+			numErrors++;
+		}
+		else
+		{
+			System.out.println("PASS");
+		}
+
+		System.out.print("Testing the method compress using nine node tree from previous test and the input string is \"abcde\": ");
+		if(!CompressDecompress.compress(nodeABCDE, "abcde").equals("0000010100111"))
+		{
+			System.out.println("FAIL");
+			System.out.println("CompressDecompress.compress(nodeABCDE,\"abcde\") should return \"0000010100111\".");
+			System.out.println("But your method compress(twoNodeTreeRoot,\"abcde\") returns " + CompressDecompress.compress(nodeABCDE,"abcde") + ".");
+			numErrors++;
+		}
+		else
+		{
+			System.out.println("PASS");
+		}
+		
+		// Test decompress()
+		
+		System.out.println();
+		
+		System.out.print("Testing the method decompress with empty tree and empty string: ");
+		if(!CompressDecompress.decompress("", "").equals(""))
+		{
+			System.out.println("FAIL");
+			System.out.println("CompressDecompress.decompress(\"\", \"\") should return an empty string (\"\").");
+			System.out.println("But your method decompress(\"\", \"\") returns " + CompressDecompress.decompress("", "") + ".");
+			numErrors++;
+		}
+		else
+		{
+			System.out.println("PASS");
+		}
+		
+		System.out.print("Testing the method decompress with the tree string IIILaLbILcLdLe and input string 1011010001000: ");
+		if(!CompressDecompress.decompress("IIILaLbILcLdLe", "1011010001000").equals("edcba"))
+		{
+			System.out.println("FAIL");
+			System.out.println("CompressDecompress.decompress(\"IIILaLbILcLdLe\", \"1011010001000\" should return edcba.");
+			System.out.println("But your method decompress(\"IIILaLbILcLdLe\", \"1011010001000\" returns " + CompressDecompress.decompress("IIILaLbILcLdLe", "1011010001000") + ".");
+			numErrors++;
+		}
+		else
+		{
+			System.out.println("PASS");
+		}
+		
+		System.out.println();
+
+		if(numErrors == 0)
+		{
+			System.out.println("Your CompressDecompress works perfectly (I guess). Here is your reward:\n");
+			String jokeTree = "IIILeILaIIL\nILWIL?LvILgLkIILuLoILnLsIIIIIL,LbIL\"LfLtIILrLlIIILTIILILSILALmLyIIL.L'IIILYLGIL!LHLwIIILdILpLcILhLiL ";
+			String jokeCompressed = "1011001101111100110101101100111110010010010010001010011101111100111101100001101100110001110111100101001100000001101001111110110111111011110010100110001011011101101100011101110100011011000000101001110010111100110100000000111001001101100011100100110010110011101000010100111110010010010101101010111111010011001011101010110111001011110001110101001001111101010110111101100001011111111100001110110011110001011100111101100011010000111100011110111010001111001111011110010100110000000110100111100100111001111011110000011110001000110101101000010100000101110111000111101101010101001110011100001001111100111010001010010011011010001000110000110010110001101000011101111001010011000000011010011110101011011110011101000011110000111011001111000111101000001100101010111011000011110000011110001000110101101011011101010001111011001001111011111001001111110111100101001100010110111011011000111011101010100100101111101111000000100000111001011110000100000100100100111011100011010010101111001110110111010010101111110010010010101101010001100011101001100101110101011011111010000101001111000011101100111100010111001111011001011101000011110010101010100111111101011000111000111110010101011010111111010000101001111100111010101011001110100000111111001001101100011101110010110111100010000011110111011011110000101010011111001100100110111110100010001101110001110010011010110110011101011011011000111011110110101010100111101111100100110100110111011011100100010001100001100101100011010000111100011110111010001111001111011110010100110000000110100111110100000011111001001010110110000111100000111100010101111001010101011100011111001111010010111011110011000101111010111101111011000101001111100111010101011001110100000111111110010101000101100001001010000110101101101111101111101010100101011100001101011101100111111010001000110111000111100011110111001111101101010101001011100100010";
+			
+			System.out.println(CompressDecompress.decompress(jokeTree, jokeCompressed));
+		}
+		else
+		{
+			System.out.println("There are " + numErrors + " errors in your CompressDecompress.java");
+			System.out.println("Fix your code and try again.");
+		}
+	}
+}
diff --git a/projects/project4_huffman_tree/HuffmanTree.java b/projects/project4_huffman_tree/HuffmanTree.java
new file mode 100644
index 0000000..dcbb0b4
--- /dev/null
+++ b/projects/project4_huffman_tree/HuffmanTree.java
@@ -0,0 +1,127 @@
+import java.util.ArrayList;
+
+public class HuffmanTree
+{
+	private String str;
+	private BinaryNodeInterface<Character> root;
+	private ArrayList<Character> charList;
+	private ArrayList<Integer> freqList;
+	
+	public HuffmanTree(String aString)
+	{
+		str = aString;
+		root = null;
+		
+		generateFrequencyList();
+		generateHuffmanTree();
+	}
+	
+	public BinaryNodeInterface<Character> getRootNode()
+	{
+		return root;
+	}
+	
+	private void generateHuffmanTree()
+	{
+		if(str == null || str.equals(""))
+		{
+			root = null;
+			return;
+		}
+		
+		MinHeapInterface<BinaryNodeFrequency<Character>> heap = new MinHeap<BinaryNodeFrequency<Character>>();
+		
+		while(!charList.isEmpty())
+		{
+			char c = charList.remove(0);
+			int freq = freqList.remove(0);
+			
+			BinaryNodeInterface<Character> newNode = new BinaryNode<Character>(c);
+			BinaryNodeFrequency<Character> newBNode = new BinaryNodeFrequency<Character>(newNode, freq);
+			heap.add(newBNode);
+		}
+		
+		while(!heap.isEmpty())
+		{
+			BinaryNodeFrequency<Character> left = heap.removeMin();
+			if(heap.isEmpty())
+			{
+				root = left.node;
+				break;
+			}
+			
+			BinaryNodeFrequency<Character> right = heap.removeMin();
+			
+			int newFrequency = left.frequency + right.frequency;
+			BinaryNodeInterface<Character> newNode = new BinaryNode<Character>(null, (BinaryNode<Character>) left.node, (BinaryNode<Character>) right.node);
+			BinaryNodeFrequency<Character> newBNode = new BinaryNodeFrequency<Character>(newNode, newFrequency);
+			heap.add(newBNode);
+		}
+		
+		if(root.isLeaf())
+		{
+			BinaryNodeInterface<Character> newNode = new BinaryNode<Character>(null, (BinaryNode<Character>) root, null);
+			root = newNode;
+		}
+		
+	}
+	
+	private void generateFrequencyList()
+	{
+		charList = new ArrayList<Character>();
+		freqList = new ArrayList<Integer>();
+		
+		int strLength = str.length();
+		
+		for(int i = 0; i < strLength; i++)
+		{
+			char c = str.charAt(i);
+			int charIndex = charList.indexOf(c);
+			
+			if(charIndex != -1)
+			{
+				freqList.set(charIndex, freqList.get(charIndex) + 1);
+			}
+			else
+			{
+				charList.add(c);
+				freqList.add(1);
+			}
+		}
+	}
+	
+	/* The min heap requires the object to implement comparable. According
+	 * to the algorithm, we need to add BinaryNode into the min heap. However,
+	 * BinaryNodes are not comparable, so we need a new type of object that
+	 * can be used to represent a BinaryNode that implements Comparable.
+	 * In this situation, our BinaryNode will be used to store a character.
+	 * To compare, we compare the frequency of the character. 
+	 */
+	private class BinaryNodeFrequency<T> implements Comparable<BinaryNodeFrequency<T>>
+	{
+		private BinaryNodeInterface<T> node;
+		private int frequency;
+		
+		private BinaryNodeFrequency(BinaryNodeInterface<T> aNode, int aFrequency)
+		{
+			node = aNode;
+			frequency = aFrequency;
+		}
+		
+		public int compareTo(BinaryNodeFrequency<T> otherBNF)
+		{
+			if(frequency < otherBNF.frequency)
+			{
+				return -1;
+			}
+			else if(frequency > otherBNF.frequency)
+			{
+				return 1;
+			}
+			else
+			{
+				return 0;
+			}
+		}
+	}
+}
diff --git a/projects/project4_huffman_tree/MinHeap.java b/projects/project4_huffman_tree/MinHeap.java
new file mode 100644
index 0000000..3b46287
--- /dev/null
+++ b/projects/project4_huffman_tree/MinHeap.java
@@ -0,0 +1,132 @@
+
+public class MinHeap<T extends Comparable<? super T>> implements MinHeapInterface<T>
+{
+	private T[] heap;
+	private int lastIndex;
+	private static final int DEFAULT_INITIAL_CAPACITY = 25;
+	
+	public MinHeap()
+	{
+		this(DEFAULT_INITIAL_CAPACITY);
+	}
+	
+	public MinHeap(int initialCapacity)
+	{
+		@SuppressWarnings("unchecked")
+		T[] tempHeap = (T[]) new Comparable[initialCapacity];
+		
+		heap = tempHeap;
+		lastIndex = 0;
+	}
+	
+	public void add(T newEntry)
+	{
+		lastIndex++;
+		ensureCapacity();
+		
+		int newIndex = lastIndex;
+		int parentIndex = newIndex / 2;
+		
+		while((parentIndex > 0) && newEntry.compareTo(heap[parentIndex]) < 0)
+		{
+			heap[newIndex] = heap[parentIndex];
+			newIndex = parentIndex;
+			parentIndex = newIndex / 2;
+		}
+		
+		heap[newIndex] = newEntry;
+	}
+
+	public T removeMin()
+	{
+		T root = null;
+		
+		if(!isEmpty())
+		{
+			root = heap[1];
+			heap[1] = heap[lastIndex];
+			lastIndex--;
+			reheap(1);
+		}
+		
+		return root;
+	}
+
+	public T getMin()
+	{
+		T root = null;
+		
+		if(!isEmpty())
+		{
+			root = heap[1];
+		}
+		
+		return root;
+	}
+
+	public boolean isEmpty()
+	{
+		return lastIndex < 1;
+	}
+
+	public int getSize()
+	{
+		return lastIndex;
+	}
+
+	public void clear()
+	{
+		for(int i = 0; i <= lastIndex; i++)
+		{
+			heap[i] = null;
+		}
+		
+		lastIndex = 0;
+	}
+
+	private void ensureCapacity()
+	{
+		if(heap.length == lastIndex)
+		{
+			@SuppressWarnings("unchecked")
+			T[] tempHeap = (T[]) new Comparable[heap.length * 2];
+			
+			for(int i = 0; i < lastIndex; i++)
+			{
+				tempHeap[i] = heap[i];
+			}
+			
+			heap = tempHeap;
+		}
+	}
+
+	private void reheap(int rootIndex)
+	{
+		boolean done = false;
+		T orphan = heap[rootIndex];
+		int leftChildIndex = rootIndex * 2;
+		
+		while(!done && (leftChildIndex <= lastIndex))
+		{
+			int smallerChildIndex = leftChildIndex;
+			int rightChildIndex = leftChildIndex + 1;
+			if((rightChildIndex <= lastIndex) && heap[rightChildIndex].compareTo(heap[smallerChildIndex]) < 0)
+			{
+				smallerChildIndex = rightChildIndex;
+			}
+			
+			if(orphan.compareTo(heap[smallerChildIndex]) > 0)
+			{
+				heap[rootIndex] = heap[smallerChildIndex];
+				rootIndex = smallerChildIndex;
+				leftChildIndex = rootIndex * 2;
+			}
+			else
+			{
+				done = true;
+			}
+		}
+		
+		heap[rootIndex] = orphan;
+	}
+}
diff --git a/projects/project4_huffman_tree/MinHeapInterface.java b/projects/project4_huffman_tree/MinHeapInterface.java
new file mode 100644
index 0000000..5728a67
--- /dev/null
+++ b/projects/project4_huffman_tree/MinHeapInterface.java
@@ -0,0 +1,11 @@
+
+public interface MinHeapInterface<T extends Comparable<? super T>>
+{
+	public void add(T newEntry);
+	public T removeMin();
+	public T getMin();
+	public boolean isEmpty();
+	public int getSize();
+	public void clear();
+
+}
diff --git a/projects/project4_huffman_tree/project4_huffman_tree.pdf b/projects/project4_huffman_tree/project4_huffman_tree.pdf
new file mode 100644
index 0000000..8a06f3c
--- /dev/null
+++ b/projects/project4_huffman_tree/project4_huffman_tree.pdf