(* Oct-edge data structure. *)

INTERFACE OctEdge;

(* 
  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

  This version created by J.Stolfi (DCC, Unicamp 94-04-20).
  Based on several previous implementations in Mesa, Modula-2, C, and Modula-3
  by J. Stolfi (XEROX PARC and DEC SRC, 1983-1992), Jim Roth 
  (DEC CADM Advanced Group, May 1986), and Rober M. Rosi
  (DCC-UNICAMP, 1993-1994).
*)

(*** BASIC TYPES ***)

TYPE
  T <: PublicT;
  
  PublicT = OBJECT METHODS
    init(num: EdgeNum): Edge; 
      (* 
        Initializes "e" so that it describes an isolated
        edge with two distinct vertices and one face. *)
    END;

  Arc = RECORD edge: Edge; obits: [0..7] END;
  
(*** EDGE ORIENTATION OPERATORS ***)

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

PROCEDURE Flop (a: Arc): Arc; (* Reverse longitudinal orientation *)
PROCEDURE Flip (a: Arc): Arc; (* Reverse transversal orientation *)
PROCEDURE Dual (a: Arc): Arc; (* Exchange lng/lat orientations *)

(*** 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;

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

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 Splice (a, b: Arc);

          
      write (wr: Wr.T);
        (*
          Calls "PrintArc(wr, s Rot^i Onext)" for "i" in [0..3],
          where "s" is the reference arc of "self".  Prints
          a space between two arcs. *)
          
      read (rd: Rd.T; READONLY map: ARRAY OF Arc) RAISES {Error};
        (*
          Modifies 
  
(*** 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 OctEdge.