daily pastebin goal
45%
SHARE
TWEET

Untitled

a guest Apr 16th, 2018 66 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.util.ArrayList;
  2. import java.util.HashMap;
  3. import java.util.List;
  4. import java.util.Map;
  5. import java.util.Map.Entry;
  6. import java.util.Hashtable;
  7. import java.util.Set;
  8. import java.io.BufferedReader;
  9. import java.io.BufferedWriter;
  10. import java.io.File;
  11. import java.io.FileReader;
  12. import java.io.FileWriter;
  13. import java.io.IOException;
  14. import java.io.InputStream;
  15. import java.util.Scanner;
  16. import java.io.FileNotFoundException;
  17.  
  18. public class PA2{
  19.  
  20.     //PA #2 TODO: finds the smallest tree in a given forest, allowing for a single skip
  21.     //Finds the smallest tree (by weight) in the supplied forest.  
  22.     //Note that this function accepts a second optional parameter of an index to skip.  
  23.     //Use this index to allow your function to also find the 2nd smallest tree in the
  24.     //forest.
  25.     public static int findSmallestTree(List<HuffmanTree<Character>> forest)
  26.     {
  27.         return findSmallestTree(forest, -1); //find the real smallest
  28.     }
  29.     public static int findSmallestTree(List<HuffmanTree<Character>> forest, int index_to_ignore)
  30.     {
  31.         //iterate through every character , each tree in forest, look at weight
  32.         //smallest weight, record it, if you hit weight smaller
  33.         //record index number, if smaller
  34.         //current index, smallest index, weight
  35.         //Then loop if I!= index to ignore && list (i).getweight < smallest weight
  36.                 //then smallest index = I and smallest weight = list (i).get weight
  37.                 //Then when the loop is done return smallest index
  38.        
  39.         int smallest_weight = Integer.MAX_VALUE;
  40.         int smallest_index = -1;
  41.         for(int i = 0; i <forest.size(); i ++)
  42.         {
  43.             if(i!= index_to_ignore && forest.get(i).getWeight() < smallest_weight)
  44.             {
  45.                 smallest_index = i;
  46.                 smallest_weight = forest.get(i).getWeight();
  47.             }
  48.         }
  49.         return smallest_index;
  50.        
  51.  
  52.          //find the smallest except the index to ignore.
  53.     }
  54.  
  55.     //PA #2 TODO: Generates a Huffman character tree from the supplied text
  56.     //Builds a Huffman Tree from the supplied list of strings.
  57.     //This function implement's Huffman's Algorithm as specified in page
  58.     //435 of the book. 
  59.     public static HuffmanTree<Character> huffmanTreeFromText(List<String> data) {
  60.         //In order for your tree to be the same as mine, you must take care
  61.         //to do the following:
  62.         //1.    When merging the two smallest subtrees, make sure to place the
  63.         //      smallest tree on the left side!
  64.         //2.    Have the newly created tree take the spot of the smallest
  65.         //      tree in the forest(e.g. list.set(smallest_index, merged_tree) ).
  66.         //3.    Use list.remove(second_smallest_index) to remove
  67.         //      the other tree from the forest.
  68.         //HuffmanTree<Character> some_tree = new HuffmanTree<Character>('a', 5);
  69.         //HuffmanNode<Character> root = some_tree.getRoot();
  70.         //hashtable<character, int>
  71.         Hashtable<Character, Integer> dict = new Hashtable<Character, Integer>();
  72.    
  73.         for(String line: data)
  74.         {
  75.             for(Character c: line.toCharArray())
  76.             {
  77.                 if( dict.contains(c))
  78.                 {
  79.                     dict.put(c, dict.get(c)+1);
  80.                 }
  81.                 else
  82.                 {
  83.                     dict.put(c, 1);
  84.                 }
  85.             }
  86.         }
  87.         List<HuffmanTree<Character>> forest = new ArrayList<HuffmanTree<Character>>();
  88.         Set<Character> keys = dict.keySet();
  89.         for(Character key: keys)
  90.         {
  91.             HuffmanTree<Character> tree = new HuffmanTree<Character>(key, dict.get(key));
  92.             forest.add(tree);
  93.         }
  94.         int smallestIndex = -1;
  95.         int secondIndex = -1;
  96.         HuffmanTree<Character> tree = null;
  97.         while(forest.size() >1)
  98.         {
  99.             //1.    When merging the two smallest subtrees, make sure to place the
  100.             //      smallest tree on the left side!
  101.             //2.    Have the newly created tree take the spot of the smallest
  102.             //      tree in the forest(e.g. list.set(smallest_index, merged_tree) ).
  103.             //3.    Use list.remove(second_smallest_index) to remove
  104.             //      the other tree from the forest.
  105.             smallestIndex = findSmallestTree(forest);
  106.             secondIndex = findSmallestTree(forest, smallestIndex);
  107.             HuffmanTree<Character> smallest = forest.get(smallestIndex);
  108.             HuffmanTree<Character> secondSmallest = forest.get(secondIndex);
  109.             tree = new HuffmanTree<>(smallest, secondSmallest);
  110.             forest.set(smallestIndex, tree);
  111.             forest.remove(secondIndex);
  112.         }
  113.        
  114.         //note that root is a HuffmanNode instance. This type cast would only work
  115.         //if you are sure that root is not a leaf node.
  116.         //Vice versa, for this assignment, you might need to force type cast a HuffmanNode
  117.         //to a HuffmanLeafNode when you are sure that what you are getting is a HuffmanLeafNode.
  118.         //HuffmanInternalNode<Character> i_root = (HuffmanInternalNode<Character>)root;  
  119.         return tree;
  120.     }
  121.  
  122.  
  123.     //PA #2 TODO: Generates a Huffman character tree from the supplied encoding map
  124.     //NOTE: I used a recursive helper function to solve this!
  125.     public static HuffmanTree<Character> huffmanTreeFromMap(Map<Character, String> huffmanMap) {
  126.         //Generates a Huffman Tree based on the supplied Huffman Map.Recall that a
  127.         //Huffman Map contains a series of codes(e.g. 'a' = > 001).Each digit(0, 1)
  128.         //in a given code corresponds to a left branch for 0 and right branch for 1.
  129.        
  130.         //reccursion while something is still in the string
  131.         //if 1 get the right child
  132.         //create node, split value up, and take eah part in till done.
  133.         HuffmanTree tree = new HuffmanTree(new HuffmanInternalNode(null, null));
  134.         for(Character key: huffmanMap.keySet())
  135.         {
  136.             helper(tree.getRoot(), huffmanMap.get(key),key);
  137.         }
  138.        
  139.            
  140.         return tree;
  141.        
  142.     }
  143.  
  144.     //PA #2 TODO: Generates a Huffman encoding map from the supplied Huffman tree
  145.     //NOTE: I used a recursive helper function to solve this!
  146.     public static Map<Character, String> huffmanEncodingMapFromTree(HuffmanTree<Character> tree) {
  147.         //Generates a Huffman Map based on the supplied Huffman Tree.  Again, recall
  148.         //that a Huffman Map contains a series of codes(e.g. 'a' = > 001).Each digit(0, 1)
  149.         //in a given code corresponds to a left branch for 0 and right branch for 1.  
  150.         //As such, a given code represents a pre-order traversal of that bit of the
  151.         //tree.  I used recursion to solve this problem.
  152.        
  153.        
  154.         Map<Character, String> result = new HashMap<>();
  155.         helper2(tree.getRoot(), "", result);
  156.         return result;
  157.     }
  158.  
  159.     //PA #2 TODO: Writes an encoding map to file.  Needed for decompression.
  160.     public static void writeEncodingMapToFile(Map<Character, String> huffmanMap, String file_name) {
  161.         //Writes the supplied encoding map to a file.  My map file has one
  162.         //association per line (e.g. 'a' and 001).  Each association is separated by
  163.         //a sentinel value.  In my case, I went with a double pipe (||).
  164.         String newline = System.getProperty("line.separator");
  165.         File file = new File(file_name);
  166.         FileWriter fWriter = null;
  167.         BufferedWriter bWriter = null;
  168.         try
  169.         {
  170.             fWriter = new FileWriter(file);
  171.             bWriter = new BufferedWriter(fWriter);
  172.             for(Map.Entry<Character,String> entry: huffmanMap.entrySet())
  173.             {
  174.                 Character key = entry.getKey();
  175.                 String value = entry.getValue();
  176.                 bWriter.write(key + "||" + value + newline);
  177.             }
  178.         }catch(IOException e) {
  179.             e.printStackTrace();
  180.         }finally {
  181.             try {
  182.                 if(bWriter != null)
  183.                 {
  184.                     bWriter.close();
  185.                 }
  186.                 if(fWriter != null)
  187.                 {
  188.                     fWriter.close();
  189.                 }
  190.             }catch(IOException e) {
  191.                 e.printStackTrace();
  192.             }
  193.         }
  194.     }
  195.  
  196.     //PA #2 TODO: Reads an encoding map from a file.  Needed for decompression.
  197.     public static Map<Character, String> readEncodingMapFromFile(String file_name) throws FileNotFoundException {
  198.         //Creates a Huffman Map from the supplied file.Essentially, this is the
  199.         //inverse of writeEncodingMapToFile. Use String.split() function - note that
  200.         //the split() function takes a Regular Expression as an input, not a "string" itself.
  201.         //To separate based on "||", the argument for the function should be: split("\\|\\|")
  202.         String newline = System.getProperty("line.separator");
  203.         Map<Character, String> result = new HashMap<>();
  204.         File file = new File(file_name);
  205.         FileReader fReader = new FileReader(file);
  206.         BufferedReader bReader = new BufferedReader(fReader);
  207.         try
  208.         {
  209.         String line = "";
  210.         while((line = bReader.readLine()) != null)
  211.                 {
  212.                     String parts[] = line.split("\\|\\|");
  213.                     result.put(parts[0].charAt(0), parts[1]);
  214.                 }
  215.         }catch (IOException e) {
  216.             e.printStackTrace();
  217.         } finally {
  218.             try {
  219.                 if (bReader != null) {
  220.                     bReader.close();
  221.                 }
  222.                 if(fReader != null)
  223.                 {
  224.                     fReader.close();
  225.                 }
  226.             } catch (IOException e) {
  227.                 e.printStackTrace();
  228.             }
  229.         }
  230.         return result;
  231.     }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top