#include <queue>     // priority_queue
#include <stdexcept> // out_of_range
#include <algorithm> // reverse

using namespace std;

#include "Huffman.h"

Huffman::Nodo::Nodo(char c, float f)
  : caracter{c}, frecuencia{f}, izquierdo{nullptr}, derecho{nullptr}, padre{nullptr} {
}

Huffman::Huffman(const vector< pair<char, float> > & frecuencias) {

   if (frecuencias.size() < 2)
      throw string("Necesitamos al menos dos caracteres con sus frecuencias.");

   class ComparadorNodos {
   public:
      bool operator() (Nodo * n1, Nodo * n2) const {
	 return n1->frecuencia > n2->frecuencia; // Para que salgan de la cola de prioridad de menor a mayor
      }
   };
  
   priority_queue<Nodo *, vector<Nodo *>, ComparadorNodos> colaPrioridad;
  
   for (auto dato : frecuencias) {
      Nodo * hoja = new Nodo(dato.first, dato.second);
      colaPrioridad.push(hoja);
      hojas[dato.first] = hoja;
   }
  
   while (colaPrioridad.size() > 1) {
      Nodo * n = new Nodo(' ', 0);
      n->izquierdo = colaPrioridad.top();
      colaPrioridad.pop();
      n->derecho = colaPrioridad.top();
      colaPrioridad.pop();
      n->frecuencia = n->izquierdo->frecuencia + n->derecho->frecuencia;
      n->izquierdo->padre = n;
      n->izquierdo->bit = '0';
      n->derecho->padre = n;
      n->derecho->bit = '1';
      colaPrioridad.push(n);
   }
   raiz = colaPrioridad.top();

}

string Huffman::codificar(const string & mensaje) const {
  
   string mensajeCodificado, caracterCodificado;
   Nodo * n;

   for (char caracter : mensaje) {
      try {
	 n = hojas.at(caracter);
      } catch(out_of_range e) {
	 throw string("El mensaje a codificar contiene algun caracter que no estaba ")
	       + string("en la tabla de frecuencias inicial (") + caracter + ").";
      }
      caracterCodificado = "";
      while (n->padre != nullptr) {
	 caracterCodificado += n->bit;
	 // Valdria caracterCodificado = n->bit + caracterCodificado pero seria menos eficiente
	 // Por eso usamos asi += y despues invertimos la cadena con reverse
	 n = n->padre;
      }
      reverse(caracterCodificado.begin(), caracterCodificado.end());
      mensajeCodificado += caracterCodificado;
   }

   return mensajeCodificado;

}

string Huffman::decodificar(const string & mensajeCodificado) const {
  
   string mensajeOriginal;
   Nodo * n = raiz;
  
   for (char caracter : mensajeCodificado) {
      if (caracter == '0')
	 n = n->izquierdo;
      else
	 n = n->derecho;
      if (n->izquierdo == nullptr) { // Hemos alcanzado nodo hoja
	 mensajeOriginal += n->caracter;
	 n = raiz;
      }
   }
  
   return mensajeOriginal;

}