#!/usr/bin/perl -w
# Huffman Compression - Operating on a string of ASCII characters
# Lossless compression - fixed length data to variable length representation
###############################################################################
### Given a random character set, the characters that appear least often should
### have the longest bit-codes and those that appear most often should have the
### shortest bit-codes.
###############################################################################

use strict;

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

my @chars = ();
my %prob = ();
my ($smallest, $second);
my %leaf = ();
my $leafnumber = 0;
my @bitcode = ();
my %compression = ();
my $newdata;
my $line;

### Step 0 : If a filename is passed as a command line argument, use its 
###          contents for the @chars array instead of the test data. 

open (INFILE, $ARGV[0]) or die "Cannot open $ARGV[0]: $!\n";
while ($line = <INFILE>) {
	chomp($line);
	push (@chars, split (//, $line));
}
close (INFILE) or die "Cannot close $ARGV[0]: $!\n";


### Step 1: Count the instances of each character

foreach (@chars) { $prob{$_}++; }
foreach (keys(%prob)) { $prob{$_}/=@chars; }

foreach (keys(%prob)) {
	print "$_ : $prob{$_}\n";
}

do {

	### Step 2: Find the character that appears least often

	$smallest = (keys(%prob))[0];
	foreach (keys(%prob)) {
		if ($prob{$_} < $prob{$smallest}) {
			$smallest = $_;
		}
	}
	print "Smallest value is $smallest with probability $prob{$smallest}\n";
	
	### Step 3: Find the character that appears next least often

	if ($smallest ne (keys(%prob))[0]) { $second = (keys(%prob))[0]; }
	else { $second = (keys(%prob))[-1]; }
	foreach (keys(%prob)) {
		if ($_ ne $smallest && $prob{$_} < $prob{$second}) {
			$second = $_;
		}
	}
	print "Second smallest value is $second with probability $prob{$second}\n";
	
	### Step 4: Add $smallest and $second to binary tree data structure
	
		if (!defined($leaf{$smallest})) {
			$leaf{$smallest}[0] = undef;
			$leaf{$smallest}[1] = undef;
			$leaf{$smallest}[2] = $prob{$smallest};
		}
		if (!defined($leaf{$second})) {
			$leaf{$second}[0] = undef;
			$leaf{$second}[1] = undef;
			$leaf{$second}[2] = $prob{$second};
		}
		$leafnumber++;
		$leaf{$leafnumber}[0] = $smallest;
		$leaf{$leafnumber}[1] = $second;
		$leaf{$leafnumber}[2] = $prob{$smallest} + $prob{$second};
	
	### Step 5: Remove $smallest and $second from %prob and replace them
	###         with ($prob{$smallest} + $prob{$second})
	
		delete $prob{$smallest};
		delete $prob{$second};
		$prob{$leafnumber} = $leaf{$leafnumber}[2];

		foreach (keys(%prob)) {
			print "$_ : $prob{$_}\n";
		}
	
} while (keys(%prob) > 1);

### Step 6: Traverse binary tree and calculate bit-codes for individual chars

print "\nTraversing Binary Tree Structure...";
traverse_tree($leafnumber, \@bitcode, \%compression);
print "Analysis completed\n";
foreach (sort keys(%compression)) {
	print "$_ : $compression{$_}\n";
}

### Step 7: Encode the input data and output to a file

print "\nEncoding Data...\n";
my $i;
for ($i=0; $i<@chars; $i++) {
	$chars[$i] = $compression{$chars[$i]};
}
$newdata = join ("", @chars);
print $newdata;

open (OUTFILE, ">huffman.out") or die "Cannot write to huffman.out: $!\n";
foreach (sort keys(%compression)) {
	print OUTFILE "$_ : $compression{$_}\n";
}
print OUTFILE "\n$newdata\n";
close (OUTFILE) or die "Cannot close huffman.out: $!\n";

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


###############################################################################

sub traverse_tree {
	my $leafname = $_[0];
	my $bitcode = $_[1];
	my $compression = $_[2];

	if ($leafname =~ /\D/) {
		$$compression{$leafname} = join("", @$bitcode);
	}
	if (defined($leaf{$leafname}[0])) {
		push (@$bitcode, 0);
		traverse_tree($leaf{$leafname}[0], $bitcode, $compression);
		pop (@$bitcode);
	}
	if (defined($leaf{$leafname}[1])) {
		push (@$bitcode, 1);
		traverse_tree($leaf{$leafname}[1], $bitcode, $compression);
		pop (@$bitcode);
	}
}
