// @file Wagner-Fischer Edit Distance
// @author Dustin Boston
// @see R. Wagner, and M. Fischer, "The String-to-String Correction Problem,"
//  ACM, vol. 21, no. 1, pp. 168–173, 1974.

// Calculates the edit distance between two strings, indicating how many
// operations (insert, delete, substitute) are required to transform the
// start word into the target word. This function implements the Wagner-Fischer
// algorithm.
export function editDistance(startTerm: string, targetTerm: string): number[][] {
  const distance: number[][] = [[0]];
  for (let i = 1; i <= startTerm.length; i++) {
    distance[i] = [distance[i - 1][0] + cost(startTerm[i - 1], undefined)];
  }

  for (let index = 1; index <= targetTerm.length; index++) {
    distance[0][index] = distance[0][index - 1] + cost(undefined, targetTerm[index - 1]);
  }

  for (let i = 1; i <= startTerm.length; i++) {
    for (let index = 1; index <= targetTerm.length; index++) {
      const m1 = distance[i - 1][index - 1] + cost(startTerm[i - 1], targetTerm[index - 1]);
      const m2 = distance[i - 1][index] + cost(startTerm[i - 1], undefined);
      const m3 = distance[i][index - 1] + cost(undefined, targetTerm[index - 1]);
      distance[i][index] = Math.min(m1, m2, m3);
    }
  }

  return distance;
}

/**
 * Determines the cost of an edit operation between two characters or undefined
 * values. The cost is used in the calculation of the edit distance between
 * two strings.
 *
 * @param a - Char from the first string or undefined if it's an insert/delete.
 * @param b - Char from the second string or undefined if it's an insert/delete.
 * @returns Cost of the edit operation. 0 for no change, 1 for all others.
 * @throws Error if both parameters are undefined.
 */
export function cost(a: string | undefined = undefined, b: string | undefined = undefined): number {
  if (a === b) return 0;
  if (a !== undefined && b !== undefined) return 1; // Change
  if (a === undefined && b !== undefined) return 1; // Insert
  if (a !== undefined && b === undefined) return 1; // Delete
  throw new Error("Invalid cost arguments");
}