#!/usr/bin/perl

# huff_decode( $tree, \&get_bit, \&put_stream )
#    Accept a stream of bits (provided one at a time with &$get_bit).
#    Convert to symbols using the Huffman order defined by $tree,
#    and write the resulting data using &$put_stream.
#
sub huff_decode {
    my $tree       = shift;
    my $get_bit    = shift;
    my $put_stream = shift;

    my $cur_node = $tree;
    my $cur_bit;

    while( defined( $cur_bit = &$get_bit ) ) {
        # Down to next node.
        $cur_node = $cur_bit ? $cur_node->{right} : $cur_node->{left};
        unless( $cur_node->{left} ) {
            # At a leaf - output the value and start a new one.
            &$put_stream( $cur_node->{value} );
            $cur_node = $tree;
        }
    }
}

# huff_hash_subtree( $node, \%hash, $prefix )
#    Fill %hash.  Traverse the tree down to leaves
#    in the subtree, recursing into left and right subtrees,
#    accumulating @$prefix on the way.
#    Each key in the %hash will be one of the values that
#    can be found in the original file.  The corresponding
#    value will be the bits that encode it.
#    $prefix is the sequence of bits that specify $node.
sub huff_hash_subtree {
    my $node   = shift;
    my $hash   = shift;
    my $prefix = shift;

    if( $node->{left} ) {
        huff_hash_subtree( $node->{left}, $hash, [ @$prefix, 0 ] );
        huff_hash_subtree( $node->{right}, $hash, [ @$prefix, 1 ] );
    } else {
        $hash->{$node->{value}} = $prefix;
    }
}

# huff_hash( $tree, \%hash )
#    Fill %hash.  Use huff_hash_subtree(), starting from
#    the root of the tree.
sub huff_hash {
    my $tree = shift;
    my $hash = shift;
    %$hash = ( );

    huff_hash_subtree( $tree, $hash, [] );
}

# huff_encode( $hash, \&get_stream, \&put_bit )
#    Given a stream of symbols, read one at a time with $get_stream,
#    convert to the compressed format using the Huffman order defined
#    by huff_hash(), and write the resulting data using $put_bit.
sub huff_encode {
    my $hash       = shift;
    my $get_stream = shift;
    my $put_bit    = shift;

    my $cur_stream;
    my $cur_bits;

    while( defined( $cur_stream = &$get_stream ) ) {
        # Convert to ASCII bits.
        foreach $cur_bit (@{ $hash->{$cur_stream} }) {
            # At a leaf - output the value and start a new one.
            &$put_bit( $cur_bit );
        }
    }
}

# $tree = build_hash_tree( \%weights )
#    Convert a hash of symbols and their weights to a
#    Huffman decoding tree.
sub build_hash_tree {
    my $hash = shift;
    my $list = [ ];
    my( $symbol, $weight );

    # Make a leaf node for each symbol.
    while( ($symbol, $weight) = each(%$hash) ) {
        push( @$list, {
                value => $symbol,
                weight => $weight,
            } );
    }

    # Reduce list into a single tree.
    while( $#$list ) {
        @$list = sort
            { $a->{weight} <=> $b->{weight} ||
              $a->{value}  <=> $b->{value}     }
            @$list;
        my( $left, $right ) = splice( @$list, 0, 2 );
        my $new_node = {
                left   => $left,
                right  => $right,
                weight => $left->{weight} + $right->{weight},
                value  => $left->{value} . $right->{value},
            };
        unshift( @$list, $new_node );
    }

    # The tree is the remaining element of the list.
    return $list->[0];
}

%symbol_weights = (
    'a',  5,
    'b',  2,
    'c',  9,
    'd',  1,
    'e',  1,
    'f',  12,
);