huf_methods.h

huffman_template_algorithm.zip

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

        ASSERT (!(newPtrInternalNode == NULL));

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

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

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

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

} // void BasicHuffmanTree<SYMBOL, WEIGHT, ARY>::createInternalNode


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

int cur_stage = 0;
        while (vectorHuffmanProcess_i.size () > 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]->is_TerminalNode_));

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



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

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




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

        for (cur_index = 0; cur_index < 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 <"
                                    << cur_symbol
                                    << "> occurs more than one time"
                                    << endl
                                    << FATAL_SHIFT
                                    << "See symbol ["
                                    << cur_index
                                    << "]"
                                    << " and "
                                    << "symbol ["
                                    << (*(mapAlphabet_.find (cur_symbol))).second.symbol_original_index_
                                    << "]"
                                    << endl
                                    << FATAL_SHIFT
                                    << "Note! First symbol is symbol [0]"
                                    );
                }
                //==========================================
                if (!((mapAlphabet_.insert (Tree_MAP_SYMBOLS::value_type (cur_symbol, Cell<SYMBOL, WEIGHT> (cur_symbol, cur_weight, cur_index)))).second))
                {
                        ASSERT (0);
                }
        } // for (unsigned int i = 0; i < data_vector_i.size (); i++)

        //=====================================
TerminalNode<SYMBOL, WEIGHT>*   newPtrTerminalNode;
Tree_MAP_SYMBOLS::iterator      iterAlphabet;
        for (iterAlphabet = mapAlphabet_.begin();
             !(iterAlphabet == mapAlphabet_.end());
             iterAlphabet++
             )
        {
                newPtrTerminalNode = new TerminalNode<SYMBOL, WEIGHT> ((*iterAlphabet).second);
                ASSERT (!(newPtrTerminalNode == NULL));
                newPtrTerminalNode->creation_stage_ = 0;

                vectorHuffmanProcess_i.push_back (newPtrTerminalNode);
        }

        stable_sort (vectorHuffmanProcess_i.begin (), vectorHuffmanProcess_i.end (), lessNodesCompare<SYMBOL, WEIGHT> ());
} // void BasicHuffmanTree<SYMBOL, WEIGHT, ARY>::createAllTerminalNodes




//-----------------------
template <typename SYMBOL, typename WEIGHT, unsigned int ARY>
void BasicHuffmanTree<SYMBOL, WEIGHT, ARY>::storeHuffmanCodes ()
{

Tree_MAP_SYMBOLS::iterator                      iterAlphabet;

        //=====================================
        for (iterAlphabet = mapAlphabet_.begin();
             !(iterAlphabet == mapAlphabet_.end());
             iterAlphabet++
             )
        {
                ASSERT (!mapHuffmanCodes_.count ((*iterAlphabet).second.symbol_path_));
                if (!((mapHuffmanCodes_.insert (Tree_MAP_HUFFMAN_DECODING::value_type ((*iterAlphabet).second.symbol_path_, (*iterAlphabet).first))).second))
                {
                        ASSERT (0);
                }

                vectorHuffmanCodes_.push_back ((*iterAlphabet).second.symbol_path_);

        }

        stable_sort (vectorHuffmanCodes_.begin (), vectorHuffmanCodes_.end (), lessVectorsAlterCompare<CODE> ());


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


//-----------------------
template <typename SYMBOL, typename WEIGHT, unsigned int ARY>
unsigned int BasicHuffmanTree<SYMBOL, WEIGHT, ARY>::getCodeSizesSum () const
{
unsigned int    ret_intValue = 0;
        for (unsigned int cur_index = 0; cur_index < vectorHuffmanCodes_.size (); cur_index++)
        {
                ret_intValue += vectorHuffmanCodes_[cur_index].size ();
        }
        return ret_intValue;
} // unsigned int BasicHuffmanTree<SYMBOL, WEIGHT, ARY>::getCodeSizesSum () const


//-----------------------
template <typename SYMBOL, typename WEIGHT, unsigned int ARY>
WEIGHT BasicHuffmanTree<SYMBOL, WEIGHT, ARY>::getWeightsSum () const
{
Tree_MAP_SYMBOLS::const_iterator        const_iterAlphabet;
WEIGHT ret_WEIGHT_Value;
        //=====================================
        ret_WEIGHT_Value = WEIGHT ();
        for (const_iterAlphabet = mapAlphabet_.begin();
             !(const_iterAlphabet == mapAlphabet_.end());
             const_iterAlphabet++
             )
        {
                ret_WEIGHT_Value += (*const_iterAlphabet).second.data_weight_;
        }

        return ret_WEIGHT_Value;

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


//-----------------------
template <typename SYMBOL, typename WEIGHT, unsigned int ARY>
unsigned int BasicHuffmanTree<SYMBOL, WEIGHT, ARY>::getLongestSymbolSize () const
{
Tree_MAP_SYMBOLS::const_iterator        const_iterAlphabet;

        //=====================================
unsigned int ret_intValue = 0;

        for (const_iterAlphabet = mapAlphabet_.begin();
             !(const_iterAlphabet == mapAlphabet_.end());
             const_iterAlphabet++
             )
        {
                strstream       tmp_strstream;
                tmp_strstream << (*const_iterAlphabet).first;
                tmp_strstream << ends;
                ret_intValue = MAX_VALUE (ret_intValue, string (tmp_strstream.str()).size ());
                tmp_strstream.rdbuf()->freeze (0);
        }

        //=====================================
        return ret_intValue;

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




//-----------------------
template <typename SYMBOL, typename WEIGHT, unsigned int ARY>
WEIGHT BasicHuffmanTree<SYMBOL, WEIGHT, ARY>::getWeightedCodeSizesSum () const
{
Tree_MAP_SYMBOLS::const_iterator        const_iterAlphabet;
WEIGHT ret_WEIGHT_Value;
        //=====================================
        ret_WEIGHT_Value = WEIGHT ();
        for (const_iterAlphabet = mapAlphabet_.begin();
             !(const_iterAlphabet == mapAlphabet_.end());
             const_iterAlphabet++
             )
        {
                ret_WEIGHT_Value += ((*const_iterAlphabet).second.data_weight_ * (*const_iterAlphabet).second.symbol_path_.size ());
        }
        //=====================================
        return ret_WEIGHT_Value;
} // WEIGHT BasicHuffmanTree<SYMBOL, WEIGHT, ARY>::getWeightedCodeSizesSum () const


//-----------------------
template <typename SYMBOL, typename WEIGHT, unsigned int ARY>
bool BasicHuffmanTree<SYMBOL, WEIGHT, ARY>::encodeOneSymbol (const SYMBOL& symbol_i, vector<CODE>& path_o) const
{
        if (!mapAlphabet_.count (symbol_i))
        {
                ERROR_MSG ("Symbol <"
                           << symbol_i
                           << "> is out of Alphabet"
                           );
                showAll ();
                return false;

        }
        path_o = (*(mapAlphabet_.find (symbol_i))).second.symbol_path_;

        //=====================================
        return true;

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


//-----------------------
template <typename SYMBOL, typename WEIGHT, unsigned int ARY>
bool BasicHuffmanTree<SYMBOL, WEIGHT, ARY>::knowSymbolWeight (const SYMBOL& symbol_i, WEIGHT& weight_o) const
{
        if (!mapAlphabet_.count (symbol_i))
        {
                ERROR_MSG ("Symbol <"
                           << symbol_i
                           << "> is out of Alphabet"
                           );
                showAll ();
                return false;

        }
        weight_o = (*(mapAlphabet_.find (symbol_i))).second.data_weight_;

        //=====================================
        return true;

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




//-----------------------
template <typename SYMBOL, typename WEIGHT, unsigned int ARY>
bool BasicHuffmanTree<SYMBOL, WEIGHT, ARY>::knowCodeSymbol (const vector<CODE>& path_i, SYMBOL& symbol_o) const
{
        if (!mapHuffmanCodes_.count (path_i))
        {