Huffman.H

/*
  This file is part of Aleph system

  Copyright (c) 2002, 2003, 2004, 2005, 2006
  UNIVERSITY LOS ANDES (ULA) Merida - REPÚBLICA BOLIVARIANA DE VENEZUELA  

  - Center of Studies in Microelectronics & Distributed Systems (CEMISID) 
  - ULA Computer Science Department
  - FUNDACITE Mérida - Ministerio de Ciencia y Tecnología

  PERMISSION TO USE, COPY, MODIFY AND DISTRIBUTE THIS SOFTWARE AND ITS
  DOCUMENTATION IS HEREBY GRANTED, PROVIDED THAT BOTH THE COPYRIGHT
  NOTICE AND THIS PERMISSION NOTICE APPEAR IN ALL COPIES OF THE
  SOFTWARE, DERIVATIVE WORKS OR MODIFIED VERSIONS, AND ANY PORTIONS
  THEREOF, AND THAT BOTH NOTICES APPEAR IN SUPPORTING DOCUMENTATION.

  Aleph is distributed in the hope that it will be useful, but WITHOUT
  ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
  or FITNESS FOR A PARTICULAR PURPOSE.

  UNIVERSIDAD DE LOS ANDES requests users of this software to return to 

  Leandro Leon
  CEMISID 
  Ed La Hechicera 
  3er piso, ala sur
  Facultad de Ingenieria 
  Universidad de Los Andes 
  Merida - REPÚBLICA BOLIVARIANA DE VENEZUELA    or

  lrleon@ula.ve

  any improvements or extensions that they make and grant Universidad 
  de Los Andes (ULA) the rights to redistribute these changes. 

  Aleph is (or was) granted by: 
  - Consejo de Desarrollo Cientifico, Humanistico, Tecnico de la ULA 
    (CDCHT)
  - Fundacite Mérida
*/


# ifndef HUFFMAN_H
# define HUFFMAN_H

# include <memory>
# include <autosprintf.h>
# include <tpl_treap.H>
# include <tpl_binHeap.H>
# include <tpl_dynMapTree.H>
# include <bitArray.H>

namespace Aleph {

class Huffman_Node;

typedef DynMapTree<Treap_Vtl, string, Huffman_Node *> Symbol_Map;
typedef BinNode< Aleph::pair<string, size_t> > Freq_Node;

struct Huffman_Node : public BinHeap<size_t>::Node
{
  BinNode<string> * bin_node; 

  Freq_Node * freq_node;

  Huffman_Node() : BinHeap<size_t>::Node(0), bin_node(NULL), freq_node(NULL) 
  {
    /* empty */ 
  }

  Huffman_Node(BinNode<string> * node) 
    : BinHeap<size_t>::Node(0), bin_node(node), freq_node(NULL)
  {
    /* empty */
  }

  ~Huffman_Node() { /* No debe liberarse memoria de bin_node */ }

};
typedef BinHeap<size_t> Huffman_Heap;
static inline const size_t & get_freq(Huffman_Node * huffman_node)

{
  return huffman_node->get_key();
}

static inline void increase_freq(Huffman_Node * huffman_node)

{
  huffman_node->get_key()++;
}

static inline void set_freq(Huffman_Node * huffman_node, const size_t & freq)

{
  huffman_node->get_key() = freq;
}

typedef DynMapTree<Treap_Vtl, string, BitArray> Code_Map;
static inline bool is_leaf(BinNode<string> * p)
{
  return LLINK(p) == NULL and RLINK(p) == NULL;
}

class Huffman_Encoder_Engine
{
  BinNode<string> * root; 
  Huffman_Heap heap;
  Symbol_Map   symbol_map; 
  Code_Map code_map;

  Freq_Node * freq_root;

  string end_symbol;
  size_t text_len;
  void build_prefix_encoding(BinNode<string> * root, 
                             BitArray &        array, 
                             const size_t &    len)
  {
    if (is_leaf(root))
      {
        string & str = root->get_key();

        code_map.insert(str, BitArray(array, len));

        return;
      }

    array[len] = 0; // ir hacia la izquierda
    build_prefix_encoding(LLINK(root), array, len + 1);

    array[len] = 1; // ir hacia la derecha
    build_prefix_encoding(RLINK(root), array, len + 1);
  }
  void build_encoding_map()
  {

    I(symbol_map.size() > 0);

    if (root == NULL)
      throw domain_error("Huffman encoding tree has not been generated");

    const size_t h = computeHeightRec(root);
    BitArray array(h * symbol_map.size());
    symbol_map.empty();
    build_prefix_encoding(root, array, 0);
  }
  bool test_end(const string & str) const
  {
    if (end_symbol == "NO-END")
      return false;

    return end_symbol == str;
  }
  void update_freq(const string & str)
  {

    if (root != NULL)
      throw domain_error("Huffman encoding tree has already been generated");

    if (test_end(str))
      throw domain_error("End symbol has already been inserted");

    Huffman_Node * huffman_node = NULL;

    Huffman_Node ** huffman_node_ptr = symbol_map.test(str);

    if (huffman_node_ptr == NULL) // ¿Fue definido previamente el símbolo?
      { // No ==> crear una entrada en symbol_map e insertarlo en heap
        auto_ptr<BinNode<string> > bin_node_auto ( new BinNode<string> (str) );

        huffman_node = static_cast<Huffman_Node*>
          (heap.insert(new Huffman_Node(bin_node_auto.get())));

        symbol_map.insert(str, huffman_node);

        bin_node_auto.release();
      }
    else
      huffman_node = *huffman_node_ptr; // Ya definido, recuperarlo

    increase_freq(huffman_node); 

    heap.update(huffman_node);
  }
  static void append_code(BitArray & bit_stream, size_t & bit_stream_len,
                          const BitArray & symbol_code)
  {
    const size_t symbol_code_size = symbol_code.size();

    if (bit_stream_len + symbol_code_size > bit_stream.size())

      {

      bit_stream.resize(5 * (bit_stream_len + symbol_code_size) / 4);

        I(bit_stream_len + symbol_code_size < bit_stream.size());
      }

        
    for (int i = 0; i < symbol_code_size; i++) 
      bit_stream[bit_stream_len++] = symbol_code[i];
  }
  public:
  Huffman_Encoder_Engine() 
    : root(NULL), freq_root(NULL), end_symbol("NO-END"), text_len(0)
  {
    // empty
  }
  BinNode<string> * get_root() 
  {
    if (root == NULL)
      throw std::domain_error("Huffman tree has not been generated");

    return root; 
  }
  BinNode<string> * generate_huffman_tree(

  const bool & with_freqs = false

                                          ) 
  {
    while (heap.size() > 1)
      {
        Huffman_Node * l_huffman_node = // nodo izquierdo
          static_cast <Huffman_Node *> (heap.getMin());

        Huffman_Node * r_huffman_node = // nodo derecho
          static_cast <Huffman_Node *> (heap.getMin());
        BinNode <string> * bin_node = new BinNode <string>;
        Huffman_Node * huffman_node = new Huffman_Node (bin_node);

        LLINK(bin_node) = l_huffman_node->bin_node;
        RLINK(bin_node) = r_huffman_node->bin_node;

        const size_t new_freq = get_freq(l_huffman_node) + get_freq(r_huffman_node);

        Aleph::set_freq(huffman_node, new_freq);

        if (with_freqs)
          {
            Freq_Node *& l_freq_node = l_huffman_node->freq_node;

            if (l_freq_node == NULL)
              {
                l_freq_node                    = new Freq_Node;
                l_freq_node->get_key().first   = 
                  l_huffman_node->bin_node->get_key();
                l_freq_node->get_key().second = l_huffman_node->get_key();
              }

            Freq_Node *& r_freq_node = r_huffman_node->freq_node;

            if (r_freq_node == NULL)
              {
                r_freq_node                    = new Freq_Node;
                r_freq_node->get_key().first   = 
                  r_huffman_node->bin_node->get_key();
                r_freq_node->get_key().second = r_huffman_node->get_key();
              }

            const string str = gnu::autosprintf ("%d", new_freq);

            Freq_Node *& freq_node      = huffman_node->freq_node;
            freq_node                   = new Freq_Node;
            freq_node->get_key().first  = str;
            freq_node->get_key().second = huffman_node->get_key();
            LLINK(freq_node)            = l_freq_node;
            RLINK(freq_node)            = r_freq_node;
          }

        delete l_huffman_node;
        delete r_huffman_node;

        heap.insert(huffman_node);
      } // Al salir del while,  queda en el heap un solo nodo que contiene
        // la raíz del árbol de prefijos  
    
    Huffman_Node * huffman_root = static_cast <Huffman_Node *> (heap.getMin());

    root = huffman_root->bin_node;

    if (with_freqs)
      freq_root = huffman_root->freq_node;

    delete huffman_root;

    build_encoding_map(); // construir mapeo de códigos

    return root;
  }
  Freq_Node * get_freq_root() 
  { 
    if (freq_root == NULL)
      throw std::domain_error("Huffman tree has not been generated");

    return freq_root; 
  }
  void set_freq(const string & str, const size_t & freq)

  {
    if (root != NULL)
      throw domain_error("Huffman encoding tree has already been generated");

    if (test_end(str))
      throw domain_error("End symbol has already been inserted");
       
        // Buscar símbolo str
    Huffman_Node ** huffman_node_ptr = symbol_map.test(str);

    if (huffman_node_ptr != NULL) // ¿ya fue definido?
      throw std::domain_error // Sí ==> esto es un error!
        (gnu::autosprintf("Frequency for symbol %s has already set", 
                          str.c_str()));

    auto_ptr<BinNode<string> > bin_node_auto ( new BinNode<string> (str) );

    Huffman_Node * huffman_node = new Huffman_Node(bin_node_auto.get());

    Aleph::set_freq(huffman_node, freq); 

    heap.insert(huffman_node);

    symbol_map.insert(str, huffman_node);

    bin_node_auto.release();
  }

  private:

    static const size_t Max_Token_Size = 256;

  public:

  void read_input(char * input

  , const bool & with_freqs = false

                  )

  {
    if (root != NULL)
      throw domain_error("Huffman encoding tree has already been generated");

    char * curr_stream = input;
    char curr_token[Max_Token_Size];
    curr_token[1] = '\0';

    while (*curr_stream != '\0')
      {
        curr_token[0] = *curr_stream++; 

        update_freq(curr_token);
        text_len++;
      }

    set_end_of_stream("");
    generate_huffman_tree(with_freqs);
  }
  void read_input(ifstream & input, const bool & with_freqs = false)
  {
    if (root != NULL)
      throw domain_error("Huffman encoding tree has already been generated");

    char curr_token[2];
    curr_token[0] = curr_token[1] = '\0';

    while (not input.eof())
      {
        input.read(curr_token, 1); 

        update_freq(curr_token);
        text_len++;
      }
      
    set_end_of_stream("");
    generate_huffman_tree(with_freqs);
  }

  void set_end_of_stream(const string & str)
  {
    if (test_end(str))
      throw domain_error("End symbol has already been inserted");

    if (root != NULL)
      throw domain_error("Huffman encoding tree has already been generated");

    auto_ptr<BinNode<string> > bin_node_auto ( new BinNode<string> (str) );

    Huffman_Node * huffman_node =  static_cast<Huffman_Node*>
      (heap.insert(new Huffman_Node(bin_node_auto.get())));

    symbol_map.insert(str, huffman_node); 

    bin_node_auto.release();

    end_symbol = str;
  }
  size_t encode(char * input, BitArray & bit_stream)
  {

    if (root == NULL)
      throw std::domain_error("Huffman tree has not been generated");

    char * curr_stream = input;
    char curr_token[Max_Token_Size];
    curr_token[1] = '\0';

    size_t bit_stream_len = 0;

    while (*curr_stream != '\0')
      {
        curr_token[0] = *curr_stream++; 

        append_code(bit_stream, bit_stream_len, code_map[curr_token]);
      }

    append_code(bit_stream, bit_stream_len, code_map[""]);

    return bit_stream_len;
  }

  size_t encode(ifstream & input, BitArray & bit_stream)
  {
    if (root == NULL)
      throw std::domain_error("Huffman tree has not been generated");

    char curr_token[2];
    curr_token[0] = curr_token[1] = '\0';
    size_t bit_stream_len = 0;

    while (not input.eof())
      {
        input.read(curr_token, 1); 

        append_code(bit_stream, bit_stream_len, code_map[curr_token]);
      }

    append_code(bit_stream, bit_stream_len, code_map[""]);

    return bit_stream_len;
  }

};

class Huffman_Decoder_Engine
{
  BinNode<string> * root; 
  string end_symbol;
  public:

  Huffman_Decoder_Engine(BinNode<string> * p, const string & end)
    : root(p), end_symbol(end)
  {
    // empty
  }
  BinNode<string> * get_root() 
  {
    if (root == NULL)
      throw std::domain_error("Huffman tree has not been generated");

    return root; 
  }
  void decode(BitArray &     bit_stream, 
              const size_t & bit_stream_len,
              ostream &      output)
  {
    BinNode<string> * p = root;

    for (int i = 0; i < bit_stream_len; ++i)
      {
        if (bit_stream.read_bit(i) == 0)
          p = LLINK(p);
        else
          p = RLINK(p);


       if (p == NULL)
         throw std::domain_error("Invalid bits sequence");

       if (is_leaf(p)) // ¿es hoja?
         {     // sí ==> escribir smíbolo y reiniciar a raíz
           const string & symbol = p->get_key();
            
           if (symbol == end_symbol) // ¿se alcanza final?
             break;

           output << symbol;

           p = root;
         }
      }
  }
};

} // end namespace Aleph

# endif // HUFFMAN_H

---