<<-- 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.>> 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] = <<-- Directed edge with same Left as e and following e c.c.w. around Left[e].>> {RETURN [Rot[Onext[Tor[e]]]]}; Rnext: PUBLIC PROC [e: Edge] RETURNS [ne: Edge] = <<-- Directed edge with same Right as e and following e c.c.w. around Right[e].>> {RETURN [Tor[Onext[Rot[e]]]]}; Dnext: PUBLIC PROC [e: Edge] RETURNS [ne: Edge] = <<-- Directed edge with same Dest as e and following e c.c.w. around Dest[e].>> {RETURN [Sym[Onext[Sym[e]]]]}; Oprev: PUBLIC PROC [e: Edge] RETURNS [ne: Edge] = <<-- Directed edge whose Onext is e.>> {RETURN [Rot[Onext[Rot[e]]]]}; Lprev: PUBLIC PROC [e: Edge] RETURNS [ne: Edge] = <<-- Directed edge whose Lnext is e.>> {RETURN [Sym[Onext[e]]]}; Rprev: PUBLIC PROC [e: Edge] RETURNS [ne: Edge] = <<-- Directed edge whose Rnext is e.>> {RETURN [Onext[Sym[e]]]}; Dprev: PUBLIC PROC [e: Edge] RETURNS [ne: Edge] = <<-- Directed edge whose Dnext is e.>> {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; <<-- PRIMITIVES FOR DIAGRAM CONSTRUCTION - - - - - - - - - - - - - - - - - - - - - - - - - - ->> 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 <<-- Returns Rot^k [e]>> {RETURN [[e.rec, (e.ix + k) MOD 4]]}; KTor: PROC [e: Edge, k: [0..4)] RETURNS [Edge] = INLINE <<-- Returns Tor^k [e]>> {RETURN [[e.rec, (e.ix + 4 - k) MOD 4]]}; PutKRotring: PROC [e: Edge, k: [0..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; 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. <> <> <<>> <<>> <<>> <<>>