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