dsalgo 0.3.10

A package for Datastructures and Algorithms.
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

pub struct SparseTable<T, F> {
    node: Vec<Vec<T>>,
    f: F,
}

impl<T: Clone, F: Fn(T, T) -> T> SparseTable<T, F> {
    pub fn new(
        f: F,
        a: &[T],
    ) -> Self {
        let n = a.len();

        assert!(n > 0);

        let h = n.next_power_of_two().trailing_zeros().max(1) as usize;

        let mut node = vec![vec![]; h];

        node[0] = a.to_vec();

        for i in 1..h {
            let d1 = 1 << i;

            let d0 = d1 >> 1;

            let w = n - d1 + 1;

            node[i] = (0..w)
                .map(|j| f(node[i - 1][j].clone(), node[i - 1][j + d0].clone()))
                .collect();
        }

        Self { node, f }
    }

    pub fn size(&self) -> usize {
        self.node[0].len()
    }

    pub fn get(
        &self,
        l: usize,
        r: usize,
    ) -> T {
        assert!(l < r && r <= self.size());

        if r - l == 1 {
            return self.node[0][l].clone();
        }

        let i = (r - l).next_power_of_two().trailing_zeros() as usize - 1;

        (self.f)(self.node[i][l].clone(), self.node[i][r - (1 << i)].clone())
    }
}

#[cfg(test)]

mod tests {

    use super::*;

    #[test]

    fn test() {
        let a: Vec<usize> = vec![0, 4, 2, 8, 5, 1];

        let f = |a: usize, b: usize| a.min(b);

        let sp = SparseTable::new(&f, &a);

        assert_eq!(sp.get(0, 4), 0);

        assert_eq!(sp.get(3, 4), 8);

        assert_eq!(sp.get(1, 6), 1);
    }
}