/**
 * @file Longest Common Subsequence (LCS)
 * @author Dustin Boston
 * @see Cormen, T, Leiserson, C, Rivest, R, and Stein, C. (2001).
 * _Introduction to Algorithms_. (2nd ed). The MIT Press.
 */

/**
 * Computes the longest common subsequence (LCS) length and the optimal path
 * matrix between two sequences. This function uses dynamic programming to build
 * a table that stores the lengths of LCSs for different segments of the two
 * input arrays.
 *
 * @template T - The type of elements in the input arrays.
 * @param arrayX - The first sequence of elements.
 * @param arrayY - The second sequence of elements.
 * @returns A tuple containing two matrices:
 *
 *   - `computed`: A matrix of LCS lengths for subarrays at the coordinate.
 *   - `trace`: A matrix of directions to trace back the LCS.
 */
export function lcsLength<T>(arrayX: T[], arrayY: T[]): [computed: number[][], trace: string[][]] {
  const lengthX = arrayX.length;
  const lengthY = arrayY.length;

  const computed: number[][] = [];
  const trace: string[][] = [];

  for (let i = 0; i <= lengthX; i++) {
    computed[i] = Array.from({ length: lengthY + 1 }, () => 0);
    trace[i] = Array.from({ length: lengthY + 1 }, () => "");
  }

  for (let i = 1; i <= lengthX; i++) {
    for (let index = 1; index <= lengthY; index++) {
      if (arrayX[i - 1] === arrayY[index - 1]) {
        computed[i][index] = computed[i - 1][index - 1] + 1;
        trace[i][index] = "↖";
      } else if (computed[i - 1][index] >= computed[i][index - 1]) {
        computed[i][index] = computed[i - 1][index];
        trace[i][index] = "↑";
      } else {
        computed[i][index] = computed[i][index - 1];
        trace[i][index] = "←";
      }
    }
  }

  return [computed, trace];
}

/**
 * Recursively reconstructs the longest common subsequence (LCS) from the trace
 * matrix generated by the `lcsLength` function. This function traces the
 * optimal path from the bottom-right corner of the matrix to the top-left,
 * building the LCS string by following the directions stored in the matrix.
 *
 * @template T - The type of elements in the input array.
 * @param trace - The matrix containing the optimal path directions.
 * @param arrayX - The sequence of elements used to generate the trace matrix.
 * @param i - The current row index in the `trace` matrix to be considered.
 * @param j - The current column index in the `trace` matrix to be considered.
 * @returns The longest common subsequence as a string.
 */
export function printLcs<T>(trace: string[][], arrayX: T[], i: number, index: number): string {
  if (i === 0 || index === 0) {
    // Return empty when we reach the edge of the table.
    return "";
  }

  if (trace[i][index] === "↖") {
    // Include this character and continue recursion
    return printLcs(trace, arrayX, i - 1, index - 1) + arrayX[i - 1];
  }

  if (trace[i][index] === "↑") {
    // Recurse upwards
    return printLcs(trace, arrayX, i - 1, index);
  }

  // Recurse leftwards
  return printLcs(trace, arrayX, i, index - 1);
}