// ************************************************************************** //
//                                                                            //
//    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 finds for each node in a forest of trees its root. The//
// forest of trees is encoded by an array that assigns node i its predecssor  //
// root pre[i]. The algorithm runs with O(log(N)) steps with work O(N*log(N)).//
// ************************************************************************** //

macro N=16;

module FindRoots([N]nat ?pre,root,event !rdy) {
    // -------------------------------------------------------------------------
    // first copy the predecessors to the root array
    // -------------------------------------------------------------------------
    for(i=0..N-1)
        root[i] = pre[i];
    // -------------------------------------------------------------------------
    // pointer jumping: copy the root of the root log(N) times
    // -------------------------------------------------------------------------
    for(l=1..log(N)) {
        for(i=0..N-1)
            next(root[i]) = root[root[i]];
        pause;
    }
    emit(rdy);
}
drivenby t0 {
    //     0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
    pre = [0,0,1,1,0,4,7,8,8,8, 9, 9, 3, 3, 6, 6];
    await(rdy);
}
drivenby t1 {
    //     0 1 2 3 4 5 6 7 8  9 10 11 12 13 14 15
    pre = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,15];
    await(rdy);
}