// ************************************************************************** //
//                                                                            //
//    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                                             //
//                                                                            //
// ************************************************************************** //
// The following module removes duplicates from an array of length N. It works//
// with depth O(log(N)) and work O(N^2).                                      //
// ************************************************************************** //

macro N=8;

module RemoveDuplicates([N]int ?x,!y,event !rdy) {
    [N]nat rank;
    [N]bool dup;
    // -------------------------------------------------------------------------
    // determine the indices of the duplicates
    // -------------------------------------------------------------------------
    for(i=0..N-2)
        for(j=i+1..N-1)
            if(x[i]==x[j])
                dup[j] = true;

    // -------------------------------------------------------------------------
    // count the number of duplicates left to an index (including it)
    // by a parallel prefix sum over array rank
    // -------------------------------------------------------------------------
    for(i=0..N-1)
        rank[i] = (dup[i]?1:0);
    // bottom-up traversal: time log(n) with n-1 work and n/2 processors
    for(l=1..log(N)) {
        for(j=1..N/exp(2,l)) {
            next(rank[j*exp(2,l)-1]) = rank[j*exp(2,l)-1] + rank[(2*j-1)*exp(2,l-1)-1];
        }
        pause;
    }
    // top-down traversal: time log(N)-1 with N-log(N)-1 work and N/2 proc.
    for(i=1..log(N)-1) {
        let(l = log(N)-i)
        for(j=1..exp(2,i)-1) {
            next(rank[(2*j+1)*exp(2,l-1)-1]) = rank[(2*j+1)*exp(2,l-1)-1] + rank[j*exp(2,l)-1];
        }
        pause;
    }
    // -------------------------------------------------------------------------
    // assign the array elements that are no duplicates; note that we need the
    // array dup here again to avoid write conflicts
    // -------------------------------------------------------------------------
    for(i=0..N-1)
        if(not(dup[i]))
            y[i-rank[i]] = x[i];
    emit(rdy);

}
drivenby t0 {
    x = [1,2,2,3,1,4,2,3];
    await(rdy);
}