(* ====== Arcs ====== *)

(* A FRBits value identifies a particular arc within any edge, according 
   to the following table (where 'e' is the reference arc of the edge):
    
      arc         FRBits   FBit  SBit  DBit   RBits
      ----------------------------------------------
      e            000 0    0     0     0       0  
      e.flip       001 1    1     0     0       0  
      e.rot        010 2    0     0     1       1  
      e.rot.flip   011 3    1     0     1       1  
      e.sym        100 4    0     1     0       2  
      e.sym.flip   101 5    1     1     0       2  
      e.tor        110 6    0     1     1       3  
      e.tor.flip   111 7    1     1     1       3   
       
   In general, the arc Flip^f(Rot^r(e)), for r in [0..3] and f in [0..1],
   has FRBits equal to 2r + f
*)

(* ====== Edge/Arc Numbering ====== *)

(* 
  The procedures in this section use the edge
  number assigned at edge creation time, or set later with
  SetEdgeNo/NumberEdges. *)

PROCEDURE SetEdgeNo (e: Edge; no: EdgeNo); 
(*
  Assigns number "no" to the edge "e", and thus to all
  its arcs. *)

PROCEDURE GetEdgeNo (e: Edge): EdgeNo; 
(* Returns the edge number. *)

PROCEDURE GetOrgNo (a: Arc): OrgNo;
(* Returns the number stored in the Org half of arc "a". *)

PROCEDURE GetArcNo (a: Arc): ArcNo;
(* Returns the number of arc "a" = GetEdgeNo(a.edge) * 8 + a.bits *)

(*
  
PROCEDURE SetOrgNo (a: Arc; no: OrgNo);
(*
  Assigns number "no" to the "Org" half of "a" and "Flip(a)".
  Does NOT change the OrgNo's of other arcs with same Org
  as "a". *)

-----

REVEAL 
  Edge = PublicEdge BRANDED
  OBJECT 
    no: EdgeNo := 0;                  (* Edge number *)
    (* Element index [r] refers to arc a[r] = Arc{e,r}: *)
    enext: ARRAY [0..3] OF Edge;      (* Edge of Onext(a[r]) *)
    bnext: ARRAY [0..3] OF [0..7];    (* FRBits of Onext(a[r]) *)
  OVERRIDES  
    init := OctInit;
  END;
    
PROCEDURE OctInit(e: Edge; no: EdgeNo): Edge =    
  BEGIN 
    e.no := no;
            
    FOR i := 0 TO 3 DO e.enext[i] := e END;
    
    e.bnext[0] := 0;
    e.bnext[1] := 6;
    e.bnext[2] := 4;
    e.bnext[3] := 2;
    RETURN e
  END OctInit;
  
PROCEDURE NumberEdges(READONLY e: ARRAY OF Edge): REF ARRAY OF Edge =
  (*
    Enumerates all edges reachable from "a", and assigns
    them consecutive serial numbers starting from 0.
    Returns a vector of those edges, indexeed by serial number. *)

  CONST InitNE = 64;
  VAR 
    et := NEW(REF ARRAY OF Edge, InitNE);
    NE: CARDINAL := 0;  (* Num of Edges seen so far *)
    KE: CARDINAL := 0;  (* Num of Edges whose "enext"s have been seen. *)
    
    (* An edge "e" has been seen iff "et[e.no] = e". *)

  PROCEDURE VisitAndMark (t: Edge) =
    (* If t is unmarked: visit, mark, and es it. *)
    BEGIN
      WITH tno = t.edge DO
        IF tno >= NE OR et[tno] # t THEN
          tno := NE;  StoreEdge(t, NE, et)
        END
      END
    END VisitAndMark;
  
  BEGIN
    FOR i := 0 TO LAST(e) DO VisitAndMark (e[i]) END;
    WHILE KE < NE DO
      VisitAndMark(et[KE].enext[0]);
      VisitAndMark(et[KE].enext[1]);
      VisitAndMark(et[KE].enext[2]);
      VisitAndMark(et[KE].enext[3]);
      INC(KE)
    END;
    WITH
      r = NEW(REF ARRAY OF Edge, NE)
    DO
      r^ := SUBARRAY(et^, 0, NE);
      RETURN r
    END;
  END NumberEdges;
  
PROCEDURE StoreEdge(e: Edge; VAR N: CARDINAL; VAR et: REF ARRAY OF Edge) =
  (* 
    Stores "e" in "et[N]" and increments "N".  
    If necessary, reallocates "et". *)
  BEGIN
    WITH maxN = NUMBER(et^) DO
      IF N = maxN THEN
        WITH 
          maxNew = 2*maxN, 
          atNew = NEW(REF ARRAY OF Edge, maxNew)
        DO
          SUBARRAY(atNew^, 0, maxN) := et^;
          et := atNew
        END;
      END;
    END;
    et[N] := e;
    INC(N);
  END StoreEdge;
 
PROCEDURE StoreArc(e: Arc; VAR N: CARDINAL; VAR at: REF ARRAY OF Arc) =
  (* 
    Stores "a" in "at[N]" and increments "N".  
    If necessary, reallocates "at". *)
  BEGIN
    WITH maxN = NUMBER(at^) DO
      IF N = maxN THEN
        WITH 
          maxNew = 2*maxN, 
          atNew = NEW(REF ARRAY OF Arc, maxNew)
        DO
          SUBARRAY(atNew^, 0, maxN) := at^;
          at := atNew
        END;
      END;
    END;
    at[N] := a;
    INC(N);
  END StoreArc;
 
PROCEDURE Enum1(
    NE: CARDINAL;
    READONLY a: ARRAY OF Arc; 
    step1: StepProc;
  ): REF ARRAY OF Arc =
  (*
    Enumerates the arcs reachable from "a" through
    zero or more applications of the permutation "step1".
    Returns a vector of those arcs. 
    Assumes all reachable edges have distinct serial numbers
    in the range [0..NE-1]. *)
  BEGIN
    WITH 
      NA = 8*NE,
      mark = NEW(REF ARRAY OF BOOLEAN, NA)^
      (* An arc "a" has been seen if mark[GetArcNo(a)] = TRUE. *)
    DO

      CONST InitN1 = 64;
      VAR 
        at1 := NEW(REF ARRAY OF Arc, InitN1);
        N1: CARDINAL := 0;  (* Num of arcs seen so far *)
        K1: CARDINAL := 0;  (* Num of arcs whose "step1"s have been seen. *)
 
      PROCEDURE VisitAndMark (t: Arc) =
        (* If t is unmarked: visit, mark, and save it. *)
        BEGIN
          WITH tno = 8 * t.edge.no + t.bits DO
            <* ASSERT tno < NA *>
            IF NOT mark[tno] THEN
              mark[tno] := TRUE; StoreArc(t, N1, at1)
            END
          END
        END VisitAndMark;

      BEGIN
        FOR i := 0 TO LAST(mark) DO mark[i] := FALSE END;
        FOR i := 0 TO LAST(a) DO VisitAndMark(a[i]) END;
        WHILE K1 < N1 DO
          VisitAndMark(step1(at[KE]));
        END;
        WITH
          r = NEW(REF ARRAY OF Arc, N1)
        DO
          r^ := SUBARRAY(at^, 0, N1);
          RETURN r
        END;
      END
    END
  END Enum1;

PROCEDURE Enum(
    NE: CARDINAL;
    READONLY a: ARRAY OF Arc; 
    step: ARRAY OF StepProc;
    visit: ARRAY OF VisitProc;
  ): ARRAY OF REF ARRAY OF Arc =
  (*
    Enumerates the arcs reachable from "a" through
    zero or more applications of the permutations "step[0..M-1]".
    
    Returns a set of vectors "r[0..M]", such that "r[d]"
    is a list with exactly one arc in each reachable orbit of the
    subgroup generated by "step[d..M-1]".  
    
    Thus, "r[M]" is the list of all reachable arcs; 
    "r[M-1]" has one arc out of each "step[M-1]"-orbit;
    "r[M-2]" has one arc out of each "step[M-1]+step[M-2]"-orbit;
    and so on. 
    Assumes all reachable edges have distinct serial numbers
    in the range [0..NE-1]. *)
  BEGIN
    WITH 
      M = NUMBER(step),
      NA = 8*NE,
      mark = NEW(REF ARRAY OF BOOLEAN, NA)^
      (* An arc "a" has been seen if mark[GetArcNo(a)] = TRUE. *)
    DO

      PROCEDURE DoEnum(
          a: Arc;
          READONLY st: ARRAY OF StepProc; 
          READONLY vs: ARRAY OF VisitProc;
        ): CARDINAL =
        BEGIN
          IF <a is unmarked> THEN
            
            IF NUMBER(st) = 0 THEN
              vs(a, 1)
            ELSE
              n := Enum(a, REST(st), REST(vs));
              vs(a, n)
            END
          END
        END DoEnum;
      
      CONST InitN = 64;
      VAR 
        at: ARRAY [0..M-1] OF REF ARRAY OF Arc;
        N1: CARDINAL := 0;  (* Num of arcs seen so far *)
        K1: CARDINAL := 0;  (* Num of arcs whose "step1"s have been seen. *)
 
      PROCEDURE VisitAndMark (t: Arc) =
        (* If t is unmarked: visit, mark, and save it. *)
        BEGIN
          WITH tno = 8 * t.edge.no + t.bits DO
            <* ASSERT tno < NA *>
            IF NOT mark[tno] THEN
              mark[tno] := TRUE; StoreArc(t, N1, at1)
            END
          END
        END VisitAndMark;

      BEGIN
         := NEW(REF ARRAY OF Arc, InitN);
        
        FOR i := 0 TO LAST(a) DO VisitAndMark (a[i]) END;
        WHILE K1 < N1 DO
          VisitAndMark(step1(at[KE]));
        END;
        WITH
          r = NEW(REF ARRAY OF Arc, N1)
        DO
          r^ := SUBARRAY(at^, 0, N1);
          RETURN r
        END;
      END
    END
  END Enum1;



PROCEDURE NumberElements(READONLY a: ARRAY OF Arc): ElementTables =
  BEGIN
    WITH 
      e = NumberEdges(a),
      NE = NUMBER(e^),
      v = NumberVertices(a, NE),
      f = NumberFaces(a, NE),
      t = ElementTables{edge := e, vertex := v, face := f}
    DO
      RETURN t
    END
  END NumberElements;