// ************************************************************************** //
//                                                                            //
//    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                                             //
//                                                                            //
// ************************************************************************** //
// ShearSort is parallel sorting algorithm that is performed on a MxN array.  //
// The sorted sequence will finally be mapped to the array in a snake-like    //
// row major indexing scheme, as eg.                                          //
//                                                                            //
//     01 02 03 04                                                            //
//     08 07 06 05                                                            //
//     09 10 11 12                                                            //
//     16 15 14 13                                                            //
//                                                                            //
// The algorithm is due to [Scherson & Sen, 1989], and works by performing    //
// a loop of column sorts and row sorts until the array is sorted. The        //
// version below makes use of selection sort to for the column and row        //
// sorting phases which is not that efficient.                                //
// ************************************************************************** //

macro N = 4;
macro M = 4;
macro I = 64;

module ShearOddEvenSort([M*N]int{I} ?a,[M][N]int{I}b, event ready) {
    bool swapped,colsorted,rowsorted,firstRound;
    // gather the input row-wise in the matrix
    for(i=0..(M-1))
        for(j=0..(N-1))
            b[i][j] = a[i*N+j];

    firstRound = true;
    weak abort
        loop {
            // column-wise sorting by OddEvenSort
            colsorted = false;
            while(!colsorted) {
                next(colsorted) = true;
                colOddStep: pause;
                for(j=0..(N-1)) {
                    for(i=0..(M-3)/2){
                        if(b[2*i+1][j]>b[2*i+2][j]) {
                            next(b[2*i+2][j]) = b[2*i+1][j];
                            next(b[2*i+1][j]) = b[2*i+2][j];
                            next(colsorted) = false;
                            next(swapped) = true;
                            }
                        }
                }
                colEvenStep: pause;
                for(j=0..(N-1)) {
                    for(i=0..(M-2)/2){
                        if(b[2*i][j]>b[2*i+1][j]) {
                            next(b[2*i][j]) = b[2*i+1][j];
                            next(b[2*i+1][j]) = b[2*i][j];
                            next(colsorted) = false;
                            next(swapped) = true;
                            }
                        }
                }
                next(rowsorted) = false;
                colCheckSorted: pause;
            }
            if(!swapped&!firstRound) emit(ready);
            else next(swapped) = false;
            // row-wise sorting by OddEvenSort
            while(!rowsorted) {
                next(rowsorted) = true;
                rowOddStep: pause;
                for(i=0..(M-1)) do || {
                    for(j=0..(N-3)/2){
                        if((i%2==0?b[i][2*j+1]>b[i][2*j+2]:b[i][2*j+1]<b[i][2*j+2])) {
                            next(b[i][2*j+2]) = b[i][2*j+1];
                            next(b[i][2*j+1]) = b[i][2*j+2];
                            next(rowsorted) = false;
                            next(swapped) = true;
                            }
                        }
                }
                rowEvenStep: pause;
                for(i=0..(M-1)) do || {
                    for(j=0..(N-2)/2){
                        if((i%2==0?b[i][2*j]>b[i][2*j+1]:b[i][2*j]<b[i][2*j+1])) {
                            next(b[i][2*j]) = b[i][2*j+1];
                            next(b[i][2*j+1]) = b[i][2*j];
                            next(rowsorted) = false;
                            next(swapped) = true;
                            }
                        }
                    }
                next(colsorted) = false;
                rowCheckSorted: pause;
            }
            if(!swapped&!firstRound) emit(ready);
            else next(swapped) = false;
            firstRound = false;
        }
    when(ready);
}
drivenby Test01 {
    // generate already sorted sequence
    for(i=0..M*N-1) a[i] = i;
    dw: await(ready);
    // check that rows are sorted in snake-like order
    for(i=0..M-1) 
        if(i%2==0)
            assert(forall(p=1..N-1) (b[i][p-1]<=b[i][p]));
        else
            assert(forall(p=1..N-1) (b[i][p-1]>=b[i][p]));
    // and check that the first and last column are sorted
    assert(forall(p=1..M-1) (b[p-1][0]<=b[p][0]));
    assert(forall(p=1..M-1) (b[p-1][N-1]<=b[p][N-1]));
}
drivenby Test02 {
    // generate reversed sorted sequence
    for(i=0..M*N-1) a[i] = M*N-1-i;
    dw: await(ready);
    // check that rows are sorted in snake-like order
    for(i=0..M-1) 
        if(i%2==0)
            assert(forall(p=1..N-1) (b[i][p-1]<=b[i][p]));
        else
            assert(forall(p=1..N-1) (b[i][p-1]>=b[i][p]));
    // and check that the first and last column are sorted
    assert(forall(p=1..M-1) (b[p-1][0]<=b[p][0]));
    assert(forall(p=1..M-1) (b[p-1][N-1]<=b[p][N-1]));
}
drivenby Test03 {
    for(i=0..M*N-1)
        a[i] = ((i%2==0)?i:((M*N%2==0)?M*N-i:M*N-1-i));
    dw: await(ready);
    // check that rows are sorted in snake-like order
    for(i=0..M-1) 
        if(i%2==0)
            assert(forall(p=1..N-1) (b[i][p-1]<=b[i][p]));
        else
            assert(forall(p=1..N-1) (b[i][p-1]>=b[i][p]));
    // and check that the first and last column are sorted
    assert(forall(p=1..M-1) (b[p-1][0]<=b[p][0]));
    assert(forall(p=1..M-1) (b[p-1][N-1]<=b[p][N-1]));
}