// ************************************************************************** //
//                                                                            //
//    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                                             //
//                                                                            //
// ************************************************************************** //


// ----------------------------------------------------------------
// In this file, we take the algorithms of KuLL87a.qrz and map one
// of the three iterations to time. Thus, the three-dimensional
// arrays become two-dimensional.
// ----------------------------------------------------------------

// ----------------------------------------------------------------
// The reference is the following O(N) time version of Warshall's
// algorithm (see WarshallAB.qrz for equivalent variants).
// ----------------------------------------------------------------

package ComputerArchitecture.SystolicArrays.TransitiveClosure.Warshall;

macro N = 3;

// ----------------------------------------------------------------
// The following versions are obtained by the elimination of spiral
// dependencies as described in KuLL87a.qrz.
// ----------------------------------------------------------------

module TimedOpt1RotLocDepWarshall([N][N]bool ?a, t, event !OnlyReflexive) {
    event [N][N]bool c, r;
    
    /*for(i=0..(N-1))
        for(j=0..(N-1)) {
            c[i][j] = ((j==0) ? a[i][0] : c[i][j-1]);
            r[i][j] = ((i==0) ? a[0][j] : r[i-1][j]);
            if((i==0)|(j==0))
                next(t[(i-1)%N][(j-1)%N]) = a[i][j];
            else
                next(t[(i-1)%N][(j-1)%N]) = a[i][j] | c[i][j] & r[i][j];
        }
    */
    
    //--- START WORKAROUND ---
    c[0][0] = a[0][0];
    r[0][0] = a[0][0];
    
    next(t[abs ((-1)%N)][abs ((-1)%N)]) = a[0][0];
    
    for(j=1..(N-1)) {
        c[0][j] = c[0][j-1];
        r[0][j] = a[0][j];
        next(t[abs ((-1)%N)][abs ((-1+j)%N)]) = a[0][j];
    }
    
    for(i=1..(N-1)){
        c[i][0] = a[i][0];
        r[i][0] = r[i-1][0];
        next(t[abs ((-1+i)%N)][abs ((-1)%N)]) = a[i][0];
    }
        
    for(i=1..(N-1))
        for(j=1..(N-1)) {
            c[i][j] = c[i][j-1];
            r[i][j] = r[i-1][j];
            next(t[abs ((-1+i)%N)][abs ((-1+j)%N)]) = a[i][j] | c[i][j] & r[i][j];
        }
    //--- END WORKAROUND ---
    pause;
    for(k=1..(N-1)) {
        /*for(i=0..(N-1))
            for(j=0..(N-1)) {
                c[i][j] = ((j==0) ? t[i][j] : c[i][j-1]);
                r[i][j] = ((i==0) ? t[i][j] : r[i-1][j]);
                if((i==0)|(j==0))
                    next(t[(i-1)%N][(j-1)%N]) = t[i][j];
                else
                    next(t[(i-1)%N][(j-1)%N]) = t[i][j] | c[i][j] & r[i][j];
            }
        */
        //--- START WORKAROUND ---
        c[0][0] = t[0][0];
        r[0][0] = t[0][0];
        
        next(t[abs ((-1)%N)][abs ((-1)%N)]) = t[0][0];
        
        for(i=1..(N-1)) {
            c[i][0] = t[i][0];
            r[i][0] = r[i-1][0];
            next(t[abs ((-1+i)%N)][abs ((-1)%N)]) = t[i][0];
        }
            
        for(j=1..(N-1)) {
            c[0][j] = c[0][j-1];
            r[0][j] = t[0][j];
            next(t[abs  ((-1)%N)][abs ((-1+j)%N)]) = t[0][j];
        }
        
        for(i=1..(N-1))
            for(j=1..(N-1)) {
                c[i][j] = c[i][j-1];
                r[i][j] = r[i-1][j];
                next(t[abs ((-1+i)%N)][abs ((-1+j)%N)]) = t[i][j] | c[i][j] & r[i][j];
            }
        //--- END WORKAROUND ---

        pause;
    }
}