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

Problem: Finds the Minimum value in a line.

Example of Execution:
L2:529 1008 224 88 330 465 468 498 597 872 46 462 325 325 969
Min:  2

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, Mn, MaxVal:  INTEGER;
			K: BOOLEAN;
(*----------------------------------------------------------
MAIN
----------------------------------------------------------*)
BEGIN
	(* initialize data  change the value of L1 to any line *)
	RightLimit := 16;
	MaxVal:= 1024; (* maximum possible value for the line *)
	L2 := RandomInt(chain ) MOD MaxVal;
	
	
(* ==================start algorithm======================= *)
	Mn:= MaxVal; (* set min to the maximum value *)
	K:= TRUE;
	
	WHILE K DO
		IF L2 >= Mn THEN
			K:= FALSE;			(* assume that there is nothing greater *)
		ELSE
			Mn:= REDUCE.FIRST(L2);	(* record new min *)
			K:= TRUE;	(*test for new min *)
		END; (*IF *)
	END; (* WHILE*)
	
	
(* ==================printing============================= *)
	IF ID(chain) < RightLimit THEN
		WriteString("L2:" ); WriteInt(L2, 2); WriteLn;
		WriteString("Min: " ); WriteInt(Mn, 2); WriteLn;
	END; (* IF *)
END min.