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

/* Last edited on 2007-01-28 04:14:33 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 OctfRep_C_copyright \
  "Copyright ©  1998, 2007 Universidade Estadual de Campinas (UNICAMP)"

#define INIT_QUEUE_SIZE 1024

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

/* 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.nel) && (! stop); i++)
      { EnumWedgesOfOne(PWedge(root.el[i])); }

    /* We are done: */
    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.el[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.el[wn] != w))
          { /* First visit to wedge {w}: */
            stop = visit(WedgeBase(w));
            /* Add it to the visited wedge set: */
            wn = nW; nW++; 
            Wedge_vec_expand(&W, wn);
            W.el[wn] = w;
            /* Set the wedge's {num} field to its index in {pw}: */
            w->num = wn;
          }
      }

  }

#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\n" \
  "jan/2007 by J.Stolfi, who rewrote {EnumWedges}" \
  "and unified it with {RenumberWedges}."