seg-tree 0.3.0

A simple segment tree library
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
128

use crate::nodes::{LazyNode, Node, PersistentNode};

/// 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.
#[derive(Clone)]
pub struct LazySetWrapper<T>
where
    T: Node,
{
    node: T,
    lazy_value: Option<<T as Node>::Value>,
}

impl<T> std::fmt::Debug for LazySetWrapper<T>
where
    T: Node + std::fmt::Debug,
    <T as Node>::Value: std::fmt::Debug,
{
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        f.debug_struct("LazySetWrapper")
            .field("node", &self.node)
            .field("lazy_value", &self.lazy_value)
            .finish()
    }
}

impl<T> Node for LazySetWrapper<T>
where
    T: Node,
{
    type Value = T::Value;

    #[inline]
    fn initialize(value: &Self::Value) -> Self {
        Self {
            node: T::initialize(value),
            lazy_value: None,
        }
    }

    #[inline]
    fn combine(a: &Self, b: &Self) -> Self {
        Self {
            node: T::combine(&a.node, &b.node),
            lazy_value: None,
        }
    }

    #[inline]
    fn value(&self) -> &Self::Value {
        self.node.value()
    }
}
impl<T> LazyNode for LazySetWrapper<T>
where
    T: Node,
{
    #[inline]
    fn lazy_update(&mut self, _i: usize, _j: usize) {
        if let Some(value) = self.lazy_value.take() {
            self.node = Node::initialize(&value);
        }
    }
    #[inline]
    fn update_lazy_value(&mut self, new_value: &<Self as Node>::Value) {
        self.lazy_value = Some(new_value.clone());
    }
    #[inline]
    fn lazy_value(&self) -> Option<&<Self as Node>::Value> {
        self.lazy_value.as_ref()
    }
}
impl<T> PersistentNode for LazySetWrapper<T>
where
    T: PersistentNode,
{
    #[inline]
    fn left_child(&self) -> usize {
        self.node.left_child()
    }
    #[inline]
    fn right_child(&self) -> usize {
        self.node.right_child()
    }
    #[inline]
    fn set_children(&mut self, left: usize, right: usize) {
        self.node.set_children(left, right);
    }
}

impl<T> From<T> for LazySetWrapper<T>
where
    T: Node,
{
    #[inline]
    fn from(node: T) -> Self {
        Self {
            node,
            lazy_value: None,
        }
    }
}

#[cfg(test)]
mod tests {
    use crate::{
        nodes::{LazyNode, Node},
        utils::Min,
    };

    use super::LazySetWrapper;

    type LSMin<T> = LazySetWrapper<Min<T>>;
    #[test]
    fn update_lazy_value_works() {
        let mut node = LSMin::initialize(&1);
        node.update_lazy_value(&2);
        assert_eq!(node.lazy_value(), Some(&2));
    }

    #[test]
    fn lazy_update_works() {
        // Node represents the range [0,10] with min 1.
        let mut node = LSMin::initialize(&1);
        node.update_lazy_value(&2);
        node.lazy_update(0, 10);
        assert_eq!(node.value(), &2);
    }
}