seg_tree/utils/
persistent_wrapper.rs

1use crate::nodes::{LazyNode, Node, PersistentNode};
2
3/// A simple wrapper for nodes to easily implement [`PersistentNode`]. If the wrapped node implements [`LazyNode`] the wrapper also implements it.
4#[derive(Clone, Debug)]
5pub struct PersistentWrapper<T>
6where
7    T: Node,
8{
9    node: T,
10    left: usize,
11    right: usize,
12}
13
14impl<T> Node for PersistentWrapper<T>
15where
16    T: Node,
17{
18    type Value = T::Value;
19
20    #[inline]
21    fn initialize(value: &Self::Value) -> Self {
22        Self {
23            node: T::initialize(value),
24            left: 0,
25            right: 0,
26        }
27    }
28
29    #[inline]
30    fn combine(a: &Self, b: &Self) -> Self {
31        Self {
32            node: T::combine(&a.node, &b.node),
33            left: 0,
34            right: 0,
35        }
36    }
37    #[inline]
38    fn value(&self) -> &Self::Value {
39        self.node.value()
40    }
41}
42impl<T> LazyNode for PersistentWrapper<T>
43where
44    T: LazyNode,
45{
46    #[inline]
47    fn lazy_update(&mut self, i: usize, j: usize) {
48        self.node.lazy_update(i, j);
49    }
50
51    #[inline]
52    fn update_lazy_value(&mut self, new_value: &<Self as Node>::Value) {
53        self.node.update_lazy_value(new_value);
54    }
55
56    #[inline]
57    fn lazy_value(&self) -> Option<&<Self as Node>::Value> {
58        self.node.lazy_value()
59    }
60}
61impl<T> PersistentNode for PersistentWrapper<T>
62where
63    T: Node,
64{
65    #[inline]
66    fn left_child(&self) -> usize {
67        self.left
68    }
69
70    #[inline]
71    fn right_child(&self) -> usize {
72        self.right
73    }
74
75    #[inline]
76    fn set_children(&mut self, left: usize, right: usize) {
77        self.left = left;
78        self.right = right;
79    }
80}
81
82impl<T> From<T> for PersistentWrapper<T>
83where
84    T: Node,
85{
86    #[inline]
87    fn from(node: T) -> Self {
88        Self {
89            node,
90            left: 0,
91            right: 0,
92        }
93    }
94}
seg_tree/utils/persistent_wrapper.rs

seg_tree/utils/
persistent_wrapper.rs
