
<<-- File: IPCBImpl.mesa>>
<<-- Last Edited by: CSChow, February 2, 1985 2:29:38 am PST>>

<<--Note: IPCB = ChannelBoundary>>
<<>>

DIRECTORY
    IPCB;

IPCBImpl: CEDAR PROGRAM
IMPORTS IPCB
EXPORTS IPCB = BEGIN OPEN IPCB;

SideEmpty: PUBLIC ERROR= CODE;
NotFound: PUBLIC ERROR= CODE;

Create: PUBLIC PROC[owner: Channel] RETURNS[r: Ref] ={
    RETURN [NEW[Rep _ [owner]]]}; --Create --

    Destroy: PUBLIC PROC[r: Ref] ={
        p: PROC [iNd: IntersectionNode] ={iNd.dual _ NIL}; --p--
        AllIntersectionNodes[r, p]  --Maybe should do this differently--
        }; --Destroy--

    CheckSelf: PUBLIC PROC[r: Ref] ={
        BEGIN
            pI: PROC [iNd: IPCB.IntersectionNode] ={
                IF iNd = NIL OR iNd.dual = NIL THEN ERROR;
                IF iNd.owner # r.owner THEN ERROR;
                IF iNd.dual.dual # iNd THEN ERROR;
                IF iNd.dual.intersection.ch # r.owner THEN ERROR}; --pI--
            AllIntersectionNodes[r, pI];
            END;
        BEGIN
            prevComp: Component _ NIL;
            pI: EachINodeAction ={ 
                IF prevComp = NIL THEN prevComp _ iNd.posComp ELSE {
                    IF prevComp = iNd.negComp THEN prevComp _ iNd.posComp  ELSE ERROR};
                SELECT iNd.intersection.type FROM
                    Cross => IF iNd.dual.intersection.type # Cross THEN ERROR;
                    TPos, TNeg => IF iNd.dual.intersection.type # TEnd THEN ERROR;
                    ENDCASE => ERROR;
                }; --pI--
            IntersectionNodes[r, pI, neg];
            prevComp _ NIL;
            IntersectionNodes[r, pI, pos];
            END;
        BEGIN
            IF r.negEnd.negComp # NIL OR r.negEnd.posComp # NIL THEN ERROR;
            IF r.posEnd.negComp # NIL OR r.posEnd.posComp # NIL THEN ERROR;
            IF r.negComp # NIL AND NOT NoIntersection[r, neg] THEN ERROR;
            IF r.posComp # NIL AND NOT NoIntersection[r, pos] THEN ERROR;
            SELECT r.negEnd.intersection.type FROM
                TEnd => IF r.negEnd.dual.intersection.type # TPos THEN ERROR;
                LNeg, LPos => IF r.negEnd.dual.intersection.type # LPos THEN ERROR;
                ENDCASE => ERROR;
            SELECT r.posEnd.intersection.type FROM
                TEnd => IF r.posEnd.dual.intersection.type # TNeg THEN ERROR;
                LNeg, LPos => IF r.posEnd.dual.intersection.type # LNeg THEN ERROR;
                ENDCASE => ERROR;
            END;
        BEGIN
            IF (r.negSideTl # NIL AND r.negSideTl.rest # NIL) OR  
                (r.posSideTl # NIL AND r.posSideTl.rest # NIL) THEN ERROR;
            IF r.negSideHd = NIL OR r.negSideHd.rest = NIL THEN{
                IF r.negSideHd # r.negSideTl THEN ERROR};
            IF r.posSideHd = NIL OR r.posSideHd.rest = NIL THEN{
                IF r.posSideHd # r.posSideTl THEN ERROR};
            END;
        }; --CheckSelf--

    End: PUBLIC PROC[r: Ref, which: Side] RETURNS[Intersection] ={
        RETURN[ SELECT which FROM
            neg => r.negEnd.intersection,
            pos => r.posEnd.intersection,
            ENDCASE => ERROR]}; -- End-- 

    NthIntersection: PUBLIC PROC[r: Ref, which: Side, n: INT] RETURNS[Intersection] ={
        iNd: IntersectionNode _ NthINode[r, which, n];
        IF iNd = NIL THEN RETURN[NIL] ELSE RETURN [iNd.intersection]}; --NthIntersection -- 

    NthComponent: PUBLIC PROC [r: Ref, which: Side, n: INT] RETURNS[Component] ={
        iNd: IntersectionNode; 
        IF NoIntersection[r, which] THEN {
            SELECT n FROM
                -1, 1 => RETURN [SideGetComp[r, which]];
                ENDCASE => RETURN [NIL]};
        iNd _ NthINode[r, which, n];
        IF iNd = NIL THEN RETURN [NIL] ELSE RETURN [(IF n < 0 THEN iNd.posComp ELSE iNd.negComp)]
        }; --NthComponent--

    NoIntersection: PUBLIC PROC[r: Ref, which: Side] RETURNS[BOOL] ={
        RETURN[ SELECT which FROM
            neg => r.negSideHd = NIL,
            pos => r.posSideHd = NIL,
            ENDCASE => ERROR]}; -- NoIntersection--

    NoComponent: PUBLIC PROC[r: Ref, which: Side] RETURNS[BOOL] ={
        RETURN[ SELECT which FROM
            neg => r.negSideHd = NIL AND r.negComp = NIL,
            pos => r.posSideHd = NIL AND r.posComp = NIL,
            ENDCASE => ERROR]}; -- NoComponent--

    ComponentOn: PUBLIC PROC[r: Ref, comp: Component, which: Side] RETURNS[BOOL]={
        p: EachComponentAction ={IF co = comp  THEN { quit _ TRUE}};
        RETURN [NOT Components[r, which, p]]
        };--ComponentOn--

    GetChNbr: PUBLIC PROC[r: Ref, ch: Channel, whichNbr, hint: Side] RETURNS [Channel] ={
        IF End[r, neg].ch = ch THEN {
            IF whichNbr = neg THEN ERROR NotFound;
            RETURN [IF NoIntersection[r, hint] THEN End[r, pos].ch ELSE SideGet[r, hint].Hd.first.intersection.ch]};
        IF End[r, pos].ch = ch THEN {
            IF whichNbr = pos THEN ERROR NotFound;
            RETURN [IF NoIntersection[r, hint] THEN End[r, neg].ch ELSE SideGet[r, hint].Tl.first.intersection.ch]};
        BEGIN
            lPt, lHd, lTl: LIST OF IntersectionNode _ NIL;
            [lHd, lTl] _ SideGet[r, hint];
            IF whichNbr = neg THEN {
                IF lHd.first.intersection.ch = ch THEN RETURN [End[r, neg].ch];
                FOR l: LIST OF IntersectionNode _ lHd, l.rest UNTIL l = NIL  DO
                    IF l.rest.first.intersection.ch = ch THEN {lPt _ l; EXIT}
                    ENDLOOP;
                IF lPt = NIL THEN ERROR NotFound; --ch may not intersects r--
                RETURN [lPt.first.intersection.ch]} ELSE {
                IF lTl.first.intersection.ch = ch THEN RETURN [End[r,pos].ch];
                FOR l: LIST OF IntersectionNode _ lHd, l.rest UNTIL l = NIL  DO
                    IF l.first.intersection.ch = ch THEN {lPt _ l; EXIT}
                    ENDLOOP;
                IF lPt = NIL THEN ERROR NotFound;
                RETURN [lPt.rest.first.intersection.ch]};
            END;
        }; --GetChNbr--

    SetBoundary: PUBLIC PROC[r: Ref, negEnd, posEnd: Intersection, negSide, posSide: LIST OF Intersection] ={
        SetUpDuals[SetEnd[r, ItoINode[negEnd, r.owner], neg], pos]; 
        SetUpDuals[SetEnd[r, ItoINode[posEnd, r.owner], pos], neg]; 
        FOR l: LIST OF Intersection _ negSide, l.rest UNTIL l = NIL DO 
            IF l.first.type IN NIntersectionType 
                THEN SetUpDuals[SideAddh[r, ItoINode[l.first, r.owner], neg], neg]
                ELSE ERROR
            ENDLOOP;
        FOR l: LIST OF Intersection _ posSide, l.rest UNTIL l = NIL DO 
            IF l.first.type IN PIntersectionType 
                THEN SetUpDuals[SideAddh[r, ItoINode[l.first, r.owner], pos], pos]
                ELSE ERROR
            ENDLOOP;
        }; --SetBoundary --


    InsertCoBetween: PUBLIC PROC[r: Ref, co: Component, negBnd, posBnd: Channel, which: Side] ={
        IF NoIntersection[r, which] 
            THEN SideSetComp[r, co, which]
            ELSE {
                IF End[r, neg].ch # negBnd THEN GetINode[r, negBnd, which].posComp _ co;
                IF End[r, pos].ch # posBnd THEN GetINode[r, posBnd, which].negComp _ co}
        }; --InsertCoBetween --
     
    InsertCoAt: PUBLIC PROC[r: Ref, co: Component, whichSide, whichEnd: Side] ={
        IF NoIntersection[r, whichSide] THEN SideSetComp[r, co, whichSide]
            ELSE {
                SELECT whichEnd FROM
                    neg => {NthINode[r, whichSide, 1].negComp _ co};
                    pos => {NthINode[r, whichSide, -1].posComp _ co};
                    ENDCASE => ERROR}
        }; --InsertCoAt--

    Components: PUBLIC PROC[r: Ref, which: Side, p: EachComponentAction] RETURNS[BOOL] ={
        IF NoIntersection[r, which] THEN RETURN [NOT p[SideGetComp[r, which]]]
            ELSE {
                lHd, lTl: LIST OF IntersectionNode;
                [lHd, lTl] _ SideGet[r, which];
                FOR l: LIST OF IntersectionNode _ lHd, l.rest UNTIL l = NIL DO {
                    IF p[l.first.negComp] THEN RETURN[FALSE]}
                    ENDLOOP;
                RETURN[NOT p[lTl.first.posComp]]}
        }; -- Components--

    AllInteriorIntersections: PUBLIC PROC [r: Ref] RETURNS[LIST OF IntersectionNode] ={
        RETURN[NIL];
        };

    ChannelSegments: PUBLIC PROC[r: Ref, p: EachChSegAction] RETURNS[BOOL] ={
        negIntNd: IntersectionNode _ r.negEnd;
        posIntNd: IntersectionNode;
        <<>>
        <<next do the interior intersections>>
        FOR iList: LIST OF IntersectionNode _ IPCB.AllInteriorIntersections[r], iList.rest WHILE iList # NIL DO
            posIntNd _ iList.first;
            IF p[r, negIntNd, posIntNd] THEN RETURN[FALSE];
            negIntNd _ posIntNd;
            ENDLOOP;
        <<>>
        <<finally, the right of the channel>>
        posIntNd _ r.posEnd;
        IF p[r, negIntNd, posIntNd] THEN RETURN[FALSE];
        RETURN[TRUE]
        };

    Intersections: PUBLIC PROC[r: Ref, which: Side, p: EachIntersectionAction] RETURNS[BOOL] ={
        FOR l: LIST OF IntersectionNode _ SideGet[r, which].Hd, l.rest UNTIL l = NIL DO {
            IF p[l.first.intersection] THEN RETURN[FALSE]}
            ENDLOOP;
        RETURN[TRUE]
        }; --Intersections --

    <<--######Used mainly by EditOpsImpl######-->>
    GetINode:  PUBLIC PROC[r: Ref, ch: Channel, hint: Side] RETURNS [IntersectionNode]=  {
        IF r.negEnd # NIL AND r.negEnd.intersection.ch = ch THEN RETURN [r.negEnd];
        IF r.posEnd # NIL AND r.posEnd.intersection.ch = ch THEN RETURN [r.posEnd];
        FOR l: LIST OF IntersectionNode _ SideGet[r, hint].Hd, l.rest UNTIL l = NIL DO
            IF l.first.intersection.ch = ch THEN RETURN[l.first]
            ENDLOOP;
        RETURN [NIL]
        }; --GetINode--

    IntersectsCh: PUBLIC PROC[r: Ref, ch: Channel] RETURNS [BOOL] ={
        RETURN [NOT (GetINode[r, ch, neg] = NIL AND GetINode[r, ch, pos] = NIL)]
        }; --IntersectsCh--

    ArmOn: PUBLIC PROC[r: Ref, ch: Channel, which: Side] RETURNS [BOOL] ={RETURN [XingCount[r, ch, which] >= 0]}; --ArmOn--

    SideAddl: PUBLIC PROC [r: Ref, iNd: IntersectionNode, which: Side] RETURNS [IntersectionNode]= {
    UpdateDual[r, iNd];
        SELECT which FROM
            neg => {r.negComp _ NIL; IF r.negSideHd = NIL THEN r.negSideHd _ r.negSideTl _ LIST[iNd] ELSE r.negSideHd _CONS[iNd, r.negSideHd]};
            pos => {r.posComp _ NIL; IF r.posSideHd = NIL THEN r.posSideHd _ r.posSideTl_ LIST[iNd] ELSE r.posSideHd _ CONS[iNd, r.posSideHd]};
            ENDCASE => ERROR;
        RETURN [iNd]}; --SideAddl--

    SideAddh: PUBLIC PROC [r: Ref, iNd: IntersectionNode, which: Side] RETURNS [IntersectionNode] = {
    UpdateDual[r, iNd];
        SELECT which FROM
            neg => {r.negComp _ NIL; IF r.negSideHd = NIL THEN r.negSideHd _ r.negSideTl _ LIST[iNd] ELSE {r.negSideTl.rest _ LIST[iNd]; 
            r.negSideTl _ r.negSideTl.rest}};
            pos => {r.posComp _ NIL; IF r.posSideHd = NIL THEN r.posSideHd _ r.posSideTl_ LIST[iNd] ELSE {r.posSideTl.rest _ LIST[iNd]; 
            r.posSideTl _ r.posSideTl.rest}};
            ENDCASE => ERROR;
        RETURN [iNd]}; --SideAddh--

    SideInsert: PUBLIC PROC[r: Ref, iNd: IntersectionNode, negBnd, posBnd: Channel, which: Side] RETURNS [IntersectionNode] = {
        lNd: LIST OF IntersectionNode;
    UpdateDual[r, iNd];
    SideSetComp[r, NIL, which];
        IF End[r, neg].ch = negBnd THEN  {nd: IntersectionNode_ NthINode[r, which, 1];
            IF nd = NIL THEN {nd _ r.posEnd} ELSE {nd.negComp _ iNd.posComp};
            IF  nd.intersection.ch # posBnd THEN ERROR;
            [] _ SideAddl[r, iNd, which];
            RETURN [iNd]};
        IF End[r, pos].ch = posBnd THEN {nd: IntersectionNode _ NthINode[r, which, -1];
            IF nd = NIL OR nd.intersection.ch # negBnd THEN ERROR;
            nd.posComp _ iNd.negComp;
            [] _ SideAddh[r, iNd, which];
            RETURN [iNd]};
        FOR l: LIST OF IntersectionNode _ SideGet[r, which].Hd, l.rest DO
            IF l.first.intersection.ch = negBnd THEN {lNd _ l; EXIT}
            ENDLOOP;
        IF lNd.rest.first.intersection.ch # posBnd THEN ERROR;
        lNd.first.posComp _ iNd.negComp;
        lNd.rest.first.negComp _ iNd.posComp;
        lNd.rest _ CONS[iNd, lNd.rest];
        RETURN [iNd]
        }; --SideInsert--
    SetEnd: PUBLIC PROC [r: Ref, iNd: IntersectionNode, whichEnd: Side] RETURNS [IntersectionNode]={
        UpdateDual[r, iNd];
        iNd.negComp _ iNd.posComp _ NIL;
        SELECT whichEnd FROM
            neg => {r.negEnd _ iNd};
            pos => {r.posEnd _ iNd};
            ENDCASE => ERROR;
        RETURN [iNd]
        }; --SetEnd--

    SideRemovel: PUBLIC PROC [r: Ref, which: Side] RETURNS [iNd: IntersectionNode] = {
        IF NoIntersection[r, which] THEN ERROR SideEmpty;
        SELECT which FROM
            neg => {iNd _ r.negSideHd.first; 
                IF (r.negSideHd _ r.negSideHd.rest) = NIL THEN {r.negSideTl _ NIL; r.negComp _ iNd.posComp}};
            pos => {iNd _ r.posSideHd.first; 
                IF (r.posSideHd _ r.posSideHd.rest) = NIL THEN {r.posSideTl _ NIL; r.posComp _ iNd.posComp}};
            ENDCASE => ERROR;}; --SideRemovel--

    SideRemoveh: PUBLIC PROC [r: Ref, which: Side] RETURNS [iNd: IntersectionNode] =  {
        lHd, lTl: LIST OF IntersectionNode;
        [lHd, lTl] _ SideGet[r, which];
        IF lHd = NIL THEN ERROR SideEmpty;
        iNd _ lTl.first;
        IF lHd = lTl THEN {
            SELECT which FROM
                neg => {r.negSideHd _ r.negSideTl _ NIL; r.negComp _ iNd.negComp};
                pos => {r.posSideHd _ r.posSideTl _ NIL; r.posComp _ iNd.negComp};
                ENDCASE => ERROR;} ELSE{ 
            lPt: LIST OF IntersectionNode;
            FOR l: LIST OF IntersectionNode _ lHd, l.rest DO
                IF l.rest = lTl THEN {lPt _ l; EXIT;}
                ENDLOOP;
            SELECT which FROM
                neg => r.negSideTl _ lPt;
                pos => r.posSideTl _ lPt;
                ENDCASE => ERROR;
            lPt.rest _ NIL;}
        }; --SideRemoveh--

    SideRem: PUBLIC PROC[r: Ref, ch: Channel, which: Side, repCo: Component] RETURNS [iNd: IntersectionNode]= {
        lHd, lTl: LIST OF IntersectionNode;
        [lHd, lTl] _ SideGet[r, which];
        IF lHd = NIL THEN ERROR SideEmpty;
        IF lHd.first.intersection.ch = ch THEN {
            iNd _ SideRemovel[r,which];
            SELECT which FROM
                neg => IF r.negSideHd = NIL THEN r.negComp _ repCo ELSE r.negSideHd.first.negComp _ repCo;
                pos =>IF r.posSideHd = NIL THEN r.posComp _ repCo ELSE r.posSideHd.first.negComp _ repCo;
                ENDCASE => ERROR;} ELSE {
            lPt: LIST OF IntersectionNode _ NIL;
            FOR l: LIST OF IntersectionNode _ lHd, l.rest UNTIL l.rest = NIL DO
                IF l.rest.first.intersection.ch = ch THEN {lPt _ l; EXIT;}
                ENDLOOP;
            IF lPt = NIL THEN ERROR NotFound;
            iNd _ lPt.rest.first;
            lPt.first.posComp _ repCo;
            lPt.rest _ lPt.rest.rest;
            IF lPt.rest =  NIL THEN SideSet[r, lHd, lPt, which] ELSE lPt.rest.first.negComp _ repCo;};
        RETURN [iNd]
        }; --SideRem --

    SideRem2: PUBLIC PROC[r: Ref, iNd: IntersectionNode, repCo: Component] RETURNS [IntersectionNode] ={
        iNdCh: Channel _ iNd.intersection.ch;
        IF r.negEnd = iNd THEN ERROR NotFound;
        IF r.posEnd = iNd THEN ERROR NotFound;
        IF GetINode[r, iNdCh, neg] = iNd THEN RETURN [SideRem[r, iNdCh, neg, repCo]];
        IF GetINode[r, iNdCh, pos] = iNd THEN RETURN [SideRem[r, iNdCh, pos, repCo]];
        ERROR NotFound;
        }; --SideRem2 --

    Fragment: PUBLIC PROC [r: Ref, co1, co2: Component, negCh, posCh: Channel] ={
        negF: Ref _ Create[negCh];
        posF: Ref _ Create[posCh];
        negCo, posCo: Component;
        SELECT TRUE FROM
            ComponentOn[r, co1, neg] AND ComponentOn[r, co2, pos]=> {negCo _ co1; posCo _ co2};
            ComponentOn[r, co2, neg] AND ComponentOn[r, co1, pos]=> {negCo _ co2; posCo _ co1};
            ENDCASE => ERROR;
        [] _ SetEnd[negF, r.negEnd, neg];
        [] _ SetEnd[posF, r.posEnd, pos];
        negF.negComp _ posF.negComp _ negCo; 
        negF.posComp _ posF.posComp _ posCo; 
        IF r.negComp = negCo AND negCo # NIL THEN NULL ELSE {
            addN: BOOL _ TRUE;
            p: EachINodeAction ={
                IF iNd.negComp = negCo THEN addN _ FALSE;
                IF addN THEN [] _ SideAddh[negF, iNd, neg] ELSE [] _ SideAddh[posF, iNd, neg]}; --p--
            IntersectionNodes[r, p, neg]};
        IF r.posComp = posCo AND posCo # NIL THEN NULL ELSE {
            addN: BOOL _ TRUE;
            p: EachINodeAction ={
                IF iNd.negComp = posCo THEN addN _ FALSE;
                IF addN THEN [] _ SideAddh[negF, iNd, pos] ELSE [] _ SideAddh[posF, iNd, pos]}; --p--
            IntersectionNodes[r, p, pos]};
    negCh.boundary _ negF;
    posCh.boundary _ posF;
        }; --Fragment--

    Merge: PUBLIC PROC [negR, posR: Ref, owner: Channel]={
        mergedR: Ref _ Create[owner];
        pNSide: EachINodeAction ={[] _ SideAddh[mergedR, iNd, neg]}; --pNSide--
        pPSide: EachINodeAction ={[] _ SideAddh[mergedR, iNd, pos]}; --pPSide--
        IF NthComponent[negR, neg, -1] # NthComponent[posR, neg, 1]  OR NthComponent[negR, pos, -1] # NthComponent[posR, pos, 1] THEN ERROR;
        mergedR.negComp _ NthComponent[negR, neg, 1];
        mergedR.posComp _ NthComponent[posR, pos, 1];
        [] _ SetEnd[mergedR, negR.negEnd, neg];
        [] _ SetEnd[mergedR, posR.posEnd, pos];
        IntersectionNodes[negR, pNSide, neg]; IntersectionNodes[posR, pNSide, neg];
        IntersectionNodes[negR, pPSide, pos]; IntersectionNodes[posR, pPSide, pos];
        owner.boundary _ mergedR;
        };--Merge--

    XingCount: PUBLIC PROC [r: Ref, ch: Channel, which: Side] RETURNS [INT]={
        found: BOOL _ FALSE;
        notFoundCount: INT = -1;
        xingCount: INT _ 0;
        p1: PROC[iNd: IntersectionNode] ={
            IF iNd.intersection.ch = ch THEN { 
                SELECT which FROM
                    neg => IF iNd.intersection.type # IPCB.LPos THEN found _ TRUE;
                    pos => IF iNd.intersection.type # IPCB.LNeg THEN found _ TRUE;
                    ENDCASE => ERROR;}}; --p1--
        p2: EachINodeAction ={
            IF iNd.intersection.ch = ch THEN {found _ TRUE; RETURN [TRUE]};
            IF iNd.intersection.type = Cross THEN xingCount _ xingCount.SUCC;}; --p2--
        p1[r.negEnd];
        IF NOT found THEN IntersectionNodes[r, p2, which];
        IF NOT found THEN p1[r.posEnd];
        IF found THEN RETURN [xingCount] ELSE RETURN [notFoundCount]
        };--XingCount--

    InCount: PUBLIC PROC[r: Ref, ch: Channel, which: Side] RETURNS [INT] = {
        found: BOOL _ FALSE;
        notFoundCount: INT = -1;
        inCount: INT _ 0;
        p1: PROC[iNd: IntersectionNode] ={
            SELECT which FROM
                neg => IF iNd.intersection.type # IPCB.LPos THEN {
                    inCount _ inCount.SUCC;
                    IF iNd.intersection.ch = ch THEN found _ TRUE};
                pos => IF iNd.intersection.type # IPCB.LNeg THEN {
                    inCount _ inCount.SUCC;
                    IF iNd.intersection.ch = ch THEN found _ TRUE};
                ENDCASE => ERROR;}; --p1--
        p2: EachINodeAction ={
            inCount _ inCount.SUCC;
            IF iNd.intersection.ch = ch THEN {found _ quit _ TRUE}}; --p2--
        p1[r.negEnd];
        IF NOT found THEN IntersectionNodes[r, p2, which];
        IF NOT found THEN p1[r.posEnd];
        IF found THEN RETURN [inCount] ELSE RETURN [notFoundCount]
        }; --InCount--


    NthINode: PUBLIC PROC [r: Ref, which: Side, n: INT] RETURNS[IntersectionNode]= {
        lHd, lTl: LIST OF IntersectionNode;
        [lHd, lTl] _ SideGet[r, which];
        IF lHd = NIL THEN RETURN [NIL];
        SELECT n FROM
            -1 => RETURN [lTl.first];
            1 => RETURN [lHd.first]
            ENDCASE => RETURN [Nth[lHd, n]];
        }; --NthINode--

    IntersectionNodes: PUBLIC PROC[r: Ref, p: EachINodeAction, which: Side] = {
        FOR l: LIST OF IntersectionNode _ SideGet[r, which].Hd, l.rest UNTIL l = NIL DO
            IF p[l.first] THEN EXIT
            ENDLOOP;}; --IntersectionNodes--

    AllIntersectionNodes: PUBLIC PROC [r: Ref, p: PROC [iNd: IntersectionNode]] = {
        p[r.negEnd]; 
        FOR l: LIST OF IntersectionNode _ r.negSideHd, l.rest UNTIL l = NIL DO
            p[l.first]
            ENDLOOP;
        FOR l: LIST OF IntersectionNode _ r.posSideHd, l.rest UNTIL l = NIL DO
            p[l.first]
            ENDLOOP;
        p[r.posEnd];
        }; --AllIntersectionNodes--

    SetUpDuals: PUBLIC PROC [iNd: IntersectionNode, hint: Side] =  {
        dINode: IntersectionNode _ GetINode[iNd.intersection.ch.boundary, iNd.owner, hint];
        IF dINode = NIL 
            THEN NULL 
            ELSE {iNd.dual _ dINode; dINode.dual _ iNd};
        }; --SetUpDuals--

    UpdateDual: PROC[r: Ref, iNd: IntersectionNode] = --INLINE-- {
        IF r.owner = iNd.owner THEN NULL ELSE {
            iNd.owner _ r.owner;
            iNd.dual.intersection.ch _ r.owner}}; --UpdateDual--

    SideGet: PUBLIC PROC [r: Ref, which: Side] RETURNS [Hd, Tl: LIST OF IntersectionNode]=  {
        SELECT which FROM
            neg => {Hd _ r.negSideHd; Tl _ r.negSideTl};
            pos => {Hd _ r.posSideHd; Tl _ r.posSideTl};
            ENDCASE => ERROR;
        }; --SideGet--

    SideSet: PROC [r: Ref, lHd, lTl: LIST OF IntersectionNode, which: Side]=  {
        SELECT which FROM
            neg => {r.negSideHd _ lHd; r.negSideTl _ lTl};
            pos => {r.posSideHd _ lHd; r.posSideTl _ lTl};
            ENDCASE => ERROR;
        }; --SideGet--

    SideSetComp: PUBLIC PROC [r: Ref, comp: Component, which: Side] = {
        SELECT which FROM
            neg => r.negComp _ comp;
            pos => r.posComp _ comp;
            ENDCASE => ERROR}; --SideSetComp--

    SideGetComp:PUBLIC PROC [r: Ref, which: Side] RETURNS [Component]= {
        SELECT which FROM
            neg => RETURN [r.negComp];
            pos => RETURN [r.posComp];
            ENDCASE => ERROR}; --SideGetComp--

    ItoINode: PUBLIC PROC [i: Intersection, o: Channel] RETURNS [IntersectionNode] = {
        RETURN [NEW[IntersectionNodeRep _ [owner: o, intersection: i]]]};--ItoINode--

    SideOpenHole1: PUBLIC PROC[mainR, sideR: Ref, negBnd, posBnd: Channel, sideToOp: Side]={
        IF End[mainR, neg].ch = negBnd THEN {
            l: LIST OF IntersectionNode _ SideGet[mainR, sideToOp].Hd;
            WHILE l # NIL AND l.first.intersection.ch # posBnd DO
                [] _ SideAddh[sideR, SideRemovel[mainR, sideToOp], sideToOp];
                l _ SideGet[mainR, sideToOp].Hd;
                ENDLOOP;
            IF NoIntersection[sideR, sideToOp] THEN SideSetComp[sideR, NthComponent[mainR, sideToOp, 1], sideToOp]} ELSE {
            lHd, lTl: LIST OF IntersectionNode _ NIL;
            FOR l: LIST OF IntersectionNode _ SideGet[mainR, sideToOp].Hd, l.rest UNTIL l = NIL DO
                IF l.first.intersection.ch = negBnd THEN lHd _ l;
                IF l.first.intersection.ch = posBnd THEN {lTl _ l; EXIT};
                ENDLOOP;
            IF lTl = NIL THEN SideSet[mainR, SideGet[mainR, sideToOp].Hd, lHd, sideToOp];
            FOR l: LIST OF IntersectionNode _ lHd.rest, l.rest UNTIL l = lTl DO
                [] _ SideAddh[sideR, l.first, sideToOp];
                ENDLOOP;
            lHd.rest _ lTl;
            IF NoIntersection[sideR, sideToOp] THEN SideSetComp[sideR, lHd.first.posComp, sideToOp]}
        }; --SideOpenHole1--

    SideOpenHole2: PUBLIC PROC[mainR, sideR: Ref, negBnd, posBnd: Channel, sideToOp: Side]={
        lNd, lTl: LIST OF IntersectionNode;
        [] _ SetEnd[sideR, mainR.posEnd, pos];
        lNd _ SideGet[mainR, sideToOp].Hd;
        IF End[mainR, neg].ch = negBnd 
            THEN SideSet[mainR, NIL, NIL, sideToOp] 
            ELSE{
                FOR l: LIST OF IntersectionNode _ lNd, l.rest DO
                    IF l.first.intersection.ch = negBnd THEN {lTl _ l; EXIT}
                    ENDLOOP;
                SideSet[mainR, lNd, lTl, sideToOp];
                lNd _ lTl.rest; lTl.rest _ NIL;}; --EndIf--
        WHILE lNd # NIL DO 
            [] _ SideAddh[sideR, lNd.first, sideToOp]; lNd _ lNd.rest; 
            ENDLOOP;
        IF NoIntersection[sideR, sideToOp] THEN SideSetComp[sideR, NthComponent[mainR, sideToOp, -1], sideToOp];

        sideToOp _ IF sideToOp = neg THEN pos ELSE neg;
        lNd _ SideGet[mainR, sideToOp].Hd;
        IF End[mainR, pos].ch = posBnd THEN RETURN; --This includes lNd = NIL--
        IF lNd.first.intersection.ch = posBnd 
            THEN {
                SideSet[mainR, NIL, NIL, sideToOp];
                SideSetComp[mainR, lNd.first.negComp, sideToOp];} 
            ELSE {
                FOR l: LIST OF IntersectionNode _ lNd, l.rest DO
                    IF l.rest.first.intersection.ch = posBnd THEN {lTl _ l; EXIT}
                    ENDLOOP;
                SideSet[mainR, lNd, lTl, sideToOp];
                lNd _ lTl.rest; lTl.rest _ NIL;}; --EndIf--
        WHILE lNd # NIL DO 
            [] _ SideAddh[sideR, lNd.first, sideToOp]; lNd _ lNd.rest; 
            ENDLOOP;}; --SideOpenHole2--

    SideCloseHole1: PUBLIC PROC [mainR, sideR: Ref, negBnd, posBnd: Channel, sideToCl: Side] ={
        lNd, lTl: LIST OF IntersectionNode _ NIL;
        IF End[mainR, pos].ch = posBnd THEN NULL ELSE {lNd _ SideGet[mainR, sideToCl].Hd;
            IF lNd.first.intersection.ch = posBnd 
                THEN SideSet[mainR, NIL, NIL, sideToCl]
                ELSE {
                    FOR l: LIST OF IntersectionNode _ lNd, l.rest DO
                        IF l.rest.first.intersection.ch = posBnd THEN {lTl _ l; EXIT}
                        ENDLOOP;
                    SideSet[mainR, lNd, lTl, sideToCl];
                    lNd _ lTl.rest; lTl.rest _ NIL;}; --endIF--
            }; --endIF--
        FOR l: LIST OF IntersectionNode _ SideGet[sideR, sideToCl].Hd, l.rest UNTIL l = NIL DO
            [] _ SideAddh[mainR, l.first, sideToCl]; 
            ENDLOOP;
        FOR l: LIST OF IntersectionNode _ lNd, l.rest UNTIL l = NIL  DO
            [] _ SideAddh[mainR, l.first, sideToCl]; 
            ENDLOOP;
        IF NoIntersection[mainR, sideToCl] 
            THEN SideSetComp[mainR, SideGetComp[sideR, sideToCl], sideToCl];
        }; --SideCloseHole1--
    SideCloseHole2: PUBLIC PROC [mainR, sideR: Ref, negBnd, posBnd: Channel, sideToCl: Side] ={
        FOR l: LIST OF IntersectionNode _ SideGet[sideR, sideToCl].Hd, l.rest UNTIL l = NIL DO
            [] _ SideAddh[mainR, l.first, sideToCl];
            ENDLOOP;
        IF NoIntersection[mainR, sideToCl] 
            THEN SideSetComp[mainR, SideGetComp[sideR, sideToCl], sideToCl];
        sideToCl _ IF sideToCl = neg THEN pos ELSE neg; --Flip it--
        FOR l: LIST OF IntersectionNode _ SideGet[sideR, sideToCl].Hd, l.rest UNTIL l = NIL DO
            [] _ SideAddh[mainR, l.first, sideToCl];
            ENDLOOP;
        [] _ SetEnd[mainR, sideR.posEnd, pos];
        }; --SideCloseHole2--

    Nth: PROC[list: LIST OF IntersectionNode, n: INT] RETURNS[IntersectionNode] ={
        tail: LIST OF IntersectionNode;
        IF list = NIL OR n = 0 THEN RETURN[NIL];
        IF n > 0 THEN
            {tail _ NthTail[list, n-1]} ELSE {tail _ NthTail[list, n]};
        IF tail = NIL THEN RETURN[NIL];
        RETURN[tail.first]}; --Nth --

NthTail:  PROC [list: LIST OF IntersectionNode, n: INT] RETURNS[LIST OF IntersectionNode] = {
IF n=0 THEN RETURN[list];
IF list = NIL THEN RETURN[NIL];
IF n > 0 THEN THROUGH [0..n) DO 
list _ list.rest;
IF list = NIL THEN RETURN[NIL];
REPEAT
FINISHED => RETURN[list];
ENDLOOP
 ELSE
{lead: LIST OF IntersectionNode _ NthTail[list, -n];
UNTIL lead = NIL DO
lead _ lead.rest;
list _ list.rest;
ENDLOOP;
RETURN[list];
};
}; -- of NthTail

    END.