Function longestCommonSubsequence

packages/2d/src/lib/code/diff.ts:120–155

* Takes a map from the unique common lines between two arrays and determines * the longest common subsequence. * * @see uniqueCommon * * @param abMap - The map of unique common lines between two arrays. * @returns An array of objects containing the indices of the longest common

(
    abMap: Map<string, Subsequence>,
  )

   * subsequence.
   */
  function longestCommonSubsequence(
    abMap: Map<string, Subsequence>,
  ): Subsequence[] {
    const jagged: [Subsequence][] = [];

    abMap.forEach(value => {
      let i = 0;
      while (jagged[i] && jagged[i].at(-1)!.bIndex < value.bIndex) {
        i++;
      }

      if (i > 0) {
        value.prev = jagged[i - 1].at(-1);
      }

      if (!jagged[i]) {
        jagged[i] = [value];
      } else {
        jagged[i].push(value);
      }
    });

    // Pull out the longest common subsequence
    let lcs: Subsequence[] = [];

    if (jagged.length > 0) {
      lcs = [jagged.at(-1)!.at(-1)!];
      let cursor = lcs.at(-1);
      while (cursor?.prev) {
        cursor = cursor.prev;
        lcs.push(cursor);
      }
    }

    return lcs.reverse();
  }

  /**
   * Keeps track of the aLines that have been deleted, are shared between aLines