xlsx_diff/core/
diff.rs

1use serde::Serialize;
2#[derive(Debug, Clone, PartialEq, Serialize)]
3pub struct DiffItem<T> {
4    pub op: String,
5    pub old_index: Option<usize>,
6    pub new_index: Option<usize>,
7    pub value: T,
8}
9/**
10 * Myers diff algorithm
11 * @param a old data
12 * @param b new data
13 * @returns diff result
14 * TODO: ignore some columns when using the 'header row' option
15 */
16pub fn myers_diff<T: Eq + Clone>(a: &[T], b: &[T]) -> Vec<DiffItem<T>> {
17    let n = a.len();
18    let m = b.len();
19    let max = n + m;
20    let mut v = vec![0; 2 * max + 2];
21    let offset = max;
22    let mut path = Vec::new();
23    for d in 0..=max {
24        let mut v_prev = v.clone();
25        for k in (-(d as isize)..=d as isize).step_by(2) {
26            let idx = (k + offset as isize) as usize;
27            let (x_start, k_prev) = if k == -(d as isize) || (k != d as isize && v[(k -1 + offset as isize) as usize] < v[(k + 1 + offset as isize) as usize]) {
28                (v[(k + 1 + offset as isize) as usize], k + 1)
29            } else {
30                (v[(k - 1 + offset as isize) as usize] + 1, k - 1)
31            };
32            let mut x = x_start;
33            let mut y = x as isize - k;
34
35            while x < n && y < m as isize && a[x] == b[y as usize] {
36                x += 1;
37                y += 1;
38            }
39            v[idx] = x;
40            if x >= n && y >= m as isize {
41                // Reconstruct the path
42                let mut ops = Vec::new();
43                let mut x = n;
44                let mut y = m as isize;
45                for d_back in (0..=d).rev() {
46                    let k = x as isize - y;
47                    let idx = (k + offset as isize) as usize;
48                    let k_prev = if k == -(d_back as isize) as isize || (k != d_back as isize && v_prev[(k -1 + offset as isize) as usize] < v_prev[(k +1 + offset as isize) as usize]) {
49                        k + 1
50                    } else {
51                        k - 1
52                    };
53                    let x_prev = v_prev[(k_prev + offset as isize) as usize];
54                    let y_prev = x_prev as isize - k_prev;
55
56                    while x > x_prev && y > y_prev {
57                        x -= 1;
58                        y -= 1;
59                        // ops.push(DiffItem {
60                        //     op: "Equal".to_string(),
61                        //     old_index: Some(x),
62                        //     new_index: Some(y as usize),
63                        //     value: a[x].clone(),
64                        // });
65                    }
66                    if x > x_prev && x > 0 {
67                        x -= 1;
68                        ops.push(DiffItem {
69                            op: "Delete".to_string(),
70                            old_index: Some(x),
71                            new_index: None,
72                            value: a[x].clone(),
73                        });
74                    } else if y > y_prev && y > 0 {
75                        y -= 1;
76                        ops.push(DiffItem {
77                            op: "Insert".to_string(),
78                            old_index: None,
79                            new_index: Some(y as usize),
80                            value: b[y as usize].clone(),
81                        });
82                    }
83                    v_prev = path.pop().unwrap_or(v_prev);
84                }
85                ops.reverse();
86                return ops;
87            }
88        }
89        path.push(v.clone());
90    }
91    Vec::new()
92}
xlsx_diff/core/diff.rs

xlsx_diff/core/
diff.rs
