index.ts

/**
 * Copyright (c) Facebook, Inc. and its affiliates. All Rights Reserved.
 *
 * This source code is licensed under the MIT license found in the
 * LICENSE file in the root directory of this source tree.
 *
 */

// This diff-sequences package implements the linear space variation in
// An O(ND) Difference Algorithm and Its Variations by Eugene W. Myers

// Relationship in notation between Myers paper and this package:
// A is a
// N is aLength, aEnd - aStart, and so on
// x is aIndex, aFirst, aLast, and so on
// B is b
// M is bLength, bEnd - bStart, and so on
// y is bIndex, bFirst, bLast, and so on
// Δ = N - M is negative of baDeltaLength = bLength - aLength
// D is d
// k is kF
// k + Δ is kF = kR - baDeltaLength
// V is aIndexesF or aIndexesR (see comment below about Indexes type)
// index intervals [1, N] and [1, M] are [0, aLength) and [0, bLength)
// starting point in forward direction (0, 0) is (-1, -1)
// starting point in reverse direction (N + 1, M + 1) is (aLength, bLength)

// The “edit graph” for sequences a and b corresponds to items:
// in a on the horizontal axis
// in b on the vertical axis
//
// Given a-coordinate of a point in a diagonal, you can compute b-coordinate.
//
// Forward diagonals kF:
// zero diagonal intersects top left corner
// positive diagonals intersect top edge
// negative diagonals insersect left edge
//
// Reverse diagonals kR:
// zero diagonal intersects bottom right corner
// positive diagonals intersect right edge
// negative diagonals intersect bottom edge

// The graph contains a directed acyclic graph of edges:
// horizontal: delete an item from a
// vertical: insert an item from b
// diagonal: common item in a and b
//
// The algorithm solves dual problems in the graph analogy:
// Find longest common subsequence: path with maximum number of diagonal edges
// Find shortest edit script: path with minimum number of non-diagonal edges

// Input callback function compares items at indexes in the sequences.
type IsCommon = (
  aIndex: number, // caller can assume: 0 <= aIndex && aIndex < aLength
  bIndex: number, // caller can assume: 0 <= bIndex && bIndex < bLength
) => boolean;

// Output callback function receives the number of adjacent items
// and starting indexes of each common subsequence.
type FoundSubsequence = (
  nCommon: number, // caller can assume: 0 < nCommon
  aCommon: number, // caller can assume: 0 <= aCommon && aCommon < aLength
  bCommon: number, // caller can assume: 0 <= bCommon && bCommon < bLength
) => void;

// Either original functions or wrapped to swap indexes if graph is transposed.
type Callbacks = {
  foundSubsequence: FoundSubsequence;
  isCommon: IsCommon;
};

// Indexes in sequence a of last point of forward or reverse paths in graph.
// Myers algorithm indexes by diagonal k which for negative is bad deopt in V8.
// This package indexes by iF and iR which are greater than or equal to zero.
// and also updates the index arrays in place to cut memory in half.
// kF = 2 * iF - d
// kR = d - 2 * iR
type Indexes = Array<number>;

// Division of index intervals in sequences a and b at the middle change.
// Invariant: intervals do not have common items at the start or end.
type Division = {
  // The end of interval preceding division is open like array slice method.
  nChangePreceding: number; // number of change items
  aEndPreceding: number;
  bEndPreceding: number;

  nCommonPreceding: number; // 0 if no common items preceding middle change
  aCommonPreceding: number; // ignore prop value if nCommonPreceding === 0
  bCommonPreceding: number; // ignore prop value if nCommonPreceding === 0

  nCommonFollowing: number; // 0 if no common items following middle change
  aCommonFollowing: number; // ignore prop value if nCommonFollowing === 0
  bCommonFollowing: number; // ignore prop value if nCommonFollowing === 0

  // The start of interval following division is closed like array slice method.
  nChangeFollowing: number; // number of change items
  aStartFollowing: number;
  bStartFollowing: number;
};

const pkg = 'diff-sequences'; // for error messages
const NOT_YET_SET = 0; // small int instead of undefined to avoid deopt in V8

// Return the number of common items that follow in forward direction.
// The length of what Myers paper calls a “snake” in a forward path.
const countCommonItemsF = (
  aIndex: number,
  aEnd: number,
  bIndex: number,
  bEnd: number,
  isCommon: IsCommon,
) => {
  let nCommon = 0;
  while (aIndex < aEnd && bIndex < bEnd && isCommon(aIndex, bIndex)) {
    aIndex += 1;
    bIndex += 1;
    nCommon += 1;
  }
  return nCommon;
};

// Return the number of common items that precede in reverse direction.
// The length of what Myers paper calls a “snake” in a reverse path.
const countCommonItemsR = (
  aStart: number,
  aIndex: number,
  bStart: number,
  bIndex: number,
  isCommon: IsCommon,
) => {
  let nCommon = 0;
  while (aStart <= aIndex && bStart <= bIndex && isCommon(aIndex, bIndex)) {
    aIndex -= 1;
    bIndex -= 1;
    nCommon += 1;
  }
  return nCommon;
};

// A simple function to extend forward paths from (d - 1) to d changes
// when forward and reverse paths cannot yet overlap.
const extendPathsF = (
  d: number,
  aEnd: number,
  bEnd: number,
  bF: number, // bIndex = bF + aIndex - kF
  isCommon: IsCommon,
  aIndexesF: Indexes, // update indexes in sequence a of paths in diagonals kF
  iMaxF: number, // return the value because optimization might decrease it
): number => {
  // Unroll the first iteration.
  let iF = 0;
  let kF = -d; // kF = 2 * iF - d
  let aFirst = aIndexesF[iF]; // in first iteration always insert
  let aIndexPrev1 = aFirst; // prev value of [iF - 1] in next iteration
  aIndexesF[iF] += countCommonItemsF(
    aFirst + 1,
    aEnd,
    bF + aFirst - kF + 1,
    bEnd,
    isCommon,
  );

  // Optimization: skip diagonals in which paths cannot ever overlap.
  const nF = d < iMaxF ? d : iMaxF;

  // The diagonals kF are odd when d is odd and even when d is even.
  for (iF += 1, kF += 2; iF <= nF; iF += 1, kF += 2) {
    // To get first point of path segment, move one change in forward direction
    // from last point of previous path segment in an adjacent diagonal.
    // In last possible iteration when iF === d and kF === d always delete.
    if (iF !== d && aIndexPrev1 < aIndexesF[iF]) {
      aFirst = aIndexesF[iF]; // vertical to insert from b
    } else {
      aFirst = aIndexPrev1 + 1; // horizontal to delete from a

      if (aEnd <= aFirst) {
        // Optimization: delete moved past right of graph.
        return iF - 1;
      }
    }

    // To get last point of path segment, move along diagonal of common items.
    aIndexPrev1 = aIndexesF[iF];
    aIndexesF[iF] =
      aFirst +
      countCommonItemsF(aFirst + 1, aEnd, bF + aFirst - kF + 1, bEnd, isCommon);
  }

  return iMaxF;
};

// A simple function to extend reverse paths from (d - 1) to d changes
// when reverse and forward paths cannot yet overlap.
const extendPathsR = (
  d: number,
  aStart: number,
  bStart: number,
  bR: number, // bIndex = bR + aIndex - kR
  isCommon: IsCommon,
  aIndexesR: Indexes, // update indexes in sequence a of paths in diagonals kR
  iMaxR: number, // return the value because optimization might decrease it
): number => {
  // Unroll the first iteration.
  let iR = 0;
  let kR = d; // kR = d - 2 * iR
  let aFirst = aIndexesR[iR]; // in first iteration always insert
  let aIndexPrev1 = aFirst; // prev value of [iR - 1] in next iteration
  aIndexesR[iR] -= countCommonItemsR(
    aStart,
    aFirst - 1,
    bStart,
    bR + aFirst - kR - 1,
    isCommon,
  );

  // Optimization: skip diagonals in which paths cannot ever overlap.
  const nR = d < iMaxR ? d : iMaxR;

  // The diagonals kR are odd when d is odd and even when d is even.
  for (iR += 1, kR -= 2; iR <= nR; iR += 1, kR -= 2) {
    // To get first point of path segment, move one change in reverse direction
    // from last point of previous path segment in an adjacent diagonal.
    // In last possible iteration when iR === d and kR === -d always delete.
    if (iR !== d && aIndexesR[iR] < aIndexPrev1) {
      aFirst = aIndexesR[iR]; // vertical to insert from b
    } else {
      aFirst = aIndexPrev1 - 1; // horizontal to delete from a

      if (aFirst < aStart) {
        // Optimization: delete moved past left of graph.
        return iR - 1;
      }
    }

    // To get last point of path segment, move along diagonal of common items.
    aIndexPrev1 = aIndexesR[iR];
    aIndexesR[iR] =
      aFirst -
      countCommonItemsR(
        aStart,
        aFirst - 1,
        bStart,
        bR + aFirst - kR - 1,
        isCommon,
      );
  }

  return iMaxR;
};

// A complete function to extend forward paths from (d - 1) to d changes.
// Return true if a path overlaps reverse path of (d - 1) changes in its diagonal.
const extendOverlappablePathsF = (
  d: number,
  aStart: number,
  aEnd: number,
  bStart: number,
  bEnd: number,
  isCommon: IsCommon,
  aIndexesF: Indexes, // update indexes in sequence a of paths in diagonals kF
  iMaxF: number,
  aIndexesR: Indexes,
  iMaxR: number,
  division: Division, // update prop values if return true
): boolean => {
  const bF = bStart - aStart; // bIndex = bF + aIndex - kF
  const aLength = aEnd - aStart;
  const bLength = bEnd - bStart;
  const baDeltaLength = bLength - aLength; // kF = kR - baDeltaLength

  // Range of diagonals in which forward and reverse paths might overlap.
  const kMinOverlapF = -baDeltaLength - (d - 1); // -(d - 1) <= kR
  const kMaxOverlapF = -baDeltaLength + (d - 1); // kR <= (d - 1)

  let aIndexPrev1 = NOT_YET_SET; // prev value of [iF - 1] in next iteration

  // Optimization: skip diagonals in which paths cannot ever overlap.
  const nF = d < iMaxF ? d : iMaxF;

  // The diagonals kF = 2 * iF - d are odd when d is odd and even when d is even.
  for (let iF = 0, kF = -d; iF <= nF; iF += 1, kF += 2) {
    // To get first point of path segment, move one change in forward direction
    // from last point of previous path segment in an adjacent diagonal.
    // In first iteration when iF === 0 and kF === -d always insert.
    // In last possible iteration when iF === d and kF === d always delete.
    const insert = iF === 0 || (iF !== d && aIndexPrev1 < aIndexesF[iF]);
    const aLastPrev = insert ? aIndexesF[iF] : aIndexPrev1;
    const aFirst = insert
      ? aLastPrev // vertical to insert from b
      : aLastPrev + 1; // horizontal to delete from a

    // To get last point of path segment, move along diagonal of common items.
    const bFirst = bF + aFirst - kF;
    const nCommonF = countCommonItemsF(
      aFirst + 1,
      aEnd,
      bFirst + 1,
      bEnd,
      isCommon,
    );
    const aLast = aFirst + nCommonF;

    aIndexPrev1 = aIndexesF[iF];
    aIndexesF[iF] = aLast;

    if (kMinOverlapF <= kF && kF <= kMaxOverlapF) {
      // Solve for iR of reverse path with (d - 1) changes in diagonal kF:
      // kR = kF + baDeltaLength
      // kR = (d - 1) - 2 * iR
      const iR = (d - 1 - (kF + baDeltaLength)) / 2;

      // If this forward path overlaps the reverse path in this diagonal,
      // then this is the middle change of the index intervals.
      if (iR <= iMaxR && aIndexesR[iR] - 1 <= aLast) {
        // Unlike the Myers algorithm which finds only the middle “snake”
        // this package can find two common subsequences per division.
        // Last point of previous path segment is on an adjacent diagonal.
        const bLastPrev = bF + aLastPrev - (insert ? kF + 1 : kF - 1);

        // Because of invariant that intervals preceding the middle change
        // cannot have common items at the end,
        // move in reverse direction along a diagonal of common items.
        const nCommonR = countCommonItemsR(
          aStart,
          aLastPrev,
          bStart,
          bLastPrev,
          isCommon,
        );

        const aIndexPrevFirst = aLastPrev - nCommonR;
        const bIndexPrevFirst = bLastPrev - nCommonR;

        const aEndPreceding = aIndexPrevFirst + 1;
        const bEndPreceding = bIndexPrevFirst + 1;

        division.nChangePreceding = d - 1;
        if (d - 1 === aEndPreceding + bEndPreceding - aStart - bStart) {
          // Optimization: number of preceding changes in forward direction
          // is equal to number of items in preceding interval,
          // therefore it cannot contain any common items.
          division.aEndPreceding = aStart;
          division.bEndPreceding = bStart;
        } else {
          division.aEndPreceding = aEndPreceding;
          division.bEndPreceding = bEndPreceding;
        }

        division.nCommonPreceding = nCommonR;
        if (nCommonR !== 0) {
          division.aCommonPreceding = aEndPreceding;
          division.bCommonPreceding = bEndPreceding;
        }

        division.nCommonFollowing = nCommonF;
        if (nCommonF !== 0) {
          division.aCommonFollowing = aFirst + 1;
          division.bCommonFollowing = bFirst + 1;
        }

        const aStartFollowing = aLast + 1;
        const bStartFollowing = bFirst + nCommonF + 1;

        division.nChangeFollowing = d - 1;
        if (d - 1 === aEnd + bEnd - aStartFollowing - bStartFollowing) {
          // Optimization: number of changes in reverse direction
          // is equal to number of items in following interval,
          // therefore it cannot contain any common items.
          division.aStartFollowing = aEnd;
          division.bStartFollowing = bEnd;
        } else {
          division.aStartFollowing = aStartFollowing;
          division.bStartFollowing = bStartFollowing;
        }

        return true;
      }
    }
  }

  return false;
};

// A complete function to extend reverse paths from (d - 1) to d changes.
// Return true if a path overlaps forward path of d changes in its diagonal.
const extendOverlappablePathsR = (
  d: number,
  aStart: number,
  aEnd: number,
  bStart: number,
  bEnd: number,
  isCommon: IsCommon,
  aIndexesF: Indexes,
  iMaxF: number,
  aIndexesR: Indexes, // update indexes in sequence a of paths in diagonals kR
  iMaxR: number,
  division: Division, // update prop values if return true
): boolean => {
  const bR = bEnd - aEnd; // bIndex = bR + aIndex - kR
  const aLength = aEnd - aStart;
  const bLength = bEnd - bStart;
  const baDeltaLength = bLength - aLength; // kR = kF + baDeltaLength

  // Range of diagonals in which forward and reverse paths might overlap.
  const kMinOverlapR = baDeltaLength - d; // -d <= kF
  const kMaxOverlapR = baDeltaLength + d; // kF <= d

  let aIndexPrev1 = NOT_YET_SET; // prev value of [iR - 1] in next iteration

  // Optimization: skip diagonals in which paths cannot ever overlap.
  const nR = d < iMaxR ? d : iMaxR;

  // The diagonals kR = d - 2 * iR are odd when d is odd and even when d is even.
  for (let iR = 0, kR = d; iR <= nR; iR += 1, kR -= 2) {
    // To get first point of path segment, move one change in reverse direction
    // from last point of previous path segment in an adjacent diagonal.
    // In first iteration when iR === 0 and kR === d always insert.
    // In last possible iteration when iR === d and kR === -d always delete.
    const insert = iR === 0 || (iR !== d && aIndexesR[iR] < aIndexPrev1);
    const aLastPrev = insert ? aIndexesR[iR] : aIndexPrev1;
    const aFirst = insert
      ? aLastPrev // vertical to insert from b
      : aLastPrev - 1; // horizontal to delete from a

    // To get last point of path segment, move along diagonal of common items.
    const bFirst = bR + aFirst - kR;
    const nCommonR = countCommonItemsR(
      aStart,
      aFirst - 1,
      bStart,
      bFirst - 1,
      isCommon,
    );
    const aLast = aFirst - nCommonR;

    aIndexPrev1 = aIndexesR[iR];
    aIndexesR[iR] = aLast;

    if (kMinOverlapR <= kR && kR <= kMaxOverlapR) {
      // Solve for iF of forward path with d changes in diagonal kR:
      // kF = kR - baDeltaLength
      // kF = 2 * iF - d
      const iF = (d + (kR - baDeltaLength)) / 2;

      // If this reverse path overlaps the forward path in this diagonal,
      // then this is a middle change of the index intervals.
      if (iF <= iMaxF && aLast - 1 <= aIndexesF[iF]) {
        const bLast = bFirst - nCommonR;

        division.nChangePreceding = d;
        if (d === aLast + bLast - aStart - bStart) {
          // Optimization: number of changes in reverse direction
          // is equal to number of items in preceding interval,
          // therefore it cannot contain any common items.
          division.aEndPreceding = aStart;
          division.bEndPreceding = bStart;
        } else {
          division.aEndPreceding = aLast;
          division.bEndPreceding = bLast;
        }

        division.nCommonPreceding = nCommonR;
        if (nCommonR !== 0) {
          // The last point of reverse path segment is start of common subsequence.
          division.aCommonPreceding = aLast;
          division.bCommonPreceding = bLast;
        }

        division.nChangeFollowing = d - 1;
        if (d === 1) {
          // There is no previous path segment.
          division.nCommonFollowing = 0;
          division.aStartFollowing = aEnd;
          division.bStartFollowing = bEnd;
        } else {
          // Unlike the Myers algorithm which finds only the middle “snake”
          // this package can find two common subsequences per division.
          // Last point of previous path segment is on an adjacent diagonal.
          const bLastPrev = bR + aLastPrev - (insert ? kR - 1 : kR + 1);

          // Because of invariant that intervals following the middle change
          // cannot have common items at the start,
          // move in forward direction along a diagonal of common items.
          const nCommonF = countCommonItemsF(
            aLastPrev,
            aEnd,
            bLastPrev,
            bEnd,
            isCommon,
          );

          division.nCommonFollowing = nCommonF;
          if (nCommonF !== 0) {
            // The last point of reverse path segment is start of common subsequence.
            division.aCommonFollowing = aLastPrev;
            division.bCommonFollowing = bLastPrev;
          }

          const aStartFollowing = aLastPrev + nCommonF; // aFirstPrev
          const bStartFollowing = bLastPrev + nCommonF; // bFirstPrev

          if (d - 1 === aEnd + bEnd - aStartFollowing - bStartFollowing) {
            // Optimization: number of changes in forward direction
            // is equal to number of items in following interval,
            // therefore it cannot contain any common items.
            division.aStartFollowing = aEnd;
            division.bStartFollowing = bEnd;
          } else {
            division.aStartFollowing = aStartFollowing;
            division.bStartFollowing = bStartFollowing;
          }
        }

        return true;
      }
    }
  }

  return false;
};

// Given index intervals and input function to compare items at indexes,
// divide at the middle change.
//
// DO NOT CALL if start === end, because interval cannot contain common items
// and because this function will throw the “no overlap” error.
const divide = (
  nChange: number,
  aStart: number,
  aEnd: number,
  bStart: number,
  bEnd: number,
  isCommon: IsCommon,
  aIndexesF: Indexes, // temporary memory, not input nor output
  aIndexesR: Indexes, // temporary memory, not input nor output
  division: Division, // output
) => {
  const bF = bStart - aStart; // bIndex = bF + aIndex - kF
  const bR = bEnd - aEnd; // bIndex = bR + aIndex - kR
  const aLength = aEnd - aStart;
  const bLength = bEnd - bStart;

  // Because graph has square or portrait orientation,
  // length difference is minimum number of items to insert from b.
  // Corresponding forward and reverse diagonals in graph
  // depend on length difference of the sequences:
  // kF = kR - baDeltaLength
  // kR = kF + baDeltaLength
  const baDeltaLength = bLength - aLength;

  // Optimization: max diagonal in graph intersects corner of shorter side.
  let iMaxF = aLength;
  let iMaxR = aLength;

  // Initialize no changes yet in forward or reverse direction:
  aIndexesF[0] = aStart - 1; // at open start of interval, outside closed start
  aIndexesR[0] = aEnd; // at open end of interval

  if (baDeltaLength % 2 === 0) {
    // The number of changes in paths is 2 * d if length difference is even.
    const dMin = (nChange || baDeltaLength) / 2;
    const dMax = (aLength + bLength) / 2;

    for (let d = 1; d <= dMax; d += 1) {
      iMaxF = extendPathsF(d, aEnd, bEnd, bF, isCommon, aIndexesF, iMaxF);

      if (d < dMin) {
        iMaxR = extendPathsR(d, aStart, bStart, bR, isCommon, aIndexesR, iMaxR);
      } else if (
        // If a reverse path overlaps a forward path in the same diagonal,
        // return a division of the index intervals at the middle change.
        extendOverlappablePathsR(
          d,
          aStart,
          aEnd,
          bStart,
          bEnd,
          isCommon,
          aIndexesF,
          iMaxF,
          aIndexesR,
          iMaxR,
          division,
        )
      ) {
        return;
      }
    }
  } else {
    // The number of changes in paths is 2 * d - 1 if length difference is odd.
    const dMin = ((nChange || baDeltaLength) + 1) / 2;
    const dMax = (aLength + bLength + 1) / 2;

    // Unroll first half iteration so loop extends the relevant pairs of paths.
    // Because of invariant that intervals have no common items at start or end,
    // and limitation not to call divide with empty intervals,
    // therefore it cannot be called if a forward path with one change
    // would overlap a reverse path with no changes, even if dMin === 1.
    let d = 1;
    iMaxF = extendPathsF(d, aEnd, bEnd, bF, isCommon, aIndexesF, iMaxF);

    for (d += 1; d <= dMax; d += 1) {
      iMaxR = extendPathsR(
        d - 1,
        aStart,
        bStart,
        bR,
        isCommon,
        aIndexesR,
        iMaxR,
      );

      if (d < dMin) {
        iMaxF = extendPathsF(d, aEnd, bEnd, bF, isCommon, aIndexesF, iMaxF);
      } else if (
        // If a forward path overlaps a reverse path in the same diagonal,
        // return a division of the index intervals at the middle change.
        extendOverlappablePathsF(
          d,
          aStart,
          aEnd,
          bStart,
          bEnd,
          isCommon,
          aIndexesF,
          iMaxF,
          aIndexesR,
          iMaxR,
          division,
        )
      ) {
        return;
      }
    }
  }

  /* istanbul ignore next */
  throw new Error(
    `${pkg}: no overlap aStart=${aStart} aEnd=${aEnd} bStart=${bStart} bEnd=${bEnd}`,
  );
};

// Given index intervals and input function to compare items at indexes,
// return by output function the number of adjacent items and starting indexes
// of each common subsequence. Divide and conquer with only linear space.
//
// The index intervals are half open [start, end) like array slice method.
// DO NOT CALL if start === end, because interval cannot contain common items
// and because divide function will throw the “no overlap” error.
const findSubsequences = (
  nChange: number,
  aStart: number,
  aEnd: number,
  bStart: number,
  bEnd: number,
  transposed: boolean,
  callbacks: Array<Callbacks>,
  aIndexesF: Indexes, // temporary memory, not input nor output
  aIndexesR: Indexes, // temporary memory, not input nor output
  division: Division, // temporary memory, not input nor output
) => {
  if (bEnd - bStart < aEnd - aStart) {
    // Transpose graph so it has portrait instead of landscape orientation.
    // Always compare shorter to longer sequence for consistency and optimization.
    transposed = !transposed;
    if (transposed && callbacks.length === 1) {
      // Lazily wrap callback functions to swap args if graph is transposed.
      const {foundSubsequence, isCommon} = callbacks[0];
      callbacks[1] = {
        foundSubsequence: (nCommon, bCommon, aCommon) => {
          foundSubsequence(nCommon, aCommon, bCommon);
        },
        isCommon: (bIndex, aIndex) => isCommon(aIndex, bIndex),
      };
    }

    const tStart = aStart;
    const tEnd = aEnd;
    aStart = bStart;
    aEnd = bEnd;
    bStart = tStart;
    bEnd = tEnd;
  }
  const {foundSubsequence, isCommon} = callbacks[transposed ? 1 : 0];

  // Divide the index intervals at the middle change.
  divide(
    nChange,
    aStart,
    aEnd,
    bStart,
    bEnd,
    isCommon,
    aIndexesF,
    aIndexesR,
    division,
  );
  const {
    nChangePreceding,
    aEndPreceding,
    bEndPreceding,
    nCommonPreceding,
    aCommonPreceding,
    bCommonPreceding,
    nCommonFollowing,
    aCommonFollowing,
    bCommonFollowing,
    nChangeFollowing,
    aStartFollowing,
    bStartFollowing,
  } = division;

  // Unless either index interval is empty, they might contain common items.
  if (aStart < aEndPreceding && bStart < bEndPreceding) {
    // Recursely find and return common subsequences preceding the division.
    findSubsequences(
      nChangePreceding,
      aStart,
      aEndPreceding,
      bStart,
      bEndPreceding,
      transposed,
      callbacks,
      aIndexesF,
      aIndexesR,
      division,
    );
  }

  // Return common subsequences that are adjacent to the middle change.
  if (nCommonPreceding !== 0) {
    foundSubsequence(nCommonPreceding, aCommonPreceding, bCommonPreceding);
  }
  if (nCommonFollowing !== 0) {
    foundSubsequence(nCommonFollowing, aCommonFollowing, bCommonFollowing);
  }

  // Unless either index interval is empty, they might contain common items.
  if (aStartFollowing < aEnd && bStartFollowing < bEnd) {
    // Recursely find and return common subsequences following the division.
    findSubsequences(
      nChangeFollowing,
      aStartFollowing,
      aEnd,
      bStartFollowing,
      bEnd,
      transposed,
      callbacks,
      aIndexesF,
      aIndexesR,
      division,
    );
  }
};

const validateLength = (name: string, arg: any) => {
  const type = typeof arg;
  if (type !== 'number') {
    throw new TypeError(`${pkg}: ${name} typeof ${type} is not a number`);
  }
  if (!Number.isSafeInteger(arg)) {
    throw new RangeError(`${pkg}: ${name} value ${arg} is not a safe integer`);
  }
  if (arg < 0) {
    throw new RangeError(`${pkg}: ${name} value ${arg} is a negative integer`);
  }
};

const validateCallback = (name: string, arg: any) => {
  const type = typeof arg;
  if (type !== 'function') {
    throw new TypeError(`${pkg}: ${name} typeof ${type} is not a function`);
  }
};

// Compare items in two sequences to find a longest common subsequence.
// Given lengths of sequences and input function to compare items at indexes,
// return by output function the number of adjacent items and starting indexes
// of each common subsequence.
export default (
  aLength: number,
  bLength: number,
  isCommon: IsCommon,
  foundSubsequence: FoundSubsequence,
) => {
  validateLength('aLength', aLength);
  validateLength('bLength', bLength);
  validateCallback('isCommon', isCommon);
  validateCallback('foundSubsequence', foundSubsequence);

  // Count common items from the start in the forward direction.
  const nCommonF = countCommonItemsF(0, aLength, 0, bLength, isCommon);

  if (nCommonF !== 0) {
    foundSubsequence(nCommonF, 0, 0);
  }

  // Unless both sequences consist of common items only,
  // find common items in the half-trimmed index intervals.
  if (aLength !== nCommonF || bLength !== nCommonF) {
    // Invariant: intervals do not have common items at the start.
    // The start of an index interval is closed like array slice method.
    const aStart = nCommonF;
    const bStart = nCommonF;

    // Count common items from the end in the reverse direction.
    const nCommonR = countCommonItemsR(
      aStart,
      aLength - 1,
      bStart,
      bLength - 1,
      isCommon,
    );

    // Invariant: intervals do not have common items at the end.
    // The end of an index interval is open like array slice method.
    const aEnd = aLength - nCommonR;
    const bEnd = bLength - nCommonR;

    // Unless one sequence consists of common items only,
    // therefore the other trimmed index interval consists of changes only,
    // find common items in the trimmed index intervals.
    const nCommonFR = nCommonF + nCommonR;
    if (aLength !== nCommonFR && bLength !== nCommonFR) {
      const nChange = 0; // number of change items is not yet known
      const transposed = false; // call the original unwrapped functions
      const callbacks = [{foundSubsequence, isCommon}];

      // Indexes in sequence a of last points in furthest reaching paths
      // from outside the start at top left in the forward direction:
      const aIndexesF = [NOT_YET_SET];
      // from the end at bottom right in the reverse direction:
      const aIndexesR = [NOT_YET_SET];

      // Initialize one object as output of all calls to divide function.
      const division = {
        aCommonFollowing: NOT_YET_SET,
        aCommonPreceding: NOT_YET_SET,
        aEndPreceding: NOT_YET_SET,
        aStartFollowing: NOT_YET_SET,
        bCommonFollowing: NOT_YET_SET,
        bCommonPreceding: NOT_YET_SET,
        bEndPreceding: NOT_YET_SET,
        bStartFollowing: NOT_YET_SET,
        nChangeFollowing: NOT_YET_SET,
        nChangePreceding: NOT_YET_SET,
        nCommonFollowing: NOT_YET_SET,
        nCommonPreceding: NOT_YET_SET,
      };

      // Find and return common subsequences in the trimmed index intervals.
      findSubsequences(
        nChange,
        aStart,
        aEnd,
        bStart,
        bEnd,
        transposed,
        callbacks,
        aIndexesF,
        aIndexesR,
        division,
      );
    }

    if (nCommonR !== 0) {
      foundSubsequence(nCommonR, aEnd, bEnd);
    }
  }
};