import java.io.File;
   import java.io.BufferedReader;
   import java.io.FileReader;
   import java.io.IOException;
   import java.util.ArrayList;
   import java.util.HashMap;
   /**
	*This class implements Huffman's Algorithm. It reads in any .txt file given in the command argument
	* and reads the characters that are in and determines: how many characters there are, how many times they occur, and
	* generates binary code for them according to Huffman's Algorithm.
	* @author Charlie Davis (CLD0023@auburn.edu), Jordan Hutcheson (jmh0049@auburn.edu)
	* @version 2011-04-25
	*/

   public class Huff
   {
      private File file;
      private BufferedReader reader;
      private HashMap charHash = new HashMap();
      private PriorityQueue queue;
      private String string = "";
      private char[] tokens;
      private ArrayList<TreeNode> array = new ArrayList<TreeNode>();
      private int bitBefore = 0;
      private int bitAfter = 0;

   /**
   *Constructor that takes in a String representation of the File that is to be read.
   *@param fileIn String containing a file name including .txt
   */
      public Huff(String fileIn)
      {
         this(new File(fileIn));
      }
   /**
   *Secondary constructor that stores the file and calls the read() method.
   *@param fileIn to be read by Huff.
   */

      public Huff(File fileIn)
      {
         this.file = fileIn;
         read();
      }
   /**
   *This is the read() method which essentially performs the task of reading the file into the class.
   *This method also sets up the small variable important to the final output.
   */
      public void read()
      {
         try {
            reader = new BufferedReader(new FileReader(file));
            while (reader.ready())
            {
               string += reader.readLine();
            }
            //convert the string into a char[]
            tokens = string.toCharArray();
           	//bits before the text is "compressed"
            bitBefore = 8 * tokens.length;
            reader.close();
         }
            catch (IOException e)
            {
               e.printStackTrace();
               return;
            }
         //instantiate the toAdd boolean to true so that it will add the first character.
         boolean toAdd = true;

      	//loop through the token array and store the characters as TreeNodes into an ArrayList.
         for (int i = 0; i < tokens.length; i++) {

            for (int a = 0; a < array.size(); a++) {
            //if the character is already inside of the arrayList find it and increment its weight.
               if (tokens[i] == (Character) (array.get(a).getValue())) {
                  array.get(a).setWeight(array.get(a).getWeight() + 1);
                  toAdd = false;
                  break;
               }
            }

            if (toAdd) {
               array.add(new TreeNode(tokens[i], 1));
            }

            toAdd = true;
         }

         queue = new PriorityQueue(array);

         TreeNode c1;
         TreeNode c2;
         TreeNode c3;

         while (queue.size() > 1) {
            c1 = (TreeNode) queue.remove();
            c2 = (TreeNode) queue.remove();
            c3 = new TreeNode(null, c1.getWeight() + c2.getWeight(), c1, c2);
            queue.add(c3);
         }

         TreeNode minTreeNodeTree = (TreeNode) queue.remove();

      	//traverse the tree and set all of the binary.
         for (int i = 0; i < tokens.length; i++) {
            searchTree(minTreeNodeTree, tokens[i], "");
         }

         String s = "";
         for (int i = 0; i < tokens.length; i++) {
            s += charHash.get(tokens[i]);
         }

         bitAfter = s.length();

      }
   /**
   *A Recursive Depth-First approach to traversing the binary tree. Takes in the intial string "" and adds a '0' or a '1' depending on if it goes
   *to a left child or a right child.
   *@param node TreeNode to be traversed.
   *@param target char to be found, if it exists.
   *@param pre String binary to be produced and placed in the HashMap along with the character key.
   */
      @SuppressWarnings("unchecked")
      public void searchTree(TreeNode node, char target, String pre) {

         if (node == null) {
            return;
         }

         else if (node.getValue() != null && (Character) node.getValue() == target) {
         //store the character as a key along with the binary string (pre)
            charHash.put((Character) node.getValue(), pre);
            return;
         }

         else {
            searchTree(node.lNode(), target, pre + '0');
            searchTree(node.rNode(), target, pre + '1');
         }
      }

   /**
   *Creates a string for output containing the characters, frequency of the character, and the binary generated.
   *@return String representation of each character.
   */
      public String toString()
      {
         String s = "Huff:\n";
         for (int i = 0; i < array.size(); i++)
         {
            s += array.get(i) + " Huffman Code: " + charHash.get(array.get(i).getValue()) + "\n";
         }
         s += "Bits before: " + bitBefore + "\nBits after: " + bitAfter + "\nTotal characters in the file: " + tokens.length;
         return s;
      }

   /**
   *This main runs the first file in the Command Arguments if it is a valid file.
   *@param args user-defined File to be read.
   */

      public static void main(String[] args) {
         File file;
         try {
            file = new File(args[0]);
            if (file.exists()) {
               Huff p = new Huff(args[0]);
               System.out.print(p);
            }
            else {
               System.out.println("File or Filename invalid.");
            }
         }
            catch (ArrayIndexOutOfBoundsException e) {
               System.out.println("There are no command arguments..");
            }


      }

   }

   import java.io.File;
   import java.io.BufferedReader;
   import java.io.FileReader;
   import java.io.IOException;
   import java.util.ArrayList;
   import java.util.HashMap;
   import java.util.Comparator;
   /**
	*This class implements Huffman's Algorithm but with a Max Heap instead of a Min Heap, making it severly worse.
	* It reads in any .txt file given in the command argument
	* and reads the characters that are in and determines: how many characters there are, how many times they occur, and
	* generates binary code for them according to Huffman's Algorithm.
	* @author Charlie Davis (CLD0023@auburn.edu), Jordan Hutcheson (jmh0049@auburn.edu)
	* @version 2011-04-25
	*/

   public class Puff
   {

      private File file;
      private BufferedReader reader;
      private HashMap charHash = new HashMap();
      private PriorityQueue queue;
      private String string = "";
      private char[] tokens;
      private ArrayList<TreeNode> array = new ArrayList<TreeNode>();
      private int bitBefore = 0;
      private int bitAfter = 0;
   /**
   *An inner class in Puff that is simply a Comparator to be given into the PriorityQueue.
   */
      @SuppressWarnings("unchecked")
      public static class PuffCompare implements Comparator {
      /**
      *Method that returns the negative comparison of the two objects.
      *@param o1 Object one to be compared.
      *@param o2 Object two to be compared.
      *@return int based on comparison.
      */
         public int compare(Object o1, Object o2)
         {
            return -(((Comparable) o1).compareTo(o2));
         }

      }
   /**
   *Constructor that takes in a String fileName and passes it into the secondary constructor.
   *@param fileIn String containing a file name including .txt
   */
      public Puff(String fileIn)
      {
         this(new File(fileIn));
      }
   /**
   *Secondary constructor that stores the file and calls the read() method.
   *@param fileIn to be read by Puff.
   */
      public Puff(File fileIn)
      {
         this.file = fileIn;
         read();
      }
   /**
   *This is the read() method which essentially performs the task of reading the file into the class.
   *This method also sets up the small variable important to the final output.
   */
      public void read()
      {
         try {
            reader = new BufferedReader(new FileReader(file));
            while (reader.ready())
            {
               string += reader.readLine();
            }
            tokens = string.toCharArray();
            bitBefore = 8 * tokens.length;
            reader.close();
         }
            catch (IOException e)
            {
               e.printStackTrace();
               return;
            }

         boolean toAdd = true;

         for (int i = 0; i < tokens.length; i++) {

            for (int a = 0; a < array.size(); a++) {

               if (tokens[i] == (Character) (array.get(a).getValue())) {
                  array.get(a).setWeight(array.get(a).getWeight() + 1);
                  toAdd = false;
                  break;
               }
            }

            if (toAdd) {
               array.add(new TreeNode(tokens[i], 1));
            }

            toAdd = true;
         }

         Comparator compare = new PuffCompare();
         queue = new PriorityQueue(compare);

         for (int i = 0; i < array.size(); i++) {
            queue.add(array.get(i));
         }


         TreeNode c1;
         TreeNode c2;
         TreeNode c3;

         while (queue.size() > 1) {
            c1 = (TreeNode) queue.remove();
            c2 = (TreeNode) queue.remove();
            c3 = new TreeNode(null, c1.getWeight() + c2.getWeight(), c1, c2);
            queue.add(c3);

         }

         TreeNode minTreeNodeTree = (TreeNode) queue.remove();
         for (int i = 0; i < tokens.length; i++) {
            searchTree(minTreeNodeTree, tokens[i], "");
         }

         String s = "";
         for (int i = 0; i < tokens.length; i++) {
            s += charHash.get(tokens[i]);
         }

         bitAfter = s.length();

      }
   /**
   *A Recursive Depth-First approach to traversing the binary tree. Takes in the intial string "" and adds a '0' or a '1' depending on if it goes
   *to a left child or a right child.
   *@param node TreeNode
   *@param target char
   *@param pre String
   */
      @SuppressWarnings("unchecked")
      public void searchTree(TreeNode node, char target, String pre) {

         if (node == null) {
            return;
         }

         else if (node.getValue() != null && (Character) node.getValue() == target) {
            charHash.put((Character) node.getValue(), pre);
            return;
         }

         else {
            searchTree(node.lNode(), target, pre + '0');
            searchTree(node.rNode(), target, pre + '1');
         }
      }
   /**
   *Creates a string for output containing the characters, frequency of the character, and the binary generated.
   *@return String representation of each character.
   */
      public String toString()
      {
         String s = "Puff:\n";
         for (int i = 0; i < array.size(); i++)
         {
            s += array.get(i) + " Huffman Code: " + charHash.get(array.get(i).getValue()) + "\n";
         }
         s += "Bits before: " + bitBefore + "\nBits after: " + bitAfter + "\nTotal characters in the file: " + tokens.length;
         return s;
      }

   /**
   *This main method runs the first file in the Command Argument if it is a valid file.
   *@param args user-defined File to be read.
   */
      public static void main(String[] args) {
         File file;
         try {
            file = new File(args[0]);
            if (file.exists()) {
               Puff p = new Puff(args[0]);
               System.out.print(p);
            }
            else {
               System.out.println("File or Filename invalid.");
            }
         }
            catch (ArrayIndexOutOfBoundsException e) {
               System.out.println("There are no command arguments..");
            }
      }

   }

   import java.io.File;
   import java.io.BufferedReader;
   import java.io.FileReader;
   import java.io.IOException;
   import java.util.ArrayList;
   import java.util.HashMap;
   import java.util.HashSet;
   /**
	*Blow is the class responsible for compressing files using a fixed length code instead of Huffman's algorithm.
	*The class finds what 2 to the nth is large enough to represent all the unique characters represented in the file.
	*Then it creates binary that has up to n bits to represent the characters.
	*
	*@author Jordan Hutcheson (jmh0049@auburn.edu), Charlie Davis (CLD0023@auburn.edu)
	*@version 2011-04-25
	*/
   public class Blow
   {

      private File file;
      private BufferedReader reader;
      private HashMap<Character, String> charHash = new HashMap<Character, String>();
      private String string = "";
      private char[] tokens;
      private ArrayList<TreeNode> nodeArray = new ArrayList<TreeNode>();
      private int bitBefore = 0;
      private int bitAfter = 0;
      private static int spacesNeeded = 0;

   /**
   *This is the class's constructor that creates the blow class and sets up the values based off of the file.
   *
   *@param fileIn The file to be used to set up the class.
   */
      public Blow(String fileIn)
      {
         this(new File(fileIn));
      }
   /**
   *This is the secondary constructor that is called in the previous constructor to create the Blow class. Calls the
   *read() method.
   *
   *@param fileIn The file to set up the class.
   */
      public Blow(File fileIn)
      {
         this.file = fileIn;
         read();
      }
      /**
   	*This is the read() method which essentially performs the task of reading the file into the class.
   	*This method also sets up the small variable important to the final output.
   	*/
      public void read()
      {
         try {
            reader = new BufferedReader(new FileReader(file));
            while (reader.ready())
            {
               string += reader.readLine();
            }
            tokens = string.toCharArray();
            bitBefore = 8 * tokens.length;
            reader.close();
         }
            catch (IOException e)
            {
               e.printStackTrace();
               return;
            }

         boolean toAdd = true;

         for (int i = 0; i < tokens.length; i++) {

            for (int a = 0; a < nodeArray.size(); a++) {

               if (tokens[i] == (Character) (nodeArray.get(a).getValue())) {
                  nodeArray.get(a).setWeight(nodeArray.get(a).getWeight() + 1);
                  toAdd = false;
                  break;
               }
            }

            if (toAdd) {
               nodeArray.add(new TreeNode(tokens[i], 1));
            }

            toAdd = true;
         }

         charHash = createBinary(nodeArray);
         bitAfter = spacesNeeded * tokens.length;

      }
     /**
     *This is a recursive method that iterates in order to find out if the passed in array can be, by the rules of
     *binary addition, be incremented and if so performs it. It actually uses reverse recursion.
     *
     *@param arrayIn The array to be checked if it can be incremented.
     *@param j Where in array it should be checked if it can increment by one.
     *@return arrayIn Returns the arraIn at these default conditions.
     */

      private int[] recursive(int[] arrayIn, int j) {
         if (j < 0 && arrayIn[0] == 1) {
            return arrayIn;
         }
         else if (arrayIn[j] == 0) {
            arrayIn[j] = 1;
            return arrayIn;
         }
         else {
            arrayIn[j] = 0;
            return recursive(arrayIn, j - 1);
         }
      }
   	/**
   	*checkAllDone takes in an array and checks to see if every position is all equal to one. This simply
   	*checks to see if the recursive method has executed to it maximum amount.
   	*
   	*@param arrayIn The array that is going to be checked if all positions are equal to 1.
   	*@return allDone Boolean which tells whether all the positions of the array are 1 or not.
   	*/
      public boolean checkAllDone(int[] arrayIn) {
         boolean allDone = true;
         int n = 0;
         while (allDone && n < arrayIn.length) {
            if (arrayIn[n] != 1) {
               allDone = false;
            }
            else {
               n++;
            }
         }
         return allDone;
      }
      /**
   	*This method is responsible for creating the hasmap that is the main brute force of the whole class.
   	*This class determines how many binary numbers of the fixed length are necessary to represent all the unique chars.
   	*Then, the class iterates and creates the binary while also assigning the new binary to the unique characters in the
   	*charHash.
   	*
   	*@param a ArrayList of tree nodes that represent the unique characters.
   	*@return map The returned hashMap that contains all the newly assigned variables and binary numbers.
   	*/
      public HashMap<Character, String> createBinary(ArrayList<TreeNode>  a) {
         int n = 0;
         int uniqueChars = a.size();
         HashSet<String> binaryHolder = new HashSet<String>();
         HashMap<Character, String> map = new HashMap<Character, String>();

         while (Math.pow(2, n) < uniqueChars) {
            n++;
         }
         spacesNeeded = n;
         int[] binary = new int[n];

         while (!checkAllDone(binary) && !(binaryHolder.size() == uniqueChars)) {
            binaryHolder.add(convert(binary));
            binary = recursive(binary, binary.length - 1);
         }
         int i = 0;
         for (String s : binaryHolder) {
            map.put((Character) a.get(i).getValue(), s);
            i++;
         }
         return map;
      }
      /**
   	*convert() simply takes in an array of integers and converts them into a string. This method is mainly only important for the toString()
   	*method and does not carry much purpose elsewhere in the class.
   	*
   	*@param a The integer array to be transformed into a String.
   	*@return temp The returned String version of the int array.
   	*/
      public String convert(int[] a)
      {
         String temp = "";
         for (int i = 0; i < a.length; i++) {
            temp += a[i];
         }
         return temp;
      }
      /**
   	*The toString method of the class which takes the class and puts its information into a string form for reading.
   	*It shows all the special characters and their values and the amount by which the file has been shortened.
   	*
   	*@return string The string representation of the class.
   	*/
      public String toString()
      {
         String aString = "Blow:\n";
         for (int i = 0; i < nodeArray.size(); i++)
         {
            aString += nodeArray.get(i) + " Code: " + charHash.get(nodeArray.get(i).getValue()) + "\n";
         }
         aString += "Bits before: " + bitBefore + "\nBits after: " + bitAfter + "\nTotal characters in the file: " + tokens.length;
         return aString;
      }
   /**
   *This is the main method of the class Blow. It takes in args but only uses the first argument passed.
   *
   *@param args The arguments are generally going to be files passed in as the name of files.
   */

      public static void main(String[] args) {
         File file;
         try {
            file = new File(args[0]);
            if (file.exists()) {
               Blow p = new Blow(args[0]);
               System.out.print(p);
            }
            else {
               System.out.println("YO FILE SUX");
            }
         }
            catch (ArrayIndexOutOfBoundsException e) {
               System.out.println("There are no command arguments..");
            }
      }

   }