MODULE inssort;
(*---------------------------------------------------------
File name: inssort.pm
Author: MM, AG
Date: 6/09/05 

Problem: Sorts on ascending order an ARRAY of integers located
in the controller. Result remains in a line.

Example of Execution:
	Array:  4 2 6 3 8
	Result:  2  3  4  6  8

Cycles: 
2 assign + (N- 1) test + (N -1) insert.
*)
(*----------------------------------------------------------
		CONFIGURATION
----------------------------------------------------------*)
CONST  MAXCELLS=1024; (* MAXCELLS cells in one line *)
CONST  MAXINT = 1000000; (* maximum value for integer is 2^31 *)

CONFIGURATION chain[0..(MAXCELLS - 1)];
CONNECTION
		left: chain [i] -> chain[(i-1) MOD MAXCELLS];
		right: chain[i] -> chain[(i+1) MOD MAXCELLS];
(*----------------------------------------------------------
		VARIABLES
----------------------------------------------------------*)
VAR 
		L1Res: chain OF INTEGER;
		i, N:INTEGER;
		A: ARRAY[0..(N-1)] OF INTEGER; (* pattern of ints *)
(*-----------------------------------------------------------
	PROCEDURES
----------------------------------------------------------*)
PROCEDURE insert(w : INTEGER; VAR L1 : chain OF INTEGER);
	(* insert: inserts w before the first element of L1.
		w is the value to insert
		L1 is the chain in which it is going to be inserted
			L1 is passed by reference
	
	Cycles = 1 (on Connex) (refer to insert.pm)
	*)
(*----------------------------------------------------------
		PROCEDURE VARIABLES
----------------------------------------------------------*)
VAR 
		L0id: chain OF INTEGER;
		ind: INTEGER;
(*----------------------------------------------------------
		PROCEDURE MAIN
----------------------------------------------------------*)
BEGIN
	L0id := ID(chain);
	ind := REDUCE.FIRST(L0id); (* index of first selected *)
	L1 := RECEIVE.right(L1);
	L1<<ind>>:= w;
	
END insert;
(*----------------------------------------------------------
		MAIN
----------------------------------------------------------*)
BEGIN
	(* initialize data *)
	N:=5;	(* size array *)
	A[0] := 4;
	A[1] := 2;
	A[2] := 6;
	A[3] := 3;
	A[4] := 8; 
	
	(*printing *)
	WriteString("Array: ");
	FOR i:= 0 TO (N - 1) DO
		WriteInt(A[i], 2);
	END; (* FOR *)
	WriteLn;
	
	L1Res:= MAXINT;
	L1Res<<1>>:= A[0];	(* insert first item *)
	
	FOR i:= 1 TO (N - 1) DO
		IF L1Res > A[i] THEN
			insert(A[i] , L1Res);
		END; (* IF *)
	END; (* FOR *)
			
	(* Printing *)
	IF ID(chain) < N +1 THEN
		WriteString("Result: "); WriteInt(L1Res, 2); WriteLn;
	END; (* IF *)
END inssort.