1 files changed, 189 insertions, 0 deletions
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;
+	}
+	
+}