1use std::cmp;
2
3#[derive(Debug, PartialEq)]
4pub enum DiffResult<T: PartialEq + Clone> {
5 Removed(DiffElement<T>),
6 Common(DiffElement<T>),
7 Added(DiffElement<T>),
8}
9
10#[derive(Debug, PartialEq)]
11pub struct DiffElement<T: PartialEq + Clone> {
12 pub old_index: Option<usize>,
13 pub new_index: Option<usize>,
14 pub data: T,
15}
16
17fn create_table<T: PartialEq + Clone>(old: &[T], new: &[T]) -> Vec<Vec<u32>> {
18 let new_len = new.len();
19 let old_len = old.len();
20 let mut table = vec![vec![0; old_len + 1]; new_len + 1];
21 for (i, _) in new.iter().enumerate() {
22 let i = new_len - i - 1;
23 table[i][old_len] = 0;
24 for (j, _) in old.iter().enumerate() {
25 let j = old_len - j - 1;
26 table[i][j] = if new[i] == old[j] {
27 table[i + 1][j + 1] + 1
28 } else {
29 cmp::max(table[i + 1][j], table[i][j + 1])
30 }
31 }
32 }
33 table
34}
35
36pub fn diff<T: PartialEq + Clone>(old: &[T], new: &[T]) -> Vec<DiffResult<T>> {
37 let mut result: Vec<DiffResult<T>> = Vec::new();
38 let new_len = new.len();
39 let old_len = old.len();
40
41 if new_len == 0 {
42 let mut o = 0;
43 while o < old_len {
44 result.push(DiffResult::Removed(DiffElement {
45 old_index: Some(o),
46 new_index: None,
47 data: old[o].clone(),
48 }));
49 o += 1;
50 }
51 return result;
52 } else if old_len == 0 {
53 let mut n = 0;
54 while n < new_len {
55 result.push(DiffResult::Added(DiffElement {
56 old_index: None,
57 new_index: Some(n),
58 data: new[n].clone(),
59 }));
60 n += 1;
61 }
62 return result;
63 } else {
64 let mut o = 0;
65 let mut n = 0;
66 let common_prefix = old.iter().zip(new).take_while(|p| p.0 == p.1);
67 let prefix_size = common_prefix.count();
68 let common_suffix = old.iter()
69 .rev()
70 .zip(new.iter().rev())
71 .take(cmp::min(old_len, new_len) - prefix_size)
72 .take_while(|p| p.0 == p.1);
73 let suffix_size = common_suffix.count();
74 let table = create_table(&old[prefix_size..(old_len - suffix_size)],
75 &new[prefix_size..(new_len - suffix_size)]);
76 let new_len = new_len - prefix_size - suffix_size;
77 let old_len = old_len - prefix_size - suffix_size;
78
79 let mut prefix_index = 0;
81 while prefix_index < prefix_size {
82 result.push(DiffResult::Common(DiffElement {
83 old_index: Some(prefix_index),
84 new_index: Some(prefix_index),
85 data: old[prefix_index].clone(),
86 }));
87 prefix_index += 1;
88 }
89
90
91 loop {
92 if n >= new_len || o >= old_len {
93 break;
94 }
95 let new_index = n + prefix_size;
96 let old_index = o + prefix_size;
97 if new[new_index] == old[old_index] {
98 result.push(DiffResult::Common(DiffElement {
99 old_index: Some(old_index),
100 new_index: Some(new_index),
101 data: new[new_index].clone(),
102 }));
103 n += 1;
104 o += 1;
105 } else if table[n + 1][o] >= table[n][o + 1] {
106 result.push(DiffResult::Added(DiffElement {
107 old_index: None,
108 new_index: Some(new_index),
109 data: new[new_index].clone(),
110 }));
111 n += 1;
112 } else {
113 result.push(DiffResult::Removed(DiffElement {
114 old_index: Some(old_index),
115 new_index: None,
116 data: old[old_index].clone(),
117 }));
118 o += 1;
119 }
120 }
121 while n < new_len {
122 let new_index = n + prefix_size;
123 result.push(DiffResult::Added(DiffElement {
124 old_index: None,
125 new_index: Some(new_index),
126 data: new[new_index].clone(),
127 }));
128 n += 1;
129 }
130 while o < old_len {
131 let old_index = o + prefix_size;
132 result.push(DiffResult::Removed(DiffElement {
133 old_index: Some(old_index),
134 new_index: None,
135 data: old[old_index].clone(),
136 }));
137 o += 1;
138 }
139
140 let mut suffix_index = 0;
142 while suffix_index < suffix_size {
143 let old_index = suffix_index + old_len + prefix_size;
144 let new_index = suffix_index + new_len + prefix_size;
145 result.push(DiffResult::Common(DiffElement {
146 old_index: Some(old_index),
147 new_index: Some(new_index),
148 data: old[old_index].clone(),
149 }));
150 suffix_index += 1;
151 }
152 }
153 result
154}
155
156
157#[test]
158fn shoud_create_table_with_numbers() {
159 let table = create_table(&vec![2, 3], &vec![0, 1, 2]);
160 let expected = vec![vec![1, 0, 0], vec![1, 0, 0], vec![1, 0, 0], vec![0, 0, 0]];
161 assert_eq!(table, expected);
162}
163
164#[test]
165fn shoud_create_table_with_char() {
166 let table = create_table(&vec!["a", "d"], &vec!["a", "b", "c"]);
167 let expected = vec![vec![1, 0, 0], vec![0, 0, 0], vec![0, 0, 0], vec![0, 0, 0]];
168 assert_eq!(table, expected);
169}
170
171#[test]
172fn shoud_create_table_with_string() {
173 let table = create_table(&vec!["abc", "bcd"], &vec!["abc", "bcd", "c"]);
174 let expected = vec![vec![2, 1, 0], vec![1, 1, 0], vec![0, 0, 0], vec![0, 0, 0]];
175 assert_eq!(table, expected);
176}
177
178#[test]
179fn shoud_create_diff_result_with_added() {
180 let result = diff(&vec!["abc", "c"], &vec!["abc", "bcd", "c"]);
181 let expected = vec![DiffResult::Common(DiffElement {
182 old_index: Some(0),
183 new_index: Some(0),
184 data: "abc",
185 }),
186 DiffResult::Added(DiffElement {
187 old_index: None,
188 new_index: Some(1),
189 data: "bcd",
190 }),
191 DiffResult::Common(DiffElement {
192 old_index: Some(1),
193 new_index: Some(2),
194 data: "c",
195 })];
196
197 assert_eq!(result, expected);
198}
199
200
201#[test]
202fn shoud_create_diff_result_with_removed() {
203 let result = diff(&vec!["abc", "bcd", "c"], &vec!["abc", "c"]);
204 let expected = vec![DiffResult::Common(DiffElement {
205 old_index: Some(0),
206 new_index: Some(0),
207 data: "abc",
208 }),
209 DiffResult::Removed(DiffElement {
210 old_index: Some(1),
211 new_index: None,
212 data: "bcd",
213 }),
214 DiffResult::Common(DiffElement {
215 old_index: Some(2),
216 new_index: Some(1),
217 data: "c",
218 })];
219 assert_eq!(result, expected);
220}
221
222#[test]
223fn shoud_create_diff_result_without_new() {
224 let result = diff(&vec!["abc", "bcd", "c"], &vec![]);
225 let expected = vec![DiffResult::Removed(DiffElement {
226 old_index: Some(0),
227 new_index: None,
228 data: "abc",
229 }),
230 DiffResult::Removed(DiffElement {
231 old_index: Some(1),
232 new_index: None,
233 data: "bcd",
234 }),
235 DiffResult::Removed(DiffElement {
236 old_index: Some(2),
237 new_index: None,
238 data: "c",
239 })];
240 assert_eq!(result, expected);
241}
242
243#[test]
244fn shoud_create_diff_result_without_old() {
245 let result = diff(&vec![], &vec!["abc", "bcd", "c"]);
246 let expected = vec![DiffResult::Added(DiffElement {
247 old_index: None,
248 new_index: Some(0),
249 data: "abc",
250 }),
251 DiffResult::Added(DiffElement {
252 old_index: None,
253 new_index: Some(1),
254 data: "bcd",
255 }),
256 DiffResult::Added(DiffElement {
257 old_index: None,
258 new_index: Some(2),
259 data: "c",
260 })];
261 assert_eq!(result, expected);
262}
263
264#[test]
265fn shoud_create_empty_result_with_empty_input() {
266 let result = diff(&vec![0u8; 0], &vec![0u8; 0]);
267 let expected = vec![];
268 assert_eq!(result, expected);
269}