-- File Merge.mesa
-- Written by Maureen Stone, October 1980
-- based on Polygon, Written by Martin Newell, May 1980
-- Last updated: November 5, 1980 3:21 PM

-- Merges rectangular areas for the refresh process
-- Last Edited by: Stone, February 3, 1983 4:09 pm
-- Last Edited by: Pier, February 14, 1984 10:37:27 am PST

DIRECTORY

PrincOpsUtils: FROM "PrincOpsUtils" USING [BITOR],
MergeDefs: FROM "MergeDefs",
PointDefs: FROM "PointDefs" USING[ScrPt, X, Y],
GriffinMemoryDefs USING[UCZone, CZone];

Merge: PROGRAM
IMPORTS PrincOpsUtils, GriffinMemoryDefs
EXPORTS MergeDefs =

BEGIN OPEN PrincOpsUtils, MergeDefs, GriffinMemoryDefs, PointDefs;
Edge: TYPE = LONG POINTER TO EdgeRecord;
EdgeRecord: TYPE = RECORD[
 next: Edge,
 x: INTEGER,
 ystart: INTEGER,
 yend: INTEGER,
 z: INTEGER, --an indication of overlap order. z constant for whole box
 lastouty: INTEGER,  --y value where edge of deferred box was last output
 mate: Edge,   --other edge making up a deferred box
 up: BOOLEAN,   --TRUE if edge defined in increasing y
 flagout: BOOLEAN --TRUE if edge will need to be output at ycurr
];

AreaBlock: PUBLIC TYPE = RECORD[
  edgeList: Edge,   --unprocessed edges
  edgeListEl: Edge,  --last edge added to EdgeList
  activeList: Edge  --edges being processed
  ];

AreaDescriptor: TYPE = REF AreaBlock;

EdgeType: TYPE = {acontinuingUp, acontinuingDown, aterminatingUp, aterminatingDown,
 estartingUp, estartingDown, null};

AreaCreate: PUBLIC PROCEDURE RETURNS[area: AreaDescriptor] =
 BEGIN
 area ← CZone.NEW[AreaBlock];
 area^ ← [
   edgeList: NIL,
   edgeListEl: NIL,
   activeList: NIL
   ];
 END;

AreaNewBox: PUBLIC PROCEDURE[area: AreaDescriptor, tl,br: ScrPt,z: INTEGER] =
-- edge list is built in sort in increasing lower.y
 BEGIN
  --make an edge and bubble it into edgeList
 lEdge: Edge ← MakeEdge[tl[X],tl[Y],br[Y],z,TRUE];
 rEdge: Edge ← MakeEdge[br[X],tl[Y],br[Y],z,FALSE];
 AddToEdgeList[area, lEdge];
 AddToEdgeList[area, rEdge];
 END;

AreaGenerate: PUBLIC PROCEDURE[area: AreaDescriptor,
     outputBox: PROCEDURE[tl,br: ScrPt, z: INTEGER]] =
-- Generate the area defined up to last AreaNewBox
 BEGIN OPEN area;
 ynext,ycurr,yprev: INTEGER;
 edgeListQueue: Edge; --isolates edges being thrown back onto edge list
 edge,prevedge: Edge;
 edgetype: EdgeType;
 newActiveList,pendingFreeEdges,nextedge: Edge;
 ptrnewActiveList: LONG POINTER TO Edge;
 boxleft: Edge;
 adepth,edepth: INTEGER;
 inc: INTEGER;
 StartBox: PROCEDURE[e: Edge] =
  BEGIN
  boxleft ← e;
  END;
 EndBox: PROCEDURE[right: Edge] =
  BEGIN
  left: Edge ← boxleft;
  IF left.mate#right THEN
   BEGIN --pairing changed or NIL
   OutBox[left,yprev];
   OutBox[right,yprev];
   left.mate ← right;
   right.mate ← left;
   END;
  IF left.flagout OR right.flagout THEN
   BEGIN
   OutBox[left,ycurr];
   left.flagout ← right.flagout ← FALSE; --mustn't do this in OutBox because of other calls to it
   END;
  END;
 OutBox: PROCEDURE[e1: Edge, ytop: INTEGER] =
  BEGIN
  e2: Edge ← e1.mate;
  IF e2#NIL THEN
   BEGIN
   rx: INTEGER ← XatY[e2,ytop];
   lx: INTEGER ← XatY[e1,e1.lastouty];
   outputBox[[lx,e1.lastouty],[rx,ytop],MIN[e1.z, e2.z]];
--debug
--   PrintBox[[lx,e1.lastouty],[rx,ytop],MIN[e1.z, e2.z]];
   e1.lastouty ← e2.lastouty ← ytop;
   e1.mate ← e2.mate ← NIL;
   END;
  END;
 UpdateynextNewALAndprevedge: PROCEDURE[edge: Edge] =
 --Update ynext, newActiveList, and prevedge
  BEGIN
 --ynext:
  ynext ← CheckIntersection[prevedge,edge,ycurr,MIN[ynext,edge.yend]];
 --newActiveList:
  edge.next ← NIL;
  ptrnewActiveList^ ← edge;
  ptrnewActiveList ← @edge.next;
 --and prevedge:
  prevedge ← edge;
  END;
 CheckIntersection: PROCEDURE[e1,e2: Edge, ylow,yhigh: INTEGER] RETURNS[y: INTEGER] =
 --check for and deal with intersection of e1 and e2 between ylow and yhigh
 --Returns either yhigh or y of intersection
 --assumes edges are in order at ylow
  BEGIN
  RETURN[yhigh];
  END;
 
 QueueForFreeEdge: PROCEDURE[edge: Edge] =
  BEGIN
  edge.next ← pendingFreeEdges;
  pendingFreeEdges ← edge;
  END;
 QueueForEdgeList: PROCEDURE[edge: Edge] =
  BEGIN
  edge.next ← edgeListQueue;
  edgeListQueue ← edge;
  END;

--AreaGenerate starts here
--WriteLine["new area"];


 UNTIL activeList=NIL AND edgeList=NIL DO
--in one pass through each ActiveList:
-- output box in previous swath
-- remove terminating edges from previous swath,
-- introduce newly entering ones,
-- drawing capping lines as necessary,
-- and find lowest upper y in ynext
  IF activeList=NIL THEN
   BEGIN
   ycurr ← edgeList.ystart;
   ynext ← edgeList.yend;
   END
  ELSE ynext ← activeList.yend;
  adepth ← edepth ← 0;
  [edge,edgetype] ← GetEdge[area,ycurr];
  prevedge ← NIL;
  pendingFreeEdges ← NIL;
  newActiveList ← edgeListQueue ← NIL;
  ptrnewActiveList ← @newActiveList;
  IF ycurr=yprev THEN
   BEGIN --scan only to find ynext (and therefore to do intersections)
   UNTIL edge=NIL DO
    SELECT edgetype FROM
    aterminatingUp,aterminatingDown => QueueForFreeEdge[edge];
    acontinuingUp,acontinuingDown,estartingUp,estartingDown =>
     UpdateynextNewALAndprevedge[edge];
    ENDCASE;
    [edge,edgetype] ← GetEdge[area,ycurr];
   ENDLOOP;
   END
  ELSE
   BEGIN --normal case
   UNTIL edge=NIL DO
    inc ← IF edge.up THEN 1 ELSE -1;
    SELECT edgetype FROM
    aterminatingUp,aterminatingDown =>
     BEGIN
     IF adepth=0 THEN
      BEGIN
      edge.flagout ← TRUE;
      StartBox[edge];
      END;
     adepth ← adepth+inc;
     IF adepth=0 THEN
      BEGIN
      edge.flagout ← TRUE;
      EndBox[edge];
      END;
     QueueForFreeEdge[edge];
     END;
    acontinuingUp,acontinuingDown =>
     BEGIN
     case: CARDINAL ← 0;
     UpdateynextNewALAndprevedge[edge]; --must do this first incase intersection set .flagout
     IF edepth#0 THEN case ← 10B;
     IF adepth#0 THEN case ← BITOR[case,4];
     adepth ← adepth+inc;
     edepth ← edepth+inc;
     IF edepth#0 THEN case ← BITOR[case,2];
     IF adepth#0 THEN case ← BITOR[case,1];
     SELECT case FROM
     3   => StartBox[edge];
     6,16B  => BEGIN edge.flagout ← TRUE; EndBox[edge]; END;
     7,15B  => edge.lastouty ← ycurr;
     11B,13B => BEGIN edge.flagout ← TRUE; StartBox[edge]; END;
     14B  => EndBox[edge];
     ENDCASE;
     END;
    estartingUp,estartingDown =>
     BEGIN
     UpdateynextNewALAndprevedge[edge];
     edepth ← edepth+inc;
     END;
    ENDCASE;
    [edge,edgetype] ← GetEdge[area,ycurr];
   ENDLOOP;
   END;
  activeList ← newActiveList;
  FOR edge ← pendingFreeEdges,nextedge UNTIL edge=NIL DO
   nextedge ← edge.next;
   FreeEdge[edge];
  ENDLOOP;
  FOR edge ← edgeListQueue,nextedge UNTIL edge=NIL DO
   nextedge ← edge.next;
   AddToEdgeList[area,edge];
  ENDLOOP;
  IF edgeList#NIL THEN ynext ← MIN[ynext,edgeList.ystart];
  yprev ← ycurr;
  ycurr ← ynext;
 ENDLOOP; --UNTIL (...
 END;

AreaDestroy: PUBLIC PROCEDURE[area: AreaDescriptor] =
-- Destroy area
 BEGIN OPEN area;
 e,next: Edge;
 FOR e ← edgeList, next UNTIL e=NIL DO
  next ← e.next;
  UCZone.FREE[@e];
 ENDLOOP;
 FOR e ← activeList, next UNTIL e=NIL DO
  next ← e.next;
  UCZone.FREE[@e];
 ENDLOOP;
 END;

-- Private procedures

MakeEdge: PROCEDURE [xstart,ystart,yend: INTEGER, z: INTEGER, up: BOOLEAN]
  RETURNS[edge: Edge] =
 BEGIN
 dy: INTEGER ← yend-ystart;
 IF dy<=0 THEN RETURN[NIL];
--make vertical edge
 edge ← AllocateEdge[];
 edge^ ← [
  next: ,
  x: xstart,
  ystart: ystart,
  yend: yend,
  z: z,
  lastouty: ystart,
  mate: NIL,
  up: up,
  flagout: FALSE
  ];
 RETURN[edge];
 END;

GetEdge: PROCEDURE[area: AreaDescriptor, ycurr: INTEGER]
  RETURNS[edge: Edge, edgeType: EdgeType] =
 --Get next edge for new active list - filter out zero height edges
 BEGIN
 DO
  [edge,edgeType] ← GetEdge1[area,ycurr];
  IF edge=NIL OR edge.yend>edge.ystart THEN EXIT;
  FreeEdge[edge]; --exists and zero height
 ENDLOOP;
 END;

GetEdge1: PROCEDURE[area: AreaDescriptor, ycurr: INTEGER]
  RETURNS[edge: Edge, edgeType: EdgeType] =
 --Get next edge for new active list
 BEGIN OPEN area;
 peekAtEdgeList: Edge ← PeekAtEdgeList[area];
 TakeFromActiveList: PROCEDURE =
  BEGIN
  edge ← activeList;
  activeList ← activeList.next;
  edgeType ← IF edge.yend<=ycurr
      THEN IF edge.up THEN aterminatingUp ELSE aterminatingDown
      ELSE IF edge.up THEN acontinuingUp ELSE acontinuingDown;
  END;
 TakeFromEdgeList: PROCEDURE =
  BEGIN
  edge ← GetFromEdgeList[area];
  edgeType ← IF edge.up THEN estartingUp ELSE estartingDown;
 --tidy it up
  edge.flagout ← FALSE;
  edge.lastouty ← edge.ystart;
  edge.mate ← NIL;
  END;

 SELECT TRUE FROM
 activeList=NIL =>
  BEGIN --take it from EdgeList provided starting at ycurr
  IF peekAtEdgeList#NIL AND peekAtEdgeList.ystart <= ycurr THEN
   TakeFromEdgeList[]
  ELSE
   BEGIN
   edge ← NIL;
   edgeType ← null;
   END;
  END;
 peekAtEdgeList=NIL => TakeFromActiveList[]; -- must be non-NIL if get here
 ENDCASE => --both lists are candidates
  IF peekAtEdgeList.ystart <= ycurr AND
   EdgeLessThan[peekAtEdgeList,activeList, ycurr]
  THEN TakeFromEdgeList[]
  ELSE TakeFromActiveList[];
 END;

XatY: PROCEDURE[edge: Edge, y: INTEGER] RETURNS[x: INTEGER] = INLINE
 BEGIN
 RETURN[edge.x];
 END;

Xend: PROCEDURE[edge: Edge] RETURNS[xend: INTEGER] = INLINE
 BEGIN
 RETURN[edge.x];
 END;


AllocateEdge: PROCEDURE RETURNS[Edge] =
 BEGIN
 RETURN[UCZone.NEW[EdgeRecord]];
 END;

FreeEdge: PROCEDURE[edge: Edge] =
 BEGIN
 UCZone.FREE[@edge];
 END;

-- The next 3 procedures (AddToEdgeList, PeekAtEdgeList, GetFromEdgeList) implement
--  the EdgeList and are subject to replacement

-- In this version the EdgeList is kept doubly linked and search for
--  insertion place is started at last-inserted Edge
--  Back pointers use the .mate field

AddToEdgeList: PROCEDURE[area: AreaDescriptor, edge: Edge] =
 BEGIN OPEN area;
 e,save,start: Edge;
 y: INTEGER ← edge.ystart;
 start ← edgeListEl;
 edgeListEl ← edge;
 IF edgeList=NIL THEN
  BEGIN
  edge.next ← NIL;
  edge.mate ← NIL;
  edgeList ← edge;
  RETURN;
  END;
 IF start=NIL THEN start ← edgeList;
--search forward
 save ← NIL;
 FOR e ← start, e.next UNTIL e=NIL DO
  IF y<e.ystart OR (y=e.ystart AND EdgeLessThan[edge, e, y])
   THEN GOTO searchbackwards;
  save ← e;
 REPEAT
  searchbackwards =>
   BEGIN --edge "<" e
   FOR e ← e.mate, e.mate UNTIL e=NIL DO
    IF e.ystart<y OR (e.ystart=y AND EdgeLessThan[e, edge, y])
     THEN GOTO append;
   REPEAT
    append =>
     BEGIN --append edge to e
     edge.next ← e.next;
     edge.mate ← e;
     e.next.mate ← edge;
     e.next ← edge;
     RETURN;
     END;
   ENDLOOP;
  --reached begin of list - insert edge before 1st element
   edge.next ← edgeList;
   edge.mate ← NIL;
   edgeList.mate ← edge;
   edgeList ← edge;
   RETURN;
   END;
 ENDLOOP;
--reached end of list - append edge to save
 edge.next ← NIL;
 edge.mate ← save;
 save.next ← edge;
 END;

PeekAtEdgeList: PROCEDURE[area: AreaDescriptor] RETURNS[edge: Edge] =
--Returns next edge from EdgeList without removing it from EdgeList
 BEGIN OPEN area;
 edge ← edgeList;
 END;

GetFromEdgeList: PROCEDURE[area: AreaDescriptor] RETURNS[edge: Edge] =
--Returns next edge from EdgeList having removed it from EdgeList
 BEGIN OPEN area;
 edge ← edgeList;
 IF edge#NIL THEN
  BEGIN
  edgeList ← edge.next;
  IF edge.next#NIL THEN edge.next.mate ← NIL;
  edgeListEl ← edge.next;
  edge.mate ← NIL; --clean up
  END;
 END;

--

EdgeLessThan: PROCEDURE[e1,e2: Edge, y: INTEGER] RETURNS[BOOLEAN] =
 BEGIN
--orders up/down within slope within x
 x1: INTEGER ← XatY[e1,y];
 x2: INTEGER ← XatY[e2,y];
 RETURN[x1<x2];
 END;

--for debugging:

PrintBox: PUBLIC PROCEDURE[tl,br: ScrPt, z: INTEGER] = {
-- WriteString["xl:"]; WriteDecimal[tl[X]]; WriteChar[SP];
-- WriteString["ty:"]; WriteDecimal[tl[Y]]; WriteChar[SP];
-- WriteString["rx:"]; WriteDecimal[br[X]]; WriteChar[SP];
-- WriteString["by:"]; WriteDecimal[br[Y]]; WriteChar[SP];
-- WriteString["z:"]; WriteDecimal[z]; WriteChar[CR];
 };

PrintList: PUBLIC PROCEDURE[area: AreaDescriptor, list: Edge] =
 BEGIN OPEN area;
-- e: Edge;
-- SELECT list FROM
-- activeList => WriteLine["ActiveList"];
-- edgeList => WriteLine["EdgeList"];
-- ENDCASE;
-- WriteOctal[list]; WriteChar[CR];
-- FOR e ← list, e.next UNTIL e=NIL DO
--  WriteString["next:"]; WriteOctal[e.next]; WriteChar[SP];
--  WriteString["x:"]; WriteDecimal[e.x]; WriteChar[SP];
--  WriteString["ystart:"]; WriteDecimal[e.ystart]; WriteChar[SP];
--  WriteString["xend:"]; WriteDecimal[Xend[e]]; WriteChar[SP];
--  WriteString["yend:"]; WriteDecimal[e.yend]; WriteChar[SP];
--  WriteString["up:"]; WriteChar[IF e.up THEN 'T ELSE 'F]; WriteChar[SP];
--  WriteString["flagout:"]; WriteChar[IF e.flagout THEN 'T ELSE 'F]; WriteChar[SP];
--  WriteString["lastouty:"]; WriteDecimal[e.lastouty]; WriteChar[SP];
--  WriteString["mate:"]; WriteOctal[e.mate]; WriteChar[CR];
--  WriteChar[CR];
-- ENDLOOP;
 END;


END.
(635)\214b9B292b5B257b10B182b10B341b12B451b8B54b6B404b6B372b27B302b17B262b16B101b16B2755b11B294b8B360b7B325b8B196b18B243b16B727b4B96b4B88b12B87b8B357b13B310b13B1109b14B167b15B328b12B197b8B334b9B