#!/usr/bin/perl

##########################################################################
# Practical Session: Spelling Error Correction, Computational Linguistics
# Naoki Peter <naoki.peter@epfl.ch>
# 2013-03-14
##########################################################################


use strict;
use Data::Dumper;
use List::Util qw[min max];


my $input = 'ababa';                       # EDIT  <---------


our @x = split //, $input;             # input string
our @y = '';                           # potential solution string
our @d = ();                           # the table
our $theta = 1;                        # maximum cut-off distance
our $lowerCutOffBound = 0;             # variable for synchronizing D_c and D
our @alphabet = ('a', 'b');            # alphabet of the FSA
our @states = ({ 'a', 1, 'b', 3 },     # the FSA
               { 'b', 2 }, 
               { 'a', 0 }, 
               { 'a', 4 }, 
               { 'b', 0 });

# init first column
for (0..@x) { $d[$_] = [$_] }

# walk through FSA
my @solutions = fsa();

# print solutions
print "Solutions for \"$input\" with an edit distance <= $theta:\n";
foreach my $solution (@solutions) {
	print "- $solution\n";
}

#editDistance('bab');

exit;



# compute cut-off edit distance
sub D_c {
	my $j = shift;
	my $n = @x - 1;
	my $im = min($n, max(0, $j - $theta));
	my $jm = min($n, max(0, $j + $theta));
	$lowerCutOffBound = $jm;
	
	# init column
	$d[0][$j+1] = $j+1;
	
	# compute column up to jm
	my @window = ();
	for (my $i = 0; $i <= $jm; $i++) {
		if ($x[$i] eq $y[$j]) {
			$d[$i+1][$j+1] = $d[$i][$j];
		} elsif (($i >= 1) && ($j >= 1) && ($x[$i-1] eq $y[$j]) && ($x[$i] eq $y[$j-1])) {
			$d[$i+1][$j+1] = 1 + min($d[$i-1][$j-1], $d[$i][$j+1], $d[$i+1][$j]);
		} else {
			$d[$i+1][$j+1] = 1 + min($d[$i][$j], $d[$i][$j+1], $d[$i+1][$j]);
		}
		if ($i >= $im) { push @window, $d[$i+1][$j+1] }
	}
	#print join('', @y), ": ", join(', ', @window), "\n";
	return min(@window);
}

# compute edit distance (has to be run AFTER D_c for each column!)
sub D {
	my $j = shift;
	for (my $i = $lowerCutOffBound + 1; $i < @x; $i++) {
		if ($x[$i] eq $y[$j]) {
			$d[$i+1][$j+1] = $d[$i][$j];
		} elsif (($i >= 1) && ($j >= 1) && ($x[$i-1] eq $y[$j]) && ($x[$i] eq $y[$j-1])) {
			$d[$i+1][$j+1] = 1 + min($d[$i-1][$j-1], $d[$i][$j+1], $d[$i+1][$j]);
		} else {
			$d[$i+1][$j+1] = 1 + min($d[$i][$j], $d[$i][$j+1], $d[$i+1][$j]);
		}
	}
	return $d[@x][$j+1];
}

# move to next sate in the FSA
sub nextState {
	my ($state, $letter) = @_;
	return (defined $states[$state]{$letter}) ? $states[$state]{$letter} : -1;
}

# check whether the current state is a final state
sub finalState {
	my $state = shift;
	return ($state == 0);
}

# Walk through a FSA within a distance range (prefix-compatible depth-first version)
sub fsa {
	my @solutions = ();
	my @stack = (['', '', 0]);
	while (@stack > 0) {
		my $node = pop @stack;
		my ($z, $c, $p) = @{$node};
		my $a = '';
		my $q = -1;
		foreach (@alphabet) {
			next if (ord($_) <= ord($c));
			$q = nextState($p, $_);
			if ($q != -1) {
				$a = $_;
				last;
			}
		}
		if ($q != -1) {
			push @stack, [$z, $a, $p];
			my $yString = $z . $a;
			@y = split(//, $yString);
			if (D_c(length($yString)-1) <= $theta) {
				#prettyPrintTable(); exit;
				push @stack, [$yString, '', $q];
				if ((D(length($yString)-1) <= $theta) && finalState($q)) {
					push @solutions, $yString;
				}
			}
		}
	}
	return @solutions;
}

# edit distance for a given y string
sub editDistance {
	@y = split //, shift;
	for (my $j = 0; $j < @y; $j++) {
		D_c($j);
		D($j);
	}
	prettyPrintTable();
}

# pretty print @d
sub prettyPrintTable {
	foreach my $row (@d) { print join(" ", @{$row}), "\n" }
}

















