huf_methods.h

huffman_template_algorithm.zip

// ==============================================================
//
//  Copyright (c) 1999-2001 by Alex Vinokur.  This work and all works
//  derived from it may be copied and modified without any
//  restrictions other than that a copy of this copyright notice
//  must be included in any copy of this work or any derived work.
//
// ==============================================================

///////////////////////////////////////

#ifndef huf_methods_H
#define huf_methods_H

///////////////////////////////////////

static char id_huf_methods_H[] = "@(#)## n-ary Huffman Template Algorithm ## Author : Alex Vinokur ## "__FILE__;

// ##############################################################
// =============================
//  n-ary Huffman Template Algorithm
//  The algorithm (program) contains the following files :
//  - huf_service.H
//  - huf_class.H
//  - huf_methods.H
//  - huf_main.C
// =============================
//
//  FILE : huf_methods.H
//
//  AUTHOR : Alex Vinokur
//
//  DESCRIPTION :
//         Implementation of methods of the following template classes :
//         ----------------------------------------------
//         - Cell                         <SYMBOL, WEIGHT>
//         - Node                         <SYMBOL, WEIGHT>
//         - InternalNode                 <SYMBOL, WEIGHT>
//         - TerminalNode                 <SYMBOL, WEIGHT>
//         - BasicHuffmanTree             <SYMBOL, WEIGHT, ARY>
//         - DriedHuffmanTree             <WEIGHT, ARY>
//         ----------------------------------------------
//	   Note. The following class has no its own methods :
//         - LoadedHuffmanTree            <SYMBOL, WEIGHT, ARY>
//         ----------------------------------------------
//
//  DATE           VERSION
//  ----           -------
//  Aug-26-1999    NHTA 1.0
//  Jul-05-2001    NHTA 1.1
//  Sep-11-2001    NHTA 1.2
//
// ##############################################################



//=====================
#include "huf_class.H"
//=====================




//#######################################################
//##### PART : template class Cell ######################
//############ Methods ##################################
//#######################################################

//-----------------------
// Constructor
template <typename SYMBOL, typename WEIGHT>
Cell<SYMBOL, WEIGHT>::Cell (
                        const SYMBOL&   data_symbol_i,
                        const WEIGHT&   data_weight_i,
                        unsigned int    symbol_original_index_i
                        )
{
        data_symbol_            = data_symbol_i;
        data_weight_            = data_weight_i;
        symbol_original_index_  = symbol_original_index_i;
} // Cell<SYMBOL, WEIGHT>::Cell (


//-----------------------
template <typename SYMBOL, typename WEIGHT>
istream& operator>>(istream &stream_o, Cell<SYMBOL, WEIGHT>& instance_i)
{
        stream_o >> instance_i.data_symbol_ >> instance_i.data_weight_;
        return stream_o;
}





//#######################################################
//##### PART : template class Node ######################
//############ Methods ##################################
//#######################################################

//-----------------------
template <typename SYMBOL, typename WEIGHT>
ostream& operator<<(ostream &str_o, const Node<SYMBOL, WEIGHT>& instance_i)
{
const string shift_CNS = "\t---> ";
        return str_o << endl
                     << shift_CNS
                     << "weight_ = "
                     << instance_i.weight_
                     << gstr_map (instance_i.mapSymbols_, shift_CNS);
}





//#######################################################
//##### PART : template class InternalNode ##############
//############ Methods ##################################
//#######################################################

//-----------------------
template <typename SYMBOL, typename WEIGHT>
void InternalNode<SYMBOL, WEIGHT>::addNode(Node<SYMBOL, WEIGHT> const * const ptr2_i)
{
SYMBOL  cur_symbol;
WEIGHT  cur_weight;

Node_MAP_SYMBOLS::const_iterator                const_iterSymbols;


        ASSERT (!(ptr2_i == NULL));

        //=============== ptr2 =====================
        weight_ += ptr2_i->weight_;

        for (const_iterSymbols = ptr2_i->mapSymbols_.begin();
             !(const_iterSymbols == ptr2_i->mapSymbols_.end());
             const_iterSymbols++
             )
        {
                cur_symbol = (*const_iterSymbols).first;
                cur_weight = (*const_iterSymbols).second;
                //==========================================
                ASSERT (!mapSymbols_.count (cur_symbol));
                //==========================================
                if (!((mapSymbols_.insert (Node_MAP_SYMBOLS::value_type (cur_symbol, cur_weight))).second))
                {
                        ASSERT (0);
                }
                //==========================================
        }


} // void InternalNode<SYMBOL, WEIGHT>::addNode(





//#######################################################
//##### PART : template class TerminalNode ##############
//############ Methods ##################################
//#######################################################

//-----------------------
// Constructor
template <typename SYMBOL, typename WEIGHT>
TerminalNode<SYMBOL, WEIGHT>::TerminalNode (const Cell<SYMBOL, WEIGHT>& cell_i)
{
        //==========================================
        is_TerminalNode_ = true;
        //==========================================
        ASSERT (!mapSymbols_.count (cell_i.data_symbol_));

        weight_ = cell_i.data_weight_;
        if (!((mapSymbols_.insert (Node_MAP_SYMBOLS::value_type (cell_i.data_symbol_, weight_))).second))
        {
                ASSERT (0);
        }

} // TerminalNode<SYMBOL, WEIGHT>::TerminalNode





//#######################################################
//##### PART : template class BasicHuffmanTree ##########
//############ Methods ##################################
//#######################################################

//-----------------------
// Constructor-1
template <typename SYMBOL, typename WEIGHT, unsigned int ARY>
BasicHuffmanTree<SYMBOL, WEIGHT, ARY>::BasicHuffmanTree (
                        const vector<Cell<SYMBOL, WEIGHT> >& data_vector_i
                        )
{
        doBasicHuffmanTree (data_vector_i);

} // BasicHuffmanTree<SYMBOL, WEIGHT, ARY>::BasicHuffmanTree ()


//-----------------------
// Constructor-2
template <typename SYMBOL, typename WEIGHT, unsigned int ARY>
BasicHuffmanTree<SYMBOL, WEIGHT, ARY>::BasicHuffmanTree (const string& data_file_name_i)
{
vector<Cell<SYMBOL, WEIGHT> >   data_vector;

ifstream fin (data_file_name_i.c_str ());

        if (!fin)
        {
                FATAL_MSG ("Cannot open file <"
                            << data_file_name_i
                            << "> for reading"
                            << endl
                            << FATAL_SHIFT
                            << "The file must contain data to be Huffman-coded"
                            );
        }

        copy(istream_iterator<Cell<SYMBOL, WEIGHT> >(fin),
             istream_iterator<Cell<SYMBOL, WEIGHT> >(),
             back_inserter(data_vector));

        doBasicHuffmanTree (data_vector);
} // BasicHuffmanTree<SYMBOL, WEIGHT, ARY>::BasicHuffmanTree ()



//-----------------------
template <typename SYMBOL, typename WEIGHT, unsigned int ARY>
void BasicHuffmanTree<SYMBOL, WEIGHT, ARY>::doBasicHuffmanTree (
                        const vector<Cell<SYMBOL, WEIGHT> >& data_vector_i
                        )
{
        if (!(ARY >= 2))
        {
                FATAL_MSG ("Illegal ARY - "
                            << ARY
                            << " (Must be >= 2)"
                            );
        }

        switch (data_vector_i.size ())
        {
                case 0 :
                        FATAL_MSG ("Empty alphabet"
                                    << endl
                                    << FATAL_SHIFT
                                    << "Alphabet size must be >= 2"
                                    );
                        break;

                case 1 :
                        FATAL_MSG ("Alphabet size = "
                                    << data_vector_i.size ()
                                    << endl
                                    << FATAL_SHIFT
                                    << "Alphabet size must be >= 2"
                                    );
                        break;

                default :
                        break;
        } // switch


        ASSERT (ARY >= 2);
        if (!((data_vector_i.size () - 1)%(ARY - 1) == 0))
        {
                FATAL_MSG ("Illegal alphabet size (N = "
                            << data_vector_i.size ()
                            << ") for "
                            << ARY
                            << "-ary tree."
                            << endl
                            << FATAL_SHIFT
                            << "N must satisfy the following condition : (N - 1) mod ("
                            << (ARY - 1)
                            << ") = 0"
                            << endl
                            << FATAL_SHIFT
                            << "In reality "
                            << (data_vector_i.size () - 1)
                            << " mod ("
                            << (ARY - 1)
                            << ")"
                            << " = "
                            << ((data_vector_i.size () - 1)%(ARY - 1))
                            );
        }

        ASSERT (data_vector_i.size () > 1);

        ASSERT ((data_vector_i.size () - 1)%(ARY - 1) == 0);

        //=================
vector<Node<SYMBOL, WEIGHT>*>           vectorHuffmanProcess;

        createAllTerminalNodes (data_vector_i, vectorHuffmanProcess);
        createHuffmanTree (vectorHuffmanProcess);
        storeHuffmanCodes ();

        //=================
InternalNode<SYMBOL, WEIGHT>*           ptrRootNode;
        ASSERT (vectorHuffmanProcess.size () == 1);
        ptrRootNode = dynamic_cast<InternalNode<SYMBOL, WEIGHT>*> (vectorHuffmanProcess [0]);
        ASSERT (!(ptrRootNode == NULL));
        //=================
        rootNode_ = *ptrRootNode;
        //=================
        delete (vectorHuffmanProcess [0]);
        //=================
        ASSERT (testAllCodes ());
        //=================
        ASSERT (mapAlphabet_.size () == mapHuffmanCodes_.size ());
        ASSERT (mapAlphabet_.size () == vectorHuffmanCodes_.size ());
        ASSERT (mapHuffmanCodes_.size () == vectorHuffmanCodes_.size ());
        //=================
} // BasicHuffmanTree<SYMBOL, WEIGHT, ARY>::doBasicHuffmanTree ()