//****************************************************************************
//
// Program:      Homework 3 -- Huffman Codes
//
// Author:       Travis Dillon
// Email:        tdillon@ace.cs.ohiou.edu
//
// Description:  The input file is a code of ones and zeros.  This program
//               turns that program into a dictionary of codes and then
//               the encoded message.
//               
// Date:         September 30, 2003
//
//****************************************************************************

#include "prog2.h"

int main()
{
   string filename;
   getline(cin, filename);
   
   get_info(filename);

   return EXIT_SUCCESS;
}


//****************************************************************************
//
// Function:   get_info
//
// Purpose:    reads the code from the file and sends it out three
//             lines at a time
//
// Parameters: filename - the input file
//
// Calls:      open, c_str, fail, exit, peek, getline, size, insert, close,
//             huffman
//
// Time Comp:  O(size of file)
//
// Space Com:  O(lenght of file line)
//
//****************************************************************************


void get_info(string filename)
{
   ifstream fin;
   fin.open(filename.c_str());
   if(fin.fail())
   {
      cerr << "\nError in input file.\n";
      exit(1);
   }
   
   vector<Tree> list;
   string one;
   string two;
   string three;   
   size_t count(0);
   size_t length;

   while(fin.peek() != EOF)
   {
      getline(fin, one);
      if(one.size() % 3 != 0 || fin.peek() == EOF)
      {
         cerr <<"\nError in input file.\n";
         exit(1);
      }

      getline(fin, two);
      if(one.size() != two.size() || fin.peek() == EOF)
      {
         cerr <<"\nError in input file.\n";
         exit(1);
      }

      getline(fin, three);
      if(one.size() != three.size())
      {
         cerr << "\nError in input file.\n";
         exit(1);
      }

      if(count++ == 0)
      {
         length = one.size();  //now all .size()'s must be == to length
      }

      insert(list, one, two, three, length);
   }
   fin.close();   
   huffman(list, filename);   
}


//****************************************************************************
//
// Function:   insert
//
// Purpose:    takes the incoming string and creates nodes to send to be put
//             in the list
//
// Parameters: list - a vector of Trees
//             one - first line from file
//             two - second line from file
//             three - third line from file
//             length - length the lines have to be
//
// Calls:      size, put_in_list
//
// Time Comp:  O(length of line)
//
// Space Com:  O(1)
//
//****************************************************************************


void insert(vector<Tree>& list, string one, string two,
            string three, size_t length)
{
   if(one.size() != length)
   {
      cerr <<"\nError in input file.\n";
      exit(0);
   }

   for(size_t i(0); i < (one.size() / 3); ++i)
   {
      Node temp_node(one[i*3], one[i*3+1], one[i*3+2], two[i*3], two[i*3+1],
                     two[i*3+2], three[i*3], three[i*3+1], three[i*3+2]);      
      put_in_list(list, temp_node);
   }
}


//****************************************************************************
//
// Function:   put_in_list
//
// Purpose:    puts node into a Tree and puts it into the correct place
//             in the list
//
// Parameters: list - vector of Trees
//             in_node - node to be put into list
//
// Calls:      begin, end, get_value, increase_weight, erase, get_weight,
//             insert, push_back
//
// Time Comp:  O(number of elements in the list squared)
//
// Space Com:  O(1)
//
//****************************************************************************


void put_in_list(vector<Tree>& list, Node in_node)
{
   vector<Tree>::iterator iter = list.begin();
   Tree temp_tree(in_node);   

   for(iter = list.begin(); iter != list.end(); ++iter)
   {
      if(iter -> get_value() == temp_tree.get_value())
      {
         iter -> increase_weight();
         Tree tree_holder = *iter;
         list.erase(iter);
         for(iter = list.begin(); iter != list.end(); ++iter)
         {
            if(tree_holder.get_weight() < iter -> get_weight())
            {
               list.insert(iter, tree_holder);
               return;
            }
            if((tree_holder.get_weight() == iter -> get_weight()) &&
               (tree_holder.get_value() < iter -> get_value()))
            {
               list.insert(iter, tree_holder);
               return;
            }
         }
         list.push_back(tree_holder);
         return;
      }         
   }
   
   iter = list.begin();
   while(iter != list.end())
   {
      if(temp_tree.get_weight() < iter -> get_weight())
      {
         list.insert(iter, temp_tree);
         return;
      }
      if((temp_tree.get_weight() == iter -> get_weight()) &&
         (temp_tree.get_value() < iter -> get_value()))
      {
         list.insert(iter, temp_tree);
         return;
      }
      ++iter;
   }
   list.push_back(temp_tree);
}


//****************************************************************************
//
// Function:   huffman
//
// Purpose:    creates a single huffman tree
//
// Parameters: list - vector of Trees
//             filename - input file
//
// Calls:      size, get_min, set_kids, make_tree, test, get_root, begin,
//             print_dictionary, print_comp
//
// Time Comp:  O(size of list)
//
// Space Com:  O(1)
//
//****************************************************************************


void huffman(vector<Tree>& list, string filename)
{
   size_t sz(list.size());
   for(size_t i(0); i < (sz - 1); ++i)
   {
      Tree first = get_min(list);
      Tree second = get_min(list);
      Tree temp_tree;
      temp_tree.set_kids(first, second);
      make_tree(temp_tree, list);
   }
   string huff_code;
   
   test(list.begin() -> get_root() , huff_code);   
   
   cout << "dictionary\n";
   list.begin() -> print_dictionary(list.begin() -> get_root());  
   cout << "compressed file\n";
   print_comp(list, filename);
   cout << endl;
}


//****************************************************************************
//
// Function:   make_tree
//
// Purpose:    this orders the list according to weight
//
// Parameters: temp_tree - Tree to insert into list
//             list - vector of Trees
//
// Calls:      begin, end, get_weight, insert, push_back
//
// Time Comp:  O(size of list)
//
// Space Com:  O(1)
//
//****************************************************************************


void make_tree(Tree temp_tree, vector<Tree>& list)
{
   vector<Tree>::iterator iter = list.begin();
   while(iter != list.end())
   {
      if(temp_tree.get_weight() < iter -> get_weight())
      {
         list.insert(iter, temp_tree);
         return;
      }
      if((temp_tree.get_weight() == iter -> get_weight()) &&
         (temp_tree.get_value() < iter -> get_value()))
      {
         list.insert(iter, temp_tree);
         return;
      }
      ++iter;
   }
   list.push_back(temp_tree);
}


//****************************************************************************
//
// Function:   get_min
//
// Purpose:    deletes and returns the smallest Tree in the list
//
// Parameters: list - vector of Trees
//
// Calls:      empty, exit, front, erase, begin
//
// Time Comp:  O(1)
//
// Space Com:  O(1)
//
//****************************************************************************


Tree get_min(vector<Tree>& list)
{
   if(list.empty())
   {
      cerr <<"\nError in input file.\n";
      exit(1);
   }
   Tree temp_tree = list.front();
   list.erase(list.begin());
   return temp_tree;
}


//****************************************************************************
//
// Function:   test
//
// Purpose:    gets the code from the tree and sends it out to be set
//
// Parameters: the_root - pointer to root in the huffman tree
///            huff_code - string that keeps track of left and right 0 and 1
//
// Calls:      at_left, at_right, new, size, set_code, test, erase
//
// Time Comp:  O(size of tree)
//
// Space Com:  O(size of tree)
//
//****************************************************************************


void test(Node* the_root, string huff_code)
{
   if(the_root != NULL)
   {
      if((the_root -> at_left() == NULL) &&
         (the_root -> at_right() == NULL))
      {
         char* temp_array;
         temp_array = new char[huff_code.size()];
         for(size_t i(0); i < huff_code.size(); ++i)
         {
            temp_array[i] = huff_code[i];
         }
         the_root -> set_code(huff_code.size(), temp_array);
      }
      test(the_root -> at_left(), huff_code += '0');
      huff_code.erase(huff_code.size() - 1, 1);
      test(the_root -> at_right(), huff_code += '1');
   }
}


//****************************************************************************
//
// Function:   print_comp
//
// Purpose:    gets the original data from file and sends it away to get
//             the codes and print out
//
// Parameters: list - vector of Trees
//             filename - input file
//
// Calls:      open, c_str, fail, exit, peek, getline, size, begin,
//             print_compressed, get_root, close
//
// Time Comp:  O(file size * line length)
//
// Space Com:  O(line length)
//
//****************************************************************************


void print_comp(vector<Tree> list, string filename)
{
   ifstream fin;
   fin.open(filename.c_str());
   if(fin.fail())
   {
      cerr << "\nError in input file.\n";
      exit(1);
   }   
   string one;
   string two;
   string three;
   while(fin.peek() != EOF)
   {
      getline(fin, one);
      getline(fin, two);
      getline(fin, three);
      for(size_t i(0); i < (one.size() / 3); ++i)
      {
         size_t temp_data[9];
         temp_data[0] = one[i*3];
         temp_data[1] = one[i*3+1];
         temp_data[2] = one[i*3+2];
         temp_data[3] = two[i*3];
         temp_data[4] = two[i*3+1];
         temp_data[5] = two[i*3+2];
         temp_data[6] = three[i*3];
         temp_data[7] = three[i*3+1];
         temp_data[8] = three[i*3+2];
         list.begin() -> print_compressed(list.begin() -> get_root(), temp_data);
      }
      cout << endl;
   }
   fin.close();
}