1#![cfg_attr(feature = "clippy", feature(plugin))]
2#![cfg_attr(feature = "clippy", plugin(clippy))]
3#![allow(non_snake_case)]
4
5use std::cmp;
6
7const NONE: u8 = 0;
8const REMOVED: u8 = 1;
9const COMMON: u8 = 2;
10const ADDED: u8 = 3;
11
12#[derive(Debug)]
13struct Ctx<'a, T: 'a> {
14 k: isize,
15 base: isize,
16 A: &'a [T],
17 B: &'a [T],
18 ptr: &'a mut usize,
19 routes: &'a mut [usize],
20 diff_types: &'a mut [u8],
21}
22
23#[derive(Debug, PartialEq)]
24pub enum DiffResult {
25 Removed(DiffElement),
26 Common(DiffElement),
27 Added(DiffElement),
28}
29
30#[derive(Debug, PartialEq)]
31pub struct DiffElement {
32 pub old_index: Option<usize>,
33 pub new_index: Option<usize>,
34}
35
36#[derive(Clone)]
37struct FarthestPoint {
38 y: isize,
39 id: usize,
40}
41
42fn back_trace<T: PartialEq + Clone>(
43 A: &[T],
44 B: &[T],
45 current: &FarthestPoint,
46 swapped: bool,
47 routes: &[usize],
48 diff_types: &[u8],
49 prefix_size: usize,
50) -> Vec<DiffResult> {
51 let M = A.len();
52 let N = B.len();
53 let mut result: Vec<DiffResult> = vec![];
54 let mut a = M - 1;
55 let mut b = N - 1;
56 let mut j = routes[current.id];
57 let mut diff_type = diff_types[current.id];
58 loop {
59 if j == 0 && diff_type == NONE {
60 break;
61 }
62 let prev = j;
63 match diff_type {
64 ADDED => {
65 let old_index = if swapped {
66 None
67 } else {
68 Some(a.wrapping_add(prefix_size))
69 };
70 let new_index = if swapped {
71 Some(a.wrapping_add(prefix_size))
72 } else {
73 None
74 };
75 let result_type = if swapped {
76 DiffResult::Added
77 } else {
78 DiffResult::Removed
79 };
80 result.push(result_type(DiffElement {
81 old_index,
82 new_index,
83 }));
84 a = a.wrapping_sub(1);
85 }
86 REMOVED => {
87 let old_index = if swapped {
88 Some(b.wrapping_add(prefix_size))
89 } else {
90 None
91 };
92 let new_index = if swapped {
93 None
94 } else {
95 Some(b.wrapping_add(prefix_size))
96 };
97 let result_type = if swapped {
98 DiffResult::Removed
99 } else {
100 DiffResult::Added
101 };
102 result.push(result_type(DiffElement {
103 old_index,
104 new_index,
105 }));
106 b = b.wrapping_sub(1);
107 }
108 _ => {
109 let i = (Some(a.wrapping_add(prefix_size)), Some(b.wrapping_add(prefix_size)));
110 let (old_index, new_index) = if swapped {
111 (i.1, i.0)
112 } else {
113 i
114 };
115
116 result.push(DiffResult::Common(DiffElement { old_index, new_index }));
117 a = a.wrapping_sub(1);
118 b = b.wrapping_sub(1);
119 }
120 };
121 j = routes[prev];
122 diff_type = diff_types[prev];
123 }
124 result.into_iter().rev().collect()
125}
126
127fn create_fp<T: PartialEq>(fp: &[FarthestPoint], ctx: &mut Ctx<T>) -> FarthestPoint {
128 if ctx.base < 1 as isize {
129 let base = (ctx.base + 1) as usize;
130 let prev = fp[base].id;
131 let y = fp[base].y + 1;
132 *ctx.ptr += 1;
133 ctx.routes[*ctx.ptr] = prev;
134 ctx.diff_types[*ctx.ptr] = REMOVED;
135 return FarthestPoint { y, id: *ctx.ptr };
136 } else if ctx.base + 1 >= fp.len() as isize {
137 let base = (ctx.base - 1) as usize;
138 let prev = fp[base].id;
139 let y = fp[base].y;
140 *ctx.ptr += 1;
141 ctx.routes[*ctx.ptr] = prev;
142 ctx.diff_types[*ctx.ptr] = ADDED;
143 return FarthestPoint { y, id: *ctx.ptr };
144 }
145
146 let slide = &fp[(ctx.base - 1) as usize];
147 let down = &fp[(ctx.base + 1) as usize];
148
149 if slide.y == -1 && down.y == -1 {
150 return FarthestPoint { y: 0, id: 0 };
151 }
152 *ctx.ptr += 1;
153 if down.y == -1 || ctx.k == ctx.A.len() as isize || slide.y > down.y + 1 {
154 let prev = slide.id;
155 let y = slide.y;
156 ctx.routes[*ctx.ptr] = prev;
157 ctx.diff_types[*ctx.ptr] = ADDED;
158 return FarthestPoint { y, id: *ctx.ptr };
159 }
160 let prev = down.id;
161 let y = down.y + 1;
162 ctx.routes[*ctx.ptr] = prev;
163 ctx.diff_types[*ctx.ptr] = REMOVED;
164 FarthestPoint { y, id: *ctx.ptr }
165}
166
167fn snake<T: PartialEq>(fps: &[FarthestPoint], ctx: &mut Ctx<T>) -> FarthestPoint {
168 let M = ctx.A.len() as isize;
169 let N = ctx.B.len() as isize;
170 if ctx.k + N < 0 || M - ctx.k < 0 {
171 return FarthestPoint { y: -1, id: 0 };
172 }
173 let mut fp = create_fp(fps, ctx);
174 while fp.y + ctx.k < M && fp.y < N && ctx.A[(fp.y + ctx.k) as usize] == ctx.B[fp.y as usize] {
175 let prev = fp.id;
176 *ctx.ptr += 1;
177 fp.id = *ctx.ptr;
178 fp.y += 1;
179 ctx.routes[*ctx.ptr] = prev;
180 ctx.diff_types[*ctx.ptr] = COMMON;
181 }
182 fp
183}
184
185pub fn diff<T: PartialEq + Clone>(old: &[T], new: &[T]) -> Vec<DiffResult> {
186 let new_len = new.len();
187 let old_len = old.len();
188 let common_prefix = old.iter().zip(new).take_while(|p| p.0 == p.1);
189 let prefix_size = common_prefix.count();
190 let common_suffix = old
191 .iter()
192 .rev()
193 .zip(new.iter().rev())
194 .take(cmp::min(old_len, new_len) - prefix_size)
195 .take_while(|p| p.0 == p.1);
196 let suffix_size = common_suffix.count();
197 let swapped = old_len < new_len;
198 let sliced_old = &old[prefix_size..(old_len - suffix_size)];
199 let sliced_new = &new[prefix_size..(new_len - suffix_size)];
200
201 let (A, B) = if swapped {
202 (sliced_new, sliced_old)
203 } else {
204 (sliced_old, sliced_new)
205 };
206
207 let mut result: Vec<DiffResult> = Vec::new();
208 let M = A.len();
209 let N = B.len();
210
211 if M == 0 && N == 0 && prefix_size == 0 && suffix_size == 0 {
212 return result;
213 }
214
215 if N == 0 {
216 let mut p = 0;
217 while p < prefix_size {
218 result.push(DiffResult::Common(DiffElement {
219 old_index: Some(p),
220 new_index: Some(p),
221 }));
222 p += 1;
223 }
224
225 let mut o = prefix_size;
226 while o < M + prefix_size {
227 if swapped {
228 result.push(DiffResult::Added(DiffElement {
229 old_index: None,
230 new_index: Some(o),
231 }));
232 } else {
233 result.push(DiffResult::Removed(DiffElement {
234 old_index: Some(o),
235 new_index: None,
236 }));
237 }
238 o += 1;
239 }
240
241 let mut s = 0;
242 let old_offset = sliced_old.len() + prefix_size;
243 let new_offset = sliced_new.len() + prefix_size;
244 while s < suffix_size {
245 let old_index = s + old_offset;
246 result.push(DiffResult::Common(DiffElement {
247 old_index: Some(old_index),
248 new_index: Some(s + new_offset),
249 }));
250 s += 1;
251 }
252 return result;
253 }
254
255 let offset = N as isize;
256 let D = (M - N) as isize;
257 let size = M + N + 1;
258 let mut fp: Vec<FarthestPoint> = vec![FarthestPoint { y: -1, id: 0 }; size];
259 let mut P = 0;
260 let mut ptr = 0;
261 let mut routes: Vec<usize> = vec![0; M * N + size + 1];
262 let mut diff_types: Vec<u8> = vec![0; M * N + size + 1];
263
264 let mut ctx = Ctx {
265 k: 0,
266 base: 0,
267 A,
268 B,
269 ptr: &mut ptr,
270 routes: &mut routes,
271 diff_types: &mut diff_types,
272 };
273
274 while fp[(D + offset) as usize].y < N as isize {
275 let mut k = -(P as isize);
276 while k < D as isize {
277 let base = k + offset as isize;
278 ctx.k = k;
279 ctx.base = base;
280 fp[base as usize] = snake(&fp, &mut ctx);
281 k += 1;
282 }
283 let mut k = (D + P) as isize;
284 while k > D as isize {
285 let base = k + offset as isize;
286 ctx.k = k;
287 ctx.base = base;
288 fp[base as usize] = snake(&fp, &mut ctx);
289 k -= 1;
290 }
291 let base = D + offset;
292 ctx.k = D;
293 ctx.base = base;
294 fp[base as usize] = snake(&fp, &mut ctx);
295 P += 1;
296 }
297
298 let mut result: Vec<DiffResult> = vec![];
299 let mut p = 0;
300 while p < prefix_size {
301 result.push(DiffResult::Common(DiffElement {
302 old_index: Some(p),
303 new_index: Some(p),
304 }));
305 p += 1;
306 }
307 let base = (D + offset) as usize;
308 let back_trace_result = back_trace(
309 A,
310 B,
311 &fp[base],
312 swapped,
313 &ctx.routes,
314 &ctx.diff_types,
315 prefix_size,
316 );
317 result.extend(back_trace_result);
318 let mut s = 0;
319 let old_offset = sliced_old.len() + prefix_size;
320 let new_offset = sliced_new.len() + prefix_size;
321 while s < suffix_size {
322 let old_index = s + old_offset;
323 result.push(DiffResult::Common(DiffElement {
324 old_index: Some(old_index),
325 new_index: Some(new_offset + s),
326 }));
327 s += 1;
328 }
329 result
330}
331
332#[test]
333fn should_return_one_changed() {
334 let result = diff(&vec!["a"], &vec!["b"]);
335 let expected = vec![
336 DiffResult::Removed(DiffElement {
337 old_index: Some(0),
338 new_index: None,
339 }),
340 DiffResult::Added(DiffElement {
341 old_index: None,
342 new_index: Some(0),
343 }),
344 ];
345
346 assert_eq!(result, expected);
347}
348
349#[test]
350fn should_return_empty() {
351 let a: Vec<String> = vec![];
352 let b: Vec<String> = vec![];
353 let result = diff(&a, &b);
354 let expected = vec![];
355 assert_eq!(result, expected);
356}
357
358#[test]
359fn should_return_one_common() {
360 let result = diff(&vec!["a"], &vec!["a"]);
361 let expected = vec![DiffResult::Common(DiffElement {
362 old_index: Some(0),
363 new_index: Some(0),
364 })];
365 assert_eq!(result, expected);
366}
367
368#[test]
369fn should_return_one_removed() {
370 let result = diff(&vec!["a"], &vec![]);
371 let expected = vec![DiffResult::Removed(DiffElement {
372 old_index: Some(0),
373 new_index: None,
374 })];
375 assert_eq!(result, expected);
376}
377
378#[test]
379fn should_return_one_added() {
380 let result = diff(&vec![], &vec!["a"]);
381 let expected = vec![DiffResult::Added(DiffElement {
382 old_index: None,
383 new_index: Some(0),
384 })];
385 assert_eq!(result, expected);
386}
387
388#[test]
389fn should_return_two_changed() {
390 let result = diff(&vec!["a", "a"], &vec!["b", "b"]);
391 let expected = vec![
392 DiffResult::Removed(DiffElement {
393 old_index: Some(0),
394 new_index: None,
395 }),
396 DiffResult::Removed(DiffElement {
397 old_index: Some(1),
398 new_index: None,
399 }),
400 DiffResult::Added(DiffElement {
401 old_index: None,
402 new_index: Some(0),
403 }),
404 DiffResult::Added(DiffElement {
405 old_index: None,
406 new_index: Some(1),
407 }),
408 ];
409
410 assert_eq!(result, expected);
411}
412
413#[test]
414fn should_create_diff_result_with_added() {
415 let result = diff(&vec!["abc", "c"], &vec!["abc", "bcd", "c"]);
416 let expected = vec![
417 DiffResult::Common(DiffElement {
418 old_index: Some(0),
419 new_index: Some(0),
420 }),
421 DiffResult::Added(DiffElement {
422 old_index: None,
423 new_index: Some(1),
424 }),
425 DiffResult::Common(DiffElement {
426 old_index: Some(1),
427 new_index: Some(2),
428 }),
429 ];
430
431 assert_eq!(result, expected);
432}
433
434#[test]
435fn should_create_diff_result_with_added_common_no_suffix() {
436 let result = diff(&vec![
437 "common",
438 ], &vec![
439 "added",
440 "common",
441 "added",
442 ]);
443 let expected = vec![
444 DiffResult::Added(DiffElement {
445 old_index: None,
446 new_index: Some(0),
447 }),
448 DiffResult::Common(DiffElement {
449 old_index: Some(0),
450 new_index: Some(1),
451 }),
452 DiffResult::Added(DiffElement {
453 old_index: None,
454 new_index: Some(2),
455 }),
456 ];
457
458 assert_eq!(result, expected);
459}
460
461#[test]
462fn should_create_diff_result_with_added_common_no_suffix_swapped() {
463 let result = diff(&vec![
464 "added",
465 "common",
466 "added",
467 ], &vec![
468 "common",
469 ]);
470 let expected = vec![
471 DiffResult::Removed(DiffElement {
472 old_index: Some(0),
473 new_index: None,
474 }),
475 DiffResult::Common(DiffElement {
476 old_index: Some(1),
477 new_index: Some(0),
478 }),
479 DiffResult::Removed(DiffElement {
480 old_index: Some(2),
481 new_index: None,
482 }),
483 ];
484
485 assert_eq!(result, expected);
486}
487
488#[test]
489fn should_create_diff_result_with_added_swapped() {
490 let result = diff(&vec!["abc", "bcd", "c"], &vec!["abc", "c"]);
491 let expected = vec![
492 DiffResult::Common(DiffElement {
493 old_index: Some(0),
494 new_index: Some(0),
495 }),
496 DiffResult::Removed(DiffElement {
497 old_index: Some(1),
498 new_index: None,
499 }),
500 DiffResult::Common(DiffElement {
501 old_index: Some(2),
502 new_index: Some(1),
503 }),
504 ];
505
506 assert_eq!(result, expected);
507}
508
509#[test]
510fn should_create_diff_result_with_removed() {
511 let result = diff(&vec!["abc", "bcd", "c"], &vec!["abc", "c"]);
512 let expected = vec![
513 DiffResult::Common(DiffElement {
514 old_index: Some(0),
515 new_index: Some(0),
516 }),
517 DiffResult::Removed(DiffElement {
518 old_index: Some(1),
519 new_index: None,
520 }),
521 DiffResult::Common(DiffElement {
522 old_index: Some(2),
523 new_index: Some(1),
524 }),
525 ];
526 assert_eq!(result, expected);
527}
528
529#[test]
530fn should_create_diff_result_without_new() {
531 let result = diff(&vec!["abc", "bcd", "c"], &vec![]);
532 let expected = vec![
533 DiffResult::Removed(DiffElement {
534 old_index: Some(0),
535 new_index: None,
536 }),
537 DiffResult::Removed(DiffElement {
538 old_index: Some(1),
539 new_index: None,
540 }),
541 DiffResult::Removed(DiffElement {
542 old_index: Some(2),
543 new_index: None,
544 }),
545 ];
546 assert_eq!(result, expected);
547}
548
549#[test]
550fn should_create_diff_result_without_old() {
551 let result = diff(&vec![], &vec!["abc", "bcd", "c"]);
552 let expected = vec![
553 DiffResult::Added(DiffElement {
554 old_index: None,
555 new_index: Some(0),
556 }),
557 DiffResult::Added(DiffElement {
558 old_index: None,
559 new_index: Some(1),
560 }),
561 DiffResult::Added(DiffElement {
562 old_index: None,
563 new_index: Some(2),
564 }),
565 ];
566 assert_eq!(result, expected);
567}
568
569#[test]
570fn should_create_empty_result_with_empty_input() {
571 let result = diff(&vec![0u8; 0], &vec![0u8; 0]);
572 let expected = vec![];
573 assert_eq!(result, expected);
574}
575
576#[test]
577fn should_create_one_removed_diff_result() {
578 let result = diff(
579 &vec!["abc", "bcd", "c", "aaa", "bbb", "ccc"],
580 &vec!["abc", "c", "aaa", "bbb", "ccc"],
581 );
582 let expected = vec![
583 DiffResult::Common(DiffElement {
584 old_index: Some(0),
585 new_index: Some(0),
586 }),
587 DiffResult::Removed(DiffElement {
588 old_index: Some(1),
589 new_index: None,
590 }),
591 DiffResult::Common(DiffElement {
592 old_index: Some(2),
593 new_index: Some(1),
594 }),
595 DiffResult::Common(DiffElement {
596 old_index: Some(3),
597 new_index: Some(2),
598 }),
599 DiffResult::Common(DiffElement {
600 old_index: Some(4),
601 new_index: Some(3),
602 }),
603 DiffResult::Common(DiffElement {
604 old_index: Some(5),
605 new_index: Some(4),
606 }),
607 ];
608 assert_eq!(result, expected);
609}
610
611#[test]
612fn should_create_string_and_strength_diff_result() {
613 let result = diff(
614 &vec!["s", "t", "r", "e", "n", "g", "t", "h"],
615 &vec!["s", "t", "r", "i", "n", "g"],
616 );
617 let expected = vec![
618 DiffResult::Common(DiffElement {
619 old_index: Some(0),
620 new_index: Some(0),
621 }),
622 DiffResult::Common(DiffElement {
623 old_index: Some(1),
624 new_index: Some(1),
625 }),
626 DiffResult::Common(DiffElement {
627 old_index: Some(2),
628 new_index: Some(2),
629 }),
630 DiffResult::Removed(DiffElement {
631 old_index: Some(3),
632 new_index: None,
633 }),
634 DiffResult::Added(DiffElement {
635 old_index: None,
636 new_index: Some(3),
637 }),
638 DiffResult::Common(DiffElement {
639 old_index: Some(4),
640 new_index: Some(4),
641 }),
642 DiffResult::Common(DiffElement {
643 old_index: Some(5),
644 new_index: Some(5),
645 }),
646 DiffResult::Removed(DiffElement {
647 old_index: Some(6),
648 new_index: None,
649 }),
650 DiffResult::Removed(DiffElement {
651 old_index: Some(7),
652 new_index: None,
653 }),
654 ];
655 assert_eq!(result, expected);
656}