xlsx-diff 0.1.3

a libray for comparing differences between two XLSX files
Documentation 
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

use serde::Serialize;
#[derive(Debug, Clone, PartialEq, Serialize)]
pub struct DiffItem<T> {
    pub op: String,
    pub old_index: Option<usize>,
    pub new_index: Option<usize>,
    pub value: T,
}
/**

 * Myers diff algorithm
 * @param a old data
 * @param b new data
 * @returns diff result
 * TODO: ignore some columns when using the 'header row' option
 */
pub fn myers_diff<T: Eq + Clone>(a: &[T], b: &[T]) -> Vec<DiffItem<T>> {
    let n = a.len();
    let m = b.len();
    let max = n + m;
    let mut v = vec![0; 2 * max + 2];
    let offset = max;
    let mut path = Vec::new();
    for d in 0..=max {
        let mut v_prev = v.clone();
        for k in (-(d as isize)..=d as isize).step_by(2) {
            let idx = (k + offset as isize) as usize;
            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]) {
                (v[(k + 1 + offset as isize) as usize], k + 1)
            } else {
                (v[(k - 1 + offset as isize) as usize] + 1, k - 1)
            };
            let mut x = x_start;
            let mut y = x as isize - k;

            while x < n && y < m as isize && a[x] == b[y as usize] {
                x += 1;
                y += 1;
            }
            v[idx] = x;
            if x >= n && y >= m as isize {
                // Reconstruct the path
                let mut ops = Vec::new();
                let mut x = n;
                let mut y = m as isize;
                for d_back in (0..=d).rev() {
                    let k = x as isize - y;
                    let idx = (k + offset as isize) as usize;
                    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]) {
                        k + 1
                    } else {
                        k - 1
                    };
                    let x_prev = v_prev[(k_prev + offset as isize) as usize];
                    let y_prev = x_prev as isize - k_prev;

                    while x > x_prev && y > y_prev {
                        x -= 1;
                        y -= 1;
                        // ops.push(DiffItem {
                        //     op: "Equal".to_string(),
                        //     old_index: Some(x),
                        //     new_index: Some(y as usize),
                        //     value: a[x].clone(),
                        // });
                    }
                    if x > x_prev && x > 0 {
                        x -= 1;
                        ops.push(DiffItem {
                            op: "Delete".to_string(),
                            old_index: Some(x),
                            new_index: None,
                            value: a[x].clone(),
                        });
                    } else if y > y_prev && y > 0 {
                        y -= 1;
                        ops.push(DiffItem {
                            op: "Insert".to_string(),
                            old_index: None,
                            new_index: Some(y as usize),
                            value: b[y as usize].clone(),
                        });
                    }
                    v_prev = path.pop().unwrap_or(v_prev);
                }
                ops.reverse();
                return ops;
            }
        }
        path.push(v.clone());
    }
    Vec::new()
}