INTERFACE PZLR3Chain;

IMPORT LR3, LR4x4, Rd, Wr;
IMPORT PZIntChain, PZLRChain, PZMatch, PZFourierChain;

TYPE
  LONG = LONGREAL;
  T = ARRAY OF LR3.T;
  CostMatrix = PZMatch.CostMatrix;

PROCEDURE FromIntChain(READONLY c: PZIntChain.T): REF T;
  (*
    Converts "c" to floating point, adding the third coordinate "Z=0". *)

PROCEDURE ToIntChain(READONLY c: T): REF PZIntChain.T;
  (*
   Converts "c" to integer format, ignoring the "Z" coodinate
   and rounding "X" and "Y" to the nearest INTEGER. *)
   
PROCEDURE FromSegment(READONLY p, q: LR3.T; n: CARDINAL): REF T;
  (*
    Creates a chain with "n" points equally spaced
    along the segment "seg". *)

PROCEDURE Trim(READONLY c: T; start, length: CARDINAL): REF T;
  (*
    Returns a new chain that is a copy of elements from "c[start]"
    to "c[start+length-1]".  Assumes the chain is periodic, i.e.
    "c[i+n]=c[i]" for all "i", where "n=NUMBER(c)". *)
    
PROCEDURE Reverse(VAR c: T); 
  (*
    Reverses the direction of traversal of the Chain "c". *)
  
PROCEDURE Map(READONLY c: T; READONLY m: LR4x4.T): REF T;
  (*
    Maps "c" by the given projective transformation. *)
    
(* CHAINS AS CLOSED POLYGONS *)

(* 
  The procedures in this section interpret the chain "p" as the
  vertices of a closed polygonal curve with "m = NUMBER(p)" sides.  It
  is assumed that each edge is traversed at constant speed, in such a
  way that the chain reaches vertex "p[i]" at time "t[i]", for "i IN
  [0..m-1]"; and the curve goes back to vertex "p[0]" at time "t[0] + tPeriod". *)
    
PROCEDURE LinearLengths(
    READONLY p: T;              (* "p[i]" is curve position at time "t[i]". *) 
    VAR s: PZLRChain.T;         (* "s[j]" is the length from "p[0] to "p[j] "j". *) 
  ): LONG;
  (*
    Computes the Euclidean length "s[j]" on the polygonal from
    vertex "p[0]" to vertex "p[j]", for "j" in "[0..LAST(p)]".
    Returns the total length of the polygonal as the result of the call. *)
    

PROCEDURE LinearUniformSample(
    READONLY t: PZLRChain.T;    (* Times of input samples. *) 
    tPeriod: LONG;              (* Time period *)
    READONLY p: T;              (* "p[i]" is curve position at time "t[i]". *) 
    tStart: LONG;               (* Time of first output sample *)
    VAR q: T;                   (* "q[j]" will be position sample number "j". *) 
  );
  (*
    Computes "n" samples along the curve, equally spaced in time, starting
    with time "tStart".  The samples are returned in "q[j]", "j IN [0..n-1]". *)

PROCEDURE LinearEquidistantSample(
    READONLY p: T;              (* "p[i]" is curve position at time "t[i]". *) 
    tStart: LONG;               (* Time of first output sample *)
    VAR q: T;                   (* "q[j]" will be position sample number "j". *) 
  );
  (*
    Same as "LinearUniformSample", assuming that the curve is traversed
    with constant velocity in unit time. *)

PROCEDURE LinearTimeSample(
    READONLY t: PZLRChain.T;    (* Times OF input samples. *) 
    tPeriod: LONG;              (* Time period *)
    READONLY p: T;              (* Input curve positions at times "t[i]". *)
    READONLY r: PZLRChain.T;    (* Times OF output samples. *)
    VAR q: T;                   (* Output curve positions at times "r[j]". *) 
  );
  (*
    Computes the positions "q[j]" at the specified times "tq[j]",
    "j IN [0..n-1]". *)
   
(* CHAINS AS CLOSED C_1 CUBIC SPLINES *)

(* 
  The procedures in this section interpret the chains "p" and "dp" as the
  positions and velocities of a closed spline curve with "m = NUMBER(p)" 
  cubic arcs, at the nodal times "t[0..m-1]".  It is assumed the curve 
  goes back to vertex "p[0]" and velocity "dp[0]" at time "t[0] + tPeriod". *)

 
PROCEDURE HermiteUniformSample(
    READONLY t: PZLRChain.T;    (* Times of input samples. *) 
    tPeriod: LONG;              (* Time period *)
    READONLY p: T;              (* "p[i]" is curve position at time "t[i]". *)
    READONLY dp: T;             (* "dp[i]" is velocity at time "t[i]". *)
    tStart: LONG;               (* Time of first output sample *)
    VAR q: T;                   (* "q[j]" will be position sample number "j". *) 
    VAR dq: T;                  (* "dq[j]" will be velocity at point "q[j]". *) 
  );
  (*
    Computes "n" samples "q[0..n-1]" along the curve, and their velocities "dq[0..n-1]",
    equally spaced in time, starting with time "tStart". *)

PROCEDURE HermiteEquidistantSample(
    READONLY p: T;              (* "p[i]" is curve position at time "t[i]". *) 
    tStart: LONG;               (* Time of first output sample *)
    VAR q: T;                   (* "q[j]" will be position sample number "j". *) 
    VAR dq: T;                  (* "dq[j]" will be velocity at point "q[j]". *) 
  );
  (*
    Same as "HermiteUniformSample", assuming that the curve is traversed
    with constant velocity in the total time "tPeriod". *)

PROCEDURE HermiteTimeSample(
    READONLY t: PZLRChain.T;    (* Times of input samples. *) 
    tPeriod: LONG;              (* Time period *)
    READONLY p: T;              (* "p[i]" is curve position at time "t[i]". *)
    READONLY dp: T;             (* "dp[i]" is velocity at time "t[i]". *)
    READONLY r: PZLRChain.T;    (* Times of output samples. *)
    VAR q: T;                   (* "q[j]" will be curve position at time "r[j]". *) 
    VAR dq: T;                  (* "dq[j]" will be velocity at time "r[j]". *) 
  );  
  (*
    Computes the positions "q[j]" and velocities "dq[j]" at the specified 
    times "r[j]", "j IN [0..n-1]". *)

PROCEDURE EstimateVelocities(
    READONLY t: PZLRChain.T;
    tPeriod: LONG;
    READONLY p: T;
    VAR dp: T;
    est: VelEstimator;
  );
  (*
    Estimates the velocity "dp[i]" at each point "p[i]",
    by applying the estimator "est" to three consecutive times. *)
    
TYPE
  VelEstimator = PROCEDURE (
      a: LONG; READONLY pa: LR3.T; 
      b: LONG; READONLY pb: LR3.T; 
      c: LONG; READONLY pc: LR3.T;
    ): LR3.T;


TYPE
  ReadData = RECORD 
      cmt: TEXT;      (* Comment text *)
      c: REF T;       (* The samples *)
      unit: LONG;     (* Unit that was used when writing the data *)
    END;

PROCEDURE Read(rd: Rd.T): ReadData;
  (*
    Reads a chain (and its comments) from "rd" *)
 
PROCEDURE Write(wr: Wr.T; READONLY cmt: TEXT;  READONLY c: T; unit: LONG);  
  (*
    Writes chain "c" to "wr", prefixed with comments "cmt".
    The coordinates will be written as integer multiples of the given "unit". *)

PROCEDURE ReadAll(
    puzzle: TEXT; 
    band: CARDINAL;
    extension: TEXT;
    READONLY sel: ARRAY OF BOOLEAN;
  ): REF ARRAY OF ReadData;
  (*
    Returns a vector "r" such that "r[k]" is the ReadData
    for curve "k", if "sel[k] = TRUE".  
    Otherwise "r[k]" is an empty data record.
    
    The data is read from file "KKKK/NNN-KKKK-fBBBEEE",
    where "NNN" is the "puzzle" name, "KKKK" is the 
    curve number "k" (4 digits, zero padded),
    "BBB" is the "band" number (3 digits, zero padded),
    and "EEE" is the given "extension". *)

PROCEDURE Match(
    READONLY a: T;
    READONLY b: T;
    maxDist: LONGREAL;
    removeUnmatchedEnds: BOOLEAN;
    VAR (*OUT*) avgDist: LONGREAL;
    VAR (*OUT*) lengthMatched: LONGREAL; 
    VAR (*OUT*) match: REF PZMatch.T;
  ); 
  (*
    Computes (by dynamic programming) a minimum-distance monotone
    matching "match" between two curves "a" and "b".  
    
    Each segment of one curve is matched either to one segment or to a
    single vertex of the opposite chain.  Specifically, the
    vertex "a[match[k][0]]" is paired with vertex "b[match[k][1]]",
    for all "k"; and "match[k]" increases by either 0 or 1 in each
    coordinate.
    
    Two consecutive pairs "match[k]" and "match[k+1]" are
    called a ``step'' of the matching; it consists of either
    two segments, one on each curve, or a point of one curve 
    and a segment of the other curve.  The length of the step,
    by definition, is the average of the lengths of the two segments.
    
    The mean width of a step is the the root mean square distance "mw"
    between two points, each traversing the respective segments
    simultaneously at constant speed.  The average distance "avgDist"
    between the two chains is then the root mean square of the step
    widths, weighted by the respective step lengths.
    
    However, the width "mw" of each step is clipped so as not
    to exceed "maxDist".  Thus, "maxDist" can be interpreted as the
    cost of leaving two segments of unit length completely unmatched.
    
    The procedure returns in "lengthMatched" the total length of the 
    steps whose mean width was strictly less than "maxDist". *)
    
PROCEDURE OutMatch(
    READONLY a: T;
    READONLY b: T;
    loc: LONGREAL;
    align: LONGREAL;
    maxShift: LONGREAL;
    maxDist: LONGREAL;
    cutDist: LONGREAL; 
    step: LONGREAL;
    minChainEdges: CARDINAL;
    VAR (*OUT*) mismatch: LONGREAL;
    VAR (*OUT*) nMatched: CARDINAL; 
    VAR (*OUT*) match: REF PZMatch.T;
    VAR (*OUT*) xCenter, yCenter: CARDINAL;
    VAR (*OUT*) minAvgDist: REF ARRAY OF LONGREAL;
    VAR (*WORK*) XYCost: REF CostMatrix;
  ); 
  (*
    Finds (by bidirectional dynamic programming) a minimum-mismatch
    monotone matching "match" between the polygonal chains "a" and "b".
    The chains are assumed to have edges of equal length "step".
    
    Each segment of one chain is matched either to one segment or to a
    single vertex of the opposite chain.  Specifically, the
    vertex "a[match[k][0]]" is paired with vertex "b[match[k][1]]",
    for all "k"; and "match[k]" increases by either 0 or 1 in each
    coordinate.
    
    We will denote by "totChainEdges" the total number of edges in
    the matched portion of the two chains, that is
      "(match[m-1][0]-match[0][0]) + (match[m-1][1]-match[0][1])".
    
    The match will include exactly one `central' pair
    "match[kc]=(ia,ib)" with "ia+ib = ROUND(loc)".  The difference
    "ia-ib", called the `alignment' of the match, will be
    approximately "align"; the "maxShift" parameter specifies the
    maximum amount by which the two quantities are allowed to differ.
    (The procedure will fail if "loc" and "align" are outside the
    obvious bounds).
    
    Two consecutive pairs "match[k]" and "match[k+1]" are called a
    ``step'' of the matching.  A step consists of either two segments,
    one on each curve, or a point of one curve and a segment of the
    other curve.
    
    The "length" of the step, by definition, is the average of the
    lengths of the two edges: namely, "step" for an edge-edge match,
    and "step/2" for an edge-vertex match.  The "width" of the step is the root
    mean square value of "|a(t) - b(t)|^2", where "a(t)" and "b(t)"
    interpolate linearly along the respective edges of the step.
    (For these definitions, a vertex is assumed to be a
    zero-length edge.)
    
    The squared cost "costSqr" of a step is its "length" times the
    "width" squared.
    
    In any case, the "width" is clipped to a maximum of "maxDist".
    Thus, "maxDist" can be interpreted as the distance beyond which
    two segments are considered to be completely unmatched.
    
    The `mismatch' of a match is defined as 
      "intgCostSqr - totLength*cutDist^2"
    where "intgCostSqr" is the sum of all squared step costs (each
    clipped as explained above); and "totLength" is the total length
    of those steps (that is, "totChainEdges*step/2").  However, if
    "totChainEdges" is less than "minChainEdges", the mismatch is "+oo" by
    definition.
    
    The procedure also returns in "nMatched" the number of steps whose
    width is strictly less than "maxDist".
    
    The procedure also returns in "minAvgDist[k]", for "k" in
    "[0..na+nb-2]", the root mean square step width, over all
    matches with "totChainEdges = k".
    
    The parameters "xCenter", "yCenter", and "XYCost"
    are as in "PZMatch.OutMatch".
  *)
    
PROCEDURE FourierTransform(READONLY c: T; VAR f: PZFourierChain.T);
  (*
    Computes the Fourier spectrum "f" of curve "c". 
    Their lengths must be equal and a power of two. *)
  
PROCEDURE InvFourierTransform(VAR f : PZFourierChain.T; VAR c : T);  
  (*
    Computes a curve "c" given its Fourier spectrum "f".
    Their lengths must be equal and a power of two.
    WARNING: destroys "f" in the process. *)
    
END PZLR3Chain.