-- File CIFDrcList.mesa
-- Written by Dan Fitzpatrick and Martin Newell, September 1980
-- Last updated: January 13, 1981  5:06 PM

DIRECTORY

CIFDrcListDefs: FROM "CIFDrcListDefs",
CIFDrcUtilsDefs: FROM "CIFDrcUtilsDefs" USING [DisplayTrap,Trapezoid,PrintTrapList],
IODefs: FROM "IODefs" USING [WriteLine];

CIFDrcList: PROGRAM
IMPORTS CIFDrcUtilsDefs, IODefs 
EXPORTS CIFDrcListDefs =

BEGIN OPEN CIFDrcListDefs, CIFDrcUtilsDefs, IODefs;

InitList: PUBLIC PROCEDURE =
BEGIN
	TrapList _ ALL[NIL];
	END;

GetFirst: PUBLIC PROCEDURE [layer:CARDINAL,list:POINTER TO ListDescriptor] RETURNS[trap:Trapezoid] =
BEGIN
	list.layer _ layer;
	IF TrapList[layer] # NIL THEN list.trapPtr _ TrapList[layer].front;
	RETURN[TrapList[layer]];
	END;

GetNext: PUBLIC PROCEDURE [list:POINTER TO ListDescriptor] RETURNS[trap:Trapezoid] =
BEGIN
	trap _ list.trapPtr;
	IF list.trapPtr # NIL THEN list.trapPtr _ list.trapPtr.front;
	END;

GetInitialLocal: PUBLIC PROCEDURE [minx,maxx:REAL, layer:CARDINAL, list:POINTER TO ListDescriptor] RETURNS[trap:Trapezoid] =
BEGIN
	list.layer _ layer;
	list.min _ minx;
	list.max _ maxx;
	trap _ BackTo[minx,layer];
	IF trap # NIL THEN list.trapPtr _ trap.front;
	END;

GetLocal: PUBLIC PROCEDURE [list:POINTER TO ListDescriptor] RETURNS[trap:Trapezoid] =
BEGIN
	trap _ list.trapPtr;
	IF list.trapPtr # NIL THEN list.trapPtr _ list.trapPtr.front;
	END;

GetCurrent: PUBLIC PROCEDURE [list:POINTER TO ListDescriptor] RETURNS[trap:Trapezoid] =
BEGIN
	trap _ list.trapPtr;
	END;

EmptyList: PUBLIC PROCEDURE [layer:CARDINAL] =
BEGIN
	IF TrapList[layer] # NIL THEN Break["List is not empty"];
	TrapList[layer] _ NIL;
	END;

BackTo:PROCEDURE [x:REAL, layer:CARDINAL] RETURNS[trap: Trapezoid] =
BEGIN
	-- Get the first element in this layer which has geometry past x

	-- Check to see if list is empty
	IF TrapList[layer] = NIL THEN RETURN[NIL];
	trap _ TrapList[layer];
	-- See whether we must search forward or backward in list
	IF trap.maxx <= x THEN BEGIN			-- search forward
		UNTIL trap = NIL OR x <= trap.maxx DO trap _ trap.front; ENDLOOP;
		RETURN[trap];
		END
	 ELSE BEGIN		 						--search backwards
		UNTIL trap.back = NIL OR trap.back.maxx < x DO trap _ trap.back; ENDLOOP;
		RETURN[trap];
		END; 
	END;

InsertTrap:PUBLIC PROCEDURE [trap:Trapezoid, layer:CARDINAL] =
BEGIN
	ptr,last: Trapezoid;
	DisplayTrap[trap];
	IF trap = NIL THEN BEGIN
				Break["Insert Trap called with NIL value"];
				RETURN;
				END;
	IF TrapList[layer] = NIL THEN BEGIN
		-- List is empty; Put trap in list
		TrapList[layer] _ trap;
		trap.front _ trap.back _ NIL;
		END
	 ELSE BEGIN
		-- List is not empty; insert, maintaining list in ascending order on maxx
		IF trap.maxx < TrapList[layer].maxx THEN BEGIN
			-- Insert trap at beginning of list
			trap.front _ TrapList[layer];
			trap.back _  NIL;
			TrapList[layer].back _ trap;
			TrapList[layer] _ trap;
			END
		 ELSE BEGIN
			last _ TrapList[layer];
			FOR ptr _ TrapList[layer].front,ptr.front
				UNTIL ptr = NIL OR trap.maxx < ptr.maxx DO
				last _ ptr;
				IF ptr.back.front # ptr THEN Break["Inconsistant Trap List"];
				ENDLOOP;
			-- At end of loop we know: ptr.back.maxx <= trap.maxx < ptr.maxx
			-- Insert trap immediately after oldTrap
			trap.back _ last;
			trap.front _ ptr;
			IF ptr # NIL THEN ptr.back _ trap;
			last.front _ trap;
			END;
		END;
		IF TrapList[layer] = NIL THEN Break["Trap List is NIL after insertion"];
	END;

RemoveTrap:PUBLIC PROCEDURE [trap:Trapezoid, layer:CARDINAL] =
BEGIN
	-- RemoveTrap must not only remove the trapezoid from the list but
	-- must also free the edges associated with the trapezoid as well
	-- deleting all dangling references to the trapezoid (i.e. oldTrap
	-- must not remain pointing at trap.)
	IF trap = NIL THEN RETURN;
	IF trap.front # NIL THEN BEGIN
				IF trap.front.back # trap THEN Break["Called Remove Trap with bad trap"];
				trap.front.back _ trap.back;
				END;
	IF trap.back # NIL THEN BEGIN
				IF trap.back.front # trap THEN Break["Called Remove Trap with bad trap"];
				trap.back.front _ trap.front;
				END
						  ELSE	BEGIN
							IF TrapList[layer] # trap THEN Break["Called Remove Trap with wrong layer"];
							TrapList[layer] _ trap.front;
							END;
	trap.front _ trap.back _ NIL;
	END;

PrintList: PUBLIC PROCEDURE[i:CARDINAL] =
--Used for debugging; can be called from JaM
BEGIN
	PrintTrapList[TrapList[i]];
	END;

Break: PROCEDURE[s:STRING] =
BEGIN
	x: REAL _ 0;
	WriteLine[s]; IF 10/x = 9 THEN WriteLine[s];
	END;

TrapList:ARRAY [0..9] OF Trapezoid;
(672)\132b9B168b10B122b8B55b9B220b9B174b17B253b10B174b12B111b11B134b6B585b10B1170bv10BV63v10V749b9B120b5B
END.