-- 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].

{RETURN [Dual[ONext[Prim[e]]]]};

-- Directed edge with same Right as e and following e c.c.w. around Right[e].

{RETURN [Prim[ONext[Dual[e]]]]};

-- Directed edge with same Dest as e and following e c.c.w. around Dest[e].

{RETURN [Sym[ONext[Sym[e]]]]};

-- Directed edge whose ONext is e.

{RETURN [Dual[ONext[Dual[e]]]]};

-- Directed edge whose LNext is e.

{RETURN [Sym[ONext[e]]]};

-- Directed edge whose RNext is e.

{RETURN [ONext[Sym[e]]]};

-- Directed edge whose DNext is e.

{RETURN [Prim[ONext[Prim[e]]]]};

BEGIN
et: DEdge ← e;
DO
FixOrg[et, v];
et ← ONext[et];
IF et = e THEN RETURN
ENDLOOP
END;

BEGIN
no ← EdgeCount;
EdgeCount ← EdgeCount+1
END;

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;

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;

BEGIN
x.rec.next[x.ix] ← xn
END;

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;

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;

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;

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;

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;

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;

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;

BEGIN
Bug.out.PutF ["%g:%g ", int[No[e]], int[e.ix]];
END;

-- Returns Dual^k [e]

{RETURN [[e.rec, (e.ix + k) MOD 4]]};

-- Returns Prim^k [e]

{RETURN [[e.rec, (e.ix + 4 - k) MOD 4]]};

-- prints all edges in the ring defined by ONext, RNext, DNext or LNext, depending on whether k is 0, 1, 2, or 3.

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;

{PutKDualRing [e, 0]};

{PutKDualRing [e, 1]};

{PutKDualRing [e, 2]};

{PutKDualRing [e, 3]};

BEGIN
DoPutORing: VisitProc =
{Bug.out.PutF ["\n["]; PutORing[e]; Bug.out.PutF["]"]};
[] ← Traverse [dg: e, Visit: DoPutORing, choice: vertices]
END;