#include <bits/stdc++.h>

using namespace std;

// este programa usa Huffman para comprimir archivos de texto
// solo usa el codigo ascii estandar

struct Codigo{
	int bits; // codigo, por ejemplo "10110" que equivale a 22 en binario
	int len; // n bits tomados desde la derecha 
};

struct Nodo{
	int frecuencia;
	int father;
	int left;
	int right;
	bool isleft; // en vez de esta bandera, podría tomarse en el campo de frecuencia un signo positivo para la derecha y un signo negativo para la izquierda
};

// mensaje
char mensaje[1000];
char mensaje_descomp[1000];
int len_mensaje;
// arbol de huffman
struct Nodo arbol[255]; // arbol
char alfabeto[128]; /// en este programa no es necesario, porque es el codigo ascii
struct Codigo codigos[128]; // codigos que genera este programa
int pq; // apuntador a la cola de prioridad
int pQueue[128]; // se usa para ir obteniendo siempre el par de elementos que aparecen con menor frecuencia
// mensaje comprimido
unsigned char comprimido[1000];
int cantidad_bits;

// Cola de prioridad
void pqinsert(int valor){ // Agrega un valor a la pQueue
    pQueue[++pq] = valor;
}

int pqmindelete(){ // Quita el siguiente valor (el de menor  tamaño) y lo devuelve
    int min, valor;
    min = 0;
    for(int i=1; i<=pq; i++) // busca y toma el menor de todos
		if(arbol[pQueue[i]].frecuencia < arbol[pQueue[min]].frecuencia) {
			min = i; 
		}
    valor = pQueue[min];
    pQueue[min] = pQueue[pq--];
    return valor;
}

/// rutina para ver como quedaron los códigos
void Ver_Codigos(){
	int c;
	cout << "\n\n";
	// imprime el codigo
	for(int i=0; i<128; i++){
		if(arbol[i].frecuencia>0){
			cout << alfabeto[i] << "  " << arbol[i].frecuencia << "  ";
			for(int k=codigos[i].len; k>0; k--){
				if(codigos[i].bits & (1<<(k-1))) cout << 1;
				else cout << 0;
			}
			cout << "\n";
		}
	}	
}

void Ver_Mensaje_Comprimido(){
	int f = 0;
	int bit = 128;
	
	// muestra el mensaje comprimido
	cout << "\n\nTamano comprimido: " << cantidad_bits << " bits\n\n" ;
	for(int i=0; i<cantidad_bits; i++){
		if(comprimido[f]&bit) cout << 1;
		else cout << 0;
		bit/=2;
		if(bit==0){
			bit = 128;
			f++;
		}		
	}

}

void Leer_Mensaje(){
	// Lee el mensaje
	gets(mensaje);
	len_mensaje = strlen(mensaje);
}

void Contar_Frecuencia() {
	// cuenta cuantas veces aparece cada caracter en el mensaje
	for(int i=0; i<len_mensaje; i++){
		arbol[mensaje[i]].frecuencia++;		
	}
}

int main() {
	int rootnodes = 0;
	int p, p1, p2, root;
	pq = -1;
	cantidad_bits = 0;
	
	Leer_Mensaje();
	
    Contar_Frecuencia();
	
	// tamaño original
	cout << "\n\nTamano original: " << len_mensaje*8 << " bits.";
	
	///////////////////////////////////////////////////////
	// prepara el arreglo del alphabeto y la cola de prioridad
	for(int i=0; i<128; i++){
		alfabeto[i] = i; /// en este programa no es necesario, porque es el codigo ascii
		if(arbol[i].frecuencia>0) { // solo toma los caracteres que realmente estan en el mensaje
			pqinsert(i);
		}
	}

	///////////////////////////////////////////////////////
	// construye el arbol
	for(p=128; pq>=1; p++){
		// toma los nodos p1 y p2 con menores frecuencias
		p1 = pqmindelete();
		p2 = pqmindelete();
		// los pone como hijos de un nuevo nodo
		arbol[p1].father = p;
		arbol[p1].isleft = true;
		arbol[p].left = p1;
		arbol[p2].father = p;
		arbol[p2].isleft = false;
		arbol[p].right = p2;
		arbol[p].frecuencia = arbol[p1].frecuencia + arbol[p2].frecuencia;
		pqinsert(p);
	}

	///////////////////////////////////////////////////////
	// extrae los codigos del arbol
	// Esto no es necesario. Solo es para probarlo. Podrían irse tomando 
	// los códigos diretamente desde el árbol
	root = pqmindelete();
	for(int i=0; i<128; i++){
		if(arbol[i].frecuencia>0){
			// sube por el arbol
			p = i;
			while(p!=root){
				// aqui va construyendo el codigo
				if(arbol[p].isleft) /* no le suma nada*/;
				else codigos[i].bits += (1<<codigos[i].len); // le suma un 2^len
				codigos[i].len++;
				p = arbol[p].father;
			} // aqui ya termio de construir el codigo lo copia de la variable al arreglo
		}
	}
	
	Ver_Codigos();
	
	///////////////////////////////////////////////////////
	// Realiza la compresión. 
	int f = 0;
	int bit = 128;
	unsigned char c = 0;
	for(int i=0; i<len_mensaje; i++){ // recorre todo el mensaje
		// toma el código de ese caracter
		for(int k=codigos[mensaje[i]].len; k>0; k--){
			if(codigos[mensaje[i]].bits & (1<<(k-1))) c += bit;
			else c += 0;
			cantidad_bits++;
			bit /= 2;
			if(bit==0) { // ya terminó de llenar todo un byte, lo agrega al mensaje
				comprimido[f++] = c;
				c = 0;
				bit = 128;
			}
		}
	}
	// tal vez aún quedan caracteres por poner en el mensaje comprimido
	if(bit!=128) comprimido[f++] = c;

	Ver_Mensaje_Comprimido();
	
	///////////////////////////////////////////////////////
	// Realiza la descompresión ////////////////////////////
	f = 0;
	bit = 128;
	c = comprimido[f];
	int m = 0;
	while(cantidad_bits>0){
		// recorre el árbol
		p = root;
		while(p>=128) {
			if(c&bit) {	// baja por la derecha
				p = arbol[p].right;
			}
			else {  // baja por la izquierda
				p = arbol[p].left;
			}
			cantidad_bits--;
			bit /= 2;
			if(bit==0){
				c = comprimido[++f];
				bit = 128;
			}
		}
		// ya llegó a una hoja (las hojas están en los primeros 127 posiciones)
		mensaje_descomp[m++] = alfabeto[p];
	}
	
	// muestra el mensaje descomprimido
	cout << "\n\n" << mensaje_descomp;
}