// ************************************************************************** //
//                                                                            //
//    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                                             //
//                                                                            //
// ************************************************************************** //
// OddEvenSort is similar to BubbleSort, but lends itself better to parallel  //
// implementation as shown below. The algorithm works as follows: Each        //
// iteration consists of an oddStep and an evenStep. In oddStep, the algorithm//
// checks the pairs (1,2);(3,4);(5,6);... for swaps, and in the evenStep, it  //
// checks the pairs (0,1);(2,3);(4,5);... for swaps. It is easily seen that   //
// the array is sorted if there was neither a swap in the oddStep nor in the  //
// evenStep.                                                                  //
// The algorithm can be easily parallelized in that all the swaps checked and //
// done in the oddStep and the evenStep, respectively, are done in parallel.  //
// This way, N processors are required to sort a list of size N with N steps. //
// To determine the loop bounds for oddStep and evenStep, consider the cases  //
// (1) aSize=2N (with N:=aSize/2):                                            //
//     oddStep:  (1,2);(3,4);(5,6);...;(2N-3,2N-2)                            //
//     evenStep: (0,1);(2,3);(4,5);...;(2N-2,2N-1)                            //
//     and we have (aSize-3)/2 = (2N-3)/2 = N-2                               //
//     and (aSize-2)/2 = (2N-2)/2 = N-1                                       //
// (2) aSize=2N+1 (with N:=aSize/2):                                          //
//     oddStep:  (1,2);(3,4);(5,6);...;(2N-1,2N)                              //
//     evenStep: (0,1);(2,3);(4,5);...;(2N-2,2N-1)                            //
//     and we have (aSize-3)/2 = (2N-2)/2 = N-1                               //
//     and (aSize-2)/2 = (2N-1)/2 = N-1                                       //
// ************************************************************************** //

macro aSize = 16;
macro iSize = 64;

module OddEvenSort([aSize]int{iSize} ?a,b, event !ready) {
    bool sorted;
    for(i=0..(aSize-1))
        b[i] = a[i];
    sorted = false;
    while(!sorted) {
        next(sorted) = true;
        oddStep: pause;
        for(i=0..(aSize-3)/2){
            if(b[2*i+1]>b[2*i+2]) {
                next(b[2*i+2]) = b[2*i+1];
                next(b[2*i+1]) = b[2*i+2];
                next(sorted) = false;
                }
            }
        evenStep: pause;
        for(i=0..(aSize-2)/2){
            if(b[2*i]>b[2*i+1]) {
                next(b[2*i]) = b[2*i+1];
                next(b[2*i+1]) = b[2*i];
                next(sorted) = false;
                }
            }
        checkSorted: pause;
    }
    emit(ready);
}
drivenby Test01 {
    for(i=0..aSize-1) a[i] = i;
    dw: await(ready);
    for(i=0..aSize-1) assert(b[i] == i);
}
drivenby Test02 {
    for(i=0..aSize-1) a[i] = aSize-1-i;
    dw: await(ready);
    for(i=0..aSize-1) assert(b[i] == i);
}
drivenby Test03 {
    for(i=0..aSize-1)
        a[i] = ((i%2==0)?i:((aSize%2==0)?aSize-i:aSize-1-i));
    dw: await(ready);
    for(i=0..aSize-1) assert(b[i] == i);
}