package basics.string;

import basics.testing.Test;

/**
 * Berechnung der LevinshteinDistanz zweier Zeichenketten. Dies ist urspruengliche Fassung: Jede
 * Operation zaehlt, sind also zwei vertauschte Zeichen zaehlen als 2 Operationen (es gibt ein
 * Fassung, die Vertauschung als 1 Op. berechnet), ist aber langsamer und spielt in unserem Kontext
 * keine Rolle. Quelle nicht klar, naehere Erlaeuterungen:
 * http://www-igm.univ-mlv.fr/~lecroq/seqcomp/node2.html http://www.merriampark.com/ld.htm. Kleine
 * Anpassungen von mir, KS
 */
public class LDistance implements StringMatcher
{
private String term1       = "";
private String term2       = "";
private int    term1length = 0;
private int    term2length = 0; // length of t

// -------------- StringMatcherr interface usage
// -------------------//
/**
 * Use this if either distance or likeness are interesting.
 */
public LDistance()
{
}

public boolean hasLikeness(String term1, String term2, double threshold)
{
   return likeness(term1, term2) >= threshold;
}

public int distance(String term1, String term2)
{
   this.term1 = term1;
   this.term2 = term2;
   term1length = term1 == null ? 0 : term1.length();
   term2length = term2 == null ? 0 : term2.length();
   return distance();
}

/**
 * Calculates the degreed of similarity using distance and length of the strings.
 * @param a
 * @param b
 * @return value between 0 and 1
 */
public double likeness(String term1, String term2)
{
   this.term1 = term1;
   this.term2 = term2;
   term1length = term1 == null ? 0 : term1.length();
   term2length = term2 == null ? 0 : term2.length();
   return likeness();
}

// -----------------------------------------------------------------//
/**
 * Use this if distance AND likeness are needed.
 * @param term1
 * @param term2
 */
public LDistance(String term1, String term2)
{
   this.term1 = term1;
   this.term2 = term2;
   term1length = term1 == null ? 0 : term1.length();
   term2length = term2 == null ? 0 : term2.length();
}

@SuppressWarnings("unused")
public static void main(String [] args)
{
   if(args.length != 2)
   {
      System.out
         .println("LDistance [string1] [string2] - computes Levenshtein LDistance (results 0-100).");
      String a = "aabaa";
      String b = "aacaa";
   }
   {
      String a = args[0];
      String b = args[1];
      LDistance ld = new LDistance(a, b);
      System.out.println("Compare    : {" + a + "} to {" + b + "}");
      System.out.println("Distance   : " + ld.distance());
      System.out.println("Equivalence: " + ld.likeness() + " %");
   }
}

public double likeness()
{
   double deltatermlen = (term1length + term2length) / 2D;
   // OsUtl.trace("likeness ("+term1+","+term2+") " + this);
   return (1D / deltatermlen) * (deltatermlen - ((double)distance()));
}

// ****************************
// Get minimum of three values
// ****************************
private int Minimum(int a, int b, int c)
{
   int mi;
   mi = a;
   if(b < mi)
   {
      mi = b;
   }
   if(c < mi)
   {
      mi = c;
   }
   return mi;
}

// *****************************
// Compute Levenshtein LDistance
// *****************************
public int distance()
{
   int d[][]; // matrix
   // int term1length; // length of s
   int i; // iterates through s
   int j; // iterates through t
   char s_i; // ith character of s
   char t_j; // jth character of t
   int cost; // cost
   // Step 1
   if(term1length == 0)
      return term2length;
   if(term2length == 0)
      return term1length;
   d = new int [term1length + 1] [term2length + 1];
   // OsUtl.trace("distance ("+term1+","+term2+") " + this);
   // Step 2
   for(i = 0; i <= term1length; i++)
   {
      d[i][0] = i;
   }
   for(j = 0; j <= term2length; j++)
   {
      d[0][j] = j;
   }
   // Step 3
   for(i = 1; i <= term1length; i++)
   {
      s_i = term1.charAt(i - 1);
      // Step 4
      for(j = 1; j <= term2length; j++)
      {
         t_j = term2.charAt(j - 1);
         // Step 5
         if(s_i == t_j)
         {
            cost = 0;
         }
         else
         {
            cost = 1;
         }
         // Step 6
         d[i][j] = Minimum(d[i - 1][j] + 1, d[i][j - 1] + 1, d[i - 1][j - 1] + cost);
      }
   }
   // Step 7
   return d[term1length][term2length];
}

public static void unittest()
{
   String a = "aabaa12345";
   String b = "aacaa12345";
   LDistance ld = new LDistance(a, b);
   Test.assertTrue(ld.distance() == 1, "distance is not 1");
   Test.assertTrue(ld.likeness() == 0.9, "likeness is not 0.9");
   String c = "cacaa12345";
   ld = new LDistance(a, c);
   Test.assertTrue(ld.distance() == 2, "distance is not 2");
   Test.assertTrue(ld.likeness() == 0.8, "likeness is not 0.8");
}
}