///////////
//
//  utils.cpp
//
//      AUTHOR: Aaron Lenard Hatcher (hatcher@fas.harvard.edu)
//          and Russell James Lowke  (lowke@fas.harvard.edu)
//
//		  T.Fs: Francis Crick & Bryan Kim
//
//		  Date: 8/12/2002
//
//  CSCIE-s111: Assignment Nine, Huffman Encoding
//
// Description: Utils is common to both huff and puff, and contains two
//				classes that are used for building and manipulating Huffman trees.
//				These classes are Tree and Forest.
//
// 				The Tree class constitutes the nodes on a Huffman Tree.
//				Key properties are: letter, frequency, leftTree, rightTree.
//	
//				The forest class is used for manipulating groups of Trees,
//				and combining them into a single key tree.
//
//				Encoding and Decoding is all resident within Forest,
//				and as such Forest is the common interface used by both
//				Huff and Puff to the Huffman Tree. 
//
//   Functions:
//
//			  swap() - used by sorting routines, i.e. sort();
//		BubbleSort() - perform bubble sort on the specified array
//
//
//     Methods: 
//
//			Tree class
//
//		   getLeft() - returns a pointer to what leftTree is pointing to
//		  getRight() - returns a pointer to what rightTree is pointing to
//       getLetter() - returns the value of "letter" within a tree
//    getFrequency() - returns the value of "frequency" within a tree
//		   setLeft() - set the leftTree pointer
//		  setRight() - same as setLeft, just on the right side
//		 setLetter() - set field letter
//	  setFrequency() - set field frequency
//
//			Forest class
//
//			Forest() - contructor, turns an integer array into an array of trees
//		 clearTree() - deletes a tree and all of its children
//		   ~Forest() - destructor, clears out the entire tree pointed to by *key
//			  sort() - bubble bubble toil & trouble (modified bubble sort)
//			 merge() - merge two trees
//		 createKey() - turns array of pointers to a single Huffman tree
//		 storeCode() - stores encoding
//		 encodeKey() - traverses the Huffman tree and builds a table of codes
//					   for all of the letters.
//		   getTree() - getTree
//	   getEncoding() - getEncoding
//
//		   Note: a tree frequency of -1 is used to represent interior tree node.
//

#include <iostream>
#include <iomanip>
#include <cassert>
#include "utils.hpp"
#include "bits.hpp"


//
// swap - used in QuickSort and our modified BubbleSort called sort();
//
void swap(Tree *&a, Tree *&b)
{
    Tree* temp;
    temp = a;
    a = b;
    b = temp;
    temp = NULL;
}


//
// BubbleSort - perform bubble sort on the specified array
//
template <class elt>
void BubbleSort(elt arr[], int num_objects)
{
	for (int i = 1; i <= num_objects; i++)
		for (int j = num_objects; j >= i; j--)
			if (*arr[j ] < *arr[j-1])
				swap(arr[j - 1], arr[j]);
}


//
// opereator < - overloaded operator for comparing trees
//
bool operator < (Tree one, Tree two)
{

	//compare the frequencies of the trees
	if (one.frequency < two.frequency) {
		return true;
    
	} else if (one.frequency == two.frequency) {
	
		// frequencies are equal, check the letter values		
		if (one.letter < two.letter) {
			return true;
		}
  
	}
	
	// return false for all other cases
	return false;
}


//
// operator > - overloaded operator for comparing trees
//
bool operator > (Tree one, Tree two)
{

	//compare the frequencies of the trees
	if (one.frequency > two.frequency) {
		return true;
		
	} else if (one.frequency == two.frequency) {
	
		//frequencies are equal, check the letter values
		if (one.letter > two.letter) {
			return true;
		}
	}
	
	// return false for all other cases
	return false;
}


//////////////////
//
//  Tree class
//
//

//
// getLeft - returns a pointer to what leftTree is pointing to
//
Tree *Tree::getLeft()
{
	return leftTree;
}


//
// getRight - returns a pointer to what rightTree is pointing to
//
Tree *Tree::getRight()
{
	return rightTree;
}


//
// getLetter - returns the value of "letter" within a tree
//
char Tree::getLetter()
{
	return letter;
}


//
// getFrequency - returns the value of "frequency" within a tree
//
int Tree::getFrequency()
{
	return frequency;
}


//
// setLeft - makes the leftTree pointer of a tree points to the argument
//
void Tree::setLeft( Tree *mLeft )
{
	leftTree = mLeft;
}


//
// setRight - same as setLeft, just on the right side
//
void Tree::setRight( Tree *mRight )
{
	rightTree = mRight;
}


//
// setLetter - sets the field "letter" to the character passed in as an argument
//
void Tree::setLetter ( char mChar )
{
	letter = mChar;
}


//
// setFrequency - sets the field "frequency" to integer passed in as an arg
//
void Tree::setFrequency (int mFrequency)
{
	frequency = mFrequency;
}




//////////////////
//
//  Forest class
//
//


//
// Forest - contructor, turns an integer array into an
// array of trees with characters and frequencies
//
Forest::Forest( int frequencyData[] )
{
	key = NULL;
	int _index = 0;
	for (int i = 0; i < TOTLETTERS; i++) {
		if (frequencyData[i] != 0) {
			Tree *temp = new Tree (frequencyData[i], (char) i );
			array[_index] = temp;
			_index++;
		}
	}
	--_index;							// decrement _index
	BubbleSort (array, _index);
	
	index = _index;
}


//
// clearTree - deletes a tree and all of its children,
// and its children's children, and children's children's children...
//
void Forest::clearTree(Tree* head)
{
	//takes care of empty tree case
	if (head == NULL) {
		cout<<"Tree already empty\n";
		return;
	}

	// recursive cases - delete left and right child if they exist
	if ( head->getLeft()!= NULL )
		clearTree (head->getLeft());
		
	if ( head->getRight()!= NULL )
		clearTree (head->getRight());

	// once done, delete the node we're on
	delete head;
}


//
// ~Forest - destructor, clears out the entire tree pointed to by *key
//
Forest::~Forest()
{
	clearTree(key);
}


//
//	sort - an efficient Bubblesort algorithm to be used in all intermediate 
//  passes over the array of pointers to tree.  Relies on the knowledge that 
//  only the first item will be out of order when it's called.
//
void Forest::sort(int min = 0, int max = TOTLETTERS-1)
{
	for (int i = min; i < max; i++) {
	
		if ( (*array[i]) > (*array[i + 1]) ) {
			swap (array[i], array[i + 1]);
		} else {
			return;
		}
	}
}


//
//  merge - "merge" two trees under a new tree
//
Tree* Forest::merge (Tree *mLeft, Tree *mRight)
{
	Tree *temp = new Tree (mLeft, mRight);
	return temp;
}


//
// createKey - turns the array of pointers to trees into a single Huffman tree
//
Tree * Forest::createKey()
{
	// keeps track of the first  and last valid index in the array.
	// necessary because our array shrinks from the front end
	int first = 0;
	int last = index;
	
	// goes until the array of trees has shrunk down to only one element
	while (first != last ) {
	
		// merges the first two trees and places a pointer to
		// the new tree into the SECOND spot
		array [first + 1] = merge (array[first], array [first+1]);

		// let's the function know that the tree shrunk by one element
		first++;
		
		// places that element in its proper place in the tree
		sort (first, index);
	}
	
	// makes member variable key point to the root of the finished Huffman tree
	key = array [first];
	
	// also returns a pointer to the head of the completed tree
	return array [first];
}

	
//
// storeCode - stores encoding
//
void Forest::storeCode (int *tempCode, int index, char letter)
{
	unsigned int thecode = 0;
	
	// for testing.  To be removed later.
	
	for (int i = 0; i <= index; i++)
	{
		assert ( tempCode[i] == 0 || tempCode[i] == 1);
		thecode = (thecode << 1);
		thecode |= tempCode[i];
	}
	// for testing
	code letterCode;
	letterCode.bits = thecode;
	letterCode.length = index + 1;
	encodings[letter] = letterCode;
}
		

//
//	encodeKey - traverses Huffman tree building a table of codes for all letters.	
//	
void Forest::encodeKey(Tree* node = NULL, int *tempCode = NULL)
{
	// the static integer that will keep track of which index in the tempCode
	// array to write to by keeping track of "how deep" in our recursive funtion
	// call we are, which also happens to correspond to the level in the tree
	// (assuming the root is level 0)
	
	static int index;
	
	// creates the integer array that will hold the temporary code the first time
	// through, initializes index to zero, and makes Tree *node point to the head
	// of the tree
	if (tempCode == NULL && node == NULL) {
		tempCode = new int [32];
		node = key;
		index = 0;		
	}

	// base case: we've reached a tree node
	if (node->getLeft() == NULL && node->getRight() == NULL) {

		storeCode(tempCode, index, node->getLetter());
		
		// bounce back a step in the recursive call
		return;
	}
	
	
	// recursives cases: left and right children do exist.
	if (node->getLeft() != NULL) {
	
		// if we go left, we must store that information as a zero in the
		// appropriate code, increment the index, then make the recursive call
		// on the left subtree
		tempCode[index] = 0;
		index++;
		
		encodeKey (node->getLeft(), tempCode);
		// restore the index to how it was before the recursive call
		index--;
	}
	
	if (node->getRight() != NULL) {
		
		tempCode[index] = 1;
		index++;
		
		encodeKey (node->getRight(), tempCode);
		index--;
	}
	
	// we need to deallocate the memory we're using on the heap in the case that
	// we're back at the beginning and we've made the recursive calls, so we check
	// for that and act accordingly
	if (index == 0) {
		delete [] tempCode;
	}
	return;
}


//
// get and set methods
//

//
//  getTree
//
Tree *Forest::getTree()
{
	return key;
}


//
//  getEncoding
//			
code Forest::getEncoding(char let)
{
	return (encodings[(int)let]);
}
