STSheets/tests/align/dtw.test.ts

import { test, expect } from "bun:test";
import { dtw } from "../../src/align/dtw.ts";

// Ground-truth path: diagonal with a kink (j runs ahead by 10 after i=50).
function truthJ(i: number): number { return i < 50 ? i : i + 10; }
const N = 100, M = 110;
// Path cells cost 0, others grow with distance from the true path.
const cost = (i: number, j: number) => {
  const t = truthJ(i);
  return Math.min(1, Math.abs(j - t) * 0.2);
};

test("dtw recovers diagonal-with-kink path", () => {
  const p = dtw(cost, N, M);
  expect(p[0]).toEqual([0, 0]);
  expect(p[p.length - 1]).toEqual([N - 1, M - 1]);
  for (const [i, j] of p) if (i !== 49 && i !== 50) expect(Math.abs(j - truthJ(i))).toBeLessThanOrEqual(1);
  for (let k = 1; k < p.length; k++) {
    const di = p[k]![0] - p[k - 1]![0], dj = p[k]![1] - p[k - 1]![1];
    expect(di >= 0 && di <= 1 && dj >= 0 && dj <= 1 && di + dj >= 1).toBe(true);
  }
});

test("banded dtw equals unbanded when the band covers the path", () => {
  const full = dtw(cost, N, M);
  const banded = dtw(cost, N, M, { center: (i) => truthJ(i), width: 15 });
  expect(banded).toEqual(full);
});

test("banded dtw only visits cells in the band", () => {
  let calls = 0;
  const p = dtw((i, j) => { calls++; return Math.abs(i - j) * 0.1; }, 200, 200, { center: (i) => i, width: 5 });
  expect(calls).toBeLessThanOrEqual(200 * 11);
  expect(p[p.length - 1]).toEqual([199, 199]);
});

test("3000x3000 unbanded dtw finishes in < 5 s", () => {
  const n = 3000;
  const t0 = performance.now();
  const p = dtw((i, j) => Math.abs(i - j) * 0.001 + ((i * 7 + j * 13) % 5) * 0.0001, n, n);
  const ms = performance.now() - t0;
  console.log(`dtw 3000x3000: ${ms.toFixed(0)} ms`);
  expect(p[p.length - 1]).toEqual([n - 1, n - 1]);
  expect(ms).toBeLessThan(5000);
});

// ---- slope-limited steps and open begin/end (ruling A8) ----
const stepsOf = (p: [number, number][]) => p.slice(1).map(([i, j], k) => [i - p[k]![0], j - p[k]![1]] as const);
/** No two consecutive non-diagonal steps in the same direction: local slope stays within [1/2, 2]. */
function slopeLimited(p: [number, number][]): boolean {
  const s = stepsOf(p);
  return s.every(([di, dj], k) => {
    if (!((di === 1 && dj === 1) || (di === 1 && dj === 0) || (di === 0 && dj === 1))) return false;
    const prev = s[k - 1];
    return !(k > 0 && di + dj === 1 && prev![0] === di && prev![1] === dj);
  });
}

test("slope-limited steps: path never makes an abrupt jump even when the cost invites one", () => {
  // the cost is 0 on a path that jumps 20 columns at i = 50; symmetric steps follow the jump, slope-limited ones cannot
  const jumpCost = (i: number, j: number) => Math.min(1, Math.abs(j - (i < 50 ? i : i + 20)) * 0.2);
  const sym = dtw(jumpCost, 100, 120);
  expect(stepsOf(sym).some(([di, dj], k, s) => di === 0 && dj === 1 && s[k + 1]?.[0] === 0)).toBe(true); // a horizontal run
  const p = dtw(jumpCost, 100, 120, undefined, { steps: "slope" });
  expect(p[0]).toEqual([0, 0]);
  expect(p[p.length - 1]).toEqual([99, 119]);
  expect(slopeLimited(p)).toBe(true);
});

test("slope-limited steps follow a smooth diagonal-with-kink path exactly like the default (banded too)", () => {
  const p = dtw(cost, N, M, undefined, { steps: "slope" });
  expect(slopeLimited(p)).toBe(true);
  for (const [i, j] of p) if (i < 45 || i > 60) expect(Math.abs(j - truthJ(i))).toBeLessThanOrEqual(1);
  expect(dtw(cost, N, M, { center: truthJ, width: 15 }, { steps: "slope" })).toEqual(p);
});

test("slope-limited steps throw 'unreachable' when the aspect ratio exceeds 2", () => {
  expect(() => dtw(cost, 10, 30, undefined, { steps: "slope" })).toThrow(/unreachable/);
});

test("open end: the path may stop before the recording ends (subsequence end)", () => {
  // the query (rows) matches columns 0..99 diagonally; the last 40 columns are extra material
  const c = (i: number, j: number) => (j < 100 ? Math.min(1, Math.abs(i - j) * 0.2) : 0.5);
  const closed = dtw(c, 100, 140, undefined, { steps: "slope" });
  expect(closed[closed.length - 1]).toEqual([99, 139]);
  const open = dtw(c, 100, 140, undefined, { steps: "slope", openEnd: true });
  expect(open[open.length - 1]).toEqual([99, 99]);
  for (const [i, j] of open) expect(Math.abs(i - j)).toBeLessThanOrEqual(1);
  // the query being longer than the target (its extra rows mismatch everything, costing more than an unconsumed row):
  // the path may end on the last column
  const longer = dtw((i, j) => (i < 60 ? Math.min(1, Math.abs(i - j) * 0.2) : 1.5), 100, 60, undefined, { steps: "slope", openEnd: true });
  expect(longer[longer.length - 1]).toEqual([59, 59]);
});

test("open begin: the path may start after the beginning of the target", () => {
  const c = (i: number, j: number) => (j >= 30 ? Math.min(1, Math.abs(i + 30 - j) * 0.2) : 0.5);
  const p = dtw(c, 100, 130, undefined, { steps: "slope", openBegin: true });
  expect(p[0]).toEqual([0, 30]);
  expect(p[p.length - 1]).toEqual([99, 129]);
  for (const [i, j] of p) expect(Math.abs(i + 30 - j)).toBeLessThanOrEqual(1);
  // banded with a band that does not include column 0 at row 0
  expect(dtw(c, 100, 130, { center: (i) => i + 30, width: 10 }, { steps: "slope", openBegin: true })).toEqual(p);
});

test("open begin + end: a trivial path in a zero-cost corner does not win (unconsumed rows cost 1 each)", () => {
  // the last column is free everywhere (e.g. silence vs silence), the real match is the diagonal of the first 100 columns
  const c = (i: number, j: number) => (j === 119 ? 0 : j < 100 ? Math.min(1, Math.abs(i - j) * 0.2) : 0.6);
  const p = dtw(c, 100, 120, undefined, { steps: "slope", openBegin: true, openEnd: true });
  expect(p.length).toBeGreaterThan(90);
  expect(p[p.length - 1]).toEqual([99, 99]);
});