1 files changed, 103 insertions, 0 deletions
diff --git a/src/utils/levenshtein.ts b/src/utils/levenshtein.ts
new file mode 100644
index 0000000..87bfd9d
--- /dev/null
+++ b/src/utils/levenshtein.ts
@@ -0,0 +1,103 @@
+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;
+};