huffman_template_algorithm.html

huffman_template_algorithm.zip

//#######################################################
//##### PART : typedefs #################################
//#######################################################
typedef unsigned int    CODE;



//#######################################################
//##### PART : FUNCTIONS ################################
//#######################################################


//#####################################################3
template <typename T>
string to_str (T value_i, int width_i = -1, char fill_i = ' ', const string& prefix_i = string ())
{
string          ret_stringValue;
strstream       tmp_strstream;

        //=================================
        if (width_i > 0)
        {
                tmp_strstream.width (width_i);
                tmp_strstream.fill (fill_i);
        }
        tmp_strstream << prefix_i;
        tmp_strstream << value_i;

        //=================================
        tmp_strstream << ends;
        ret_stringValue = tmp_strstream.str();
        tmp_strstream.rdbuf()->freeze (0);
        //=================================
        return ret_stringValue;
} // string to_str (T value_i)



//#####################################################3
template <typename T>
void add_to_vector (vector<T>& vector_i, const basic_string<T>& string_i)
{
        copy (string_i.begin (), string_i.end (), back_inserter (vector_i));
} //void add_to_vector (T value_o)



//#####################################################3
template <typename T>
void fill_vector (vector<T>& vector_i, const basic_string<T>& string_i)
{
        vector_i = vector<T> ();
        add_to_vector (vector_i, string_i);
} //void fill_vector (T value_o)




//#####################################################3
template <typename T>
unsigned int get_width (T value_i)
{
unsigned int    ret_intValue;
strstream       tmp_strstream;

        tmp_strstream << value_i;

        //=================================
        tmp_strstream << ends;
        ret_intValue = string (tmp_strstream.str()).size ();
        tmp_strstream.rdbuf()->freeze (0);
        //=================================
        return ret_intValue;
} // unsigned int get_width (T value_i)



//#####################################################
template <typename T1>
string   gstr_vect_ptrs (const vector<T1*>& vector_i, const string& delimiter_i = "")
{
strstream               tmp_strstream;
string                  tmp_string;
unsigned int            cur_index;

        cout << delimiter_i << endl;
        for (cur_index = 0; cur_index < vector_i.size (); cur_index++)
        {
                cout << "vector element ["
                     << cur_index << "] : "
                     << (*(vector_i [cur_index]))
                     << delimiter_i
                     << endl;
        }


        tmp_strstream << ends;
        tmp_string = tmp_strstream.str(); tmp_strstream.rdbuf()->freeze (0);

        //===================
        return tmp_string;

} // gstr_vect_ptrs (const vector<CODE>& vector_i)



//#####################################################
template <typename T1>
string   gstr_vector (const vector<T1>& vector_i, unsigned int start_pos_i = 0, unsigned int end_pos_i = UINT_MAX, const string& delimiter_i = "")
{

        if (vector_i.empty ())
        {
                return "Empty Vector";
        }
        //=====================================
        if (end_pos_i == UINT_MAX)
        {
                end_pos_i = vector_i.size () - 1;
        }
        ASSERT (end_pos_i < vector_i.size ());
        ASSERT (start_pos_i <= end_pos_i);
        //=====================================

strstream               tmp_strstream;
string                  tmp_string;
ostream_iterator<T1>    out (tmp_strstream, delimiter_i.c_str ());

        copy (vector_i.begin () + start_pos_i, vector_i.begin () + end_pos_i + 1, out);

        tmp_strstream << ends;
        tmp_string = tmp_strstream.str(); tmp_strstream.rdbuf()->freeze (0);

        //===================
        return tmp_string;

} // gstr_vector (const vector<CODE>& vector_i)



//#####################################################
template <typename T1>
ostream& operator<< (ostream& o, const vector<T1>& vector_i)
{
        return o << gstr_vector (vector_i);
}


//#####################################################
template <typename T1>
string   gstr_vector (const vector<T1>& vector_i, const string& delimiter_i, unsigned int start_pos_i = 0, unsigned int end_pos_i = UINT_MAX)
{
        return gstr_vector (vector_i, start_pos_i, end_pos_i, delimiter_i);
} // string   gstr_vector - 2


//#####################################################
template <unsigned int ARY>
string   gstr_path (const vector<CODE>& path_i)
{
const string    delimiter_CNS = (ARY > 16) ? "." : "";
strstream       tmp_strstream;
string          tmp_string;

        if (path_i.empty ())
        {
                tmp_strstream << "This is Huffman Tree Root";
        }
        else
        {
                for (unsigned int cur_index = 0; cur_index < path_i.size (); cur_index++)
                {
                        if (cur_index > 0)
                        {
                                tmp_strstream << delimiter_CNS;
                        }
                        tmp_strstream << path_i [cur_index];
                }
        }
        //=====================================
        tmp_strstream << ends;
        tmp_string = tmp_strstream.str(); tmp_strstream.rdbuf()->freeze (0);

        //===================
        return tmp_string;

} // gstr_path (const vector<CODE>& path_i)




//#######################################
template <typename T1, typename T2>
string gstr_map (const map<T1, T2, less<T1> >& map_i, const string &shift_i = string ())
{
strstream       tmp_strstream;
string          tmp_string;

        tmp_strstream << endl;
        tmp_strstream << endl;
        tmp_strstream << shift_i;
        tmp_strstream << "\tmap size = "
                      << map_i.size ()
                      << endl;

map<T1, T2, less<T1> >::const_iterator  cur_const_iter;
        for (cur_const_iter = map_i.begin(); !(cur_const_iter == map_i.end()); cur_const_iter++)
        {
                tmp_strstream << shift_i;
                tmp_strstream << "map element ["
                              << (*cur_const_iter).first
                              << "] = "
                              << "<"
                              << (*cur_const_iter).second
                              << ">";
                tmp_strstream << endl;
        }
        tmp_strstream << ends;
        tmp_string = tmp_strstream.str(); tmp_strstream.rdbuf()->freeze (0);

        return tmp_string;

} // string gstr_map



//#######################################
template <typename T1, typename T2>
ostream& operator<<(ostream &str_o, const map<T1, T2, less<T1> >& map_i)
{
        return str_o << gstr_map (map_i);

} // ostream& operator<<(ostream &str_o, const map<T1>& map_i)


#endif	// huf_service_H


//#######################################################
//################ END OF FILE ##########################
//####################################################### 
</PRE></TD></TR></TABLE>
------------------- C++ code : END ----------------------
=== File #1 of 4 : huf_service.H ========================



<a NAME="label_huf_class"></a>
#########################################################
=== File <font color="blue"><b>#2</b></font> <a href="#label_huf_methods">of 4</a> : <font color="blue"><b>huf_class.H</b></font> ==========================
------------------- C++ code : BEGIN --------------------
<TABLE><TR><TD bgcolor="#DEEEDD"><PRE>
// ==============================================================
//
//  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_class_H
#define huf_class_H

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

static char id_huf_class_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 : <font color="blue"><b>huf_class.H</b></font>
//
//  AUTHOR : Alex Vinokur
//
//  DESCRIPTION :
//         <font color="#FF00FF"><b>Definition of the following template classes :</b></font>
//         ----------------------------------------------
//         - Cell                         &lt;SYMBOL, WEIGHT&gt;
//         - Node                         &lt;SYMBOL, WEIGHT&gt;
//         - InternalNode                 &lt;SYMBOL, WEIGHT&gt;
//         - TerminalNode                 &lt;SYMBOL, WEIGHT&gt;
//         - BasicHuffmanTree             &lt;SYMBOL, WEIGHT, ARY&gt;
//         - LoadedHuffmanTree            &lt;SYMBOL, WEIGHT, ARY&gt;
//         - DriedHuffmanTree             &lt;WEIGHT, ARY&gt;
//         ----------------------------------------------
//
//         <font color="#FF00FF"><b>Definition and implementation of the following template classes :</b></font>
//         ----------------------------------------------
//         - lessNodesCompare             &lt;SYMBOL, WEIGHT&gt;
//         - lessNodesCorrectingCompare01 &lt;SYMBOL, WEIGHT&gt;
//         - lessNodesCorrectingCompare02 &lt;SYMBOL, WEIGHT&gt;
//         - lessCellsCompare             &lt;SYMBOL, WEIGHT&gt;
//         - lessVectorsAlterCompare      &lt;T&gt;
//         ----------------------------------------------
//
//  DATE           VERSION
//  ----           -------
//  Aug-26-1999    NHTA 1.0
//  Jul-05-2001    NHTA 1.1
//  Sep-11-2001    NHTA 1.2
//
// ##############################################################

//======================
#include "huf_service.H"
//======================

//#######################################################
//##### PART : DEFINES & CONSTANTS ######################
//#######################################################

//#define       SHOW_HUFFMAN_PROCESS_STATUS


//#######################################################