// ************************************************************************** //
//                                                                            //
//    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                                             //
//                                                                            //
// ************************************************************************** //
// ShellSort [Shel59,Cyph89,PlPS92,Sedg96,JiLV00,Ciur01] is usually presented //
// as a variant of InsertionSort (see comments in file ShellSort). However, it//
// can also be used with BubbleSort to perform a gap-sorting of the sequence, //
// which is remarked in many references including [Sedg96]. Using BubbleSort  //
// allows to implement ShellSort as a sorting network as shown below. The     //
// remarkable fact is that using the gap sequence 1,2,3,4,6,8,9,12,16,...,    //
// 2^p3^q one obtains a sorting network of depth O(N*log^2(N)) which is the   //
// same depth as the sorting networks obtained by MergeSortBitonic and        //
// MergeSortOddEven. The implementation of ShellSort is however much simpler, //
// however, it requires more comparators than MergeSortBitonic and            //
// MergeSortOddEven.                                                          //
// ************************************************************************** //

macro aSize = 16;
macro iSize = 64;
macro hSize = 8;

macro step(i) = 
    (i==0?12
    :(i==1?9
    :(i==2?8
    :(i==3?6
    :(i==4?4
    :(i==5?3
    :(i==6?2:1)))))));


module ShellSortNet1([aSize]nat{iSize} ?a,b, event !ready) {

    for(i=0..aSize-1)
        b[i] = a[i];       
  
    // perform one round of BubbleSort using gaps steps(0)..steps(hSize-1);
    // note that steps(i) of the swaps in round s=stop
    for(s=0..hSize-1) {
        for(i=0..aSize-step(s)-1) {
            if(b[i]>b[i+step(s)]) {
                next(b[i+step(s)]) = b[i];
                next(b[i]) = b[i+step(s)];
            }
            if(i%step(i)==0) 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);
}