#!/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, $bitlength, $bitsread);
my @newdata;
my $i;
my ($chopped1, $chopped2);

### 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 =~ /_BITLENGTH_ : \d+/) {
	if ($line =~ /^\n$/) {
		push(@temp, $line);
		$line = <OLDFILE>;
		push(@temp, $line);
		$line = join(//, @temp);
	}
	@temp = split(/ : /, $line);
	chomp($temp[1]);
	$decodetable{$temp[1]} = $temp[0];
	$line = <OLDFILE>;
}
$bitlength = (split(/ : /, $line))[1];
while ($line = <OLDFILE>) {
	push(@lines, $line);
}

close(OLDFILE);


# -----------------------
# print the table out
if (1) {
  foreach (keys %decodetable){
    print $decodetable{$_} . " : " . $_ . "\n";
  }

}

exit;


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}];
	}	

	$chopped1 = chop $longest;
	$chopped2 = chop $second;
	if (length($longest) > 0) {
		$node{$longest} = [$longest . '0', $longest. '1', undef];
		$node{$second} = [$second . '0', $second. '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 . $chopped1};
	$decodetable{$second} = $decodetable{$second . $chopped2};
	delete $decodetable{$longest . $chopped1};
	delete $decodetable{$second . $chopped2};


	### 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);
$line = unpack("B*", $line);

print "\n------ 0's and 1's --------------------------\n";
print $line;
print "\n--------------------------------\n";


@lines = split(//, $line);

for ($i=0; $i<$bitlength; $i++) { print $lines[$i]; }
print "\n", "-" x $bitlength, "\n";

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

print "STARTING THE TREE TRAVERSAL\n";
$bit = '';
$bitsread = 0;
for ($i=0; defined($bit) && ($bitsread < $bitlength); $i++) {
	$probe = 'TOP';
	print "PASS $i\n";
	while (defined($node{$probe}[0]) && ($bitsread < $bitlength)) {
		print "PROBE => $probe\n";
		$bit = shift(@lines);
		$bitsread++;
		print "BIT   => $bit\n";
		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";
		}
	}
}

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);
close(OUTFILE) or die "Cannot close output file: $!\n";

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