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(&self) -> Node<'_, 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(&mut self) -> NodeMut<'_, 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(&self) -> Option<Node<'_, 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(&mut self) -> Option<NodeMut<'_, 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(&self, node_idx: NodeIdx<V>) -> Node<'_, 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(&mut self, node_idx: NodeIdx<V>) -> NodeMut<'_, 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(&self, node_idx: NodeIdx<V>) -> Option<Node<'_, 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(&mut self, node_idx: NodeIdx<V>) -> Option<NodeMut<'_, 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(&self, node_idx: NodeIdx<V>) -> Result<Node<'_, 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(
551 &mut self,
552 node_idx: NodeIdx<V>,
553 ) -> Result<NodeMut<'_, 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(&self, node_idx: NodeIdx<V>) -> Node<'_, 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(&mut self, node_idx: NodeIdx<V>) -> NodeMut<'_, V, M, P> {
584 NodeMut::new(&mut self.0, node_idx.0.node_ptr())
585 }
586
587 // move nodes
588
589 /// ***O(1)*** Tries to swap the nodes together with their subtrees rooted at the given `first_idx` and `second_idx`
590 /// in constant time (*).
591 ///
592 /// The indices remain valid.
593 ///
594 /// In order to have a valid swap operation, the two subtrees must be **independent** of each other without
595 /// any shared node. Necessary and sufficient condition is then as follows:
596 ///
597 /// * node with the `first_idx` is not an ancestor of the node with the `second_idx`,
598 /// * and vice versa.
599 ///
600 /// Swap operation will succeed if both indices are valid and the above condition holds. Panics ...
601 ///
602 /// # Panics
603 ///
604 /// * Panics if either of the node indices is invalid.
605 /// * Panics if node with the `first_idx` is an ancestor of the node with the `second_idx`; or vice versa.
606 ///
607 /// # See also
608 ///
609 /// (*) Validation of the independence of the subtrees is performed in ***O(D)*** time where D is the maximum
610 /// depth of the tree. When we are certain that the subtrees do not intersect, we can use the unsafe variant
611 /// [`swap_subtrees_unchecked`] to bypass the validation.
612 ///
613 /// See also:
614 ///
615 /// * [`swap_data_with`]
616 /// * [`swap_subtrees`]
617 /// * [`try_swap_nodes`]
618 /// * [`swap_subtrees_unchecked`]
619 ///
620 /// [`swap_data_with`]: crate::NodeMut::swap_data_with
621 /// [`swap_subtrees`]: crate::Tree::swap_subtrees
622 /// [`try_swap_nodes`]: crate::Tree::try_swap_nodes
623 /// [`swap_subtrees_unchecked`]: crate::Tree::swap_subtrees_unchecked
624 ///
625 /// # Examples
626 ///
627 /// ```
628 /// use orx_tree::*;
629 ///
630 /// // 1
631 /// // ╱ ╲
632 /// // ╱ ╲
633 /// // 2 3
634 /// // ╱ ╲ ╱ ╲
635 /// // 4 5 6 7
636 /// // | | ╱ ╲
637 /// // 8 9 10 11
638 ///
639 /// let mut tree = DynTree::new(1);
640 ///
641 /// let mut root = tree.root_mut();
642 /// let [id2, id3] = root.push_children([2, 3]);
643 ///
644 /// let mut n2 = tree.node_mut(id2);
645 /// let [id4, _] = n2.push_children([4, 5]);
646 ///
647 /// tree.node_mut(id4).push_child(8);
648 ///
649 /// let mut n3 = tree.node_mut(id3);
650 /// let [id6, id7] = n3.push_children([6, 7]);
651 ///
652 /// tree.node_mut(id6).push_child(9);
653 /// let [_, _] = tree.node_mut(id7).push_children([10, 11]);
654 ///
655 /// // we can swap n2 & n7
656 /// // 1
657 /// // ╱ ╲
658 /// // ╱ ╲
659 /// // 7 3
660 /// // ╱ ╲ ╱ ╲
661 /// // 10 11 6 2
662 /// // | ╱ ╲
663 /// // 9 4 5
664 /// // |
665 /// // 8
666 ///
667 /// tree.swap_subtrees(id2, id7);
668 ///
669 /// let bfs: Vec<_> = tree.root().walk::<Bfs>().copied().collect();
670 /// assert_eq!(bfs, [1, 7, 3, 10, 11, 6, 2, 9, 4, 5, 8]);
671 /// ```
672 pub fn swap_subtrees(&mut self, first_idx: NodeIdx<V>, second_idx: NodeIdx<V>) {
673 assert!(self.is_node_idx_valid(first_idx), "{}", INVALID_IDX_ERROR);
674 assert!(self.is_node_idx_valid(second_idx), "{}", INVALID_IDX_ERROR);
675 let ptr_root = self.root_ptr().expect("tree is not empty");
676 let ptr_p = first_idx.0.node_ptr();
677 let ptr_q = second_idx.0.node_ptr();
678
679 match ptr_p == ptr_q {
680 true => {}
681 false => {
682 assert!(
683 AncestorsIterPtr::new(ptr_root, ptr_p).all(|x| x != ptr_q),
684 "Node with `second_idx` is an ancestor of the node with `first_idx`; cannot swap nodes."
685 );
686 assert!(
687 AncestorsIterPtr::new(ptr_root, ptr_q).all(|x| x != ptr_p),
688 "Node with `first_idx` is an ancestor of the node with `second_idx`; cannot swap nodes."
689 );
690 // # SAFETY: all possible error cases are checked and handled
691 unsafe { self.swap_subtrees_unchecked(first_idx, second_idx) };
692 }
693 }
694 }
695
696 /// ***O(1)*** Tries to swap the nodes together with their subtrees rooted at the given `first_idx` and `second_idx`
697 /// in constant time (*).
698 /// Returns the error if the swap operation is invalid.
699 ///
700 /// The indices remain valid.
701 ///
702 /// In order to have a valid swap operation, the two subtrees must be **independent** of each other without
703 /// any shared node. Necessary and sufficient condition is then as follows:
704 ///
705 /// * node with the `first_idx` is not an ancestor of the node with the `second_idx`,
706 /// * and vice versa.
707 ///
708 /// Swap operation will succeed and return Ok if both indices are valid and the above condition holds.
709 /// It will the corresponding [`NodeSwapError`] otherwise.
710 ///
711 /// # See also
712 ///
713 /// (*) Validation of the independence of the subtrees is performed in ***O(D)*** time where D is the maximum
714 /// depth of the tree. When we are certain that the subtrees do not intersect, we can use the unsafe variant
715 /// [`swap_subtrees_unchecked`] to bypass the validation.
716 ///
717 /// See also:
718 ///
719 /// * [`swap_data_with`]
720 /// * [`swap_subtrees`]
721 /// * [`try_swap_nodes`]
722 /// * [`swap_subtrees_unchecked`]
723 ///
724 /// [`swap_data_with`]: crate::NodeMut::swap_data_with
725 /// [`swap_subtrees`]: crate::Tree::swap_subtrees
726 /// [`try_swap_nodes`]: crate::Tree::try_swap_nodes
727 /// [`swap_subtrees_unchecked`]: crate::Tree::swap_subtrees_unchecked
728 ///
729 /// # Examples
730 ///
731 /// ```
732 /// use orx_tree::*;
733 ///
734 /// // 1
735 /// // ╱ ╲
736 /// // ╱ ╲
737 /// // 2 3
738 /// // ╱ ╲ ╱ ╲
739 /// // 4 5 6 7
740 /// // | | ╱ ╲
741 /// // 8 9 10 11
742 ///
743 /// let mut tree = DynTree::new(1);
744 ///
745 /// let mut root = tree.root_mut();
746 /// let id1 = root.idx();
747 /// let [id2, id3] = root.push_children([2, 3]);
748 ///
749 /// let mut n2 = tree.node_mut(id2);
750 /// let [id4, _] = n2.push_children([4, 5]);
751 ///
752 /// tree.node_mut(id4).push_child(8);
753 ///
754 /// let mut n3 = tree.node_mut(id3);
755 /// let [id6, id7] = n3.push_children([6, 7]);
756 ///
757 /// tree.node_mut(id6).push_child(9);
758 /// let [id10, _] = tree.node_mut(id7).push_children([10, 11]);
759 ///
760 /// // cannot swap n3 & n10
761 ///
762 /// assert_eq!(
763 /// tree.try_swap_nodes(id3, id10),
764 /// Err(NodeSwapError::FirstNodeIsAncestorOfSecond)
765 /// );
766 ///
767 /// // cannot swap n4 & n1 (root)
768 ///
769 /// assert_eq!(
770 /// tree.try_swap_nodes(id4, id1),
771 /// Err(NodeSwapError::SecondNodeIsAncestorOfFirst)
772 /// );
773 ///
774 /// // we can swap n2 & n7
775 /// // 1
776 /// // ╱ ╲
777 /// // ╱ ╲
778 /// // 7 3
779 /// // ╱ ╲ ╱ ╲
780 /// // 10 11 6 2
781 /// // | ╱ ╲
782 /// // 9 4 5
783 /// // |
784 /// // 8
785 ///
786 /// let result = tree.try_swap_nodes(id2, id7);
787 /// assert_eq!(result, Ok(()));
788 ///
789 /// let bfs: Vec<_> = tree.root().walk::<Bfs>().copied().collect();
790 /// assert_eq!(bfs, [1, 7, 3, 10, 11, 6, 2, 9, 4, 5, 8]);
791 /// ```
792 pub fn try_swap_nodes(
793 &mut self,
794 first_idx: NodeIdx<V>,
795 second_idx: NodeIdx<V>,
796 ) -> Result<(), NodeSwapError> {
797 let ptr_root = match self.root_ptr() {
798 Some(x) => x,
799 None => return Err(NodeSwapError::NodeIdxError(NodeIdxError::RemovedNode)),
800 };
801 let ptr_p = self.0.try_get_ptr(first_idx.0)?;
802 let ptr_q = self.0.try_get_ptr(second_idx.0)?;
803
804 if ptr_p == ptr_q {
805 Ok(())
806 } else if AncestorsIterPtr::new(ptr_root, ptr_p).any(|x| x == ptr_q) {
807 Err(NodeSwapError::SecondNodeIsAncestorOfFirst)
808 } else if AncestorsIterPtr::new(ptr_root, ptr_q).any(|x| x == ptr_p) {
809 Err(NodeSwapError::FirstNodeIsAncestorOfSecond)
810 } else {
811 // # SAFETY: all possible error cases are checked and handled
812 unsafe { self.swap_subtrees_unchecked(first_idx, second_idx) };
813 Ok(())
814 }
815 }
816
817 /// ***O(1)*** Swaps the nodes together with their subtrees rooted at the given `first_idx` and `second_idx`.
818 ///
819 /// The indices remain valid.
820 ///
821 /// In order to have a valid swap operation, the two subtrees must be **independent** of each other without
822 /// any shared node. Necessary and sufficient condition is then as follows:
823 ///
824 /// * node with the `first_idx` is not an ancestor of the node with the `second_idx`,
825 /// * and vice versa.
826 ///
827 /// # Panics
828 ///
829 /// Panics if either of the node indices is invalid.
830 ///
831 /// # Safety
832 ///
833 /// It is safe to use this method only when the swap operation is valid; i.e., abovementioned independence condition
834 /// of the subtrees holds.
835 ///
836 /// # See also
837 ///
838 /// * [`swap_data_with`]
839 /// * [`swap_subtrees`]
840 /// * [`try_swap_nodes`]
841 /// * [`swap_subtrees_unchecked`]
842 ///
843 /// [`swap_data_with`]: crate::NodeMut::swap_data_with
844 /// [`swap_subtrees`]: crate::Tree::swap_subtrees
845 /// [`try_swap_nodes`]: crate::Tree::try_swap_nodes
846 /// [`swap_subtrees_unchecked`]: crate::Tree::swap_subtrees_unchecked
847 ///
848 /// # Examples
849 ///
850 /// ```
851 /// use orx_tree::*;
852 ///
853 /// // 1
854 /// // ╱ ╲
855 /// // ╱ ╲
856 /// // 2 3
857 /// // ╱ ╲ ╱ ╲
858 /// // 4 5 6 7
859 /// // | | ╱ ╲
860 /// // 8 9 10 11
861 ///
862 /// let mut tree = DynTree::new(1);
863 ///
864 /// let mut root = tree.root_mut();
865 /// let [id2, id3] = root.push_children([2, 3]);
866 ///
867 /// let mut n2 = tree.node_mut(id2);
868 /// let [id4, _] = n2.push_children([4, 5]);
869 ///
870 /// tree.node_mut(id4).push_child(8);
871 ///
872 /// let mut n3 = tree.node_mut(id3);
873 /// let [id6, id7] = n3.push_children([6, 7]);
874 ///
875 /// tree.node_mut(id6).push_child(9);
876 /// let [_, _] = tree.node_mut(id7).push_children([10, 11]);
877 ///
878 /// // we can swap n2 & n5
879 /// // 1
880 /// // ╱ ╲
881 /// // ╱ ╲
882 /// // 7 3
883 /// // ╱ ╲ ╱ ╲
884 /// // 10 11 6 2
885 /// // | ╱ ╲
886 /// // 9 4 5
887 /// // |
888 /// // 8
889 ///
890 /// unsafe { tree.swap_subtrees_unchecked(id2, id7) };
891 ///
892 /// let bfs: Vec<_> = tree.root().walk::<Bfs>().copied().collect();
893 /// assert_eq!(bfs, [1, 7, 3, 10, 11, 6, 2, 9, 4, 5, 8]);
894 /// ```
895 pub unsafe fn swap_subtrees_unchecked(
896 &mut self,
897 first_idx: NodeIdx<V>,
898 second_idx: NodeIdx<V>,
899 ) {
900 assert!(self.is_node_idx_valid(first_idx), "{}", INVALID_IDX_ERROR);
901 assert!(self.is_node_idx_valid(second_idx), "{}", INVALID_IDX_ERROR);
902
903 let ptr_p = first_idx.0.node_ptr();
904 let ptr_q = second_idx.0.node_ptr();
905
906 if ptr_p == ptr_q {
907 return;
908 }
909
910 let p = unsafe { &mut *ptr_p.ptr_mut() };
911 let q = unsafe { &mut *ptr_q.ptr_mut() };
912
913 let parent_p = p.prev().get();
914 let parent_q = q.prev().get();
915
916 match parent_p {
917 Some(parent_ptr_p) => {
918 let parent_p = unsafe { &mut *parent_ptr_p.ptr_mut() };
919 parent_p.next_mut().replace_with(ptr_p, ptr_q);
920
921 q.prev_mut().set_some(parent_ptr_p);
922 }
923 None => {
924 q.prev_mut().set_none();
925 }
926 }
927
928 match parent_q {
929 Some(parent_ptr_q) => {
930 let parent_q = unsafe { &mut *parent_ptr_q.ptr_mut() };
931 parent_q.next_mut().replace_with(ptr_q, ptr_p);
932
933 p.prev_mut().set_some(parent_ptr_q);
934 }
935 None => {
936 p.prev_mut().set_none();
937 }
938 }
939
940 if p.prev().get().is_none() {
941 self.0.ends_mut().set_some(first_idx.0.node_ptr());
942 } else if q.prev().get().is_none() {
943 self.0.ends_mut().set_some(second_idx.0.node_ptr());
944 }
945 }
946
947 // parallelization
948
949 /// Creates a parallel iterator over references to the elements of the tree in **arbitrary order**.
950 ///
951 /// Note that `par` is parallel counterpart of `iter`.
952 ///
953 /// In order to iterate over data in a particular order, please use traversers with [`walk`], [`walk_mut`]
954 /// or [`into_walk`] methods.
955 ///
956 /// Please see [`ParIter`] for details of the parallel computation.
957 /// In brief, computation is defined as chain of iterator transformations and parallelization
958 /// is handled by the underlying parallel executor.
959 ///
960 /// Requires **parallel** feature.
961 ///
962 /// [`ParIter`]: orx_parallel::ParIter
963 /// [`walk`]: crate::NodeRef::walk
964 /// [`walk_mut`]: crate::NodeMut::walk_mut
965 /// [`into_walk`]: crate::NodeMut::into_walk
966 ///
967 /// # Examples
968 ///
969 /// ```
970 /// use orx_tree::*;
971 ///
972 /// let num_children = 4;
973 /// let total_depth = 8;
974 ///
975 /// let mut tree = DynTree::new(0.to_string());
976 /// let mut dfs = Traversal.dfs().over_nodes();
977 ///
978 /// for _ in 0..total_depth {
979 /// let root = tree.root();
980 /// let leaves: Vec<_> = root.leaves_with(&mut dfs).map(|x| x.idx()).collect();
981 /// for idx in leaves {
982 /// let count = tree.len();
983 /// let mut node = tree.node_mut(idx);
984 /// for j in 0..num_children {
985 /// node.push_child((count + j).to_string());
986 /// }
987 /// }
988 /// }
989 ///
990 /// let seq_result: usize = tree
991 /// .iter()
992 /// .filter_map(|x| x.parse::<usize>().ok())
993 /// .filter(|x| x % 2 == 0)
994 /// .sum();
995 ///
996 /// // compute in parallel with default configuration
997 /// let par_result = tree
998 /// .par() // replace iter() with par()
999 /// .filter_map(|x| x.parse::<usize>().ok())
1000 /// .filter(|x| x % 2 == 0)
1001 /// .sum();
1002 /// assert_eq!(seq_result, par_result);
1003 ///
1004 /// // configure parallel computation
1005 /// let par_result = tree
1006 /// .par()
1007 /// .num_threads(4)
1008 /// .chunk_size(64)
1009 /// .filter_map(|x| x.parse::<usize>().ok())
1010 /// .filter(|x| x % 2 == 0)
1011 /// .sum();
1012 /// assert_eq!(seq_result, par_result);
1013 /// ```
1014 #[cfg(feature = "parallel")]
1015 pub fn par(&self) -> impl orx_parallel::ParIter<Item = &V::Item>
1016 where
1017 V::Item: Send + Sync,
1018 for<'a> &'a <P as PinnedStorage>::PinnedVec<V>:
1019 orx_concurrent_iter::IntoConcurrentIter<Item = &'a crate::aliases::N<V>>,
1020 {
1021 use orx_parallel::*;
1022
1023 let pinned = self.0.nodes();
1024 pinned.par().filter_map(|x| x.data())
1025 }
1026
1027 /// Consumes the tree and creates a parallel iterator over owned elements of the tree in **arbitrary order**.
1028 ///
1029 /// Note that `into_par` is parallel counterpart of `into_iter`.
1030 ///
1031 /// In order to iterate over data in a particular order, please use traversers with [`walk`], [`walk_mut`]
1032 /// or [`into_walk`] methods.
1033 ///
1034 /// Please see [`ParIter`] for details of the parallel computation.
1035 /// In brief, computation is defined as chain of iterator transformations and parallelization
1036 /// is handled by the underlying parallel executor.
1037 ///
1038 /// Requires **parallel** feature.
1039 ///
1040 /// [`ParIter`]: orx_parallel::ParIter
1041 /// [`walk`]: crate::NodeRef::walk
1042 /// [`walk_mut`]: crate::NodeMut::walk_mut
1043 /// [`into_walk`]: crate::NodeMut::into_walk
1044 ///
1045 /// # Examples
1046 ///
1047 /// ```
1048 /// use orx_tree::*;
1049 ///
1050 /// let num_children = 4;
1051 /// let total_depth = 8;
1052 ///
1053 /// let mut tree = DynTree::new(0.to_string());
1054 /// let mut dfs = Traversal.dfs().over_nodes();
1055 ///
1056 /// for _ in 0..total_depth {
1057 /// let root = tree.root();
1058 /// let leaves: Vec<_> = root.leaves_with(&mut dfs).map(|x| x.idx()).collect();
1059 /// for idx in leaves {
1060 /// let count = tree.len();
1061 /// let mut node = tree.node_mut(idx);
1062 /// for j in 0..num_children {
1063 /// node.push_child((count + j).to_string());
1064 /// }
1065 /// }
1066 /// }
1067 ///
1068 /// let seq_result: usize = tree
1069 /// .clone()
1070 /// .into_iter()
1071 /// .filter_map(|x| x.parse::<usize>().ok())
1072 /// .filter(|x| x % 2 == 0)
1073 /// .sum();
1074 ///
1075 /// // compute in parallel with default configuration
1076 /// let par_result = tree
1077 /// .clone()
1078 /// .into_par() // replace into_iter() with into_par()
1079 /// .filter_map(|x| x.parse::<usize>().ok())
1080 /// .filter(|x| x % 2 == 0)
1081 /// .sum();
1082 /// assert_eq!(seq_result, par_result);
1083 ///
1084 /// // configure parallel computation
1085 /// let par_result = tree
1086 /// .into_par()
1087 /// .num_threads(4)
1088 /// .chunk_size(64)
1089 /// .filter_map(|x| x.parse::<usize>().ok())
1090 /// .filter(|x| x % 2 == 0)
1091 /// .sum();
1092 /// assert_eq!(seq_result, par_result);
1093 /// ```
1094 #[cfg(feature = "parallel")]
1095 pub fn into_par(self) -> impl orx_parallel::ParIter<Item = V::Item>
1096 where
1097 V::Item: Send + Sync + Clone,
1098 <P as PinnedStorage>::PinnedVec<V>:
1099 orx_concurrent_iter::IntoConcurrentIter<Item = crate::aliases::N<V>>,
1100 {
1101 use orx_parallel::*;
1102 let (pinned, _, _) = self.0.into_inner().0.into_inner();
1103 pinned.into_par().filter_map(|x| x.into_data())
1104 }
1105
1106 // helpers
1107
1108 pub(crate) fn new_with_root(root_value: V::Item) -> Self
1109 where
1110 P::PinnedVec<V>: Default,
1111 {
1112 let mut col = Col::<V, M, P>::new();
1113 let root_ptr = col.push(root_value);
1114 let root_mut: &mut RefsSingle<V> = col.ends_mut();
1115 root_mut.set_some(root_ptr);
1116
1117 Self(col)
1118 }
1119
1120 /// Returns the pointer to the root; None if empty.
1121 fn root_ptr(&self) -> Option<NodePtr<V>> {
1122 self.0.ends().get()
1123 }
1124}