#!/usr/bin/perl
# Huffman Decompression - Operating on a string of ASCII characters
# Lossless compression - fixed length data to variable length representation
###############################################################################

use strict;

my ($line, @lines);
my @temp;
my %decodetable;
my ($longest, $second);
my %node;
my $probe;
my $bit;
my @newdata;

### Step 1: Open file passed as first argument to the program
###         1) Read in the decoding table to a hash
###         2) Read in the rest of the data as an array of lines

die "Usage: huffman_decode.pl <file to decode>\n" if @ARGV != 1;

open(OLDFILE, "<$ARGV[0]") or die "Cannot open $ARGV[0]: $!\n";

$line = <OLDFILE>;
until ($line eq "\n") {
	@temp = split(/ : /, $line);
	chomp($temp[1]);
	$decodetable{$temp[1]} = $temp[0];
	$line = <OLDFILE>;
}

while ($line = <OLDFILE>) {
	push(@lines, $line);
}

close(OLDFILE);

while (scalar(keys(%decodetable)) > 1) {

	### Step 2: Find the character with the longest code string

	$longest = (keys(%decodetable))[0];
	foreach (keys %decodetable) {
		if (length($_) > length($longest)) {
			$longest = $_;
		}
	}
	print "Longest value is $decodetable{$longest} => $longest\n";

	### Step 3: Find the character with the second longest code string

	if ($longest ne (keys(%decodetable))[0]) { 
		$second = (keys(%decodetable))[0]; 
	} else {
		$second = (keys(%decodetable))[-1];
	}
	foreach (keys(%decodetable)) {
		if ($_ ne $longest && length($_) > length($second)) {
			$second = $_;
		}
	}
	print "Second longest value is $decodetable{$second} => $second\n";

	### Step 4: Create nodes for $longest and $second 
	###         and attach the two into the tree

	unless (defined($node{$longest})) {
		$node{$longest} = [undef, undef, $decodetable{$longest}];
	}
	unless (defined($node{$second})) {
		$node{$second}  = [undef, undef, $decodetable{$second}];
	}	
	chop $longest;
	if (length($longest) > 0) {
		$node{$longest} = [$longest . '0', $longest . '1', undef];
	} else {
		$node{'TOP'} = [0, 1, undef];
	}
	
	### Step 5: Remove $longest and $second from %decodetable
	###         and replace them with a combination of their values
	
	$decodetable{$longest} = 
		$decodetable{$longest . '0'} . $decodetable{$longest . '1'};
	delete $decodetable{$longest . '0'};
	delete $decodetable{$longest . '1'};


	### Step 6: Print out current %decodetable values for debugging
	foreach (keys %decodetable) {
		print "$decodetable{$_} => $_\n";
	}
}

### Step 7: Decode the data from the file using the node tree

chomp (@lines);
$line = join('', @lines);
@lines = split(//, $line);

foreach (@lines) { print $_; }
print "\n", "-" x scalar(@lines), "\n";

##########
##__##__##
##########
## #### ##
##\____/##
##########

while (@lines > 0) {
	$probe = 'TOP';
	while (defined($node{$probe}[0])) {
		$bit = shift(@lines);
		if ($bit eq '0') { $probe = $node{$probe}[0]; }
		if ($bit eq '1') { $probe = $node{$probe}[1]; }
		if (defined($node{$probe}[2])) { 
			push(@newdata, $node{$probe}[2]); 
		}
	}
}

print join('', @newdata), "\n";

### Step 8: Write the decoded data out to a file

open(OUTFILE, ">huffman.unzip") or die "Cannot open output file: $!\n";
print OUTFILE join('', @newdata), "\n";
close(OUTFILE) or die "Cannot close output file: $!\n";

print "Data has been written to huffman.unzip\n";
