Inital commitHEADmaster

1 files changed, 127 insertions, 0 deletions

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