orx_tree/traversal/
over.rs

1use super::breadth_first::BreadthFirstEnumeration;
2use super::depth_first::DepthFirstEnumeration;
3use super::node_item::NodeItem;
4use super::post_order::PostOrderEnumeration;
5use crate::memory::{Auto, MemoryPolicy};
6use crate::pinned_storage::{PinnedStorage, SplitRecursive};
7use crate::traversal::enumeration::Enumeration;
8use crate::traversal::enumerations::{DepthSiblingIdxVal, DepthVal, SiblingIdxVal, Val};
9use crate::{Node, TreeVariant};
10use orx_selfref_col::NodePtr;
11
12pub type OverItem<'a, V, O, M = Auto, P = SplitRecursive> =
13    <<O as Over>::Enumeration as Enumeration>::Item<<O as Over>::NodeItem<'a, V, M, P>>;
14
15/// Type that defines the type of the items that iterators created by a traverser such as the [`Dfs`] or [`PostOrder`].
16///
17/// [`Dfs`]: crate::traversal::Dfs
18/// [`PostOrder`]: crate::traversal::PostOrder
19pub trait Over: 'static {
20    /// Enumeration of the traversal, which might be only the node item; or it might include one or both of the
21    /// depth and sibling index.
22    type Enumeration: Enumeration
23        + PostOrderEnumeration
24        + DepthFirstEnumeration
25        + BreadthFirstEnumeration;
26
27    /// Part of the iterator item which only depends on the node's internal data.
28    type NodeItem<'a, V, M, P>: NodeItem<'a, V, M, P>
29    where
30        V: TreeVariant,
31        M: MemoryPolicy,
32        P: PinnedStorage,
33        V: 'a,
34        Self: 'a;
35
36    /// Transformed version of the over item where it yields data rather than Node.
37    type IntoOverData: Over;
38
39    /// Transformed version of the over item where it yields Node rather than data.
40    type IntoOverNode: Over;
41
42    /// Transformed version of the over item where it yields
43    ///
44    /// * (depth, x) rather than x, or
45    /// * (depth, sibling_idx, x) rather than (sibling_idx, x)
46    ///
47    /// where x might be data or Node.
48    type IntoWithDepth: Over;
49
50    /// Transformed version of the over item where it yields
51    ///
52    /// * (sibling_idx, x) rather than x, or
53    /// * (depth, sibling_idx, x) rather than (depth, x)
54    ///
55    /// where x might be data or Node.
56    type IntoWithSiblingIdx: Over;
57}
58
59// val
60
61/// Yields the data of the nodes; i.e., [`data`] and [`data_mut`].
62///
63/// [`data`]: crate::NodeRef::data
64/// [`data_mut`]: crate::NodeMut::data_mut
65pub struct OverData;
66
67impl Over for OverData {
68    type Enumeration = Val;
69
70    type NodeItem<'a, V, M, P>
71        = &'a V::Item
72    where
73        M: MemoryPolicy,
74        P: PinnedStorage,
75        V: TreeVariant + 'a,
76        Self: 'a;
77
78    type IntoOverData = Self;
79    type IntoOverNode = OverNode;
80    type IntoWithDepth = OverDepthData;
81    type IntoWithSiblingIdx = OverSiblingIdxData;
82}
83
84/// Yields a reference to the nodes; i.e., [`Node`].
85///
86/// [`Node`]: crate::Node
87pub struct OverNode;
88
89impl Over for OverNode {
90    type Enumeration = Val;
91
92    type NodeItem<'a, V, M, P>
93        = Node<'a, V, M, P>
94    where
95        M: MemoryPolicy,
96        P: PinnedStorage,
97        V: TreeVariant + 'a,
98        Self: 'a;
99
100    type IntoOverData = OverData;
101    type IntoOverNode = Self;
102    type IntoWithDepth = OverDepthNode;
103    type IntoWithSiblingIdx = OverSiblingIdxNode;
104}
105
106pub(crate) struct OverPtr;
107
108impl Over for OverPtr {
109    type Enumeration = Val;
110
111    type NodeItem<'a, V, M, P>
112        = NodePtr<V>
113    where
114        M: MemoryPolicy,
115        P: PinnedStorage,
116        V: TreeVariant + 'a,
117        Self: 'a;
118
119    type IntoOverData = OverData;
120    type IntoOverNode = OverNode;
121    type IntoWithDepth = OverDepthPtr;
122    type IntoWithSiblingIdx = OverSiblingIdxPtr;
123}
124
125// depth & val
126
127/// Yields (depth, data) tuple of the nodes; where data might be [`data`] and [`data_mut`].
128///
129/// The depth is relative to the root of the traversal, rather than the root of the tree.
130/// In other words, the depth of the node that the traversal is initiated from will be 0;
131/// and depth of its descendants will be evaluated relative to this.
132///
133/// [`data`]: crate::NodeRef::data
134/// [`data_mut`]: crate::NodeMut::data_mut
135pub struct OverDepthData;
136
137impl Over for OverDepthData {
138    type Enumeration = DepthVal;
139
140    type NodeItem<'a, V, M, P>
141        = &'a V::Item
142    where
143        M: MemoryPolicy,
144        P: PinnedStorage,
145        V: TreeVariant + 'a,
146        Self: 'a;
147
148    type IntoOverData = Self;
149    type IntoOverNode = OverDepthNode;
150    type IntoWithDepth = OverDepthData;
151    type IntoWithSiblingIdx = OverDepthSiblingIdxData;
152}
153
154/// Yields (depth, [`Node`]) tuple of the nodes.
155///
156/// The depth is relative to the root of the traversal, rather than the root of the tree.
157/// In other words, the depth of the node that the traversal is initiated from will be 0;
158/// and depth of its descendants will be evaluated relative to this.
159///
160/// [`Node`]: crate::Node
161pub struct OverDepthNode;
162
163impl Over for OverDepthNode {
164    type Enumeration = DepthVal;
165
166    type NodeItem<'a, V, M, P>
167        = Node<'a, V, M, P>
168    where
169        M: MemoryPolicy,
170        P: PinnedStorage,
171        V: TreeVariant + 'a,
172        Self: 'a;
173
174    type IntoOverData = OverDepthData;
175    type IntoOverNode = Self;
176    type IntoWithDepth = OverDepthNode;
177    type IntoWithSiblingIdx = OverDepthSiblingIdxNode;
178}
179
180pub(crate) struct OverDepthPtr;
181
182impl Over for OverDepthPtr {
183    type Enumeration = DepthVal;
184
185    type NodeItem<'a, V, M, P>
186        = NodePtr<V>
187    where
188        M: MemoryPolicy,
189        P: PinnedStorage,
190        V: TreeVariant + 'a,
191        Self: 'a;
192
193    type IntoOverData = OverData;
194    type IntoOverNode = OverNode;
195    type IntoWithDepth = OverDepthPtr;
196    type IntoWithSiblingIdx = OverDepthSiblingIdxPtr;
197}
198
199// sibling & val
200
201/// Yields (sibling_idx, data) tuple of the nodes; where data might be [`data`] and [`data_mut`].
202///
203/// Sibling indices of all nodes except for the root of the traversal are naturally equal to the sibling
204/// indices of the nodes in the tree.
205///
206/// However, sibling index of the root, or the node that the traversal is initiated from, will be 0.
207/// This is because the root is the only sibling in the subtree that the traversal considers.
208///
209/// [`data`]: crate::NodeRef::data
210/// [`data_mut`]: crate::NodeMut::data_mut
211pub struct OverSiblingIdxData;
212
213impl Over for OverSiblingIdxData {
214    type Enumeration = SiblingIdxVal;
215
216    type NodeItem<'a, V, M, P>
217        = &'a V::Item
218    where
219        M: MemoryPolicy,
220        P: PinnedStorage,
221        V: TreeVariant + 'a,
222        Self: 'a;
223
224    type IntoOverData = Self;
225    type IntoOverNode = OverSiblingIdxNode;
226    type IntoWithDepth = OverDepthSiblingIdxData;
227    type IntoWithSiblingIdx = OverSiblingIdxData;
228}
229
230/// Yields (sibling_idx, [`Node`]) tuple of the nodes.
231///
232/// Sibling indices of all nodes except for the root of the traversal are naturally equal to the sibling
233/// indices of the nodes in the tree.
234///
235/// However, sibling index of the root, or the node that the traversal is initiated from, will be 0.
236/// This is because the root is the only sibling in the subtree that the traversal considers.
237///
238/// [`Node`]: crate::Node
239pub struct OverSiblingIdxNode;
240
241impl Over for OverSiblingIdxNode {
242    type Enumeration = SiblingIdxVal;
243
244    type NodeItem<'a, V, M, P>
245        = Node<'a, V, M, P>
246    where
247        M: MemoryPolicy,
248        P: PinnedStorage,
249        V: TreeVariant + 'a,
250        Self: 'a;
251
252    type IntoOverData = OverSiblingIdxData;
253    type IntoOverNode = Self;
254    type IntoWithDepth = OverDepthSiblingIdxNode;
255    type IntoWithSiblingIdx = OverSiblingIdxNode;
256}
257
258pub(crate) struct OverSiblingIdxPtr;
259
260impl Over for OverSiblingIdxPtr {
261    type Enumeration = Val;
262
263    type NodeItem<'a, V, M, P>
264        = NodePtr<V>
265    where
266        M: MemoryPolicy,
267        P: PinnedStorage,
268        V: TreeVariant + 'a,
269        Self: 'a;
270
271    type IntoOverData = OverData;
272    type IntoOverNode = OverNode;
273    type IntoWithDepth = OverDepthSiblingIdxPtr;
274    type IntoWithSiblingIdx = OverSiblingIdxPtr;
275}
276
277// depth & sibling & val
278
279/// Yields (depth, sibling_idx, data) tuple of the nodes; where data might be [`data`] and [`data_mut`].
280///
281/// The depth is relative to the root of the traversal, rather than the root of the tree.
282/// In other words, the depth of the node that the traversal is initiated from will be 0;
283/// and depth of its descendants will be evaluated relative to this.
284///
285/// Sibling indices of all nodes except for the root of the traversal are naturally equal to the sibling
286/// indices of the nodes in the tree.
287///
288/// However, sibling index of the root will be 0.
289/// This is because the root is the only sibling in the subtree that the traversal considers.
290///
291/// [`data`]: crate::NodeRef::data
292/// [`data_mut`]: crate::NodeMut::data_mut
293pub struct OverDepthSiblingIdxData;
294
295impl Over for OverDepthSiblingIdxData {
296    type Enumeration = DepthSiblingIdxVal;
297
298    type NodeItem<'a, V, M, P>
299        = &'a V::Item
300    where
301        M: MemoryPolicy,
302        P: PinnedStorage,
303        V: TreeVariant + 'a,
304        Self: 'a;
305
306    type IntoOverData = Self;
307    type IntoOverNode = OverDepthSiblingIdxNode;
308    type IntoWithDepth = Self;
309    type IntoWithSiblingIdx = Self;
310}
311
312/// Yields (depth, sibling_idx, [`Node`]) tuple of the nodes.
313///
314/// The depth is relative to the root of the traversal, rather than the root of the tree.
315/// In other words, the depth of the node that the traversal is initiated from will be 0;
316/// and depth of its descendants will be evaluated relative to this.
317///
318/// Sibling indices of all nodes except for the root of the traversal are naturally equal to the sibling
319/// indices of the nodes in the tree.
320///
321/// However, sibling index of the root will be 0.
322/// This is because the root is the only sibling in the subtree that the traversal considers.
323///
324/// [`Node`]: crate::Node
325pub struct OverDepthSiblingIdxNode;
326
327impl Over for OverDepthSiblingIdxNode {
328    type Enumeration = DepthSiblingIdxVal;
329
330    type NodeItem<'a, V, M, P>
331        = Node<'a, V, M, P>
332    where
333        M: MemoryPolicy,
334        P: PinnedStorage,
335        V: TreeVariant + 'a,
336        Self: 'a;
337
338    type IntoOverData = OverDepthSiblingIdxData;
339    type IntoOverNode = Self;
340    type IntoWithDepth = Self;
341    type IntoWithSiblingIdx = Self;
342}
343pub(crate) struct OverDepthSiblingIdxPtr;
344
345impl Over for OverDepthSiblingIdxPtr {
346    type Enumeration = Val;
347
348    type NodeItem<'a, V, M, P>
349        = NodePtr<V>
350    where
351        M: MemoryPolicy,
352        P: PinnedStorage,
353        V: TreeVariant + 'a,
354        Self: 'a;
355
356    type IntoOverData = OverData;
357    type IntoOverNode = OverNode;
358    type IntoWithDepth = Self;
359    type IntoWithSiblingIdx = Self;
360}
orx_tree/traversal/over.rs

orx_tree/traversal/
over.rs
