#define FRC_NO_ICU 1
#include "FRC.h"

#include "rnn.h"




int dldist2(char const * s, char const * t, int n, int m);

int editDistance(const std::string& s1, const std::string& s2)
{
	return dldist2(s1.c_str(), s2.c_str(), s1.length(), s2.length());
	// Eigen::ArrayXXi dd(s1.length(), s2.length());
}

#define d(i,j) dd[(i) * (m+2) + (j) ]
#define min(x,y) ((x) < (y) ? (x) : (y))
#define min3(a,b,c) ((a)< (b) ? min((a),(c)) : min((b),(c)))
#define min4(a,b,c,d) ((a)< (b) ? min3((a),(c),(d)) : min3((b),(c),(d)))
#undef INFINITY

// void dprint(int* dd, int n,int m){
 // int i,j;
 // for (i=0; i < n+2;i++){
    // for (j=0;j < m+2; j++){
        // printf("%02d ",d(i,j));
    // }
    // printf("\n");
 // }
 // printf("\n");
// }

int dldist2(char const * s, char const * t, int n, int m) {
	int *dd;
	int i, j, cost, i1,j1;
	int INFINITY = n + m;
	std::array<int, 256> DA;
	
	DA.fill(0);

	if (!(dd = (int*) malloc((n+2)*(m+2)*sizeof(int)))) {
		return -1;
	}

	d(0,0) = INFINITY;
	for(i = 0; i < n+1; i++) {
		d(i+1,1) = i ;
		d(i+1,0) = INFINITY;
	}
	for(j = 0; j<m+1; j++) {
		d(1,j+1) = j ;
		d(0,j+1) = INFINITY;
	}      
	// dprint(dd,n,m);

	for(i = 1; i< n+1; i++) {
		int DB = 0;
		for(j = 1; j< m+1; j++) {
			i1 = DA[t[j-1]];
			j1 = DB;
			cost = ((s[i-1]==t[j-1])?0:1);
			if(cost==0)
				DB = j;
			d(i+1,j+1) =
				min4(d(i,j)+cost,
				d(i+1,j) + 1,
				d(i,j+1)+1, 
				d(i1,j1) + (i-i1-1) + 1 + (j-j1-1));
		}
		DA[s[i-1]] = i;
		// dprint(dd,n,m);
	}
	cost = d(n+1,m+1);
	free(dd);
	return cost;
}