alg_ds 0.3.2

Algorithms & data structures
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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127

use crate::ds::matrix::Matrix;

/// Returns length of the longest common subsequence of sequences `a` and `b`.
pub fn lcs_length<'a, T: PartialEq>(a: &'a [T], b: &[T]) -> (usize, Matrix::<'a, usize>) {
    let size_a = a.len();
    let size_b = b.len();
    let mut m = Matrix::<usize>::new(size_a + 1, size_b + 1);
    for i in (0..size_a).rev() {
        for j in (0..size_b).rev() {
            if a[i] == b[j] {
                m[i][j] = 1 + m[i + 1][j + 1];
            } else {
                if m[i + 1][j] > m[i][j + 1] {
                    m[i][j] = m[i + 1][j]
                } else {
                    m[i][j] = m[i][j + 1]
                }
            }
        }
    }
    (m[0][0], m)
}

/// Returns the longest common subsequence of sequences `a` and `b`.
pub fn lcs<'a, T: PartialEq>(a: &'a [T], b: &[T]) -> Vec<&'a T> {
    let (_, m) = lcs_length(a, b);

    let mut result = Vec::<&T>::new();
    let mut i = 0;
    let mut j = 0;
    while i < a.len() && j < b.len() {
        if a[i] == b[j] {
            result.push(&a[i]);
            i += 1;
            j += 1;
        } else if m[i + 1][j] >= m[i][j + 1] {
            i += 1;
        } else {
            j += 1;
        }
    }

    result
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn lcs_length_ok() {
        let a = Vec::<char>::new();
        let b = Vec::<char>::new();
        assert_eq!(lcs_length(&a, &b).0, 0);

        let a = Vec::<char>::new();
        let b = vec!['a', 'b', 'c', 'd', 'e'];
        assert_eq!(lcs_length(&a, &b).0, 0);

        let a = vec!['a', 'b', 'c', 'd', 'e'];
        let b = Vec::<char>::new();
        assert_eq!(lcs_length(&a, &b).0, 0);

        let a = vec!['a', 'b', 'c', 'd', 'e'];
        let b = vec!['a', 'b', 'c', 'd', 'e'];
        assert_eq!(lcs_length(&a, &b).0, 5);

        let a = vec!['a', 'b', 'c', 'd', 'e'];
        let b = vec!['a', 'c', 'e', 'd'];
        assert_eq!(lcs_length(&a, &b).0, 3);

        let a = vec!['a', 'b', 'c', 'd', 'e'];
        let b = vec!['b', 'c', 'f'];
        assert_eq!(lcs_length(&a, &b).0, 2);

        let a = vec!['b', 'c', 'f'];
        let b = vec!['a', 'b', 'c', 'd', 'e'];
        assert_eq!(lcs_length(&a, &b).0, 2);

        let a = vec!['b', 'c', 'f'];
        let b = vec!['a', 'd'];
        assert_eq!(lcs_length(&a, &b).0, 0);

        let a = vec!['b', 'c', 'f'];
        let b = vec!['f', 'd'];
        assert_eq!(lcs_length(&a, &b).0, 1);
    }

    #[test]
    fn lcs_ok() {
        let a = Vec::<char>::new();
        let b = Vec::<char>::new();
        assert_eq!(lcs(&a, &b).is_empty(), true);

        let a = Vec::<char>::new();
        let b = vec!['a', 'b', 'c', 'd', 'e'];
        assert_eq!(lcs(&a, &b).is_empty(), true);

        let a = vec!['a', 'b', 'c', 'd', 'e'];
        let b = Vec::<char>::new();
        assert_eq!(lcs(&a, &b).is_empty(), true);

        let a = vec!['a', 'b', 'c', 'd', 'e'];
        let b = vec!['a', 'b', 'c', 'd', 'e'];
        assert_eq!(lcs(&a, &b), vec![&'a', &'b', &'c', &'d', &'e']);

        let a = vec!['a', 'b', 'c', 'd', 'e'];
        let b = vec!['a', 'c', 'e', 'd'];
        assert_eq!(lcs(&a, &b), vec![&'a', &'c', &'e']);

        let a = vec!['a', 'b', 'c', 'd', 'e'];
        let b = vec!['b', 'c', 'f'];
        assert_eq!(lcs(&a, &b), vec![&'b', &'c']);

        let a = vec!['b', 'c', 'f'];
        let b = vec!['a', 'b', 'c', 'd', 'e'];
        assert_eq!(lcs(&a, &b), vec![&'b', &'c']);

        let a = vec!['b', 'c', 'f'];
        let b = vec!['a', 'd'];
        assert_eq!(lcs(&a, &b).is_empty(), true);

        let a = vec!['b', 'c', 'f'];
        let b = vec!['f', 'd'];
        assert_eq!(lcs(&a, &b), vec![&'f']);
    }
}