#include <cstdlib>
#include <iostream>
#include <map>
#include <vector>
#include <string.h>
#include <algorithm>

#define DEBUG true

#define MAX_SIZE 1024

using namespace std;

char plano[MAX_SIZE];

string codificado;

struct node {

	char content;

	string code;

	int frecuencia;

	node *left;

	node *right;

	bool operator <(const node & nodo) const {

		return frecuencia < nodo.frecuencia;

}};

vector < node > nodos;
vector < node > imprimible;
map < char, string > codigos;

void printTrees()
{

	int i, size;

	size = nodos.size();

	for (i = 0; i < size; i++) {

		cout << nodos[i].content << ":" << nodos[i].frecuencia << " | ";

	}

	cout << endl;

}

/*Buscamos el nodo con menor frecuencia
*/
int findMin()
{

	return 0;//Desde que lo ordenamos. En fin, retriste maestro

}

/*Convertimos el monton de nodos en un arbol huffman
*/
node getHuffmanTree()
{

	node *nuevo = new node;

	node *hijo_izquierdo, *hijo_derecho;

	int menor;

	while (!nodos.empty()) {

		//Los dos nuevos hijos deben ser los mas pequeños de la camada
		menor = findMin();

		hijo_izquierdo = new node(nodos[menor]);

		nodos.erase(nodos.begin() + menor);

		menor = findMin();

		hijo_derecho = new node(nodos[menor]);

		nodos.erase(nodos.begin() + menor);

		if (DEBUG) {

			//cout<<endl<<"Insertamos "<<hijo_izquierdo->content<<":"<<hijo_izquierdo->frecuencia<<" y 
"<<hijo_derecho->content<<":"<<hijo_derecho->frecuencia<<endl;
			/*int frecuencia=(int) nodos.size()*3;
			   for (int i=0; i<(frecuencia-9); i++) cout<<"--";
			   cout<<">"<<endl; */
		}
		//Ahora los insertamos
		nuevo->left = hijo_izquierdo;

		nuevo->right = hijo_derecho;

		nuevo->frecuencia = hijo_izquierdo->frecuencia + hijo_derecho->frecuencia;

		nuevo->content = '*';

		nodos.push_back(*nuevo);

		sort(nodos.begin(), nodos.end());

		if (DEBUG)
			printTrees();

		//Si ya solo hay uno, es que ya terminamos
		if (nodos.size() == 1)
			break;

	}

	return nodos[0];

}
/*Creacion de la tabla de codigos
*/
void makeCode(node * root)
{				//Una bonita busqueda en un arbol binario... que chulo :(
	node *local = new node;

	string codigo;

	local = root;

	double porcentaje;
	
	vector<node>::iterator end;

	codigo = root->code;

	if (local != NULL) {	//si el nodo esta vacio, no hay nada que hacer
		//if (local->left == NULL && local->right == NULL)
		if (local->content != '*') {	//Ya terminamos!
			//codigos.push_back(*local);
			codigos[local->content]=local->code;
			end=imprimible.end();
			imprimible.insert(end, *local);

			if (DEBUG) {

				/*porcentaje = (double) (local->frecuencia * 100) / (double) strlen (plano);
				   cout << local->content << "\t=>\t" << local->code << "\t=>\t" << porcentaje<< "%" << endl; */

			}

		} else {

			if (local->left != NULL) {

				local->left->code = codigo + "0";

				makeCode(local->left);

			}

			if (local->right != NULL) {

				local->right->code = codigo + "1";

				makeCode(local->right);

			}

		}

	}

}

/*La creada de los nodos
*/
void createNodes(char caracter)
{

	struct node nodo;

	vector < node >::iterator i;

	nodo.content = caracter;

	nodo.frecuencia = 1;

	i = nodos.end();

	nodos.insert(i, nodo);

}

/*Nomas jalamos el codigo de la tabla de codigos
*/
void Encode()
{

	int i, size;

	codificado = "";

	size = strlen(plano);

	for (i = 0; i < size; i++) {

		codificado.append(codigos[plano[i]]);

	}

}

//Buscamos un caracter dado en la lista de nodos
int findChar(char caracter)
{

	int i, size;

	size = nodos.size();

	for (i = 0; i < size; i++) {

		if (nodos[i].content == caracter)
			return i;

	}

	return -1;

}

/*Mapeamos cada caracter a su frecuencia
*/
void mapChar()
{

	int size, i, pos;

	size = strlen(plano);

	for (i = 0; i < size; i++) {

		pos = findChar(plano[i]);

		if (pos == -1) {	//Si no lo hemos visto, lo creamos
			createNodes(plano[i]);

		} else {	// De otro modo, incrementamos la frecuencia en 1
			nodos[pos].frecuencia++;

		}

	}

}

void printTableCode()
{
	int i, size, mensaje;
	double porcentaje;

	mensaje=strlen(plano);
	size=imprimible.size();
	sort(imprimible.rbegin(), imprimible.rend());
	for(i=0; i<size; i++){
		porcentaje=(double) imprimible[i].frecuencia*100.0/mensaje;
		cout<<imprimible[i].content<<"\t=>\t"<<imprimible[i].code<<"\t=>\t"<<porcentaje<<"%"<<endl;
	}
}

int main(int argc, char *argv[])
{

	node root;

	cout << "Dame el mensaje que comprimiremos" << endl;

	cin.getline(plano, MAX_SIZE - 1, '\n');

	mapChar();

	sort(nodos.begin(), nodos.end());

	printTrees();

	root = getHuffmanTree();

	root.code = "";
	makeCode(&root);
	printTableCode();

	Encode();
	cout << "El texto codificado es: " << codificado << endl;
	system ("PAUSE");

	return EXIT_SUCCESS;

}