/************************** Start of AHUFF.C *************************
*
* This is the adaptive Huffman coding module used in Chapter 4.
* Compile with BITIO.C, ERRHAND.C, and either MAIN-C.C or MAIN-E.C
*/
#include
#include
#include
#include
#include "bitio.h"
#include "errhand.h"
char *CompressionName = "Adaptive Huffman coding, with escape codes";
char *Usage = "infile outfile [ -d ]";
#define END_OF_STREAM 256
#define ESCAPE 257
#define SYMBOL_COUNT 258
#define NODE_TABLE_COUNT ( ( SYMBOL_COUNT * 2 ) - 1 )
#define ROOT_NODE 0
#define MAX_WEIGHT 0x8000
#define TRUE 1
#define FALSE 0
/*
* This data structure is all that is needed to maintain an adaptive
* Huffman tree for both encoding and decoding. The leaf array is a
* set of indices into the nodes that indicate which node is the
* parent of a symbol. For example, to encode 'A', we would find the
* leaf node by way of leaf[ 'A' ]. The next_free_node index is used
* to tell which node is the next one in the array that can be used.
* Since nodes are allocated when characters are read in for the first
* time, this pointer keeps track of where we are in the node array.
* Finally, the array of nodes is the actual Huffman tree. The child
* index is either an index pointing to a pair of children, or an
* actual symbol value, depending on whether 'child_is_leaf' is true
* or false.
*/
typedef struct tree {
int leaf[ SYMBOL_COUNT ];
int next_free_node;
struct node {
unsigned int weight;
int parent;
int child_is_leaf;
int child;
} nodes[ NODE_TABLE_COUNT ];
} TREE;
/*
* The Tree used in this program is a global structure. Under other
* circumstances it could just as well be a dynamically allocated
* structure built when needed, since all routines here take a TREE
* pointer as an argument.
*/
TREE Tree;
/*
* Function prototypes for both ANSI C compilers and their K&R brethren.
*/
#ifdef __STDC__
void CompressFile( FILE *input, BIT_FILE *output, int argc, char *argv[] );
void ExpandFile( BIT_FILE *input, FILE *output, int argc, char *argv[] );
void InitializeTree( TREE *tree );
void EncodeSymbol( TREE *tree, unsigned int c, BIT_FILE *output );
int DecodeSymbol( TREE *tree, BIT_FILE *input );
void UpdateModel( TREE *tree, int c );
void RebuildTree( TREE *tree );
void swap_nodes( TREE *tree, int i, int j );
void add_new_node( TREE *tree, int c );
void PrintTree( TREE *tree );
void print_codes( TREE *tree );
void print_code( TREE *tree, int c );
void calculate_rows( TREE *tree, int node, int level );
int calculate_columns( TREE *tree, int node, int starting_guess );
int find_minimum_column( TREE *tree, int node, int max_row );
void rescale_columns( int factor );
void print_tree( TREE *tree, int first_row, int last_row );
void print_connecting_lines( TREE *tree, int row );
void print_node_numbers( int row );
void print_weights( TREE *tree, int row );
void print_symbol( TREE *tree, int row );
#else
void CompressFile();
void ExpandFile();
void InitializeTree();
void EncodeSymbol();
int DecodeSymbol();
void UpdateModel();
void RebuildTree();
void swap_nodes();
void add_new_node();
void PrintTree();
void print_codes();
void print_code();
void calculate_rows();
int calculate_columns();
void rescale_columns();
void print_tree();
void print_connecting_lines();
void print_node_numbers();
void print_weights();
void print_symbol();
#endif
/*
* The high level view of the compression routine is very simple.
* First, we initialize the Huffman tree, with just the ESCAPE and
* END_OF_STREAM symbols. Then, we sit in a loop, encoding symbols,
* and adding them to the model. When there are no more characters
* to send, the special END_OF_STREAM symbol is encoded. The decoder
* will later be able to use this symbol to know when to quit.
*
* This routine will accept a single additional argument. If the user
* passes a "-d" argument, the function will dump out the Huffman tree
* to stdout when the program is complete. The code to accomplish this
* is thrown in as a bonus., and not documented in the book.
*/
void CompressFile( input, output, argc, argv )
FILE *input;
BIT_FILE *output;
int argc;
char *argv[];
{
int c;
InitializeTree( &Tree );
while ( ( c = getc( input ) ) != EOF ) {
EncodeSymbol( &Tree, c, output );
UpdateModel( &Tree, c );
}
EncodeSymbol( &Tree, END_OF_STREAM, output );
while ( argc-- > 0 ) {
if ( strcmp( *argv, "-d" ) == 0 )
PrintTree( &Tree );
else
printf( "Unused argument: %s\n", *argv );
argv++;
}
}
/*
* The Expansion routine looks very much like the compression routine.
* It first initializes the Huffman tree, using the same routine as
* the compressor did. It then sits in a loop, decoding characters and
* updating the model until it reads in an END_OF_STREAM symbol. At
* that point, it is time to quit.
*
* This routine will accept a single additional argument. If the user
* passes a "-d" argument, the function will dump out the Huffman tree
* to stdout when the program is complete.
*/
void ExpandFile( input, output, argc, argv )
BIT_FILE *input;
FILE *output;
int argc;
char *argv[];
{
int c;
InitializeTree( &Tree );
while ( ( c = DecodeSymbol( &Tree, input ) ) != END_OF_STREAM ) {
if ( putc( c, output ) == EOF )
fatal_error( "Error writing character" );
UpdateModel( &Tree, c );
}
while ( argc-- > 0 ) {
if ( strcmp( *argv, "-d" ) == 0 )
PrintTree( &Tree );
else
printf( "Unused argument: %s\n", *argv );
argv++;
}
}
/*
* When performing adaptive compression, the Huffman tree starts out
* very nearly empty. The only two symbols present initially are the
* ESCAPE symbol and the END_OF_STREAM symbol. The ESCAPE symbol has to
* be included so we can tell the expansion prog that we are transmitting a
* previously unseen symbol. The END_OF_STREAM symbol is here because
* it is greater than eight bits, and our ESCAPE sequence only allows for
* eight bit symbols following the ESCAPE code.
*
* In addition to setting up the root node and its two children, this
* routine also initializes the leaf array. The ESCAPE and END_OF_STREAM
* leaf elements are the only ones initially defined, the rest of the leaf
* elements are set to -1 to show that they aren't present in the
* Huffman tree yet.
*/
void InitializeTree( tree )
TREE *tree;
{
int i;
tree->nodes[ ROOT_NODE ].child = ROOT_NODE + 1;
tree->nodes[ ROOT_NODE ].child_is_leaf = FALSE;
tree->nodes[ ROOT_NODE ].weight = 2;
tree->nodes[ ROOT_NODE ].parent = -1;
tree->nodes[ ROOT_NODE + 1 ].child = END_OF_STREAM;
tree->nodes[ ROOT_NODE + 1 ].child_is_leaf = TRUE;
tree->nodes[ ROOT_NODE + 1 ].weight = 1;
tree->nodes[ ROOT_NODE + 1 ].parent = ROOT_NODE;
tree->leaf[ END_OF_STREAM ] = ROOT_NODE + 1;
tree->nodes[ ROOT_NODE + 2 ].child = ESCAPE;
tree->nodes[ ROOT_NODE + 2 ].child_is_leaf = TRUE;
tree->nodes[ ROOT_NODE + 2 ].weight = 1;
tree->nodes[ ROOT_NODE + 2 ].parent = ROOT_NODE;
tree->leaf[ ESCAPE ] = ROOT_NODE + 2;
tree->next_free_node = ROOT_NODE + 3;
for ( i = 0 ; i < END_OF_STREAM ; i++ )
tree->leaf[ i ] = -1;
}
/*
* This routine is responsible for taking a symbol, and converting
* it into the sequence of bits dictated by the Huffman tree. The
* only complication is that we are working are way up from the leaf
* to the root, and hence are getting the bits in reverse order. This
* means we have to rack up the bits in an integer and then send them
* out after they are all accumulated. In this version of the program,
* we keep our codes in a long integer, so the maximum count is set
* to an arbitray limit of 0x8000. It could be set as high as 65535
* if desired.
*/
void EncodeSymbol( tree, c, output )
TREE *tree;
unsigned int c;
BIT_FILE *output;
{
unsigned long code;
unsigned long current_bit;
int code_size;
int current_node;
code = 0;
current_bit = 1;
code_size = 0;
current_node = tree->leaf[ c ];
if ( current_node == -1 )
current_node = tree->leaf[ ESCAPE ];
while ( current_node != ROOT_NODE ) {
if ( ( current_node & 1 ) == 0 )
code |= current_bit;
current_bit <<= 1;
code_size++;
current_node = tree->nodes[ current_node ].parent;
};
OutputBits( output, code, code_size );
if ( tree->leaf[ c ] == -1 ) {
OutputBits( output, (unsigned long) c, 8 );
add_new_node( tree, c );
}
}
/*
* Decoding symbols is easy. We start at the root node, then go down
* the tree until we reach a leaf. At each node, we decide which
* child to take based on the next input bit. After getting to the
* leaf, we check to see if we read in the ESCAPE code. If we did,
* it means that the next symbol is going to come through in the next
* eight bits, unencoded. If that is the case, we read it in here,
* and add the new symbol to the table.
*/
int DecodeSymbol( tree, input )
TREE *tree;
BIT_FILE *input;
{
int current_node;
int c;
current_node = ROOT_NODE;
while ( !tree->nodes[ current_node ].child_is_leaf ) {
current_node = tree->nodes[ current_node ].child;
current_node += InputBit( input );
}
c = tree->nodes[ current_node ].child;
if ( c == ESCAPE ) {
c = (int) InputBits( input, 8 );
add_new_node( tree, c );
}
return( c );
}
/*
* UpdateModel is called to increment the count for a given symbol.
* After incrementing the symbol, this code has to work its way up
* through the parent nodes, incrementing each one of them. That is
* the easy part. The hard part is that after incrementing each
* parent node, we have to check to see if it is now out of the proper
* order. If it is, it has to be moved up the tree into its proper
* place.
*/
void UpdateModel( tree, c )
TREE *tree;
int c;
{
int current_node;
int new_node;
if ( tree->nodes[ ROOT_NODE].weight == MAX_WEIGHT )
RebuildTree( tree );
current_node = tree->leaf[ c ];
while ( current_node != -1 ) {
tree->nodes[ current_node ].weight++;
for ( new_node = current_node ; new_node > ROOT_NODE ; new_node-- )
if ( tree->nodes[ new_node - 1 ].weight >=
tree->nodes[ current_node ].weight )
break;
if ( current_node != new_node ) {
swap_nodes( tree, current_node, new_node );
current_node = new_node;
}
current_node = tree->nodes[ current_node ].parent;
}
}
/*
* Rebuilding the tree takes place when the counts have gone too
* high. From a simple point of view, rebuilding the tree just means that
* we divide every count by two. Unfortunately, due to truncation effects,
* this means that the tree's shape might change. Some nodes might move
* up due to cumulative increases, while others may move down.
*/
void RebuildTree( tree )
TREE *tree;
{
int i;
int j;
int k;
unsigned int weight;
/*
* To start rebuilding the table, I collect all the leaves of the Huffman
* tree and put them in the end of the tree. While I am doing that, I
* scale the counts down by a factor of 2.
*/
printf( "R" );
j = tree->next_free_node - 1;
for ( i = j ; i >= ROOT_NODE ; i-- ) {
if ( tree->nodes[ i ].child_is_leaf ) {
tree->nodes[ j ] = tree->nodes[ i ];
tree->nodes[ j ].weight = ( tree->nodes[ j ].weight + 1 ) / 2;
j--;
}
}
/*
* At this point, j points to the first free node. I now have all the
* leaves defined, and need to start building the higher nodes on the
* tree. I will start adding the new internal nodes at j. Every time
* I add a new internal node to the top of the tree, I have to check to
* see where it really belongs in the tree. It might stay at the top,
* but there is a good chance I might have to move it back down. If it
* does have to go down, I use the memmove() function to scoot everyone
* bigger up by one node. Note that memmove() may have to be change
* to memcpy() on some UNIX systems. The parameters are unchanged, as
* memmove and memcpy have the same set of parameters.
*/
for ( i = tree->next_free_node - 2 ; j >= ROOT_NODE ; i -= 2, j-- ) {
k = i + 1;
tree->nodes[ j ].weight = tree->nodes[ i ].weight +
tree->nodes[ k ].weight;
weight = tree->nodes[ j ].weight;
tree->nodes[ j ].child_is_leaf = FALSE;
for ( k = j + 1 ; weight < tree->nodes[ k ].weight ; k++ )
;
k--;
memmove( &tree->nodes[ j ], &tree->nodes[ j + 1 ],
( k - j ) * sizeof( struct node ) );
tree->nodes[ k ].weight = weight;
tree->nodes[ k ].child = i;
tree->nodes[ k ].child_is_leaf = FALSE;
}
/*
* The final step in tree reconstruction is to go through and set up
* all of the leaf and parent members. This can be safely done now
* that every node is in its final position in the tree.
*/
for ( i = tree->next_free_node - 1 ; i >= ROOT_NODE ; i-- ) {
if ( tree->nodes[ i ].child_is_leaf ) {
k = tree->nodes[ i ].child;
tree->leaf[ k ] = i;
} else {
k = tree->nodes[ i ].child;
tree->nodes[ k ].parent = tree->nodes[ k + 1 ].parent = i;
}
}
}
/*
* Swapping nodes takes place when a node has grown too big for its
* spot in the tree. When swapping nodes i and j, we rearrange the
* tree by exchanging the children under i with the children under j.
*/
void swap_nodes( tree, i, j )
TREE *tree;
int i;
int j;
{
struct node temp;
if ( tree->nodes[ i ].child_is_leaf )
tree->leaf[ tree->nodes[ i ].child ] = j;
else {
tree->nodes[ tree->nodes[ i ].child ].parent = j;
tree->nodes[ tree->nodes[ i ].child + 1 ].parent = j;
}
if ( tree->nodes[ j ].child_is_leaf )
tree->leaf[ tree->nodes[ j ].child ] = i;
else {
tree->nodes[ tree->nodes[ j ].child ].parent = i;
tree->nodes[ tree->nodes[ j ].child + 1 ].parent = i;
}
temp = tree->nodes[ i ];
tree->nodes[ i ] = tree->nodes[ j ];
tree->nodes[ i ].parent = temp.parent;
temp.parent = tree->nodes[ j ].parent;
tree->nodes[ j ] = temp;
}
/*
* Adding a new node to the tree is pretty simple. It is just a matter
* of splitting the lightest-weight node in the tree, which is the highest
* valued node. We split it off into two new nodes, one of which is the
* one being added to the tree. We assign the new node a weight of 0,
* so the tree doesn't have to be adjusted. It will be updated later when
* the normal update process occurs. Note that this code assumes that
* the lightest node has a leaf as a child. If this is not the case,
* the tree would be broken.
*/
void add_new_node( tree, c )
TREE *tree;
int c;
{
int lightest_node;
int new_node;
int zero_weight_node;
lightest_node = tree->next_free_node - 1;
new_node = tree->next_free_node;
zero_weight_node = tree->next_free_node + 1;
tree->next_free_node += 2;
tree->nodes[ new_node ] = tree->nodes[ lightest_node ];
tree->nodes[ new_node ].parent = lightest_node;
tree->leaf[ tree->nodes[ new_node ].child ] = new_node;
tree->nodes[ lightest_node ].child = new_node;
tree->nodes[ lightest_node ].child_is_leaf = FALSE;
tree->nodes[ zero_weight_node ].child = c;
tree->nodes[ zero_weight_node ].child_is_leaf = TRUE;
tree->nodes[ zero_weight_node ].weight = 0;
tree->nodes[ zero_weight_node ].parent = lightest_node;
tree->leaf[ c ] = zero_weight_node;
}
/*
* All the code from here down is concerned with printing the tree.
* Printing the tree out is basically a process of walking down through
* all the nodes, with each new node to be printed getting nudged over
* far enough to make room for everything that has come before.
*/
/*
* This array is used to keep track of all the nodes that are in a given
* row. The nodes are kept in a linked list. This array is used to keep
* track of the first member. The subsequent members will be found in
* a linked list in the positions[] array.
*/
struct row {
int first_member;
int count;
} rows[ 32 ];
/*
* The positions[] array is used to keep track of the row and column of each
* node in the tree. The next_member element points to the next node
* in the row for the given node. The column is calculated on the fly,
* and represents the actual column that a given number is to be printed in.
* Note that the column for a node is not an actual column on the page. For
* purposes of analysis, it is assumed that each node takes up exactly one
* column. So, if printing out the actual values in a node takes up for
* spaces on the printed page, we might want to allocate five physical print
* columns for each column in the array.
*/
struct location {
int row;
int next_member;
int column;
} positions[ NODE_TABLE_COUNT ];
/*
* This is the main routine called to print out a Huffman tree. It first
* calls the print_codes function, which prints out the binary codes
* for each symbol. After that, it calculates the row and column that
* each node will be printed in, then prints the tree out. This code
* is not documented in the book, since it is essentially irrelevant to
* the data compression process. However, it is nice to be able to
* print out the tree.
*/
void PrintTree( tree )
TREE *tree;
{
int i;
int min;
print_codes( tree );
for ( i = 0 ; i < 32 ; i++ ) {
rows[ i ].count = 0;
rows[ i ].first_member = -1;
}
calculate_rows( tree, ROOT_NODE, 0 );
calculate_columns( tree, ROOT_NODE, 0 );
min = find_minimum_column( tree, ROOT_NODE, 31 );
rescale_columns( min );
print_tree( tree, 0, 31 );
}
/*
* This routine is called to print out the Huffman code for each symbol.
* The real work is done by the print_code routine, which racks up the
* bits and puts them out in the right order.
*/
void print_codes( tree )
TREE *tree;
{
int i;
printf( "\n" );
for ( i = 0 ; i < SYMBOL_COUNT ; i++ )
if ( tree->leaf[ i ] != -1 ) {
if ( isprint( i ) )
printf( "%5c: ", i );
else
printf( "<%3d>: ", i );
printf( "%5u", tree->nodes[ tree->leaf[ i ] ].weight );
printf( " " );
print_code( tree, i );
printf( "\n" );
}
}
/*
* print_code is a workhorse routine that prints out the Huffman code for
* a given symbol. It ends up looking a lot like EncodeSymbol(), since
* it more or less has to do the same work. The major difference is that
* instead of calling OutputBit, this routine calls putc, with a character
* argument.
*/
void print_code( tree, c )
TREE *tree;
int c;
{
unsigned long code;
unsigned long current_bit;
int code_size;
int current_node;
int i;
code = 0;
current_bit = 1;
code_size = 0;
current_node = tree->leaf[ c ];
while ( current_node != ROOT_NODE ) {
if ( current_node & 1 )
code |= current_bit;
current_bit <<= 1;
code_size++;
current_node = tree->nodes[ current_node ].parent;
};
for ( i = 0 ; i < code_size ; i++ ) {
current_bit >>= 1;
if ( code & current_bit )
putc( '1', stdout );
else
putc( '0', stdout );
}
}
/*
* In order to print out the tree, I need to calculate the row and column
* where each node will be printed. The rows are easier than the columns,
* and I do them first. It is easy to keep track of what row a node is
* in as I walk through the tree. As I walk through the tree, I also keep
* track of the order the nodes appear in a given row, by adding them to
* a linked list in the proper order. After calculate_rows() has been
* recursively called all the way through the tree, I have a linked list of
* nodes for each row. This same linked list is used later to calculate
* which column each node appears in.
*/
void calculate_rows( tree, node, level )
TREE *tree;
int node;
int level;
{
if ( rows[ level ].first_member == -1 ) {
rows[ level ].first_member = node;
rows[ level ].count = 0;
positions[ node ].row = level;
positions[ node ].next_member = -1;
} else {
positions[ node ].row = level;
positions[ node ].next_member = rows[ level ].first_member;
rows[ level ].first_member = node;
rows[ level ].count++;
}
if ( !tree->nodes[ node ].child_is_leaf ) {
calculate_rows( tree, tree->nodes[ node ].child, level + 1 );
calculate_rows( tree, tree->nodes[ node ].child + 1, level + 1 );
}
}
/*
* After I know which row each of the nodes is in, I can start the
* hard work, which is calculating the columns. This routine gets
* called recursively. It starts off with a starting guess for where
* we want the node to go, and returns the actual result, which is
* the column the node ended up in. For example, I might want my node
* to print in column 0. After recursively evaluating everything under
* the node, I may have been pushed over to node -10 ( the tree is
* evaluated down the right side first ). I return that to whoever called
* this routine so it can use the nodes position to calculate where
* the node in a higher row is to be placed.
*/
int calculate_columns( tree, node, starting_guess )
TREE *tree;
int node;
int starting_guess;
{
int next_node;
int right_side;
int left_side;
/*
* The first thing I check is to see if the node on my immediate right has
* already been placed. If it has, I need to make sure that I am at least
* 4 columns to the right of it. This allows me to print 3 characters plus
* leave a blank space between us.
*/
next_node = positions[ node ].next_member;
if ( next_node != -1 ) {
if ( positions[ next_node ].column < ( starting_guess + 4 ) )
starting_guess = positions[ next_node ].column - 4;
}
if ( tree->nodes[ node ].child_is_leaf ) {
positions[ node ].column = starting_guess;
return( starting_guess );
}
/*
* After I have adjusted my starting guess, I calculate the actual position
* of the right subtree of this node. I pass it a guess for a starting
* node based on my starting guess. Naturally, what comes back may be
* moved over quite a bit.
*/
right_side = calculate_columns( tree, tree->nodes[ node ].child, starting_guess + 2 );
/*
* After figuring out where the right side lands, I do the same for the
* left side. After doing the right side, I have a pretty good guess where
* the starting column for the left side might go, so I can pass it a good
* guess for a starting column.
*/
left_side = calculate_columns( tree, tree->nodes[ node ].child + 1, right_side - 4 );
/*
* Once I know where the starting column for the left and right subtrees
* are going to be for sure, I know where this node should go, which is
* right in the middle between the two. I calcluate the column, store it,
* then return the result to whoever called me.
*/
starting_guess = ( right_side + left_side ) / 2;
positions[ node ].column = starting_guess;
return( starting_guess );
}
int find_minimum_column( tree, node, max_row )
TREE *tree;
int node;
int max_row;
{
int min_right;
int min_left;
if ( tree->nodes[ node ].child_is_leaf || max_row == 0 )
return( positions[ node ].column );
max_row--;
min_right = find_minimum_column( tree, tree->nodes[ node ].child + 1, max_row );
min_left = find_minimum_column( tree, tree->nodes[ node ].child, max_row );
if ( min_right < min_left )
return( min_right );
else
return( min_left );
}
/*
* Once the columns of each node have been calculated, I go back and rescale
* the columns to be actual printer columns. In this particular program,
* each node takes three characters to print, plus one space to keep nodes
* separate. We take advantage of the fact that every node has at least one
* logical column between it and the ajacent node, meaning that we can space
* nodes only two physical columns apart. The spacing here consists of
* rescaling each column so that the smallest column is at zero, then
* multiplying by two to get a physical printer column.
*/
void rescale_columns( factor )
int factor;
{
int i;
int node;
/*
* Once min is known, we can rescale the tree so that column min is
* pushed over to column 0, and each logical column is set to be two
* physical columns on the printer.
*/
for ( i = 0 ; i < 30 ; i++ ) {
if ( rows[ i ].first_member == -1 )
break;
node = rows[ i ].first_member;
do {
positions[ node ].column -= factor;
node = positions[ node ].next_member;
} while ( node != -1 );
}
}
/*
* print_tree is called after the row and column of each node have been
* calculated. It just calls the four workhorse routines that are
* responsible for printing out the four elements that go on each row.
* At the top of the row are the connecting lines hooking the tree
* together. On the next line of the row are the node numbers. Below
* them are the weights, and finally the symbol, if there is one.
*/
void print_tree( tree, first_row, last_row )
TREE *tree;
int first_row;
int last_row;
{
int row;
for ( row = first_row ; row <= last_row ; row++ ) {
if ( rows[ row ].first_member == -1 )
break;
if ( row > first_row )
print_connecting_lines( tree, row );
print_node_numbers( row );
print_weights( tree, row );
print_symbol( tree, row );
}
}
/*
* Printing the connecting lines means connecting each pair of nodes.
* I use the IBM PC character set here. They can easily be replaced
* with more standard alphanumerics.
*/
#ifndef ALPHANUMERIC
#define LEFT_END 218
#define RIGHT_END 191
#define CENTER 193
#define LINE 196
#define VERTICAL 179
#else
#define LEFT_END '+'
#define RIGHT_END '+'
#define CENTER '+'
#define LINE '-'
#define VERTICAL '|'
#endif
void print_connecting_lines( tree, row )
TREE *tree;
int row;
{
int current_col;
int start_col;
int end_col;
int center_col;
int node;
int parent;
current_col = 0;
node = rows[ row ].first_member;
while ( node != -1 ) {
start_col = positions[ node ].column + 2;
node = positions[ node ].next_member;
end_col = positions[ node ].column + 2;
parent = tree->nodes[ node ].parent;
center_col = positions[ parent ].column;
center_col += 2;
for ( ; current_col < start_col ; current_col++ )
putc( ' ', stdout );
putc( LEFT_END, stdout );
for ( current_col++ ; current_col < center_col ; current_col++ )
putc( LINE, stdout );
putc( CENTER, stdout );
for ( current_col++; current_col < end_col ; current_col++ )
putc( LINE, stdout );
putc( RIGHT_END, stdout );
current_col++;
node = positions[ node ].next_member;
}
printf( "\n" );
}
/*
* Printing the node numbers is pretty easy.
*/
void print_node_numbers( row )
int row;
{
int current_col;
int node;
int print_col;
current_col = 0;
node = rows[ row ].first_member;
while ( node != -1 ) {
print_col = positions[ node ].column + 1;
for ( ; current_col < print_col ; current_col++ )
putc( ' ', stdout );
printf( "%03d", node );
current_col += 3;
node = positions[ node ].next_member;
}
printf( "\n" );
}
/*
* Printing the weight of each node is easy too.
*/
void print_weights( tree, row )
TREE *tree;
int row;
{
int current_col;
int print_col;
int node;
int print_size;
int next_col;
char buffer[ 10 ];
current_col = 0;
node = rows[ row ].first_member;
while ( node != -1 ) {
print_col = positions[ node ].column + 1;
sprintf( buffer, "%u", tree->nodes[ node ].weight );
if ( strlen( buffer ) < 3 )
sprintf( buffer, "%03u", tree->nodes[ node ].weight );
print_size = 3;
if ( strlen( buffer ) > 3 ) {
if ( positions[ node ].next_member == -1 )
print_size = strlen( buffer );
else {
next_col = positions[ positions[ node ].next_member ].column;
if ( ( next_col - print_col ) > 6 )
print_size = strlen( buffer );
else {
strcpy( buffer, "---" );
print_size = 3;
}
}
}
for ( ; current_col < print_col ; current_col++ )
putc( ' ', stdout );
printf( buffer );
current_col += print_size;
node = positions[ node ].next_member;
}
printf( "\n" );
}
/*
* Printing the symbol values is a little more complicated. If it is a
* printable symbol, I print it between simple quote characters. If
* it isn't printable, I print a hex value, which also only takes up three
* characters. If it is an internal node, it doesn't have a symbol,
* which means I just print the vertical line. There is one complication
* in this routine. In order to save space, I check first to see if
* any of the nodes in this row have a symbol. If none of them have
* symbols, we just skip this part, since we don't have to print the
* row at all.
*/
void print_symbol( tree, row )
TREE *tree;
int row;
{
int current_col;
int print_col;
int node;
current_col = 0;
node = rows[ row ].first_member;
while ( node != -1 ) {
if ( tree->nodes[ node ].child_is_leaf )
break;
node = positions[ node ].next_member;
}
if ( node == -1 )
return;
node = rows[ row ].first_member;
while ( node != -1 ) {
print_col = positions[ node ].column + 1;
for ( ; current_col < print_col ; current_col++ )
putc( ' ', stdout );
if ( tree->nodes[ node ].child_is_leaf ) {
if ( isprint( tree->nodes[ node ].child ) )
printf( "'%c'", tree->nodes[ node ].child );
else if ( tree->nodes[ node ].child == END_OF_STREAM )
printf( "EOF" );
else if ( tree->nodes[ node ].child == ESCAPE )
printf( "ESC" );
else
printf( "%02XH", tree->nodes[ node ].child );
} else
printf( " %c ", VERTICAL );
current_col += 3;
node = positions[ node ].next_member;
}
printf( "\n" );
}
/************************** End of AHUFF.C ****************************/