INTERFACE PZLRChain;

(* Chains of float values: used for times, lengths, curvatures, etc. *)

IMPORT Rd, Wr;
IMPORT PZMatch;

TYPE 
  LONG = LONGREAL;
  T = ARRAY OF LONG;

PROCEDURE Write(wr: Wr.T; READONLY cmt: TEXT; READONLY c: T; stride: LONG; unit: LONG);
  (*
    Writes chain "c" to "wr", prefixed with comment "cmt" and the given "stride".
    The samples will be written as integer multiples of the given "unit". *)

TYPE
  ReadData = RECORD 
      cmt: TEXT;     (* Comments *)
      c: REF T;      (* Times, values, etc. *)
      stride: LONG;  (* Period, total length, etc; 0 if not applicable. *)
      unit: LONG;    (* Unit used when recording the samples *)
    END; 
 
PROCEDURE Read(rd: Rd.T): ReadData;
  (*
    Reads a chain from "rd". *)

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 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 ReverseAndComplement(VAR c: T);
  (*
    Reverses the chain back-to-front and negates all elements. *)

PROCEDURE MatchGraphs(
    READONLY a: T;
    READONLY b: T;
    maxDist: LONG;
    removeUnmatchedEnds: BOOLEAN;
    VAR (*OUT*) avgCost: LONG;
    VAR (*OUT*) nMatched: CARDINAL; 
    VAR (*OUT*) match: REF PZMatch.T;
  ); 
  (*
    Finds (by dynamic programming) a minimum-cost monotone matching
    "match" between the chains "a" and "b".
    
    The chains are interpreted as graphs of curvature (or some other
    attribute of a curve) as a function of some common parameter,
    sampled at equally spaced steps.
    
    Each step of one graph is matched either to one step or to a
    single sample of the opposite chain.  Specifically, the sample
    "a[match[k][0]]" is paired with sample "b[match[k][1]]", for all
    "k"; and "match[k]" increases by either 0 or 1 in each coordinate.
    
    The cost of matching a step to a single sample is "maxDist/2",
    irrespective of the corresponding sample values.  The cost
    of matching two steps is the root mean square value of 
    "a(t)-b(t)", where "a(t)" and "b(t)" interpolate linearly between
    the two corresponding samples; except that the cost is 
    clipped to a maximum of "maxDist" in any case.  The average
    cost "avgCost" of the matching is then the root mean square of those
    individual step costs.
    
    The procedure returns in "nMatched" the number of steps whose
    cost is strictly less than its maximum cost. *)
    
(* INTEGRAL-PERIODIC FUNCTIONS *)

(*
  The procedures in this section interpret a chain "c" as 
  a continuous function "c(x)" that is the integral of some 
  non-negative periodic function "f(x)" with period "m = NUMBER(c)".
  
  Specifically, the procedures assume that 
    
    (1) "c[i]" is the integral of "f(x)" from an arbitrary
        parameter "x = x0" to parameter "x = i"; 

    (2) "stride" is the integral of "f(x)" over a whole period, 
        so that "c(x + m) = f(x) + stride", for any "x"; and

    (3) "f(x)" is linear between successive integer values of 
        the argument "x".
*)

PROCEDURE Delta(READONLY c: T; stride: LONG; ini, fin: INTEGER): LONG;
  (*
    Returns "c(fin) - c(ini)", where the chain "c" is implicitly extended
    as explained above. *)

PROCEDURE ValueFromArg(READONLY c: T; stride: LONG; x: LONG): LONG; 
  (*
    Returns "c(x)"; that is, a value "y" such that
    "c[floor(x)] <= y <= c[ceiling(x)]", interpolating linearly
    between these two points.  The chain "c" is implicitly 
    extended as explained above. *)

PROCEDURE ArgFromValue(READONLY c: T; stride: LONG; y: LONG): LONG; 
  (* 
    Returns a fractional argument "x" such that "c(x) = y";
    that is, such that "c[floor(x)] <= y <= c[ceiling(x)]",
    with linear interpolation between these two points.
    The chain "c" is implicitly extended as explained above. *)
    
PROCEDURE ValuesFromArgs(
    READONLY c: T; 
    stride: LONG; 
    READONLY x: ARRAY OF LONG;
    VAR y: ARRAY OF LONG;
  );
  (*
    Sets "y[i] := ValueFromArg(c, stride, x[i])" for all "i". *)

PROCEDURE ArgsFromValues(
    READONLY c: T; 
    stride: LONG; 
    READONLY y: ARRAY OF LONG;
    VAR x: ARRAY OF LONG;
  ); 
  (* 
    Sets "x[i]" to "ArgFromValue(c, stride, y[i])" for every i,
    but faster if "y" is sorted. *)
    
PROCEDURE ValueFromValue(
    READONLY a: T; aStride: LONG; 
    READONLY b: T; bStride: LONG; 
    ya: LONG;
  ): LONG; 
  (*
    Finds the value "yb" of function "b(x)" for an argument "x" such that
    the function "a(x)" has value "ya". The chains "a" and "b" 
    are implicitly extended as explained above. *)

PROCEDURE ArgFromArg(
    READONLY a: T; aStride: LONG; 
    READONLY b: T; bStride: LONG;
    xa: LONG;
  ): LONG; 
  (*
    Finds an argument "xb" such that "b(xb) = a(xa)", where
    "xa" is given. The chains "a" and "b" are implicitly extended as 
    explained above. *)

END PZLRChain.