-- 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 [Rot[Onext[Tor[e]]]]};

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

{RETURN [Tor[Onext[Rot[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 [Rot[Onext[Rot[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 [Tor[Onext[Tor[e]]]]};

BEGIN
et: Edge ← e;
DO
SetOdata[et, d];
et ← Onext[et];
IF et = e THEN RETURN
ENDLOOP
END;

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

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;

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

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;

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;

BEGIN
a ← Oprev[e];
b ← Oprev[Sym[e]];
Splice[b, Sym[e]];
Splice[a, e]
END;

BEGIN
e ← MakeBridge [Odata[a], Odata[b], Ldata[b], Ldata[a]];
AttachEdge[e, a, b];
END;

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;

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;

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;

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;

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

-- Returns Rot^k [e]

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

-- Returns Tor^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: 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;

{PutKRotring [e, 0]};

{PutKRotring [e, 1]};

{PutKRotring [e, 2]};

{PutKRotring [e, 3]};

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