;;;; levenshtein.scm - by Lorenzo Seidinari and Lars Rustemeier


(declare
 (foreign-declare #<<EOF
#define min(a,b) ( ((a)<(b)) ? (a) : (b) )
#define min3(a,b,c) min(min((a),(b)),(c))
EOF
))

;; ******************************************
;; * Implementation of Levenshtein distance *
;; ******************************************

;; Compute levenshtein distance between s and t */

(define levenshtein-distance
  (foreign-callback-lambda* 
   int ((c-string s) (c-string t))
"
  //Step 1
  int k,i,j,n,m,cost,*d,distance;
  n=strlen(s);
  m=strlen(t);
  if(n!=0&&m!=0) {
    d=(int*)malloc((sizeof(int))*(m+1)*(n+1));
    m++;
    n++;
    //Step 2
    for(k=0;k<n;k++)
      d[k]=k;
    for(k=0;k<m;k++)
      d[k*n]=k;
    //Step 3 and 4
    for(i=1;i<n;i++)
      for(j=1;j<m;j++) {
	//Step 5
	if(s[i-1]==t[j-1])
	  cost=0;
	else
	  cost=1;
	//Step 6	
	d[j*n+i]=min3(d[(j-1)*n+i]+1,d[j*n+i-1]+1,d[(j-1)*n+i-1]+cost);
      }
    distance=d[n*m-1];
    free(d);          
    return(distance);
  }
  else
    return(-1); //a negative return value means that one or both strings are empty.
"))