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

Problem: Sorts on ascending order an ARRAY of integers located
in the controller. Result remains in a line. Does not insert if the 
element is already in the line.

Example of Execution:
	Array:  7 4 6 4 8
	Result:  4  6  7  8 1000000 	( last element is junk )

Cycles: 
2 assign + 2(N) test + (N) 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;
		flag: BOOLEAN;
(*----------------------------------------------------------
		PROCEDURE MAIN
----------------------------------------------------------*)
BEGIN
	flag:= TRUE;
	
	IF L1 = w THEN
		flag := FALSE; 	(* the element is already in line *)
	END; (* IF *)
	IF flag THEN
		IF	L1 > w THEN
			L0id := ID(chain);
			ind := REDUCE.FIRST(L0id); (* index of first selected *)
			L1 := RECEIVE.right(L1);	(* move everything to the right *)
			L1<<ind>>:= w;
		END; (* IF *)
	END; (* IF *)
END insert;
(*----------------------------------------------------------
		MAIN
----------------------------------------------------------*)
BEGIN
	(* initialize data *)
	N:=5;	(* size array *)
	A[0] := 7;
	A[1] := 4;
	A[2] := 6;
	A[3] := 4;
	A[4] := 8; 
	
	(*printing *)
	WriteString("Array: ");
	FOR i:= 0 TO (N - 1) DO
		WriteInt(A[i], 2);
	END; (* FOR *)
	WriteLn;
	
	L1Res:= MAXINT;
	insert(A[0], L1Res);		(*L1Res<<1>>:= A[0]	insert first item *)
	
	FOR i:= 1 TO (N - 1) DO
		insert(A[i] , L1Res);
	END; (* FOR *)
			
	(* Printing *)
	IF ID(chain) < N +1 THEN
		WriteString("Result: "); WriteInt(L1Res, 2); WriteLn;
	END; (* IF *)
END inssort2.