/* See {Octf.h} */
#include <Octf.h>

/* Last edited on 2007-01-25 10:02:01 by stolfi */

#include <OctfRep.h>

#include <fget.h>
#include <affirm.h>

#define _GNU_SOURCE
#include <stdio.h>
#include <assert.h>

#define Octf_C_copyright \
  "Copyright © 1998 Universidade Estadual de Campinas (UNICAMP)"

#define INIT_STACK_SIZE 1024

void EnumWedges(Place_t p, VisitProc visit, bool_t wedges)
  { Place_vec_t stack = Place_vec_new(INIT_STACK_SIZE);
    uint top = 0;
    uint seen = 0; /*!=of @{quad->?}s whose childeren were looked at */

    auto void VisitAndMark(Place_t c);
      /* If wedge(c) is unmarked: visit, mark, and stack it. */

    void VisitAndMark(Place_t c)
      { Wedge_t w = PWedge(c);
        if (! w->marks2[DualBit(c)]) 
          { visit(c); /* [!!! Should we allow for early termination? !!!] */
            if (! wedges) { visit(Clock(c));};
            Place_vec_expand(&stack,top);
            w->marks2[DualBit(c)] = TRUE; 
            stack.el[top] = c; top++;
          }
      }

    assert(! PWedge(p)->marks2[DualBit(p)]); 
    /* Enumerate all wedges: */
    VisitAndMark(p);
    while (seen < top)
      { Place_t b = stack.el[seen];
        VisitAndMark(PrevF(b));
        VisitAndMark(PrevE(b));
        VisitAndMark(NextE(b));
        VisitAndMark(NextF(PrevE(b)));        
        seen++;
      }
    /* Erase all marks */
    while (top > 0)
      { top--;
        Place_t b = stack.el[top];
        PWedge(b)->marks2[DualBit(b)] = FALSE;
      }
  }

uint DegreeOfWall(Place_t p)
  { uint n = 0;
    Place_t s = p;
    do { n++; s = NextF(s); } while (s != p);
    return n;
  }

uint DegreeOfEdge(Place_t p)
  { uint n = 0;
    Place_t s = p;
    do { n++; s = NextE(s); } while (s != p);
    return n;
  }

void SetEdgeInfo(Place_t p, EdgeWallInfo_t n)
  { PWedge(p)->edge = n; }

void SetWallInfo(Place_t p, EdgeWallInfo_t n)
  { PWedge(p)->wall = n; }

void SetRingWallInfo(Place_t p, EdgeWallInfo_t n)
  { Place_t t = p;
    do { SetWallInfo(t,n); t = NextE(t); } while (t != p);
  }

void SetRingEdgeInfo(Place_t p, EdgeWallInfo_t n)
  { Place_t t = p;
    do { SetEdgeInfo(t,n);  t = NextF(t); } while (t != p);
  }

OBit_t OrientationBit(Place_t p)
  { return (PBits(p) >> 2); }

SBit_t SpinBit(Place_t p)
  { return (PBits(p) & 1u); }
  
DBit_t DualBit(Place_t p)
  { return ((PBits(p) >> 1) & 1u); }

RBits_t SrotBits(Place_t p)
  { return ((PBits(p) >> 1) & 3u); }

Place_t Dual(Place_t p)
  { return Spin(Srot(p)); }

Place_t Srot(Place_t p)
  { return PlaceInWedge(PWedge(p), (PBits(p) + 2u + ((PBits(p) ^ 1u) << 2)) & 7u); }

Place_t Spin(Place_t p)
  { return PlaceInWedge(PWedge(p), PBits(p) ^ 1u); }
  
Place_t Clock(Place_t p)
  { return PlaceInWedge(PWedge(p), (PBits(p) + 4u) & 7u); }
  
Place_t Tors(Place_t p)
  { return PlaceInWedge(PWedge(p), (PBits(p) + 6u + ((PBits(p) ^ 1u) << 2)) & 7u); }

Place_t NextF(Place_t p)
  { SBit_t sbit = SpinBit(p);
    /* If {p} is spinned, must compute Spin(Clock(NextF(Clock(p)))): */
    if (sbit) { p = Clock(p); }
    /* Now {SpinBit(p)} is 0, get {NextF} from stored pointers: */
    RBits_t rbits = SrotBits(p);
    p = PWedge(p)->next[rbits];
    /* Fix result if {p} was spinned: */
    if (sbit) { p = Spin(Clock(p)); }
    return p;
  }

Place_t NextE(Place_t p)
  { return Srot(NextF(Tors(p))); }

Place_t PrevE(Place_t p)
  { return Clock(Srot(NextF(Srot(p)))); }

Place_t PrevF(Place_t p)
  { return Clock(NextF(Clock(p))); }

Place_t NextEk(Place_t p, int k)
  { if (k > 0)
      { do { p = NextE(p); k--; } while (k > 0); }
    else if (k < 0)
      { do { p = PrevE(p); k++; } while (k < 0); }
    return p;
  }

Place_t NextFk(Place_t p, int k)
  { if (k > 0)
      { do { p = NextF(p); k--; } while (k > 0); }
    else if (k < 0)
      { do { p = PrevF(p); k++; } while (k < 0); }
    return p;
  }

void SpliceWalls(Place_t a, Place_t b)
  { assert(b != Spin(NextF(a)));
    if (a!=b) 
      {
        Place_t ta = NextF(a),  tb = NextF(b);
        Place_t  c = Clock(ta),  d = Clock(tb); 
        Place_t tc = NextF(c),  td = NextF(d);

        if (SpinBit(a) == 0)
          { PWedge(a)->next[SrotBits(a)] = tb; }
        else
          { PWedge(a)->next[SrotBits(Clock(Spin(a)))] = Spin(d); }

        if (SpinBit(b) == 0)
          { PWedge(b)->next[SrotBits(b)] = ta; }
        else
          { PWedge(b)->next[SrotBits(Clock(Spin(b)))] = Spin(c); }

        if (SpinBit(c) == 0)
          { PWedge(c)->next[SrotBits(c)] = td; }
        else
          { PWedge(c)->next[SrotBits(Clock(Spin(c)))] = Spin(b); }

        if (SpinBit(d) == 0)
          { PWedge(d)->next[SrotBits(d)] = tc; }
        else
          { PWedge(d)->next[SrotBits(Clock(Spin(d)))] = Spin(a); }
     }  
  }

void SpliceEdges(Place_t a, Place_t b)
  { SpliceWalls(Dual(a), Dual(b)); }
 
void Meld(Place_t a, Place_t b)
  { Place_t p = a, q = b;
    do 
    {
      Place_t pp = PrevF(p);
      if (NextF(p)!=q) { SpliceWalls(p, PrevF(q)); assert(NextF(p) == q); } 
      DeleteWedge(p);
      if (SpinBit(pp) == SpinBit(q)){ assert(NextF(pp) == q); }
      p = NextE(p);
      q = NextE(q);
    } while (p != a);
  }

Place_t Onext(Place_t s)
  { return (DualBit(s)== 0 ? Clock(NextF(PrevE(s))) : PrevE(s)); }  

Place_t Oprev(Place_t s)
  { /* [!!! Comment in Octf.h was : 
      If DualBit(s) == 0, then return Clock(PrevF(PrevE(s)))  else return PrevE(s) */
    /* [!!! Comment in Octh.c was : equivalent to Onext but change NextF by PrevF */ 
    return Clock(PrevF(PrevE(s)));
  }

void WedgeInit(Wedge_t w)
  { w->marks2[0] = FALSE;
    w->marks2[1] = FALSE;
    /* Place_t p = PlaceInWedge(w, 0); */
    w->edge = NULL; /* [!!! WAS: MakeEdge(); w->edge->pa = p; !!!] */
    w->wall = NULL; /* [!!! WAS: MakeWall(); w->wall->pa = p; !!!] */
    /* Connect to itself: */
    w->next[0] = PlaceInWedge(w, 0);
    w->next[1] = PlaceInWedge(w, 2);
    w->next[2] = PlaceInWedge(w, 4);
    w->next[3] = PlaceInWedge(w, 6);
    /* Fields from {TriangulationWedgeRec_t}: */
    w->org[0] = NULL; /* For now, node of primal: C  */
    w->org[1] = NULL; /* For now, node of dual:   C' */
    w->org[2] = NULL; /* For now, node of primal: C  */
    w->org[3] = NULL; /* For now, node of dual:   C' */
  }

Place_t MakeWedge(void)   
  { Wedge_t w = (Wedge_t)notnull(malloc(sizeof(WedgeRec_t)), "no mem");
    WedgeInit(w);
    return PlaceInWedge(w, 0);
  }

void DeleteWedge (Place_t p)
  { SpliceWalls(p, PrevF(p));
    SpliceWalls(Clock(p), PrevF(Clock(p))); 
    free(PWedge(p));
  }

PlaceNum_t GetPlaceNum_t(Place_t p)
  { return (PWedge(p)->num << 3) | PBits(p); }

Place_vec_t RenumberWedges(Place_vec_t *pv)
  { Place_vec_t pstack = Place_vec_new(INIT_STACK_SIZE);
    uint nstack = 0;
    uint seen = 0; /* Number of wedges whose childeren were looked at */

    /* A wedge {n} is "marked" if PWedge(pstack.el[n.num]) == n. i.e whether stacked */

    auto void VisitAndMark(Place_t t);
      /* If {t} is unmarked: visit, mark, and stack it. */

    void VisitAndMark(Place_t t)
      { Wedge_t w = PWedge(t);
        if ((w->num < nstack) && (PWedge(pstack.el[w->num]) == w))
          { /* wedge is already marked, do nothing. */ }
        else
          { Place_vec_expand(&pstack,nstack);
            w->num = nstack;
            pstack.el[nstack] = t;
            nstack++;
          }
      }

    /* Enumerate wedges: */
    int i;
    for (i = 0; i < pv->nel; i++) { VisitAndMark(pv->el[i]); } 
    while (seen < nstack)
      { Place_t s = pstack.el[seen]; 
        VisitAndMark(PrevF(s));
        VisitAndMark(PrevE(s));
        VisitAndMark(NextE(s));
        VisitAndMark(NextF(PrevE(s)));
        seen++;
      }
    /* Trim and return the {pstack}: */
    Place_vec_trim(&pstack,nstack);
    return pstack;
  }

void SetNextF(Place_t a, Place_t b)
  { if (NextF(a) != b) { SpliceWalls(a, PrevF(b)); } }

void SetNextE(Place_t a, Place_t b)
  { if (NextE(a) != b){ SpliceEdges(a, PrevE(b)); } }

void PrintPlace(FILE *wr, Place_t p, uint feWidth, bool_t nl /* DF FALSE */)
  { fprintf(wr, "%*u:%u:%u%s", feWidth, PWedge(p)->num, SpinBit(p), SrotBits(p), (nl ? "\n" : "")); }

Place_t ReadPlace(FILE *rd, Wedge_vec_t *map)
  { int m = fget_int(rd); assert((m >= 0) && (m < map->nel));
    fget_match(rd, ":");
    int s = fget_int(rd); assert((s >= 0) && (s < 2));
    fget_match(rd, ":");
    int r = fget_int(rd); assert((r >= 0) && (r < 4));
    return PlaceInWedge(map->el[m], 2*r + s);
  }

void PrintWedge(FILE *wr, Wedge_t w, uint feWidth /* DF 1 */)
  { int i;
    for (i = 0; i < 4; i++)
      { if (i > 0){ fputc(' ', wr); }
        PrintPlace(wr, w->next[i], feWidth, FALSE);
      }
  }
  
void ReadWedge(FILE *rd, Wedge_t w, Wedge_vec_t *map)
  { int i;
    for (i = 0; i < 4; i++)
      { SetNextF(PlaceInWedge(w, 2*i), ReadPlace(rd, map)); }
  }

#define Octf_C_author \
  "The Modula-3 version of this source file was created in 1998" \
  "by Luis Arturo Perez Lozada, UNICAMP, inspired on the " \
  "Modula-3 implementation of the quad-edge data structure by " \
  "J.Stolfi and R.M.Rosi (ca. 1994). " \
  "It was converted to C and substantially revised in jan/2007 by J.Stolfi."