use std::collections::HashSet;
use std::hash::Hash;
use crate::{myers, Diff};
#[derive(Debug)]
enum Elems<T> {
UniqueRun(Vec<T>),
NormalElem(T),
}
struct MapDiff<'a, D> {
elems1: &'a [usize],
elems2: &'a [usize],
diff: D,
e0: usize,
f0: usize,
}
fn create_elems<'a, T: Hash + Eq>(v: &'a [T], w: &'a [T]) -> (Vec<usize>, Vec<Elems<&'a T>>) {
let hs: HashSet<_> = w.iter().collect();
let mut elems = Vec::new();
let mut ix_map = Vec::new();
for (i, elem) in v.iter().enumerate() {
if i == 0 || hs.contains(elem) {
elems.push(Elems::NormalElem(elem));
ix_map.push(i);
// TODO: resurrect the last UniqueRun if it was too short
} else {
let l = elems.len();
if let Elems::UniqueRun(e_vec) = &mut elems[l - 1] {
e_vec.push(elem);
} else {
elems.push(Elems::UniqueRun(Vec::new()));
ix_map.push(i);
}
}
}
ix_map.push(v.len());
(ix_map, elems)
}
impl<T: PartialEq> PartialEq for Elems<T> {
fn eq(&self, other: &Self) -> bool {
match (self, other) {
(Self::NormalElem(x), Self::NormalElem(y)) => x == y,
_ => false,
}
}
}
impl<'a, D> MapDiff<'a, D> {
pub fn new(diff: D, elems1: &'a [usize], elems2: &'a [usize], e0: usize, f0: usize) -> Self {
Self {
diff,
elems1,
elems2,
e0,
f0,
}
}
}
impl<'a, D: Diff> Diff for MapDiff<'a, D> {
type Error = D::Error;
fn equal(&mut self, old: usize, new: usize, len: usize) -> Result<(), D::Error> {
let old2 = self.elems1[old] + self.e0;
let new2 = self.elems2[new] + self.f0;
let len2 = self.elems1[old + len] - self.elems1[old];
self.diff.equal(old2, new2, len2)
}
fn delete(&mut self, old: usize, len: usize, new: usize) -> Result<(), D::Error> {
let old2 = self.elems1[old] + self.e0;
let len2 = self.elems1[old + len] - self.elems1[old];
let new2 = self.elems2[new] + self.f0;
self.diff.delete(old2, len2, new2)
}
fn insert(&mut self, old: usize, new: usize, new_len: usize) -> Result<(), D::Error> {
let old2 = self.elems1[old] + self.e0;
let new2 = self.elems2[new] + self.f0;
let new_len2 = self.elems2[new + new_len] - self.elems2[new];
self.diff.insert(old2, new2, new_len2)
}
fn replace(
&mut self,
old: usize,
old_len: usize,
new: usize,
new_len: usize,
) -> Result<(), D::Error> {
let old2 = self.elems1[old] + self.e0;
let old_len2 = self.elems1[old + old_len] - self.elems1[old];
let new2 = self.elems2[new] + self.f0;
let new_len2 = self.elems2[new + new_len] - self.elems2[new];
self.diff.replace(old2, old_len2, new2, new_len2)
}
fn finish(&mut self) -> Result<(), D::Error> {
self.diff.finish()
}
}
/// Optimized Myers' diff algorithm.
///
/// Repeated sequences of unique elements are merged into one.
pub fn diff<T, D: Diff>(
d: &mut D,
e: &[T],
e0: usize,
e1: usize,
f: &[T],
f0: usize,
f1: usize,
) -> Result<(), D::Error>
where
T: Eq + Hash + std::fmt::Debug,
{
let (ivec1, st1) = create_elems(&e[e0..e1], &f[f0..f1]);
let (ivec2, st2) = create_elems(&f[f0..f1], &e[e0..e1]);
let mut diff = MapDiff::new(d, &ivec1, &ivec2, e0, f0);
myers::diff(&mut diff, &st1, 0, st1.len(), &st2, 0, st2.len())
}