(* Quad-edge data structure. *)

INTERFACE QuadEdge;

(* 
  A data structure for the representation of cellular
  subdivisions of orientable surfaces.
  
  See 

  "Primitives for the Manipulation of General Subdivisions 
  and the Computation of Voronoi Diagrams"
  by L. Guibas, J. Stolfi, ACM TOG, April 1985

  Implemented by Jim Roth (DEC CADM Advanced Group) on May 1986.
  Adapted by J. Stolfi on April 1993.
*)

(*** BASIC TYPES ***)

TYPE
  T = Arc;
  
  Arc = RECORD edge: Edge; rot: [0..3] END;
  
  Edge <: REFANY;
  
(*** EDGE ORIENTATION OPERATORS ***)

PROCEDURE Rot (a: Arc): Arc;
PROCEDURE Sym (a: Arc): Arc;
PROCEDURE Tor (a: Arc): Arc; (* Inverse of "Rot" *)

(*** VERTEX/FACE WALKING OPERATORS ***)

PROCEDURE ONext (a: Arc): Arc;
PROCEDURE RNext (a: Arc): Arc;
PROCEDURE DNext (a: Arc): Arc;
PROCEDURE LNext (a: Arc): Arc;

PROCEDURE OPrev (a: Arc): Arc;
PROCEDURE RPrev (a: Arc): Arc;
PROCEDURE DPrev (a: Arc): Arc;
PROCEDURE LPrev (a: Arc): Arc;

PROCEDURE ODeg(a: Arc): CARDINAL;   (* Degree of vertex "Org(a)" *)
PROCEDURE DDeg(a: Arc): CARDINAL;   (* Degree of vertex "Dst(a)" *)
PROCEDURE LDeg(a: Arc): CARDINAL;   (* Degree of face "Left(a)" *)
PROCEDURE RDeg(a: Arc): CARDINAL;   (* Degree of face "Right(a)" *)

(*** CREATING AND MODIFYING STRUCTURES ***)

PROCEDURE MakeEdge (no: EdgeNo): Arc;

PROCEDURE Splice (a, b: Arc);

(*** TRAVERSAL ***)

TYPE VisitProc = PROCEDURE (a: Arc) RAISES ANY;

PROCEDURE EnumArcs (a: Arc; visit: VisitProc) RAISES ANY;
PROCEDURE EnumEdges (a: Arc; visit: VisitProc) RAISES ANY;
PROCEDURE EnumVertices (a: Arc; visit: VisitProc) RAISES ANY;
(* 
  Calls "visit(e)" for arcs "e" that can be reached from
  "a" by repeated application of "Sym"s and "Onext"s.
  
  "EnumArcs" visits all such arcs.  
  
  "EnumEdges" visits only one arc on each edge: that is, if
  arc "e" is reachable from "root", exactly one of "e" and "Sym(e)"
  will be visited.
  
  "EnumVertices" visits exactly one arc out of each reachable
  vertex.

  Note that if arc "e" is reachable then neither "Rot(e)" 
  nor "Tor(e)" are reachable (unless "Splice" has been
  improperly used.)
  
*)

(*** ELEMENT NUMBERING ***)

PROCEDURE ArcId(a: Arc): CARDINAL;
PROCEDURE EdgeId(a: Arc): CARDINAL;
PROCEDURE VertexId(a: Arc): CARDINAL;
(*
  Each arc, edge, and vertex is identified by a distinct numerical id.
  
  The four arcs corresponding to the same edge have consecutive ids;
  the lowest of them is divisible by four, and is the edge id.
  
  The id of a vertex is that of the lowest arc with the same origin.
  
  Thus, the following hold

    EdgeId(a) = EdgeId(Rot(a)) <= ArcId(a)

    VertexId(a) = VertexId(ONext(a)) <= ArcId(a)

  The cost of "VertexId" s proprotional to the vertex's degree.
*)

END QuadEdge.