Dustin Boston

/**
 * @file Myers Diff
 * @author Dustin Boston
 * @see E. Myers, "An O(ND) difference algorithm and its variations,"
 *   _Algorithmica_, vol. 1, no. 1–4, pp. 251–266, 1986.
 * @see J. Coglan, "The Myers diff algorithm: part 1," The if works,
 *   https://blog.jcoglan.com/2017/02/12/the-myers-diff-algorithm-part-1/
 * @see R. Elder, "Myers Diff Algorithm - Code & Interactive Visualization,"
 *   Robert Elder Software Inc, https://blog.robertelder.org/diff-algorithm/
 */

import {NegativeArray} from "../negative-array/code.ts";

/**
 * Computes the diff between two strings using the Myers algorithm and returns
 * an edit script in the form `xD` or `xIb` where `x` is the `x` coordinate, `D`
 * is delete, `I` is insert, and `b` is the char inserted at`x`, for example
 * `1D,2D,3IB,6D,7IC`.
 *
 * @param original - The original string.
 * @param target - The target string to compare.
 * @returns An edit script.
 */
export function diff(original: string, target: string): string[] {
  const operations: string[] = [];
  const editTrace = shortestEdit(original, target);
  if (!editTrace) throw new Error("Invalid return.");

  // Backtrack yields from the end to the start.
  for (const [previousX, previousY, currentX, currentY] of backtrack(
    original.length,
    target.length,
    editTrace,
  )) {
    const targetChar = target[previousY];
    if (currentX === previousX) operations.unshift(`${currentX}I${targetChar}`);
    else if (currentY === previousY) operations.unshift(`${currentX}D`);
  }

  return operations;
}

/**
 * The Greedy LCS/SES Algorithm (figure 2 in the paper) Finds the shortest edit
 * path for two strings using the Myers diff algorithm.
 *
 * @param original - The original string.
 * @param target - The target string.
 * @returns The trace of V operations with each step taken.
 */
export function shortestEdit(
  original: string,
  target: string,
): number[][] | undefined {
  const originalLength = original.length;
  const targetLength = target.length;
  const maxLength = originalLength + targetLength;

  /** An array of the furthest reaching edit distances across the edit graph */
  const furthestReachingPoints: number[] = new NegativeArray<number>(
    2 * maxLength + 2,
  );
  furthestReachingPoints[1] = 0;

  /** Record of each operation */
  const trace: number[][] = new NegativeArray<number[]>();

  // Calculate distances (d)
  for (let distance = 0; distance <= maxLength + 1; distance++) {
    trace.push(new NegativeArray<number>(...furthestReachingPoints));

    // Calculate the operations (k)
    for (let diagonal = -distance; diagonal <= distance + 1; diagonal += 2) {
      let currentX =
        diagonal === -distance ||
        (diagonal !== distance &&
          furthestReachingPoints[diagonal - 1] <
            furthestReachingPoints[diagonal + 1])
          ? furthestReachingPoints[diagonal + 1] // Move down (deletion)
          : furthestReachingPoints[diagonal - 1] + 1; // Move right (insertion)

      let currentY = currentX - diagonal;
      while (
        currentX < originalLength &&
        currentY < targetLength &&
        original[currentX] === target[currentY]
      ) {
        currentX++;
        currentY++;
      }

      furthestReachingPoints[diagonal] = currentX;
      if (currentX >= originalLength && currentY >= targetLength) {
        return trace;
      }
    }
  }
}

/** Records a movement from the previous position to the current position. */
export type Move = [
  previousX: number,
  previousY: number,
  currentX: number,
  currentY: number,
];

/**
 * A generator function that backtracks from the computed trace to find the
 * actual diff path.
 *
 * @param originalLength - Length of the original string.
 * @param targetLength - Length of the target string.
 * @param trace - The edit trace
 * @yields Individual moves to transform the original string into the target
 *   string.
 */
export function* backtrack(
  originalLength: number,
  targetLength: number,
  trace: number[][],
): Generator<Move, void> {
  let currentX = originalLength;
  let currentY = targetLength;

  for (let distance = trace.length - 1; distance > -1; distance--) {
    /** Array of furthest reaching x distances across the edit graph */
    const furthestReachingPoints = trace[distance];
    /** The operation */
    const diagonal = currentX - currentY;

    /** Previous edit operation */
    const previousDiagonal =
      diagonal === -distance ||
      (diagonal !== distance &&
        furthestReachingPoints[diagonal - 1] <
          furthestReachingPoints[diagonal + 1])
        ? diagonal + 1
        : diagonal - 1;

    const previousX = furthestReachingPoints[previousDiagonal];
    const previousY = previousX - previousDiagonal;

    while (currentX > previousX && currentY > previousY) {
      yield [currentX - 1, currentY - 1, currentX, currentY];
      currentX -= 1;
      currentY -= 1;
    }

    if (distance > 0) yield [previousX, previousY, currentX, currentY];
    currentX = previousX;
    currentY = previousY;
  }
}

// Usage
(() => {
  const array = new NegativeArray(1, 2, 3, 4, 5);
  if (array[-1] !== 5) {
    throw new Error(`Expected 5 but got ${array[-1]}`);
  }

  // Diff between 'ABCABBA' and 'CBABAC'
  const abcActual = diff("ABCABBA", "CBABAC");
  const abcExpected = "1D,2D,3IB,6D,7IC";

  if (abcActual.toString() !== abcExpected) {
    throw new Error(`Expected ${abcExpected} but got ${abcActual.join(",")}`);
  }

  // Diff between 'CARE' and 'BEAR'
  const careActual = diff("CARE", "BEAR");
  const careExpected = "1D,1IB,1IE,4D";

  if (careActual.toString() !== careExpected) {
    throw new Error(`Expected ${careExpected} but got ${careActual.join(",")}`);
  }

  console.log("Diff passed");
})();

import {diff} from "../../../../data/algorithms/src/myers_diff.ts";
import {assertEquals} from "$assert";

test("Diff between 'ABCABBA' and 'CBABAC'", () => {
  const result = diff("ABCABBA", "CBABAC");
  const expected = "1D,2D,3IB,6D,7IC";
  assertEquals(result.toString(), expected);
});

test("Diff between 'CARE' and 'BEAR'", () => {
  const result = diff("CARE", "BEAR");
  const expected = "1D,1IB,1IE,4D";
  assertEquals(result.toString(), expected);
});