From 89cdf3efb49335e7c07a68a5a64657eeec2288a6 Mon Sep 17 00:00:00 2001 From: Alexander Pickering Date: Mon, 6 Feb 2017 11:41:36 -0500 Subject: Inital commit --- projects/project4_huffman_tree/BinaryNode.java | 100 ++++++++++ .../project4_huffman_tree/BinaryNodeInterface.java | 15 ++ .../project4_huffman_tree/CompressDecompress.java | 189 ++++++++++++++++++ .../CompressDecompressGUI.java | 217 +++++++++++++++++++++ .../CompressDecompressTester.java | 159 +++++++++++++++ projects/project4_huffman_tree/HuffmanTree.java | 127 ++++++++++++ projects/project4_huffman_tree/MinHeap.java | 132 +++++++++++++ .../project4_huffman_tree/MinHeapInterface.java | 11 ++ .../project4_huffman_tree.pdf | Bin 0 -> 220769 bytes 9 files changed, 950 insertions(+) create mode 100644 projects/project4_huffman_tree/BinaryNode.java create mode 100644 projects/project4_huffman_tree/BinaryNodeInterface.java create mode 100644 projects/project4_huffman_tree/CompressDecompress.java create mode 100644 projects/project4_huffman_tree/CompressDecompressGUI.java create mode 100644 projects/project4_huffman_tree/CompressDecompressTester.java create mode 100644 projects/project4_huffman_tree/HuffmanTree.java create mode 100644 projects/project4_huffman_tree/MinHeap.java create mode 100644 projects/project4_huffman_tree/MinHeapInterface.java create mode 100644 projects/project4_huffman_tree/project4_huffman_tree.pdf (limited to 'projects/project4_huffman_tree') 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 implements BinaryNodeInterface +{ + private T data; + private BinaryNode left; + private BinaryNode right; + + public BinaryNode(T dataPortion, BinaryNode leftChild, BinaryNode 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 getLeftChild() + { + return left; + } + + public BinaryNodeInterface getRightChild() + { + return right; + } + + public void setLeftChild(BinaryNodeInterface leftChild) + { + left = (BinaryNode) leftChild; + } + + public void setRightChild(BinaryNodeInterface rightChild) + { + right = (BinaryNode) 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 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 +{ + public T getData(); + public void setData(T newData); + public BinaryNodeInterface getLeftChild(); + public BinaryNodeInterface getRightChild(); + public void setLeftChild(BinaryNodeInterface leftChild); + public void setRightChild(BinaryNodeInterface 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 root) + { + String output = getTreeStringHelper(root); + + return output; // Do not forget to change this line!!! + } + private static String getTreeStringHelper(final BinaryNodeInterface 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 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 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 root, char c) + { + return getStringForCharHelper(root,c,""); + } + private static String getStringForCharHelper(BinaryNodeInterface 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 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 getTreeFor(String pre) + { + if(pre.isEmpty()) + { + return null; + } + char type = pre.charAt(0); + BinaryNode root = new BinaryNode(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 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 nodeA = new BinaryNode('a');"); + System.out.println(" BinaryNodeInterface twoNodeTreeRoot = new BinaryNode(null, (BinaryNode) nodeA, null);"); + System.out.print("Testing the method getTreeString() with two node tree: "); + BinaryNodeInterface nodeA = new BinaryNode('a'); + BinaryNodeInterface twoNodeTreeRoot = new BinaryNode(null, (BinaryNode) 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 nodeA = new BinaryNode('a');"); + System.out.println(" BinaryNodeInterface nodeB = new BinaryNode('b');"); + System.out.println(" BinaryNodeInterface nodeC = new BinaryNode('c');"); + System.out.println(" BinaryNodeInterface nodeD = new BinaryNode('d');"); + System.out.println(" BinaryNodeInterface nodeE = new BinaryNode('e');"); + System.out.println(" BinaryNodeInterface nodeAB = new BinaryNode(null, (BinaryNode) nodeA, (BinaryNode) nodeB);"); + System.out.println(" BinaryNodeInterface nodeCD = new BinaryNode(null, (BinaryNode) nodeC, (BinaryNode) nodeD);"); + System.out.println(" BinaryNodeInterface nodeABCD = new BinaryNode(null, (BinaryNode) nodeAB, (BinaryNode) nodeCD);"); + System.out.println(" BinaryNodeInterface nodeABCDE = new BinaryNode(null, (BinaryNode) nodeABCD, (BinaryNode) nodeE);"); + System.out.print("Testing the method getTreeString() with nine node tree: "); + BinaryNodeInterface nodeB = new BinaryNode('b'); + BinaryNodeInterface nodeC = new BinaryNode('c'); + BinaryNodeInterface nodeD = new BinaryNode('d'); + BinaryNodeInterface nodeE = new BinaryNode('e'); + BinaryNodeInterface nodeAB = new BinaryNode(null, (BinaryNode) nodeA, (BinaryNode) nodeB); + BinaryNodeInterface nodeCD = new BinaryNode(null, (BinaryNode) nodeC, (BinaryNode) nodeD); + BinaryNodeInterface nodeABCD = new BinaryNode(null, (BinaryNode) nodeAB, (BinaryNode) nodeCD); + BinaryNodeInterface nodeABCDE = new BinaryNode(null, (BinaryNode) nodeABCD, (BinaryNode) 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 root; + private ArrayList charList; + private ArrayList freqList; + + public HuffmanTree(String aString) + { + str = aString; + root = null; + + generateFrequencyList(); + generateHuffmanTree(); + } + + public BinaryNodeInterface getRootNode() + { + return root; + } + + private void generateHuffmanTree() + { + if(str == null || str.equals("")) + { + root = null; + return; + } + + MinHeapInterface> heap = new MinHeap>(); + + while(!charList.isEmpty()) + { + char c = charList.remove(0); + int freq = freqList.remove(0); + + BinaryNodeInterface newNode = new BinaryNode(c); + BinaryNodeFrequency newBNode = new BinaryNodeFrequency(newNode, freq); + heap.add(newBNode); + } + + while(!heap.isEmpty()) + { + BinaryNodeFrequency left = heap.removeMin(); + if(heap.isEmpty()) + { + root = left.node; + break; + } + + BinaryNodeFrequency right = heap.removeMin(); + + int newFrequency = left.frequency + right.frequency; + BinaryNodeInterface newNode = new BinaryNode(null, (BinaryNode) left.node, (BinaryNode) right.node); + BinaryNodeFrequency newBNode = new BinaryNodeFrequency(newNode, newFrequency); + heap.add(newBNode); + } + + if(root.isLeaf()) + { + BinaryNodeInterface newNode = new BinaryNode(null, (BinaryNode) root, null); + root = newNode; + } + + } + + private void generateFrequencyList() + { + charList = new ArrayList(); + freqList = new ArrayList(); + + 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 implements Comparable> + { + private BinaryNodeInterface node; + private int frequency; + + private BinaryNodeFrequency(BinaryNodeInterface aNode, int aFrequency) + { + node = aNode; + frequency = aFrequency; + } + + public int compareTo(BinaryNodeFrequency 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> implements MinHeapInterface +{ + 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> +{ + 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 Binary files /dev/null and b/projects/project4_huffman_tree/project4_huffman_tree.pdf differ -- cgit v1.2.3-70-g09d2