seg_tree/utils/
min.rs

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

seg_tree/utils/
min.rs
