(* Quad-edge data structure. *)

INTERFACE SPQuad;

(* See 

   "Primitives for the Manipulation of General Subdivisions 
   and the Computation of Voronoi Diagrams"

   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.

*)

TYPE
  T = Arc;
  
  Arc = RECORD quad: Quad; bits: [0..3] END;
  
  Quad <: REFANY;
  
CONST
  NullArc = Arc{quad := NIL, bits := 0};  (* NIL for Arc variables *)
  
(* 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;

(* Data pointers: *)

PROCEDURE Odata (a: Arc): REFANY;
PROCEDURE Rdata (a: Arc): REFANY;
PROCEDURE Ddata (a: Arc): REFANY;
PROCEDURE Ldata (a: Arc): REFANY;

PROCEDURE SetOdata (a: Arc; data: REFANY);
PROCEDURE SetRdata (a: Arc; data: REFANY);
PROCEDURE SetDdata (a: Arc; data: REFANY);
PROCEDURE SetLdata (a: Arc; data: REFANY);

PROCEDURE MakeEdge (): Arc;

PROCEDURE Splice (a, b: Arc);

PROCEDURE ToText(a: Arc): TEXT;

(* Enumeration *)

PROCEDURE NumberArcs(a: Arc): REF ARRAY OF Arc;
  (*
    Returns a vector containing all arcs reachable from "a" by zero or
    more Onext and Sym operations.  The two orientations of the "i"th
    edge will be found at elements [2*i] and [2*i + 1] of the vector.
  *)
  
PROCEDURE CollectArcs(a: Arc; VAR arc: ARRAY OF Arc);
  (*
    Stores into "arc" all arcs reachable from "a" by zero or more
    Onext and Sym operations.  Assumes that NumberArcs(a) has been
    called previously.  The two orientations of the "i"th edge will be
    found at elements [2*i] and [2*i + 1] of the vector.
  *)
  
PROCEDURE EdgeNum(a: Arc): CARDINAL;
  (*
    The number of the undirected edge "a.quad", as assigned by
    NumberArcs.  If EdgeNum(a) = i", the arcs "a" and "Sym(a)" are
    found in elements "[2*i]" and "[2*i+1]" of the output of
    NumberArcs, in some order. *)
    
PROCEDURE SetEdgeNum(a: Arc; num: CARDINAL);
  (*
    Sets the number of the undirected edge "a.quad".
    To be used only by routines that know what they are doing. *)

END SPQuad.