seg_tree/utils/
max.rs

1use crate::nodes::Node;
2
3/// Implementation of range max for generic type T, it only implements [`Node`].
4#[derive(Clone, Debug, Eq, PartialEq)]
5pub struct Max<T> {
6    value: T,
7}
8
9impl<T> Node for Max<T>
10where
11    T: Ord + Clone,
12{
13    type Value = T;
14    fn initialize(v: &Self::Value) -> Self {
15        Self { value: v.clone() }
16    }
17    fn combine(a: &Self, b: &Self) -> Self {
18        Self {
19            value: a.value.clone().max(b.value.clone()),
20        }
21    }
22    fn value(&self) -> &Self::Value {
23        &self.value
24    }
25}
26
27#[cfg(test)]
28mod tests {
29    use crate::{nodes::Node, utils::Max};
30
31    #[test]
32    fn max_works() {
33        const N: usize = 1_000;
34        let nodes: Vec<Max<usize>> = (0..=N).map(|x| Max::initialize(&x)).collect();
35        let result = nodes
36            .iter()
37            .fold(Max::initialize(&0), |acc, new| Max::combine(&acc, new));
38        assert_eq!(result.value(), &N);
39    }
40}
seg_tree/utils/max.rs

seg_tree/utils/
max.rs
