export enum EditOperation {
  Insert = "insert",
  Delete = "delete",
  Edit = "edit",
  None = "none",
}

interface Diff {
  old: string;
  new: string;
}

interface Edit {
  operation: EditOperation;
  diff: Diff;
}

export const calculateLevenshteinOperations = (
  str1: string,
  str2: string
): Edit[] => {
  const len1 = str1.length;
  const len2 = str2.length;
  const dp: number[][] = Array.from({ length: len1 + 1 }, () =>
    Array(len2 + 1).fill(0)
  );

  // Initialize DP table
  for (let i = 0; i <= len1; i++) dp[i][0] = i;
  for (let j = 0; j <= len2; j++) dp[0][j] = j;

  // Fill DP table
  for (let i = 1; i <= len1; i++) {
    for (let j = 1; j <= len2; j++) {
      const cost = str1[i - 1] === str2[j - 1] ? 0 : 1;
      dp[i][j] = Math.min(
        dp[i - 1][j] + 1, // Deletion
        dp[i][j - 1] + 1, // Insertion
        dp[i - 1][j - 1] + cost // Substitution (Edit)
      );
    }
  }

  // Backtrack to find operations
  let operations: Edit[] = [];
  let i = len1,
    j = len2;
  while (i > 0 || j > 0) {
    if (
      i > 0 &&
      j > 0 &&
      dp[i][j] === dp[i - 1][j - 1] &&
      str1[i - 1] === str2[j - 1]
    ) {
      // No operation needed
      operations.unshift({
        operation: EditOperation.None,
        diff: { old: str1[i - 1], new: str2[j - 1] },
      });
      i--;
      j--;
    } else if (i > 0 && dp[i][j] === dp[i - 1][j] + 1) {
      // Delete operation
      operations.unshift({
        operation: EditOperation.Delete,
        diff: { old: str1[i - 1], new: "" },
      });
      i--;
    } else if (j > 0 && dp[i][j] === dp[i][j - 1] + 1) {
      // Insert operation
      operations.unshift({
        operation: EditOperation.Insert,
        diff: { old: "", new: str2[j - 1] },
      });
      j--;
    } else if (i > 0 && j > 0) {
      // Edit operation
      operations.unshift({
        operation: EditOperation.Edit,
        diff: { old: str1[i - 1], new: str2[j - 1] },
      });
      i--;
      j--;
    }
  }

  // Simplify consecutive "none" operations into single operations
  const simplifiedOperations = operations.reduce<Edit[]>((acc, op) => {
    if (
      acc.length > 0 &&
      op.operation === EditOperation.None &&
      acc[acc.length - 1].operation === EditOperation.None
    ) {
      acc[acc.length - 1].diff.old += op.diff.old;
      acc[acc.length - 1].diff.new += op.diff.new;
    } else {
      acc.push(op);
    }
    return acc;
  }, []);

  return simplifiedOperations;
};