/*
l_distance ()   Determines to what extent two character strings
             are (un)equal using the 'Levenstein distance'
             algorithm.

Limitation:     For memory space conservation and execution speed
             this implementation compares the first 20
             characters of both strings only if longer strings
             are supplied to 1_distance ().
             '#define COMP_LEN' may be changed to decrease or
             increase the number of characters compared.

             De-commenting the following '#define DEBUG' will
             create a stand-alone program, which enables you
             to experiment with different values for the
             constants 'ADDITION', 'CHANGE' and 'DELETION'.
*/

/* #define DEBUG */

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

#ifdef DEBUG
#include <stdio.h>
#define PRINTF printf
#define PRINTF2 printf
#else
#define PRINTF(_a)
#define PRINTF2(_a,_b)
#endif

#define ADDITION         1               /* change constants in this block */
#define CHANGE           3               /* of four lines if needed.       */
#define DELETION         5
#define COMP_LEN         20

#define ARR_SIZE                COMP_LEN + 1
#define SMALLEST_OF(x,y,z)      ((x<y) ? min (x,z) : min (y,z))
#define ZERO_IF_EQUAL(x,y)      ( requested[x-1] == found[y-1] ? 0 : CHANGE)

int l_distance (char *requested, char *found)
{

       int i, r_len, f_len;
       register int j, itmp, idist, iprev;
       int     distance [ARR_SIZE];

       if ((r_len = strlen (requested)) > COMP_LEN)
              r_len = COMP_LEN;
       if ((f_len = strlen (found))     > COMP_LEN)
              f_len = COMP_LEN;

       PRINTF ("\n");
       distance[0] = itmp = 0;
       for (j = 1; j <= ARR_SIZE; j++)
              distance[j] = itmp += ADDITION;
       for (i = 1; i <= r_len; i++) {
              iprev = distance[0] + DELETION;
           for (j = 1; j <= f len; j++, iprev = idist}    {
                    idist = iprev + ADDITION;
                    if ((itmp = distance [j-1] + ZERO_IF_EQUAL(i,j)) < idist)
                           idist = itmp;
                    distance [j-1] = iprev;
                    if ((itmp - distance[j] + DELETION) < idist)
                           idist = itmp;
                    PRINTF2 (" %3d", idist);
              }
              distance [f_len] = idist;
              PRINTF ("\n");
       }

       return idist;
}

#ifdef DEBUG
void usage ()
{
   printf("\nUsage:  LD requested found\n");
      printf("\n        requested & found are the two strings");
      printf("\n        to be compared with the Levenstein distance");
   printf("\n        algorithm.\n\n");
}

int main (int argc, char *argv [])
{
   int result;

   if (argc != 3) {
      usage ();
      exit (1);
   } else {
      printf ("\nComparing '%s' and '%s':\n", argv[1], argv[2]);
      result = l_distance (argv[1], argv[2]);
      printf ("\nResult = %d\n", result);
   }
   return (0);
}
#endif

/* End of File */