(* ------------------------------------------------------ *)
(* shearsort.pm                                           *)
(* Shearsort algorithm.                                   *)
(* Implements the shearsort algorithm by applying odd-even*)
(* sort to the rows and columns of the two dimensional    *)
(* array                                                  *)
(* Typical output shown at end of code                    *)
(* ------------------------------------------------------ *)
MODULE shearsort;  (* Odd-Even Transposition Sorting *)

CONST N     = 16;
CONST SQRTN = 4;
CONST LOGN  = 4;

CONFIGURATION mesh[1..SQRTN],[1..SQRTN];
CONNECTION left: mesh[i,j] <-> mesh[i,j-1] :right;
           down: mesh[i,j] <-> mesh[i+1,j] : up;

VAR step    : INTEGER;
    a       : ARRAY[1..SQRTN],[1..SQRTN] OF INTEGER;
    val,comp: mesh OF INTEGER;
    lhs     : mesh OF BOOLEAN;
    oddRow  : mesh OF BOOLEAN;

(* --------------------------------------------------- *)
(* SORCOL: sorts column using odd-even sort            *)
(* --------------------------------------------------- *)
PROCEDURE sortCol;
VAR
  step: INTEGER;
BEGIN
  oddRow := ODD(DIM(mesh,2));  (* PE is 1st in up-down pair *)
  FOR step:=1 TO SQRTN DO
    IF (oddRow) THEN comp := RECEIVE.up (val)
           ELSE comp := RECEIVE.down(val)
    END;
    IF (oddRow = (comp<val)) THEN val:=comp END; 
    oddRow := NOT oddRow;  
  END;  
END sortCol;

(* --------------------------------------------------- *)
(* SORTROW: sorts the odd rows in increasing order, and*)
(*          the even rows in decreasing order.  Uses   *)
(*          odd-even sort to do the job.               *)
(* --------------------------------------------------- *)
PROCEDURE sortRow;
VAR
  step: INTEGER;
  map : mesh OF ARRAY BOOLEAN OF CHAR;
BEGIN
  map[TRUE]:='T'; map[FALSE]:='F';

  oddRow := ODD(DIM(mesh,2));  
  lhs    := ODD(DIM(mesh,1));  (* PE is 1st in left-right pair *)
  FOR step:=1 TO SQRTN DO
    IF (lhs) THEN comp := RECEIVE.left (val)
             ELSE comp := RECEIVE.right(val)
    END;
    IF (oddRow) THEN
       IF (lhs = (comp<val)) THEN val:=comp END; 
    ELSE 
       IF (lhs = (comp>val)) THEN val:=comp END; 
    END;
    lhs := NOT lhs;  
  END;  
END sortRow;

(* --------------------------------------------------- *)
(*                M A I N   P R O G R A M              *)
(* --------------------------------------------------- *)
BEGIN
  (*--- get original array ---*)
  ReadInt(val);
  WriteInt(val,5);
  
  (*--- sort it ---*)
  FOR step:=1 TO LOGN DIV 2 DO 
     sortRow; WriteString("sorted rows"); WriteLn; WriteInt(val,5);
     sortCol; WriteString("sorted columns"); WriteLn; WriteInt(val,5);
  END;
  sortRow;

  (*--- display result ---*)
  WriteString("sorted rows and done!"); WriteLn; WriteInt(val,5);

END shearsort.

(* typical output
shearsort < shear.data
    5    10    12    14 
    1     3     4    15 
    6    11    13    16 
    2     7     9     8 

sorted rows
    5    10    12    14 
   15     4     3     1 
    6    11    13    16 
    9     8     7     2 

sorted columns
    5     4     3     1 
    6     8     7     2 
    9    10    12    14 
   15    11    13    16 

sorted rows
    1     3     4     5 
    8     7     6     2 
    9    10    12    14 
   16    15    13    11 

sorted columns
    1     3     4     2 
    8     7     6     5 
    9    10    12    11 
   16    15    13    14 

sorted row and done!
    1     2     3     4 
    8     7     6     5 
    9    10    11    12 
   16    15    14    13 

*)