/* See frb_segment.h. */
/* Last edited on 2005-01-16 14:20:38 by stolfi */
/* Copyright © 2005 Universidade Estadual de Campinas. See note at end of file. */

#include <frb_segment.h>
#include <frb_types.h>
#include <frb_proc.h>

#include <fget.h>
#include <nget.h>
#include <filefmt.h>
#include <js.h>
#include <stdio.h>

bool frb_segment_is_empty (frb_segment_t *s)
  { return s->ns == 0; }

int frb_segment_abs_index (int iRel, frb_segment_t *s)
  { if (s->rev)
      { return s->ini + s->ns - 1 - iRel; }
    else
      { return s->ini + iRel; }
  }

int frb_segment_rel_index (int iAbs, frb_segment_t *s)
  { if (s->rev)
      { return s->ini + s->ns - 1 - iAbs; }
    else
      { return iAbs - s->ini; }
  }

int frb_segment_abs_index_clip (int iRel, frb_segment_t *s)
  { affirm(iRel <= s->ns, "bad iRel");
    if (s->rev)
      { return frb_imod(s->ini + s->ns - 1 - iRel, s->tot); }
    else
      { return frb_imod(iRel + s->ini, s->tot); }
  }

int frb_segment_rel_index_clip (int iAbs, frb_segment_t *s)
  { int j = frb_imod(iAbs - s->ini, s->tot);
    if (j < s->ns)
      { if (s->rev)
          { return s->ns - 1 - j; }
        else
          { return j; }
      }
    else
      { return (s->ns - 1); }
  }

frb_segment_t frb_segment_complement (frb_segment_t *s)
  { affirm(s->ns > 0, "bad ns");
    affirm(s->ns <= s->tot + 1, "bad ns");
    int newIni = frb_imod(s->ini + s->ns - 1, s->tot);
    int newLen = s->tot - s->ns + 2;
    return (frb_segment_t){
      /*cvx*/ s->cvx,
      /*tot*/ s->tot,
      /*ini*/ newIni,
      /*ns*/  newLen,
      /*rev*/ s->rev
    };
  }

frb_segment_t frb_segment_expand (frb_segment_t *s, int iniEx, int finEx)
  { int askedLen = s->ns + iniEx + finEx;
    int newLen = frb_imax(1, frb_imin(askedLen, s->tot + 1));
    int excessSteps = askedLen - newLen;
    int newIni = frb_imod(s->ini - iniEx +  excessSteps / 2, s->tot);
    return (frb_segment_t){
      /*cvx*/ s->cvx,
      /*tot*/ s->tot,
      /*ini*/ newIni,
      /*ns*/  newLen,
      /*rev*/ s->rev
    };
  }

int frb_segment_overlap (frb_segment_t *a, frb_segment_t *b)
{ if ((a->cvx != b->cvx) || (a->rev != b->rev))
      { return 0; }
    else
      { affirm(a->tot == b->tot, "inconsistent segs");
      if ((a->ns >= a->tot) || (b->ns >= b->tot))
          { return frb_imin(a->ns, b->ns); }
        else if (a->ini == b->ini)
          { return frb_imin(a->ns, b->ns); }
        else
          { int m = a->tot;
            int dab = frb_imod(b->ini - a->ini, m);
            int nab = frb_imin(a->ns - dab, b->ns);
            int dba = frb_imod(a->ini - b->ini, m);
            int nba = frb_imin(b->ns - dba, a->ns);
            return frb_imax(0, frb_imax(nba, nab));
          }
      }
  }

frb_segment_t frb_segment_meet (frb_segment_t *a, frb_segment_t *b)
  {
    int ini, ns;
    if ((a->cvx != b->cvx) || (a->rev != b->rev))
      { return frb_segment_empty; }
    else
      { affirm(a->tot == b->tot, "incosistent segs");
        if ((a->ns == 0) || (b->ns == 0))
          { return frb_segment_empty; }
        else if (a->ns >= a->tot + 1)
          { return *b; }
        else if (b->ns >= b->tot + 1)
          { return *a; }

        int m = a->tot;
        int dab = frb_imod(b->ini - a->ini, m);
        int dba = frb_imod(a->ini - b->ini, m);

        if (dab == 0)
          { /* Both segments start together */
            ini = frb_imod(a->ini, m); ns = frb_imin(a->ns, b->ns);
          }
        else if ((dab < a->ns) && (dba < b->ns))
          { /* Each segment starts inside the other; wrap-around! */
            return frb_segment_empty;
          }
        else if (dab < a->ns)
          { /* {b} starts inside {a} */
            ini = frb_imod(b->ini, m); ns = frb_imin(a->ns - dab, b->ns);
          }
        else if (dba < b->ns)
          { /* {a} starts inside {b} */
            ini = frb_imod(a->ini, m); ns = frb_imin(a->ns, b->ns - dba);
          }
        else
          { /* Disjoint */
            return frb_segment_empty;
          }
        return (frb_segment_t){/*cvx*/ a->cvx, /*tot*/ m, /*ini*/ ini, /*ns*/ ns, /*rev*/ a->rev};
      }
  }

frb_segment_t frb_segment_join (frb_segment_t *a, frb_segment_t *b)
  {
    frb_segment_t res;
    affirm(a->cvx == b->cvx, "bad segs");
    affirm(a->rev == b->rev, "bad segs");
    affirm(a->tot == b->tot, "inconsistent segs");
    res.cvx = a->cvx; res.tot = a->tot; res.rev = a->rev;

    int m = a->tot;
    int dab = frb_imod(b->ini - a->ini, m);
    int dba = m - dab;
    bool tab = dab < a->ns; /* Segment {a} runs into segment {b} */
    bool tba = dba < b->ns; /* Segment {b} runs into segment {a} */

    if ((tab && tba) || (a->ns > a->tot) || (b->ns > b->tot))
      { /* The two segments cover the whole curve: */
        res.ini = 0; res.ns = a->tot+1;
      }
    else
      { if (tab)
          { /* Segment {a} runs over {b} but there is a gap from {b} to {a}: */
            res.ini = a->ini; res.ns = frb_imax(a->ns, dab + b->ns);
          }
        else if (tba)
          { /* Segment {b} runs over {a} but there is a gap from {a} to {b}: */
            res.ini = b->ini; res.ns = frb_imax(b->ns, dba + a->ns);
          }
        else
          { /* The segments don't overlap; join through the smallest gap: */
            if (dab - a->ns <= dba - b->ns)
              { res.ini = a->ini; res.ns = dab + b->ns; }
            else
              { res.ini = b->ini; res.ns = dba + a->ns; }
          }
        affirm(res.ns <= m, "bug");
      }
    return res;
  }

#define frb_segment_OldFileVersion "97-04-05"
#define frb_segment_NewFileVersion "99-07-25"

void frb_segment_write_one (FILE *wr, frb_segment_t *s)
  { fprintf(wr, "%5d %5d %6d %5d %c", 
      s->cvx, s->tot, s->ini, s->ns, (s->rev ? '-' : '+')
    );
  }

void frb_segment_write (FILE *wr, char *cmt, frb_segment_vec_t *s)
  {
    int i;
    filefmt_write_header(wr, "frb_segment_vec_t", frb_segment_NewFileVersion);
    filefmt_write_comment(wr, cmt, '|');
    fprintf(wr, "segments = %d\n", s->nel);
    for (i = 0; i < s->nel; i++)
      { frb_segment_write_one(wr, &(s->el[i]));
        fprintf(wr, "\n");
      }
    filefmt_write_footer(wr, "frb_segment_vec_t");
    fflush(wr);
  }

frb_segment_t frb_segment_read_one (FILE *rd)
  {
    frb_segment_t s; 
    s.cvx = fget_int(rd); fget_skip_spaces(rd);
    s.tot = fget_int(rd); fget_skip_spaces(rd);
    s.ini = fget_int(rd); fget_skip_spaces(rd);
    s.ns = fget_int(rd); fget_skip_spaces(rd);

    int c = fgetc(rd);
    if (c == '-')
      { s.rev = TRUE; }
    else if (c == '+')
      { s.rev = FALSE; }
    else
      { fprintf(stderr, "Invalid segment direction\n");
        affirm(FALSE, "bad format");
      }
    return s;
  }

frb_segment_read_data_t  frb_segment_read (FILE *rd)
  { frb_segment_read_data_t d;
    filefmt_read_header(rd, "frb_segment_vec_t", frb_segment_NewFileVersion);
    d.cmt = filefmt_read_comment(rd, '|');

    int n = nget_int(rd, "segments"); fget_eol(rd);
    d.s = frb_segment_vec_new(n);
    int i;
    for (i = 0; i < n; i++)
      { fget_skip_spaces(rd);
        d.s.el[i] = frb_segment_read_one(rd);
        fget_eol(rd);
      }
    filefmt_read_footer(rd, "frb_segment_vec_t");
    return d;
  }

frb_segment_vec_t frb_segment_vec_new(nat nel)
  { /* This is not a macro only because gcc does not allow cast of struct: */
    vec_t v = vec_new(nel, sizeof(frb_segment_t));
    frb_segment_vec_t r;
    r.nel = v.nel; r.el = (frb_segment_t*)v.el;
    return r;
  }

frb_segment_read_data_t frb_segment_read_old (FILE *rd, int_vec_t *m)
  {
    frb_segment_read_data_t d;
    filefmt_read_header(rd, "frb_segment_vec_t", frb_segment_OldFileVersion);
    d.cmt = filefmt_read_comment(rd, '|');

    int n = nget_int(rd, "segments"); fget_eol(rd);
    int i;
    d.s = frb_segment_vec_new(n);
    for (i = 0; i <= n-1 ; i++)
      {
        fget_skip_spaces(rd);

        frb_segment_t *si = &(d.s.el[i]);

        si->cvx = fget_int(rd); fget_skip_spaces(rd);
        si->tot = m->el[si->cvx];
        si->ini = fget_int(rd); fget_skip_spaces(rd);

        int fin = fget_int(rd); fget_skip_spaces(rd);
        si->ns = frb_imod(fin - si->ini, si->tot) + 1;
        fget_eol(rd);
        si->rev = FALSE;
      }
    filefmt_read_footer(rd, "frb_segment_vec_t");
    return d;
  }

bool_vec_t frb_segment_curves_used (frb_segment_vec_t *s)
  { /* Find number of elements to allocate: */
    int max_cvx = 0;
    int i, k;
    for (i = 0; i < s->nel; i++)
      { max_cvx = frb_imax(max_cvx, s->el[i].cvx); }

    /* Mark used curves: */
    bool_vec_t used = bool_vec_new(max_cvx + 1);
    for (k = 0; k < used.nel; k++) { used.el[k] = FALSE; }
    for (i = 0; i < s->nel; i++) 
      { used.el[s->el[i].cvx] = TRUE; }
    return used;
  }

void frb_segment_print (FILE *wr, frb_segment_t *s)
  {
    double fm = ((double)s->tot);
    double pci = ((double)s->ini) / fm;
    int fin = frb_imod(s->ini + s->ns - 1, s->tot);
    double pcj = ((double)fin) / fm;
    
    fprintf(wr, "curve %4d - %6d samples in %6d", s->cvx, s->ns, s->tot);
    fprintf(wr, " %04d(%5.3f) .. %04d(%5.3f) ", s->ini, pci, fin, pcj);
    fprintf(wr, "%c", (s->rev ? '-' : '+'));
  }


/* COPYRIGHT AND AUTHORSHIP NOTICE

  Copyright © 2005 Universidade Estadual de Campinas (UNICAMP).
  Created by Helena C. G. Leitão and Jorge Stolfi in 1995--2005.
  
  This source file can be freely distributed, used, and modified,
  provided that this copyright and authorship notice is preserved in
  all copies, and that any modified versions of this file are clearly
  marked as such.
  
  This software has NO WARRANTY of correctness or applicability for
  any purpose. Neither the authors nor their employers shall be held
  responsible for any losses or damages that may result from its use.

  END OF NOTICE */