#ifndef tree_h
#define tree_h

#include <iostream.h>  // for output 
#include <stdlib.h>  // for atoi 
#include <string>  // for strings 
#include <fstream.h>  // for file stuff 

class tree{

public:
	// *** constructors *** 

	tree();  
	tree(const int stuff, const char new_letter);	 
	tree(int new_root, char new_letter, tree * left, tree * right);  // construct a tree with root value new_root 
	tree(int new_root, tree * left, tree * right); // and left tree left, right tree right 



	// *** changing/accessing nodes *** 

	int root() {return data;} // returns the data of the root 
	void change_root(int new_data) {data = new_data;} // changes the data of the root 
	
	// accessing sub-trees 

	tree * left () {return leftchild;} 		 // return left subtree 
	void left(tree *l) {leftchild = l;}		 // return left child 
	tree * right () {return rightchild;}		 // return right subtree 
	void right(tree *r) { rightchild = r;}		 // return right child 



	// *** traversal *** 
	void traverse(tree * the_tree, string str = "");
	// *** Boolean Operators *** 
	bool operator<(tree the_tree) { return root() < the_tree.data;}
	bool operator>(tree the_tree) { return root() > the_tree.data;}

private:

	int data;
	char letter;
	tree * rightchild ;
	tree * leftchild ;
	tree * subtree (tree *);
	bool fakenode;
};



tree::tree(){
	data = 0;
	rightchild = NULL;
	leftchild = NULL;
	fakenode = 1;
}

tree::tree(const int stuff, const char new_letter){
	data = stuff;
	letter = new_letter;
	rightchild = NULL;
	leftchild = NULL;
	fakenode = 1;
}

tree::tree(int new_root, char new_letter, tree * left, tree * right){
	data = new_root;
	letter = new_letter;
	leftchild = left;
	rightchild = right;
	fakenode = 0;
}

tree::tree(int new_root, tree * left, tree * right){
	data = new_root;
	leftchild = left;
	rightchild = right;
	fakenode = 0;
}

tree * tree::subtree( tree * pointer){
	tree * new_point;

	if (pointer) {
		new_point = new tree();
		new_point->data = pointer->root();
		new_point->leftchild = pointer->subtree(pointer->leftchild);
		new_point->rightchild = pointer->subtree(pointer->rightchild);
	}
	else 
	new_point = 0;
	
	return new_point;
}

void tree::traverse(tree * the_tree, string str){
	ofstream out_file, delete_file;
	out_file.open("outfile.dat", ios::app);
	
	if (out_file.fail()){
		cout << "Output file outfile.dat failed to open." << endl;
		exit(1);
	}
	
	tree new_tree(*the_tree);
	if(new_tree.leftchild == NULL && new_tree.rightchild == NULL){
		out_file << new_tree.data << ' ' << new_tree.letter << '\t' << str + '\n';
	} else {
		traverse(new_tree.leftchild, str+ '0');
		traverse(new_tree.rightchild, str+ '1');
	}
}


#endif


 // *** HEAPS CLASS *** 


#ifndef heap_h
#define heap_h
#define ascii_size     257


class heap{
public:
	heap();  // default constructor 
	heap(tree the_tree);  // construct heap from a one element tree 
	
	 // member functions 

	int size() { return length; }  // done 
	void add(tree * the_tree);
	void add(tree the_tree);
	tree min() { return heap_data[1]; }
	void remove();  // removes top (smallest element) of a tree 
	


private:
        int length;
        tree heap_data[ascii_size];

};

heap::heap(){
	length = 0;
}


heap::heap(tree the_tree){
	length = 1;
	heap_data[1] = the_tree;

}


void heap::add(tree the_tree){

	unsigned int position = length+1;
        int data = the_tree.root();
         // bubble the tree up to where it belongs.. 

        while( position > 1 && data < heap_data[(position)/2].root()){
                heap_data[position] = heap_data[(position)/2];
                position = (position)/2;
        }
 	heap_data[position] = the_tree;
        length++;
}

void heap::add(tree * the_tree){
	unsigned int position = length+1;	
	tree new_tree = *the_tree;
	int data = new_tree.root();
	 // bubble the tree up to where itbelongs.. 
		
	while( position > 1 && data < heap_data[(position)/2].root()){
		heap_data[position] = heap_data[(position)/2];
		position = (position)/2;
	}
	
	 // if the data (the value of the tree we are adding) is less than 
	 // that of the parent of the first open spot in the heap, it puts 
	 // the parent in the first open spot in the heap. 
	 // then it checks the parent of that.. if there is no parent, then 
	 // the loop terminates, and the new root of the heap is the_tree. 
	 // if there is a parent, then it see's whether or not data is smaller 
	 // than this parent..  if not, then data is that position (above its 
	 // old parent.  

	heap_data[position]=new_tree;	
	length++;
}

void heap::remove(){
	unsigned int root = 1;
	heap_data[1] = heap_data[length];
	
	tree tmp_tree = heap_data[1];
	unsigned int place = root+1;
	length--;
	while (place <= length){
		if (place < length && heap_data[place] > heap_data[place+1]){
				place++;
		}
		if (tmp_tree < heap_data[place]){	
				break;
		}
		else{   	
				heap_data[(place)/2] = heap_data[place];
				place = 2*place;
		}
	
	}
	heap_data[(place)/2] = tmp_tree; 
	
}

#endif

tree pop(heap &the_heap);
string get_input();

void main(int argc, char* argv[]){
	ofstream out_file, delete_file;
	out_file.open("outfile.dat", ios::trunc);
	out_file.close();
	 // This deletes outfile.dat so it can be re-written 

	int i;
	/* declare objects */
	ifstream in_file;
	
	/* open the file for input  */
	in_file.open(argv[1]);
	if (in_file.fail()) {
	        cout << "Input file " << argv[1] << " failed to open." << endl;
	        exit(1);
        }

	string buffer;

	heap hef;
	string input;
	int * freq_tab = new int[256];
	int temp_int;
	getline(in_file, input, '\n');
	while(!in_file.eof()){
		for(int i=0; input[i]!='\0'; i++){
			temp_int=input[i];
			freq_tab[temp_int]++;

		}
		getline(in_file, input, '\n');
	}

	for(int i=0; i<256; i++){
		char temp_char;
		if(freq_tab[i]!=0) {
			temp_char =i;
			tree temp_tree(freq_tab[i], temp_char);
			hef.add(temp_tree);
		}
	
	}
	
	int size=hef.size();

	for(int i=0; i<size; i++){
		temp_int=0;
		if(hef.size()>1){
			tree *temp1= new tree(pop(hef));
			tree *temp2= new tree(pop(hef));
			tree temp4(*temp1);
			temp_int+=temp4.root();
			tree temp5(*temp2);
			temp_int+=temp5.root();
			tree *temp3= new tree(temp_int, temp1, temp2);
			hef.add(temp3);	
		}
	}

	cout << endl << endl;
	string newstring="";
	tree *huffman = new tree(pop(hef));
	tree huffm1(*huffman);
	huffm1.traverse(huffman, newstring);
	cout << "Huffman bit table successfully output to outfile.dat" << endl;
}

tree pop(heap &the_heap){

	if(the_heap.size() == 0){
		cout << "Popping empty heap.. No good" << endl;
		tree a;
		return a;
	}
	
	tree tmp(the_heap.min());
	the_heap.remove();
	return tmp;
}

string get_input(){

	string a;
	char * array = new char[30];
	cout << "Input a string of any length " << endl;
	cin.getline(array , 30 );
	a=array;
	return a;
}