/**
 * longest common subsequence
 *
 * @param a 
 * @param b 
 * @returns 
 */
export const longestCommonSubsequence = (a: string[], b: string[]): string[] => {
  // Create a 2D array to store the lengths of common subsequences
  const lengths: number[][] = Array(a.length + 1)
    .fill(null)
    .map(() => Array(b.length + 1).fill(0));

  // Fill the lengths array
  for (let i = 1; i <= a.length; i++) {
    for (let j = 1; j <= b.length; j++) {
      if (a[i - 1] === b[j - 1]) {
        // If characters match, increment the length
        lengths[i][j] = lengths[i - 1][j - 1] + 1;
      } else {
        // If characters don't match, take the maximum of the adjacent cells
        lengths[i][j] = Math.max(lengths[i - 1][j], lengths[i][j - 1]);
      }
    }
  }

  // Reconstruct the longest common subsequence
  const result: string[] = [];
  let i = a.length, j = b.length;
  
  while (i > 0 && j > 0) {
    if (a[i - 1] === b[j - 1]) {
      // If characters match, add to result and move diagonally
      result.unshift(a[i - 1]);
      i--;
      j--;
    } else if (lengths[i - 1][j] > lengths[i][j - 1]) {
      // Move up if the cell above is greater
      i--;
    } else {
      // Move left otherwise
      j--;
    }
  }

  return result;
};

/**
 * myers diff
 *
 * @param oldText 
 * @param newText 
 * @returns 
 */
export const myersDiff = (oldText: string, newText: string): string[] => {
  // Split both texts into lines
  const oldLines = oldText.split('\n');
  const newLines = newText.split('\n');

  // Get the longest common subsequence of lines
  const lcs = longestCommonSubsequence(oldLines, newLines);

  // Initialize the array to store diff results
  const diff: string[] = [];

  // Initialize indices for old text, new text, and LCS
  let oldIndex = 0;
  let newIndex = 0;
  let lcsIndex = 0;

  // Iterate through all lines of both texts
  while (oldIndex < oldLines.length || newIndex < newLines.length) {
    if (
      lcsIndex < lcs.length &&
      oldLines[oldIndex] === lcs[lcsIndex] &&
      newLines[newIndex] === lcs[lcsIndex]
    ) {
      // If the line is in LCS, it's unchanged
      diff.push(`  ${oldLines[oldIndex]}`);
      oldIndex++;
      newIndex++;
      lcsIndex++;
    } else if (
      newIndex < newLines.length &&
      (lcsIndex >= lcs.length || newLines[newIndex] !== lcs[lcsIndex])
    ) {
      // If the line is in new text but not in LCS, it's an addition
      diff.push(`+ ${newLines[newIndex]}`);
      newIndex++;
    } else {
      // If the line is in old text but not in LCS, it's a deletion
      diff.push(`- ${oldLines[oldIndex]}`);
      oldIndex++;
    }
  }

  return diff;
};