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