Octane v1.01.20 - The Open Compression Toolkit for C++

http://octane.sourceforge.net/

coders/coder_huffman/huffmannodes.hpp

Go to the documentation of this file.

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

//---------------------------------------------------------------------------
// recursive header protection
#ifndef Coder_HuffmanNodesH
#define Coder_HuffmanNodesH
//---------------------------------------------------------------------------


//---------------------------------------------------------------------------
// application includes
#include "../../bitio/bitio.hpp"
// system includes
#include <string>
#include <iostream>
#include <iomanip>
#include <vector>
#include <queue>
#include <set>
#include <bitset>
using namespace std;
//---------------------------------------------------------------------------


//---------------------------------------------------------------------------
// forward declarations
class HuffNode;
class HuffNode_Middle;
class HuffNode_Leaf;
//---------------------------------------------------------------------------


//---------------------------------------------------------------------------
// jibz modified huffman pq weight comparisn,
#define OCTANE_USEJIBZHUFFMANPQGREATER
// <mouser> so if left is a leaf and right is not a leaf, then you treat right as if it has lower weight
// <mouser> (on ties)
// <Jibz> yes .. that was what I was going for .. making internal nodes seem slightly smaller than leafs with the same weight
// <mouser> now why is this good?
// <Jibz> I don't know .. it may even be bad ;)
// <mouser> hehehehe
// <Jibz> but it seems like it might be better to make a choice, than to pick at random (or whatever the pq gives you)
// COMPARISON SHOWS -> no perceivable difference.
//--------------------------------------------------------------------------- 



//---------------------------------------------------------------------------
// TypeDefs and Defines
//
// what kind of precision should we use for the weights?
//  note that because of the way trees are built, this values needs to store
//  the SUM of all weights in the tree, not just the maximum frequency of
//  any leaf(!).

// We could use a typedef here but it can cause warnings on type conversions
// //typedef unsigned long THuffmanNodeWeight;
// #define THuffmanNodeWeight unsigned long
// #define THuffmanNodeWeight_MAX       ULONGMAX
// typedef unsigned long THuffmanNodeWeight;

#define THuffmanNodeWeight float

#define THuffmanNodeWeight_MAX  FLOATMAX

#define DEF_HUFFMANPQ_MAXIMUM_CODEBITDEPTH      160

#define DEF_HUFFMANPQ_MAXFUNCBITS 200
//---------------------------------------------------------------------------






//---------------------------------------------------------------------------
class HuffNode {
protected:
        THuffmanNodeWeight weight;
public:
        HuffNode() { ; }
        virtual ~HuffNode() { ; }
public:
        bool operator>( const HuffNode* &a ) const {return weight > (a->get_weight());}
public:
        virtual void traverse_buildbitcodes(std::bitset<DEF_HUFFMANPQ_MAXFUNCBITS> &current_bitset, int bitsetlength);
public:
        virtual void recursive_freechildren() { ; }
public:
        THuffmanNodeWeight get_weight() const {return weight;}
        void increment_weight(int increment) {weight+=increment;}
        void set_weight(THuffmanNodeWeight val) {weight=val;}
        virtual unsigned int get_memoryused() const {return sizeof(this);}
        virtual HuffNode *get_child0() {return 0;}
        virtual HuffNode *get_child1() {return 0;}
public:
        virtual bool isleaf() {return false;}
};
//---------------------------------------------------------------------------


//---------------------------------------------------------------------------
class HuffNode_Middle : public HuffNode {
protected:
        HuffNode *child0;
        HuffNode *child1;
public:
        HuffNode_Middle(HuffNode* c0, HuffNode *c1 ) {weight=c0->get_weight()+c1->get_weight(); child0=c0; child1=c1;}
        virtual ~HuffNode_Middle() { ; }
public:
        void recursive_freechildren() {child0->recursive_freechildren(); delete child0; child1->recursive_freechildren(); delete child1;}
public:
        virtual void traverse_buildbitcodes(std::bitset<DEF_HUFFMANPQ_MAXFUNCBITS> &current_bitset, int bitsetlength);
public:
        virtual unsigned int get_memoryused() const {return sizeof(this)+(child0->get_memoryused())+(child1->get_memoryused());}
        virtual HuffNode *get_child0() {return child0;}
        virtual HuffNode *get_child1() {return child1;}
public:
        bool isleaf() {return false;}
};
//---------------------------------------------------------------------------


//---------------------------------------------------------------------------
class HuffNode_Leaf : public HuffNode {
protected:
        // length of the bitcode for this symbol
        unsigned char code_bitsetlength;
        std::bitset<DEF_HUFFMANPQ_MAXIMUM_CODEBITDEPTH> code_bitset;
        int symbolid;
public:
        HuffNode_Leaf(int insymbolid, THuffmanNodeWeight inweight) {symbolid=insymbolid; weight=inweight;}
        virtual ~HuffNode_Leaf() { ; }
public:
        void recursive_freechildren() { ; }
public:
        virtual void traverse_buildbitcodes(std::bitset<DEF_HUFFMANPQ_MAXFUNCBITS> &current_bitset, int bitsetlength);
public:
        int get_symbolid() {return symbolid;}
        void set_symbolid(int val) {symbolid=val;}
        unsigned char get_bitcode_length() {return code_bitsetlength;};
        std::string get_bitcode_string();
public:
        virtual unsigned int get_memoryused() const {return (unsigned int)(sizeof(this)+sizeof(code_bitset));}
public:
        virtual bool isleaf() {return true;}
public:
        virtual bool AddBitsToBitWriter(bitwriter &bw);
};
//---------------------------------------------------------------------------


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

template< class T >
class PQWeightGreater
{
    public:
        bool operator() (const T& pLeft, const T& pRight) const
        {
        #ifdef OCTANE_USEJIBZHUFFMANPQGREATER
                if (pLeft->get_weight()==pRight->get_weight()) return (pLeft->isleaf() && !pRight->isleaf());
                //if (pLeft->get_weight()==pRight->get_weight()) return (!pLeft->isleaf() && pRight->isleaf());
        #endif
        return pLeft->get_weight()>pRight->get_weight();
        }
};
//---------------------------------------------------------------------------


//---------------------------------------------------------------------------
// typedef for priority queue of HuffNodes, which we use in huffman coding and in DictionarySet
typedef std::priority_queue< HuffNode*, std::vector< HuffNode* >, PQWeightGreater<HuffNode*> > THuffmanNodePriorityQueue;
//---------------------------------------------------------------------------






//---------------------------------------------------------------------------
#endif
//---------------------------------------------------------------------------

 

Generated on 20 May 2004 by doxygen 1.3.3