#include "tree.h"


//****************************************************************************
//
// Function:   Tree
//
// Purpose:    tree c-tor
//
// Parameters: none
//
// Calls:      none
//
// Time Comp:  O(1)
//
// Space Com:  O(1)
//
//****************************************************************************


Tree::Tree()
{
   root = new Node;
}


//****************************************************************************
//
// Function:   Tree
//
// Purpose:    insert node into tree
//
// Parameters: in - node to set root equal to
//
// Calls:      new
//
// Time Comp:  O(1)
//
// Space Com:  O(1)
//
//****************************************************************************


Tree::Tree(Node in)
{
   root = new Node(in);
}


//****************************************************************************
//
// Function:   get_value
//
// Purpose:    returns the value of a node for comparison
//
// Parameters: none
//
// Calls:      none
//
// Time Comp:  O(1)
//
// Space Com:  O(1)
//
//****************************************************************************


size_t Tree::get_value()
{
   return(root -> data[0]*100000000 + root -> data[1]*10000000 +
          root -> data[2]*1000000 + root -> data[3]*100000 + 
          root -> data[4]*10000 + root -> data[5]*1000 +
          root -> data[6]*100 + root -> data[7]*10 +
          root -> data[8]);
}


//****************************************************************************
//
// Function:   get_weight
//
// Purpose:    return weight of node
//
// Parameters: none
//
// Calls:      none
//
// Time Comp:  O(1)
//
// Space Com:  O(1)
//
//****************************************************************************


size_t Tree::get_weight()
{
   return root -> weight;
}


//****************************************************************************
//
// Function:   increase_weight
//
// Purpose:    increase the weight of a node
//
// Parameters: none
//
// Calls:      none
//
// Time Comp:  O(1)
//
// Space Com:  O(1)
//
//****************************************************************************


void Tree::increase_weight()
{
   ++ root -> weight;
}


//****************************************************************************
//
// Function:   set_kids
//
// Purpose:    sets the right and left child of the calling tree
//
// Parameters: first - new left child of calling tree
//             second - new right child of calling tree
//
// Calls:      new
//
// Time Comp:  O(1)
//
// Space Com:  O(1)
//
//****************************************************************************


void Tree::set_kids(Tree& first, Tree& second)
{
   root -> left = new Node(*first.root);
   root -> right = new Node(*second.root);
   root -> weight = first.root -> weight + second.root -> weight;
   if(first.root -> get_data() < second.root -> get_data())
   {
      for(size_t i(0); i < 9; ++i)
      {
         root -> data[i] = first.root -> data[i];
      }
   }
   else
   {
      for(size_t i(0); i < 9; ++i)
      {
         root -> data[i] = second.root -> data[i];
      }
   }
}


//****************************************************************************
//
// Function:   print_dictionary
//
// Purpose:    print the orignal character then the new code for them
//
// Parameters: the_root - root of the Tree
//
// Calls:      print_dictionary
//
// Time Comp:  O(size of tree)
//
// Space Com:  O(size of tree)
//
//****************************************************************************


void Tree::print_dictionary(Node* the_root)
{
   if(the_root != NULL)
   {
      print_dictionary(the_root -> left);
      
      if((the_root -> left == NULL) && (the_root -> right == NULL))
      {
         for(size_t i(0); i < 9; ++i)
         {
            cout << the_root -> data[i];
         }
         cout << " ";
         for(size_t i(0); i < the_root -> code_size; ++i)
         {
            cout << the_root -> code[i];
         }
         cout << endl;
      }
      
      print_dictionary(the_root -> right);
   }
}


//****************************************************************************
//
// Function:   print_compressed
//
// Purpose:    prints the compressed form of the orignal document
//
// Parameters: the_root - root of tree
//             checker - data to look for
//
// Calls:      print_compressed
//
// Time Comp:  O(size of file)
//
// Space Com:  O(size of file)
//
//****************************************************************************


void Tree::print_compressed(Node* the_root, size_t checker[])
{
   if(the_root != NULL)
   {      
      print_compressed(the_root -> left, checker);
      
      if((the_root -> left == NULL) && (the_root -> right == NULL))
      {
         bool not_equal(true);
         for(size_t i(0); i < 9; ++i)
         {
            if(checker[i] - 48 == the_root -> data[i])
            {
               not_equal = false;
            }
            else
            {
               not_equal = true;
            }
            if(not_equal)
            {
               return;
            }
         }
         for(size_t i(0); i < the_root -> code_size; ++i)
         {
            cout << the_root -> code[i];
         }
         return;
      }
      
      print_compressed(the_root -> right, checker);
   }
}