// ************************************************************************** //
//                                                                            //
//    eses                   eses                                             //
//   eses                     eses                                            //
//  eses    eseses  esesese    eses   Embedded Systems Group                  //
//  ese    ese  ese ese         ese                                           //
//  ese    eseseses eseseses    ese   Department of Computer Science          //
//  eses   eses          ese   eses                                           //
//   eses   eseses  eseseses  eses    University of Kaiserslautern            //
//    eses                   eses                                             //
//                                                                            //
// ************************************************************************** //
// The edit (Levenshtein) distance of sequences a[0..M-1] and b[0..N-1] is    //
// defined as the minimum number of insertions, deletions, or substitutions to//
// transform one string into the other one. The definition of the distance as //
// directly implemented in module DistanceLevenshtein shows that the matrix   //
// elements d[i][j] that will store the distance between prefixes a[0..i] and //
// b[0..j] have data dependencies such that d[i][j] depends on d[i-1][j-1],   //
// d[i-1][j], and d[i][j-1]. Therefore, one can compute the elements of matrix//
// d step by step where in each step, a diagonal of the matrix is computed.   //
// In the implementation below, the O(M*N) operations are scheduled to O(M+N) //
// dependent macro steps where each step executes between 1 and min(M,N) many //
// micro steps (note that min(M,N) is the length of the longest diagonal).    //
// Note that the space requirement can be reduced to O(min(M,N)) since each   //
// diagonal only refers to value of the two previously computed diagonals.    //
// ************************************************************************** //

macro M = 4;    // size of sequence a
macro N = 5;    // size of sequence b
macro C = 8;    // sequence elements have type nat{C}
macro max(x,y) = (x<y ? y : x);
macro min(x,y) = (x<y ? x : y);
macro min3(x,y,z) = min(x,min(y,z));
macro minMN = min(M,N);


module EditDistanceParallel([M]nat{C} ?a,[N]nat{C} ?b,nat{C} dist,event !rdy) {
    [M+1][N+1]nat{max(M,N)+1} d;

    // distances from a[0..i-1] to b[0..-1] (i.e., b is empty)
    for(i=0..M)
        d[i][0] = i;

    // distances from a[0..-1] to b[0..j-1] (i.e., a is empty)
    for(j=0..N)
        d[0][j] = j;

    // define diagonals step-by-step
    for(k=2..M+N) {
        for(i=abs(max(1,+k-N))..min(M,k-1)) {
            let(j=k-i)
            next(d[i][j]) = min3(d[i-1][j-1] + (a[i-1]==b[j-1] ? 0 : 1),
                                 d[i][j-1] + 1,
                                 d[i-1][j] + 1);
        }
        pause;
    }

    // final result
    dist = d[M][N];
    emit(rdy);
}
drivenby {
    // dist=3 since a[0]=0;a[2]=3;a[4]=6;
    a = [1,2,2,3];
    b = [0,2,3,3,6];
    await(rdy);
    assert(dist==3);
}