1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101

use std::cmp::{max, min};
use Diff;

fn modulo(a: isize, b: usize) -> usize {
    let b = b as isize;
    (((a % b) + b) % b) as usize
}

#[test]
fn test_modulo() {
    assert_eq!(modulo(-11, 10), 9);
    assert_eq!(modulo(23, 7), 2);
    assert_eq!(modulo(-12, 6), 0);
}

/// Myers' diff algorithm.
pub fn diff<A, B: PartialEq<A>, D: Diff>(d: &mut D, e: &[A], f: &[B]) -> Result<(), D::Error> {
    diff_offsets(d, e, f, 0, 0)?;
    d.finish()
}

pub(crate) fn diff_offsets<D: Diff + ?Sized, A, B: PartialEq<A>>(
    diff: &mut D,
    e: &[A],
    f: &[B],
    i: usize,
    j: usize,
) -> Result<(), D::Error> {
    let n = e.len();
    let m = f.len();
    let l = (n + m) as isize;
    let z = (2 * min(n, m) + 2) as usize;
    if n > 0 && m > 0 {
        let w = n as isize - m as isize;
        let mut g = vec![0; z as usize];
        let mut p = vec![0; z as usize];
        for h in 0..=(l / 2 + l % 2) {
            macro_rules! search {
                ($e: expr, $c: expr, $d: expr) => {
                    let (k0, k1) = {
                        let (m, n) = (m as isize, n as isize);
                        (-(h - 2*max(0, h - m)), h-2*max(0, h-n)+1)
                    };
                    for k in (k0..k1).step_by(2) {
                        let mut a: usize = if k == -h || k != h && $c[modulo(k-1, z)] < $c[modulo(k+1, z)] {
                            $c[modulo(k+1, z)]
                        } else {
                            $c[modulo(k-1, z)] + 1
                        };
                        let mut b = (a as isize - k) as usize;
                        let (s, t) = (a, b);
                        while a < n && b < m && {
                            let (e_i, f_i) = if $e { (a, b) } else { (n - a - 1, m - b - 1) };
                            f[f_i] == e[e_i]
                        } {
                            a += 1;
                            b += 1;
                        }
                        $c[modulo(k, z)] = a;
                        let bound = if $e { h-1 } else { h };
                        if (l%2 == 1) == $e
                            && w-k >= -bound && w-k <= bound
                            && $c[modulo(k, z)]+$d[modulo(w-k, z)] >= n
                        {
                            let (x, y, u, v) = if $e {
                                (s, t, a, b)
                            } else {
                                (n-a, m-b, n-s, m-t)
                            };
                            if h + bound > 1 || (x != u && y != v) {
                                diff_offsets(diff, &e[0..x], &f[0..y], i, j)?;
                                if x != u {
                                    diff.equal(i + x, j + y, u-x)?;
                                }
                                diff_offsets(diff, &e[u..n], &f[v..m], i+u, j+v)?;
                                return Ok(())
                            } else if m > n {
                                diff.equal(i, j, n)?;
                                diff.insert(i+n, j+n, m-n)?;
                                return Ok(())
                            } else if m < n {
                                diff.equal(i, j, m)?;
                                diff.delete(i+m, n-m)?;
                                return Ok(())
                            } else {
                                return Ok(())
                            }
                        }
                    }
                }
            }
            search!(true, g, p);
            search!(false, p, g);
        }
    } else if n > 0 {
        diff.delete(i, n)?
    } else if m > 0 {
        diff.insert(i, j, m)?
    }
    Ok(())
}