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 .cloned()
219 .map(|p| Node::new(&self.0, p))
220 .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.")
221 }
222
223 /// Returns the mutable root node of the tree.
224 ///
225 /// # Panics
226 ///
227 /// Panics if the tree is empty and has no root.
228 ///
229 /// When not certain, you may use [`is_empty`] or [`get_root_mut`] methods to have a safe access.
230 ///
231 /// [`is_empty`]: Self::is_empty
232 /// [`get_root_mut`]: Self::get_root_mut
233 ///
234 /// # Examples
235 ///
236 /// ```
237 /// use orx_tree::*;
238 ///
239 /// // initiate a rooted tree
240 /// let mut tree = DynTree::<_>::new('a');
241 /// *tree.root_mut().data_mut() = 'x';
242 /// assert_eq!(tree.root().data(), &'x');
243 ///
244 /// tree.clear();
245 /// // *tree.root_mut().data_mut() = 'x'; // panics!
246 ///
247 /// // initiate an empty tree
248 /// let mut tree = BinaryTree::<_>::empty();
249 /// // *tree.root_mut().data_mut() = 'x'; // panics!
250 ///
251 /// tree.push_root('a');
252 ///
253 /// // build the tree from the root
254 /// let mut root = tree.root_mut();
255 /// assert_eq!(root.data(), &'a');
256 ///
257 /// let [b, c] = root.push_children(['b', 'c']);
258 /// tree.node_mut(&b).push_child('d');
259 /// tree.node_mut(&c).push_children(['e', 'f']);
260 /// ```
261 pub fn root_mut(&mut self) -> NodeMut<'_, V, M, P> {
262 self.root_ptr()
263 .cloned()
264 .map(|p| NodeMut::new(&mut self.0, p))
265 .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.")
266 }
267
268 /// Returns the root node of the tree; None if the tree is empty.
269 ///
270 /// # Examples
271 ///
272 /// ```
273 /// use orx_tree::*;
274 ///
275 /// // initiate a rooted tree
276 /// let mut tree = DynTree::<_>::new('a');
277 /// assert_eq!(tree.root().data(), &'a');
278 ///
279 /// tree.clear();
280 /// assert_eq!(tree.get_root(), None);
281 ///
282 /// // initiate an empty tree
283 /// let mut tree = BinaryTree::<_>::empty();
284 /// assert_eq!(tree.get_root(), None);
285 ///
286 /// tree.push_root('a');
287 /// assert_eq!(tree.root().data(), &'a');
288 /// ```
289 pub fn get_root(&self) -> Option<Node<'_, V, M, P>> {
290 self.root_ptr().cloned().map(|p| Node::new(&self.0, p))
291 }
292
293 /// Returns the root as a mutable node of the tree; None if the tree is empty.
294 ///
295 /// # Examples
296 ///
297 /// ```
298 /// use orx_tree::*;
299 ///
300 /// let mut tree = DynTree::<_>::new('a');
301 ///
302 /// let mut root = tree.root_mut();
303 ///
304 /// assert_eq!(root.data(), &'a');
305 /// *root.data_mut() = 'x';
306 /// assert_eq!(root.data(), &'x');
307 ///
308 /// root.push_child('b');
309 /// let idx = root.push_child('c');
310 ///
311 /// tree.clear();
312 /// assert_eq!(tree.get_root_mut(), None);
313 /// ```
314 pub fn get_root_mut(&mut self) -> Option<NodeMut<'_, V, M, P>> {
315 self.root_ptr()
316 .cloned()
317 .map(|p| NodeMut::new(&mut self.0, p))
318 }
319
320 // get nodes
321
322 /// Returns true if the `node_idx` is valid for this tree.
323 ///
324 /// Returns false if any of the following holds:
325 ///
326 /// * the node index is created from a different tree => [`NodeIdxError::OutOfBounds`]
327 /// * the node that this index is created for is removed from the tree => [`NodeIdxError::RemovedNode`]
328 /// * the tree is using `Auto` memory reclaim policy and nodes are reorganized due to node removals
329 /// => [`NodeIdxError::ReorganizedCollection`]
330 ///
331 /// Please see [`NodeIdx`] documentation for details on the validity of node indices.
332 ///
333 /// * If [`is_node_idx_valid`] is true, then [`node_idx_error`] is None;
334 /// * If [`is_node_idx_valid`] is false, then [`node_idx_error`] is Some.
335 ///
336 /// [`is_node_idx_valid`]: crate::Tree::is_node_idx_valid
337 /// [`node_idx_error`]: crate::Tree::node_idx_error
338 #[inline(always)]
339 pub fn is_node_idx_valid(&self, node_idx: &NodeIdx<V>) -> bool {
340 node_idx.0.is_valid_for(&self.0)
341 }
342
343 /// Returns the node index error if the `node_idx` is invalid.
344 /// Returns None if the index is valid for this tree.
345 ///
346 /// Returns Some if any of the following holds:
347 ///
348 /// * the node index is created from a different tree => [`NodeIdxError::OutOfBounds`]
349 /// * the node that this index is created for is removed from the tree => [`NodeIdxError::RemovedNode`]
350 /// * the tree is using `Auto` memory reclaim policy and nodes are reorganized due to node removals
351 /// => [`NodeIdxError::ReorganizedCollection`]
352 ///
353 /// * If [`is_node_idx_valid`] is true, then [`node_idx_error`] is None;
354 /// * If [`is_node_idx_valid`] is false, then [`node_idx_error`] is Some.
355 ///
356 /// [`is_node_idx_valid`]: crate::Tree::is_node_idx_valid
357 /// [`node_idx_error`]: crate::Tree::node_idx_error
358 pub fn node_idx_error(&self, node_idx: &NodeIdx<V>) -> Option<NodeIdxError> {
359 self.0.node_idx_error(&node_idx.0)
360 }
361
362 /// Returns the node with the given `node_idx`.
363 ///
364 /// # Panics
365 ///
366 /// Panics if this node index is not valid for the given `tree`; i.e., when either of the following holds:
367 ///
368 /// * the node index is created from a different tree => [`NodeIdxError::OutOfBounds`]
369 /// * the node that this index is created for is removed from the tree => [`NodeIdxError::RemovedNode`]
370 /// * the tree is using `Auto` memory reclaim policy and nodes are reorganized due to node removals
371 /// => [`NodeIdxError::ReorganizedCollection`]
372 ///
373 /// When not certain, you may use [`is_node_idx_valid`] or [`get_node`] methods to have a safe access.
374 ///
375 /// Please see [`NodeIdx`] documentation for details on the validity of node indices.
376 ///
377 /// [`is_node_idx_valid`]: crate::Tree::is_node_idx_valid
378 /// [`get_node`]: Self::get_node
379 ///
380 /// [`NodeIdxError::OutOfBounds`]: crate::NodeIdxError::OutOfBounds
381 /// [`NodeIdxError::RemovedNode`]: crate::NodeIdxError::RemovedNode
382 /// [`NodeIdxError::ReorganizedCollection`]: crate::NodeIdxError::ReorganizedCollection
383 ///
384 /// # Examples
385 ///
386 /// ```
387 /// use orx_tree::*;
388 ///
389 /// // 1
390 /// // ╱ ╲
391 /// // ╱ ╲
392 /// // 2 3
393 /// // ╱ ╲
394 /// // 4 5
395 ///
396 /// let mut tree = DynTree::new(1);
397 ///
398 /// let mut root = tree.root_mut();
399 /// let [id2, id3] = root.push_children([2, 3]);
400 ///
401 /// let n2 = tree.node(&id2);
402 /// assert_eq!(n2.data(), &2);
403 ///
404 /// let mut n3 = tree.node_mut(&id3);
405 /// n3.push_children([4, 5]);
406 ///
407 /// let bfs_values: Vec<_> = tree.root().walk::<Bfs>().copied().collect();
408 /// assert_eq!(bfs_values, [1, 2, 3, 4, 5]);
409 /// ```
410 #[inline(always)]
411 pub fn node(&self, node_idx: &NodeIdx<V>) -> Node<'_, V, M, P> {
412 assert!(self.is_node_idx_valid(node_idx), "{}", INVALID_IDX_ERROR);
413 Node::new(&self.0, node_idx.0.node_ptr())
414 }
415
416 /// Returns the mutable node with the given `node_idx`.
417 ///
418 /// # Panics
419 ///
420 /// Panics if this node index is not valid for the given `tree`; i.e., when either of the following holds:
421 ///
422 /// * the node index is created from a different tree => [`NodeIdxError::OutOfBounds`]
423 /// * the node that this index is created for is removed from the tree => [`NodeIdxError::RemovedNode`]
424 /// * the tree is using `Auto` memory reclaim policy and nodes are reorganized due to node removals
425 /// => [`NodeIdxError::ReorganizedCollection`]
426 ///
427 /// When not certain, you may use [`is_node_idx_valid`] or [`get_node_mut`] methods to have a safe access.
428 ///
429 /// Please see [`NodeIdx`] documentation for details on the validity of node indices.
430 ///
431 /// [`is_node_idx_valid`]: crate::Tree::is_node_idx_valid
432 /// [`get_node_mut`]: Self::get_node_mut
433 ///
434 /// [`NodeIdxError::OutOfBounds`]: crate::NodeIdxError::OutOfBounds
435 /// [`NodeIdxError::RemovedNode`]: crate::NodeIdxError::RemovedNode
436 /// [`NodeIdxError::ReorganizedCollection`]: crate::NodeIdxError::ReorganizedCollection
437 ///
438 /// # Examples
439 ///
440 /// ```
441 /// use orx_tree::*;
442 ///
443 /// // 1
444 /// // ╱ ╲
445 /// // ╱ ╲
446 /// // 2 3
447 /// // ╱ ╲
448 /// // 4 5
449 ///
450 /// let mut tree = DynTree::new(1);
451 ///
452 /// let mut root = tree.root_mut();
453 /// let [id2, id3] = root.push_children([2, 3]);
454 ///
455 /// let n2 = tree.node(&id2);
456 /// assert_eq!(n2.data(), &2);
457 ///
458 /// let mut n3 = tree.node_mut(&id3);
459 /// n3.push_children([4, 5]);
460 ///
461 /// let bfs_values: Vec<_> = tree.root().walk::<Bfs>().copied().collect();
462 /// assert_eq!(bfs_values, [1, 2, 3, 4, 5]);
463 /// ```
464 #[inline(always)]
465 pub fn node_mut(&mut self, node_idx: &NodeIdx<V>) -> NodeMut<'_, V, M, P> {
466 assert!(self.is_node_idx_valid(node_idx), "{}", INVALID_IDX_ERROR);
467 NodeMut::new(&mut self.0, node_idx.0.node_ptr())
468 }
469
470 /// Returns the node with the given `node_idx`; returns None if the node index is invalid.
471 ///
472 /// The node index is invalid if any of the following holds:
473 ///
474 /// * the node index is created from a different tree => [`NodeIdxError::OutOfBounds`]
475 /// * the node that this index is created for is removed from the tree => [`NodeIdxError::RemovedNode`]
476 /// * the tree is using `Auto` memory reclaim policy and nodes are reorganized due to node removals
477 /// => [`NodeIdxError::ReorganizedCollection`]
478 ///
479 /// You may use [`try_node`] method to get the underlying reason when the index is invalid.
480 ///
481 /// Please see [`NodeIdx`] documentation for details on the validity of node indices.
482 ///
483 /// [`try_node`]: Self::try_node
484 /// [`NodeIdxError::OutOfBounds`]: crate::NodeIdxError::OutOfBounds
485 /// [`NodeIdxError::RemovedNode`]: crate::NodeIdxError::RemovedNode
486 /// [`NodeIdxError::ReorganizedCollection`]: crate::NodeIdxError::ReorganizedCollection
487 #[inline(always)]
488 pub fn get_node(&self, node_idx: &NodeIdx<V>) -> Option<Node<'_, V, M, P>> {
489 self.is_node_idx_valid(node_idx)
490 .then(|| Node::new(&self.0, node_idx.0.node_ptr()))
491 }
492
493 /// Returns the mutable node with the given `node_idx`; returns None if the node index is invalid.
494 ///
495 /// The node index is invalid if any of the following holds:
496 ///
497 /// * the node index is created from a different tree => [`NodeIdxError::OutOfBounds`]
498 /// * the node that this index is created for is removed from the tree => [`NodeIdxError::RemovedNode`]
499 /// * the tree is using `Auto` memory reclaim policy and nodes are reorganized due to node removals
500 /// => [`NodeIdxError::ReorganizedCollection`]
501 ///
502 /// You may use [`try_node_mut`] method to get the underlying reason when the index is invalid.
503 ///
504 /// Please see [`NodeIdx`] documentation for details on the validity of node indices.
505 ///
506 /// [`try_node_mut`]: Self::try_node_mut
507 /// [`NodeIdxError::OutOfBounds`]: crate::NodeIdxError::OutOfBounds
508 /// [`NodeIdxError::RemovedNode`]: crate::NodeIdxError::RemovedNode
509 /// [`NodeIdxError::ReorganizedCollection`]: crate::NodeIdxError::ReorganizedCollection
510 #[inline(always)]
511 pub fn get_node_mut(&mut self, node_idx: &NodeIdx<V>) -> Option<NodeMut<'_, V, M, P>> {
512 self.is_node_idx_valid(node_idx)
513 .then(|| NodeMut::new(&mut self.0, node_idx.0.node_ptr()))
514 }
515
516 /// Returns the node with the given `node_idx`; returns the corresponding error if the node index is invalid.
517 ///
518 /// The node index is invalid if any of the following holds:
519 ///
520 /// * the node index is created from a different tree => [`NodeIdxError::OutOfBounds`]
521 /// * the node that this index is created for is removed from the tree => [`NodeIdxError::RemovedNode`]
522 /// * the tree is using `Auto` memory reclaim policy and nodes are reorganized due to node removals
523 /// => [`NodeIdxError::ReorganizedCollection`]
524 ///
525 /// Please see [`NodeIdx`] documentation for details on the validity of node indices.
526 ///
527 /// [`try_node`]: Self::try_node
528 /// [`NodeIdxError::OutOfBounds`]: crate::NodeIdxError::OutOfBounds
529 /// [`NodeIdxError::RemovedNode`]: crate::NodeIdxError::RemovedNode
530 /// [`NodeIdxError::ReorganizedCollection`]: crate::NodeIdxError::ReorganizedCollection
531 #[inline(always)]
532 pub fn try_node(&self, node_idx: &NodeIdx<V>) -> Result<Node<'_, V, M, P>, NodeIdxError> {
533 self.0
534 .try_get_ptr(&node_idx.0)
535 .map(|ptr| Node::new(&self.0, ptr))
536 }
537
538 /// Returns the node with the given `node_idx`; returns the corresponding error if the node index is invalid.
539 ///
540 /// The node index is invalid if any of the following holds:
541 ///
542 /// * the node index is created from a different tree => [`NodeIdxError::OutOfBounds`]
543 /// * the node that this index is created for is removed from the tree => [`NodeIdxError::RemovedNode`]
544 /// * the tree is using `Auto` memory reclaim policy and nodes are reorganized due to node removals
545 /// => [`NodeIdxError::ReorganizedCollection`]
546 ///
547 /// Please see [`NodeIdx`] documentation for details on the validity of node indices.
548 ///
549 /// [`try_node`]: Self::try_node
550 /// [`NodeIdxError::OutOfBounds`]: crate::NodeIdxError::OutOfBounds
551 /// [`NodeIdxError::RemovedNode`]: crate::NodeIdxError::RemovedNode
552 /// [`NodeIdxError::ReorganizedCollection`]: crate::NodeIdxError::ReorganizedCollection
553 #[inline(always)]
554 pub fn try_node_mut(
555 &mut self,
556 node_idx: &NodeIdx<V>,
557 ) -> Result<NodeMut<'_, V, M, P>, NodeIdxError> {
558 self.0
559 .try_get_ptr(&node_idx.0)
560 .map(|ptr| NodeMut::new(&mut self.0, ptr))
561 }
562
563 /// Returns the node with the given `node_idx`.
564 ///
565 /// # Safety
566 ///
567 /// It omits the index validity assertions that [`node`] method performs; hence it is only safe to use
568 /// this method when we are certain that '`is_node_idx_valid`' would have returned true.
569 ///
570 /// [`node`]: Self::node
571 /// [`is_node_idx_valid`]: Self::is_node_idx_valid
572 #[inline(always)]
573 pub unsafe fn node_unchecked(&self, node_idx: &NodeIdx<V>) -> Node<'_, V, M, P> {
574 Node::new(&self.0, node_idx.0.node_ptr())
575 }
576
577 /// Returns the mutable node with the given `node_idx`.
578 ///
579 /// # Safety
580 ///
581 /// It omits the index validity assertions that [`node_mut`] method performs; hence it is only safe to use
582 /// this method when we are certain that '`is_node_idx_valid`' would have returned true.
583 ///
584 /// [`node_mut`]: Self::node_mut
585 /// [`is_node_idx_valid`]: Self::is_node_idx_valid
586 #[inline(always)]
587 pub unsafe fn node_mut_unchecked(&mut self, node_idx: &NodeIdx<V>) -> NodeMut<'_, V, M, P> {
588 NodeMut::new(&mut self.0, node_idx.0.node_ptr())
589 }
590
591 // move nodes
592
593 /// ***O(1)*** Tries to swap the nodes together with their subtrees rooted at the given `first_idx` and `second_idx`
594 /// in constant time (*).
595 ///
596 /// The indices remain valid.
597 ///
598 /// In order to have a valid swap operation, the two subtrees must be **independent** of each other without
599 /// any shared node. Necessary and sufficient condition is then as follows:
600 ///
601 /// * node with the `first_idx` is not an ancestor of the node with the `second_idx`,
602 /// * and vice versa.
603 ///
604 /// Swap operation will succeed if both indices are valid and the above condition holds. Panics ...
605 ///
606 /// # Panics
607 ///
608 /// * Panics if either of the node indices is invalid.
609 /// * Panics if node with the `first_idx` is an ancestor of the node with the `second_idx`; or vice versa.
610 ///
611 /// # See also
612 ///
613 /// (*) Validation of the independence of the subtrees is performed in ***O(D)*** time where D is the maximum
614 /// depth of the tree. When we are certain that the subtrees do not intersect, we can use the unsafe variant
615 /// [`swap_subtrees_unchecked`] to bypass the validation.
616 ///
617 /// See also:
618 ///
619 /// * [`swap_data_with`]
620 /// * [`swap_subtrees`]
621 /// * [`try_swap_nodes`]
622 /// * [`swap_subtrees_unchecked`]
623 ///
624 /// [`swap_data_with`]: crate::NodeMut::swap_data_with
625 /// [`swap_subtrees`]: crate::Tree::swap_subtrees
626 /// [`try_swap_nodes`]: crate::Tree::try_swap_nodes
627 /// [`swap_subtrees_unchecked`]: crate::Tree::swap_subtrees_unchecked
628 ///
629 /// # Examples
630 ///
631 /// ```
632 /// use orx_tree::*;
633 ///
634 /// // 1
635 /// // ╱ ╲
636 /// // ╱ ╲
637 /// // 2 3
638 /// // ╱ ╲ ╱ ╲
639 /// // 4 5 6 7
640 /// // | | ╱ ╲
641 /// // 8 9 10 11
642 ///
643 /// let mut tree = DynTree::new(1);
644 ///
645 /// let mut root = tree.root_mut();
646 /// let [id2, id3] = root.push_children([2, 3]);
647 ///
648 /// let mut n2 = tree.node_mut(&id2);
649 /// let [id4, _] = n2.push_children([4, 5]);
650 ///
651 /// tree.node_mut(&id4).push_child(8);
652 ///
653 /// let mut n3 = tree.node_mut(&id3);
654 /// let [id6, id7] = n3.push_children([6, 7]);
655 ///
656 /// tree.node_mut(&id6).push_child(9);
657 /// let [_, _] = tree.node_mut(&id7).push_children([10, 11]);
658 ///
659 /// // we can swap n2 & n7
660 /// // 1
661 /// // ╱ ╲
662 /// // ╱ ╲
663 /// // 7 3
664 /// // ╱ ╲ ╱ ╲
665 /// // 10 11 6 2
666 /// // | ╱ ╲
667 /// // 9 4 5
668 /// // |
669 /// // 8
670 ///
671 /// tree.swap_subtrees(&id2, &id7);
672 ///
673 /// let bfs: Vec<_> = tree.root().walk::<Bfs>().copied().collect();
674 /// assert_eq!(bfs, [1, 7, 3, 10, 11, 6, 2, 9, 4, 5, 8]);
675 /// ```
676 pub fn swap_subtrees(&mut self, first_idx: &NodeIdx<V>, second_idx: &NodeIdx<V>) {
677 assert!(self.is_node_idx_valid(first_idx), "{}", INVALID_IDX_ERROR);
678 assert!(self.is_node_idx_valid(second_idx), "{}", INVALID_IDX_ERROR);
679 let ptr_root = self.root_ptr().expect("tree is not empty");
680 let ptr_p = first_idx.0.node_ptr();
681 let ptr_q = second_idx.0.node_ptr();
682
683 match ptr_p == ptr_q {
684 true => {}
685 false => {
686 assert!(
687 AncestorsIterPtr::new(ptr_root.clone(), ptr_p.clone()).all(|x| x != ptr_q),
688 "Node with `second_idx` is an ancestor of the node with `first_idx`; cannot swap nodes."
689 );
690 assert!(
691 AncestorsIterPtr::new(ptr_root.clone(), ptr_q.clone()).all(|x| x != ptr_p),
692 "Node with `first_idx` is an ancestor of the node with `second_idx`; cannot swap nodes."
693 );
694 // # SAFETY: all possible error cases are checked and handled
695 unsafe { self.swap_subtrees_unchecked(first_idx, second_idx) };
696 }
697 }
698 }
699
700 /// ***O(1)*** Tries to swap the nodes together with their subtrees rooted at the given `first_idx` and `second_idx`
701 /// in constant time (*).
702 /// Returns the error if the swap operation is invalid.
703 ///
704 /// The indices remain valid.
705 ///
706 /// In order to have a valid swap operation, the two subtrees must be **independent** of each other without
707 /// any shared node. Necessary and sufficient condition is then as follows:
708 ///
709 /// * node with the `first_idx` is not an ancestor of the node with the `second_idx`,
710 /// * and vice versa.
711 ///
712 /// Swap operation will succeed and return Ok if both indices are valid and the above condition holds.
713 /// It will the corresponding [`NodeSwapError`] otherwise.
714 ///
715 /// # See also
716 ///
717 /// (*) Validation of the independence of the subtrees is performed in ***O(D)*** time where D is the maximum
718 /// depth of the tree. When we are certain that the subtrees do not intersect, we can use the unsafe variant
719 /// [`swap_subtrees_unchecked`] to bypass the validation.
720 ///
721 /// See also:
722 ///
723 /// * [`swap_data_with`]
724 /// * [`swap_subtrees`]
725 /// * [`try_swap_nodes`]
726 /// * [`swap_subtrees_unchecked`]
727 ///
728 /// [`swap_data_with`]: crate::NodeMut::swap_data_with
729 /// [`swap_subtrees`]: crate::Tree::swap_subtrees
730 /// [`try_swap_nodes`]: crate::Tree::try_swap_nodes
731 /// [`swap_subtrees_unchecked`]: crate::Tree::swap_subtrees_unchecked
732 ///
733 /// # Examples
734 ///
735 /// ```
736 /// use orx_tree::*;
737 ///
738 /// // 1
739 /// // ╱ ╲
740 /// // ╱ ╲
741 /// // 2 3
742 /// // ╱ ╲ ╱ ╲
743 /// // 4 5 6 7
744 /// // | | ╱ ╲
745 /// // 8 9 10 11
746 ///
747 /// let mut tree = DynTree::new(1);
748 ///
749 /// let mut root = tree.root_mut();
750 /// let id1 = root.idx();
751 /// let [id2, id3] = root.push_children([2, 3]);
752 ///
753 /// let mut n2 = tree.node_mut(&id2);
754 /// let [id4, _] = n2.push_children([4, 5]);
755 ///
756 /// tree.node_mut(&id4).push_child(8);
757 ///
758 /// let mut n3 = tree.node_mut(&id3);
759 /// let [id6, id7] = n3.push_children([6, 7]);
760 ///
761 /// tree.node_mut(&id6).push_child(9);
762 /// let [id10, _] = tree.node_mut(&id7).push_children([10, 11]);
763 ///
764 /// // cannot swap n3 & n10
765 ///
766 /// assert_eq!(
767 /// tree.try_swap_nodes(&id3, &id10),
768 /// Err(NodeSwapError::FirstNodeIsAncestorOfSecond)
769 /// );
770 ///
771 /// // cannot swap n4 & n1 (root)
772 ///
773 /// assert_eq!(
774 /// tree.try_swap_nodes(&id4, &id1),
775 /// Err(NodeSwapError::SecondNodeIsAncestorOfFirst)
776 /// );
777 ///
778 /// // we can swap n2 & n7
779 /// // 1
780 /// // ╱ ╲
781 /// // ╱ ╲
782 /// // 7 3
783 /// // ╱ ╲ ╱ ╲
784 /// // 10 11 6 2
785 /// // | ╱ ╲
786 /// // 9 4 5
787 /// // |
788 /// // 8
789 ///
790 /// let result = tree.try_swap_nodes(&id2, &id7);
791 /// assert_eq!(result, Ok(()));
792 ///
793 /// let bfs: Vec<_> = tree.root().walk::<Bfs>().copied().collect();
794 /// assert_eq!(bfs, [1, 7, 3, 10, 11, 6, 2, 9, 4, 5, 8]);
795 /// ```
796 pub fn try_swap_nodes(
797 &mut self,
798 first_idx: &NodeIdx<V>,
799 second_idx: &NodeIdx<V>,
800 ) -> Result<(), NodeSwapError> {
801 let ptr_root = match self.root_ptr() {
802 Some(x) => x,
803 None => return Err(NodeSwapError::NodeIdxError(NodeIdxError::RemovedNode)),
804 };
805 let ptr_p = self.0.try_get_ptr(&first_idx.0)?;
806 let ptr_q = self.0.try_get_ptr(&second_idx.0)?;
807
808 if ptr_p == ptr_q {
809 Ok(())
810 } else if AncestorsIterPtr::new(ptr_root.clone(), ptr_p.clone()).any(|x| x == ptr_q) {
811 Err(NodeSwapError::SecondNodeIsAncestorOfFirst)
812 } else if AncestorsIterPtr::new(ptr_root.clone(), ptr_q.clone()).any(|x| x == ptr_p) {
813 Err(NodeSwapError::FirstNodeIsAncestorOfSecond)
814 } else {
815 // # SAFETY: all possible error cases are checked and handled
816 unsafe { self.swap_subtrees_unchecked(first_idx, second_idx) };
817 Ok(())
818 }
819 }
820
821 /// ***O(1)*** Swaps the nodes together with their subtrees rooted at the given `first_idx` and `second_idx`.
822 ///
823 /// The indices remain valid.
824 ///
825 /// In order to have a valid swap operation, the two subtrees must be **independent** of each other without
826 /// any shared node. Necessary and sufficient condition is then as follows:
827 ///
828 /// * node with the `first_idx` is not an ancestor of the node with the `second_idx`,
829 /// * and vice versa.
830 ///
831 /// # Panics
832 ///
833 /// Panics if either of the node indices is invalid.
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 assert!(self.is_node_idx_valid(first_idx), "{}", INVALID_IDX_ERROR);
905 assert!(self.is_node_idx_valid(second_idx), "{}", INVALID_IDX_ERROR);
906
907 let ptr_p = first_idx.0.node_ptr();
908 let ptr_q = second_idx.0.node_ptr();
909
910 if ptr_p == ptr_q {
911 return;
912 }
913
914 let p = unsafe { &mut *ptr_p.ptr_mut() };
915 let q = unsafe { &mut *ptr_q.ptr_mut() };
916
917 let parent_p = p.prev().get().cloned();
918 let parent_q = q.prev().get().cloned();
919
920 match parent_p {
921 Some(parent_ptr_p) => {
922 let parent_p = unsafe { &mut *parent_ptr_p.ptr_mut() };
923 parent_p.next_mut().replace_with(&ptr_p, ptr_q.clone());
924
925 q.prev_mut().set_some(parent_ptr_p);
926 }
927 None => {
928 q.prev_mut().set_none();
929 }
930 }
931
932 match parent_q {
933 Some(parent_ptr_q) => {
934 let parent_q = unsafe { &mut *parent_ptr_q.ptr_mut() };
935 parent_q.next_mut().replace_with(&ptr_q, ptr_p);
936
937 p.prev_mut().set_some(parent_ptr_q);
938 }
939 None => {
940 p.prev_mut().set_none();
941 }
942 }
943
944 if p.prev().get().is_none() {
945 self.0.ends_mut().set_some(first_idx.0.node_ptr());
946 } else if q.prev().get().is_none() {
947 self.0.ends_mut().set_some(second_idx.0.node_ptr());
948 }
949 }
950
951 // parallelization
952
953 /// Creates a parallel iterator over references to the elements of the tree in **arbitrary order**.
954 ///
955 /// Note that `par` is parallel counterpart of `iter`.
956 ///
957 /// In order to iterate over data in a particular order, please use traversers with [`walk`], [`walk_mut`]
958 /// or [`into_walk`] methods.
959 ///
960 /// Please see [`ParIter`] for details of the parallel computation.
961 /// In brief, computation is defined as chain of iterator transformations and parallelization
962 /// is handled by the underlying parallel executor.
963 ///
964 /// Requires **orx-parallel** feature.
965 ///
966 /// [`ParIter`]: orx_parallel::ParIter
967 /// [`walk`]: crate::NodeRef::walk
968 /// [`walk_mut`]: crate::NodeMut::walk_mut
969 /// [`into_walk`]: crate::NodeMut::into_walk
970 ///
971 /// # Examples
972 ///
973 /// ```
974 /// use orx_tree::*;
975 ///
976 /// let num_children = 4;
977 /// let total_depth = 10;
978 ///
979 /// let mut tree = DynTree::new(0.to_string());
980 /// let mut dfs = Traversal.dfs().over_nodes();
981 ///
982 /// for _ in 0..total_depth {
983 /// let root = tree.root();
984 /// let leaves: Vec<_> = root.leaves_with(&mut dfs).map(|x| x.idx()).collect();
985 /// for idx in leaves {
986 /// let count = tree.len();
987 /// let mut node = tree.node_mut(&idx);
988 /// for j in 0..num_children {
989 /// node.push_child((count + j).to_string());
990 /// }
991 /// }
992 /// }
993 ///
994 /// let seq_result: usize = tree
995 /// .iter()
996 /// .filter_map(|x| x.parse::<usize>().ok())
997 /// .filter(|x| x % 2 == 0)
998 /// .sum();
999 ///
1000 /// // compute in parallel with default configuration
1001 /// let par_result = tree
1002 /// .par() // replace iter() with par()
1003 /// .filter_map(|x| x.parse::<usize>().ok())
1004 /// .filter(|x| x % 2 == 0)
1005 /// .sum();
1006 /// assert_eq!(seq_result, par_result);
1007 ///
1008 /// // configure parallel computation
1009 /// let par_result = tree
1010 /// .par()
1011 /// .num_threads(4)
1012 /// .chunk_size(64)
1013 /// .filter_map(|x| x.parse::<usize>().ok())
1014 /// .filter(|x| x % 2 == 0)
1015 /// .sum();
1016 /// assert_eq!(seq_result, par_result);
1017 /// ```
1018 #[cfg(feature = "orx-parallel")]
1019 pub fn par(&self) -> impl orx_parallel::ParIter<Item = &V::Item>
1020 where
1021 V::Item: Send + Sync,
1022 for<'a> &'a <P as PinnedStorage>::PinnedVec<V>:
1023 orx_concurrent_iter::IntoConcurrentIter<Item = &'a crate::aliases::N<V>>,
1024 {
1025 use orx_parallel::*;
1026
1027 let pinned = self.0.nodes();
1028 pinned.par().filter_map(|x| x.data())
1029 }
1030
1031 /// Consumes the tree and creates a parallel iterator over owned elements of the tree in **arbitrary order**.
1032 ///
1033 /// Note that `into_par` is parallel counterpart of `into_iter`.
1034 ///
1035 /// In order to iterate over data in a particular order, please use traversers with [`walk`], [`walk_mut`]
1036 /// or [`into_walk`] methods.
1037 ///
1038 /// Please see [`ParIter`] for details of the parallel computation.
1039 /// In brief, computation is defined as chain of iterator transformations and parallelization
1040 /// is handled by the underlying parallel executor.
1041 ///
1042 /// Requires **orx-parallel** feature.
1043 ///
1044 /// [`ParIter`]: orx_parallel::ParIter
1045 /// [`walk`]: crate::NodeRef::walk
1046 /// [`walk_mut`]: crate::NodeMut::walk_mut
1047 /// [`into_walk`]: crate::NodeMut::into_walk
1048 ///
1049 /// # Examples
1050 ///
1051 /// ```
1052 /// use orx_tree::*;
1053 ///
1054 /// let num_children = 4;
1055 /// let total_depth = 10;
1056 ///
1057 /// let mut tree = DynTree::new(0.to_string());
1058 /// let mut dfs = Traversal.dfs().over_nodes();
1059 ///
1060 /// for _ in 0..total_depth {
1061 /// let root = tree.root();
1062 /// let leaves: Vec<_> = root.leaves_with(&mut dfs).map(|x| x.idx()).collect();
1063 /// for idx in leaves {
1064 /// let count = tree.len();
1065 /// let mut node = tree.node_mut(&idx);
1066 /// for j in 0..num_children {
1067 /// node.push_child((count + j).to_string());
1068 /// }
1069 /// }
1070 /// }
1071 ///
1072 /// let seq_result: usize = tree
1073 /// .clone()
1074 /// .into_iter()
1075 /// .filter_map(|x| x.parse::<usize>().ok())
1076 /// .filter(|x| x % 2 == 0)
1077 /// .sum();
1078 ///
1079 /// // compute in parallel with default configuration
1080 /// let par_result = tree
1081 /// .clone()
1082 /// .into_par() // replace into_iter() with into_par()
1083 /// .filter_map(|x| x.parse::<usize>().ok())
1084 /// .filter(|x| x % 2 == 0)
1085 /// .sum();
1086 /// assert_eq!(seq_result, par_result);
1087 ///
1088 /// // configure parallel computation
1089 /// let par_result = tree
1090 /// .into_par()
1091 /// .num_threads(4)
1092 /// .chunk_size(64)
1093 /// .filter_map(|x| x.parse::<usize>().ok())
1094 /// .filter(|x| x % 2 == 0)
1095 /// .sum();
1096 /// assert_eq!(seq_result, par_result);
1097 /// ```
1098 #[cfg(feature = "orx-parallel")]
1099 pub fn into_par(self) -> impl orx_parallel::ParIter<Item = V::Item>
1100 where
1101 V::Item: Send + Sync + Clone,
1102 <P as PinnedStorage>::PinnedVec<V>:
1103 orx_concurrent_iter::IntoConcurrentIter<Item = crate::aliases::N<V>>,
1104 {
1105 use orx_parallel::*;
1106 let (pinned, _, _) = self.0.into_inner().0.into_inner();
1107 pinned.into_par().filter_map(|x| x.into_data())
1108 }
1109
1110 // helpers
1111
1112 pub(crate) fn new_with_root(root_value: V::Item) -> Self
1113 where
1114 P::PinnedVec<V>: Default,
1115 {
1116 let mut col = Col::<V, M, P>::new();
1117 let root_ptr = col.push(root_value);
1118 let root_mut: &mut RefsSingle<V> = col.ends_mut();
1119 root_mut.set_some(root_ptr);
1120
1121 Self(col)
1122 }
1123
1124 /// Returns the pointer to the root; None if empty.
1125 fn root_ptr(&self) -> Option<&NodePtr<V>> {
1126 self.0.ends().get()
1127 }
1128}