Search  

---

C:/temp/src/j2k/DataType/Huffman/HuffMan.hpp

Go to the documentation of this file.

/***************************************************************************
 *** Huffman coding tree example program.                                ***
 ***************************************************************************

First, read from the data file a set of strings and associated frequencies.

These are placed onto a list of (single node) Huffman trees.

Next, build a single Huffman coding tree for the set.

The strings and their codes are then output,
with CodeTable storing the coding for each input string.

Next, read commands to "encode" or "decode" strings,
providing the appropriate output.
***************************************************************************/

#include <j2k/Fred/Standard.hpp>
#include <ctype.h>

#include <j2k/DataType/HuffMan/LettFreq.hpp>
typedef LettFreq* Belem;

#include <j2k/DataType/BinTree.hpp>
#include <j2k/DataType/HuffMan/HuffTree.hpp>

typedef HuffTree* Elem;

// Use for freelist link class.
#include <j2k/DataType/Link/SLink.hpp>
#include <j2k/DataType/Link/SList.hpp>

// Load the member functions
#include <j2k/DataType/Link/SLink.cpp>
#include <j2k/DataType/Link/SList.cpp>

#define CODELEN 20 // Max length of a huffman code

// Print out the elements of list "in"
void print(List& in) 
{
  if (in.isEmpty()) 
  {
    cout << "()\n";
  }
  else 
  {
    in.setFirst();
    cout << "( " << in.currValue();
    in.next();

    while (in.isInList()) 
    {
      cout << ", " << in.currValue();
      in.next();
    }

    cout << " )\n";
  }
}

double total = 0;

// overload for the << operator to allow "nice" output of a LettFreq object
ostream& operator << (ostream& s, LettFreq* z)
{
  cout << "In lettfreq << operator\n";
  if (z->letter() != '\0')
  {
    return(s << z->letter() << "/" << z->weight());
  }
  else
  {
    return(s << "NULL/" << z->weight());
  }
}

// overload for the << operator to allow "nice" output of HuffTree object
ostream& operator << (ostream& s, HuffTree* z)
{ 
  return(s << z->root()->value());
}

// CodeTable stores the codewords and their associated codes.
struct CodeTableEntry 
{
  LettFreq* entrydata;
  char code[CODELEN];

} CodeTable[100];

int CodeCount = 0; // Number of entries in CodeTable
FILE *fp;

List templist; // Holds the Huffman forest during construction

// Read a list of strings and frequencies from standard input,
// building a list of Huffman coding tree nodes
void read_freqs(List& hufflist)
{ 
  char buff[100];
  char buff2[100];
  char *ptr;
  char *ptr2;
  int  freq;
  HuffTree* temptree;

  while (TRUE)
  {
    if (!fgets(buff, 99, fp))  // read the next entry
    { 
      cout << "No more codes to read -- where is end?\n";
      assert(FALSE); 
    }

    // process the entry, creating a new HuffTree
    for(ptr=buff; *ptr==' '; ptr++);
    {
      if (!strncmp(ptr, "end", 3))
      { 
        cout<< "Print out the tree:\n";
        print(hufflist);
        return;
      }
    }

    if (*ptr != '"')
    {
      cout << "First char was not a quote mark.\n";
      assert(FALSE);
    }

    for (ptr2=buff2,ptr++; *ptr!='"'; ptr++)
    {
      *ptr2++ = *ptr;
    }

    *ptr2 = '\0'; // End of string

    for (ptr++; *ptr==' '; ptr++);

    if (!isdigit(*ptr)) assert(FALSE);

    freq = atoi(ptr);

    CodeTable[CodeCount].entrydata = new LettFreq(freq, buff2[0]);

    temptree = new HuffTree(CodeTable[CodeCount++].entrydata);

    // put in the list in sorted order
    // WARNING: This may be considered buggy.  Nodes with equal weight will
    // be put in reverse order of appearance, not in alphabetical order.
    for (hufflist.setFirst(); hufflist.isInList(); hufflist.next())
    {
      if (temptree->weight() <= hufflist.currValue()->weight())
      {
         hufflist.insert(temptree);
         break;
      }
    }

    if (!hufflist.isInList())
    {
        hufflist.append(temptree);
    }

  } // End of while loop
}

#include <j2k/DataType/HuffMan/HuffBld.hpp>

// Find the index in CodeTable for the codeword
int getindex(char codeword) 
{
  register int i;

  for ( i = 0; i < CodeCount; i++ ) 
  {
    if ( codeword == CodeTable[i].entrydata->letter() ) 
    {
      return i;
    }
  }

  return -1; // Not found
}


// Print out the codes, and also insert these codes into CodeTable
void output_tree( BinNode* node, char* prefix, int level ) 
{
  int index;
  assert( node != NULL ); // This is a Full Binary Tree so should NOT happen
  if ( node->isLeaf() ) 
  {
    cout << node->value()->letter() << "\t" << prefix << "\n";
    index = getindex( node->value()->letter() );
    strcpy( CodeTable[index].code, prefix );
    total += level * node->value()->weight();
  } 
  else 
  {
    prefix[ level     ] = '0';
    prefix[ level + 1 ] = '\0';
    output_tree( node->leftchild(),  prefix, level+1 );

    prefix[ level     ] = '1';
    prefix[ level + 1 ] = '\0';
    output_tree( node->rightchild(), prefix, level+1 );

    prefix[ level     ] = '\0';
  }
}


void do_commands( HuffTree* tree ) 
{
  BinNode* temp;
  char*    currchar;
  char     buff[80];
  int      index;

  while( fgets(buff, 99, fp) ) 
  {
    if( !strncmp(buff, "decode", 6) ) 
    {
      for( currchar = buff; *currchar != '"'; currchar++ );

      cout << "Decode " << currchar++;
      temp = tree->root();

      while (*currchar != '"')  // Traverse the tree
      {
        if ( *currchar == '0' ) 
        {
          temp = temp->leftchild();
        } 
        else if ( *currchar == '1' ) 
        {
          temp = temp->rightchild();
        } 
        else 
        {
          cout << "Bad input! " << *currchar << "\n";
          abort();
        }

        if ( temp->isLeaf() ) 
        {
          cout << temp->value()->letter();
          temp = tree->root();   // reset at root
        }

        currchar++;

      } // End of 2nd while()

    } 
    else if( !strncmp(buff, "encode", 6) ) 
    {

      for ( currchar = buff; *currchar != '"'; currchar++);

      cout << "Encode " << currchar++;

      // Assume codes are characters.  Should generalize this.
      while( *currchar != '"' )   
      {
        if (*currchar == ' ') 
        {
          cout << ' ';
        } 
        else 
        {
          index = getindex( *currchar );
          assert( index < CodeCount );    // Must find it
          cout << CodeTable[index].code;
        }

        currchar++;  // This is what needs generalized
      }
    }
    cout << "\n";

  } // End of 1st while()
}


int main( int argc, char** argv ) 
{
  HuffTree* codes;
  char prefix[30];

  if (argc == 1) 
  {
    fp = stdin;
  } 
  else 
  {
    fp = fopen(argv[1], "rt");
    cout << "Read frequencies\n";
    read_freqs(templist);
    cout << "Build the tree\n";
    codes = build_tree(templist);
    cout << "Output the tree\n";
    output_tree(codes->root(), prefix, 0);
    cout << "Average code length is ";
    cout << total/(double)codes->weight() << "\n";
    do_commands(codes);
    return(FALSE);
  }
}

---