SweepStructureImpl.mesa
Copyright © 1985 by Xerox Corporation. All rights reserved.
Greene, March 27, 1986 3:22:00 pm PST
DIRECTORY
Sweep;
SweepStructureImpl: CEDAR PROGRAM IMPORTS Sweep EXPORTS Sweep =
BEGIN OPEN Sweep;
InsertLineInPointAbove:
PUBLIC
PROC [l: Line] ~ {
p: Point ← l.above;
prev, next: Line;
prev ← NIL; next ← p.outgoing;
UNTIL next =
NIL
DO
IF CompareSlopes[l, next] = greater THEN EXIT;
prev ← next; next ← prev.clockwiseAroundAbove;
ENDLOOP;
IF prev = NIL THEN p.outgoing ← l ELSE prev.clockwiseAroundAbove ← l;
l.clockwiseAroundAbove ← next
};
InsertLineInPointBelow:
PUBLIC
PROC [l: Line] ~ {
p: Point ← l.below;
prev, next: Line;
prev ← NIL; next ← p.incoming;
UNTIL next =
NIL
DO
IF CompareSlopes[l, next] = greater THEN EXIT;
prev ← next; next ← prev.clockwiseAroundBelow;
ENDLOOP;
IF prev = NIL THEN p.incoming ← l ELSE prev.clockwiseAroundBelow ← l;
l.clockwiseAroundBelow ← next
};
RemoveLineFromPointAbove:
PUBLIC
PROC [l: Line] ~ {
p: Point ← l.above;
prev, next: Line;
prev ← NIL; next ← p.outgoing;
UNTIL next = l
DO
prev ← next; next ← prev.clockwiseAroundAbove;
ENDLOOP;
IF prev = NIL THEN p.outgoing ← next.clockwiseAroundAbove ELSE prev.clockwiseAroundAbove ← next.clockwiseAroundAbove;
l.clockwiseAroundAbove ← NIL;
};
RemoveLineFromPointBelow:
PUBLIC
PROC [l: Line] ~ {
p: Point ← l.below;
prev, next: Line;
prev ← NIL; next ← p.incoming;
UNTIL next = l
DO
prev ← next; next ← prev.clockwiseAroundBelow;
ENDLOOP;
IF prev = NIL THEN p.incoming ← next.clockwiseAroundBelow ELSE prev.clockwiseAroundBelow ← next.clockwiseAroundBelow;
l.clockwiseAroundBelow ← NIL;
};
MergePoints:
PUBLIC PROC [p1, p2: Point] ~ {
MergeIncoming[p2.incoming, p1];
MergeOutgoing[p2.outgoing, p1];
};
MergeOutgoing:
PROC [l: Line, p: Point] ~ {
nextLine: Line;
UNTIL l =
NIL
DO
nextLine ← l.clockwiseAroundAbove;
l.above ← p;
InsertLineInPointAbove[l];
l ← nextLine;
ENDLOOP;
};
MergeIncoming:
PROC [l: Line, p: Point] ~ {
nextLine: Line;
UNTIL l =
NIL
DO
nextLine ← l.clockwiseAroundBelow;
l.below ← p;
InsertLineInPointBelow[l];
l ← nextLine;
ENDLOOP;
};
NewGraph:
PUBLIC
PROC []
RETURNS [out: Graph] ~ {
out ← NEW[GraphRec ← [status: raw, points: NEW[PointSeq[32]]]];
};
NewPoint:
PUBLIC
PROC [in: Graph, x, y:
INT, state:
REF
ANY ←
NIL]
RETURNS [out: Graph] ~ {
OPEN in.points;
out ← in; in.status ← raw;
ExpandIfNecessary[in];
data[size] ← NEW[PointRec ← [x: x, y: y]];
size ← size + 1;
};
LineTo:
PUBLIC
PROC [in: Graph, x, y:
INT, state:
REF
ANY ←
NIL,
Flip: FlipLineProc ← NilFlip]
RETURNS [out: Graph] ~ {
OPEN in.points;
l: Line; a, b: Point; r: Relation;
out ← in; in.status ← raw;
IF size = 0 THEN ERROR;
ExpandIfNecessary[in];
a ← data[size-1]; b ← data[size] ← NEW[PointRec ← [x: x, y: y]]; size ← size + 1;
BoundsCheck[a]; BoundsCheck[b];
r ← ComparePoints[a, b];
IF r = equal THEN {size ← size - 1; RETURN}; --Skip lines of zero length
IF r = less
THEN
{state ← Flip[state];
b ← a; a ← data[size - 1]};
l ← NEW[LineRec ← [above: a, below: b, state: state]];
InsertLineInEndPoints[l];
};
LastLine:
PUBLIC PROC [in: Graph]
RETURNS [l: Line] ~ {
OPEN in.points;
p: Point;
IF size = 0 THEN ERROR;
p ← data[size - 1];
IF p.incoming = NIL THEN RETURN[p.outgoing] ELSE RETURN[p.incoming];
};
ExpandIfNecessary:
PROC [in: Graph] ~
INLINE {
OPEN in.points;
IF size = max
THEN {
newPoints: REF PointSeq ← NEW[PointSeq[max*2]];
FOR i: CARDINAL IN [0..size) DO newPoints.data[i] ← data[i] ENDLOOP;
newPoints.size ← size;
in.points ← newPoints;
};
};
CopyGraph: PUBLIC PROC [in: Graph, Copy: CopyLineProc ← NilCopy] RETURNS [out: Graph] ~ {
OPEN in.points;
scan, next, prev: Line;
np, p: Point;
out ← NEW[GraphRec];
out.status ← in.status;
out.points ← NEW[PointSeq[max]];
out.points.size ← size;
FOR i:
CARDINAL
IN [0..size)
DO
p ← data[i];
out.points.data[i] ← np ← NEW[PointRec ← [x: p.x, y: p.y]];
scan ← p.outgoing;
prev ← NIL;
WHILE scan #
NIL
DO
IF ISTYPE[scan.state, Line] AND scan.state # NIL THEN { --Line already copied
next ← NARROW[scan.state, Line];
next.above ← np;
scan.state ← next.state; next.state ← Copy[scan.state];
}
ELSE {
next ← NEW[LineRec ← [above: np, below: NIL, state: scan.state]];
scan.state ← next;
};
IF prev = NIL THEN np.outgoing ← next ELSE prev.clockwiseAroundAbove ← next;
prev ← next;
scan ← scan.clockwiseAroundAbove;
ENDLOOP;
scan ← p.incoming;
prev ← NIL;
WHILE scan #
NIL
DO
IF ISTYPE[scan.state, Line] AND scan.state # NIL THEN { --Line already copied
next ← NARROW[scan.state, Line];
next.below ← np;
scan.state ← next.state; next.state ← Copy[scan.state];
}
ELSE {
next ← NEW[LineRec ← [above: NIL, below: np, state: scan.state]];
scan.state ← next;
};
IF prev = NIL THEN np.incoming ← next ELSE prev.clockwiseAroundBelow ← next;
prev ← next;
scan ← scan.clockwiseAroundBelow;
ENDLOOP;
ENDLOOP;
};
DestroyGraph:
PUBLIC
PROC [in: Graph] ~ {
l: Line; p: Point;
IF in = NIL THEN RETURN;
FOR i:
CARDINAL
IN [0..in.points.size)
DO
p ← in.points.data[i]; l ← p.outgoing;
UNTIL l =
NIL
DO
l.above ← l.below ← NIL;
l.clockwiseAroundBelow ← NIL;
l ← l.clockwiseAroundAbove;
ENDLOOP;
p.incoming ← p.outgoing ← NIL;
ENDLOOP;
};
MergeGraphs:
PUBLIC
PROC [in1, in2: Graph]
RETURNS [out: Graph] ~ {
required, displacement: CARDINAL;
IF in1 = NIL THEN RETURN[in2];
IF in2 = NIL THEN RETURN[in1];
required ← in1.points.size + in2.points.size;
IF required > in1.points.max
THEN {
IF required > in2.points.max
THEN {
out ← NEW[GraphRec];
out.points ← NEW[PointSeq[PowerOf2[required]]]; out.points.size ← in1.points.size;
FOR i:
CARDINAL
IN [0..in1.points.size)
DO
out.points.data[i] ← in1.points.data[i];
ENDLOOP;
}
ELSE {out ← in2; in2 ← in1}
}
ELSE {out ← in1};
displacement ← out.points.size;
FOR i:
CARDINAL
IN [displacement..required)
DO
out.points.data[i] ← in2.points.data[i-displacement];
ENDLOOP;
out.points.size ← required;
out.status ← raw;
};
PowerOf2:
PROC [in:
CARDINAL]
RETURNS [out:
CARDINAL ← 32] ~ {
UNTIL out >= in
DO
out ← out * 2;
ENDLOOP;
};
EnumerateLines: PUBLIC PROC [in: Graph, LineAction: LineActionProc] RETURNS [quit: BOOL ← FALSE] ~ {
l: Line; p: Point;
IF in = NIL THEN RETURN;
FOR i:
CARDINAL
IN [0..in.points.size)
DO
p ← in.points.data[i]; l ← p.outgoing;
UNTIL l =
NIL
DO
IF LineAction[l] THEN RETURN[TRUE];
l ← l.clockwiseAroundAbove;
ENDLOOP;
ENDLOOP;
};
Verify:
PUBLIC
PROC [in: Graph] ~ {
OuterAction:
PROC [l: Line]
RETURNS [quit:
BOOL ←
FALSE] ~ {
global: Line ← l;
InnerAction:
PROC [l: Line]
RETURNS [quit:
BOOL ←
FALSE] ~ {
p: Point; s: LineRelation; s1, s2: EndPointRelation;
IF l = global THEN RETURN[TRUE];
[p, s, s1, s2] ← PairIntersection[l, global];
SELECT s
FROM
intersect =>
{
SELECT s1
FROM
above => IF p # l.above THEN ERROR;
below => IF p # l.below THEN ERROR;
interior, exterior => ERROR;
ENDCASE;
SELECT s2
FROM
above => IF p # global.above THEN ERROR;
below => IF p # global.below THEN ERROR;
interior, exterior => ERROR;
ENDCASE;
};
colinear => ERROR;
ENDCASE
};
IF NOT EnumerateLines[in, InnerAction] THEN ERROR
};
[] ← EnumerateLines[in, OuterAction];
};
END.