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

Ź»˜JšČĻc 
œ
4Ļk3;œ
ž	œžœžœžœžœžœ
žœž
œž
œžœžœ
žœ"žœžœ
žœ?žœžœžœžœžœžœ	žœžœ<œžœ5œ&œžœ'œ
žœ
/œžœžœœœœžœžœžœkĻn
œžœ
ž	œ
žœžœžœ%žœžœžœžœŸ
œžœ
ž	œ'žœ4œ
žœ+œž
œž
œž
œžœž
œž
œž
œžœ>žœŸœžœ
ž	œ'ž	œžœ4œ
žœ
žœžœ2œnžœ
žœ'žœžœŸœž	œžœžœŸœž	œžœžœžœžœ
œ^žœžœžœžœžœ:žœ9œžœžœŸœž	œžœžœžœžœ
žœžœžœžœAžœCœ<žœžœžœŸœž	œ,œžœ	œ0žœœžœ@œžœŸœž	œžœžœžœKœ
,œ
%œžœžœžœŸœž	œžœ>žœŸœž	œžœ8žœ4œžœžœ
žœ
žœ
žœ
å
œžœžœ
žœžœ:žœžœgžœžœ$žœ)žœ
žœžœ
?œžœžœ
žœžœ
žœ«
žœ0žœžœžœžœ
œžœžœ
žœžœ	žœžœ	žœ
žœ-žœžœ
žœžœžœžœ!žœ
žœžœžœžœ$žœ,žœžœ.6œžœ
žœžœ
žœžœCžœ
žœžœžœ
žœžœžœžœ,žœžœžœ8žœžœžœ"žœžœ(žœHžœžœ0žœžœ"žœ"žœžœ
žœ/žœžœžœžœ
žœ9žœžœ
žœ
žœ	žœ<žœ
œ
žœŸœžœ
ž	œœ
žœ
žœžœžœžœ
žœžœžœžœžœžœ
žœžœžœžœœ
Ÿœž	œžœžœžœžœžœžœžœžœ
žœ
žœœ~žœžœžœ	žœŸœž	œžœžœ$Cœ
žœžœ-žœžœ
žœžœ
žœœ
žœžœŸœž	œžœžœ$$œ
žœ
žœ6Ÿœž	œžœCžœžœ
žœ	žœžœžœ
žœ	žœžœžœŸœž	œžœ.žœ	žœ
žœ
œžœ/žœžœžœ
žœ
žœ
žœžœ
3œžœžœ
žœ žœžœžœžœžœžœžœœ
žœœžœ žœ5žœžœžœŸœž	œžœžœžœžœžœžœžœŸœž	œ
žœžœžœžœžœžœŸœž	œ
žœ
žœžœžœžœŸœž	œžœ	žœ
žœ„
œ
 
œ
Ÿ
œž	œ&žœ
žœ žœ:žœ
žœ
žœžœžœžœžœžœžœžœ
žœœžœžœžœžœ
žœžœžœ
žœžœ
žœžœžœ

œžœžœžœ
žœžœžœ
žœ žœ
žœžœžœ
œ_žœžœžœ9œ(žœ2žœžœžœ,œ
žœ)žœŸœž	œžœDœ
žœ
žœžœŸœž	œžœBœ
žœ
žœžœžœ
žœžœžœžœ
žœžœ*žœœžœžœœ
Ÿœž	œžœžœ
žœžœ
'œžœžœžœ
žœœ
Ÿœžœ
ž	œžœ¢œŸ	œžœ
ž	œ&žœ
žœĀœ
žœžœĘ
˜„e—…—2Ø:i