(* Oct-edge data structure. *)
(* Last edited by Rober Marcone Rosi on Mon Oct 18 1993 *)

MODULE Oct;

IMPORT Lex, FloatMode, Word, Wr, Rd, Fmt, Thread, TextRd, TextWr;
(* IMPORT Stdio; *)

(* The arc Onext(a) is given by arc(a.edge.enext[rbit], a.edge.bnext[rbit]),
   provided that the "flip' bit of a is 0. Otherwise Onext(a) is computed by 
   the formula: Onext(a) = Flip(Rot(Onext(Rot(Flip(a)))))
*)

TYPE 
  MarkBit = (* BITS 1 FOR *) BOOLEAN;

REVEAL 
  Edge = PublicEdge BRANDED
  OBJECT 
    no: EdgeNo := 0;                  (* Edge number *)

    marks: ARRAY [0..1] OF  MarkBit;  (* Used by Enum, enumvertices *)
    
    (* Element index [r] refers to arc a[r] = Arc{e,r}: *)
    orgno: ARRAY [0..3] OF VertexNo;  (* Face/vertex number for Org(a[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 := 0): Edge =    
  BEGIN 
    e.no := no;
    e.marks[0] := FALSE;
    e.marks[1] := FALSE;
            
    FOR i := 0 TO 3 DO e.enext[i] := e END;
    e.bnext[0] := 0;  e.orgno[0] := 3*no;
    e.bnext[1] := 6;  e.orgno[1] := 3*no + 2;
    e.bnext[2] := 4;  e.orgno[2] := 3*no + 1;
    e.bnext[3] := 2;  e.orgno[3] := 3*no + 2;
    RETURN e
  END OctInit;
  
PROCEDURE Make (no: EdgeNo := 0): Arc =
  BEGIN
    WITH 
      e = NEW(Edge).init(no)
    DO
      RETURN Arc{edge := e, bits := 0}
    END;
  END Make;
  
PROCEDURE SenseBit(a: Arc): SBit =
  BEGIN RETURN Word.RightShift(a.bits, 2) END SenseBit;

(* If a = flip^f(rot^r(e)), where e is the reference arc of edge,
   r in [0..3], and f in [0..1], then a.bits = (2r + f).
   Therefore,
   
     a.flip.bits = XOR(a.bits, 1)
     
     If fbit is 0
       a.rot.bits = (a.bits + 2) MOD 8 
     otherwise
       a.rot.bits = (a.bits + 6) MOD 8
*)

PROCEDURE FlipBit (a: Arc): FBit =
  BEGIN RETURN Word.And(a.bits, 1) END FlipBit;
  
PROCEDURE DualBit (a: Arc): DBit =
  BEGIN RETURN Word.And(Word.RightShift(a.bits, 1), 1) END DualBit;

PROCEDURE RotBits (a: Arc): RBits =
  BEGIN RETURN Word.And( Word.RightShift(a.bits, 1), 3) END RotBits;
  
PROCEDURE GetArcNo (a: Arc): ArcNo =
  BEGIN RETURN 8 * a.edge.no + a.bits END GetArcNo;

PROCEDURE GetEdgeNo(e: Edge): EdgeNo =
  BEGIN RETURN e.no END GetEdgeNo;
  
PROCEDURE SetEdgeNo(e: Edge; no: EdgeNo) =
  BEGIN e.no := no END SetEdgeNo;
  
PROCEDURE GetOrgNo (a: Arc): VertexNo =
  BEGIN RETURN a.edge.orgno[RotBits(a)] END GetOrgNo;
  
PROCEDURE SetOrgNo (a: Arc; no: VertexNo) =
  BEGIN a.edge.orgno[RotBits(a)] := no END SetOrgNo;

PROCEDURE Rot(a: Arc): Arc =
  BEGIN
    RETURN Arc{edge := a.edge, 
               bits := Word.And( a.bits + 2 + Word.LeftShift( 
               Word.And(a.bits, 1), 2), 7) };
  END Rot;

PROCEDURE Flip(a: Arc): Arc =
  BEGIN
    RETURN Arc{edge := a.edge, bits := Word.Xor( a.bits, 1 )};
  END Flip;
  
PROCEDURE Sym(a: Arc): Arc =
  BEGIN
    RETURN Arc{edge := a.edge, bits := Word.And( (a.bits + 4), 7 )};
  END Sym;
  
PROCEDURE Tor(a: Arc): Arc =
  BEGIN
    RETURN Arc{edge := a.edge,
               bits := Word.And( a.bits + 6 + Word.LeftShift( 
                       Word.And(a.bits, 1), 2), 7) };    
  END Tor;

PROCEDURE Onext(a: Arc): Arc =
  BEGIN
    WITH s = Word.And( Word.RightShift( (a.bits + 1), 1 ), 3 ) DO     
      WITH 
      r = a.edge.bnext[s] 
      DO
        a.edge := a.edge.enext[s];
        IF ( Word.And( a.bits, 1 ) = 1) THEN 
          a.bits := Word.Xor( Word.And( r + 2 + Word.LeftShift( 
                    Word.And(r, 1), 2), 7), 1) ;
        ELSE
          a.bits := r;
        END;
      END
    END;
    RETURN a;
  END Onext;

PROCEDURE Oprev(a: Arc): Arc =
  BEGIN RETURN Rot(Onext(Rot(a))) END Oprev;
  
  
PROCEDURE Dnext(a: Arc): Arc =
  BEGIN RETURN Sym(Onext(Sym(a)))  END Dnext;

PROCEDURE Dprev(a: Arc): Arc =
  BEGIN RETURN Tor(Onext(Tor(a)))  END Dprev;
  
PROCEDURE Lnext(a: Arc): Arc =
  BEGIN RETURN Rot(Onext(Tor(a)))  END Lnext;
  
PROCEDURE Lprev(a: Arc): Arc =
  BEGIN RETURN Sym(Onext(a))  END Lprev;
  
PROCEDURE Rnext(a: Arc): Arc =
  BEGIN RETURN Tor(Onext(Rot(a)))  END Rnext;

PROCEDURE Rprev(a: Arc): Arc =
  BEGIN RETURN Onext(Sym(a))  END Rprev;

<*UNUSED*>
PROCEDURE Debug() =
  BEGIN 
  END Debug;

PROCEDURE Splice (a, b: Arc) =
  BEGIN
  <* ASSERT b # Flip(Onext(a)) *>
  IF a # b THEN 
    WITH
      ta = Onext(a), tb = Onext(b),
      c = Rot(ta), d = Rot(tb), 
      tc = Onext(c), td = Onext(d)
    DO
      IF ( Word.And(a.bits, 1) = 0 ) THEN 
        WITH
          rba = RotBits(a)
        DO
          a.edge.enext[rba] := tb.edge;
          a.edge.bnext[rba] := tb.bits;
        END
      ELSE
        WITH
          ra = Rot(Flip(a)), fd = Flip(d), rbra = RotBits(ra)
        DO
          ra.edge.enext[rbra] := fd.edge;
          ra.edge.bnext[rbra] := fd.bits;
        END
      END;
        
      IF ( Word.And(b.bits, 1) = 0 ) THEN 
        WITH
          rbb = RotBits(b)
        DO
          b.edge.enext[rbb] := ta.edge;
          b.edge.bnext[rbb] := ta.bits;          
        END
      ELSE
        WITH
          rb = Rot(Flip(b)), fc = Flip(c), rbrb = RotBits(rb)            
        DO
          rb.edge.enext[rbrb] := fc.edge;
          rb.edge.bnext[rbrb] := fc.bits;
        END
      END;
      

      IF ( Word.And(c.bits, 1) = 0 ) THEN 
        WITH
          rbc = RotBits(c) 
        DO
          c.edge.enext[rbc] := td.edge;
          c.edge.bnext[rbc] := td.bits;
        END
      ELSE
        WITH
          rc = Rot(Flip(c)), fb = Flip(b), rbrc = RotBits(rc)
        DO
          rc.edge.enext[rbrc] := fb.edge;
          rc.edge.bnext[rbrc] := fb.bits;
        END          
      END;

      IF ( Word.And(d.bits, 1) = 0 ) THEN
      WITH
        rbd = RotBits(d)
      DO
        d.edge.enext[rbd] := tc.edge;
        d.edge.bnext[rbd] := tc.bits;          
      END
      ELSE
        WITH
          rd = Rot(Flip(d)), fa = Flip(a), rbrd = RotBits(rd) 
        DO
          rd.edge.enext[rbrd] := fa.edge;
          rd.edge.bnext[rbrd] := fa.bits;
        END
      END;
    END;
  END;  
  END Splice;

PROCEDURE SetOnext(a, b: Arc) =
  BEGIN
    IF Onext(a) # b THEN Splice(a, Oprev(b)) END
  END SetOnext;

PROCEDURE PrintArc (wr: Wr.T; a: Arc) =
  <* FATAL Wr.Failure, Thread.Alerted *>
  BEGIN
    Wr.PutText (wr, 
      Fmt.Int(a.edge.no) & ":" &
      Fmt.Int(RotBits(a)) & ":" &
      Fmt.Int(FlipBit(a))
    )
  END PrintArc;
  
PROCEDURE PrintEdge(wr: Wr.T; e: Edge) =
  <* FATAL Wr.Failure, Thread.Alerted *>
  BEGIN
    FOR i := 0 TO 3 DO 
      IF i > 0 THEN Wr.PutChar(wr, ' ') END;
      PrintArc(wr, Arc{edge := e.enext[i], bits := e.bnext[i]});
    END
  END PrintEdge;
  
PROCEDURE ReadEdge(rd: Rd.T; e: Edge; READONLY map: ARRAY OF Edge) =
  BEGIN
    FOR i := 0 TO 3 DO 
      SetOnext(Arc{edge := e, bits := 2 * i}, ReadArc(rd, map))
    END
  END ReadEdge;
  
BEGIN
END Oct.