#!/usr/bin/perl

BEGIN { do "huffman" }  # Execute the "huffman" program from current directory

#####################################################################
#
# Build an optimal hash tree for the text.  (Normally, you don't get
# to use the entire text, but text that is representative of the
# character distribution.)

my $text = <<EOT;
twas brillig and the slithy toves
did gyre and gymbal in the wabes
all mimsy were the borogroves
and the momes rath outgrabes
EOT

my %weights;

foreach $ch (split //, $text) {
    ++$weights{$ch};
}

my $code_tree = build_hash_tree \%weights;



#####################################################################
#
# Compression
#
# we'll provide the "symbols" as one character at a time:

my @stream;

sub get_stream {
    return shift @stream;
}

# we'll collect the "bits" as a string of 0/1 characters

my $output = '';

sub put_bit {
    $output .= substr "01", $_[0], 1;
}

# compute the hash that corresponds to the tree

my %tree_hash;
huff_hash $code_tree, \%tree_hash;

# do the encoding

@stream = split //, $text;

huff_encode \%tree_hash, \&get_stream, \&put_bit;





#####################################################################
#
# Decompression
#
# we'll extract the "bits" one at a time:

my @bits = split //, $output;

my %bit = ( '0'=>0, '1'=>1 );

sub get_bit {
    return $bit{shift @bits};
}

# we'll collect the tokens into a string

my $decode = '';

sub put_stream {
    $decode .= $_[0];
}

# do the decoding

huff_decode $code_tree, \&get_bit, \&put_stream;

print "Original text: -----\n$text----- ", length($text), " characters\n",
    "\nEncoded text: -----\n$output\n----- ", length($output), " bits = ",
	int((length($output)+7)/8), " characters\n",
    "\nFinal text: -----\n$decode----- ", length($decode), " characters\n";