-- 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
ELSEBEGIN
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;

END.