fn lcs<'a, T: Eq + 'a, I: ExactSizeIterator<Item = &'a T>>(
    x: impl ExactSizeIterator<Item = &'a T>,
    y: impl Fn() -> I
) -> Vec<usize> {
    let width = x.len() + 1;
    let mut c = vec![0; width * (y().len() + 1)];

    for (i, x) in x.enumerate() {
        for (j, y) in y().enumerate() {
            c[(i + 1) * width + (j + 1)] = if x == y {
                c[i * width + j] + 1
            } else {
                c[(i + 1) * width + j].max(c[i * width + (j + 1)])
            };
        }
    }

    c
}

/*
// Original Non-iter version
fn lcs<T: Eq>(x: &[T], y: &[T]) -> Vec<usize> {
    let width = (x.len() + 1);
    let mut c = vec![0; width * (y.len() + 1)];

    for i in 0..x.len() {
        for j in 0..y.len() {
            c[(i + 1) * width + (j + 1)] = if x[i] == y[j] {
                c[i * width + j] + 1
            } else {
                c[(i + 1) * width + j].max(c[i * width + (j + 1)])
            };
        }
    }

    c
}
*/

#[derive(Debug)]
enum Edit<'a, T> {
    Copy(&'a T),
    Add(&'a T),
    Remove(&'a T),
}

// TODO: Convert to iter version like above
fn diff<'a, T: Eq>(
    c: &'a [usize], x: &'a [T], y: &'a [T], i: usize, j: usize, x_len: usize, y_len: usize
) -> Box<dyn Iterator<Item = Edit<'a, T>> + 'a> {
    if i > 0 && j > 0 && x[i - 1] == y[j - 1] {
        Box::new(diff(c, x, y, i - 1, j - 1, x_len, y_len)
            .chain(std::iter::once(Edit::Copy(&x[i - 1]))))
    } else if j > 0 && (i == 0 || c[i * (x_len + 1) + j - 1] >= c[(i - 1) * (x_len + 1) + j]) {
        Box::new(diff(c, x, y, i, j - 1, x_len, y_len)
            .chain(std::iter::once(Edit::Add(&y[j - 1]))))
    } else if i > 0 && (j == 0 || c[i * (x_len + 1) + j - 1] < c[(i - 1) * (x_len + 1) + j]) {
        Box::new(diff(c, x, y, i - 1, j, x_len, y_len)
            .chain(std::iter::once(Edit::Remove(&x[i - 1]))))
    } else {
        Box::new(std::iter::empty())
    }
}

fn main() {
    // TODO: Non-raw
    let left = b"XMJYAUZ";
    let right = b"MZJAWXU";

    let c = lcs(left.iter(), || right.iter());

    println!("{:?}", diff(&c, left, right, left.len(), right.len(), left.len(), right.len())
        .collect::<Vec<_>>());
}