inline_levenshtein

New file: inline_levenshtein
inline do |builder|
  builder.add_link_flags '-lruby'

  builder.c_raw <<-EOT
  long minimum(long a,long b,long c)
  /*Gets the minimum of three values*/
  {
    long min=a;
    if(b<min)
      min=b;
    if(c<min)
      min=c;
    return min;
  }
  EOT

  builder.c <<-EOT


  /****************************************/
  /*Implementation of Levenshtein distance*/
  /****************************************/

  long levenshtein_distance(char *s,char*t)
  /*Compute levenshtein distance between s and t*/
  {
    //Step 1
    long k,i,j,n,m,cost,*d,distance;
    n=strlen(s); 
    m=strlen(t);
    if(n!=0&&m!=0)
    {
      d=malloc((sizeof(long))*(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]=minimum(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.
  }

  EOT
end