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
use std::cmp;
#[derive(Clone, Debug, PartialEq)]
pub enum Result<T> {
Left(T),
Both(T, T),
Right(T)
}
pub fn slice<'a, T: PartialEq>(left: &'a [T],
right: &'a [T]) -> Vec<Result<&'a T>> {
iter(left.iter(), right.iter())
}
pub fn lines<'a>(left: &'a str, right: &'a str) -> Vec<Result<&'a str>> {
iter(left.lines(), right.lines())
}
pub fn chars<'a>(left: &'a str, right: &'a str) -> Vec<Result<char>> {
iter(left.chars(), right.chars())
}
fn iter<'a, I, T>(left: I, right: I) -> Vec<Result<T>> where
I: Clone + Iterator<Item = T> + DoubleEndedIterator, T: PartialEq
{
let left_count = left.clone().count();
let right_count = right.clone().count();
let min_count = cmp::min(left_count, right_count);
let leading_equals = left.clone()
.zip(right.clone())
.take_while(|p| p.0 == p.1)
.count();
let trailing_equals = left.clone()
.rev()
.zip(right.clone().rev())
.take(min_count - leading_equals)
.take_while(|p| p.0 == p.1)
.count();
let left_diff_size = left_count - leading_equals - trailing_equals;
let right_diff_size = right_count - leading_equals - trailing_equals;
let table: Vec<Vec<u32>> = {
let mut table = vec![vec![0; right_diff_size + 1]; left_diff_size + 1];
let left_skip = left.clone().skip(leading_equals).take(left_diff_size);
let right_skip = right.clone()
.skip(leading_equals)
.take(right_diff_size);
for (i, l) in left_skip.clone().enumerate() {
for (j, r) in right_skip.clone().enumerate() {
table[i+1][j+1] = if l == r {
table[i][j] + 1
} else {
std::cmp::max(table[i][j+1], table[i+1][j])
};
}
}
table
};
let diff = {
let mut diff = Vec::with_capacity(left_diff_size + right_diff_size);
let mut i = left_diff_size;
let mut j = right_diff_size;
let mut li = left.clone().rev().skip(trailing_equals);
let mut ri = right.clone().rev().skip(trailing_equals);
loop {
if j > 0 && (i == 0 || table[i][j] == table[i][j-1]) {
j -= 1;
diff.push(Result::Right(ri.next().unwrap()));
} else if i > 0 && (j == 0 || table[i][j] == table[i-1][j]) {
i -= 1;
diff.push(Result::Left(li.next().unwrap()));
} else if i > 0 && j > 0 {
i -= 1;
j -= 1;
diff.push(Result::Both(li.next().unwrap(), ri.next().unwrap()));
} else {
break
}
}
diff
};
let diff_size = leading_equals + diff.len() + trailing_equals;
let mut total_diff = Vec::with_capacity(diff_size);
total_diff.extend(left.clone()
.zip(right.clone())
.take(leading_equals)
.map(|(l, r)| Result::Both(l, r)));
total_diff.extend(diff.into_iter().rev());
total_diff.extend(left.skip(leading_equals + left_diff_size)
.zip(right.skip(leading_equals + right_diff_size))
.map(|(l, r)| Result::Both(l, r)));
total_diff
}