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

/* Last edited on 2023-02-12 07:47:23 by stolfi */

#include <Octf.h>
#include <OctfRep.h>

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

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

#define PBITSMASK  ((uintptr_t)7u)
#define PWEDGEMASK (~ PBITSMASK)

Place_t PlaceInWedge(Wedge_t w, SRBits_t srb)
  { return (Place_t)(((uintptr_t)w) | ((uintptr_t)srb)); }

Place_t WedgeBase(Wedge_t w)
  { return (Place_t)w; }

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);
  }

Wedge_t PWedge(Place_t p)
  { return (Wedge_t)(((uintptr_t)p) & PWEDGEMASK); }

SRBits_t PBits(Place_t p)
  { return (SRBits_t)(((uintptr_t)p) & PBITSMASK); }

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 Flip(Place_t p, uint i)
  { switch(i)
      { case 0: return Flip0(p);
        case 1: return Flip1(p);
        case 2: return Flip2(p);
        case 3: return Flip3(p);
        default: demand(FALSE, "bad element dimension"); return NULL;
      }
  }

Place_t Flip0(Place_t p)
  { return PlaceInWedge(PWedge(p), (PBits(p) ^ 5u) & 7u); }

Place_t Flip1(Place_t p)
  { return Flip0(PrevE(p)); }

Place_t Flip2(Place_t p)
  { return Flip3(PrevF(p)); }

Place_t Flip3(Place_t p)
  { return PlaceInWedge(PWedge(p), PBits(p) ^ 1u); }

Place_t FlipIJ(Place_t p, uint i, uint j)
  { return Flip(Flip(p, i), j); }
  
/* [!!! The following implementations need to be optimized !!!] */

Place_t Flip03(Place_t p)
  { return Flip3(Flip0(p)); }

Place_t Flip30(Place_t p) 
  { return Flip0(Flip3(p)); }

Place_t Flip32(Place_t p)
  { return Flip2(Flip3(p)); }

Place_t Flip23(Place_t p)
  { return Flip3(Flip2(p)); }

Place_t Flip01(Place_t p)
  { return Flip1(Flip0(p)); }

Place_t Flip10(Place_t p)
  { return Flip0(Flip1(p)); }

Place_t Flip02(Place_t p)
  { return Flip2(Flip0(p)); }

Place_t Flip20(Place_t p)
  { return Flip0(Flip2(p)); }

Place_t Flip31(Place_t p)
  { return Flip1(Flip3(p)); }

Place_t Flip13(Place_t p)
  { return Flip3(Flip1(p)); }

Place_t Flip21(Place_t p)
  { return Flip1(Flip2(p)); }

Place_t Flip12(Place_t p)
  { return Flip2(Flip1(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 SymVF(Place_t p)
  { return Flip0(Flip2(p)); }

Place_t SymEC(Place_t p)
  { return Flip3(Flip1(p)); }

Place_t ONext(Place_t p)
  { /* [!!! Was: {(DualBit(p)== 0 ? Clock(NextF(PrevE(p))) : PrevE(p))} !!!] */
    return Clock(PrevE(PrevF(p)));
  }  

Place_t OPrev(Place_t p)
  { /* [!!! Comment in Octf.h was : 
      If DualBit(p) == 0, then return Clock(PrevF(PrevE(p)))  else return PrevE(p) */
    /* [!!! Comment in Octh.c was : equivalent to ONext but change NextF by PrevF */ 
    return Clock(PrevF(PrevE(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);
  }

void WedgeInit(Wedge_t w)
  { /* 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' */
  }

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

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); }

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_int32(rd); assert((m >= 0) && (m < map->ne));
    fget_match(rd, ":");
    int s = fget_int32(rd); assert((s >= 0) && (s < 2));
    fget_match(rd, ":");
    int r = fget_int32(rd); assert((r >= 0) && (r < 4));
    return PlaceInWedge(map->e[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 INIT_QUEUE_SIZE 1024

/* ENUMERATING WEDGES */

Wedge_vec_t EnumWedges(Place_vec_t root, VisitFunc_t visit)
  { 
    int nW = 0;
    Wedge_vec_t W = Wedge_vec_new(INIT_QUEUE_SIZE);
      /* The wedges visited so far are {W[0..nW-1]}. */

    auto void VisitMarkAndStack(Wedge_t w);
      /* If {w} is unvisited, visits it, marks it as visited,
        appends it to the queue {W[0..nW-1]}. */
    
    bool_t stop = FALSE;

    auto void EnumWedgesOfOne(Wedge_t w);
      /* Enumerates all unvisited wedges that can be reached from
        {w} by zero or more {next} links, and
        appends those wedges to {W[0..nW-1]}. */
    
    /* Enumerate all roots: */
    int i;
    for (i = 0; (i < root.ne) && (! stop); i++)
      { EnumWedgesOfOne(PWedge(root.e[i])); }

    /* We are done: */
    Wedge_vec_trim(&W, nW);
    return W;

    void EnumWedgesOfOne(Wedge_t w)
      { /* Save the queue's state: */
        int nS = nW; /* Links of wedges {W[nS..nW-1]} still need following. */
        VisitMarkAndStack(w);
        while ((nS < nW) && (! stop))
          { /* Get a visited wedge {u}, follow its links: */
            Wedge_t u = W.e[nS]; nS++;
            int r;
            for (r = 0; r < 4; r++)
              { w = PWedge(u->next[r]);
                VisitMarkAndStack(w);
              }
          }
      }
             
    void VisitMarkAndStack(Wedge_t w)
      { uint wn = w->num;
        if ((wn >= nW) || (W.e[wn] != w))
          { /* First visit to wedge {w}: */
            stop = (visit == NULL ? FALSE : visit(WedgeBase(w)));
            /* Add it to the visited wedge set: */
            wn = nW; nW++; 
            Wedge_vec_expand(&W, wn);
            W.e[wn] = w;
            /* Set the wedge's {num} field to its index in {pw}: */
            w->num = wn;
          }
      }
  }
  
vec_typeimpl(Wedge_vec_t,Wedge_vec,Wedge_t);

vec_typeimpl(Node_vec_t,Node_vec,Node_t);
vec_typeimpl(Edge_vec_t,Edge_vec,Edge_t);
vec_typeimpl(Wall_vec_t,Wall_vec,Wall_t);
vec_typeimpl(Cell_vec_t,Cell_vec,Cell_t);

#define OctfRep_C_copyright \
  "Copyright ©  1998, 2007 Universidade Estadual de Campinas (UNICAMP)"

#define OctfRep_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\n" \
  "jan/2007 by J.Stolfi.\n" \
  "Some chanegs:\n" \
  "  2007-01-24  Rewrote {EnumWedges}, unified with {RenumberWedges}."