// Arup Guha
// 7/11/03, finished 7/13/03
// Huffman Coding Program Solution for 2003 BHCSI Algorithms Class
// Brief Description: This program takes in a file containing frequency
//                    information of each character from a file and
//                    outputs Huffman codes for each character for that
//                    file into an output file.

#include <iostream.h>
#include <fstream.h>
#include <math.h>

// Stores a node for a binary tree node. Each node stores a character and
// its associated frequency.
struct BTNode {
	char ch;
	int freq;
	BTNode* left;
	BTNode* right;
};

typedef BTNode*	BTNodePtr;

int numdigits(int value);
char* convert(int value);

class Heap {
public:
	Heap();
	void read_file(ifstream &fin);
	void bubbleDown(int i);
	void bubbleUp(int i);
	void makeHeap();
	BTNodePtr removeMin();
	int minChildIndex(int i);
	void makeTree();
	void makeCode();
	void saveCode(BTNodePtr root, int code);
	void writeCodes(ofstream &fout); 

private:
	BTNodePtr *all_trees;
	int size;
	int num_chars;
	int codes[256];	
};

// Default constructor initializes each code to a sentinel value -1 that indicates
// that no code has been assigned to that character.
Heap::Heap() { 
	for (int i=0; i<256; i++)
		codes[i] = -1;
}

// A heap is formed out of the collection of unsorted binary trees.
void Heap::makeHeap() {

	for (int i=size/2; i>0; i--) 
		bubbleDown(i);
}

// Places an element from the top of a heap into its proper location in the heap.
void Heap::bubbleDown(int i) {

	// Potentially loop until we have reached the leaf nodes.
	while (i <= size/2) {

		// Find the child node with the minimum frequency.
		int index_min;
		if (2*i == size)
			index_min = 2*i;
		else
			index_min = minChildIndex(i);

		// Swap nodes if the node in question needs to be.
		if (all_trees[i]->freq > all_trees[index_min]->freq) {

			BTNodePtr temp = all_trees[i];
			all_trees[i] = all_trees[index_min];
			all_trees[index_min] = temp;
			i = index_min;
		}

		// Quit bubbling down the node since it's in the proper location.
		else
			break;
	}
}

// Places an element from the last position in the heap into its proper location.
void Heap::bubbleUp(int i) {

	// Potentially loop until the node is at the top of the heap.
	while (i > 1) {

		// Check if the node in question must be switched with its parent.
		if (all_trees[i]->freq < all_trees[i/2]->freq) {

			BTNodePtr temp = all_trees[i];
			all_trees[i] = all_trees[i/2];
			all_trees[i/2] = temp;
			i = i/2;
		}

		// Quit bubbling up since the node is in its proper location.
		else
			break;
	}
}

// Removes the node with the minimum frequency from the heap.
BTNodePtr Heap::removeMin() {

	// Grab the minimum node.
	BTNodePtr retval = all_trees[1];

	// Place the last node at the top of the heap to replace the deleted node.
	all_trees[1] = all_trees[size];

	// Place this node in its proper location and adjust the size of the heap.
	bubbleDown(1);
	size--;
	return retval;
}

void Heap::makeTree() {

	// Continue merging trees until there is one left.
	while (size > 1) {

		// Remove the two binary trees with the smallest frequencies.
		BTNodePtr left_side = removeMin();
		BTNodePtr right_side = removeMin();
		BTNodePtr merged_tree = new BTNode;

		// Create the newly merged binary tree.
		merged_tree->ch = '\0';
		merged_tree->freq = left_side->freq + right_side->freq;
		merged_tree->left = left_side;
		merged_tree->right = right_side;

		// Add the tree to the end of the heap.
		size++;
		all_trees[size] = merged_tree;

		// Place this node properly into the heap.
		bubbleUp(size);
	}
}

// This method returns the index of the child of the ith node with the minumum
// frequency.
int Heap::minChildIndex(int i) {

	// Compare the frequency of both children and return the proper index.
	if (all_trees[2*i]->freq < all_trees[2*i+1]->freq)
		return 2*i;
	else 
		return 2*i+1;
}

// Reads in the character frequency information from a file into the Heap object.
void Heap::read_file(ifstream &fin) {

	// Find out the size of the initial heap.
	fin >> size;
	num_chars = size;
	all_trees = new BTNodePtr[size+1];
	
	// Insert each element one by one into the heap.
	for (int i=1; i<=size; i++) {

		all_trees[i] = new BTNode;
		int ch, freq;
		fin >> ch >> freq;

		all_trees[i]->ch = ch;
		all_trees[i]->freq = freq;
		all_trees[i]->left = NULL;
		all_trees[i]->right = NULL;
	}
	fin.close();
}

// Save all the Huffman Codes into the array of the current object.
void Heap::saveCode(BTNodePtr root, int code) {

	// Iterate through the nodes in an inorder fashion, adjusting the
	// new code at that node as necessary.
    if (root != NULL) {
		saveCode(root->left, 2*code);
		if (root->ch != '\0')
			codes[(int)root->ch]=code;
		saveCode(root->right, 2*code+1);
	}
}

// Save all the codes from the main merged tree.
void Heap::makeCode() {
	saveCode(all_trees[1], 1);
}

// Returns the number of binary digits necessary to store value.
int numdigits(int value) {

	// Determines how many times 2 divides into value.
	int digits = 0;
	while (value > 1) {
		digits++;
		value /= 2;
	}
	return digits;
}

// Returns a character array that stores the binary string equivalent to value.
char* convert(int value) {

	// Determine the length of the string and initialize it.
	int length = numdigits(value);
	char* number = new char[length+1];
	number[length] = '\0';
	int index = length-1;
	
	// Strip off one digit at a time in reverse order.
	while (value > 1) {
		number[index] = (char)('0'+value%2);
		value = value/2;
		index--;
	}
	
	return number;
}

// Once the codes are saved, this method writes them out to the file pointed to by
// fout.
void Heap::writeCodes(ofstream &fout) {

	// Write out each code.
	fout << num_chars << endl;
	for (int i=0; i<256; i++) {

		// Only write it if the character existed in the file.
		if (codes[i] != -1) {
			fout << (char)i << "\t";
			fout << convert(codes[i]) << endl;
		}
	}
	fout.close();
}

void main() {

	// Get input file name.
	char in_file[20];
	cout << "Enter the file with the character frequencies." << endl;
	cin >> in_file;
	ifstream fin(in_file);

	// Create the heap, then the Huffman Tree, and creates and saves the codes.
	Heap mine;
	mine.read_file(fin);
	mine.makeHeap();
	mine.makeTree();
	mine.makeCode();


	// Get the output file name and write out the necessary information.
	char out_file[20];
	cout << "What file would you like to store the Huffman Codes?" << endl;
	cin >> out_file;
	ofstream fout(out_file);
	mine.writeCodes(fout);
}