///////////
//
//  utils.hpp
//              header for utils.cpp package
//
//      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
//

#ifndef _UTILS_H_
#define _UTILS_H_

#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <assert.h>
#include "bits.hpp"

const int TOTLETTERS = 128;						// total possible letter types
const int TAGNAME    = -1444;					// tag used to recognize a huff
												// compresed file

class Tree
{
	friend bool operator < (Tree one, Tree two);
	friend bool operator > (Tree one, Tree two);

	private:

 	  char	letter;								// letter this tree represents
	  int	frequency;							// frequency of this letter
	  Tree	*leftTree;							// ptr to left child (0)
	  Tree	*rightTree;							// ptr to right child (1)

	public:

	  // methods
	  Tree( int mFrequency, char mChar )		// constuctor used by Forest
	  {
		frequency = mFrequency;
	  	letter    = mChar;
	  	leftTree  = NULL;
	  	rightTree = NULL;
	  }

	  Tree( Tree  *mLeft, Tree  *mRight )		// constuctor used by merge()		
	  {
	  	assert (mLeft != NULL && mRight != NULL);
	  	frequency = mLeft->frequency + mRight->frequency;
	  	letter    = -1;
	  	leftTree  = mLeft;
	  	rightTree = mRight;
	  }
	  void	setFrequency( int mFreqency );		// set frequency for this tree
	  int	getFrequency();						// get the frequency
	  void	setLeft( Tree *mLeft );				// set left child
	  void	setRight( Tree *mRight );			// set right child
	  void	setLetter( char mChar );			// set Tree letter
	  char	getLetter();						// get Tree letter
	  Tree *getLeft();							// returns ptr to left chid
	  Tree *getRight();							// returns ptr to right child
};

class Forest
{
	private:
        
	  Tree 	*array[TOTLETTERS];					// letter frequency trees
	  Tree 	*key;								// finished tree from array[]
	  code	encodings[TOTLETTERS];				// list of binary encodings used
												// by Huff derived from key tree
	  int index;                            
	  // private methods
	  Tree 	*merge(Tree  *mLeft,				// merges two tress into one
	  			   Tree  *mRight);  
	  void  sort1st();
	  void 	sort(int min = 0,
	  			 int max = TOTLETTERS-1);		// sorts forest by frequency
	  void  storeCode(int *tempCode,			// used by encodeKey to store code
	  				  int index,				// for given letter encodings[] 
	  				  char letter);				// once a leaf has been reached
	  											
	  											
	  void Forest::clearTree(Tree* head);
	  
	  
	public:
        
	  // public methods
	  Forest( int frequencyData[TOTLETTERS] );	// constructor
	  ~Forest();
	  Tree 	*createKey();						// converts frequency data
	  											// into a single tree
	  void 	encodeKey(Tree* node = NULL,		// extract encodings from
	  				int *tempCode = NULL);		// Huffman tree to [encodings]
	  char 	decode( code mcode );				// decode binary code to to char
	  code	getEncoding(char);					// return Huffman code for char
	  											// ( used by Huff )
	  Tree	*getTree();							// return tree for decoding
	  											// ( used by Puff )
            

};

#endif /* _UTILS_H_ */
