#ifndef pz_double_chain_match_H
#define pz_double_chain_match_H

/* Matching two {pz_double_chain_t}s by dynamic programming. */
/* Last edited on 2015-01-20 16:49:03 by stolfilocal */

#include <pz_double_chain.h>
#include <pz_match.h>
#include <pz_segment.h>
#include <pz_candidate.h>
#include <pz_types.h>
#include <r2.h>

/*
  The procedures {pz_double_chain_match_find_best} and
  {pz_double_chain_match_refine} look for a monotone pairing {mt} (a
  {pz_match_t}) between two curves that minimizes some measure of the
  distance between corresponding samples.

  See {pz_mismatch} for the relevant concepts.  These procedures assume
  that the two curves are sampled at uniform intervals of given size
  {step}.  Therefore, the metric {h(a,i1,i2)} is assumed to be
  {step*(i2-i1)}.  The sample distance {d(a[r], b[s])} is simply the
  absolute difference {|a[r]-b[s]|}.

  The procedures return in {length} the total length {Len(mt)} of the
  pairing (average of the lengths of the two curve segments spanned
  by {mt}).  They also return in {lengthMatched} the total length of
  the pairing steps whose mean width {dist(S)} was strictly less than
  {maxDist}.

  The procedures use internally a working array with {(a.ne)} rows
  and {(b.ne)} columns.  The client may optionally provide an array
  {rCost}, at least this big, which will be automatically (re)
  allocated if omitted or too small. */

void pz_double_chain_match_find_best(
    pz_double_chain_t *a,
    pz_double_chain_t *b,
    double step,
    double maxDistSqr,
    double skipDistSqr,
    bool_t removeUnmatchedEnds,
    pz_match_t *mt, /* (OUT) */
    double *avgDisc, /* (OUT) */
    double *length, /* (OUT) */
    double *matchedLength,  /* (OUT) */
    pz_match_cost_matrix_t *rCost /* (WORK) */
  );
  /*
    Computes (by dynamic programming) a complete monotone pairing
    {mt} between two open curves {a} and {b} that minimizes their
    integrated squared dicrepancy {IntgDiscSqr(mt)}.

    The procedure returns in {avgDisc} the average discrepancy
    (in the root mean square sense).

    If {removeUnmatchedEnds} is true, the procedure removes any
    initial or final steps {s} whose distance {dist(s)} is equal to
    {maxDist}.  Otherwise the pairing {mt} will completely cover the
    two curves. */

void pz_double_chain_match_refine(
    pz_double_chain_t *a,
    pz_double_chain_t *b,
    double step,
    pz_match_t *mtOld,
    unsigned maxAdjust,
    double critDistSqr,
    double maxDistSqr,
    double skipDistSqr,
    pz_match_t *mt,  /* (OUT) */
    double *mismatch, /* (OUT) */
    double *length, /* (OUT) */
    double *matchedLength,  /* (OUT) */
    double_vec_t *minAvgDist, /* (OUT) */
    pz_match_cost_matrix_t *rCost /* (WORK) */
  );
  /*
    Finds (by bidirectional dynamic programming) a partial monotone
    pairing {mt} between the polygonal curves {a} and {b}, that is
    a refinement of an `input pairing' {mtOld}, and minimizes
    the mismatch {Mis(mt)}.

    See {pz_match_refine} for an explanation of the refinement concept,
    and the meaning of {mtOld} and {maxAdjust}.  See {PZPairing.i3}
    for the definition of the mismatch {Mis(mt)} and the meaning of
    the parameters {critDistSqr} and {maxDistSqr}.

    The value of {Mis(mt)} is returned in {mismatch}.

    The procedure returns in {minAvgDist[K]}, for {K} in
    {[0..na+nb-2]}, the average width {Dist(mtK)} of the optimum match
    {mtK} among all matches with total step count {K}.  (Note that, if
    the step count is fixed, the {critDist} term does not affect the
    optimality of the match.)  */

pz_match_t *pz_double_chain_map_match(
    pz_match_t *mOld,
    pz_segment_pair *sOld,
    pz_double_chain_t *t0Old,
    pz_double_chain_t *t1Old,
    pz_segment_pair *sNew,
    pz_double_chain_t *t0New,
    pz_double_chain_t *t1New,
    r2_t stride
  );
  /*
    Translates a partial pairing {mOld}, that defines a
    correspondence between two curves {cOld[0]}, {cOld[1]}, to a
    pairing {mNew} between new versions {cNew[0]} and {cNew[1]} of
    those two curves.

    The input pairing is assumed to be relative to segments {sOld[j]}
    of curve {cOld[j]}, for {j==0,1}.  The new pairing will be
    relative to the segments {sNew[j]}, and trimmed to fit inside
    them.

    Whenever a step of {mOld} skips several samples of the new curve,
    extra steps are inserted, by linear interpolation rounded to
    integers. */

pz_match_packed_t *pz_double_chain_map_packed_match(
    pz_match_packed_t *pm,
    pz_segment_pair *sOld,
    pz_double_chain_t *t0Old,
    pz_double_chain_t *t1Old,
    pz_segment_pair *sNew,
    pz_double_chain_t *t0New,
    pz_double_chain_t *t1New,
    r2_t stride
  );
  /*
    If {pm} is NULL, returns NULL; otherwise is equivalent
    to {pz_double_chain_map_match}, in packed format. */

/*
  Copyright © 2001 Universidade Estadual de Campinas (UNICAMP).
  Authors: Helena C. G. Leitão and Jorge Stolfi.

  This file can be freely distributed, used, and modified, provided
  that this copyright and authorship notice is preserved, and that any
  modified versions are clearly marked as such.

  This software has NO WARRANTY of correctness or applicability for
  any purpose. Neither the authors nor their employers chall be held
  responsible for any losses or damages that may result from its use.
*/
#endif