MODULE RedSquare;
(*
 * To find the maximum sized square of ones in an array of ones and zeroes.
 * --------------------------------------------------------------------------
 *)

IMPORT  InOut     : IO;  (* Input/output routines                     *)
IMPORT  Matrices  : M ;  (* Generate, Copy, Verify and Print Matrices *)
IMPORT  StatsLib  : SL;  (* Various statistics gathering routines *)
IMPORT	Params;		 (* Obtain program parameters *)
IMPORT	String;

IMPORT  PARALLEL  ;

(* ------------------------------------------------------------------------ *)

CONST

  LIMIT = M.ArrayLimit;   (* Size for arrays to contain matrices *)

VAR

  Data       : M.Ints;    (* Data matrix *)

  Seed       : INTEGER;   (* Used to seed random array generation *)

  Degree     : INTEGER;   (* Specifies degree of parallelism if required *)

  Size       : INTEGER;   (* Specifies actual array size in use *)

  Alg	     : ARRAY [0..2] OF CHAR;  (* Specifies the algorithm to execute *)

  Result     : ARRAY [1..20] OF INTEGER; (* Var which stores answer *)
  i, MaxR, MaxC : INTEGER; (* row,col indicies of lgst square, top left cnr *)

  Complete   : BOOLEAN;

(* ------------------------------------------------------------------------ *)
(* ------------------------------------------------------------------------ *)

PROCEDURE  Seq ( VAR  MAT : M.Ints );
(* Perform a sequential scan for the maximum square
 * in the 1..Size by 1..Size
 * subarray of MAT, return the maximum area as the result.
 *)

  VAR
    Row     : INTEGER;	(* current row *)
    Col     : INTEGER;	(* current column *)
    min     : INTEGER; 	(* maximum value seen so far *)
    a, b, c : INTEGER;	(* values to be compared *)

  BEGIN  (* Seq *)

    Result[1] := MAT[1,1];

    FOR Row := 2 TO Size DO
      FOR Col := 2 TO Size DO
	IF MAT[Row, Col] > 0 THEN
	    a := MAT[Row, Col-1];
	    b := MAT[Row-1, Col];
	    c := MAT[Row-1, Col-1];
	    IF a > b THEN
		    min := b;
	    ELSE 
		    min := a;
	    END;
	    IF c < min THEN
		    min:= c;
	    END;
	    MAT[Row, Col] := min + 1;
	    IF MAT[Row, Col] > Result[1] THEN Result[1] := MAT[ Row, Col ] END;
	END
      END
    END;
  END  Seq ;

(* 
   ------------------------------------------------------------------------ *)

PROCEDURE  PPar ( ROW : INTEGER;  VAR MAT : M.Ints ) ;
(* Perform a parallel scan on 1..Size by 1..Size of MAT to
 * yield its maximum.  Size copies of Par are spawned where
 * each performs the scan on a specified ROW.
 * Results are returned using the global Maximum MUTEX variable.
 *)

  VAR
    Col     : INTEGER;	(* current column *)
    RM1     : INTEGER; 	(* ROW - 1 *)
    min     : INTEGER; 	(* min of 3 values *)
    i       : INTEGER; 	(* index *)
    a, b, c : INTEGER;	(* values to be compared *)

  BEGIN  (* PPar *)

      FOR i := 2 to ROW DO SYNC; END;

      Result[ROW] := 0;
      RM1 := ROW-1;

      FOR Col := 2 TO Size DO
	IF MAT[ROW, Col] > 0 THEN
	    a := MAT[ROW, Col-1];
	    b := MAT[RM1, Col];
	    c := MAT[RM1, Col-1];
	    IF a > b THEN
		    min := b;
	    ELSE 
		    min := a;
	    END;
	    IF c < min THEN
		    min:= c;
	    END;
	    MAT[ROW, Col] := min + 1;
	    IF MAT[ROW, Col] > Result[ROW] THEN
		Result[ROW] := MAT[ ROW, Col ]
	    END;
	END;
	SYNC;
      END;
      IF Result[1] < Result[ROW] THEN
	Result[1] := Result[ROW];
      END;
	
  END  PPar ;


PROCEDURE  KPar ( ROW : INTEGER;  VAR MAT : M.Ints ) ;
(* Perform a parallel scan on 1..Size by 1..Size of MAT to
 * yield its maximum.  Degree copies of KPar are spawned where
 * each performs the scan on a number of rows.
 * Results are returned using the global Maximum MUTEX variable.
 *)

  VAR
    Col     : INTEGER;	(* current column *)
    Row     : INTEGER;	(* current row *)
    Max     : INTEGER; 	(* local maximum *)
    min     : INTEGER; 	(* min of 3 values *)
    i       : INTEGER; 	(* index *)
    a, b, c : INTEGER;	(* values to be compared *)

  BEGIN  (* KPar *)

    FOR i := 1 to ROW DO SYNC; END;

    Result[ROW] := 0;

    Row := ROW+1;
    WHILE Row <= Size DO
      FOR Col := 2 TO Size DO
	IF MAT[Row, Col] > 0 THEN
	    a := MAT[Row, Col-1];
	    b := MAT[Row-1, Col];
	    c := MAT[Row-1, Col-1];
	    IF a > b THEN
		    min := b;
	    ELSE 
		    min := a;
	    END;
	    IF c < min THEN
		    min:= c;
	    END;
	    MAT[Row, Col] := min + 1;
	    IF MAT[Row, Col] > Result[ROW] THEN
		Result[ROW] := MAT[ Row, Col ]
	    END;
	END;
	SYNC;
      END;
      Row := Row + Degree;
    END;

    IF Result[1] < Result[ROW] THEN
	Result[1] := Result[ROW];
    END;

  END  KPar ;


PROCEDURE  KKPar ( ROW : INTEGER;  VAR MAT : M.Ints ) ;
(* Perform a parallel scan on 1..Size by 1..Size of MAT to
 * yield its maximum.  Degree copies of KPar are spawned where
 * each performs the scan on a number of rows.
 * Results are returned using the global Maximum MUTEX variable.
 *)

  VAR
    Col     : INTEGER;	(* current column *)
    Row     : INTEGER;	(* current row *)
    Max     : INTEGER; 	(* local maximum *)
    min     : INTEGER; 	(* min of 3 values *)
    a, b, c : INTEGER;	(* values to be compared *)

  BEGIN  (* KKPar *)

    Result[ROW] := 0;
    Row := ROW+1;

    WHILE NOT Complete DO
	SYNC;
	Complete := TRUE;
	SYNC;
	WHILE Row <= Size DO
	  FOR Col := 2 TO Size DO
	    IF MAT[Row, Col] > 0 THEN
		a := MAT[Row, Col-1];
		b := MAT[Row-1, Col];
		c := MAT[Row-1, Col-1];
		IF a > b THEN
			min := b;
		ELSE 
			min := a;
		END;
		IF c < min THEN
			min:= c;
		END;
		IF MAT[Row,Col] # min+1 THEN
		    Complete := FALSE;
		END;
		MAT[Row, Col] := min + 1;
		IF MAT[Row, Col] > Result[ROW] THEN
		    Result[ROW] := MAT[ Row, Col ];
		END;
	    END;
	  END;
	  Row := Row + Degree;
	END;
	SYNC;
    END;

  END  KKPar ;

(* 
   ------------------------------------------------------------------------ *)

BEGIN   (*  Find Max  *)

    NOTIME

	Params.GetAlg( Alg, "s,S,k,K,p,P" );

	Params.GetSize( LIMIT, Size );

        IF String.EqualAlg(Alg, "k") OR String.EqualAlg(Alg, "K") THEN
		Params.GetDegree( Size, Size, Degree ) END;

	Params.GetSeed( Seed );

	M.GenLimitedI( 0, 2, Size, Size, Data, Seed );
	(*
	M.PrintI(Size, Size, Data);
	*)

    END;

        IF String.EqualAlg(Alg, "s") OR String.EqualAlg(Alg, "S") THEN

 	    NOTIME SL.Start(0); END;

		Seq ( Data );

	    NOTIME SL.Finish END;

	ELSIF String.EqualAlg(Alg, "p") OR String.EqualAlg(Alg, "P") THEN

 	    NOTIME SL.Start(0); END;

		PPar ( 2..Size, Data );

	    NOTIME SL.Finish END;

	ELSIF String.EqualAlg(Alg, "K") THEN

 	    NOTIME SL.Start(0); END;
		
		KKPar ( 1..Degree, Data ); 

	    NOTIME SL.Finish END;

		FOR i := 1 TO Degree DO
		  IF Result[i] > Result[1] THEN
		      Result[1] := Result[i];
		  END;
		END;

	ELSIF String.EqualAlg(Alg, "k") THEN

 	    NOTIME SL.Start(0); END;
		
		KPar ( 1..Degree, Data ); 

	    NOTIME SL.Finish END;

	END;

    NOTIME
	IO.WriteString( "Result = " );
	IO.WriteInt( Result[1], 0 );
	IO.WriteLn;
	(*
	M.PrintI(Size, Size, Data);
	*)
    END;

END  RedSquare .
