/****  Einfache Levenshtein-Distanz (p0=q0=r0=1) ****/
/****  mit Berücksichtigung von Wildcards        ****/
/****  (geschwindigkeitsoptimiertes C-Programm)  ****/
/****  Autor :  Jörg Michael, Hannover           ****/
/****  Datum :  22. Dezember 1993                ****/

/****  modus = ' ': normale Levenshtein-Distanz  ****/
/****  modus = '+': keine Unterscheidung         ****/
/****               Klein-/Großschreibung        ****/
/****  modus = '*': wie '+', aber zusätzlich     ****/
/****               "symmetrisches" Verhalten    ****/
/****               gemäß der im Text beschrie-  ****/
/****               benen Vorformatierung        ****/

#ifdef __cplusplus
extern          "C" {
#endif
#include "EXTERN.h"
#include "perl.h"
#include "XSUB.h"
#ifdef __cplusplus
}

#endif
#define  maxlen  51 
#ifndef strchr
char          *strchr();
# endif

int 
formatierung(char ziel[], char wort[], int n, char modus)
/****  Wandelt "wort" in GROSSschreibung  ****/
/****  um und expandiert Umlaute          ****/
/****  (n = Zeichenzahl von "ziel")       ****/
/****  Zurückgegeben wird: strlen (ziel)  ****/
{
  int             i, k;
  char            c, *s;

  i = 0;
  k = 0;
  while ((c = wort[i++]) != 0 && k < n - 1) {
    if (isupper(c) || isdigit(c)) {
      ziel[k++] = c;
    } else if (islower(c)) {
      ziel[k++] = c - 'a' + 'A';
    } else {
      s = strchr("ÄAEäAEÖOEöOEÜUEüUEßSS", c);
      if (s != NULL) {
	ziel[k++] = *(s + 1);
	if (k < n - 1) {
	  ziel[k++] = *(s + 2);
	}
      } else if (modus == '*' && c != '?') {
/****  Aufeinanderfolgende '*'  ****/
/****  zu einem zusammenziehen  ****/
	if (k == 0 || ziel[k - 1] != '*') {
	  ziel[k++] = '*';
	}
      } else {
	ziel[k++] = c;
      }
    }
  }
  ziel[k] = 0;
  return (k);
}

int 
WLD(wort, muster, modus, limit)
char *wort; 
char *muster; 
char modus; 
int limit;
{
  register int    spmin, p, q, r, lm, lw, d1, d2, i, k, x1, x2, x3;
  char            c, mm[maxlen], ww[maxlen];
  int             d[maxlen];

  if (limit == 0) {
    limit = maxlen;
  }
  if (modus == '+' || modus == '*') {
    lw = formatierung(ww, wort, maxlen, modus);
    lm = formatierung(mm, muster, maxlen, modus);

    if (modus == '*' && lw < lm - 1
	&& strchr(ww, '*') != NULL) {
/****  Wort und Muster tauschen  ****/
      wort = mm;
      muster = ww;
      strcpy(ww + lw, "*");
      i = lw;
      lw = lm;
      lm = i + 1;
/****  Limit neu setzen  ****/
      i = (int) (i / 3);
      if (i < limit) {
	limit = i;
      }
    } else {
      wort = ww;
      muster = mm;
    }
  } else {
    lw = strlen(wort);
    lm = strlen(muster);
    if (lw >= maxlen)
      lw = (maxlen - 1);
    if (lm >= maxlen)
      lm = (maxlen - 1);
  }

/****  Anfangswerte berechnen ****/
  if (*muster == '*') {
    for (k = 0; k <= lw; k++) {
      d[k] = 0;
    }
  } else {
    d[0] = (*muster == 0) ? 0 : 1;
    i = (*muster == '?') ? 0 : 1;
    for (k = 1; k <= lw; k++) {
      if (*muster == *(wort + k - 1)) {
	i = 0;
      }
      d[k] = k - 1 + i;
    }
  }

  spmin = (d[0] == 0 || lw == 0) ? d[0] : d[1];
  if (spmin > limit) {
    return (maxlen);
  }
/****  Distanzmatrix durchrechnen  ****/
  for (i = 2; i <= lm; i++) {
    c = *(muster + i - 1);
    p = (c == '*' || c == '?') ? 0 : 1;
    q = (c == '*') ? 0 : 1;
    r = (c == '*') ? 0 : 1;
    d2 = d[0];
    d[0] = d2 + q;
    spmin = d[0];

    for (k = 1; k <= lw; k++) {
/****  d[k] = Minimum dreier Zahlen  ****/
      d1 = d2;
      d2 = d[k];
      x1 = d1 + ((c == *(wort + k - 1)) ? 0 : p);
      x2 = d2 + q;
      x3 = d[k - 1] + r;

      if (x1 < x2) {
	x2 = x1;
      }
      d[k] = (x2 < x3) ? x2 : x3;

      if (d[k] < spmin) {
	spmin = d[k];
      }
    }

    if (spmin > limit) {
      return (maxlen);
    }
  }
  return ((d[lw] <= limit) ? d[lw] : maxlen);
}