huffman_template_algorithm.html

huffman_template_algorithm.zip

                //==========================================
                if (!((mapSymbols_.insert (Node_MAP_SYMBOLS::value_type (cur_symbol, cur_weight))).second))
                {
                        ASSERT (0);
                }
                //==========================================
        }


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




<a NAME="label_TerminalNode_method"></a>
//#######################################################
//##### PART : template class <b><a href="#label_TerminalNode_class">TerminalNode</a></b> ##############
//############ <font color="FF7733"><b>Methods</b></font> ##################################
//#######################################################

//-----------------------
// Constructor
template &lt;typename SYMBOL, typename WEIGHT&gt;
TerminalNode&lt;SYMBOL, WEIGHT&gt;::TerminalNode (const Cell&lt;SYMBOL, WEIGHT&gt;& 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&lt;SYMBOL, WEIGHT&gt;::TerminalNode




<a NAME="label_BasicHuffmanTree_method"></a>
//#######################################################
//##### PART : template class <b><a href="#label_BasicHuffmanTree_class">BasicHuffmanTree</a></b> ##########
//############ <font color="FF7733"><b>Methods</b></font> ##################################
//#######################################################

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

} // BasicHuffmanTree&lt;SYMBOL, WEIGHT, ARY&gt;::BasicHuffmanTree ()


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

ifstream fin (data_file_name_i.c_str ());

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

        copy(istream_iterator&lt;Cell&lt;SYMBOL, WEIGHT&gt; &gt;(fin),
             istream_iterator&lt;Cell&lt;SYMBOL, WEIGHT&gt; &gt;(),
             back_inserter(data_vector));

        doBasicHuffmanTree (data_vector);
} // BasicHuffmanTree&lt;SYMBOL, WEIGHT, ARY&gt;::BasicHuffmanTree ()



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

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

                case 1 :
                        FATAL_MSG ("Alphabet size = "
                                    &lt;&lt; data_vector_i.size ()
                                    &lt;&lt; endl
                                    &lt;&lt; FATAL_SHIFT
                                    &lt;&lt; "Alphabet size must be &gt;= 2"
                                    );
                        break;

                default :
                        break;
        } // switch


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

        ASSERT (data_vector_i.size () &gt; 1);

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

        //=================
vector&lt;Node&lt;SYMBOL, WEIGHT&gt;*&gt;           vectorHuffmanProcess;

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

        //=================
InternalNode&lt;SYMBOL, WEIGHT&gt;*           ptrRootNode;
        ASSERT (vectorHuffmanProcess.size () == 1);
        ptrRootNode = dynamic_cast&lt;InternalNode&lt;SYMBOL, WEIGHT&gt;*&gt; (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&lt;SYMBOL, WEIGHT, ARY&gt;::doBasicHuffmanTree ()




//-----------------------
template &lt;typename SYMBOL, typename WEIGHT, unsigned int ARY&gt;
void BasicHuffmanTree&lt;SYMBOL, WEIGHT, ARY&gt;::createInternalNode (
                                vector&lt;Node&lt;SYMBOL, WEIGHT&gt;*&gt;&  vectorHuffmanProcess_i,
                                int                             cur_stage_i
                                )
{
unsigned int    cur_arc;
map&lt;SYMBOL, WEIGHT, less&lt;SYMBOL&gt; &gt;::iterator    iterSymbols;
InternalNode&lt;SYMBOL, WEIGHT&gt;*   newPtrInternalNode = new InternalNode&lt;SYMBOL, WEIGHT&gt; ();

        ASSERT (!(newPtrInternalNode == NULL));

Node&lt;SYMBOL, WEIGHT&gt;*   front_element;
        ASSERT (newPtrInternalNode-&gt;arc_.empty ());
        for (cur_arc = 0; cur_arc &lt; ARY; cur_arc++)
        {
                front_element = vectorHuffmanProcess_i.front ();
                front_element-&gt;absorbtion_stage_ = cur_stage_i;
                newPtrInternalNode-&gt;addNode (front_element);

                for (iterSymbols = front_element-&gt;mapSymbols_.begin();
                     !(iterSymbols == front_element-&gt;mapSymbols_.end());
                     iterSymbols++
                     )
                {
                        ASSERT (mapAlphabet_.count ((*iterSymbols).first));
                        vector&lt;CODE&gt;& alias_symbol_path = mapAlphabet_ [(*iterSymbols).first].symbol_path_;
                        ASSERT (newPtrInternalNode-&gt;arc_.size () == cur_arc);
                        alias_symbol_path.insert (alias_symbol_path.begin (), newPtrInternalNode-&gt;arc_.size ());
                }
                //=====================================
                vectorHuffmanProcess_i.erase (vectorHuffmanProcess_i.begin ());
                newPtrInternalNode-&gt;creation_stage_ = cur_stage_i;
                newPtrInternalNode-&gt;arc_.push_back (front_element);
                //==========================================
        }
        ASSERT (newPtrInternalNode-&gt;arc_.size () == ARY);

        //==========================================
        vectorHuffmanProcess_i.push_back (newPtrInternalNode);
        stable_sort (vectorHuffmanProcess_i.begin (), vectorHuffmanProcess_i.end (), lessNodesCompare&lt;SYMBOL, WEIGHT&gt; ());
        //==========================================
        ASSERT ((((ARY - 1) * cur_stage_i) + vectorHuffmanProcess_i.size ()) == mapAlphabet_.size ());

        //---------------------

} // void BasicHuffmanTree&lt;SYMBOL, WEIGHT, ARY&gt;::createInternalNode


//-----------------------
template &lt;typename SYMBOL, typename WEIGHT, unsigned int ARY&gt;
void BasicHuffmanTree&lt;SYMBOL, WEIGHT, ARY&gt;::createHuffmanTree (
                                vector&lt;Node&lt;SYMBOL, WEIGHT&gt;*&gt;&  vectorHuffmanProcess_i
                                )
{
#ifdef SHOW_HUFFMAN_PROCESS_STATUS
        showHuffmanProcessStatus (vectorHuffmanProcess_i);
#endif

int cur_stage = 0;
        while (vectorHuffmanProcess_i.size () &gt; 1)
        {
                cur_stage++;
                createInternalNode (vectorHuffmanProcess_i, cur_stage);
                doBeautyTreatment (vectorHuffmanProcess_i);
#ifdef SHOW_HUFFMAN_PROCESS_STATUS
                showHuffmanProcessStatus (vectorHuffmanProcess_i, cur_stage);
#endif
        }
        ASSERT (vectorHuffmanProcess_i.size () == 1);
        ASSERT (!(vectorHuffmanProcess_i [0]-&gt;is_TerminalNode_));

} // void BasicHuffmanTree&lt;SYMBOL, WEIGHT, ARY&gt;::createHuffmanTree ()



//-----------------------
template &lt;typename SYMBOL, typename WEIGHT, unsigned int ARY&gt;
void BasicHuffmanTree&lt;SYMBOL, WEIGHT, ARY&gt;::doBeautyTreatment (
                                vector&lt;Node&lt;SYMBOL, WEIGHT&gt;*&gt;&  vectorHuffmanProcess_i
                                )
{
        ASSERT (!(vectorHuffmanProcess_i.empty ()));
        if (vectorHuffmanProcess_i.size () == 1)
        {
                return;
        }
        stable_sort (vectorHuffmanProcess_i.begin (), vectorHuffmanProcess_i.end (), lessNodesCorrectingCompare01&lt;SYMBOL, WEIGHT&gt; ());
        stable_sort (vectorHuffmanProcess_i.begin (), vectorHuffmanProcess_i.begin () + ARY, lessNodesCorrectingCompare02&lt;SYMBOL, WEIGHT&gt; ());

} // void BasicHuffmanTree&lt;SYMBOL, WEIGHT, ARY&gt;::doBeautyTreatment ()




//-----------------------
template &lt;typename SYMBOL, typename WEIGHT, unsigned int ARY&gt;
void BasicHuffmanTree&lt;SYMBOL, WEIGHT, ARY&gt;::createAllTerminalNodes (
                        const vector&lt;Cell&lt;SYMBOL, WEIGHT&gt; &gt;&    data_vector_i,
                        vector&lt;Node&lt;SYMBOL, WEIGHT&gt;*&gt;&  vectorHuffmanProcess_i
                        )
{
unsigned int    cur_index;
SYMBOL          cur_symbol;
WEIGHT          cur_weight;

        for (cur_index = 0; cur_index &lt; data_vector_i.size (); cur_index++)
        {
                //==========================================
                cur_symbol = data_vector_i [cur_index].data_symbol_;
                cur_weight = data_vector_i [cur_index].data_weight_;
                //==========================================
                if (mapAlphabet_.count(cur_symbol))
                {
                        FATAL_MSG ("Symbol &lt;"
                                    &lt;&lt; cur_symbol
                                    &lt;&lt; "&gt; occurs more than one time"
                                    &lt;&lt; endl
                                    &lt;&lt; FATAL_SHIFT
                                    &lt;&lt; "See symbol ["
                                    &lt;&lt; cur_index
                                    &lt;&lt; "]"
                                    &lt;&lt; " and "
                                    &lt;&lt; "symbol ["
                                    &lt;&lt; (*(mapAlphabet_.find (cur_symbol))).second.symbol_original_index_
                                    &lt;&lt; "]"
                                    &lt;&lt; endl
                                    &lt;&lt; FATAL_SHIFT
                                    &lt;&lt; "Note! First symbol is symbol [0]"
                                    );
                }
                //==========================================
                if (!((mapAlphabet_.insert (Tree_MAP_SYMBOLS::value_type (cur_symbol, Cell&lt;SYMBOL, WEIGHT&gt; (cur_symbol, cur_weight, cur_index)))).second))
                {
                        ASSERT (0);
                }
        } // for (unsigned int i = 0; i &lt; data_vector_i.size (); i++)

        //=====================================
TerminalNode&lt;SYMBOL, WEIG