/*  Copyright (C) 2009 Joshua Judson Rosen <rozzin@geekspace.com>.

    This program is free software: you can redistribute it and/or
    modify it under the terms of the GNU Lesser General Public License
    as published by the Free Software Foundation, either version 3
    of the License, or (at your option) any later version..

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
    GNU Lesser General Public License for more details.

    You should have received a copy of the GNU Lesser General Public License
    along with this program; see the file COPYING. If not, see
    <http://www.gnu.org/licenses/> or write to:

        The Free Software Foundation, inc.
        51 Franklin Street, Fifth Floor
        Boston, MA 02110-1301
        USA
*/

#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <assert.h>

#include "levenshtein.h"
#include "weights.h"

#include <stdio.h>

static float
min3 (float x, float y, float z)
{
  return fminf (x, fminf (y, z));
}

float
levenshtein (const char *s0, int len0,
             const char *s1, int len1,
             levenshtein_weightfunc *weight)
{
  int rowlen = len1+1;

  printf ("rowlen = %d\n", rowlen);

  float *map = calloc (sizeof (float), (len0+1)*rowlen);
  float *pos = map + (len0+1)*rowlen - 1; /* terminal position */

  int i, j;
  float cost;
  float distance = 0;

  for (i=0; i<=len0; i++) {
    map[i*rowlen] = (float) i;
  }
  for (j=0; j<=len1; j++) {
    map[j] = (float) j;
  }

  for (i=1; i<=len0; i++) {
    for (j=1; j<=len1; j++) {
      if (s0[i-1] == s1[j-1]) {
        cost = 0;
      } else {
        cost = 1;
      }
      map[i*rowlen + j] = min3 (map[(i-1)*rowlen + j] + 1,       /* ins */
                                map[i*rowlen + j-1] + 1,         /* del */
                                map[(i-1)*rowlen + j-1] + cost); /* sub */
    }
  }

  /* To figure out what each step was, start at the end and then walk
     backward: */

  while (pos > map) {
    levenshtein_op op;

    float *prepos = pos;
    printf ("pos=%ld\n", pos-map);

    if (pos > map+rowlen
        && (pos-map)%rowlen
        && *(pos-rowlen-1) == *pos - 1) {
      pos = pos-rowlen-1;
      op = LEVENSHTEIN_SUB;
      printf ("sub  ");
    } else if (pos > map+rowlen-1 && *(pos-rowlen) == *pos - 1) {
      op = LEVENSHTEIN_DEL;
      pos = pos - rowlen;
      /* Note that DEL-pos is where the char *would be*:
         the position after the last common character. */
      printf ("del  ");
    } else if (pos > map && *(pos-1) == *pos - 1) {
      pos = pos - 1;
      op = LEVENSHTEIN_INS;
      printf ("ins  ");
      /* Note that the INS-pos is where the character *is*. */
    } else {
      assert (pos > map+rowlen && (pos-map)%rowlen);
      pos = pos-rowlen-1;
      op = LEVENSHTEIN_NON;
      printf ("keep ");
    }

    i = (pos-map) / rowlen; /* row# = s0 position */
    j = (pos-map) % rowlen; /* col# = s1 position */
    distance += weight (s0, len0, i,
                        s1, len1, j,
                        op);

    printf (": %g@%ld->%g@%ld\n",
            *prepos, prepos-map,
            *pos, pos-map);
  }

  return distance;
}

double
visualid_word_difference (const char *s0, const char *s1)
{
  return levenshtein (s0, strlen (s0),
                      s1, strlen (s1),
                      weight_linear_normal);
}