
<<SweepImpl.mesa>>
    <<Copyright © 1985 by Xerox Corporation.  All rights reserved.>>
    <<Greene, October 3, 1986 5:19:24 pm PDT>>

DIRECTORY
Sweep;

SweepImpl: CEDAR PROGRAM IMPORTS Sweep EXPORTS Sweep =

BEGIN OPEN Sweep;


NilStart: PUBLIC PROC [lineLeft, lineRight: Line, regionPrevious: REF ANY] RETURNS [regionCenter: REF ANY] ~ {
RETURN[NIL]
};


    NilStop: PUBLIC PROC [lineLeft: Line, regionCenter: REF ANY, lineRight: Line] ~ {
RETURN;
};


    NilSplit: PUBLIC PROC [lineLeft, lineRight: Line, regionRight: REF ANY, regionPrevious: REF ANY _ NIL] RETURNS [regionLeft: REF 
    ANY] ~ {
RETURN[regionRight];
};


    NilMerge: PUBLIC PROC [regionLeft: REF ANY, lineLeft, lineRight: Line, regionRight: REF ANY] RETURNS [regionCenter: REF ANY] ~ {
RETURN[regionRight];
};


    NilLineChange: PUBLIC PROC [lineOld, lineNew: Line, side: LeftOrRight, regionCenter: REF ANY, regionPrevious: REF ANY _ NIL] ~ {
    RETURN;
    };


    ExpandedLineCarrier: TYPE = REF ExpandedLineCarrierRec;
ExpandedLineCarrierRec: TYPE = RECORD[
carried: Line,
regionLeft: REF ANY _ NIL,
lineLeft, lineRight: ExpandedLineCarrier _ NIL
];


    Sweep: PUBLIC PROC [in: Graph, infinityRegion: REF ANY _ NIL, Start: StartRegionProc _ NilStart, Stop: StopRegionProc _ NilStop, 
    Split: SplitRegionProc _ NilSplit, Merge: MergeRegionProc _ NilMerge, LineChange: LineChangeRegionProc _ NilLineChange] RETURNS 
    [out: Graph] ~ {

    xOrder, orderScan, temporaryELC, rightNeighbor, leftNeighbor: ExpandedLineCarrier;
    holdRegionLeft, temporaryRegion: REF ANY _ NIL;
    holdLineLeft, lineScan, prevLineScan: Line;
    currentPoint: Point;

    freeELC: ExpandedLineCarrier _ NIL;

    CleanELC: PROC [dead: ExpandedLineCarrier] ~ {
    OPEN dead;
        lineRight _ freeELC;
        freeELC _ dead;
        };

    NewELC: PROC [carried: Line, regionLeft: REF ANY _ NIL, lineLeft, lineRight: ExpandedLineCarrier _ NIL] RETURNS [alive: 
    ExpandedLineCarrier] ~ {
        IF freeELC = NIL THEN RETURN[NEW[ExpandedLineCarrierRec_ [carried: carried, regionLeft: regionLeft, lineLeft: lineLeft, lineRight: 
        lineRight]]] ELSE {
            alive _ freeELC;  freeELC _ alive.lineRight;
            alive.carried _ carried; alive.regionLeft _ regionLeft; alive.lineLeft _ lineLeft; alive.lineRight _ lineRight;
            }
        };

    TrashFreeELC: PROC [] ~ {
        UNTIL freeELC = NIL DO
            freeELC.lineLeft _ NIL; freeELC _ freeELC.lineRight;
            ENDLOOP;
        };

    IF in = NIL THEN RETURN[NIL];
    IF in.status # planar THEN ERROR;

    FOR i: CARDINAL IN [0..in.points.size) DO
        currentPoint _ in.points.data[i];
        lineScan _ currentPoint.incoming;
        IF lineScan = NIL THEN {
            leftNeighbor _ xOrder;
            rightNeighbor _ NIL;
            UNTIL leftNeighbor = NIL DO
                IF ComparePointLine[currentPoint, leftNeighbor.carried] = greater THEN EXIT;
                rightNeighbor _ leftNeighbor;
                leftNeighbor _ leftNeighbor.lineLeft;
                ENDLOOP;
            holdLineLeft _ NIL;
            holdRegionLeft _ IF rightNeighbor # NIL THEN rightNeighbor.regionLeft ELSE infinityRegion;
            }
        ELSE {
            orderScan  _ xOrder;
            UNTIL lineScan = orderScan.carried DO    --bounds fault indicates algorithmic failure
                orderScan _ orderScan.lineLeft;
                ENDLOOP;
            leftNeighbor _ orderScan.lineLeft;
            holdRegionLeft _ orderScan.regionLeft;
            holdLineLeft _ lineScan;
            DO
                prevLineScan _ lineScan;
                lineScan _ lineScan.clockwiseAroundBelow;
                rightNeighbor _ orderScan.lineRight;
                IF lineScan = NIL THEN EXIT;
                Stop[prevLineScan, rightNeighbor.regionLeft, lineScan];
                CleanELC[orderScan];
                orderScan _ rightNeighbor;
                IF lineScan # orderScan.carried THEN ERROR; 
                ENDLOOP;
            };
        lineScan _ currentPoint.outgoing;
        IF lineScan = NIL THEN {
            IF holdLineLeft # NIL THEN {
                temporaryRegion _ Merge[holdRegionLeft, holdLineLeft, prevLineScan, IF rightNeighbor = NIL THEN infinityRegion ELSE 
                rightNeighbor.regionLeft];
                CleanELC[orderScan];
                IF rightNeighbor # NIL THEN {
                    rightNeighbor.regionLeft _ temporaryRegion;
                    rightNeighbor.lineLeft _ leftNeighbor }
                ELSE {xOrder _ leftNeighbor; infinityRegion _ temporaryRegion};
                IF leftNeighbor # NIL THEN leftNeighbor.lineRight _ rightNeighbor;
                };
            }
        ELSE {
            IF holdLineLeft # NIL THEN {
                LineChange[prevLineScan, lineScan, left, IF rightNeighbor = NIL THEN infinityRegion ELSE rightNeighbor.regionLeft];
                CleanELC[orderScan];
                };
            DO
                prevLineScan _ lineScan;
                lineScan _ lineScan.clockwiseAroundAbove;
                IF lineScan = NIL THEN EXIT;
                temporaryELC _ NewELC[
                    carried: prevLineScan,
                    regionLeft: Start[lineScan, prevLineScan, IF rightNeighbor = NIL THEN infinityRegion ELSE rightNeighbor.regionLeft],
                    lineRight: rightNeighbor ];
                IF rightNeighbor # NIL THEN rightNeighbor.lineLeft _ temporaryELC ELSE xOrder _ temporaryELC;
                rightNeighbor _ temporaryELC;
                ENDLOOP;
            temporaryELC _ NewELC[
                carried: prevLineScan,
                regionLeft: holdRegionLeft,
                lineRight: rightNeighbor, lineLeft: leftNeighbor];
            IF leftNeighbor # NIL THEN leftNeighbor.lineRight _ temporaryELC;
            IF rightNeighbor # NIL THEN rightNeighbor.lineLeft _ temporaryELC ELSE xOrder _ temporaryELC;
            IF holdLineLeft # NIL THEN {
                LineChange[holdLineLeft, prevLineScan, right, holdRegionLeft, IF rightNeighbor = NIL THEN infinityRegion ELSE 
                rightNeighbor.regionLeft];
                }
            ELSE
                temporaryELC.regionLeft _ Split[prevLineScan, currentPoint.outgoing, holdRegionLeft, IF rightNeighbor = NIL THEN infinityRegion 
                ELSE rightNeighbor.regionLeft];
            };
        ENDLOOP;

    out _ NEW[GraphRec _ [status: planar, points: in.points]];
    out _ RemoveOrphanPoints[out];
    in.status _ invalid;

    TrashFreeELC[];
    };

END.