MODULE max;
(*---------------------------------------------------------
File name: max.pm
Author: AG, MM
Date: 10/20/05 

Problem: Finds the Maximum value in a line.

Example of Execution:
L2:94 465 468 743 455 650 269 81 654 623 754 291 722 688 836
Max: 1023

Cycles:
Worst Case
N(REDUCE.FIRST) + N(test) + 2N(assign)

worst case (sorted list): O(N)
average case: O(log(N))
*)
(*----------------------------------------------------------
CONFIGURATION
----------------------------------------------------------*)
CONST  MAXCELLS=1024; (* MAXCELLS cells in one line *)

CONFIGURATION chain[0..(MAXCELLS - 1)];
CONNECTION
			left: chain [i] -> chain[(i-1) MOD MAXCELLS];
			right: chain[i] -> chain[(i+1) MOD MAXCELLS];
(*----------------------------------------------------------
VARIABLES
----------------------------------------------------------*)
VAR 
			L1id, L2: chain OF INTEGER;
			RightLimit, Mx, MaxVal:  INTEGER;
			K: BOOLEAN;
(*----------------------------------------------------------
MAIN
----------------------------------------------------------*)
BEGIN
	(* initialize data  change the value of L1 to any line *)
	RightLimit := 16;
	MaxVal:= 1024; (* maximum possible number on the line *)
	L2 := RandomInt(chain ) MOD MaxVal;
	
	
(* ==================start algorithm======================= *)
	Mx:= 0; (* set max to 0 *)
	K:= TRUE;
	
	WHILE K DO
		IF L2 <= Mx THEN
			K:= FALSE;			(* assume that there is nothing greater *)
		ELSE
			Mx:= REDUCE.FIRST(L2);	(* record new max *)
			K:= TRUE;	(*test for new max *)
		END; (*IF *)
	END; (* WHILE*)
	
	
(* ==================printing============================= *)
	IF ID(chain) < RightLimit THEN
		WriteString("L2:" ); WriteInt(L2, 2); WriteLn;
		WriteString("Max: " ); WriteInt(Mx, 2); WriteLn;
	END; (* IF *)
END max.