// ************************************************************************** //
//                                                                            //
//    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                                             //
//                                                                            //
// ************************************************************************** //
// CountSort is a simple algorithm that counts the number of array elements   //
// c[a[i]] that are less than or equal to a[i] so that the sorted array       //
// can be easily generated. The algorithm is linear in aSize, but requires    //
// two additional arrays b and c, where c is indexed by the range of array a. //
// ************************************************************************** //

macro aSize = 16;
macro iSize = 64;

module CountSort([aSize]nat{iSize} ?a,b, event !ready) {
    [iSize]nat{aSize+1} c;

    // count the number of occurrences of each a[i]
    for(i=0..aSize-1) {
        next(c[a[i]]) = c[a[i]]+1;
        w1: pause;
    }

    // count the number of elements less than or equal to a[i]
    for(i=1..aSize-1) {
        next(c[i]) = c[i]+c[i-1];
        w2: pause;
    }

    // generate the sorted array
    for(i=0..aSize-1) {
        b[c[a[aSize-i-1]]-1] = a[aSize-i-1];
        next(c[a[aSize-i-1]]) = c[a[aSize-i-1]]-1;
        w3: 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);
}