/* src/cli/skeleton/src/extract/tree_diff.rs */

use super::dom::{DomNode, fingerprint};

#[derive(Debug, PartialEq)]
pub(super) enum DiffOp {
  Identical(usize, usize),
  Modified(usize, usize),
  OnlyLeft(usize),
  OnlyRight(usize),
}

/// Align two child lists using fingerprint-based LCS, then greedy tag matching.
/// Output is ordered for left-to-right consumption: OnlyLeft before OnlyRight
/// at each position, maintaining relative order of both sequences.
pub(super) fn diff_children(a: &[DomNode], b: &[DomNode]) -> Vec<DiffOp> {
  let fp_a: Vec<String> = a.iter().map(fingerprint).collect();
  let fp_b: Vec<String> = b.iter().map(fingerprint).collect();

  let n = fp_a.len();
  let m = fp_b.len();

  // Phase 1: LCS on fingerprints
  let mut dp = vec![vec![0u32; m + 1]; n + 1];
  for i in (0..n).rev() {
    for j in (0..m).rev() {
      dp[i][j] =
        if fp_a[i] == fp_b[j] { dp[i + 1][j + 1] + 1 } else { dp[i + 1][j].max(dp[i][j + 1]) };
    }
  }

  let mut lcs_pairs: Vec<(usize, usize)> = Vec::new();
  let (mut i, mut j) = (0, 0);
  while i < n && j < m {
    if fp_a[i] == fp_b[j] {
      lcs_pairs.push((i, j));
      i += 1;
      j += 1;
    } else if dp[i + 1][j] >= dp[i][j + 1] {
      i += 1;
    } else {
      j += 1;
    }
  }

  let mut matched_a = vec![false; n];
  let mut matched_b = vec![false; m];
  for &(ai, bj) in &lcs_pairs {
    matched_a[ai] = true;
    matched_b[bj] = true;
  }

  // Phase 2: greedy tag matching on remaining unmatched nodes
  let unmatched_b: Vec<usize> = (0..m).filter(|&j| !matched_b[j]).collect();
  let mut used_b = vec![false; unmatched_b.len()];
  let mut modified_pairs: Vec<(usize, usize)> = Vec::new();

  for ai in 0..n {
    if matched_a[ai] {
      continue;
    }
    if let DomNode::Element { tag: ref tag_a, .. } = a[ai] {
      for (kb, &bj) in unmatched_b.iter().enumerate() {
        if used_b[kb] {
          continue;
        }
        if let DomNode::Element { tag: ref tag_b, .. } = b[bj]
          && tag_a == tag_b
        {
          used_b[kb] = true;
          matched_a[ai] = true;
          matched_b[bj] = true;
          modified_pairs.push((ai, bj));
          break;
        }
      }
    }
  }

  // Collect all matched pairs sorted by a-index: (a_idx, b_idx, is_identical)
  let mut pairs: Vec<(usize, usize, bool)> = Vec::new();
  for &(ai, bj) in &lcs_pairs {
    pairs.push((ai, bj, true));
  }
  for &(ai, bj) in &modified_pairs {
    pairs.push((ai, bj, false));
  }
  pairs.sort_by_key(|&(ai, _, _)| ai);

  // Phase 3: interleave to build ordered output.
  // Walk matched pairs in order; before each pair, emit unmatched a-nodes
  // then unmatched b-nodes in that gap.
  let mut result = Vec::new();
  let mut prev_a = 0usize;
  let mut prev_b = 0usize;

  for &(ai, bj, is_identical) in &pairs {
    // Emit unmatched a-nodes in [prev_a, ai)
    for (idx, &m) in matched_a.iter().enumerate().take(ai).skip(prev_a) {
      if !m {
        result.push(DiffOp::OnlyLeft(idx));
      }
    }
    // Emit unmatched b-nodes in [prev_b, bj)
    for (idx, &m) in matched_b.iter().enumerate().take(bj).skip(prev_b) {
      if !m {
        result.push(DiffOp::OnlyRight(idx));
      }
    }
    // Emit the matched pair
    if is_identical {
      result.push(DiffOp::Identical(ai, bj));
    } else {
      result.push(DiffOp::Modified(ai, bj));
    }
    prev_a = ai + 1;
    prev_b = bj + 1;
  }

  // Emit remaining unmatched after the last pair
  for (idx, &m) in matched_a.iter().enumerate().take(n).skip(prev_a) {
    if !m {
      result.push(DiffOp::OnlyLeft(idx));
    }
  }
  for (idx, &matched) in matched_b.iter().enumerate().take(m).skip(prev_b) {
    if !matched {
      result.push(DiffOp::OnlyRight(idx));
    }
  }

  result
}

#[cfg(test)]
mod tests {
  use super::*;

  fn el(tag: &str, children: Vec<DomNode>) -> DomNode {
    DomNode::Element { tag: tag.to_string(), attrs: String::new(), children, self_closing: false }
  }

  fn text(s: &str) -> DomNode {
    DomNode::Text(s.to_string())
  }

  fn span(content: &str) -> DomNode {
    el("span", vec![text(content)])
  }

  #[test]
  fn diff_identical_children() {
    let nodes = vec![span("Hello"), span("World")];
    let result = diff_children(&nodes, &nodes);
    assert_eq!(result, vec![DiffOp::Identical(0, 0), DiffOp::Identical(1, 1)]);
  }

  #[test]
  fn diff_extra_in_left() {
    let a = vec![span("A"), span("B"), span("C")];
    let b = vec![span("A"), span("C")];
    let result = diff_children(&a, &b);
    assert_eq!(
      result,
      vec![DiffOp::Identical(0, 0), DiffOp::OnlyLeft(1), DiffOp::Identical(2, 1),]
    );
  }

  #[test]
  fn diff_extra_in_right() {
    let a = vec![span("A"), span("C")];
    let b = vec![span("A"), span("B"), span("C")];
    let result = diff_children(&a, &b);
    assert_eq!(
      result,
      vec![DiffOp::Identical(0, 0), DiffOp::OnlyRight(1), DiffOp::Identical(1, 2),]
    );
  }

  #[test]
  fn diff_replacement() {
    let a = vec![span("Hello")];
    let b = vec![span("Goodbye")];
    let result = diff_children(&a, &b);
    assert_eq!(result, vec![DiffOp::Modified(0, 0)]);
  }

  #[test]
  fn diff_sibling_conditionals() {
    let a = vec![span("Admin"), span("Welcome")];
    let b = vec![span("Welcome")];
    let result = diff_children(&a, &b);
    assert_eq!(result, vec![DiffOp::OnlyLeft(0), DiffOp::Identical(1, 0)]);
  }

  #[test]
  fn diff_sibling_conditionals_reversed() {
    let a = vec![span("Admin"), span("Welcome")];
    let b = vec![span("Admin")];
    let result = diff_children(&a, &b);
    assert_eq!(result, vec![DiffOp::Identical(0, 0), DiffOp::OnlyLeft(1)]);
  }

  #[test]
  fn diff_if_else_pair() {
    let a = vec![el("b", vec![text("Welcome")])];
    let b = vec![el("i", vec![text("Login")])];
    let result = diff_children(&a, &b);
    assert_eq!(result, vec![DiffOp::OnlyLeft(0), DiffOp::OnlyRight(0)]);
  }

  #[test]
  fn diff_empty_lists() {
    let result = diff_children(&[], &[]);
    assert!(result.is_empty());
  }

  #[test]
  fn diff_nested_modified() {
    let a = vec![el("div", vec![span("Old")])];
    let b = vec![el("div", vec![span("New")])];
    let result = diff_children(&a, &b);
    assert_eq!(result, vec![DiffOp::Modified(0, 0)]);
  }

  #[test]
  fn diff_empty_left_nonempty_right() {
    let b = vec![el("div", vec![])];
    let result = diff_children(&[], &b);
    assert_eq!(result, vec![DiffOp::OnlyRight(0)]);
  }

  #[test]
  fn diff_nonempty_left_empty_right() {
    let a = vec![el("div", vec![])];
    let result = diff_children(&a, &[]);
    assert_eq!(result, vec![DiffOp::OnlyLeft(0)]);
  }

  #[test]
  fn diff_completely_disjoint() {
    let a = vec![el("div", vec![]), el("span", vec![])];
    let b = vec![el("p", vec![]), el("a", vec![])];
    let result = diff_children(&a, &b);
    assert_eq!(
      result,
      vec![DiffOp::OnlyLeft(0), DiffOp::OnlyLeft(1), DiffOp::OnlyRight(0), DiffOp::OnlyRight(1)]
    );
  }

  #[test]
  fn diff_multiple_modified() {
    // Same tags but different children -> Modified pairs
    let a = vec![el("div", vec![text("old1")]), el("span", vec![text("old2")])];
    let b = vec![el("div", vec![text("new1")]), el("span", vec![text("new2")])];
    let result = diff_children(&a, &b);
    assert_eq!(result, vec![DiffOp::Modified(0, 0), DiffOp::Modified(1, 1)]);
  }
}
