ahuff.c

huffman coding and decoding adaptive huffman coding and decoding it is a assignment from my cours

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