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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129

use Diff;

/// A "differ" that combines deletions and insertions to give blocks
/// of maximal length, and replacements when appropriate.
pub struct Replace<D:Diff> {
    d: D,
    del: Option<(usize, usize)>,
    ins: Option<(usize, usize, usize)>,
    eq: Option<(usize, usize, usize)>,
}

impl<D:Diff> Replace<D> {
    pub fn new(d: D) -> Self {
        Replace {
            d,
            del: None,
            ins: None,
            eq: None,
        }
    }
    pub fn into_inner(self) -> D {
        self.d
    }
}


impl<D:Diff> Diff for Replace<D> {
    type Error = D::Error;
    fn equal(&mut self, old: usize, new: usize, len: usize) -> Result<(), D::Error> {
        if let Some((old0, len0)) = self.del.take() {
            if let Some((_, new1, new_len1)) = self.ins.take() {
                self.d.replace(old0, len0, new1, new_len1)?
            } else {
                self.d.delete(old0, len0)?
            }
        } else if let Some((old0, new0, new_len0)) = self.ins.take() {
            self.d.insert(old0, new0, new_len0)?
        }

        if let Some((a, b, c)) = self.eq.take() {
            self.eq = Some((a, b, c + len))
        } else {
            self.eq = Some((old, new, len))
        }
        Ok(())
    }
    fn delete(&mut self, old: usize, len: usize) -> Result<(), D::Error> {
        if let Some((a, b, c)) = self.eq.take() {
            self.d.equal(a, b, c)?
        }
        if let Some((old0, len0)) = self.del.take() {
            assert_eq!(old, old0 + len0);
            self.del = Some((old0, len0+len))
        } else {
            self.del = Some((old, len))
        }
        Ok(())
    }

    fn insert(&mut self, old: usize, new: usize, new_len: usize) -> Result<(), D::Error> {
        if let Some((a, b, c)) = self.eq.take() {
            self.d.equal(a, b, c)?
        }
        if let Some((old1, new1, new_len1)) = self.ins.take() {
            assert_eq!(new1+new_len1, new);
            self.ins = Some((old1, new1, new_len + new_len1))
        } else {
            self.ins = Some((old, new, new_len))
        }
        Ok(())
    }

    fn replace(&mut self, old: usize, old_len: usize, new: usize, new_len: usize) -> Result<(), D::Error> {
        if let Some((a, b, c)) = self.eq.take() {
            self.d.equal(a, b, c)?
        }
        self.d.replace(old, old_len, new, new_len)
    }

    fn finish(&mut self) -> Result<(), D::Error> {
        if let Some((a, b, c)) = self.eq.take() {
            self.d.equal(a, b, c)?
        }
        if let Some((old0, len0)) = self.del.take() {
            if let Some((_, new1, new_len1)) = self.ins.take() {
                self.d.replace(old0, len0, new1, new_len1)?
            } else {
                self.d.delete(old0, len0)?
            }
        } else if let Some((old0, new0, new_len0)) = self.ins.take() {
            self.d.insert(old0, new0, new_len0)?
        }
        self.d.finish()
    }
}

#[test]
fn myers() {
    use myers;
    let a: &[&str] = &[">>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>\n", "a\n", "b\n", "c\n",
                       "================================\n", "d\n", "e\n", "f\n",
                       "<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<\n"];
    let b: &[&str] = &[">>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>\n", "x\n", "b\n", "c\n",
                       "================================\n", "y\n", "e\n", "f\n",
                       "<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<\n"];

    struct D {}
    impl Diff for D {
        type Error = ();
        fn equal(&mut self, o: usize, n: usize, len: usize) -> Result<(), ()> {
            println!("equal {:?} {:?} {:?}", o, n, len);
            Ok(())
        }
        fn delete(&mut self, o: usize, len: usize) -> Result<(), ()> {
            println!("delete {:?} {:?}", o, len);
            Ok(())
        }
        fn insert(&mut self, o: usize, n: usize, len: usize) -> Result<(), ()> {
            println!("insert {:?} {:?} {:?}", o, n, len);
            Ok(())
        }
        fn replace(&mut self, o: usize, l: usize, n: usize, nl: usize) -> Result<(), ()> {
            println!("replace {:?} {:?} {:?} {:?}", o, l, n, nl);
            Ok(())
        }
    }
    let mut d = Replace::new(D {});
    myers::diff(&mut d, a, b).unwrap();
}