/************************** 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 ****************************/