#!/usr/bin/perl -lw

use strict;
use warnings;
use autodie;  #So I dont have to worry about my file
use utf8;

use File::Next;
use File::Basename;
use File::Path qw/make_path/;
use File::Copy;
#use XML::Simple qw(:strict);
use XML::Simple;
use Data::Dumper;
use List::Util qw/first/;
use List::Util qw/any/;
use List::Util qw/all/;
use List::Util qw/notall/;
use List::Util qw/none/;
use List::MoreUtils qw(first_index);
use Scalar::MoreUtils qw(empty);

my $word  = "___";
my $lemma = "___";
my $pos   = "___";
my $msd   = "___";
my $sID   = "___";
my $pID   = "___";
my $depRel = "X";
my $analysis  = "___";
my $sentCounter = "1";
my %dep_rel = ();
my %domain_map = ();
my $lang = 'fkv';
my $cr_type = 'fc';
my $date = '2016-12-08';
my $rootDir = "02_data4korp";
my $inDir = "./$rootDir/01_$date/$cr_type/$lang";
my $outDir = '03_corpus';
my $corpus_name = $lang.'_corpus_'.$date;
my $realLemma = "___";
my $gthome = $ENV{'GTHOME'};
my $ismeNormFile = $gthome.'/langs/'.$lang.'/src/generator-gt-norm.xfst';
my $ismeDescFile = $gthome.'/langs/'.$lang.'/src/generator-gt-desc.xfst';
my $tmp_dir = 'tmp_'.$lang.'_'.$cr_type;
my $gen_script_norm = 'c_gtest_norm.script';
my $gen_script_desc = 'c_gtest_desc.script';

#################################
# subroutines
sub get_msd
{
  local($a) = @_;
  #remove sem- and other tags
  $a =~ s/Use\/[^\s]+ //g;
  $a =~ s/Sem\/[^\s]+ //g;
  $a =~ s/Err\/[^\s]+ //g;

  # #remove syntax labels such as
  # N Sg Nom <ext> @<SUBJ #3->2
  # and
  # <ctjHead> V TV Inf @IMV #13->11
  
  $a =~ s/<[^>]+> / /g;
    
  #split the relation and find selfID and parentID
  my ($hd, $slf, $prt) = $a =~ m/^(.*)#(\d+)->(\d+)$/;
  #split the function
  my ($r, $fct) = split(/\@/, $hd, 2);

  if(!defined $r){
    $r = '___';
  }

  if(!defined $fct){
    $fct = 'X';
  }
  
  my $rest = trim($r);
  my $sfct = trim($fct);

  my ($vPOS, $vMSD) = $rest =~m/^([^\s]+)(.*)$/;

  $vMSD =~ s/TV //g;
  $vMSD =~ s/IV //g;
  $vMSD =~ s/^\s+//;
  $vMSD =~ s/\s+$//;
  $vMSD =~ s/ /\./g;
  $vMSD =~ s/\//_/g;

  if ($sfct eq "" || $sfct eq "\?")  {
    $sfct = "___";
  }
  if ($prt eq "" || $prt eq "\?")  {
    $prt = "___";
  }
  if ($slf eq "" || $slf eq "\?")  {
    $slf = "___";
  }
  if ($vPOS eq "" || $vPOS eq "\?")  {
    $vPOS = "___";
  }
  if ($vMSD eq "" || $vMSD eq "\?")  {
    $vMSD = $vPOS;
  }
  else  {
    $vMSD = $vPOS.'.'.$vMSD;
  }

  #print STDERR "h ".$h."s ".$s."p ".$p."\n";
  return ($vPOS,$vMSD,$slf,$prt,$sfct);
}


sub get_der_msd
{
  local($a) = @_;
  #remove sem- and other tags
  $a =~ s/Use\/[^\s]+ //g;
  $a =~ s/Sem\/[^\s]+ //g;
  $a =~ s/Err\/[^\s]+ //g;

  # #remove syntax labels such as
  # N Sg Nom <ext> @<SUBJ #3->2
  # and
  # <ctjHead> V TV Inf @IMV #13->11
  
  $a =~ s/<[^>]+> / /g;
    
  #split the relation and find selfID and parentID
  my ($hd, $slf, $prt) = $a =~ m/^(.*)#(\d+)->(\d+)$/;
  #split the function
  my ($r, $fct) = split(/\@/, $hd, 2);

  if(!defined $r){
    $r = '___';
  }

  if(!defined $fct){
    $fct = '___';
  }

  my $rest = trim($r);
  my $sfct = trim($fct);

  my ($vPOS, $vMSD) = $rest =~m/^([^\s]+)(.*)$/;
  
  $vMSD =~ s/TVV //g;
  $vMSD =~ s/IVV //g;
  $vMSD =~ s/TV //g;
  $vMSD =~ s/IV //g;
  $vMSD =~ s/^\s+//;
  $vMSD =~ s/\s+$//;
  $vMSD =~ s/ /\./g;
  $vMSD =~ s/\//_/g;
  $vPOS = 'V';
  
  if ($sfct eq "" || $sfct eq "\?")  {
    $sfct = "___";
  }
  if ($prt eq "" || $prt eq "\?")  {
    $prt = "___";
  }
  if ($slf eq "" || $slf eq "\?")  {
    $slf = "___";
  }
  if ($vPOS eq "" || $vPOS eq "\?")  {
    $vPOS = "___";
  }
  if ($vMSD eq "" || $vMSD eq "\?")  {
    $vMSD = $vPOS;
  }
  else  {
    $vMSD = $vPOS.'.'.$vMSD;
  }

  #print STDERR "h ".$h."s ".$s."p ".$p."\n";
  return ($vPOS,$vMSD,$slf,$prt,$sfct);
}


sub choose_analysis
{
  my @cohort = @_;
  my $analysis = '';
  my $url = is_url_N(@cohort);
  my $all_Err = is_all_Err(@cohort);
  my $none_Err = is_none_Err(@cohort);
  my $all_Der = is_all_Der(@cohort);
  my $none_Der = is_none_Der(@cohort);

  # if all analyses contain derivation tags
  if ($all_Der) {
    # if all analyses contain error tags
    if ($all_Err) {
      # choose the first analysis in the cohort
      $analysis = shift @cohort;
    }
    # choose the first analysis in the cohort
    elsif ($none_Err) {
      $analysis = shift @cohort;
    }    
    # choose some analysis without error tag
    else {
      $analysis = get_not_Err(@cohort);
    }    
  }
  # if all analyses contain error tags
  elsif ($all_Err) {
    # but no derivation tags
    if ($none_Der) {
      # choose the first analysis in the cohort
      $analysis = shift @cohort;
    }
    # or perhaps some derivation tags
    # choose some analysis without derivation tag
    else {
      $analysis = get_not_Der(@cohort);
    }  
  }
  # there might be some derivarion tags
  else {
    # but there is no derivation tag
    if ($none_Der) {
      # and there is no error tag
      if ($none_Err) {
	# check whether the cohort is www-pattern
	if ($url) {
	  # choose the analysis as N
	  $analysis = get_url_N(@cohort);
	}
	else {
	  # choose the first analysis in the cohort
	  $analysis = shift @cohort;
	}
      }
      # there is some error tag but no derivation tag
      else {
	# choose some analysis without error tag
	$analysis = get_not_Err(@cohort);
      }
    }
    # there are some derivation tags
    else {
      # and there is no error tag
      if ($none_Err) {
	# choose some analysis without derivation tag
	$analysis = get_not_Der(@cohort);
      }
      # there is both some error tag and some derivation tag
      else {
	# choose some analysis without derivation
	$analysis = get_not_Der(@cohort);
      }
    }  
  }   
  
  return $analysis;
}
  
sub is_url_N
{
  my @cohort = @_;
  my $match = 0;
  if (grep( /^.*\".*www\..*\".*\sN\s.*$/, @cohort)) {
    $match = 1;
  }
  return $match;
}

sub get_url_N
{
  my @cohort = @_;
  my ( $index ) = grep { $cohort[$_] =~ /^.*\".*www\..*\".*N .*$/ } 0..$#cohort;

  my $url = $cohort[$index];
  return $url;
}

sub is_all_Err
{
  my @cohort = @_;
  my $match = 0 ;
  $match = all { m/^.*\sErr\/.*$/ } @cohort;
  if ($match eq '') {
    $match = 0;
  }
  return $match;
}

sub is_all_Der
{
  my @cohort = @_;
  my $match = 0 ;
  $match = all { m/^.*\sDer\/.*$/ } @cohort;
  if ($match eq '') {
    $match = 0;
  }
  return $match;
}

sub is_none_Err
{
  my @cohort = @_;
  my $match = 0 ;
  $match = none { m/^.*\sErr\/.*$/ } @cohort;
  if ($match eq '') {
    $match = 0;
  }
  return $match;
}

sub is_none_Der
{
  my @cohort = @_;
  my $match = 0 ;
  $match = none { m/^.*\sDer\/.*$/ } @cohort;
  if ($match eq '') {
    $match = 0;
  }
  return $match;
}

sub get_not_Der
{
  my @cohort = @_;
  my ( $index ) = grep { $cohort[$_] !~ /^.*\sDer\/.*$/ } 0..$#cohort;
  my $match = $cohort[$index];
  return $match;
}

sub get_not_Err
{
  my @cohort = @_;
  my ( $index ) = grep { $cohort[$_] !~ /^.*\sErr\/.*$/ } 0..$#cohort;
  my $match = $cohort[$index];
  return $match;
}

sub get_generated_lemma
{
  local($a) = @_;
  #TODO:
  # 1. CMP: # in current_lemma
  # 2. Err/XXX before some pos value such as AA, NN, or VV.
  # 3. keep track of the derivation history in the MSD (?)
  
  my $current_lemma = '';
  my $isCmpLemma = '';
  my $isErrorFirstAnalysis = '';
  my $isErrorLastAnalysis = '';
  my $current_analysis = '';
  $a =~ m/^.*(\"[^\"]+\")(.*)$/;
  
  $current_lemma = $1;
  $current_analysis = $2;
  
  if ($current_lemma =~ m/#/) {
    $isCmpLemma = $current_lemma;
  }
  
  if(!defined $current_lemma){
    $current_lemma = '___';
  }
  if(!defined $current_analysis){
    $current_analysis = '___';
  }
  
  $current_lemma = lemma_trim($current_lemma);
  $current_analysis = trim($current_analysis);
  $current_lemma = unhtmlize($current_lemma);
  
  #remove sem- and other tags
  $current_analysis =~ s/Use\/[^\s]+ //g;
  $current_analysis =~ s/Sem\/[^\s]+ //g;

  # #remove syntax labels such as
  # N Sg Nom <ext> @<SUBJ #3->2
  # and
  # <ctjHead> V TV Inf @IMV #13->11
  # What about hab and ext tags? Should they appear in the annotated Korp data?
  
  $current_analysis =~ s/<[^>]+> / /g;

  if ($current_analysis =~ m/^Err\//) {
    $isErrorFirstAnalysis = $current_analysis;
  }

  if ($current_analysis =~ m/Err\/[^\s]+$/) {
    $isErrorLastAnalysis = $current_analysis;
  }
  
  #split the relation and find selfID and parentID
  my ($hd, $slf, $prt) = $current_analysis =~ m/^(.*)#(\d+)->(\d+)$/;
  #split the function
  my ($r, $fct) = split(/\@/, $hd, 2);
  
  if(!defined $hd){
    $hd = '___';
  }
  if(!defined $slf){
    $slf = '___';
  }
  if(!defined $prt){
    $prt = '___';
  }
  if(!defined $r){
    $r = '___';
  }
  if(!defined $fct){
    $fct = '___';
  }
  
  my $rest = trim($r);
  my $sfct = trim($fct);

  if ($rest =~ m/^Err\//) {
    $isErrorFirstAnalysis = $rest;
  }

  if ($rest =~ m/Err\/[^\s]+$/) {
    $isErrorLastAnalysis = $rest;
    print STDERR "___errorLast ".$rest; 
  }

  my $realPOS = '';
  my $realBaseformSpec = '';
  my $ante = '';
  my $post = '';
  my $realMSD = '';
  
  # real pos is V
  if ($rest =~ m/ V /) {
    $realPOS = 'V';
    $realBaseformSpec = 'Inf';

    my $i = rindex($rest,' '.$realPOS.' ');
    $ante = substr($rest,0,$i);
    $post = substr($rest,$i+2);
    $realMSD = $post;

    print STDERR "___+++___ ".$realPOS." _MSD ".$realMSD;
    
    if ($realMSD =~ m/Err\//) {
      $realBaseformSpec = $realMSD;
      #      print STDERR "_+_ ".$realPOS."_errorFirst ".$ante;
    }
    
    # if ($ante =~ m/^Err\/[^\s]+/) {
    #   print STDERR "_+_ ".$realPOS."_errorFirst ".$ante;
    # }
    # if ($post =~ m/Err\/[^\/\s]+$/) {
    #   print STDERR "_+_ ".$realPOS."_errorLast ".$post;
    # }
  }
  if ($rest =~ m/ N /) {
    $realPOS = 'N';
    $realBaseformSpec = 'Sg+Nom';

    my $i = rindex($rest,' '.$realPOS.' ');
    $ante = substr($rest,0,$i);
    $post = substr($rest,$i+2);
    $realMSD = $post;

    print STDERR "___+++___ ".$realPOS." _MSD ".$realMSD;

    if ($realMSD =~ m/Err\//) {
      $realBaseformSpec = $realMSD;
      #      print STDERR "_+_ ".$realPOS."_errorFirst ".$ante;
    }

    # if ($ante =~ m/^Err\/[^\s]+/) {
    #   print STDERR "_+_ ".$realPOS."_errorFirst ".$ante;
    # }
    # if ($post =~ m/Err\/[^\/\s]+$/) {
    #   print STDERR "_+_ ".$realPOS."_errorLast ".$post;
    # }
  }
  if ($rest =~ m/ A /) {
    $realPOS = 'A';
    if ($rest =~ m/ A Comp/) {
      $realBaseformSpec = 'Comp+Attr';
    }
    elsif ($rest =~ m/ A Superl/) {
      $realBaseformSpec = 'Superl+Attr';
    }
    else {
      $realBaseformSpec = 'Attr';
    }

    my $i = rindex($rest,' '.$realPOS.' ');
    $ante = substr($rest,0,$i);
    $post = substr($rest,$i+2);
    $realMSD = $post;

    print STDERR "___+++___ ".$realPOS." _MSD ".$realMSD;

    if ($realMSD =~ m/Err\//) {
      $realBaseformSpec = $realMSD;
      #      print STDERR "_+_ ".$realPOS."_errorFirst ".$ante;
    }
    
    # if ($ante =~ m/^Err\/[^\s]+/) {
    #   print STDERR "_+_ ".$realPOS."_errorFirst ".$ante;
    # }
    # if ($post =~ m/Err\/[^\/\s]+$/) {
    #   print STDERR "_+_ ".$realPOS."_errorLast ".$post;
    # }
  }
  if ($rest =~ m/ Adv\s*/) {
    $realPOS = 'Adv';
    $realBaseformSpec = '';
    my $i = rindex($rest,' '.$realPOS);
    $ante = substr($rest,0,$i);
    $post = substr($rest,$i+4);
    $realMSD = $post;
    
    print STDERR "___+++___ ".$realPOS." _MSD ".$realMSD;
    
    if ($realMSD =~ m/Err\//) {
      $realBaseformSpec = $realMSD;
      #      print STDERR "_+_ ".$realPOS."_errorFirst ".$ante;
    }
    else {
      $realMSD = '';
    }
    
    # if ($ante =~ m/^Err\/[^\s]+/) {
    #   print STDERR "_+_ ".$realPOS."_errorFirst ".$ante;
    # }
    # if ($post =~ m/Err\/[^\/\s]+$/) {
    #   print STDERR "_+_ ".$realPOS."_errorLast ".$post;
    # }
  }

  if ($isCmpLemma eq '') {
    #    print STDERR "___+++___ ".$realPOS." _MSD ".$realMSD." _SPEC ".$realBaseformSpec;
    $realMSD =~ s/TV //g;
    $realMSD =~ s/IV //g;
    $realMSD = $realPOS.$realMSD;
    ($current_lemma,$realPOS,$realMSD) = generate_correct_lemma($current_lemma,$ante,$realPOS,$realMSD,$realBaseformSpec);
  }
  else {
    $realMSD =~ s/^\s+//;
    $realMSD =~ s/\s+$//;
    $realMSD =~ s/ /\./g;
    $realMSD =~ s/\//_/g;
    $realMSD = $realPOS.'.'.$realMSD;
    $realMSD =~ s/AA\./A\./g;
    $realMSD =~ s/NN\./N\./g;
    $realMSD =~ s/VV\./V\./g;
  }
  return ($current_lemma,$realPOS,$realMSD,$slf,$prt,$sfct);
}

sub generate_correct_lemma
{   
  my ($lemma,$ante,$pos,$msd,$spec) = @_;
  
  my $i = '';
  my $realMSD = $msd;
  my $str4gen = '';
  my $rLemma = '___';
  
  $ante =~ s/^\s+//;
  $ante =~ s/\s+$//;
  $ante =~ s/ /\+/g;
  $ante =~ s/AA\+/A\+/g;
  $ante =~ s/NN\+/N\+/g;
  $ante =~ s/VV\+/V\+/g;
  
  $spec =~ s/^\s+//;
  $spec =~ s/\s+$//;
  $spec =~ s/ /\+/g;
  $spec =~ s/^\s+//;
  
  $str4gen = $lemma.'+'.$ante.'+'.$pos.'+'.$spec;
  $str4gen =~ s/^\s+//;
  $str4gen =~ s/\s+$//;
  $str4gen =~ s/TV\+//g;
  $str4gen =~ s/IV\+//g;
  $str4gen =~ s/\+\+/\+/g;
  $str4gen =~ s/^\+//g;
  $str4gen =~ s/\+$//g;

  # hack due to bug 2260
  $str4gen =~ s/\*//g;
  # hack for birget and biggot
  $str4gen =~ s/_/ /g;
  print STDERR "str4gen __ ".$str4gen;

  open (XFILE, '>', "$tmp_dir/in.gtest");
  print XFILE $str4gen."\n"; 
  close XFILE;

  # if there is some Err tag in the string then used the descriptive xfst
  if ($str4gen =~ m/^.*\+Err\/.*$/) {
    $rLemma = `xfst -q -utf8 < $tmp_dir/$gen_script_desc`;
    # otherwise the normative one
  } else {
    $rLemma = `xfst -q -utf8 < $tmp_dir/$gen_script_norm`;
  }

  print LSFILE "str4gen ".$str4gen."\n"; 
  print LSFILE "rLemma_orig |".$rLemma."|\n"; 


  $rLemma =~ s/^\s+//;
  $rLemma =~ s/\s+$//;
  $rLemma =~ s/\n/===/g;

  $rLemma =~ s/===\?\?\?//;

  print LSFILE "rLemma_changed |".$rLemma."|\n"; 
  my $current_score = 111;
  
  if ($rLemma =~ /===/) {
    my @candidates = split(/===/, $rLemma);
    
    for my $el (@candidates) {
      my $current_LVST = levenshtein($word, $el);
      
      if ($current_LVST < $current_score) {
	$current_score = $current_LVST;
	$rLemma = $el;
      } else {
	next;
      }
    }
  }
  
  $realMSD =~ s/^\s+//;
  $realMSD =~ s/\s+$//;
  $realMSD =~ s/ /\./g;
  $realMSD =~ s/\//_/g;

  if($realMSD eq '')
    {
  $realMSD = $pos.'.'.$realMSD;
    }
  
  #print STDERR "_lm_ ".$rLemma." _dHist_ ".$dHist." _realMSD_ ".$realMSD." ___".$md."___\n";
  #return ($xpos,$xmsd);
  return ($rLemma,$pos, $realMSD)
}

sub reset_var
{
  $word  = "___";
  $pos   = "___";
  $lemma = "___";
  $sID   = "___";
  $pID   = "___";
  $depRel    = "X";
  $analysis  = "___";
}

# remove quotation marks from the lemma, replace spaces by underscore and # by the empty string
sub unhtmlize
{
    my $string = shift;
    $string =~ s/&/&amp;/g;
    $string =~ s/</&lt;/g;
    $string =~ s/>/&gt;/g;
    $string =~ s/\"/&quot;/g;
    $string =~ s/\'/&apos;/g;
# commented out for diff purposes    
    $string =~ s/ /_/g;

    return $string;
}


# Perl trim function to remove whitespace from the start and end of the string
sub dtrim
{
    my $string = shift;
    $string =~ s/^\$//;
    return $string;
}

# remove quotation marks from the lemma, replace spaces by underscore and # by the empty string
sub lemma_trim
{
    my $string = shift;
    $string =~ s/\"$//;
    $string =~ s/^\"//;
    $string =~ s/ /_/g;
    $string =~ s/#//g;
    return $string;
}

# Perl trim function to remove whitespace from the start and end of the string
sub trim
{
  my $string = '';
  $string = shift;
  $string =~ s/^\s+//;
  $string =~ s/\s+$//;
  return $string;
}

sub init_dep
  {
    %dep_rel = (
		">A" => 	"→A",
		">ADVL" => 	"→ADVL",
		">CC" => 	"→CC",
		">N" => 	"→N",
		">Num" => 	"→Num",
		">P" => 	"→P",
		">Pron" => 	"→Pron",
		"<ADVL" => 	"←ADVL",
		"<OBJ" => 	"←OBJ",
		"<OPRED" => 	"←OPRED",
		"<PPRED" => 	"←PPRED",
		"<SPRED" => 	"←SPRED",
		"<SUBJ" => 	"←SUBJ",
		"+FMAINV" => 	"+FMAINV",
		"-F<ADVL" => 	"-F←ADVL",
		"-F<OBJ" => 	"-F←OBJ",
		"-F<OPRED" => 	"-F←OPRED",
		"-F<SUBJ" => 	"-F←SUBJ",
		"-FADVL>" => 	"-FADVL→",
		"-FMAINV" => 	"-FMAINV",
		"-FOBJ>" => 	"-FOBJ→",
		"-FSUBJ>" => 	"-FSUBJ→",
		"A<" => 	"A←",
		"ADVL" => 	"ADVL",
		"ADVL>" => 	"ADVL→",
		"ADVL>CS" => 	"ADVL→CS",
		"ADVL<" => 	"ADVL←",
		"APP-ADVL<" => 	"APP-ADVL←",
		"APP-N<" => 	"APP-N←",
		"APP-Pron<" => 	"APP-Pron←",
		"CNP" => 	"CNP",
		"COMP-CS<" => 	"COMP-CS←",
		"CVP" => 	"CVP",
		"FAUX" => 	"FAUX",
		"FMV" => 	"FMV",
		"FMVdic" => 	"FMVdic",
		"FS-<ADVL" => 	"FS-←ADVL",
		"FS-<SUBJ" => 	"FS-←SUBJ",
		"FS-ADVL>" => 	"FS-ADVL→",
		"FS-IAUX" => 	"FS-IAUX",
		"FS-IMV" => 	"FS-IMV",
		"FS-N<" => 	"FS-N←",
		"FS-N<IAUX" => 	"FS-N←IAUX",
		"FS-N<IMV" => 	"FS-N←IMV",
		"FS-OBJ" => 	"FS-OBJ",
		"FS-P<" => 	"FS-P←",
		"FS-VFIN<" => 	"FS-VFIN←",
		"HNOUN" => 	"HNOUN",
		"IAUX" => 	"IAUX",
		"ICL-OBJ" => 	"ICL-OBJ",
		"ICL-SUBJ" => 	"ICL-SUBJ",
		"IMV" => 	"IMV",
		"IMVdic" => 	"IMVdic",
		"INTERJ" => 	"INTERJ",
		"N<" => 	"N←",
		"Num<" => 	"Num←",
		"OBJ>" => 	"OBJ→",
		"OPRED>" => 	"OPRED→",
		"P<" => 	"P←",
		"PCLE" => 	"PCLE",
		"Pron<" => 	"Pron←",
		"S<" => 	"S←",
		"SPRED>" => 	"SPRED→",
		"SPRED<OBJ" => 	"SPRED←OBJ",
		"SUBJ>" => 	"SUBJ→",
		"VOC" => 	"VOC",
		"X" => 	"X"
	       );
    
    %domain_map = (
		   "admin" => "administration",
		   "bible" => "bible",
		   "facta" => "facts",
		   "ficti" => "fiction",
		   "laws" => "law",
		   "news" => "news",
		   "science" => "science",
		   "___" => "___"
		  );
  }
  
#
# http://eli.thegreenplace.net/files/prog_code/levenshtein.pl.txt
#
# Return the Levenshtein distance (also called Edit distance) 
# between two strings
#
# The Levenshtein distance (LD) is a measure of similarity between two
# strings, denoted here by s1 and s2. The distance is the number of
# deletions, insertions or substitutions required to transform s1 into
# s2. The greater the distance, the more different the strings are.
#
# The algorithm employs a promimity matrix, which denotes the 
# distances between substrings of the two given strings. Read the 
# embedded comments for more info. If you want a deep understanding 
# of the algorithm, printthe matrix for some test strings 
# and study it
#
# The beauty of this system is that nothing is magical - the distance
# is intuitively understandable by humans
#
# The distance is named after the Russian scientist Vladimir
# Levenshtein, who devised the algorithm in 1965
#
sub levenshtein
{
    # $s1 and $s2 are the two strings
    # $len1 and $len2 are their respective lengths
    #
    my ($s1, $s2) = @_;
    my ($len1, $len2) = (length $s1, length $s2);

    # If one of the strings is empty, the distance is the length
    # of the other string
    #
    return $len2 if ($len1 == 0);
    return $len1 if ($len2 == 0);

    my %mat;

    # Init the distance matrix
    #
    # The first row to 0..$len1
    # The first column to 0..$len2
    # The rest to 0
    #
    # The first row and column are initialized so to denote distance
    # from the empty string
    #
    for (my $i = 0; $i <= $len1; ++$i)
    {
        for (my $j = 0; $j <= $len2; ++$j)
        {
            $mat{$i}{$j} = 0;
            $mat{0}{$j} = $j;
        }

        $mat{$i}{0} = $i;
    }

    # Some char-by-char processing is ahead, so prepare
    # array of chars from the strings
    #
    my @ar1 = split(//, $s1);
    my @ar2 = split(//, $s2);

    for (my $i = 1; $i <= $len1; ++$i)
    {
        for (my $j = 1; $j <= $len2; ++$j)
        {
            # Set the cost to 1 iff the ith char of $s1
            # equals the jth of $s2
            # 
            # Denotes a substitution cost. When the char are equal
            # there is no need to substitute, so the cost is 0
            #
            my $cost = ($ar1[$i-1] eq $ar2[$j-1]) ? 0 : 1;

            # Cell $mat{$i}{$j} equals the minimum of:
            #
            # - The cell immediately above plus 1
            # - The cell immediately to the left plus 1
            # - The cell diagonally above and to the left + the cost
            #
            # We can either insert a new char, delete a char of
            # substitute an existing char (with an associated cost)
            #
            $mat{$i}{$j} = min([$mat{$i-1}{$j} + 1,
                                $mat{$i}{$j-1} + 1,
                                $mat{$i-1}{$j-1} + $cost]);
        }
    }

    # Finally, the distance equals the rightmost bottom cell
    # of the matrix
    #
    # Note that $mat{$x}{$y} denotes the distance between the 
    # substrings 1..$x and 1..$y
    #
    return $mat{$len1}{$len2};
}


# minimal element of a list
#
sub min
{
    my @list = @{$_[0]};
    my $min = $list[0];

    foreach my $i (@list)
    {
        $min = $i if ($i < $min);
    }

    return $min;
}

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

my $iterator = File::Next::files($inDir);
my $xml = new XML::Simple;

system("rm -rfv $tmp_dir");
system("mkdir -vp $tmp_dir");
open (GSFILE, '>', "$tmp_dir/$gen_script_norm");
print GSFILE "load $ismeNormFile\n"."apply up < $tmp_dir/in\.gtest\n"."quit\n"; 
close GSFILE;

open (GSFILE, '>', "$tmp_dir/$gen_script_desc");
print GSFILE "load $ismeDescFile\n"."apply up < $tmp_dir/in\.gtest\n"."quit\n"; 
close GSFILE;


open (LSFILE, '>', "$tmp_dir/levenshtein_file.txt");

init_dep();

while ( defined ( my $inFile = $iterator->() ) ) {
  print $inFile, "\n";
  if($inFile =~ /\.dep$/) {
    my ($cf) = $inFile =~ /(.*)\.dep$/; 
    my $c_plx = $cf."\.xml";
    my $c_vrt = $cf."\.xml";
    if(-f $c_plx) {
      my $cDir = dirname($inFile);
      my ($cPath) = $c_plx =~ /^$rootDir\/(.*)$/;
      $cDir= "$outDir/$cDir";
      make_path($cDir);
      my $outFile = "$outDir/$c_vrt";
      #my $out_metaFile = "$outDir/$cf.meta";
      #print("_xfilex_ $new_location");
      #copy($c_plx,$new_location) or die "Copy failed: $!";
      
      open (OUTFILE, '>', "$outFile");
      open (INFILE,"$inFile") || die "Can't Open File: $inFile\n";
      # open (OUTMETAFILE, '>', "$out_metaFile");      

      # read metadata
      my $m_data = $xml->XMLin($c_plx,
			       ForceArray => 1,
			       # ForceContent => 1,
			       SuppressEmpty=>'',
			       KeyAttr    => {},
			      );
      my $title = $m_data->{header}[0]{title}[0];
#      if ($title eq "") {
      if(!defined $title){
	$title = '___';
      }
      my $genre = $m_data->{header}[0]{genre}[0]{code};
      if(!defined $genre){
	$genre = '___';
      }
      my $translated_from = $m_data->{header}[0]{translated_from}[0]{'xml:lang'};
      if (!defined $translated_from) {
	$translated_from = '___';
      }
      my $fname = $m_data->{header}[0]{author}[0]{person}[0]{firstname};
      if (!defined $fname) {
	$fname = '___';
      }
      my $lname = $m_data->{header}[0]{author}[0]{person}[0]{lastname};
      if (!defined $lname) {
	$lname = '___';
      }
      my $nationality = $m_data->{header}[0]{author}[0]{person}[0]{nationality};
      if (!defined $nationality) {
	$nationality = '___';
      }
      
      my $datefrom = '';
      my $dateto = '';
      my $date = $m_data->{header}[0]{year}[0];
      if (!defined $date) {
	$date = '0000-00-00';
	$datefrom = '00000000';
	$dateto = '0000000';
      }
      else {
	$datefrom = $date.'0101';
	$dateto = $date.'0101';
	$date = $date.'-01-01';
      }	

      $title = unhtmlize($title);
      $genre = unhtmlize($genre);
      $translated_from = unhtmlize($translated_from);
      $fname = unhtmlize($fname);
      $lname = unhtmlize($lname);
      $nationality = unhtmlize($nationality);
      
#       # print output
#       print "===========================";
# #      print OUTMETAFILE Dumper($year);
#       print OUTMETAFILE $title;
#       print OUTMETAFILE $genre;
#       print OUTMETAFILE $translated_from;
#       print OUTMETAFILE $fname;
#       print OUTMETAFILE $lname;
#       print OUTMETAFILE $year;
#       print "===========================";

      # from cwb-encode -h 
      #  -U <str>  insert <str> for missing columns [default: "___"]
      
      print OUTFILE '<?xml version="1.0" encoding="UTF-8"?>';
      print OUTFILE '<text title="'.$title.'" lang="'.$lang.'" orig_lang="'.$translated_from.'" gt_domain="'.$domain_map{$genre}.'" first_name="'.$fname.'" last_name="'.$lname.'" nationality="'.$nationality.'" date="'.$date.'" datefrom="'.$datefrom.'" dateto="'.$dateto.'" timefrom="000000" timeto="235959">';

      my @dep_file;
      
      $/="\n\n";
      chomp(@dep_file = <INFILE>); 
      @dep_file = map [ split /\n\n/ ], @dep_file;
      for my $sentences (@dep_file) {
	print OUTFILE '  <sentence id="'.$sentCounter++.'">';
	for my $sent (@$sentences) {
	  my @lines = split("\n",$sent);
	  my @cohorts;
	  my $i = 0;

	  
	  for my $line (@lines) {
	    $i++ if ( $line =~ /^\"</ );
	    $cohorts[$i] .= $line.'¥';
	  }
	  shift @cohorts unless defined $cohorts[0]; 

	  for my $cco (@cohorts) {
	    my @current_cohort =  split("¥",$cco);
	    
	    $word = shift @current_cohort;
	    
	    if(!defined $word){
	      $word = '___';
	    }
	    # print "new word: $word\n";
	    ($word) = $word =~ /<(.+)>/;
	    $word =~ s/_/ /g;
	    $word = unhtmlize($word);
	    # print "new word___ : $word\n";

	    my $cohort_size = @current_cohort;

	    my $current_analysis = '';
	    
	    if ($cohort_size == 1) {
	      $current_analysis = shift @current_cohort;
	    }
	    else {
	      $current_analysis = choose_analysis(@current_cohort);
	    }
	    
	    if ($current_analysis =~ m/^.*\sDer\/.*$/) {
	      if ($current_analysis =~ m/\sDer\/PassL|\sDer\/PassS|\sDer\/InchL/) {
		$current_analysis =~ m/^.*(\"[^\"]+\")(.*)$/;

		$lemma = $1;
		$analysis = $2;
		
		if(!defined $lemma){
		  $lemma = '___';
		}
		if(!defined $analysis){
		  $analysis = '___';
		}
		
		$lemma = lemma_trim($lemma);
		$analysis = trim($analysis);
		$lemma = unhtmlize($lemma);
		
		($pos,$msd,$sID,$pID,$depRel) = get_der_msd($analysis);
		
	      }
	      else { 
		# print "DERIVATION ".$current_analysis." to process\n";
		($lemma,$pos,$msd,$sID,$pID,$depRel) = get_generated_lemma($current_analysis);
	      }
	    }
	    else {
	      if ($current_analysis =~ m/^.*(\"\"\")(.*)$/) {
		$lemma = '"';
		$analysis = $2;
	      }

	      $current_analysis =~ m/^.*(\"[^\"]+\")(.*)$/;
	      $lemma = $1;
	      $analysis = $2;

	      if(!defined $lemma){
		$lemma = '___';
	      }
	      if(!defined $analysis){
		$analysis = '___';
	      }
	      
	      $lemma = lemma_trim($lemma);
	      $analysis = trim($analysis);
	      $lemma = unhtmlize($lemma);

	      ($pos,$msd,$sID,$pID,$depRel) = get_msd($analysis);
	    }

	    $depRel = $dep_rel{$depRel};
	    
	    print OUTFILE "    <w word=\"".$word."\" lemma=\"".$lemma."\" pos=\"".$pos."\" msd=\"".$msd."\" sID=\"".$sID."\" depRel=\"".$depRel."\" pID=\"".$pID."\"/>";
	    
	    reset_var();
	    
	  } # for my cohort
	  # print  Dumper \@cohorts;
	  print OUTFILE '  </sentence>';
	} # for my $sent (@$sentences)
      } # for my $sentences (@dep_file)
      
      print OUTFILE '</text>';
      print "$inFile done!\n";
      close INFILE;
      close OUTFILE;
      #      close OUTMETAFILE;
      $sentCounter = "1";
    } # if(-f $c_plx)
    else{
      print STDERR "meta-file ".$c_plx." not found!\n";
    }
  } # if($inFile =~ /\.dep$/)
} # while ( defined ( my $inFile = $iterator->() ) )

exit 0;
