orx_tree/traversal/
traverser_core.rs

1use super::{
2    OverData, OverMut,
3    enumeration::Enumeration,
4    over::{Over, OverItem},
5    over_mut::{OverItemInto, OverItemMut},
6};
7use crate::{
8    NodeMut, NodeMutOrientation, NodeRef, TreeVariant, memory::MemoryPolicy,
9    pinned_storage::PinnedStorage,
10};
11use orx_self_or::SoM;
12use orx_selfref_col::NodePtr;
13
14pub trait TraverserCore<O = OverData>: Sized
15where
16    O: Over,
17{
18    type Storage<V>: Default
19    where
20        V: TreeVariant;
21
22    fn storage_mut<V: TreeVariant>(&mut self) -> &mut Self::Storage<V>;
23
24    fn iter_ptr_with_storage<'a, V>(
25        node_ptr: NodePtr<V>,
26        storage: impl SoM<Self::Storage<V>>,
27    ) -> impl Iterator<Item = <O::Enumeration as Enumeration>::Item<NodePtr<V>>>
28    where
29        V: TreeVariant + 'a;
30
31    fn iter_with_storage<'a, V, M, P>(
32        node: &'a impl NodeRef<'a, V, M, P>,
33        storage: impl SoM<Self::Storage<V>>,
34    ) -> impl Iterator<Item = OverItem<'a, V, O, M, P>>
35    where
36        V: TreeVariant + 'a,
37        M: MemoryPolicy,
38        P: PinnedStorage;
39
40    /// Returns an iterator which yields all nodes including the `node` and all its descendants; i.e.,
41    /// all nodes of the subtree rooted at the given `node`.
42    ///
43    /// The order of visited nodes depends on the internal walk strategy of the traverser; depth-first and
44    /// breadth-first are the most well-known traversals.
45    ///
46    /// Typically, the `iter` call of a traverser does not require any memory allocation.
47    ///
48    /// # Yields
49    ///
50    /// The return value of the iterations depend on the second generic parameter of the traverser which implements
51    /// the [`Over`] trait. The following is the complete list of implementations and the corresponding item type
52    /// of the created iterators. For any `Over` implementation, the corresponding traverser can be created by using
53    /// the `Default::default()` function; however, it is often more convenient to use the [`Traversal`] type.
54    /// The last column of the table demonstrates how to create different traverser types; where the depth first or dfs
55    /// is replaceable with any available traversal strategy such as `bfs` or `post_order`.
56    ///
57    /// | Over | Yields | Depth First Example |
58    /// |---|---|---|
59    /// | [`OverData`] | &data | `Traversal.dfs()` |
60    /// | [`OverDepthData`] | (depth, &data) | `Traversal.dfs().with_depth()` |
61    /// | [`OverSiblingIdxData`] | (sibling_idx, &data) | `Traversal.dfs().with_sibling_idx()` |
62    /// | [`OverDepthSiblingIdxData`] | (depth, sibling_idx, &data) | `Traversal.with_depth().with_sibling_idx()` |
63    /// | [`OverNode`] | Node | `Traversal.dfs().over_nodes()` |
64    /// | [`OverDepthNode`] | (depth, Node) | `Traversal.dfs().over_nodes().with_depth()` |
65    /// | [`OverSiblingIdxNode`] | (sibling_idx, Node) | `Traversal.dfs().over_nodes().with_sibling_idx()` |
66    /// | [`OverDepthSiblingIdxNode`] | (depth, sibling_idx, Node) | `Traversal.dfs().over_nodes().with_depth().with_sibling_idx()` |
67    ///
68    /// [`Traversal`]: crate::traversal::Traversal
69    /// [`OverData`]: crate::traversal::OverData
70    /// [`OverDepthData`]: crate::traversal::OverDepthData
71    /// [`OverSiblingIdxData`]: crate::traversal::OverSiblingIdxData
72    /// [`OverDepthSiblingIdxData`]: crate::traversal::OverDepthSiblingIdxData
73    /// [`OverNode`]: crate::traversal::OverNode
74    /// [`OverDepthNode`]: crate::traversal::OverDepthNode
75    /// [`OverSiblingIdxNode`]: crate::traversal::OverSiblingIdxNode
76    /// [`OverDepthSiblingIdxNode`]: crate::traversal::OverDepthSiblingIdxNode
77    fn iter<'a, V, M, P>(
78        &'a mut self,
79        node: &'a impl NodeRef<'a, V, M, P>,
80    ) -> impl Iterator<Item = OverItem<'a, V, O, M, P>>
81    where
82        V: TreeVariant + 'a,
83        M: MemoryPolicy,
84        P: PinnedStorage;
85
86    fn iter_mut_with_storage<'a, V, M, P, MO>(
87        node_mut: &'a mut NodeMut<'a, V, M, P, MO>,
88        storage: impl SoM<Self::Storage<V>>,
89    ) -> impl Iterator<Item = OverItemMut<'a, V, O, M, P>>
90    where
91        V: TreeVariant + 'a,
92        M: MemoryPolicy,
93        P: PinnedStorage,
94        MO: NodeMutOrientation,
95        O: OverMut;
96
97    /// Returns a mutable iterator which yields all nodes including the `node` and all its descendants; i.e.,
98    /// all nodes of the subtree rooted at the given `node`.
99    ///
100    /// The order of visited nodes depends on the internal walk strategy of the traverser; depth-first and
101    /// breadth-first are the most well-known traversals.
102    ///
103    /// Typically, the `iter` or `iter_mut` or `into_iter` call of a traverser does not require any memory allocation.
104    ///
105    /// # Yields
106    ///
107    /// The return value of the iterations depend on the second generic parameter of the traverser which implements
108    /// the [`OverMut`] trait. The following is the complete list of implementations and the corresponding item type
109    /// of the created iterators. For any `Over` implementation, the corresponding traverser can be created by using
110    /// the `Default::default()` function; however, it is often more convenient to use the [`Traversal`] type.
111    /// The last column of the table demonstrates how to create different traverser types; where the depth first or dfs
112    /// is replaceable with any available traversal strategy such as `bfs` or `post_order`.
113    ///
114    /// | Over | Yields | Depth First Example |
115    /// |---|---|---|
116    /// | [`OverData`] | &mut data | `Traversal.dfs()` |
117    /// | [`OverDepthData`] | (depth, &mut data) | `Traversal.dfs().with_depth()` |
118    /// | [`OverSiblingIdxData`] | (sibling_idx, &mut data) | `Traversal.dfs().with_sibling_idx()` |
119    /// | [`OverDepthSiblingIdxData`] | (depth, sibling_idx, &mut data) | `Traversal.with_depth().with_sibling_idx()` |
120    ///
121    /// [`Traversal`]: crate::traversal::Traversal
122    /// [`OverMut`]: crate::traversal::OverMut
123    /// [`OverData`]: crate::traversal::OverData
124    /// [`OverDepthData`]: crate::traversal::OverDepthData
125    /// [`OverSiblingIdxData`]: crate::traversal::OverSiblingIdxData
126    /// [`OverDepthSiblingIdxData`]: crate::traversal::OverDepthSiblingIdxData
127    fn iter_mut<'a, V, M, P, MO>(
128        &'a mut self,
129        node: &'a mut NodeMut<'a, V, M, P, MO>,
130    ) -> impl Iterator<Item = OverItemMut<'a, V, O, M, P>>
131    where
132        V: TreeVariant + 'a,
133        M: MemoryPolicy,
134        P: PinnedStorage,
135        MO: NodeMutOrientation,
136        O: OverMut;
137
138    fn into_iter_with_storage<'a, V, M, P, MO>(
139        node_mut: NodeMut<'a, V, M, P, MO>,
140        storage: impl SoM<Self::Storage<V>>,
141    ) -> impl Iterator<Item = OverItemInto<'a, V, O>>
142    where
143        V: TreeVariant + 'a,
144        M: MemoryPolicy,
145        P: PinnedStorage,
146        MO: NodeMutOrientation,
147        O: Over;
148
149    /// Returns an iterator which:
150    ///
151    /// * traverses all nodes including the `node` and its descendants; i.e.,
152    ///   all nodes of the subtree rooted at the given `node`,
153    /// * removes the traversed nodes from the tree, and
154    /// * yields their values.
155    ///
156    /// Once the iterator is consumed, the tree will be missing the subtree rooted at the given `node`.
157    /// If the given node is the root of the tree, the tree will be empty after this call.
158    ///
159    /// The order of visited nodes depends on the internal walk strategy of the traverser; depth-first and
160    /// breadth-first are the most well-known traversals.
161    ///
162    /// Typically, the `iter` or `iter_mut` or `into_iter` call of a traverser does not require any memory allocation.
163    ///
164    /// # Yields
165    ///
166    /// The return value of the iterations depend on the second generic parameter of the traverser which implements
167    /// the [`OverMut`] trait. The following is the complete list of implementations and the corresponding item type
168    /// of the created iterators. For any `Over` implementation, the corresponding traverser can be created by using
169    /// the `Default::default()` function; however, it is often more convenient to use the [`Traversal`] type.
170    /// The last column of the table demonstrates how to create different traverser types; where the depth first or dfs
171    /// is replaceable with any available traversal strategy such as `bfs` or `post_order`.
172    ///
173    /// Importantly note that, since the created iterators remove the nodes from the tree, the "data" below represents
174    /// the owned data taken out of the corresponding node, and hence, out of the tree.
175    ///
176    /// | Over | Yields | Depth First Example |
177    /// |---|---|---|
178    /// | [`OverData`] | data | `Traversal.dfs()` |
179    /// | [`OverDepthData`] | (depth, data) | `Traversal.dfs().with_depth()` |
180    /// | [`OverSiblingIdxData`] | (sibling_idx, data) | `Traversal.dfs().with_sibling_idx()` |
181    /// | [`OverDepthSiblingIdxData`] | (depth, sibling_idx, data) | `Traversal.with_depth().with_sibling_idx()` |
182    ///
183    /// [`Traversal`]: crate::traversal::Traversal
184    /// [`OverMut`]: crate::traversal::OverMut
185    /// [`OverData`]: crate::traversal::OverData
186    /// [`OverDepthData`]: crate::traversal::OverDepthData
187    /// [`OverSiblingIdxData`]: crate::traversal::OverSiblingIdxData
188    /// [`OverDepthSiblingIdxData`]: crate::traversal::OverDepthSiblingIdxData
189    #[allow(clippy::wrong_self_convention)]
190    fn into_iter<'a, V, M, P, MO>(
191        &'a mut self,
192        node: NodeMut<'a, V, M, P, MO>,
193    ) -> impl Iterator<Item = OverItemInto<'a, V, O>>
194    where
195        V: TreeVariant + 'a,
196        M: MemoryPolicy,
197        P: PinnedStorage,
198        MO: NodeMutOrientation,
199        O: OverMut;
200
201    // provided
202
203    fn iter_ptr_with_owned_storage<'a, V>(
204        node_ptr: NodePtr<V>,
205    ) -> impl Iterator<Item = <O::Enumeration as Enumeration>::Item<NodePtr<V>>>
206    where
207        V: TreeVariant + 'a,
208    {
209        Self::iter_ptr_with_storage(node_ptr, Self::Storage::default())
210    }
211
212    fn iter_with_owned_storage<'a, V, M, P>(
213        node: &'a impl NodeRef<'a, V, M, P>,
214    ) -> impl Iterator<Item = OverItem<'a, V, O, M, P>>
215    where
216        V: TreeVariant + 'a,
217        M: MemoryPolicy,
218        P: PinnedStorage,
219    {
220        Self::iter_with_storage(node, Self::Storage::default())
221    }
222
223    fn iter_mut_with_owned_storage<'a, V, M, P, MO>(
224        node_mut: &'a mut NodeMut<'a, V, M, P, MO>,
225    ) -> impl Iterator<Item = OverItemMut<'a, V, O, M, P>>
226    where
227        V: TreeVariant + 'a,
228        M: MemoryPolicy,
229        P: PinnedStorage,
230        MO: NodeMutOrientation,
231        O: OverMut,
232    {
233        Self::iter_mut_with_storage(node_mut, Self::Storage::default())
234    }
235
236    fn into_iter_with_owned_storage<'a, V, M, P, MO>(
237        node_mut: NodeMut<'a, V, M, P, MO>,
238    ) -> impl Iterator<Item = OverItemInto<'a, V, O>>
239    where
240        V: TreeVariant + 'a,
241        M: MemoryPolicy,
242        P: PinnedStorage,
243        MO: NodeMutOrientation,
244        O: Over,
245    {
246        Self::into_iter_with_storage(node_mut, Self::Storage::default())
247    }
248}
orx_tree/traversal/traverser_core.rs

orx_tree/traversal/
traverser_core.rs
