orx_tree/common_traits/into_iterator.rs
1use crate::{MemoryPolicy, Tree, TreeVariant, aliases::N, pinned_storage::PinnedStorage};
2use core::iter::FusedIterator;
3use orx_iterable::{Collection, CollectionMut, Iterable};
4
5// owned
6
7impl<V, M, P> IntoIterator for Tree<V, M, P>
8where
9 V: TreeVariant,
10 M: MemoryPolicy,
11 P: PinnedStorage,
12{
13 type Item = V::Item;
14
15 type IntoIter = TreeIntoIter<V, <<P as PinnedStorage>::PinnedVec<V> as IntoIterator>::IntoIter>;
16
17 /// Consumes the tree and creates an iterator over the data of the nodes of the tree in
18 /// a deterministic but an arbitrary order.
19 ///
20 /// In order to take the values out of the tree in a particular order,
21 /// you may use [`into_walk`] method on the root of the tree (or on any subtree) with the desired traverser.
22 ///
23 /// [`into_walk`]: crate::NodeMut::into_walk
24 ///
25 /// # Examples
26 ///
27 /// ```
28 /// use orx_tree::*;
29 ///
30 /// // 0
31 /// // ╱ ╲
32 /// // ╱ ╲
33 /// // 1 2
34 /// // ╱ ╲ ╱ ╲
35 /// // 3 4 5 6
36 /// // |
37 /// // 7
38 ///
39 /// let mut tree = DaryTree::<4, _>::new(0);
40 ///
41 /// let mut root = tree.root_mut();
42 /// let [id1, id2] = root.push_children([1, 2]);
43 ///
44 /// let mut n1 = tree.node_mut(&id1);
45 /// let [id3, _] = n1.push_children([3, 4]);
46 ///
47 /// tree.node_mut(&id3).push_child(7);
48 ///
49 /// let mut n2 = tree.node_mut(&id2);
50 /// n2.push_children([5, 6]);
51 ///
52 /// // transform the tree into an arbitrary order iterator
53 ///
54 /// let values: Vec<_> = tree.into_iter().collect();
55 /// assert_eq!(values, [0, 1, 2, 3, 4, 7, 5, 6]);
56 /// ```
57 fn into_iter(self) -> Self::IntoIter {
58 let (col, _) = self.0.into_inner();
59 let (pinned_vec, _, _) = col.into_inner();
60 TreeIntoIter {
61 iter: pinned_vec.into_iter(),
62 }
63 }
64}
65
66pub struct TreeIntoIter<V, I>
67where
68 V: TreeVariant,
69 I: Iterator<Item = N<V>>,
70{
71 iter: I,
72}
73
74impl<V, I> Iterator for TreeIntoIter<V, I>
75where
76 V: TreeVariant,
77 I: Iterator<Item = N<V>>,
78{
79 type Item = V::Item;
80
81 #[inline]
82 fn next(&mut self) -> Option<Self::Item> {
83 loop {
84 match self.iter.next() {
85 None => return None,
86 Some(mut node) => {
87 if node.is_active() {
88 return node.take_data();
89 }
90 }
91 }
92 }
93 }
94}
95
96impl<V, I> FusedIterator for TreeIntoIter<V, I>
97where
98 V: TreeVariant,
99 I: Iterator<Item = N<V>>,
100{
101}
102
103// ref
104
105type PinnedVecIter<'a, V, P> =
106 <<<P as PinnedStorage>::PinnedVec<V> as Collection>::Iterable<'a> as Iterable>::Iter;
107
108impl<'a, V, M, P> IntoIterator for &'a Tree<V, M, P>
109where
110 V: TreeVariant,
111 M: MemoryPolicy,
112 P: PinnedStorage,
113{
114 type Item = &'a V::Item;
115
116 type IntoIter = TreeIter<'a, V, PinnedVecIter<'a, V, P>>;
117
118 /// Creates an iterator over references to the data of the nodes of the tree in
119 /// a deterministic but an arbitrary order.
120 ///
121 /// In order to iterate over the values the tree nodes in a particular order,
122 /// you may use [`walk`] method on the root of the tree (or on any subtree) with the desired traverser.
123 ///
124 /// [`walk`]: crate::NodeRef::walk
125 ///
126 /// # Examples
127 ///
128 /// ```
129 /// use orx_tree::*;
130 ///
131 /// // 0
132 /// // ╱ ╲
133 /// // ╱ ╲
134 /// // 1 2
135 /// // ╱ ╲ ╱ ╲
136 /// // 3 4 5 6
137 /// // |
138 /// // 7
139 ///
140 /// let mut tree = DaryTree::<4, _>::new(0);
141 ///
142 /// let mut root = tree.root_mut();
143 /// let [id1, id2] = root.push_children([1, 2]);
144 ///
145 /// let mut n1 = tree.node_mut(&id1);
146 /// let [id3, _] = n1.push_children([3, 4]);
147 ///
148 /// tree.node_mut(&id3).push_child(7);
149 ///
150 /// let mut n2 = tree.node_mut(&id2);
151 /// n2.push_children([5, 6]);
152 ///
153 /// // iterate over the tree in an arbitrary order
154 ///
155 /// let values: Vec<_> = (&tree).into_iter().copied().collect();
156 /// assert_eq!(values, [0, 1, 2, 3, 4, 7, 5, 6]);
157 ///
158 /// // since Tree auto-implements orx_iterable::Collection
159 /// let values: Vec<_> = tree.iter().copied().collect();
160 /// assert_eq!(values, [0, 1, 2, 3, 4, 7, 5, 6]);
161 /// ```
162 fn into_iter(self) -> Self::IntoIter {
163 TreeIter {
164 iter: self.0.nodes().iter(),
165 }
166 }
167}
168
169pub struct TreeIter<'a, V, I>
170where
171 V: TreeVariant + 'a,
172 I: Iterator<Item = &'a N<V>>,
173{
174 iter: I,
175}
176
177impl<'a, V, I> Iterator for TreeIter<'a, V, I>
178where
179 V: TreeVariant + 'a,
180 I: Iterator<Item = &'a N<V>>,
181{
182 type Item = &'a V::Item;
183
184 #[inline]
185 fn next(&mut self) -> Option<Self::Item> {
186 loop {
187 match self.iter.next() {
188 None => return None,
189 Some(node) => {
190 if node.is_active() {
191 return node.data();
192 }
193 }
194 }
195 }
196 }
197}
198
199impl<'a, V, I> FusedIterator for TreeIter<'a, V, I>
200where
201 V: TreeVariant + 'a,
202 I: Iterator<Item = &'a N<V>>,
203{
204}
205
206// mut
207
208type PinnedVecIterMut<'a, V, P> =
209 <<P as PinnedStorage>::PinnedVec<V> as CollectionMut>::IterMut<'a>;
210
211impl<'a, V, M, P> IntoIterator for &'a mut Tree<V, M, P>
212where
213 V: TreeVariant,
214 M: MemoryPolicy,
215 P: PinnedStorage,
216{
217 type Item = &'a mut V::Item;
218
219 type IntoIter = TreeIterMut<'a, V, PinnedVecIterMut<'a, V, P>>;
220
221 /// Creates a mutable iterator over references to the data of the nodes of the tree in
222 /// a deterministic but an arbitrary order.
223 ///
224 /// In order to iterate over the values the tree nodes in a particular order,
225 /// you may use [`walk_mut`] method on the root of the tree (or on any subtree) with the desired traverser.
226 ///
227 /// [`walk_mut`]: crate::NodeMut::walk_mut
228 ///
229 /// # Examples
230 ///
231 /// ```
232 /// use orx_tree::*;
233 ///
234 /// // 0
235 /// // ╱ ╲
236 /// // ╱ ╲
237 /// // 1 2
238 /// // ╱ ╲ ╱ ╲
239 /// // 3 4 5 6
240 /// // |
241 /// // 7
242 ///
243 /// let mut tree = DaryTree::<4, _>::new(0);
244 ///
245 /// let mut root = tree.root_mut();
246 /// let [id1, id2] = root.push_children([1, 2]);
247 ///
248 /// let mut n1 = tree.node_mut(&id1);
249 /// let [id3, _] = n1.push_children([3, 4]);
250 ///
251 /// tree.node_mut(&id3).push_child(7);
252 ///
253 /// let mut n2 = tree.node_mut(&id2);
254 /// n2.push_children([5, 6]);
255 ///
256 /// // mutably iterate over the tree in an arbitrary order
257 ///
258 /// for x in (&mut tree).into_iter() {
259 /// *x += 5;
260 /// }
261 ///
262 /// // since Tree auto-implements orx_iterable::CollectionMut
263 ///
264 /// for x in tree.iter_mut() {
265 /// *x += 5;
266 /// }
267 ///
268 /// // validate
269 ///
270 /// let values: Vec<_> = tree.root().walk::<Bfs>().copied().collect();
271 /// assert_eq!(values, [10, 11, 12, 13, 14, 15, 16, 17]);
272 /// ```
273 fn into_iter(self) -> Self::IntoIter {
274 TreeIterMut {
275 iter: self.0.nodes_mut().iter_mut(),
276 }
277 }
278}
279
280pub struct TreeIterMut<'a, V, I>
281where
282 V: TreeVariant + 'a,
283 I: Iterator<Item = &'a mut N<V>>,
284{
285 iter: I,
286}
287
288impl<'a, V, I> Iterator for TreeIterMut<'a, V, I>
289where
290 V: TreeVariant + 'a,
291 I: Iterator<Item = &'a mut N<V>>,
292{
293 type Item = &'a mut V::Item;
294
295 #[inline(always)]
296 fn next(&mut self) -> Option<Self::Item> {
297 loop {
298 match self.iter.next() {
299 None => return None,
300 Some(node) => {
301 if node.is_active() {
302 return node.data_mut();
303 }
304 }
305 }
306 }
307 }
308}
309
310impl<'a, V, I> FusedIterator for TreeIterMut<'a, V, I>
311where
312 V: TreeVariant + 'a,
313 I: Iterator<Item = &'a mut N<V>>,
314{
315}