DIRECTORY
  COGDebug USING [out, Error],
  IO USING [PutF, int],
  COGDiagram;
COGDiagramImpl: CEDAR MONITOR
  IMPORTS COGDiagram, COGDebug, IO
  EXPORTS COGDiagram =
BEGIN
  OPEN COGDiagram, Bug: COGDebug, IO;
LNext: PUBLIC PROC [e: DEdge] RETURNS [ne: DEdge] =
{RETURN [Dual[ONext[Prim[e]]]]};
RNext: PUBLIC PROC [e: DEdge] RETURNS [ne: DEdge] =
{RETURN [Prim[ONext[Dual[e]]]]};
DNext: PUBLIC PROC [e: DEdge] RETURNS [ne: DEdge] =
{RETURN [Sym[ONext[Sym[e]]]]};

OPrev: PUBLIC PROC [e: DEdge] RETURNS [ne: DEdge] =
{RETURN [Dual[ONext[Dual[e]]]]};
LPrev: PUBLIC PROC [e: DEdge] RETURNS [ne: DEdge] =
{RETURN [Sym[ONext[e]]]};
RPrev: PUBLIC PROC [e: DEdge] RETURNS [ne: DEdge] =
{RETURN [ONext[Sym[e]]]};
DPrev: PUBLIC PROC [e: DEdge] RETURNS [ne: DEdge] =
{RETURN [Prim[ONext[Prim[e]]]]};
SetOrg: PUBLIC PROC [e: DEdge, v: Vertex] =
BEGIN
  et: DEdge _ e;
  DO
    FixOrg[et, v];
    et _ ONext[et];
    IF et = e THEN RETURN
   ENDLOOP
END;

EdgeCount: PUBLIC EdgeNo _ 0;		-- DEdge count (undirected) - protected by the monitor lock.
GetNextEdgeNo: ENTRY PROC RETURNS [no: EdgeNo] = INLINE
BEGIN
  no _ EdgeCount;
  EdgeCount _ EdgeCount+1
END;
MakeSphere: PUBLIC PROC [v: Vertex, f: Face] RETURNS [dg: DEdge] =
BEGIN
  dg.rec _ NEW [EdgeRec];
  dg.ix _ 0;
  dg.rec^ _
    [org: [v, f, v, f],
     next: [dg, Dual[dg], Sym[dg], Prim[dg]],
     no: GetNextEdgeNo[]];
  Bug.out.PutF ["\nDiag.MakeSphere -- edge "]; PutE[dg] 
END;
MakeBridge: PUBLIC PROC [org, dest: Vertex, f: Face] RETURNS [dg: DEdge] =
BEGIN
  dg.rec _ NEW [EdgeRec];
  dg.ix _ 0;
  dg.rec^ _
    [org: [org, f, dest, f],
     next: [dg, Prim[dg], Sym[dg], Dual[dg]],
     no: GetNextEdgeNo[]];
  Bug.out.PutF ["\nDiag.MakeBridge -- edge "]; PutE[dg]
END;
SetONext: PROC [x, xn: DEdge] = INLINE
BEGIN
  x.rec.next[x.ix] _ xn
END;
MergeOrSplitVertices: PUBLIC PROC [x, y: DEdge] =
BEGIN
  -- LOOK! NOTHING IN THE SLEEVES...
  xn: DEdge = ONext[x];
  xnd: DEdge = Dual[ONext[x]];
  ynd: DEdge = Dual[ONext[y]];
  SetONext [x, ONext[y]];
  SetONext [y, xn];
  SetONext [xnd, Prim[y]];
  SetONext [ynd, Prim[x]]
  -- PRESTO!
END;
ConnectVertices: PUBLIC PROC [a, b: DEdge] RETURNS [e: DEdge] =
BEGIN
  e _ MakeBridge [Org[a], Org[b], Left[b]];
  Bug.out.PutF["\nDiag.ConnectVertices - edge "]; PutE[e];
  Bug.out.PutF["from Org[ "]; PutE[a];
  Bug.out.PutF["] to Org[ "]; PutE[b]; Bug.out.PutF["]"];

  IF IsDummy[a] THEN
    {IF b = a THEN b _ e}
  ELSE
    {MergeOrSplitVertices[a, e]};
  IF IsDummy[b] THEN
    {}
  ELSE
    {MergeOrSplitVertices [b, Sym[e]]};
END;
DeleteEdge: PUBLIC PROC [e: DEdge] RETURNS [a, b: DEdge] =
BEGIN
  -- Check for forbidden loop!
  a _ Dual[ONext[Dual[e]]];
  b _ Dual[ONext[Dual[Sym[e]]]];
  IF b = Sym[e] THEN
    {b _ MakeSphere [Dest[e], Left[e]]}
  ELSE
    {MergeOrSplitVertices [b, Sym[e]];
     IF a = Sym[e] THEN a _ b};
  IF a = e THEN
    {a _ MakeSphere [Org[e], Left[e]];
     IF b = e THEN b _ a}
  ELSE
    {MergeOrSplitVertices [a, e]}
END;
AddVertex: PUBLIC PROC [v: Vertex, ep: DEdge, side: EdgeSide] RETURNS [e: DEdge] =
BEGIN
  a: DEdge = IF side = left THEN LNext[ep] ELSE Sym[ep];
  e _ MakeBridge [Dest[ep], v, IF side = left THEN Left[ep] ELSE Right[ep]];
  Bug.out.PutF["\nDiag.AddVertex - edge "]; PutE[e];
  Bug.out.PutF["from Dest[ "]; PutE[ep]; Bug.out.PutF["] to new vertex"];

  IF IsDummy[a] THEN
    {}
  ELSE
    {MergeOrSplitVertices[a, e]};
END;
CloseFace: PUBLIC PROC [ep, ef: DEdge, newFace: Face, side: EdgeSide] RETURNS [e: DEdge] =
BEGIN
  IF (IF side = left THEN Left[ep] # Left[ef] ELSE Right[ep] # Right[ef]) THEN
    {Bug.out.PutF ["\nDiag.CloseFace - WARNING: edges "];
     PutE[ep]; Bug.out.PutF ["and "]; PutE[ef];
     Bug.out.PutF ["have different Left data"]};
  IF side = left THEN
    {e _ ConnectVertices [LNext[ep], ef];
     FixRight[e, Left[ef]]; SetLeft[e, newFace]}
  ELSE
    {e _ ConnectVertices [Sym[ep], OPrev[ef]];
     FixLeft[e, Right[ef]]; SetRight[e, newFace]}
END;
Traverse: PUBLIC ENTRY PROC
  [dg: DEdge, Visit: VisitProc, arg: REF _ NIL, choice: EdgeSet _ all]
 RETURNS [res: REF _ NIL] =
BEGIN
  -- uses a separately allocated mark table and stack, so that only read access to the diagram is required, and traversal can be aborted without leaving garbage in the diagram.
  MarkTable: TYPE = RECORD [PACKED SEQUENCE n: EdgeNo OF BOOL];
  Mark0: REF MarkTable = NEW [MarkTable[EdgeCount]];
  Mark1: REF MarkTable = NEW [MarkTable[EdgeCount]];
  stack: LIST OF DEdge _ NIL;
  e, ea: DEdge;

  Mark: PROC [e: DEdge] = INLINE
    -- Mark the directed edge e (but not Sym[e])
    {IF e.ix < 2 THEN Mark0[No[e]] _ TRUE ELSE Mark1[No[e]] _ TRUE};

  Marked: PROC [e: DEdge] RETURNS [BOOL] = INLINE
    -- TRUE if the directed edge e has been marked.
    {RETURN [IF e.ix < 2 THEN Mark0[No[e]] ELSE Mark1[No[e]]]};

  FOR k: EdgeNo IN [0 .. EdgeCount) DO Mark0[k] _ Mark1[k] _ FALSE ENDLOOP;
  -- Bug.out.PutF["\nDiag.Traverse: begin"];
  res _ arg;
  IF IsDummy [dg] THEN
    {IF choice = vertices THEN res _ Visit[dg, res];
     RETURN};
  stack _ LIST [dg];
  WHILE stack # NIL DO
    e _ stack.first; stack _ stack.rest;
    -- Bug.out.PutF["\nDiag.Traverse: unstacked edge "]; PutE[e];
    IF NOT Marked[e] THEN
      {-- edges out of Org[e] are all unvisited;
       IF choice = vertices THEN res _ Visit [e, res];
       ea _ e;
       DO
         IF choice = all THEN res _ Visit [e, res];
         Mark[e];
         IF NOT Marked[Sym[e]] THEN
           {IF choice = oneWay THEN res _ Visit [e, res];
            stack _ CONS [Sym[e], stack]};
         e _ ONext [e];
         IF e = ea THEN EXIT
        ENDLOOP
       }
   ENDLOOP;
  -- Bug.out.PutF["\nDiag.Traverse: end"];
END;
TopSort: PUBLIC PROC
  [dg: DEdge, Visit: VisitProc, arg: REF _ NIL, Ordered: EdgePredicate, clockWise: BOOL _ TRUE]
 RETURNS [res: REF _ NIL] =
BEGIN
  -- uses a separately allocated tables and stack, so that only read access to the
  --   diagram is required, and sorting can be aborted without leaving garbage in the diagram.
  DestTable: TYPE = RECORD
    [SEQUENCE n: EdgeNo OF REF VertexEntry];
  dest: REF DestTable =
    NEW [DestTable[EdgeCount]]; -- destination of edges in Ordered direction
  VertexEntry: TYPE = RECORD
    [edg: DEdge, -- an edge out of the vertex
     rCount: NAT _ 0, -- number of Ordered edges into the vertex
     pred, succ: REF VertexEntry _ NIL -- double list links (pred used only for heap)
     ];
  stack: REF VertexEntry _ NIL; -- singly linked stack of vertices with zero reference counts
  heap: REF VertexEntry _ NIL; -- set of vertices with nonzero ref counts

  Stack: PROC [ve: REF VertexEntry] =
    -- Insert ve at the top of stack
    {ve.succ _ stack; stack _ ve;
     Bug.out.PutF ["\nDiag.TopSort: Org[ "]; PutE[ve.edg]; Bug.out.PutF ["] stacked"]
     };

  UnStack: PROC RETURNS [ve: REF VertexEntry] =
    -- Pops ve from top of stack (which must be # NIL)
    {ve _ stack;
     stack _ stack.succ;
     Bug.out.PutF ["\nDiag.TopSort: Org[ "]; PutE[ve.edg]; Bug.out.PutF ["] unstacked"]
     };

  MakeVertexEntry: VisitProc =
    -- Create a VetexEntry for e and computes its reference count. Will put
    --   it in the heap or in the stack, depending on its reference count.
    {ve: REF VertexEntry = NEW [VertexEntry _ [edg: e]];
     ea: DEdge _ e;
     DO
       IF Ordered [Sym[ea]] THEN
         {ve.rCount _ ve.rCount + 1;
          dest[No[ea]] _ ve};
       ea _ ONext[ea];
       IF ea = e THEN EXIT
      ENDLOOP;
     IF ve.rCount = 0 THEN
       {Stack[ve]}
     ELSE
       {IF heap # NIL THEN heap.pred _ ve;
        ve.succ _ heap; heap _ ve};
     Bug.out.PutF ["\nDiag.TopSort: Org[ "]; PutE[e];
     Bug.out.PutF ["] blocked by %g edges", int[ve.rCount]]
     };

  RemoveFromHeap: PROC [ve: REF VertexEntry] =
    -- Remove entry ve from heap
    {IF ve.succ # NIL THEN
       {ve.succ.pred _ ve.pred};
     IF ve.pred # NIL THEN
       {ve.pred.succ _ ve.succ}
     ELSE
       {heap _ ve.succ}
     };

  ea: DEdge;
  ve, vd: REF VertexEntry;
  -- Build heap and initialize stack
  Bug.out.PutF["\nDiag.TopSort: begin"];
  FOR k: EdgeNo IN [0 .. EdgeCount) DO dest[k] _ NIL ENDLOOP;
  [] _ Traverse [dg, MakeVertexEntry, NIL, vertices];
  -- visite vertices in sorted order
  res _ arg;
  WHILE stack # NIL DO
    ve _ UnStack[];
    res _ Visit [ve.edg, res];
    -- Decrement reference counts of dominated vertices
    ea _ ve.edg;
    DO
      IF Ordered[ea] THEN
        {vd _ dest[No[ea]];
         vd.rCount _ vd.rCount - 1;
         IF vd.rCount = 0 THEN
           {RemoveFromHeap[vd];
            vd.edg _ Sym[ea];
            Stack[vd]}
         };
      ea _ IF clockWise THEN OPrev[ea] ELSE ONext [ea];
      IF ea = ve.edg THEN EXIT
     ENDLOOP
   ENDLOOP;
  IF heap # NIL THEN Bug.Error ["Loops in input ordering"];
  Bug.out.PutF["\nDiag.TopSort: end"];
END;
PutE: PUBLIC PROC [e: DEdge] =
BEGIN
  Bug.out.PutF ["%g:%g ", int[No[e]], int[e.ix]];
END;
KDual: PROC [e: DEdge, k: [0..4)] RETURNS [DEdge] = INLINE
{RETURN [[e.rec, (e.ix + k) MOD 4]]};
KPrim: PROC [e: DEdge, k: [0..4)] RETURNS [DEdge] = INLINE
{RETURN [[e.rec, (e.ix + 4 - k) MOD 4]]};
PutKDualRing: PROC [e: DEdge, k: [0..4)] =
BEGIN
  et: DEdge _ (e _ KDual[e, k]);
  piv: REF _ Org[e];
  DO
    PutE[KPrim[et, k]];
    et _ ONext[et];
    IF piv # Org[et] THEN  -- this is wonstruous, isn't it?
      {Bug.out.PutF ["# "];
       piv _ Org[et]};
    IF et = e THEN EXIT
   ENDLOOP
END;
PutORing: PUBLIC PROC [e: DEdge] =
{PutKDualRing [e, 0]};
PutRRing: PUBLIC PROC [e: DEdge] =
{PutKDualRing [e, 1]};
PutDRing: PUBLIC PROC [e: DEdge] =
{PutKDualRing [e, 2]};
PutLRing: PUBLIC PROC [e: DEdge] =
{PutKDualRing [e, 3]};
PutDiagram: PUBLIC PROC [e: DEdge] =
BEGIN
  DoPutORing: VisitProc =
    {Bug.out.PutF ["\n["]; PutORing[e]; Bug.out.PutF["]"]};
  [] _ Traverse [dg: e, Visit: DoPutORing, choice: vertices]
END;
END.


v-- COGDiagramImpl.mesa: 2-D diagrams - data structure and primitives
-- last modified by Stolfi - October 15, 1982 4:10 pm
-- To do: Try to avoid allocating mark bits, etc. for unneeded edges
-- To do: Check conditions for applying DeleteEdge & ContractEdge.
-- Directed edge with same Left as e and following e c.c.w. around Left[e].
-- Directed edge with same Right as e and following e c.c.w. around Right[e].
-- Directed edge with same Dest as e and following e c.c.w. around Dest[e].
-- Directed edge whose ONext is e.
-- Directed edge whose LNext is e.
-- Directed edge whose RNext is e.
-- Directed edge whose DNext is e.
-- PRIMITIVES FOR DIAGRAM CONSTRUCTION - - - - - - - - - - - - - - - - - - - - - - - - - - -
-- Returns Dual^k [e]
-- Returns Prim^k [e]
-- prints all edges in the ring defined by ONext, RNext, DNext or LNext, depending on whether k is 0, 1, 2, or 3.
Κ½–
"Mesa" style˜IprocšΟcΟbΠbc.™Dš
5™5Kšœžœ<™DKšœžœ9™B—KšΟk	œ œ œ
 œ˜NKšžœ œ
 œ œ œ œ
˜WKš œ œ œ
˜+šΟnœ œ
 œ œ˜3KšŸŸ
Ÿ
Ÿ
Ÿ
™KKšœ
 œ˜ —š‘œ œ
 œ œ˜3KšŸŸ
Ÿ
Ÿ
Ÿ
™MKšœ
 œ˜ —š‘œ œ
 œ œ˜3KšŸŸ
Ÿ
Ÿ
Ÿ
™KKšœ
 œ˜—K˜š‘œ œ
 œ œ˜3KšŸŸ

™"Kšœ
 œ˜ —š‘œ œ
 œ œ˜3KšŸŸ

™"Kšœ
 œ˜—š‘œ œ
 œ œ˜3KšŸŸ

™"Kšœ
 œ˜—š‘œ œ
 œ œ˜3KšŸŸ

™"Kšœ
 œ˜ —š‘œ œ
 œ˜+Kš œ œ, œ œ
 œ œ
 œ
˜l—K˜Kš
\™\Kšž	œ œ<˜[š	‘
œ œ
 œ
 œ ˜7Kš œ- œ
˜6—š‘
œ œ
 œ œ˜BKš œ œΏ
 œ
˜Χ
—š‘
œ œ
 œ œ˜JKš œ œΓ
 œ
˜Ϋ
—š‘œ œ ˜&Kš œ œ
˜"—š‘œ œ
 œ˜1Kš œ#œ»
 œ
˜υ
—š‘œ œ
 œ œ
˜?Kš œΜ
 œ œ œ œ
 œ% œ œ
 œ) œ
˜φ—š‘
œ œ
 œ œ˜:Kš œœ? œ œ+ œ- œ œ œ œ- œ œ
 œ# œ
˜λ—š	‘	œ œ
 œ( œž˜RKš œ œ
 œ œ) œ
 œ
 œ
 œ œ
 œ# œ
˜Υ—š‘	œ œ
 œ0 œ
˜ZKš œ œ œ
 œ œ œž
 œ
 œ^ œb œ
˜Ν—šΠbnœ œ
 œ
 œ& œ œ œ œ œ˜~Kš
 œ―
œ
 œ œ œ
 œ œ
 œ œ
 œ" œ
 œ" œ
 œ	 œ‘œ œ œ-œ œ
 œ œ
 œ œ‘œ œ œ œ œ0œ œ œ
 œ œ œ œ œ œ
 œ+œ œ œ œ œ œ
 œ	 œ	 œ
 œ.>œ œ
 œ œ*œ œ œ- œ
 œ œ2 œ
 œ œ
 œ œ+ œ4 œ œ
 œ	 œ
 œ) œ
˜Ή—š’œ œ
 œ& œ œ% œ œ œ œ œ˜
KšΞ
 œQœ]œ
 œ œ œ œ
 œ œ œŸœ œ œœ
 œ
Ÿœ œ œ
ŸŸœ œ œ>œ œ œ+œ‘œ œ œ
ŸŸ
œƒ
‘œ œ
 œ œŸ
Ÿœ
žœHœGœ	 œ œ4 œ œ œb œ œ
 œ œ œ œ œ	 œ œ
 œ²
‘œ œ œŸŸ
œ œ œ
 œ' œ œ
 œ& œ9 œ#œ+ œ œ œ œ
 œ( œ#œ œ	 œ
 œ84œ œ œ
 œJ œ œm œ œ œ œ
 œ
 œ œ œ œ œ
 œO œ
˜Α—š‘œ œ
 œ
˜Kš œ3 œ
˜<—š‘œ œ œ ˜:Kš
™Kšœ
 œ œ˜%—š‘œ œ œ ˜:Kš
™Kšœ
 œ œ˜)—š‘œ œ˜*Kš
q™qKš œ) œ
 œ1 œ œ!œ7 œ œ
 œ œ
 œ
˜ƒ—š‘œ œ
 œ
˜"Kš
œ˜—š‘œ œ
 œ
˜"Kš
œ˜—š‘œ œ
 œ
˜"Kš
œ˜—š‘œ œ
 œ
˜"Kš
œ˜—š‘
œ œ
 œ
˜$Kš œž
œ‡
 œ
˜
—Kš œ
˜K˜K˜—…—&p2£