//Chad Williamson

#include <iostream> 
#include <fstream> 
#include <string> 
#include <vector> 

struct node {
	node *leftChild;
	node *rightChild;
	node *parent;
	int myASCIIValue;
	int myInputFreq;
	double myNormalizedFreq;
};

struct result {
	std::string charValue; //string type to include LF
	int ascii;
	std::string binValue;
};

//function prototypes
void sortVector(std::vector<node*> &v, int n);
void traverse(node* root, std::string p);
void sortResults(std::vector<result> &r, int n);
//global results vector
std::vector<result> results;

int main(int argc, char* argv[]) {
	//variables used to read input file
	std::ifstream input("freq.txt");
	std::string value;
	std::vector<node*> nodeVec;
	char thisChar;
	std::string freqStr;
	int frequency = 0;
	int ASCIIvalue = 0;
	int inc = 0;
	int totalCharacterCount = 0;
	int numberOfCharsInFile = 0;
	if (input.is_open()) {
		while (std::getline(input, value)) {
			freqStr = "";
			inc = 0;
			if (value[0] == 'L' && value[1] == 'F') {
				ASCIIvalue = 10;
				inc = 2;
				while (inc < value.size()) {
					if (value[inc] != ' '){
						freqStr += value[inc];
					}
					inc++;
				}
			}
			//all other printable characters
			else {
				thisChar = value[0];
				inc = 1;
				while (inc < value.size()) {
					if (value[inc] != ' ') {
						freqStr += value[inc];
					}
					inc++;
				}
				ASCIIvalue = int (thisChar);
			}
			frequency = std::stoi(freqStr);
			totalCharacterCount += frequency;
			node* newNode = new node;
			newNode->myASCIIValue = ASCIIvalue;
			newNode->myInputFreq = frequency;
			newNode->leftChild = NULL;
			newNode->rightChild = NULL;
			newNode->parent = NULL;
			newNode->myNormalizedFreq = 0.0;
			nodeVec.push_back(newNode);
		}//end while 
		input.close();
	} //end of file open
	else { std::cout << "freq.txt not found" << std::endl; }

	//normalize frequencies
	for (auto thisNode = nodeVec.begin(); thisNode != nodeVec.end(); thisNode++) {
		node *curr = *thisNode;
		curr->myNormalizedFreq = (((double)curr->myInputFreq / totalCharacterCount) * 100);
	}

	sortVector(nodeVec, nodeVec.size());
	while (nodeVec.size() > 1) {
		node* buildNode = new node;
		node* leastNode = nodeVec.back();
		nodeVec.pop_back();
		node* nextLeastNode = nodeVec.back();
		nodeVec.pop_back();
		leastNode->parent = buildNode;
		nextLeastNode->parent = buildNode;
		buildNode->leftChild = leastNode;
		buildNode->rightChild = nextLeastNode;
		buildNode->myNormalizedFreq = buildNode->leftChild->myNormalizedFreq + buildNode->rightChild->myNormalizedFreq;
		nodeVec.push_back(buildNode);
		sortVector(nodeVec, nodeVec.size());
	}
	std::string binPath = "";
	traverse(nodeVec[0], binPath);
	sortResults(results, results.size());

	//output
	std::ofstream outFile;
	outFile.open("codetable.txt");
	std::cout << "Char" << "\t" << "ASCII" << "\t" << "Huffman" << std::endl;
	for (auto res = results.begin(); res != results.end(); res++) {
		std::cout << res->charValue << "\t" << res->ascii <<  "\t" << res->binValue << std::endl;
		outFile << res->charValue << "\t" << res->binValue << std::endl;
	}

	std::cout << "\n\nResults written to codetable.txt" << std::endl;
	return 0;
}

//recursive bubble sort. sorts in descending order, ascii tiebreaker 
void sortVector(std::vector<node*> &v, int n) {
	if (n == 1)
		return;
	for (int i = 0; i < n - 1; i++) {
		node* curr = v[i];
		node* next = v[i+1];
		if (curr->myNormalizedFreq < next->myNormalizedFreq) {
			v[i] = next;
			v[i + 1] = curr;
		}
		else if (curr->myNormalizedFreq == next->myNormalizedFreq) {
			if ((curr->myASCIIValue < next->myASCIIValue) && (curr->myASCIIValue > 0) && (next->myASCIIValue > 0)) {
				v[i] = next;
				v[i + 1] = curr;
			}
		}
	}
	sortVector(v, n - 1);
}

//recursive traversal
void traverse(node* root, std::string binPath) {
	std::string bpOnEntry = binPath;
	//std::cout << "HERE" << std::endl;
	if (root->leftChild != NULL) {
		binPath += '0';
		traverse(root->leftChild, binPath);
	}
	binPath = bpOnEntry;
	if (root->rightChild != NULL) {
		binPath += '1';
		traverse(root->rightChild, binPath);
	}
	binPath = bpOnEntry;
	if (root->leftChild == NULL && root->rightChild == NULL) {
		if (root->myASCIIValue != 10) {
			results.push_back(result());
			results[results.size() - 1].ascii = root->myASCIIValue;
			results[results.size() - 1].binValue = binPath;
			results[results.size() - 1].charValue = char(root->myASCIIValue);
		}
		else {
			results.push_back(result());
			results[results.size() - 1].ascii = 10;
			results[results.size() - 1].binValue = binPath;
			results[results.size() - 1].charValue = "LF";
		}
	}
}

//recursive bubble sort. sorts in ascending order
void sortResults(std::vector<result>& r, int n) {
	if (n == 1)
		return;
	for (int i = 0; i < n - 1; i++) {
		result curr = r[i];
		result next = r[i + 1];
		if (curr.ascii > next.ascii) {
			r[i] = next;
			r[i + 1] = curr;
		}
	}
	sortResults(r, n - 1);
}