orx_tree/tree.rs
1use crate::{
2 Node, NodeIdx, NodeMut, NodeSwapError, TreeVariant,
3 aliases::Col,
4 iter::AncestorsIterPtr,
5 memory::{Auto, MemoryPolicy},
6 pinned_storage::{PinnedStorage, SplitRecursive},
7 tree_node_idx::INVALID_IDX_ERROR,
8 tree_variant::RefsChildren,
9};
10use orx_selfref_col::{NodeIdxError, NodePtr, RefsSingle};
11
12/// Core tree structure.
13pub struct Tree<V, M = Auto, P = SplitRecursive>(pub(crate) Col<V, M, P>)
14where
15 V: TreeVariant,
16 M: MemoryPolicy,
17 P: PinnedStorage;
18
19impl<V> Tree<V, Auto, SplitRecursive>
20where
21 V: TreeVariant,
22{
23 /// Creates a new tree including the root node with the given `root_value`.
24 ///
25 /// Note that the following is the preferred constructor for non-empty trees
26 ///
27 /// ```ignore
28 /// let tree = DynTree::new(42);
29 /// ```
30 ///
31 /// while it is equivalent and shorthand for the following:
32 ///
33 /// ```ignore
34 /// let mut tree = DynTree::empty();
35 /// tree.push_root(42);
36 /// ```
37 ///
38 /// # Examples
39 ///
40 /// ```rust
41 /// use orx_tree::*;
42 ///
43 /// let tree = DynTree::new(42);
44 ///
45 /// assert_eq!(tree.len(), 1);
46 /// assert_eq!(tree.root().data(), &42);
47 /// ```
48 pub fn new(root_value: V::Item) -> Self {
49 Self::new_with_root(root_value)
50 }
51
52 /// Creates an empty tree.
53 ///
54 /// You may call [`push_root`] to instantiate the empty tree.
55 ///
56 /// [`push_root`]: Self::push_root
57 ///
58 /// # Examples
59 ///
60 /// ```rust
61 /// use orx_tree::*;
62 ///
63 /// let tree = DynTree::<String>::empty();
64 ///
65 /// assert!(tree.is_empty());
66 /// assert_eq!(tree.get_root(), None);
67 /// ```
68 pub fn empty() -> Self {
69 Self(Col::<V, Auto, SplitRecursive>::new())
70 }
71}
72
73impl<V, M, P> Default for Tree<V, M, P>
74where
75 V: TreeVariant,
76 M: MemoryPolicy,
77 P: PinnedStorage,
78 P::PinnedVec<V>: Default,
79{
80 fn default() -> Self {
81 Self(Col::<V, M, P>::default())
82 }
83}
84
85impl<V, M, P> Tree<V, M, P>
86where
87 V: TreeVariant,
88 M: MemoryPolicy,
89 P: PinnedStorage,
90{
91 /// ***O(1)*** Returns the number of nodes in the tree.
92 ///
93 /// # Examples
94 ///
95 /// ```
96 /// use orx_tree::*;
97 ///
98 /// let mut tree: DynTree<i32> = DynTree::new(42);
99 /// assert_eq!(tree.len(), 1);
100 ///
101 /// let mut root = tree.root_mut();
102 /// let [_, idx] = root.push_children([4, 2]);
103 ///
104 /// assert_eq!(tree.len(), 3);
105 ///
106 /// let mut node = tree.node_mut(idx);
107 /// node.push_child(7);
108 ///
109 /// assert_eq!(tree.len(), 4);
110 /// ```
111 #[inline(always)]
112 pub fn len(&self) -> usize {
113 self.0.len()
114 }
115
116 /// Returns true if the tree is empty.
117 #[inline(always)]
118 pub fn is_empty(&self) -> bool {
119 self.0.is_empty()
120 }
121
122 /// Pushes the root to the empty tree.
123 ///
124 /// # Panics
125 ///
126 /// Panics if push_root is called when the tree is not empty.
127 ///
128 /// # Examples
129 ///
130 /// ```
131 /// use orx_tree::*;
132 ///
133 /// let mut tree: DynTree<i32> = DynTree::empty();
134 ///
135 /// assert!(tree.is_empty());
136 /// assert_eq!(tree.get_root(), None);
137 ///
138 /// tree.push_root(42);
139 /// assert!(!tree.is_empty());
140 /// assert_eq!(tree.len(), 1);
141 /// assert_eq!(tree.root().data(), &42);
142 /// ```
143 pub fn push_root(&mut self, root_value: V::Item) -> NodeIdx<V> {
144 assert!(
145 self.is_empty(),
146 "Cannot push root to the tree which already has a root."
147 );
148
149 let root_idx = self.0.push_get_idx(root_value);
150 let root_mut: &mut RefsSingle<V> = self.0.ends_mut();
151 root_mut.set_some(root_idx.node_ptr());
152
153 NodeIdx(root_idx)
154 }
155
156 /// Removes all the nodes including the root of the tree.
157 ///
158 /// # Examples
159 ///
160 /// ```
161 /// use orx_tree::*;
162 ///
163 /// let mut tree: BinaryTree<i32> = BinaryTree::new(42);
164 ///
165 /// let mut root = tree.root_mut();
166 /// root.push_child(4);
167 /// let [idx] = root.push_children([2]);
168 ///
169 /// let mut node = tree.node_mut(idx);
170 /// node.push_child(7);
171 ///
172 /// assert_eq!(tree.len(), 4);
173 /// assert_eq!(tree.root().data(), &42);
174 ///
175 /// tree.clear();
176 /// assert!(tree.is_empty());
177 /// assert_eq!(tree.get_root(), None);
178 /// ```
179 pub fn clear(&mut self) {
180 self.0.clear();
181 self.0.ends_mut().set_none();
182 }
183
184 // get root
185
186 /// Returns the root node of the tree.
187 ///
188 /// # Panics
189 ///
190 /// Panics if the tree is empty and has no root.
191 ///
192 /// When not certain, you may use [`is_empty`] or [`get_root`] methods to have a safe access.
193 ///
194 /// [`is_empty`]: Self::is_empty
195 /// [`get_root`]: Self::get_root
196 ///
197 /// # Examples
198 ///
199 /// ```
200 /// use orx_tree::*;
201 ///
202 /// // initiate a rooted tree
203 /// let mut tree = DynTree::<_>::new('a');
204 /// assert_eq!(tree.root().data(), &'a');
205 ///
206 /// tree.clear();
207 /// // assert_eq!(tree.get_root().data(), 'x'); // panics!
208 ///
209 /// // initiate an empty tree
210 /// let mut tree = BinaryTree::<_>::empty();
211 /// // assert_eq!(tree.get_root().data(), 'x'); // panics!
212 ///
213 /// tree.push_root('a');
214 /// assert_eq!(tree.root().data(), &'a');
215 /// ```
216 pub fn root<'a>(&'a self) -> Node<'a, V, M, P> {
217 self.root_ptr()
218 .map(|p| Node::new(&self.0, p))
219 .expect("Tree is empty and has no root. You may use `push_root` to add a root and/or `get_root` to safely access the root if it exists.")
220 }
221
222 /// Returns the mutable root node of the tree.
223 ///
224 /// # Panics
225 ///
226 /// Panics if the tree is empty and has no root.
227 ///
228 /// When not certain, you may use [`is_empty`] or [`get_root_mut`] methods to have a safe access.
229 ///
230 /// [`is_empty`]: Self::is_empty
231 /// [`get_root_mut`]: Self::get_root_mut
232 ///
233 /// # Examples
234 ///
235 /// ```
236 /// use orx_tree::*;
237 ///
238 /// // initiate a rooted tree
239 /// let mut tree = DynTree::<_>::new('a');
240 /// *tree.root_mut().data_mut() = 'x';
241 /// assert_eq!(tree.root().data(), &'x');
242 ///
243 /// tree.clear();
244 /// // *tree.root_mut().data_mut() = 'x'; // panics!
245 ///
246 /// // initiate an empty tree
247 /// let mut tree = BinaryTree::<_>::empty();
248 /// // *tree.root_mut().data_mut() = 'x'; // panics!
249 ///
250 /// tree.push_root('a');
251 ///
252 /// // build the tree from the root
253 /// let mut root = tree.root_mut();
254 /// assert_eq!(root.data(), &'a');
255 ///
256 /// let [b, c] = root.push_children(['b', 'c']);
257 /// tree.node_mut(b).push_child('d');
258 /// tree.node_mut(c).push_children(['e', 'f']);
259 /// ```
260 pub fn root_mut<'a>(&'a mut self) -> NodeMut<'a, V, M, P> {
261 self.root_ptr()
262 .map(|p| NodeMut::new(&mut self.0, p))
263 .expect("Tree is empty and has no root. You may use `push_root` to add a root and/or `get_root` to safely access the root if it exists.")
264 }
265
266 /// Returns the root node of the tree; None if the tree is empty.
267 ///
268 /// # Examples
269 ///
270 /// ```
271 /// use orx_tree::*;
272 ///
273 /// // initiate a rooted tree
274 /// let mut tree = DynTree::<_>::new('a');
275 /// assert_eq!(tree.root().data(), &'a');
276 ///
277 /// tree.clear();
278 /// assert_eq!(tree.get_root(), None);
279 ///
280 /// // initiate an empty tree
281 /// let mut tree = BinaryTree::<_>::empty();
282 /// assert_eq!(tree.get_root(), None);
283 ///
284 /// tree.push_root('a');
285 /// assert_eq!(tree.root().data(), &'a');
286 /// ```
287 pub fn get_root<'a>(&'a self) -> Option<Node<'a, V, M, P>> {
288 self.root_ptr().map(|p| Node::new(&self.0, p))
289 }
290
291 /// Returns the root as a mutable node of the tree; None if the tree is empty.
292 ///
293 /// # Examples
294 ///
295 /// ```
296 /// use orx_tree::*;
297 ///
298 /// let mut tree = DynTree::<_>::new('a');
299 ///
300 /// let mut root = tree.root_mut();
301 ///
302 /// assert_eq!(root.data(), &'a');
303 /// *root.data_mut() = 'x';
304 /// assert_eq!(root.data(), &'x');
305 ///
306 /// root.push_child('b');
307 /// let idx = root.push_child('c');
308 ///
309 /// tree.clear();
310 /// assert_eq!(tree.get_root_mut(), None);
311 /// ```
312 pub fn get_root_mut<'a>(&'a mut self) -> Option<NodeMut<'a, V, M, P>> {
313 self.root_ptr().map(|p| NodeMut::new(&mut self.0, p))
314 }
315
316 // get nodes
317
318 /// Returns true if the `node_idx` is valid for this tree.
319 ///
320 /// Returns false if any of the following holds:
321 ///
322 /// * the node index is created from a different tree => [`NodeIdxError::OutOfBounds`]
323 /// * the node that this index is created for is removed from the tree => [`NodeIdxError::RemovedNode`]
324 /// * the tree is using `Auto` memory reclaim policy and nodes are reorganized due to node removals
325 /// => [`NodeIdxError::ReorganizedCollection`]
326 ///
327 /// Please see [`NodeIdx`] documentation for details on the validity of node indices.
328 ///
329 /// * If [`is_node_idx_valid`] is true, then [`node_idx_error`] is None;
330 /// * If [`is_node_idx_valid`] is false, then [`node_idx_error`] is Some.
331 ///
332 /// [`is_node_idx_valid`]: crate::Tree::is_node_idx_valid
333 /// [`node_idx_error`]: crate::Tree::node_idx_error
334 #[inline(always)]
335 pub fn is_node_idx_valid(&self, node_idx: NodeIdx<V>) -> bool {
336 node_idx.0.is_valid_for(&self.0)
337 }
338
339 /// Returns the node index error if the `node_idx` is invalid.
340 /// Returns None if the index is valid for this tree.
341 ///
342 /// Returns Some if any of the following holds:
343 ///
344 /// * the node index is created from a different tree => [`NodeIdxError::OutOfBounds`]
345 /// * the node that this index is created for is removed from the tree => [`NodeIdxError::RemovedNode`]
346 /// * the tree is using `Auto` memory reclaim policy and nodes are reorganized due to node removals
347 /// => [`NodeIdxError::ReorganizedCollection`]
348 ///
349 /// * If [`is_node_idx_valid`] is true, then [`node_idx_error`] is None;
350 /// * If [`is_node_idx_valid`] is false, then [`node_idx_error`] is Some.
351 ///
352 /// [`is_node_idx_valid`]: crate::Tree::is_node_idx_valid
353 /// [`node_idx_error`]: crate::Tree::node_idx_error
354 pub fn node_idx_error(&self, node_idx: NodeIdx<V>) -> Option<NodeIdxError> {
355 self.0.node_idx_error(node_idx.0)
356 }
357
358 /// Returns the node with the given `node_idx`.
359 ///
360 /// # Panics
361 ///
362 /// Panics if this node index is not valid for the given `tree`; i.e., when either of the following holds:
363 ///
364 /// * the node index is created from a different tree => [`NodeIdxError::OutOfBounds`]
365 /// * the node that this index is created for is removed from the tree => [`NodeIdxError::RemovedNode`]
366 /// * the tree is using `Auto` memory reclaim policy and nodes are reorganized due to node removals
367 /// => [`NodeIdxError::ReorganizedCollection`]
368 ///
369 /// When not certain, you may use [`is_node_idx_valid`] or [`get_node`] methods to have a safe access.
370 ///
371 /// Please see [`NodeIdx`] documentation for details on the validity of node indices.
372 ///
373 /// [`is_node_idx_valid`]: crate::Tree::is_node_idx_valid
374 /// [`get_node`]: Self::get_node
375 ///
376 /// [`NodeIdxError::OutOfBounds`]: crate::NodeIdxError::OutOfBounds
377 /// [`NodeIdxError::RemovedNode`]: crate::NodeIdxError::RemovedNode
378 /// [`NodeIdxError::ReorganizedCollection`]: crate::NodeIdxError::ReorganizedCollection
379 ///
380 /// # Examples
381 ///
382 /// ```
383 /// use orx_tree::*;
384 ///
385 /// // 1
386 /// // ╱ ╲
387 /// // ╱ ╲
388 /// // 2 3
389 /// // ╱ ╲
390 /// // 4 5
391 ///
392 /// let mut tree = DynTree::new(1);
393 ///
394 /// let mut root = tree.root_mut();
395 /// let [id2, id3] = root.push_children([2, 3]);
396 ///
397 /// let n2 = tree.node(id2);
398 /// assert_eq!(n2.data(), &2);
399 ///
400 /// let mut n3 = tree.node_mut(id3);
401 /// n3.push_children([4, 5]);
402 ///
403 /// let bfs_values: Vec<_> = tree.root().walk::<Bfs>().copied().collect();
404 /// assert_eq!(bfs_values, [1, 2, 3, 4, 5]);
405 /// ```
406 #[inline(always)]
407 pub fn node<'a>(&'a self, node_idx: NodeIdx<V>) -> Node<'a, V, M, P> {
408 assert!(self.is_node_idx_valid(node_idx), "{INVALID_IDX_ERROR}");
409 Node::new(&self.0, node_idx.0.node_ptr())
410 }
411
412 /// Returns the mutable node with the given `node_idx`.
413 ///
414 /// # Panics
415 ///
416 /// Panics if this node index is not valid for the given `tree`; i.e., when either of the following holds:
417 ///
418 /// * the node index is created from a different tree => [`NodeIdxError::OutOfBounds`]
419 /// * the node that this index is created for is removed from the tree => [`NodeIdxError::RemovedNode`]
420 /// * the tree is using `Auto` memory reclaim policy and nodes are reorganized due to node removals
421 /// => [`NodeIdxError::ReorganizedCollection`]
422 ///
423 /// When not certain, you may use [`is_node_idx_valid`] or [`get_node_mut`] methods to have a safe access.
424 ///
425 /// Please see [`NodeIdx`] documentation for details on the validity of node indices.
426 ///
427 /// [`is_node_idx_valid`]: crate::Tree::is_node_idx_valid
428 /// [`get_node_mut`]: Self::get_node_mut
429 ///
430 /// [`NodeIdxError::OutOfBounds`]: crate::NodeIdxError::OutOfBounds
431 /// [`NodeIdxError::RemovedNode`]: crate::NodeIdxError::RemovedNode
432 /// [`NodeIdxError::ReorganizedCollection`]: crate::NodeIdxError::ReorganizedCollection
433 ///
434 /// # Examples
435 ///
436 /// ```
437 /// use orx_tree::*;
438 ///
439 /// // 1
440 /// // ╱ ╲
441 /// // ╱ ╲
442 /// // 2 3
443 /// // ╱ ╲
444 /// // 4 5
445 ///
446 /// let mut tree = DynTree::new(1);
447 ///
448 /// let mut root = tree.root_mut();
449 /// let [id2, id3] = root.push_children([2, 3]);
450 ///
451 /// let n2 = tree.node(id2);
452 /// assert_eq!(n2.data(), &2);
453 ///
454 /// let mut n3 = tree.node_mut(id3);
455 /// n3.push_children([4, 5]);
456 ///
457 /// let bfs_values: Vec<_> = tree.root().walk::<Bfs>().copied().collect();
458 /// assert_eq!(bfs_values, [1, 2, 3, 4, 5]);
459 /// ```
460 #[inline(always)]
461 pub fn node_mut<'a>(&'a mut self, node_idx: NodeIdx<V>) -> NodeMut<'a, V, M, P> {
462 assert!(self.is_node_idx_valid(node_idx), "{INVALID_IDX_ERROR}");
463 NodeMut::new(&mut self.0, node_idx.0.node_ptr())
464 }
465
466 /// Returns the node with the given `node_idx`; returns None if the node index is invalid.
467 ///
468 /// The node index is invalid if any of the following holds:
469 ///
470 /// * the node index is created from a different tree => [`NodeIdxError::OutOfBounds`]
471 /// * the node that this index is created for is removed from the tree => [`NodeIdxError::RemovedNode`]
472 /// * the tree is using `Auto` memory reclaim policy and nodes are reorganized due to node removals
473 /// => [`NodeIdxError::ReorganizedCollection`]
474 ///
475 /// You may use [`try_node`] method to get the underlying reason when the index is invalid.
476 ///
477 /// Please see [`NodeIdx`] documentation for details on the validity of node indices.
478 ///
479 /// [`try_node`]: Self::try_node
480 /// [`NodeIdxError::OutOfBounds`]: crate::NodeIdxError::OutOfBounds
481 /// [`NodeIdxError::RemovedNode`]: crate::NodeIdxError::RemovedNode
482 /// [`NodeIdxError::ReorganizedCollection`]: crate::NodeIdxError::ReorganizedCollection
483 #[inline(always)]
484 pub fn get_node<'a>(&'a self, node_idx: NodeIdx<V>) -> Option<Node<'a, V, M, P>> {
485 self.is_node_idx_valid(node_idx)
486 .then(|| Node::new(&self.0, node_idx.0.node_ptr()))
487 }
488
489 /// Returns the mutable node with the given `node_idx`; returns None if the node index is invalid.
490 ///
491 /// The node index is invalid if any of the following holds:
492 ///
493 /// * the node index is created from a different tree => [`NodeIdxError::OutOfBounds`]
494 /// * the node that this index is created for is removed from the tree => [`NodeIdxError::RemovedNode`]
495 /// * the tree is using `Auto` memory reclaim policy and nodes are reorganized due to node removals
496 /// => [`NodeIdxError::ReorganizedCollection`]
497 ///
498 /// You may use [`try_node_mut`] method to get the underlying reason when the index is invalid.
499 ///
500 /// Please see [`NodeIdx`] documentation for details on the validity of node indices.
501 ///
502 /// [`try_node_mut`]: Self::try_node_mut
503 /// [`NodeIdxError::OutOfBounds`]: crate::NodeIdxError::OutOfBounds
504 /// [`NodeIdxError::RemovedNode`]: crate::NodeIdxError::RemovedNode
505 /// [`NodeIdxError::ReorganizedCollection`]: crate::NodeIdxError::ReorganizedCollection
506 #[inline(always)]
507 pub fn get_node_mut<'a>(&'a mut self, node_idx: NodeIdx<V>) -> Option<NodeMut<'a, V, M, P>> {
508 self.is_node_idx_valid(node_idx)
509 .then(|| NodeMut::new(&mut self.0, node_idx.0.node_ptr()))
510 }
511
512 /// Returns the node with the given `node_idx`; returns the corresponding error if the node index is invalid.
513 ///
514 /// The node index is invalid if any of the following holds:
515 ///
516 /// * the node index is created from a different tree => [`NodeIdxError::OutOfBounds`]
517 /// * the node that this index is created for is removed from the tree => [`NodeIdxError::RemovedNode`]
518 /// * the tree is using `Auto` memory reclaim policy and nodes are reorganized due to node removals
519 /// => [`NodeIdxError::ReorganizedCollection`]
520 ///
521 /// Please see [`NodeIdx`] documentation for details on the validity of node indices.
522 ///
523 /// [`try_node`]: Self::try_node
524 /// [`NodeIdxError::OutOfBounds`]: crate::NodeIdxError::OutOfBounds
525 /// [`NodeIdxError::RemovedNode`]: crate::NodeIdxError::RemovedNode
526 /// [`NodeIdxError::ReorganizedCollection`]: crate::NodeIdxError::ReorganizedCollection
527 #[inline(always)]
528 pub fn try_node<'a>(&'a self, node_idx: NodeIdx<V>) -> Result<Node<'a, V, M, P>, NodeIdxError> {
529 self.0
530 .try_get_ptr(node_idx.0)
531 .map(|ptr| Node::new(&self.0, ptr))
532 }
533
534 /// Returns the node with the given `node_idx`; returns the corresponding error if the node index is invalid.
535 ///
536 /// The node index is invalid if any of the following holds:
537 ///
538 /// * the node index is created from a different tree => [`NodeIdxError::OutOfBounds`]
539 /// * the node that this index is created for is removed from the tree => [`NodeIdxError::RemovedNode`]
540 /// * the tree is using `Auto` memory reclaim policy and nodes are reorganized due to node removals
541 /// => [`NodeIdxError::ReorganizedCollection`]
542 ///
543 /// Please see [`NodeIdx`] documentation for details on the validity of node indices.
544 ///
545 /// [`try_node`]: Self::try_node
546 /// [`NodeIdxError::OutOfBounds`]: crate::NodeIdxError::OutOfBounds
547 /// [`NodeIdxError::RemovedNode`]: crate::NodeIdxError::RemovedNode
548 /// [`NodeIdxError::ReorganizedCollection`]: crate::NodeIdxError::ReorganizedCollection
549 #[inline(always)]
550 pub fn try_node_mut<'a>(
551 &'a mut self,
552 node_idx: NodeIdx<V>,
553 ) -> Result<NodeMut<'a, V, M, P>, NodeIdxError> {
554 self.0
555 .try_get_ptr(node_idx.0)
556 .map(|ptr| NodeMut::new(&mut self.0, ptr))
557 }
558
559 /// Returns the node with the given `node_idx`.
560 ///
561 /// # Safety
562 ///
563 /// It omits the index validity assertions that [`node`] method performs; hence it is only safe to use
564 /// this method when we are certain that '`is_node_idx_valid`' would have returned true.
565 ///
566 /// [`node`]: Self::node
567 /// [`is_node_idx_valid`]: Self::is_node_idx_valid
568 #[inline(always)]
569 pub unsafe fn node_unchecked<'a>(&'a self, node_idx: NodeIdx<V>) -> Node<'a, V, M, P> {
570 Node::new(&self.0, node_idx.0.node_ptr())
571 }
572
573 /// Returns the mutable node with the given `node_idx`.
574 ///
575 /// # Safety
576 ///
577 /// It omits the index validity assertions that [`node_mut`] method performs; hence it is only safe to use
578 /// this method when we are certain that '`is_node_idx_valid`' would have returned true.
579 ///
580 /// [`node_mut`]: Self::node_mut
581 /// [`is_node_idx_valid`]: Self::is_node_idx_valid
582 #[inline(always)]
583 pub unsafe fn node_mut_unchecked<'a>(
584 &'a mut self,
585 node_idx: NodeIdx<V>,
586 ) -> NodeMut<'a, V, M, P> {
587 NodeMut::new(&mut self.0, node_idx.0.node_ptr())
588 }
589
590 // move nodes
591
592 /// ***O(1)*** Tries to swap the nodes together with their subtrees rooted at the given `first_idx` and `second_idx`
593 /// in constant time (*).
594 ///
595 /// The indices remain valid.
596 ///
597 /// In order to have a valid swap operation, the two subtrees must be **independent** of each other without
598 /// any shared node. Necessary and sufficient condition is then as follows:
599 ///
600 /// * node with the `first_idx` is not an ancestor of the node with the `second_idx`,
601 /// * and vice versa.
602 ///
603 /// Swap operation will succeed if both indices are valid and the above condition holds. Panics ...
604 ///
605 /// # Panics
606 ///
607 /// * Panics if either of the node indices is invalid.
608 /// * Panics if node with the `first_idx` is an ancestor of the node with the `second_idx`; or vice versa.
609 ///
610 /// # See also
611 ///
612 /// (*) Validation of the independence of the subtrees is performed in ***O(D)*** time where D is the maximum
613 /// depth of the tree. When we are certain that the subtrees do not intersect, we can use the unsafe variant
614 /// [`swap_subtrees_unchecked`] to bypass the validation.
615 ///
616 /// See also:
617 ///
618 /// * [`swap_data_with`]
619 /// * [`swap_subtrees`]
620 /// * [`try_swap_nodes`]
621 /// * [`swap_subtrees_unchecked`]
622 ///
623 /// [`swap_data_with`]: crate::NodeMut::swap_data_with
624 /// [`swap_subtrees`]: crate::Tree::swap_subtrees
625 /// [`try_swap_nodes`]: crate::Tree::try_swap_nodes
626 /// [`swap_subtrees_unchecked`]: crate::Tree::swap_subtrees_unchecked
627 ///
628 /// # Examples
629 ///
630 /// ```
631 /// use orx_tree::*;
632 ///
633 /// // 1
634 /// // ╱ ╲
635 /// // ╱ ╲
636 /// // 2 3
637 /// // ╱ ╲ ╱ ╲
638 /// // 4 5 6 7
639 /// // | | ╱ ╲
640 /// // 8 9 10 11
641 ///
642 /// let mut tree = DynTree::new(1);
643 ///
644 /// let mut root = tree.root_mut();
645 /// let [id2, id3] = root.push_children([2, 3]);
646 ///
647 /// let mut n2 = tree.node_mut(id2);
648 /// let [id4, _] = n2.push_children([4, 5]);
649 ///
650 /// tree.node_mut(id4).push_child(8);
651 ///
652 /// let mut n3 = tree.node_mut(id3);
653 /// let [id6, id7] = n3.push_children([6, 7]);
654 ///
655 /// tree.node_mut(id6).push_child(9);
656 /// let [_, _] = tree.node_mut(id7).push_children([10, 11]);
657 ///
658 /// // we can swap n2 & n7
659 /// // 1
660 /// // ╱ ╲
661 /// // ╱ ╲
662 /// // 7 3
663 /// // ╱ ╲ ╱ ╲
664 /// // 10 11 6 2
665 /// // | ╱ ╲
666 /// // 9 4 5
667 /// // |
668 /// // 8
669 ///
670 /// tree.swap_subtrees(id2, id7);
671 ///
672 /// let bfs: Vec<_> = tree.root().walk::<Bfs>().copied().collect();
673 /// assert_eq!(bfs, [1, 7, 3, 10, 11, 6, 2, 9, 4, 5, 8]);
674 /// ```
675 pub fn swap_subtrees(&mut self, first_idx: NodeIdx<V>, second_idx: NodeIdx<V>) {
676 assert!(self.is_node_idx_valid(first_idx), "{}", INVALID_IDX_ERROR);
677 assert!(self.is_node_idx_valid(second_idx), "{}", INVALID_IDX_ERROR);
678 let ptr_root = self.root_ptr().expect("tree is not empty");
679 let ptr_p = first_idx.0.node_ptr();
680 let ptr_q = second_idx.0.node_ptr();
681
682 match ptr_p == ptr_q {
683 true => {}
684 false => {
685 assert!(
686 AncestorsIterPtr::new(ptr_root, ptr_p).all(|x| x != ptr_q),
687 "Node with `second_idx` is an ancestor of the node with `first_idx`; cannot swap nodes."
688 );
689 assert!(
690 AncestorsIterPtr::new(ptr_root, ptr_q).all(|x| x != ptr_p),
691 "Node with `first_idx` is an ancestor of the node with `second_idx`; cannot swap nodes."
692 );
693 // # SAFETY: all possible error cases are checked and handled
694 unsafe { self.swap_subtrees_unchecked(first_idx, second_idx) };
695 }
696 }
697 }
698
699 /// ***O(1)*** Tries to swap the nodes together with their subtrees rooted at the given `first_idx` and `second_idx`
700 /// in constant time (*).
701 /// Returns the error if the swap operation is invalid.
702 ///
703 /// The indices remain valid.
704 ///
705 /// In order to have a valid swap operation, the two subtrees must be **independent** of each other without
706 /// any shared node. Necessary and sufficient condition is then as follows:
707 ///
708 /// * node with the `first_idx` is not an ancestor of the node with the `second_idx`,
709 /// * and vice versa.
710 ///
711 /// Swap operation will succeed and return Ok if both indices are valid and the above condition holds.
712 /// It will the corresponding [`NodeSwapError`] otherwise.
713 ///
714 /// # See also
715 ///
716 /// (*) Validation of the independence of the subtrees is performed in ***O(D)*** time where D is the maximum
717 /// depth of the tree. When we are certain that the subtrees do not intersect, we can use the unsafe variant
718 /// [`swap_subtrees_unchecked`] to bypass the validation.
719 ///
720 /// See also:
721 ///
722 /// * [`swap_data_with`]
723 /// * [`swap_subtrees`]
724 /// * [`try_swap_nodes`]
725 /// * [`swap_subtrees_unchecked`]
726 ///
727 /// [`swap_data_with`]: crate::NodeMut::swap_data_with
728 /// [`swap_subtrees`]: crate::Tree::swap_subtrees
729 /// [`try_swap_nodes`]: crate::Tree::try_swap_nodes
730 /// [`swap_subtrees_unchecked`]: crate::Tree::swap_subtrees_unchecked
731 ///
732 /// # Examples
733 ///
734 /// ```
735 /// use orx_tree::*;
736 ///
737 /// // 1
738 /// // ╱ ╲
739 /// // ╱ ╲
740 /// // 2 3
741 /// // ╱ ╲ ╱ ╲
742 /// // 4 5 6 7
743 /// // | | ╱ ╲
744 /// // 8 9 10 11
745 ///
746 /// let mut tree = DynTree::new(1);
747 ///
748 /// let mut root = tree.root_mut();
749 /// let id1 = root.idx();
750 /// let [id2, id3] = root.push_children([2, 3]);
751 ///
752 /// let mut n2 = tree.node_mut(id2);
753 /// let [id4, _] = n2.push_children([4, 5]);
754 ///
755 /// tree.node_mut(id4).push_child(8);
756 ///
757 /// let mut n3 = tree.node_mut(id3);
758 /// let [id6, id7] = n3.push_children([6, 7]);
759 ///
760 /// tree.node_mut(id6).push_child(9);
761 /// let [id10, _] = tree.node_mut(id7).push_children([10, 11]);
762 ///
763 /// // cannot swap n3 & n10
764 ///
765 /// assert_eq!(
766 /// tree.try_swap_nodes(id3, id10),
767 /// Err(NodeSwapError::FirstNodeIsAncestorOfSecond)
768 /// );
769 ///
770 /// // cannot swap n4 & n1 (root)
771 ///
772 /// assert_eq!(
773 /// tree.try_swap_nodes(id4, id1),
774 /// Err(NodeSwapError::SecondNodeIsAncestorOfFirst)
775 /// );
776 ///
777 /// // we can swap n2 & n7
778 /// // 1
779 /// // ╱ ╲
780 /// // ╱ ╲
781 /// // 7 3
782 /// // ╱ ╲ ╱ ╲
783 /// // 10 11 6 2
784 /// // | ╱ ╲
785 /// // 9 4 5
786 /// // |
787 /// // 8
788 ///
789 /// let result = tree.try_swap_nodes(id2, id7);
790 /// assert_eq!(result, Ok(()));
791 ///
792 /// let bfs: Vec<_> = tree.root().walk::<Bfs>().copied().collect();
793 /// assert_eq!(bfs, [1, 7, 3, 10, 11, 6, 2, 9, 4, 5, 8]);
794 /// ```
795 pub fn try_swap_nodes(
796 &mut self,
797 first_idx: NodeIdx<V>,
798 second_idx: NodeIdx<V>,
799 ) -> Result<(), NodeSwapError> {
800 let ptr_root = match self.root_ptr() {
801 Some(x) => x,
802 None => return Err(NodeSwapError::NodeIdxError(NodeIdxError::RemovedNode)),
803 };
804 let ptr_p = self.0.try_get_ptr(first_idx.0)?;
805 let ptr_q = self.0.try_get_ptr(second_idx.0)?;
806
807 if ptr_p == ptr_q {
808 Ok(())
809 } else if AncestorsIterPtr::new(ptr_root, ptr_p).any(|x| x == ptr_q) {
810 Err(NodeSwapError::SecondNodeIsAncestorOfFirst)
811 } else if AncestorsIterPtr::new(ptr_root, ptr_q).any(|x| x == ptr_p) {
812 Err(NodeSwapError::FirstNodeIsAncestorOfSecond)
813 } else {
814 // # SAFETY: all possible error cases are checked and handled
815 unsafe { self.swap_subtrees_unchecked(first_idx, second_idx) };
816 Ok(())
817 }
818 }
819
820 /// ***O(1)*** Swaps the nodes together with their subtrees rooted at the given `first_idx` and `second_idx`.
821 ///
822 /// The indices remain valid.
823 ///
824 /// In order to have a valid swap operation, the two subtrees must be **independent** of each other without
825 /// any shared node. Necessary and sufficient condition is then as follows:
826 ///
827 /// * node with the `first_idx` is not an ancestor of the node with the `second_idx`,
828 /// * and vice versa.
829 ///
830 /// # Panics
831 ///
832 /// * if either of the node indices is invalid, or
833 /// * if either of the indices belong to the root since this automatically invalidates the Safety condition.
834 ///
835 /// # Safety
836 ///
837 /// It is safe to use this method only when the swap operation is valid; i.e., abovementioned independence condition
838 /// of the subtrees holds.
839 ///
840 /// # See also
841 ///
842 /// * [`swap_data_with`]
843 /// * [`swap_subtrees`]
844 /// * [`try_swap_nodes`]
845 /// * [`swap_subtrees_unchecked`]
846 ///
847 /// [`swap_data_with`]: crate::NodeMut::swap_data_with
848 /// [`swap_subtrees`]: crate::Tree::swap_subtrees
849 /// [`try_swap_nodes`]: crate::Tree::try_swap_nodes
850 /// [`swap_subtrees_unchecked`]: crate::Tree::swap_subtrees_unchecked
851 ///
852 /// # Examples
853 ///
854 /// ```
855 /// use orx_tree::*;
856 ///
857 /// // 1
858 /// // ╱ ╲
859 /// // ╱ ╲
860 /// // 2 3
861 /// // ╱ ╲ ╱ ╲
862 /// // 4 5 6 7
863 /// // | | ╱ ╲
864 /// // 8 9 10 11
865 ///
866 /// let mut tree = DynTree::new(1);
867 ///
868 /// let mut root = tree.root_mut();
869 /// let [id2, id3] = root.push_children([2, 3]);
870 ///
871 /// let mut n2 = tree.node_mut(id2);
872 /// let [id4, _] = n2.push_children([4, 5]);
873 ///
874 /// tree.node_mut(id4).push_child(8);
875 ///
876 /// let mut n3 = tree.node_mut(id3);
877 /// let [id6, id7] = n3.push_children([6, 7]);
878 ///
879 /// tree.node_mut(id6).push_child(9);
880 /// let [_, _] = tree.node_mut(id7).push_children([10, 11]);
881 ///
882 /// // we can swap n2 & n5
883 /// // 1
884 /// // ╱ ╲
885 /// // ╱ ╲
886 /// // 7 3
887 /// // ╱ ╲ ╱ ╲
888 /// // 10 11 6 2
889 /// // | ╱ ╲
890 /// // 9 4 5
891 /// // |
892 /// // 8
893 ///
894 /// unsafe { tree.swap_subtrees_unchecked(id2, id7) };
895 ///
896 /// let bfs: Vec<_> = tree.root().walk::<Bfs>().copied().collect();
897 /// assert_eq!(bfs, [1, 7, 3, 10, 11, 6, 2, 9, 4, 5, 8]);
898 /// ```
899 pub unsafe fn swap_subtrees_unchecked(
900 &mut self,
901 first_idx: NodeIdx<V>,
902 second_idx: NodeIdx<V>,
903 ) {
904 swap_subtrees_unchecked::<V, M, P>(&mut self.0, first_idx, second_idx)
905 }
906
907 // parallelization
908
909 /// Creates a parallel iterator over references to the elements of the tree in **arbitrary order**.
910 ///
911 /// Note that `par` is parallel counterpart of `iter`.
912 ///
913 /// In order to iterate over data in a particular order, please use traversers with [`walk`], [`walk_mut`]
914 /// or [`into_walk`] methods.
915 ///
916 /// Please see [`ParIter`] for details of the parallel computation.
917 /// In brief, computation is defined as chain of iterator transformations and parallelization
918 /// is handled by the underlying parallel executor.
919 ///
920 /// Requires **parallel** feature.
921 ///
922 /// [`ParIter`]: orx_parallel::ParIter
923 /// [`walk`]: crate::NodeRef::walk
924 /// [`walk_mut`]: crate::NodeMut::walk_mut
925 /// [`into_walk`]: crate::NodeMut::into_walk
926 ///
927 /// # Examples
928 ///
929 /// ```
930 /// use orx_tree::*;
931 ///
932 /// let num_children = 4;
933 /// let total_depth = 8;
934 ///
935 /// let mut tree = DynTree::new(0.to_string());
936 /// let mut dfs = Traversal.dfs().over_nodes();
937 ///
938 /// for _ in 0..total_depth {
939 /// let root = tree.root();
940 /// let leaves: Vec<_> = root.leaves_with(&mut dfs).map(|x| x.idx()).collect();
941 /// for idx in leaves {
942 /// let count = tree.len();
943 /// let mut node = tree.node_mut(idx);
944 /// for j in 0..num_children {
945 /// node.push_child((count + j).to_string());
946 /// }
947 /// }
948 /// }
949 ///
950 /// let seq_result: usize = tree
951 /// .iter()
952 /// .filter_map(|x| x.parse::<usize>().ok())
953 /// .filter(|x| x % 2 == 0)
954 /// .sum();
955 ///
956 /// // compute in parallel with default configuration
957 /// let par_result = tree
958 /// .par() // replace iter() with par()
959 /// .filter_map(|x| x.parse::<usize>().ok())
960 /// .filter(|x| x % 2 == 0)
961 /// .sum();
962 /// assert_eq!(seq_result, par_result);
963 ///
964 /// // configure parallel computation
965 /// let par_result = tree
966 /// .par()
967 /// .num_threads(4)
968 /// .chunk_size(64)
969 /// .filter_map(|x| x.parse::<usize>().ok())
970 /// .filter(|x| x % 2 == 0)
971 /// .sum();
972 /// assert_eq!(seq_result, par_result);
973 /// ```
974 #[cfg(feature = "parallel")]
975 pub fn par(&self) -> impl orx_parallel::ParIter<Item = &V::Item>
976 where
977 V::Item: Send + Sync,
978 for<'a> &'a <P as PinnedStorage>::PinnedVec<V>:
979 orx_concurrent_iter::IntoConcurrentIter<Item = &'a crate::aliases::N<V>>,
980 {
981 use orx_parallel::*;
982
983 let pinned = self.0.nodes();
984 pinned.par().filter_map(|x| x.data())
985 }
986
987 /// Consumes the tree and creates a parallel iterator over owned elements of the tree in **arbitrary order**.
988 ///
989 /// Note that `into_par` is parallel counterpart of `into_iter`.
990 ///
991 /// In order to iterate over data in a particular order, please use traversers with [`walk`], [`walk_mut`]
992 /// or [`into_walk`] methods.
993 ///
994 /// Please see [`ParIter`] for details of the parallel computation.
995 /// In brief, computation is defined as chain of iterator transformations and parallelization
996 /// is handled by the underlying parallel executor.
997 ///
998 /// Requires **parallel** feature.
999 ///
1000 /// [`ParIter`]: orx_parallel::ParIter
1001 /// [`walk`]: crate::NodeRef::walk
1002 /// [`walk_mut`]: crate::NodeMut::walk_mut
1003 /// [`into_walk`]: crate::NodeMut::into_walk
1004 ///
1005 /// # Examples
1006 ///
1007 /// ```
1008 /// use orx_tree::*;
1009 ///
1010 /// let num_children = 4;
1011 /// let total_depth = 8;
1012 ///
1013 /// let mut tree = DynTree::new(0.to_string());
1014 /// let mut dfs = Traversal.dfs().over_nodes();
1015 ///
1016 /// for _ in 0..total_depth {
1017 /// let root = tree.root();
1018 /// let leaves: Vec<_> = root.leaves_with(&mut dfs).map(|x| x.idx()).collect();
1019 /// for idx in leaves {
1020 /// let count = tree.len();
1021 /// let mut node = tree.node_mut(idx);
1022 /// for j in 0..num_children {
1023 /// node.push_child((count + j).to_string());
1024 /// }
1025 /// }
1026 /// }
1027 ///
1028 /// let seq_result: usize = tree
1029 /// .clone()
1030 /// .into_iter()
1031 /// .filter_map(|x| x.parse::<usize>().ok())
1032 /// .filter(|x| x % 2 == 0)
1033 /// .sum();
1034 ///
1035 /// // compute in parallel with default configuration
1036 /// let par_result = tree
1037 /// .clone()
1038 /// .into_par() // replace into_iter() with into_par()
1039 /// .filter_map(|x| x.parse::<usize>().ok())
1040 /// .filter(|x| x % 2 == 0)
1041 /// .sum();
1042 /// assert_eq!(seq_result, par_result);
1043 ///
1044 /// // configure parallel computation
1045 /// let par_result = tree
1046 /// .into_par()
1047 /// .num_threads(4)
1048 /// .chunk_size(64)
1049 /// .filter_map(|x| x.parse::<usize>().ok())
1050 /// .filter(|x| x % 2 == 0)
1051 /// .sum();
1052 /// assert_eq!(seq_result, par_result);
1053 /// ```
1054 #[cfg(feature = "parallel")]
1055 pub fn into_par(self) -> impl orx_parallel::ParIter<Item = V::Item>
1056 where
1057 V::Item: Send + Sync + Clone,
1058 <P as PinnedStorage>::PinnedVec<V>:
1059 orx_concurrent_iter::IntoConcurrentIter<Item = crate::aliases::N<V>>,
1060 {
1061 use orx_parallel::*;
1062 let (pinned, _, _) = self.0.into_inner().0.into_inner();
1063 pinned.into_par().filter_map(|x| x.into_data())
1064 }
1065
1066 // helpers
1067
1068 pub(crate) fn new_with_root(root_value: V::Item) -> Self
1069 where
1070 P::PinnedVec<V>: Default,
1071 {
1072 let mut col = Col::<V, M, P>::new();
1073 let root_ptr = col.push(root_value);
1074 let root_mut: &mut RefsSingle<V> = col.ends_mut();
1075 root_mut.set_some(root_ptr);
1076
1077 Self(col)
1078 }
1079
1080 /// Returns the pointer to the root; None if empty.
1081 fn root_ptr(&self) -> Option<NodePtr<V>> {
1082 self.0.ends().get()
1083 }
1084}
1085
1086/// ***O(1)*** Swaps the nodes together with their subtrees rooted at the given `first_idx` and `second_idx`.
1087///
1088/// The indices remain valid.
1089///
1090/// In order to have a valid swap operation, the two subtrees must be **independent** of each other without
1091/// any shared node. Necessary and sufficient condition is then as follows:
1092///
1093/// * node with the `first_idx` is not an ancestor of the node with the `second_idx`,
1094/// * and vice versa.
1095///
1096/// # Panics
1097///
1098/// * if either of the node indices is invalid, or
1099/// * if either of the indices belong to the root since this automatically invalidates the Safety condition.
1100///
1101/// # Safety
1102///
1103/// It is safe to use this method only when the swap operation is valid; i.e., abovementioned independence condition
1104/// of the subtrees holds.
1105pub(crate) fn swap_subtrees_unchecked<V, M, P>(
1106 col: &mut Col<V, M, P>,
1107 first_idx: NodeIdx<V>,
1108 second_idx: NodeIdx<V>,
1109) where
1110 V: TreeVariant,
1111 M: MemoryPolicy,
1112 P: PinnedStorage,
1113{
1114 let is_node_idx_valid = |node_idx: NodeIdx<V>| node_idx.0.is_valid_for(col);
1115 assert!(is_node_idx_valid(first_idx), "{}", INVALID_IDX_ERROR);
1116 assert!(is_node_idx_valid(second_idx), "{}", INVALID_IDX_ERROR);
1117
1118 let ptr_p = first_idx.0.node_ptr();
1119 let ptr_q = second_idx.0.node_ptr();
1120
1121 if ptr_p == ptr_q {
1122 return;
1123 }
1124
1125 let p = unsafe { &mut *ptr_p.ptr_mut() };
1126 let q = unsafe { &mut *ptr_q.ptr_mut() };
1127
1128 let parent_p = p.prev().get().expect("root cannot be swapped");
1129 let parent_q = q.prev().get().expect("root cannot be swapped");
1130
1131 let node_mut = |p: NodePtr<V>| unsafe { &mut *p.ptr_mut() };
1132 match parent_p == parent_q {
1133 true => {
1134 let common_parent = node_mut(parent_p);
1135 let indices = common_parent.next_mut().swap(ptr_p, ptr_q);
1136 debug_assert!(indices.is_some());
1137 }
1138 false => {
1139 node_mut(parent_p).next_mut().replace_with(ptr_p, ptr_q);
1140 q.prev_mut().set_some(parent_p);
1141
1142 node_mut(parent_q).next_mut().replace_with(ptr_q, ptr_p);
1143 p.prev_mut().set_some(parent_q);
1144 }
1145 }
1146}