MODULE PZGetRandomCands EXPORTS Main;

(* Generate random candidates from a set of contours. *)
(* Last edited on 1999-09-01 14:09:43 by hcgl *)

(*
  Reads a bunch of encoded curvature chains, and generates
  a set of random candidates from them.

  Each candidate will consist of two segments of approximately
  the same length, on two distinct contours, the second one being
  implicitly reversed.

  The candidates will avoid a specified list of segments.
  Ordinarily this list includes the external borders of the
  objects ("straight" segments) and preferably also the
  corners, if known.

  IMPORTANT: These segments must have been expanded by the corner
  blurring factor appropriate for the current filtering scale.
  Check the parameters of "PZMapSegs".
*)

IMPORT ParseParams, Process, FileRd, FileWr, Wr, Random;
IMPORT OSError, Thread, Text, Stdio, Fmt;
IMPORT PZSymbolChain, PZSymbol, PZCandidate, PZSegment;

FROM Stdio IMPORT stderr;
FROM PZTypes IMPORT LONG, NAT, BOOL, BOOLS;

<* FATAL Wr.Failure, Thread.Alerted, OSError.E *>

TYPE
  Options = RECORD
      chainDir: TEXT;        (* Directory where to find chain data. *)
      chainPrefix: TEXT;     (* Invariant chain file name prefix. *)
      nCurves: NAT;          (* Number of curves. *)
      output: TEXT;          (* Output candidate file name. *)
      band: NAT;             (* Filtering "band" (wavelength parameter). *)
      step: LONG;            (* Sampling step. *)
      borderSegs: TEXT;      (* Filename of border segments, or "". *)
      cornerSegs: TEXT;      (* Filename of corner segments, or "". *)
      nCands: NAT;           (* Number of candidates to generate *)
      minLength: LONG;       (* Min length of matched segments. *)
      maxLength: LONG;       (* Max length of matched segments. *)
      blurFactor: LONG;      (* Corner broadening factor. *)
      printCands: NAT;       (* Max candidates to print. *)
    END;

TYPE
  Segments = PZSegment.List;
  Candidates = PZCandidate.List;

  Chains = ARRAY OF PZSymbolChain.ReadData;
  ChainPair = ARRAY [0..1] OF PZSymbolChain.ReadData;
  ChainIndexPair = ARRAY [0..1] OF NAT;

PROCEDURE Main() =
  BEGIN
    WITH
      o = GetOptions(),
      band = o.band,
      lambda = FLOAT(band, LONG),
      blurAmount = o.blurFactor * lambda,
      minCandLength = EnsurePositive(o.minLength - 2.0d0 * blurAmount),
      maxCandLength = EnsurePositive(o.maxLength - 2.0d0 * blurAmount),
      ch = ReadAllCVCFiles(o.chainDir, o.chainPrefix, o.nCurves, band)^,
      borderSegs = ReadExcludedSegsFile(o.borderSegs)^,
      cornerSegs = ReadExcludedSegsFile(o.cornerSegs)^,
      cand = GenerateRandomCandidates(
        ch,
        step := o.step,
        borderSegs := borderSegs,
        cornerSegs := cornerSegs,
        minCandLength := minCandLength,
        maxCandLength := maxCandLength,
        nCands := o.nCands
      )^
    DO
      WITH wr = FileWr.Open(o.output & ".can") DO
        PZCandidate.Write(wr, CandComment(o), cand, lambda)
      END;
      PrintCandidates(cand, o.printCands);
    END;
  END Main;

PROCEDURE EnsurePositive(candLength: LONG): LONG =
  BEGIN
    IF candLength < 0.0d0 THEN
      Wr.PutText(stderr, "warning: requested candidate length too small for this scale\n");
      Wr.Flush(stderr);
      Process.Exit(1);
    END;
    RETURN MAX(0.0d0, candLength)
  END EnsurePositive;

PROCEDURE GetOptions(): Options =
  VAR o: Options;
  BEGIN
    WITH
      pp = NEW(ParseParams.T).init(stderr)
    DO
      TRY
        pp.getKeyword("-chainPrefix");
        o.chainPrefix := pp.getNext();

        IF pp.keywordPresent("-chainDir") THEN
          o.chainDir := pp.getNext()
        ELSE
          o.chainDir := "."
        END;

        pp.getKeyword("-nCurves");
        o.nCurves := pp.getNextInt();

        pp.getKeyword("-band");
        o.band := pp.getNextInt();

        pp.getKeyword("-step");
        o.step := pp.getNextLongReal(0.0d0);

        pp.getKeyword("-output");
        o.output := pp.getNext();

        pp.getKeyword("-minLength");
        o.minLength := pp.getNextLongReal(0.0d0);

        pp.getKeyword("-maxLength");
        o.maxLength := pp.getNextLongReal(o.minLength);

        pp.getKeyword("-blurFactor");
        o.blurFactor := pp.getNextLongReal(0.0d0);

        IF pp.keywordPresent("-borderSegs") THEN
          o.borderSegs := pp.getNext()
        ELSE
          o.borderSegs := ""
        END;

        IF pp.keywordPresent("-cornerSegs") THEN
          o.cornerSegs := pp.getNext()
        ELSE
          o.cornerSegs := ""
        END;

        IF pp.keywordPresent("-nCands") THEN
          o.nCands := pp.getNextInt(1)
        ELSE
          o.nCands := LAST(NAT)
        END;

        IF pp.keywordPresent("-printCands") THEN
          o.printCands := pp.getNextInt(1)
        ELSE
          o.printCands := 1000
        END;

        pp.finish();
      EXCEPT
      | ParseParams.Error =>
          Wr.PutText(stderr, "Usage: PZGetRandomCands \\\n");
          Wr.PutText(stderr, "  -chainPrefix NAME [ -chainDir DIR ] \\\n");
          Wr.PutText(stderr, "  -nCurves NUMBER \\\n");
          Wr.PutText(stderr, "  -band NUMBER -step NUMBER \\\n");
          Wr.PutText(stderr, "  [ -borderSegs FILE ] [ -cornerSegs FILE ] \\\n");
          Wr.PutText(stderr, "  -output NAME \\\n");
          Wr.PutText(stderr, "  -minLength NUMBER  -maxlength NUMBER \\\n");
          Wr.PutText(stderr, "  -blurFactor NUMBER \\\n");
          Wr.PutText(stderr, "  [ -nCands NUMBER ] \\\n");
          Wr.PutText(stderr, "  [ -printCands NUMBER ]\n");
        Process.Exit(1);
      END;
    END;
    RETURN o
  END GetOptions;

PROCEDURE GenerateRandomCandidates(
    READONLY ch : Chains;
    READONLY step: LONG;           (* Sampling step. *)
    READONLY borderSegs: Segments; (* List of border segments, to exclude. *)
    READONLY cornerSegs: Segments; (* List of corner segments, to exclude. *)
    minCandLength: LONG;           (* Min length of candidate. *)
    maxCandLength: LONG;           (* Max length of candidate. *)
    nCands: NAT;                   (* Number of candidates desired. *)
  ): REF Candidates =
  BEGIN
    WITH
      rnd = NEW(Random.Default).init(fixed := TRUE),
      rc = NEW(REF Candidates, nCands), c = rc^
    DO
      FOR i := 0 TO nCands-1 DO
        c[i] := PickCandidate(
          rnd, ch,
          step := step,
          borderSegs := borderSegs,
          cornerSegs := cornerSegs,
          minCandLength := minCandLength,
          maxCandLength := maxCandLength
        )
      END;
      PZCandidate.Sort(c, PZCandidate.LexicallyBetter);
      RETURN rc
    END
  END GenerateRandomCandidates;

CONST NoCandidate = PZCandidate.Empty;

PROCEDURE PickCandidate(
    rnd: Random.T;
    READONLY ch: Chains;
    step: LONG;
    READONLY borderSegs: Segments; (* List of border segments, to exclude. *)
    READONLY cornerSegs: Segments; (* List of corner segments, to exclude. *)
    minCandLength: LONG;           (* Min length of candidate. *)
    maxCandLength: LONG;           (* Max length of candidate. *)
  ): PZCandidate.T =
  CONST
    MaxAttempts = 100;
  VAR
    nSteps: ARRAY [0..1] OF NAT;
    attempts: NAT := 0;
  BEGIN
    Wr.PutText(stderr, "?");
    WHILE attempts < MaxAttempts DO
      WITH
        cvxPair = RandomCurvePair(rnd, ch),
        chainPair = ChainPair{
          ch[cvxPair[0]],
          ch[cvxPair[1]]
        },
        candLength = rnd.longreal(minCandLength, maxCandLength)
      DO
        FOR j := 0 TO 1 DO
          nSteps[j] := FLOOR(candLength / step)
        END;
        WITH
          cand = PickCandidateInCurvePair(
            rnd, cvxPair, chainPair,
            step := step,
            borderSegs := borderSegs,
            cornerSegs := cornerSegs,
            nSteps := nSteps
          )
        DO
          IF cand.length > 0.0d0 THEN
            Wr.PutText(stderr, "\n");
            RETURN cand
          END
        END
      END;
    END;
    Wr.PutText(stderr, "failed to find a candidate in " & Fmt.Int(attempts) & " attempts\n");
    <* ASSERT FALSE *>
  END PickCandidate;

PROCEDURE PickCandidateInCurvePair(
    rnd: Random.T;
    READONLY cvxPair: ChainIndexPair;
    READONLY chainPair: ChainPair;
    step: LONG;
    READONLY borderSegs: Segments;   (* List of border segments, to exclude. *)
    READONLY cornerSegs: Segments; (* List of corner segments, to exclude. *)
    nSteps: ARRAY [0..1] OF NAT;
  ): PZCandidate.T =
  VAR seg: PZSegment.Pair;
      segLength: ARRAY [0..1] OF LONG;
  BEGIN
    FOR j := 0 TO 1 DO
      (* Pick a random segment in each curve, fail if it is excluded: *)
      WITH
        c = chainPair[j].c^,
        m = NUMBER(c),
        s = PZSegment.T{
          cvx := cvxPair[j],
          tot := m,
          ini := rnd.integer(0, m-1),
          ns := nSteps[j] + 1,
          rev := (j = 1)
        }
      DO
        IF s.ns > s.tot DIV 3
        OR SegmentIsExcluded(s, borderSegs)
        OR SegmentIsExcluded(s, cornerSegs)
        THEN
          Wr.PutText(stderr, "-");
          RETURN NoCandidate
        END;
        seg[j] := s;
        segLength[j] := FLOAT(s.ns - 1, LONG) * step
      END;
    END;
    (* Succeeded - return the candidate *)
    Wr.PutText(stderr, "+");
    WITH
      avgDistSqr = AverageDistSqr(chainPair[0].c^, seg[0], chainPair[1].c^, seg[1]),
      length = 0.5d0 * (segLength[0] + segLength[1])
    DO
      RETURN PZCandidate.T {
        seg := seg,
        mismatch := avgDistSqr,
        length := length,
        matched := length,
        pm := NIL
      }
    END
  END PickCandidateInCurvePair;

PROCEDURE RandomCurvePair(rnd: Random.T; READONLY ch: Chains): ChainIndexPair =
  VAR k0, k1: NAT;
  BEGIN
    WITH
      nChains = NUMBER(ch)
    DO
      REPEAT
        k0 := rnd.integer(0, nChains-1);
        k1 := rnd.integer(0, nChains-2);
        IF k1 >= k0 THEN INC(k1) END;
      UNTIL ch[k0].samples > 0 AND ch[k1].samples > 0;
      IF k0 > k1 THEN VAR t := k0; BEGIN k0 := k1; k1 := t END END;
      RETURN ChainIndexPair{k0, k1}
    END
  END RandomCurvePair;

PROCEDURE AverageDistSqr(
    READONLY a: PZSymbolChain.T;
    READONLY sa: PZSegment.T;
    READONLY b: PZSymbolChain.T;
    READONLY sb: PZSegment.T;
  ): LONG =
  (*
    Computes the average distance squared between segments "sa" and "sb"
    of the chains "a" and "b", by the trapezoid rule.  Assumes the most
    perfect match possible (Bresenham's path in the matching grid). *)
  VAR sum: LONG := 0.0d0;
      h: LONG;
  BEGIN
    WITH
      nPairs = MAX(sa.ns, sb.ns),
      fp = FLOAT(nPairs-1, LONG),

      ca = PZSymbolChain.ExtractSegment(a, sa)^,
      fa = FLOAT(sa.ns-1, LONG),

      cb = PZSymbolChain.ExtractSegment(b, sb)^,
      fb = FLOAT(sb.ns-1, LONG)
    DO
      FOR k := 0 TO nPairs-1 DO
        IF k = 0 OR k = nPairs-1 THEN h := 0.5d0 ELSE h := 1.0d0 END;
        WITH
          fk = FLOAT(k, LONG),
          ia = ROUND(fk*fa/fp),
          ib = ROUND(fk*fb/fp)
        DO
          sum := sum + h*PZSymbol.DistSqr(ca[ia], cb[ib], FALSE)
        END
      END;
      RETURN sum/fp
    END
  END AverageDistSqr;

PROCEDURE SegmentIsExcluded(
    READONLY s: PZSegment.T;
    READONLY exSeg: Segments;
  ): BOOL =
  (*
    TRUE if "s" overlaps any of the segments in "exSeg". *)
  BEGIN
    FOR i := 0 TO LAST(exSeg) DO
      IF PZSegment.Overlap(s, exSeg[i]) THEN RETURN TRUE END
    END;
    RETURN FALSE
  END SegmentIsExcluded;

PROCEDURE PrintCandidates (
    READONLY cand: Candidates;
    maxCands: NAT;
  ) =
  BEGIN
    IF maxCands = 0 THEN RETURN END;
    Wr.PutText(stderr, "\n");
    FOR i := 0 TO MIN(maxCands, NUMBER(cand))-1 DO
      WITH c = cand[i] DO
        Wr.PutText(stderr, "cand[" & Fmt.Int(i) & "]\n");
        PZCandidate.Print(stderr, c, pairing := FALSE)
      END
    END;
    Wr.Flush(stderr);
  END PrintCandidates;

PROCEDURE ReadAllCVCFiles(
    chainDir: TEXT;
    chainPrefix : TEXT;
    nCurves, band: NAT;
  ): REF ARRAY OF PZSymbolChain.ReadData =
  BEGIN
    WITH
      sel = NEW(REF BOOLS, nCurves)^
    DO
      FOR i := 0 TO nCurves-1 DO sel[i] := TRUE END;
      RETURN PZSymbolChain.ReadAll(
        prefix := chainPrefix, band := band, extension := ".cvc",
        sel := sel, headerOnly := FALSE, dir := chainDir
      )
    END;
  END ReadAllCVCFiles;

PROCEDURE ReadExcludedSegsFile(segName: TEXT): REF Segments =
  BEGIN
    IF Text.Empty(segName) THEN
      RETURN NEW(REF Segments, 0)
    ELSE
      WITH fileName = segName & ".seg" DO
        Wr.PutText(stderr, fileName & "\n");
        WITH
          rd = FileRd.Open(fileName),
          sData = PZSegment.Read(rd)
        DO
          RETURN sData.s
        END
      END
    END
  END ReadExcludedSegsFile;

PROCEDURE CandComment(READONLY o: Options): TEXT =
  BEGIN
    RETURN
      "PZGetRandomCandidates\n" &
      "    chainDir " & o.chainDir & "\n" &
      "    chainPrefix " & o.chainPrefix & "\n" &
      "    nCurves = " & Fmt.Int(o.nCurves) & "\n" &
      "    band = " & Fmt.Int(o.band) & "\n" &
      "    borderSegs = \"" & o.borderSegs & "\"\n" &
      "    cornerSegs = \"" & o.cornerSegs & "\"\n" &
      "    nCands = " & Fmt.Int(o.nCands) & "\n" &
      "    minLength = " & Fmt.LongReal(o.minLength) & "\n" &
      "    maxLength = " & Fmt.LongReal(o.maxLength) & "\n" &
      "    blurFactor = " & Fmt.LongReal(o.blurFactor) & "\n"
  END CandComment;

BEGIN
  Main()
END PZGetRandomCands.