#[cfg(test)]
mod tests;
const MAX_DIFFERENCES: isize = 500;
#[derive(Clone, Copy, Debug, Default, PartialEq)]
pub enum Mark {
#[default]
Same,
Added,
Modified,
RemovedBelow,
RemovedAbove,
}
pub fn marks(old: &[String], new: &[String]) -> Vec<Mark> {
let prefix = old.iter().zip(new).take_while(|(a, b)| a == b).count();
let suffix = old[prefix..]
.iter()
.rev()
.zip(new[prefix..].iter().rev())
.take_while(|(a, b)| a == b)
.count();
let a = &old[prefix..old.len() - suffix];
let b = &new[prefix..new.len() - suffix];
let (a_kept, b_kept) =
unchanged(a, b).unwrap_or_else(|| (vec![false; a.len()], vec![false; b.len()]));
let mut marks = vec![Mark::Same; new.len()];
let (mut i, mut j) = (0, 0);
while i < a.len() || j < b.len() {
if i < a.len() && j < b.len() && a_kept[i] && b_kept[j] {
i += 1;
j += 1;
continue;
}
let (removed_from, added_from) = (i, j);
while i < a.len() && !a_kept[i] {
i += 1;
}
while j < b.len() && !b_kept[j] {
j += 1;
}
let at = prefix + added_from;
if j > added_from {
let mark = if i > removed_from { Mark::Modified } else { Mark::Added };
marks[at..prefix + j].fill(mark);
} else if at > 0 {
if marks[at - 1] == Mark::Same {
marks[at - 1] = Mark::RemovedBelow;
}
} else if let Some(first) = marks.first_mut() {
*first = Mark::RemovedAbove;
}
}
marks
}
fn unchanged(a: &[String], b: &[String]) -> Option<(Vec<bool>, Vec<bool>)> {
let (n, m) = (a.len() as isize, b.len() as isize);
let limit = MAX_DIFFERENCES.min(n + m);
let middle = limit + 1;
let mut reach = vec![0isize; (2 * limit + 3) as usize];
let at = |k: isize| (middle + k) as usize;
let mut history: Vec<Vec<isize>> = Vec::new();
for d in 0..=limit {
history.push(reach[at(-d - 1)..=at(d + 1)].to_vec());
for k in (-d..=d).step_by(2) {
let down = k == -d || (k != d && reach[at(k - 1)] < reach[at(k + 1)]);
let mut x = if down { reach[at(k + 1)] } else { reach[at(k - 1)] + 1 };
let mut y = x - k;
while x < n && y < m && a[x as usize] == b[y as usize] {
x += 1;
y += 1;
}
reach[at(k)] = x;
if x >= n && y >= m {
return Some(walk_back(&history, n, m));
}
}
}
None
}
fn walk_back(history: &[Vec<isize>], n: isize, m: isize) -> (Vec<bool>, Vec<bool>) {
let mut a_kept = vec![false; n as usize];
let mut b_kept = vec![false; m as usize];
let (mut x, mut y) = (n, m);
for d in (0..history.len() as isize).rev() {
let before = |k: isize| history[d as usize][(k + d + 1) as usize];
let k = x - y;
let (from_x, from_y) = if d == 0 {
(0, 0)
} else {
let down = k == -d || (k != d && before(k - 1) < before(k + 1));
let from_k = if down { k + 1 } else { k - 1 };
(before(from_k), before(from_k) - from_k)
};
while x > from_x && y > from_y {
x -= 1;
y -= 1;
a_kept[x as usize] = true;
b_kept[y as usize] = true;
}
(x, y) = (from_x, from_y);
}
(a_kept, b_kept)
}