DIRECTORY
  COGDebug USING [out, Error],
  IO USING [PutF, int],
  COGQuad;
COGQuadImpl: CEDAR MONITOR
  IMPORTS COGQuad, COGDebug, IO
  EXPORTS COGQuad =
BEGIN
  OPEN COGQuad, Bug: COGDebug, IO;
Lnext: PUBLIC PROC [e: Edge] RETURNS [ne: Edge] =
{RETURN [Rot[Onext[Tor[e]]]]};
Rnext: PUBLIC PROC [e: Edge] RETURNS [ne: Edge] =
{RETURN [Tor[Onext[Rot[e]]]]};
Dnext: PUBLIC PROC [e: Edge] RETURNS [ne: Edge] =
{RETURN [Sym[Onext[Sym[e]]]]};

Oprev: PUBLIC PROC [e: Edge] RETURNS [ne: Edge] =
{RETURN [Rot[Onext[Rot[e]]]]};
Lprev: PUBLIC PROC [e: Edge] RETURNS [ne: Edge] =
{RETURN [Sym[Onext[e]]]};
Rprev: PUBLIC PROC [e: Edge] RETURNS [ne: Edge] =
{RETURN [Onext[Sym[e]]]};
Dprev: PUBLIC PROC [e: Edge] RETURNS [ne: Edge] =
{RETURN [Tor[Onext[Tor[e]]]]};
SetAllOdata: PUBLIC PROC [e: Edge, d: EdgeData] =
BEGIN
  et: Edge _ e;
  DO
    SetOdata[et, d];
    et _ Onext[et];
    IF et = e THEN RETURN
   ENDLOOP
END;

EdgeCount: PUBLIC EdgeNo _ 0;		-- Edge count (undirected) - protected by the monitor lock.
GetnextEdgeNo: ENTRY PROC RETURNS [no: EdgeNo] = INLINE
BEGIN
  no _ EdgeCount;
  EdgeCount _ EdgeCount+1
END;
MakeBridge: PUBLIC PROC [od, dd, ld, rd: EdgeData _ NIL] RETURNS [e: Edge] =
BEGIN
  e.rec _ NEW [EdgeRec];
  e.ix _ 0;
  e.rec^ _
    [data: [od, rd, dd, ld],
     next: [e, Tor[e], Sym[e], Rot[e]],
     no: GetnextEdgeNo[]];
  Bug.out.PutF ["\nQuad.MakeBridge -- edge "]; PutE[e]
END;
SetOnext: PROC [x, xn: Edge] = INLINE
BEGIN
  x.rec.next[x.ix] _ xn
END;
Splice: PUBLIC PROC [a, b: Edge] =
BEGIN
  -- LOOK! NOTHING IN THE SLEEVES...
  alpha: Edge = Rot[Onext[a]];
  beta: Edge = Rot[Onext[b]];
  SetOnext [a, Tor[alpha]];
  SetOnext [b, Tor[beta]];
  SetOnext [alpha, Tor[a]];
  SetOnext [beta, Tor[b]]
  -- PRESTO!
END;
InvalidArguments: PUBLIC ERROR = CODE;
AttachEdge: PUBLIC PROC [e, a, b: Edge] =
BEGIN
  Bug.out.PutF["\nQuad.AttachEdge - edge "]; PutE[e];
  Bug.out.PutF["from Org[ "]; PutE[a];
  Bug.out.PutF["] to Org[ "]; PutE[b]; Bug.out.PutF["]"];

  IF Onext[e]#e OR Dnext[e]#e THEN
    {Bug.out.PutF["\n Warning - e is not an isolated bridge"]};
  IF a=b THEN
    {Bug.out.PutF["\n Error - a=b"];
     ERROR[InvalidArguments]};
  Splice[a, e];
  Splice[b, Sym[e]];
END;
RemoveEdge: PUBLIC PROC [e: Edge] RETURNS [a, b: Edge] =
BEGIN
  a _ Oprev[e];
  b _ Oprev[Sym[e]];
  Splice[b, Sym[e]];
  Splice[a, e]
END;
ConnectVertices: PUBLIC PROC [a, b: Edge] RETURNS [e: Edge] =
BEGIN
  e _ MakeBridge [Odata[a], Odata[b], Ldata[b], Ldata[a]];
  AttachEdge[e, a, b];
END;
AddLeaf: PUBLIC PROC [ep: Edge, side: EdgeSide, dd: EdgeData _ NIL] RETURNS [e: Edge] =
BEGIN
  a: Edge = IF side = left THEN Lnext[ep] ELSE Sym[ep];
  fd: EdgeData = IF side = left THEN Left[ep] ELSE Right[ep];
  e _ MakeBridge [Ddata[ep], dd, fd, fd];
  Bug.out.PutF["\nQuad.AddLeaf - edge "]; PutE[e];
  Bug.out.PutF["from Dest[ "]; PutE[ep]; Bug.out.PutF["] to new vertex"];

  Splice[a, e]
END;
CloseFace: PUBLIC PROC [ep, ef: Edge, side: EdgeSide, fd: EdgeData _ NIL] RETURNS [e: Edge] =
BEGIN
  IF side = left THEN
    {e _ MakeBridge[Ddata[ep], Odata[ef], Ldata[ef], Ldata[ef]];
     AttachEdge [e, Lnext[ep], ef];
     SetAllLdata[e, fd]}
  ELSE
    {e _ MakeBridge[Ddata[ep], Odata[ef], Rdata[ef], Rdata[ef]];
     AttachEdge [e, Sym[ep], Oprev[ef]];
     SetAllRdata[e, fd]}
END;
Traverse: PUBLIC ENTRY PROC
  [e: Edge, 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 subdivision is required, and traversal can be aborted without leaving garbage in the structure.
  MarkTable: TYPE = RECORD [PACKED SEQUENCE n: EdgeNo OF BOOL];
  Mark0: REF MarkTable = NEW [MarkTable[EdgeCount]];
  Mark1: REF MarkTable = NEW [MarkTable[EdgeCount]];
  stack: LIST OF Edge _ NIL;
  e, ea: Edge;

  Mark: PROC [e: Edge] = 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: Edge] 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["\nQuad.Traverse: begin"];
  res _ arg;
  stack _ LIST [e];
  WHILE stack # NIL DO
    e _ stack.first; stack _ stack.rest;
    -- Bug.out.PutF["\nQuad.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["\nQuad.Traverse: end"];
END;
TopSort: PUBLIC PROC
  [e: Edge, 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: Edge, -- 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 ["\nQuad.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 ["\nQuad.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: Edge _ 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 ["\nQuad.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: Edge;
  ve, vd: REF VertexEntry;
  -- Build heap and initialize stack
  Bug.out.PutF["\nQuad.TopSort: begin"];
  FOR k: EdgeNo IN [0 .. EdgeCount) DO dest[k] _ NIL ENDLOOP;
  [] _ Traverse [e, 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["\nQuad.TopSort: end"];
END;
PutE: PUBLIC PROC [e: Edge] =
BEGIN
  Bug.out.PutF ["%g:%g ", int[No[e]], int[e.ix]];
END;
KRot: PROC [e: Edge, k: [0..4)] RETURNS [Edge] = INLINE
{RETURN [[e.rec, (e.ix + k) MOD 4]]};
KTor: PROC [e: Edge, k: [0..4)] RETURNS [Edge] = INLINE
{RETURN [[e.rec, (e.ix + 4 - k) MOD 4]]};
PutKRotring: PROC [e: Edge, k: [0..4)] =
BEGIN
  et: Edge _ (e _ KRot[e, k]);
  piv: REF _ Org[e];
  DO
    PutE[KTor[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: Edge] =
{PutKRotring [e, 0]};
PutRring: PUBLIC PROC [e: Edge] =
{PutKRotring [e, 1]};
PutDring: PUBLIC PROC [e: Edge] =
{PutKRotring [e, 2]};
PutLring: PUBLIC PROC [e: Edge] =
{PutKRotring [e, 3]};
PutDiagram: PUBLIC PROC [e: Edge] =
BEGIN
  DoPutOring: VisitProc =
    {Bug.out.PutF ["\n["]; PutOring[e]; Bug.out.PutF["]"]};
  [] _ Traverse [e: e, Visit: DoPutOring, choice: vertices]
END;
END.

Ϊ-- COGQuadImpl.mesa: orientable 2-D subdivisions - data structure and primitives
-- last modified by Stolfi - April 8, 1983 5:32 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 Rot^k [e]
-- Returns Tor^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.
Edited on April 8, 1983 5:32 pm, by Stolfi
Changed everything to conform to STOC paper.




Κx–
"Mesa" style˜IprocšΟcΟbΠbc=™Pš
2™2Kšœžœ<™DKšœžœ9™B—KšΟk	œ œ œ
 œ˜KKšžœ œ
 œ œ œ œ
˜NKš œ œ œ
˜(šΟnœ œ
 œ œ
˜1KšŸŸ
Ÿ
Ÿ
Ÿ
™KKšœ
 œ˜—š‘œ œ
 œ œ
˜1KšŸŸ
Ÿ
Ÿ
Ÿ
™MKšœ
 œ˜—š‘œ œ
 œ œ
˜1KšŸŸ
Ÿ
Ÿ
Ÿ
™KKšœ
 œ˜—K˜š‘œ œ
 œ œ
˜1KšŸŸ

™"Kšœ
 œ˜—š‘œ œ
 œ œ
˜1KšŸŸ

™"Kšœ
 œ˜—š‘œ œ
 œ œ
˜1KšŸŸ

™"Kšœ
 œ˜—š‘œ œ
 œ œ
˜1KšŸŸ

™"Kšœ
 œ˜—š‘œ œ
 œ˜1Kš œ œ. œ œ
 œ œ
 œ
˜m—K˜Kš
\™\Kšž	œ œ;˜Zš	‘
œ œ
 œ
 œ ˜7Kš œ- œ
˜6—š
‘
œ œ
 œ œ œ˜LKš œ œΊ
 œ
˜Ρ
—š‘œ œ ˜%Kš œ œ
˜"—š‘œ œ
 œ˜"Kš œ#œ¬
 œ
˜ζ
—Kš‘œ œ˜&š‘
œ œ
 œ˜)Kš œ›
 œ œ œC œ œ+ œ: œ
˜ό—š‘
œ œ
 œ œ˜8Kš œJ œ
˜S—š‘œ œ
 œ œ˜=Kš œS œ
˜\—š‘œ œ
 œ+ œ œ
ž˜WKš œ
 œ
 œ œ œ
 œ
 œΓ
 œ
˜·—š
‘	œ œ
 œ/ œ œ˜]Kš
 œ œ
 œ
 œ„
 œ
˜¨—šΠbnœ œ
 œ
 œ$ œ œ œ œ œ˜|Kš…
 œ΅
œ
 œ œ œ
 œ œ
 œ œ
 œ" œ
 œ" œ
 œ œ‘œ œ
 œ-œ œ
 œ œ
 œ œ‘œ œ œ œ œ0œ œ œ
 œ œ œ œ œ œ
 œ+œ œ œ	 œ
 œ.>œ œ
 œ œ*œ œ œ- œ
 œ œ2 œ
 œ œ
 œ œ+ œ4 œ œ
 œ	 œ
 œ) œ
˜ΰ—š’œ œ
 œ$ œ œ% œ œ œ œ œ˜Ž
KšΞ
 œQœ]œ
 œ œ œ œ
 œ œ œŸœ œ œœ
 œ
Ÿœ œ œ
ŸŸœ œ œ>œ œ œ+œ‘œ œ œ
ŸŸ
œƒ
‘œ œ
 œ œŸ
Ÿœ
žœHœGœ	 œ œ3 œ œ œb œ œ
 œ œ œ œ œ	 œ œ
 œ²
‘œ œ œŸŸ
œ œ œ
 œ' œ œ
 œ& œ8 œ#œ+ œ œ œ œ
 œ' œ#œ œ	 œ
 œ84œ œ œ
 œJ œ œm œ œ œ œ
 œ
 œ œ œ œ œ
 œO œ
˜½—š‘œ œ
 œ˜Kš œ3 œ
˜<—š‘œ œ œ
 ˜7Kš
™Kšœ
 œ œ˜%—š‘œ œ œ
 ˜7Kš
™Kšœ
 œ œ˜)—š‘œ œ˜(Kš
q™qKš œ' œ
 œ0 œ œ!œ7 œ œ
 œ œ
 œ
˜€—š‘œ œ
 œ˜!Kš
œ˜—š‘œ œ
 œ˜!Kš
œ˜—š‘œ œ
 œ˜!Kš
œ˜—š‘œ œ
 œ˜!Kš
œ˜—š‘
œ œ
 œ˜#Kš œž
Ϡ
 œ
˜œ
—Kš œ
˜K˜š
*™*J™,—K™K™K™K™—…—#t/Ζ