diff.ltl

// ─── Section Name ────────────────────────────────────────
// ═══════════════════════════════════════════════════════════
// LATERALUS — Title
// Description line
// ═══════════════════════════════════════════════════════════
// ═══════════════════════════════════════════════════════════
-- stdlib/diff.ltl


// ─── Diff Module ────────────────────────────────────────
//
// This module provides the Myers diff algorithm for computing edit distance and line-level diffs between two strings.

module Diff {

  // ────────────────────────────────────────────────────────────────
  // ─── Struct Definition: EditDistance ──────────────────────────────
  //
  // Represents an edit distance between two strings.
  //
  // ┌───────────┬────────────────────────────────────────────────────┐
  // │ Field    │ Type                                          │
  // ├── distance│ int                                       │
  // └───────────┴────────────────────────────────────────────────────┘

  struct EditDistance {
    distance: int
  }

  // ────────────────────────────────────────────────────────────────
  // ─── Function: edit_distance ───────────────────────────────────────
  //
  // Computes the edit distance between two strings using the Myers algorithm.
  //
  // Args:
  //     a (str): First string.
  //     b (str): Second string.
  //
  // Returns:
  //     EditDistance: An edit distance object containing the minimum edit distance.

  fn edit_distance(a: str, b: str) -> EditDistance {
    let mut dp = map<list<int>>{(0, 0) => 0};
    let mut prev = map<list<int>>((0, 0) => None);

    for i in range(len(a)) {
      for j in range(len(b)) {
        if a[i] == b[j] {
          let new_dp = dp[(i + 1, j + 1)];
          dp[(i + 1, j + 1)] = new_dp;
          prev[(i + 1, j + 1)] = Some((new_dp, (i, j)));
        } else {
          let cost = abs(i - j);
          let new_dp = dp[(i + 1, j + 1)];
          dp[(i + 1, j + 1)] = min(new_dp, new_dp + cost);
          prev[(i + 1, j + 1)] = Some((min(new_dp, new_dp + cost), (i, j)));
        }
      }
    }

    // Reconstruct the edit sequence