orx_tree/common_traits/from_depth_first_iter.rs
1use crate::{MemoryPolicy, Tree, TreeVariant, pinned_storage::PinnedStorage};
2
3/// A depth first sequence is a representation of a tree in a linear storage of (depth, value) tuples.
4/// This is useful in collecting trees from iterators, (de)-serializing trees or converting its variant
5/// from one to another.
6///
7/// `DepthFirstSequence` struct is nothing but a wrapper around a `(usize, T)` iterator in order
8/// to state explicitly that this iterator is expected to follow the depth-first-order of (depth, value) pairs.
9///
10/// A `DepthFirstSequence` can be created from any type that implements `IntoIterator<Item = (usize, T)>`
11/// using `From` (or `Into`) traits.
12///
13/// In order to create a valid tree from the iterator, the order of pairs must satisfy certain conditions.
14/// Assume (depth(i), value(i)) is the i-th item of the iterator.
15/// Then, the following conditions summarize the valid relation between successive elements of the iterator:
16///
17/// * depth(0) = 0
18/// * since the first node of the depth-first traversal is the root
19/// * depth(i+1) < depth(i) is valid
20/// * we are moving from a leaf node with depth(i) to next child of one of its ancestors
21/// * depth(i+1) = depth(i) is valid
22/// * we are moving from a leaf node to its sibling which is immediately right to it
23/// * depth(i+1) = depth(i) + 1 is valid
24/// * we are moving from a non-leaf node to its first child
25///
26/// On the contrary, if either of the following two conditions hold, we cannot build a valid tree.
27///
28/// * depth(0) > 0
29/// * leads to [`DepthFirstSequenceError::NonZeroRootDepth`]
30/// * depth(i + 1) = depth(i) + q where q > 1
31/// * leads to [`DepthFirstSequenceError::DepthIncreaseGreaterThanOne`]
32///
33/// If either of these conditions hold, `try_from` or `try_into` methods will return the corresponding
34/// error instead of a valid tree.
35///
36/// # Examples
37///
38/// ## Happy Paths
39///
40/// The following examples demonstrate the happy paths leading to successful collection of a tree from valid
41/// depth-first sequences.
42///
43/// ```
44/// use orx_tree::*;
45///
46/// // empty tree
47///
48/// let dfs = DepthFirstSequence::from([]);
49/// let result: Result<DynTree<u32>, DepthFirstSequenceError> = dfs.try_into();
50/// assert_eq!(result, Ok(Tree::empty()));
51///
52/// // non-empty tree
53///
54/// // 0
55/// // ╱ ╲
56/// // ╱ ╲
57/// // 1 2
58/// // ╱ ╱ ╲
59/// // 3 4 5
60/// // | |
61/// // 6 7
62/// let depth_value_pairs = [
63/// (0, 0),
64/// (1, 1),
65/// (2, 3),
66/// (3, 6),
67/// (1, 2),
68/// (2, 4),
69/// (2, 5),
70/// (3, 7),
71/// ];
72/// let dfs = DepthFirstSequence::from(depth_value_pairs.clone());
73/// let result: Result<DynTree<u32>, DepthFirstSequenceError> = dfs.try_into();
74///
75/// assert!(result.is_ok());
76/// let tree = result.unwrap();
77///
78/// let bfs: Vec<_> = tree.root().walk::<Bfs>().copied().collect();
79/// assert_eq!(bfs, [0, 1, 2, 3, 4, 5, 6, 7]);
80///
81/// // we can get back the dfs-sequence from constructed tree using walk_with
82///
83/// let mut t = Traversal.dfs().with_depth();
84/// let dfs_back_from_tree: Vec<_> = tree
85/// .root()
86/// .walk_with(&mut t)
87/// .map(|(depth, val)| (depth, *val))
88/// .collect();
89/// assert_eq!(dfs_back_from_tree, depth_value_pairs);
90///
91/// // we can construct back any fitting tree variant from the sequence
92///
93/// let result = DepthFirstSequence::from(dfs_back_from_tree).try_into();
94/// assert!(result.is_ok());
95///
96/// let tree_back: BinaryTree<u32> = result.unwrap();
97/// assert_eq!(tree, tree_back);
98/// ```
99///
100/// ## Error Paths
101///
102/// The following examples illustrate the two potential error cases that can be observed due to
103/// the iterator not yielding a valid depth-first sequence.
104///
105/// ```
106/// use orx_tree::*;
107///
108/// // root with depth > 0
109///
110/// let dfs = DepthFirstSequence::from([(1, 1)]);
111/// let result: Result<DynTree<u32>, DepthFirstSequenceError> = dfs.try_into();
112/// assert_eq!(result, Err(DepthFirstSequenceError::NonZeroRootDepth));
113///
114/// // missing node (or forgotten depth) in the sequence
115///
116/// // 0
117/// // ╱ ╲
118/// // ╱ ╲
119/// // 1 2
120/// // ╱ ╱ ╲
121/// // ??? 4 5
122/// // | |
123/// // 6 7
124/// let depth_value_pairs = [
125/// (0, 0),
126/// (1, 1),
127/// // (2, 3), -> forgotten node leads to depth jump from 1 to 3
128/// (3, 6),
129/// (1, 2),
130/// (2, 4),
131/// (2, 5),
132/// (3, 7),
133/// ];
134/// let dfs = DepthFirstSequence::from(depth_value_pairs.clone());
135/// let result: Result<DynTree<u32>, DepthFirstSequenceError> = dfs.try_into();
136/// assert_eq!(
137/// result,
138/// Err(DepthFirstSequenceError::DepthIncreaseGreaterThanOne {
139/// depth: 1,
140/// succeeding_depth: 3
141/// })
142/// );
143/// ```
144#[derive(Clone)]
145pub struct DepthFirstSequence<T, I>(I)
146where
147 I: IntoIterator<Item = (usize, T)>;
148
149impl<T, I> From<I> for DepthFirstSequence<T, I>
150where
151 I: IntoIterator<Item = (usize, T)>,
152{
153 fn from(iter: I) -> Self {
154 Self(iter)
155 }
156}
157
158/// A depth first sequence, or [`DepthFirstSequence`] is simply a sequence of `(usize, T)` tuples
159/// corresponding to (depth, value) pairs of nodes of a tree which are ordered by the depth-first
160/// traversal order.
161///
162/// Therefore, not all `IntoIterator<Item = (usize, T)>` types satisfy the depth-first sequence
163/// requirement.
164/// The invalid sequences are represented by the `DepthFirstSequenceError` type.
165#[derive(Debug, Clone, PartialEq, Eq)]
166pub enum DepthFirstSequenceError {
167 /// The first element of the depth-first sequence must be the root with depth 0.
168 /// Therefore, any sequence with a first element having a non-zero depth leads to this error.
169 ///
170 /// Note that empty sequences are valid and represent an empty tree.
171 NonZeroRootDepth,
172 /// While traversing a tree in depth first order, we
173 ///
174 /// * either move one level down to access the child (depth = previous depth + 1)
175 /// * or stay at the same level to access the sibling to the right (depth = previous depth)
176 /// * or move up and then right to access the next child of an ancestor (depth < previous depth)
177 ///
178 /// This list represents valid depth transition.
179 /// However, we never
180 ///
181 /// * move n > 1 level down (depth > previous depth + 1)
182 ///
183 /// This leaves a gap in the depth-first traversal, and hance, is the invalid case that this
184 /// error variant represents.
185 DepthIncreaseGreaterThanOne {
186 /// Depth of the node where the error is observed.
187 depth: usize,
188 /// Depth succeeding the `depth` which is at least two more than the previous.
189 succeeding_depth: usize,
190 },
191}
192
193impl<I, V, M, P> TryFrom<DepthFirstSequence<V::Item, I>> for Tree<V, M, P>
194where
195 V: TreeVariant,
196 M: MemoryPolicy,
197 P: PinnedStorage,
198 P::PinnedVec<V>: Default,
199 I: IntoIterator<Item = (usize, V::Item)>,
200{
201 type Error = DepthFirstSequenceError;
202
203 /// Tries to convert a depth-first sequence into a valid tree.
204 /// Returns the corresponding [`DepthFirstSequenceError`] if the sequence is invalid.
205 ///
206 /// Note that:
207 ///
208 /// * A [`DepthFirstSequence`] is just a wrapper of any `IntoIterator<Item = (usize, T)>` implementor
209 /// that can be crated using the `From` trait => `DepthFirstSequence::from([(0, "a"), (1, "b")])`.
210 /// * However, not all `IntoIterator<Item = (usize, T)>` instances represent a valid depth first
211 /// sequence. Therefore, the conversion is fallible.
212 fn try_from(value: DepthFirstSequence<V::Item, I>) -> Result<Self, Self::Error> {
213 let mut iter = value.0.into_iter();
214 match iter.next() {
215 None => Ok(Tree::default()),
216 Some((d, root)) => match d {
217 0 => {
218 let mut tree = Tree::new_with_root(root);
219 match tree.root_mut().try_append_subtree_as_child(iter, 0) {
220 Ok(_) => Ok(tree),
221 Err((depth, succeeding_depth)) => {
222 Err(DepthFirstSequenceError::DepthIncreaseGreaterThanOne {
223 depth,
224 succeeding_depth,
225 })
226 }
227 }
228 }
229 _ => Err(DepthFirstSequenceError::NonZeroRootDepth),
230 },
231 }
232 }
233}