(* Quad-edge data structure. *)

INTERFACE Quad;

(* 
  A data structure for the representation of quadrilateral complexes.
  
  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 and Modula-3
  by J. Stolfi (XEROX PARC and DEC SRC, 1983-1992) and in C by Jim Roth 
  (DEC CADM Advanced Group, May 1986).
*)

(*** BASIC TYPES ***)

TYPE
  T = Side;
  
  Side = RECORD q: Patch; r: [0..3] END;
  
  Patch <: REFANY;
  
(*** WALKING OPERATORS ***)

PROCEDURE Rot (s: Side): Side;
PROCEDURE Sym (s: Side): Side;
PROCEDURE Tor (s: Side): Side; (* Inverse of "Rot" *)

PROCEDURE Rotate (s: Side; r: INTEGER): Side;  (* Rot^r(s) *)

PROCEDURE Adj (s: Side): Side;

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

PROCEDURE MakePatch (): Side;

PROCEDURE Splice (s, t: Side);

(*** TRAVERSAL ***)

TYPE VisitProc = PROCEDURE (s: Side) RAISES ANY;

PROCEDURE EnumSides (s: Side; visit: VisitProc) RAISES ANY;
PROCEDURE EnumPatches (s: Side; visit: VisitProc) RAISES ANY;
(* 
  Calls "visit(e)" for sides "e" that can be reached from
  "s" by repeated application of "Adj"s and "Rot"s.
  
  "EnumSides" visits all such sides.  
  
  "EnumPatches" visits only one side on each patch: that is, if
  side "e" is reachable from "root", exactly one of "e", "Rot(e), 
  "Sym(e)", and "Tor(e)" will be visited.
*)

(*** ELEMENT NUMBERING ***)

PROCEDURE SideId(s: Side): CARDINAL;
PROCEDURE PatchId(s: Side): CARDINAL;
(*
  Every side has a distinct and immutable numerical id; ditto
  for the patches.
  
  The four sides of the same patch have consecutive ids;
  the lowest of them is divisible by four, and that one is
  the patch id.
  
  Thus, "PatchId(s) = PatchId(Rot(s)) <= SideId(s)" for all "s"
*)

END Quad.