// ************************************************************************** //
//                                                                            //
//    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 Levenshtein distance as implemented in module DistanceLevenshtein      //
// requires O(M*N) space. Considering the data dependencies reveals that one  //
// can also implement the (sequential) algorithm as shown below where only    //
// O(N) space is required. The algorithm requires O(M) macro steps and each   //
// macro step executes O(N) micro steps that linearly depend on each other, so//
// that this is really a sequential algorithm. The advantage is however, that //
// only O(N) space is required due to the local arrays d_old and d_new.       //
// ************************************************************************** //

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


module EditDistanceLinearSpace([M]nat{C} ?a,[N]nat{C} ?b,nat{C} dist,event rdy) {
    [N+1]nat{max(M,N)+1} d_new,d_old;

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

    // recursive definitions (applied row by row)
    for(i=1..M) {
        d_new[0] = i;
        next(d_old[0]) = d_new[0];
        for(j=1..N) {
            d_new[j] = min3(d_old[j-1] + (a[i-1]==b[j-1]?0:1),
                            d_new[j-1] + 1,
                            d_old[j] + 1);
            next(d_old[j]) = d_new[j];
        }
        pause;
    }
    // final result
    dist = d_old[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);
}