huf_class.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_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 : huf_class.H
//
//  AUTHOR : Alex Vinokur
//
//  DESCRIPTION :
//         Definition of the following template classes :
//         ----------------------------------------------
//         - Cell                         <SYMBOL, WEIGHT>
//         - Node                         <SYMBOL, WEIGHT>
//         - InternalNode                 <SYMBOL, WEIGHT>
//         - TerminalNode                 <SYMBOL, WEIGHT>
//         - BasicHuffmanTree             <SYMBOL, WEIGHT, ARY>
//         - LoadedHuffmanTree            <SYMBOL, WEIGHT, ARY>
//         - DriedHuffmanTree             <WEIGHT, ARY>
//         ----------------------------------------------
//
//         Definition and implementation of the following template classes :
//         ----------------------------------------------
//         - lessNodesCompare             <SYMBOL, WEIGHT>
//         - lessNodesCorrectingCompare01 <SYMBOL, WEIGHT>
//         - lessNodesCorrectingCompare02 <SYMBOL, WEIGHT>
//         - lessCellsCompare             <SYMBOL, WEIGHT>
//         - lessVectorsAlterCompare      <T>
//         ----------------------------------------------
//
//  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


//#######################################################
//##### PART : DECLARATIONS #############################
//#######################################################

template <typename SYMBOL, typename WEIGHT>
class Cell;

template <typename SYMBOL, typename WEIGHT>
class Node;

template <typename SYMBOL, typename WEIGHT>
class InternalNode ;

template <typename SYMBOL, typename WEIGHT>
class TerminalNode ;

template <typename SYMBOL, typename WEIGHT, unsigned int ARY>
class BasicHuffmanTree;

template <typename SYMBOL, typename WEIGHT, unsigned int ARY = 2>
class LoadedHuffmanTree;

template <typename WEIGHT, unsigned int ARY = 2>
class DriedHuffmanTree;

template <typename SYMBOL, typename WEIGHT>
class lessNodesCompare;

template <typename SYMBOL, typename WEIGHT>
class lessNodesCorrectingCompare01;

template <typename SYMBOL, typename WEIGHT>
class lessNodesCorrectingCompare02;

template <typename SYMBOL, typename WEIGHT>
class lessCellsCompare;

template <typename T1>
class lessVectorsAlterCompare;




//#######################################################
//##### PART : template class Cell ######################
//############ Definition ###############################
//#######################################################

//----------- template class Cell -----------
template <typename SYMBOL, typename WEIGHT>
class Cell
{
template <typename S1, typename W1, unsigned int A1> friend class BasicHuffmanTree;

friend class TerminalNode<SYMBOL, WEIGHT>;
friend class lessCellsCompare<SYMBOL, WEIGHT>;
friend istream& operator>> <SYMBOL, WEIGHT> (istream &str_o, Cell<SYMBOL, WEIGHT>& instance_i);

        private :
                SYMBOL  data_symbol_;
                WEIGHT  data_weight_;
                unsigned int    symbol_original_index_;
                vector<CODE>    symbol_path_;
        protected :

        public :
                Cell () {}
                Cell (
                        const SYMBOL&   data_symbol_i,
                        const WEIGHT&   data_weight_i,
                        unsigned int    symbol_original_index_i = UINT_MAX
                        );
                virtual ~Cell () {}

};




//#######################################################
//##### PART : template class Node ######################
//############ Definition ###############################
//#######################################################

//----------- template class Node -----------
template <typename SYMBOL, typename WEIGHT>
class Node
{
template <typename S1, typename W1, unsigned int A1> friend class BasicHuffmanTree;

friend class InternalNode<SYMBOL, WEIGHT>;
friend class lessNodesCompare<SYMBOL, WEIGHT>;
friend class lessNodesCorrectingCompare01<SYMBOL, WEIGHT>;
friend class lessNodesCorrectingCompare02<SYMBOL, WEIGHT>;
friend ostream& operator<< <SYMBOL, WEIGHT> (ostream &str_o, const Node<SYMBOL, WEIGHT>& instance_i);

typedef map<SYMBOL, WEIGHT, less<SYMBOL> > Node_MAP_SYMBOLS;

        private :
        protected :
                Node_MAP_SYMBOLS        mapSymbols_;
                WEIGHT                  weight_;
                bool                    is_TerminalNode_;
                int                     absorbtion_stage_;
                int                     creation_stage_;

        public :
                Node () {weight_ = WEIGHT (); absorbtion_stage_ = -2; creation_stage_ = -1;}
                virtual ~Node () {}
};




//#######################################################
//##### PART : template class InternalNode ##############
//############ Definition ###############################
//#######################################################

//----------- template class InternalNode -----------
template <typename SYMBOL, typename WEIGHT>
class InternalNode : public Node<SYMBOL, WEIGHT>
{
template <typename S1, typename W1, unsigned int A1> friend class BasicHuffmanTree;
        private :
                vector<Node<SYMBOL, WEIGHT>*>   arc_;
        protected :
                void addNode (Node<SYMBOL, WEIGHT> const *  const ptr2_i);
        public :
                InternalNode () {is_TerminalNode_ = false;}
                ~InternalNode () {}
};




//#######################################################
//##### PART : template class TerminalNode ##############
//############ Definition ###############################
//#######################################################

//----------- template class TerminalNode -----------
template <typename SYMBOL, typename WEIGHT>
class TerminalNode : public Node<SYMBOL, WEIGHT>
{
template <typename S1, typename W1, unsigned int A1> friend class BasicHuffmanTree;
        private :

        protected :
        public :
                TerminalNode () {is_TerminalNode_ = true;}
                TerminalNode (const Cell<SYMBOL, WEIGHT>& cell_i);
                ~TerminalNode () {}
};



//#######################################################
//##### PART : template class less... ###################
//#######################################################

//#######################################################
//----------- template class lessNodesCompare -----------
template <typename SYMBOL, typename WEIGHT>
class lessNodesCompare
{
public:
        bool operator()(
                        const Node<SYMBOL, WEIGHT>* const left_i,
                        const Node<SYMBOL, WEIGHT>* const right_i
                        )
        {
                return (left_i->weight_ < right_i->weight_);
        }
};


//#######################################################
//------- template class lessNodesCorrectingCompare01 -----
template <typename SYMBOL, typename WEIGHT>
class lessNodesCorrectingCompare01
{
public:
        bool operator()(
                        const Node<SYMBOL, WEIGHT>* const left_i,
                        const Node<SYMBOL, WEIGHT>* const right_i
                        )
        {
                return ((left_i->weight_ == right_i->weight_) ? (!(left_i->is_TerminalNode_)) : (left_i->weight_ < right_i->weight_));
        }
};



//#######################################################
//------- template class lessNodesCorrectingCompare02 -----
template <typename SYMBOL, typename WEIGHT>
class lessNodesCorrectingCompare02
{
public:
        bool operator()(
                        const Node<SYMBOL, WEIGHT>* const left_i,
                        const Node<SYMBOL, WEIGHT>* const right_i
                        )
        {
                return ((left_i->is_TerminalNode_ == right_i->is_TerminalNode_) ? (left_i->weight_ < right_i->weight_) : (!(left_i->is_TerminalNode_)));
        }
};


//#######################################################
//----------- template class lessCellsCompare -----------
template <typename SYMBOL, typename WEIGHT>
class lessCellsCompare
{