seg_tree/utils/
lazy_set_wrapper.rs

1use crate::nodes::{LazyNode, Node, PersistentNode};
2
3/// A wrapper for nodes to easily implement [`LazyNode`] with an update which sets the range to a value. If the wrapped node implements [`PersistentNode`] the wrapper also implements it.
4#[derive(Clone)]
5pub struct LazySetWrapper<T>
6where
7    T: Node,
8{
9    node: T,
10    lazy_value: Option<<T as Node>::Value>,
11}
12
13impl<T> std::fmt::Debug for LazySetWrapper<T>
14where
15    T: Node + std::fmt::Debug,
16    <T as Node>::Value: std::fmt::Debug,
17{
18    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
19        f.debug_struct("LazySetWrapper")
20            .field("node", &self.node)
21            .field("lazy_value", &self.lazy_value)
22            .finish()
23    }
24}
25
26impl<T> Node for LazySetWrapper<T>
27where
28    T: Node,
29{
30    type Value = T::Value;
31
32    #[inline]
33    fn initialize(value: &Self::Value) -> Self {
34        Self {
35            node: T::initialize(value),
36            lazy_value: None,
37        }
38    }
39
40    #[inline]
41    fn combine(a: &Self, b: &Self) -> Self {
42        Self {
43            node: T::combine(&a.node, &b.node),
44            lazy_value: None,
45        }
46    }
47
48    #[inline]
49    fn value(&self) -> &Self::Value {
50        self.node.value()
51    }
52}
53impl<T> LazyNode for LazySetWrapper<T>
54where
55    T: Node,
56{
57    #[inline]
58    fn lazy_update(&mut self, _i: usize, _j: usize) {
59        if let Some(value) = self.lazy_value.take() {
60            self.node = Node::initialize(&value);
61        }
62    }
63    #[inline]
64    fn update_lazy_value(&mut self, new_value: &<Self as Node>::Value) {
65        self.lazy_value = Some(new_value.clone());
66    }
67    #[inline]
68    fn lazy_value(&self) -> Option<&<Self as Node>::Value> {
69        self.lazy_value.as_ref()
70    }
71}
72impl<T> PersistentNode for LazySetWrapper<T>
73where
74    T: PersistentNode,
75{
76    #[inline]
77    fn left_child(&self) -> usize {
78        self.node.left_child()
79    }
80    #[inline]
81    fn right_child(&self) -> usize {
82        self.node.right_child()
83    }
84    #[inline]
85    fn set_children(&mut self, left: usize, right: usize) {
86        self.node.set_children(left, right);
87    }
88}
89
90impl<T> From<T> for LazySetWrapper<T>
91where
92    T: Node,
93{
94    #[inline]
95    fn from(node: T) -> Self {
96        Self {
97            node,
98            lazy_value: None,
99        }
100    }
101}
102
103#[cfg(test)]
104mod tests {
105    use crate::{
106        nodes::{LazyNode, Node},
107        utils::Min,
108    };
109
110    use super::LazySetWrapper;
111
112    type LSMin<T> = LazySetWrapper<Min<T>>;
113    #[test]
114    fn update_lazy_value_works() {
115        let mut node = LSMin::initialize(&1);
116        node.update_lazy_value(&2);
117        assert_eq!(node.lazy_value(), Some(&2));
118    }
119
120    #[test]
121    fn lazy_update_works() {
122        // Node represents the range [0,10] with min 1.
123        let mut node = LSMin::initialize(&1);
124        node.update_lazy_value(&2);
125        node.lazy_update(0, 10);
126        assert_eq!(node.value(), &2);
127    }
128}
seg_tree/utils/lazy_set_wrapper.rs

seg_tree/utils/
lazy_set_wrapper.rs
