/* See {raspol_slicer.h}. */
/* Last edited on 2016-04-21 20:32:46 by stolfilocal */

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

#include <bool.h>
#include <vec.h>
#include <affirm.h>
#include <binsearch_int32.h>
#include <group_sort_uint32.h>

#include <stpoly.h>

#include <raspol_stats.h>
#include <raspol_slicer.h>

/* INTERNAL PROTOTYPES */

void raspol_slicer_group_edges
  ( stpoly_t poly,
    uint32_t nl, 
    int32_t startY, 
    int32_t stepY, 
    stpoly_edge_t e[],   /* (OUT) edges, sorted by group. */
    uint32_t gstart[]    /* (OUT) beg and end of each group. */
  );   
  /* Fills {e[0..nf-1]} with all the edges of {poly},
    sorted by increasing slicing group.

    There are {ng = nl+1} slicing groups, numbered {0..ng-1} or {0..nl}.
    For {ig} in {1..nl-1}, group {ig} has every edge {s} that start
    between slicing lines {ig-1} and {ig}, that is, such that
    {startY + (ig-1)*stepY < e.minY < startY + ig*stepY}. Group 0 has 
    every edge {s} that starts below the first line ({s.minY < startY}) and
    group {nl} has all edges that start after the last line
    (startY + (nl-1)*stepY < s.minY}).
    
    Also sets {gstart[0..ng-1]} to indicate the beginning and end of
    each group in {e}. Namely, for any group {ig} in {0..ng-1}, the
    edges in group {ig} are {e[k0..k1-1]}, where
    {k0=gstart[ig]} and {k1=gstart[ig+1]}. Note that {gstart} must
    have {ng+1 = nl+2} elements.
    
    Assumes (requires) that the {Y} coordinates of every line is
    distinct from the {Y} coordinate of every vertex; so that  
    no vertex lies on a slicing line.  */

void raspol_slicer_edge_group_sort
  ( stpoly_t poly,
    uint32_t ng,        /* Number of groups. */
    uint32_t egroup[],  /* Group assigned to each edge. */
    stpoly_edge_t e[],  /* (OUT) edges sorted by group. */
    uint32_t gstart[]   /* (OUT) Beg and end of each group. */
  );
  /* Sorts the {ne} edges of {poly} into {ng} groups. 
    
    Assumes that the groups are identified by /group indices/ in {0..ng-1},
    and that each edge of {poly} with index {uxe} belongs to the group with index {egroup[uxe]}.
    It stores the edges into {e[0..ne-1]}, sorted by increasing group index. 
    
    The procedure also sets {gstart[0..ng]} to indicate the beginning and end of
    each group in {e}. Namely, for any group index {ig} in {0..ng-1}, the
    edges in group {ig} are {e[k0..k1-1]}, where
    {k0=gstart[ig]} and {k1=gstart[ig+1]}. Note that {gstart} must
    have {ng+1} elements, not {ng}. */
    
/* IMPLEMENTATIONS */

void raspol_slicer_slice
  ( stpoly_t poly,
    uint32_t nl, 
    int32_t startY, 
    int32_t stepY, 
    raspol_slice_proc_t proc
  )
  {
    uint32_t ne = stpoly_edge_count(poly);   /* Number of segments. */
    uint32_t ng = nl + 1;     /* Number of edge groups. */
    float eps = stpoly_get_eps(poly);
    bool_t verbose = TRUE;
    
    /* Sort the segments by slicing group: */
    stpoly_edge_t *e = notnull(malloc(ne*sizeof(stpoly_edge_t)), "no mem"); /* All edges, group-sorted */
    uint32_t *gstart = notnull(malloc((ng+1)*sizeof(uint32_t)), "no mem");  /* Start of each group in {e}. */
    raspol_slicer_group_edges(poly, nl, startY, stepY, e, gstart);    

    /* Sweep over the figure with a horizontal line: */
    stpoly_edge_t *a = notnull(malloc(ne*sizeof(stpoly_edge_t)), "no mem");  /* Active edges, group-sorted */
    uint32_t na = 0; /* Number of active EDGEs. */
    uint32_t ixl;
    for (ixl = 0; ixl < nl; ixl++)
      { /* Get the quantized Y-coordinate of next slicing line: */
        int32_t pY = startY + ixl*stepY;
        /* Get the corresponding group index {ig}: */
        uint32_t ig = ixl;
        /* Append to the active list all edges in group {ig}: */
        uint32_t na_plus = gstart[ig+1] - gstart[ig]; /* Number of edges in group. */
        uint32_t ke;
        for (ke = gstart[ig]; ke < gstart[ig+1]; ke++)
          { assert(na < ne);
            a[na] = e[ke];
            na++; 
          }
        /* Remove from the active list all segments that do not cross the line: */
        uint32_t na_new = 0; /* Edges that remain active: */
        uint32_t ja;
        for (ja = 0; ja < na; ja++)
          { /* Get the next active edge {e}: */
            stpoly_edge_t aj = a[ja];
            int32_t minY, maxY;
            stpoly_edge_get_yrange(aj, &minY, &maxY);
            assert(minY < pY);
            if (maxY > pY)
              { /* Still active, keep it: */
                a[na_new] = aj;
                na_new++; 
              }
            else
              { /* Became inactive, skip it: */
                assert(maxY < pY); /* No vertices on slicing lines. */
              }
          }
        uint32_t na_minus = na_new - na; /* Number of inactivated edges. */
        na = na_new;
        if (verbose) 
          { fprintf(stderr, "  line %4u at Y = %+11d (%+.8f mm): %u edges", ixl, pY, pY*(double)eps, na_new);
            fprintf(stderr, " (added %d removed %d)\n", na_plus, na_minus);
          }
        proc(pY, na, a);
      }
      
    /* Free storage:*/
    free(e);
    free(gstart);
    free(a);
  }

void raspol_slicer_group_edges
  ( stpoly_t poly,
    uint32_t nl, 
    int32_t startY, 
    int32_t stepY, 
    stpoly_edge_t e[],   /* (OUT) edges, sorted by group. */
    uint32_t gstart[]    /* (OUT) beg and end of each group. */
  )   
  {
    uint32_t ne = stpoly_edge_count(poly);   /* Number of triangles. */
    uint32_t ng = nl + 1;     /* Number of groups. */
    bool_t verbose = TRUE;
    
    /* Get quantized {Y} coordinates {bY,eY} of first and last lines: */
    int32_t bY = startY;
    int32_t eY = startY  + (nl-1)*stepY;
    if (verbose) { fprintf(stderr, "grouping unsorted edges for %u slicing lines in %+d..%+d\n", nl, bY, eY); }
    demand(eY >= bY, "invalid line {Y} coordinates");

    /* Get quantized step {dY} of {Y} coordinate between lines, or 0 if not uniform: */
    int32_t dY = stepY;
    
    /* Assigns group index {egroup[uxe]} to each edge with index {uxe}: */
    uint32_t *egroup = notnull(malloc(ne*sizeof(uint32_t)), "no mem"); /* Group of each EDGE. */
    uint32_t uxe;
    for (uxe = 0; uxe < ne; uxe++)
      { /* Get the edge record and its {.minY} coordinate {fY}: */
        stpoly_edge_t ek = stpoly_get_edge(poly, uxe);
        int32_t eminY, emaxY;
        stpoly_edge_get_yrange(ek, &eminY, &emaxY);

        /* Compute the group index {ig}: */
        uint32_t ig;
        if (eminY < bY)
          { ig = 0; }
        else if (eminY > eY)
          { ig = nl; }
        else
          { ig = (eminY - bY)/dY + 1;
            demand((ig >= 1) && (eminY > startY + (ig-1)*stepY), "bug: vertex on lower slicing line");
            demand((ig < nl) && (eminY < startY + ig*stepY), "bug: vertex on upper slicing line");
          }
        assert(ig < ng);
        
        /* Save and count it: */
        egroup[uxe] = ig;
      }
      
    /* Put in {e[0..nE-1]} the EDGE indices, sorted by group, and set {gstart[0..ng]}: */
    raspol_slicer_edge_group_sort(poly, ng, egroup, e, gstart);

    free(egroup);
  }
  
void raspol_slicer_edge_group_sort
  ( stpoly_t poly,
    uint32_t ng,        /* Number of groups. */
    uint32_t egroup[],  /* Group assigned to each edge. */
    stpoly_edge_t e[],  /* (OUT) edges sorted by group. */
    uint32_t gstart[]   /* (OUT) Beg and end of each group. */
  )
  {
    uint32_t ne = stpoly_edge_count(poly);   /* Number of triangles. */
    
    /* Sort the EDGE indices by group: */
    stpoly_edge_unx_t *uxe = notnull(malloc(ne*sizeof(stpoly_edge_unx_t)), "no mem");
    group_sort_uint32(ne, ng, egroup, uxe, gstart);
    
    /* Pick the EDGEs in that order: */
    uint32_t k;
    for (k = 0; k < ne; k++) { e[k] = stpoly_get_edge(poly, uxe[k]); }

    /* Paranoia check: */
    assert(gstart[ng] == ne);
    
    free(uxe);
  }