// ************************************************************************** //
//                                                                            //
//    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                                             //
//                                                                            //
// ************************************************************************** //
// CombSort improves BubbleSort in a similar way as ShellSort improves        //
// InsertionSort: To avoid turtles in BubbleSort (i.e. small values on the    //
// right of the list), CombSort makes use of gap sequence. This way, turtles  //
// move faster during the first phases where the gaps are large. The final    //
// phase is made with gap=1 and therefore is BubbleSort which is enough to    //
// assure correctness.                                                        //
// ************************************************************************** //

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

module CombSort([aSize]nat{iSize} ?a,b, event !ready) {
    nat{aSize+1} i;
    bool swapped;

    [hSize]nat{iSize} steps;
    nat{hSize} s;

    s = hSize-1;
    steps[0] = 1;
    steps[1] = 2;
    steps[2] = 3;
    steps[3] = 6;

    for(i=0..aSize-1)
        b[i] = a[i];

    i = 0;
    do {
        // perform BubbleSort using gap step[s]
        next(swapped) = false;
        w0: pause;
        do {
            if(b[i+steps[s]] < b[i]) {
                next(b[i]) = b[i+steps[s]];
                next(b[i+steps[s]]) = b[i];
                next(swapped) = true;
            }
            next(i) = i+1;
            w1: pause;
        } while(i+steps[s]<aSize-1);
        if(b[i+steps[s]] < b[i]) {
            next(b[i]) = b[i+steps[s]];
            next(b[i+steps[s]]) = b[i];
            next(swapped) = true;
        }
        if(s>0) next(s) = s-1;
        next(i) = 0;
        w2: pause;
    } while(swapped | s!=0);
    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);
}