Struct NodeMut

pub struct NodeMut<'a, V, M = Auto, P = SplitRecursive, O = NodeMutUpAndDown>
where
    V: TreeVariant,
    M: MemoryPolicy,
    P: PinnedStorage,
    O: NodeMutOrientation,
{ /* private fields */ }

A node of the tree, which in turn is a tree.

Implementations

impl<'a, V, M, P, MO> NodeMut<'a, V, M, P, MO>

where V: TreeVariant, M: MemoryPolicy, P: PinnedStorage, MO: NodeMutOrientation,

pub fn data_mut(&mut self) -> &mut V::Item

Returns a mutable reference to data of this node.

Examples

use orx_tree::*;

let mut tree = DynTree::new(0);

let mut root = tree.root_mut();

*root.data_mut() = 10;
assert_eq!(root.data(), &10);

let [idx_a] = root.push_children([1]);
let mut node = tree.node_mut(&idx_a);

*node.data_mut() += 10;
assert_eq!(node.data(), &11);

pub fn swap_data_with(&mut self, other_idx: &NodeIdx<V>)

Swaps the data of this and the other node with the given other_idx.

Panics

Panics if the other_idx is invalid.

See also

See try_swap_nodes to swap two independent subtrees rooted at given node indices.

Examples

use orx_tree::*;

//      1
//     ╱ ╲
//    ╱   ╲
//   2     3
//  ╱ ╲   ╱
// 4   5 6

let mut tree = DynTree::new(1);

let mut root = tree.root_mut();
let id1 = root.idx();
let [id2, id3] = root.push_children([2, 3]);

let mut n2 = tree.node_mut(&id2);
let [id4, id5] = n2.push_children([4, 5]);

let mut n3 = tree.node_mut(&id3);
n3.push_child(6);

// swap data of nodes to obtain

//      2
//     ╱ ╲
//    ╱   ╲
//   1     5
//  ╱ ╲   ╱
// 4   3 6

tree.node_mut(&id4).swap_data_with(&id4); // does nothing
tree.node_mut(&id2).swap_data_with(&id1);
tree.node_mut(&id5).swap_data_with(&id3);

let bfs: Vec<_> = tree.root().walk::<Bfs>().copied().collect();
assert_eq!(bfs, [2, 1, 5, 4, 3, 6]);

pub fn swap_data_with_parent(&mut self) -> bool

Swaps the data of this node with its parent’s data, and returns true.

Does nothing and returns false if this node is the root, and hence, has no parent.

Examples

use orx_tree::*;

//      1
//     ╱ ╲
//    ╱   ╲
//   2     3
//  ╱ ╲   ╱ ╲
// 4   5 6   7
// |     |  ╱ ╲
// 8     9 10  11
let mut tree = DynTree::new(1);
let [id2, id3] = tree.root_mut().push_children([2, 3]);
let [id4, _] = tree.node_mut(&id2).push_children([4, 5]);
let id8 = tree.node_mut(&id4).push_child(8);
let [id6, id7] = tree.node_mut(&id3).push_children([6, 7]);
tree.node_mut(&id6).push_child(9);
tree.node_mut(&id7).push_children([10, 11]);

// let's move 8 up to root one by one, swapping with its parents
//      8
//     ╱ ╲
//    ╱   ╲
//   1     3
//  ╱ ╲   ╱ ╲
// 2   5 6   7
// |     |  ╱ ╲
// 4     9 10  11
tree.node_mut(&id8).swap_data_with_parent();
tree.node_mut(&id4).swap_data_with_parent();
tree.node_mut(&id2).swap_data_with_parent();

let swapped = tree.root_mut().swap_data_with_parent();
assert!(!swapped);

let bfs: Vec<_> = tree.root().walk::<Bfs>().copied().collect();
assert_eq!(bfs, [8, 1, 3, 2, 5, 6, 7, 4, 9, 10, 11]);

pub fn push_child(&mut self, value: V::Item) -> NodeIdx<V>

Pushes a child node with the given value; returns the NodeIdx of the created node.

If this node already has children, the new child is added to the end as the new right-most node among the children.

Examples

use orx_tree::*;

//      0
//     ╱ ╲
//    ╱   ╲
//   1     2
//  ╱ ╲   ╱ ╲
// 3   4 5   6
// |     |  ╱ ╲
// 7     8 9   10

let mut tree = DynTree::<_>::new(0);

let mut root = tree.root_mut();
let id1 = root.push_child(1);
let id2 = root.push_child(2);

let mut n1 = tree.node_mut(&id1);
let id3 = n1.push_child(3);
n1.push_child(4);

tree.node_mut(&id3).push_child(7);

let mut n2 = tree.node_mut(&id2);
let id5 = n2.push_child(5);
let id6 = n2.push_child(6);

tree.node_mut(&id5).push_child(8);
tree.node_mut(&id6).push_child(9);
tree.node_mut(&id6).push_child(10);

// validate the tree

let bfs: Vec<_> = tree.root().walk::<Bfs>().copied().collect();
assert_eq!(bfs, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]);

let dfs: Vec<_> = tree.root().walk::<Dfs>().copied().collect();
assert_eq!(dfs, [0, 1, 3, 7, 4, 2, 5, 8, 6, 9, 10]);

pub fn push_children<const N: usize>( &mut self, values: [V::Item; N], ) -> [NodeIdx<V>; N]

Pushes the given constant number of values as children of this node; returns the NodeIdx array of the created nodes.

If this node already has children, the new children are added to the end as the new right-most nodes of the children.

Examples

use orx_tree::*;

//      0
//     ╱ ╲
//    ╱   ╲
//   1     2
//  ╱ ╲   ╱ ╲
// 3   4 5   6
// |     |  ╱ ╲
// 7     8 9   10

let mut tree = DaryTree::<4, _>::new(0);

let mut root = tree.root_mut();
let [id1, id2] = root.push_children([1, 2]);

let mut n1 = tree.node_mut(&id1);
let [id3, _] = n1.push_children([3, 4]);

tree.node_mut(&id3).push_child(7);

let mut n2 = tree.node_mut(&id2);
let [id5, id6] = n2.push_children([5, 6]);

tree.node_mut(&id5).push_child(8);
tree.node_mut(&id6).push_children([9, 10]);

// validate the tree

let bfs: Vec<_> = tree.root().walk::<Bfs>().copied().collect();
assert_eq!(bfs, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]);

let dfs: Vec<_> = tree.root().walk::<Dfs>().copied().collect();
assert_eq!(dfs, [0, 1, 3, 7, 4, 2, 5, 8, 6, 9, 10]);

pub fn extend_children<'b, I>( &'b mut self, values: I, ) -> impl Iterator<Item = NodeIdx<V>> + 'b + use<'b, 'a, I, V, M, P, MO>

where I: IntoIterator<Item = V::Item>, I::IntoIter: 'b,

Pushes the given variable number of values as children of this node; returns the NodeIdx iterator of the created nodes.

If this node already has children, the new children are added to the end as the new right-most nodes of the children.

Importantly note that this method returns a lazy iterator. If the returned iterator is not consumed, the children will not be pushed.

Examples

use orx_tree::*;

//      0
//     ╱ ╲
//    ╱   ╲
//   1     2
//  ╱ ╲   ╱ ╲
// 3   4 5   6
// |     |  ╱ ╲
// 7     8 9   10

let mut idx = vec![];

let mut tree = DynTree::<_>::new(0);

let mut root = tree.root_mut();
idx.push(root.idx());
idx.extend(root.extend_children(1..=2));

let mut n1 = tree.node_mut(&idx[1]);
idx.extend(n1.extend_children([3, 4]));

let mut n2 = tree.node_mut(&idx[2]);
idx.extend(n2.extend_children(5..=6));

idx.push(tree.node_mut(&idx[3]).push_child(7));

idx.push(tree.node_mut(&idx[5]).push_child(8));
idx.extend(tree.node_mut(&idx[6]).extend_children([9, 10]));

// validate the tree

let root = tree.root();

let bfs: Vec<_> = root.walk::<Bfs>().copied().collect();
assert_eq!(bfs, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]);

let dfs: Vec<_> = root.walk::<Dfs>().copied().collect();
assert_eq!(dfs, [0, 1, 3, 7, 4, 2, 5, 8, 6, 9, 10]);

pub fn push_child_tree<Vs>(&mut self, subtree: impl SubTree<Vs>) -> NodeIdx<V>

where Vs: TreeVariant<Item = V::Item>,

Appends the entire subtree of another tree as a child of this node; and returns the NodeIdx of the created child node.

In other words, the root of the subtree will be immediate child of this node, and the other nodes of the subtree will also be added with the same orientation relative to the subtree root.

Subtree Variants

• I. Cloned / copied subtree
  • A subtree cloned or copied from another tree.
  • The source tree remains unchanged.
  • Can be created by as_cloned_subtree and as_copied_subtree methods.
  • O(n)
• II. Subtree moved out of another tree
  • The subtree will be moved from the source tree to this tree.
  • Can be created by into_subtree method.
  • O(n)
• III. Another entire tree
  • The other tree will be consumed and moved into this tree.
  • O(1)

Examples

I. Append Subtree cloned-copied from another Tree

Remains the source tree unchanged.

Runs in O(n) time where n is the number of source nodes.

use orx_tree::*;

//     a          b
// -----------------------
//     0          5
//    ╱ ╲        ╱ ╲
//   1   2      6   7
//  ╱ ╲         |  ╱ ╲
// 3   4        8 9   10

let mut a = DynTree::<_>::new(0);
let [id1, _] = a.root_mut().push_children([1, 2]);
let [id3, _] = a.node_mut(&id1).push_children([3, 4]);

let mut b = DaryTree::<4, _>::new(5);
let [id6, id7] = b.root_mut().push_children([6, 7]);
b.node_mut(&id6).push_child(8);
b.node_mut(&id7).push_children([9, 10]);

// clone b.subtree(n6) under a.n3
// clone b.subtree(n7) under a.n0
//        a
// -----------------------
//        0
//       ╱|╲
//      ╱ | ╲
//     ╱  |  ╲
//    ╱   |   ╲
//   1    2    7
//  ╱ ╲       ╱ ╲
// 3   4     9   10
// |
// 6
// |
// 8

let n6 = b.node(&id6).as_cloned_subtree();
a.node_mut(&id3).push_child_tree(n6);

let n7 = b.node(&id7).as_copied_subtree();
a.root_mut().push_child_tree(n7);

// validate the trees

let bfs_a: Vec<_> = a.root().walk::<Bfs>().copied().collect();
assert_eq!(bfs_a, [0, 1, 2, 7, 3, 4, 9, 10, 6, 8]);

let bfs_b: Vec<_> = b.root().walk::<Bfs>().copied().collect();
assert_eq!(bfs_b, [5, 6, 7, 8, 9, 10]); // unchanged

II. Append Subtree moved out of another Tree

The source subtree rooted at the given node will be removed from the source tree.

Runs in O(n) time where n is the number of source nodes.

use orx_tree::*;

//     a          b
// -----------------------
//     0          5
//    ╱ ╲        ╱ ╲
//   1   2      6   7
//  ╱ ╲         |  ╱ ╲
// 3   4        8 9   10

// into_lazy_reclaim: to keep the indices valid
let mut a = DynTree::<_>::new(0).into_lazy_reclaim();
let [id1, id2] = a.root_mut().push_children([1, 2]);
a.node_mut(&id1).push_children([3, 4]);

// into_lazy_reclaim: to keep the indices valid
let mut b = DaryTree::<4, _>::new(5).into_lazy_reclaim();
let id5 = b.root().idx();
let [id6, id7] = b.root_mut().push_children([6, 7]);
b.node_mut(&id6).push_child(8);
b.node_mut(&id7).push_children([9, 10]);

// move b.subtree(n7) under a.n2
// move a.subtree(n1) under b.n5
//     a          b
// -----------------------
//     0          5
//      ╲        ╱ ╲
//       2      6   1
//       |      |  ╱ ╲
//       7      8 3   4
//      ╱ ╲
//     9   10

let n7 = b.node_mut(&id7).into_subtree();
a.node_mut(&id2).push_child_tree(n7);

let n1 = a.node_mut(&id1).into_subtree();
b.node_mut(&id5).push_child_tree(n1);

// validate the trees

let bfs_a: Vec<_> = a.root().walk::<Bfs>().copied().collect();
assert_eq!(bfs_a, [0, 2, 7, 9, 10]);

let bfs_b: Vec<_> = b.root().walk::<Bfs>().copied().collect();
assert_eq!(bfs_b, [5, 6, 1, 8, 3, 4]);

III. Append Another Tree

The source tree will be moved into the target tree.

Runs in O(1) time.

use orx_tree::*;

//  tree    b      c
// ----------------------
//     0    4      2
//    ╱     |     ╱ ╲
//   1      7    5   6
//  ╱            |  ╱ ╲
// 3             8 9   10
// ----------------------
//      0
//     ╱ ╲
//    ╱   ╲
//   1     2
//  ╱ ╲   ╱ ╲
// 3   4 5   6
//     | |  ╱ ╲
//     7 8 9   10

let mut tree = DynTree::<_>::new(0);
let id0 = tree.root().idx();
let id1 = tree.node_mut(&id0).push_child(1);
tree.node_mut(&id1).push_child(3);

let mut b = BinaryTree::<_>::new(4);
b.root_mut().push_child(7);

let mut c = DaryTree::<4, _>::new(2);
let [id5, id6] = c.root_mut().push_children([5, 6]);
c.node_mut(&id5).push_child(8);
c.node_mut(&id6).push_children([9, 10]);

// merge b & c into tree

let id4 = tree.node_mut(&id1).push_child_tree(b);
let id2 = tree.node_mut(&id0).push_child_tree(c);

assert_eq!(tree.node(&id2).data(), &2);
assert_eq!(tree.node(&id4).data(), &4);

// validate the tree

let bfs: Vec<_> = tree.root().walk::<Bfs>().copied().collect();
assert_eq!(bfs, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]);

pub fn push_child_tree_within( &mut self, subtree: impl SubTreeWithin<V>, ) -> NodeIdx<V>

Appends the entire subtree of this tree as a child of this node; and returns the NodeIdx of the created child node.

In other words, the root of the subtree will be immediate child of this node, and the other nodes of the subtree will also be added with the same orientation relative to the subtree root.

Subtree Variants

• I. Subtree moved out of this tree
  • The subtree will be moved from its original to child of this node.
  • Can be created by into_subtree_within method.
  • Panics if the root of the subtree is an ancestor of this node.
  • O(1)
• II. Cloned / copied subtree from this tree
  • A subtree cloned or copied from another tree.
  • The source tree remains unchanged.
  • Can be created by as_cloned_subtree_within and as_copied_subtree_within methods.
  • O(n)

Panics

Panics if the subtree is moved out of this tree created by into_subtree_within (I.) and the root of the subtree is an ancestor of this node. Notice that such a move would break structural properties of the tree. When we are not certain, we can test the relation using the the is_ancestor_of method.

Examples

I. Append Subtree moved from another position of this tree

use orx_tree::*;

//      1                1              1
//     ╱ ╲              ╱ ╲             |
//    ╱   ╲            ╱   ╲            |
//   2     3          2     3           2
//  ╱ ╲   ╱ ╲   =>   ╱|╲   ╱ ╲    =>   ╱|╲
// 4   5 6   7      4 5 8 6   7       4 5 8
// |                                    |
// 8                                    3
//                                     ╱ ╲
//                                    6   7

let mut tree = DynTree::<_>::new(1);

let [id2, id3] = tree.root_mut().push_children([2, 3]);
let [id4, id5] = tree.node_mut(&id2).push_children([4, 5]);
let id8 = tree.node_mut(&id4).push_child(8);
tree.node_mut(&id3).push_children([6, 7]);

// move subtree rooted at n8 (single node) as a child of n2
let st8 = id8.into_subtree_within();
tree.node_mut(&id2).push_child_tree_within(st8);

// move subtree rooted at n3 (n3, n6 & n7) as a child of n5
let st3 = id3.into_subtree_within();
tree.node_mut(&id5).push_child_tree_within(st3);

// validate the tree

let bfs: Vec<_> = tree.root().walk::<Bfs>().copied().collect();
assert_eq!(bfs, [1, 2, 4, 5, 8, 3, 6, 7]);

let dfs: Vec<_> = tree.root().walk::<Dfs>().copied().collect();
assert_eq!(dfs, [1, 2, 4, 5, 3, 6, 7, 8]);

II. Append Subtree cloned-copied from another position of this tree

Remains the source tree unchanged.

Runs in O(n) time where n is the number of source nodes.

use orx_tree::*;

//      1                1
//     ╱ ╲              ╱ ╲
//    ╱   ╲            ╱   ╲
//   2     3          2     3
//  ╱ ╲   ╱ ╲   =>   ╱ ╲   ╱|╲
// 4   5 6   7      4   5 6 7 3
//     |            |   |    ╱ ╲
//     8            5   8   6   7
//                  |
//                  8

let mut tree = DynTree::<_>::new(1);

let [id2, id3] = tree.root_mut().push_children([2, 3]);
let [id4, id5] = tree.node_mut(&id2).push_children([4, 5]);
tree.node_mut(&id5).push_child(8);
tree.node_mut(&id3).push_children([6, 7]);

// clone subtree rooted at n5 as a child of n4
let st5 = id5.as_cloned_subtree_within();
tree.node_mut(&id4).push_child_tree_within(st5);

// copy subtree rooted at n3 (n3, n6 & n7) as a child of n3 (itself)
let st3 = id3.as_cloned_subtree_within();
tree.node_mut(&id3).push_child_tree_within(st3);

// validate the tree

let bfs: Vec<_> = tree.root().walk::<Bfs>().copied().collect();
assert_eq!(bfs, [1, 2, 3, 4, 5, 6, 7, 3, 5, 8, 6, 7, 8]);

let dfs: Vec<_> = tree.root().walk::<Dfs>().copied().collect();
assert_eq!(dfs, [1, 2, 4, 5, 8, 5, 8, 3, 6, 7, 3, 6, 7]);

pub fn push_sibling(&mut self, side: Side, value: V::Item) -> NodeIdx<V>

Pushes a sibling node with the given value:

• as the immediate left-sibling of this node when side is Side::Left,
• as the immediate right-sibling of this node when side is Side::Right,

returns the NodeIdx of the created node.

Panics

Panics if this node is the root; root node cannot have a sibling.

Examples

use orx_tree::*;

//      1
//     ╱ ╲
//    ╱   ╲
//   2     3
//  ╱ ╲     ╲
// 4   5     6

let mut tree = DynTree::new(1);

let mut root = tree.root_mut();
let [id2, id3] = root.push_children([2, 3]);

let mut n2 = tree.node_mut(&id2);
let [id4, _] = n2.push_children([4, 5]);

let mut n3 = tree.node_mut(&id3);
let [id6] = n3.push_children([6]);

// grow horizontally to obtain
//         1
//        ╱ ╲
//       ╱   ╲
//      2     3
//     ╱|╲    └────────
//    ╱ | ╲          ╱ | ╲
//   ╱ ╱ ╲ ╲        ╱  |  ╲
//  ╱ ╱   ╲ ╲      ╱╲  |  ╱╲
// 7 4    8  5    9 10 6 11 12

let mut n4 = tree.node_mut(&id4);
n4.push_sibling(Side::Left, 7);
n4.push_sibling(Side::Right, 8);

let mut n6 = tree.node_mut(&id6);
n6.push_sibling(Side::Left, 9);
n6.push_sibling(Side::Left, 10);
let id12 = n6.push_sibling(Side::Right, 12);
let id11 = n6.push_sibling(Side::Right, 11);

let bfs: Vec<_> = tree.root().walk::<Bfs>().copied().collect();
assert_eq!(bfs, [1, 2, 3, 7, 4, 8, 5, 9, 10, 6, 11, 12]);

assert_eq!(tree.node(&id12).data(), &12);
assert_eq!(tree.node(&id11).data(), &11);

pub fn push_siblings<const N: usize>( &mut self, side: Side, values: [V::Item; N], ) -> [NodeIdx<V>; N]

Pushes the given constant number of values as:

• as the immediate left-siblings of this node when side is Side::Left,
• as the immediate right-siblings of this node when side is Side::Right,

returns the NodeIdx array of the created nodes.

Panics

Panics if this node is the root; root node cannot have a sibling.

Examples

use orx_tree::*;

//      1
//     ╱ ╲
//    ╱   ╲
//   2     3
//  ╱ ╲     ╲
// 4   5     6

let mut tree = DynTree::new(1);

let mut root = tree.root_mut();
let [id2, id3] = root.push_children([2, 3]);

let mut n2 = tree.node_mut(&id2);
let [id4, _] = n2.push_children([4, 5]);

let mut n3 = tree.node_mut(&id3);
let [id6] = n3.push_children([6]);

// grow horizontally to obtain
//         1
//        ╱ ╲
//       ╱   ╲
//      2     3
//     ╱|╲    └────────
//    ╱ | ╲          ╱ | ╲
//   ╱ ╱ ╲ ╲        ╱  |  ╲
//  ╱ ╱   ╲ ╲      ╱╲  |  ╱╲
// 7 4    8  5    9 10 6 11 12

let mut n4 = tree.node_mut(&id4);
n4.push_sibling(Side::Left, 7);
n4.push_sibling(Side::Right, 8);

let mut n6 = tree.node_mut(&id6);
let [id9, id10] = n6.push_siblings(Side::Left, [9, 10]);
let [id11, id12] = n6.push_siblings(Side::Right, [11, 12]);

let bfs: Vec<_> = tree.root().walk::<Bfs>().copied().collect();
assert_eq!(bfs, [1, 2, 3, 7, 4, 8, 5, 9, 10, 6, 11, 12]);

assert_eq!(tree.node(&id9).data(), &9);
assert_eq!(tree.node(&id10).data(), &10);
assert_eq!(tree.node(&id11).data(), &11);
assert_eq!(tree.node(&id12).data(), &12);

pub fn extend_siblings<'b, I>( &'b mut self, side: Side, values: I, ) -> impl Iterator<Item = NodeIdx<V>> + 'b + use<'b, 'a, I, V, M, P, MO>

where I: IntoIterator<Item = V::Item>, I::IntoIter: 'b,

Pushes the given variable number of values as:

• as the immediate left-siblings of this node when side is Side::Left,
• as the immediate right-siblings of this node when side is Side::Right,

returns the NodeIdx iterator of the created nodes.

Importantly note that this method returns a lazy iterator. If the returned iterator is not consumed, the siblings will not be pushed.

Panics

Panics if this node is the root; root node cannot have a sibling.

Examples

use orx_tree::*;

//      1
//     ╱ ╲
//    ╱   ╲
//   2     3
//  ╱ ╲     ╲
// 4   5     6

let mut tree = DynTree::new(1);

let mut root = tree.root_mut();
let [id2, id3] = root.push_children([2, 3]);

let mut n2 = tree.node_mut(&id2);
let [id4, _] = n2.push_children([4, 5]);

let mut n3 = tree.node_mut(&id3);
let [id6] = n3.push_children([6]);

// grow horizontally to obtain
//         1
//        ╱ ╲
//       ╱   ╲
//      2     3
//     ╱|╲    └────────
//    ╱ | ╲          ╱ | ╲
//   ╱ ╱ ╲ ╲        ╱  |  ╲
//  ╱ ╱   ╲ ╲      ╱╲  |  ╱╲
// 7 4    8  5    9 10 6 11 12

let mut n4 = tree.node_mut(&id4);
n4.push_sibling(Side::Left, 7);
n4.push_sibling(Side::Right, 8);

let mut n6 = tree.node_mut(&id6);
n6.extend_siblings(Side::Left, 9..=10).count();
let idx: Vec<_> = n6.extend_siblings(Side::Right, 11..=12).collect();

let bfs: Vec<_> = tree.root().walk::<Bfs>().copied().collect();
assert_eq!(bfs, [1, 2, 3, 7, 4, 8, 5, 9, 10, 6, 11, 12]);

assert_eq!(tree.node(&idx[0]).data(), &11);
assert_eq!(tree.node(&idx[1]).data(), &12);

pub fn push_sibling_tree<Vs>( &mut self, side: Side, subtree: impl SubTree<Vs>, ) -> NodeIdx<V>

where Vs: TreeVariant<Item = V::Item>,

Appends the entire subtree:

• as the immediate left-sibling of this node when side is Side::Left,
• as the immediate right-sibling of this node when side is Side::Right,

returns the NodeIdx of the sibling child node.

In other words, the root of the subtree will be immediate sibling of this node, and the other nodes of the subtree will also be added with the same orientation relative to the subtree root.

Panics

Panics if this node is the root; root node cannot have a sibling.

Subtree Variants

• I. Cloned / copied subtree
  • A subtree cloned or copied from another tree.
  • The source tree remains unchanged.
  • Can be created by as_cloned_subtree and as_copied_subtree methods.
  • O(n)
• II. Subtree moved out of another tree
  • The subtree will be moved from the source tree to this tree.
  • Can be created by into_subtree method.
  • O(n)
• III. Another entire tree
  • The other tree will be consumed and moved into this tree.
  • O(1)

Examples

I. Append Subtree cloned-copied from another Tree

Remains the source tree unchanged.

Runs in O(n) time where n is the number of source nodes.

use orx_tree::*;

//     a          b
// -----------------------
//     0          5
//    ╱ ╲        ╱ ╲
//   1   2      6   7
//  ╱ ╲         |  ╱ ╲
// 3   4        8 9   10

let mut a = DynTree::<_>::new(0);
let [id1, id2] = a.root_mut().push_children([1, 2]);
let [_, id4] = a.node_mut(&id1).push_children([3, 4]);

let mut b = DaryTree::<4, _>::new(5);
let [id6, id7] = b.root_mut().push_children([6, 7]);
b.node_mut(&id6).push_child(8);
b.node_mut(&id7).push_children([9, 10]);

// clone b.subtree(n6) under a.n3
// clone b.subtree(n7) under a.n0
//        a
// -----------------------
//        0
//       ╱|╲
//      ╱ | ╲
//     ╱  |  ╲
//    ╱   |   ╲
//   1    2    7
//  ╱|╲       ╱ ╲
// 3 6 4     9   10
//   |
//   8

let n6 = b.node(&id6).as_cloned_subtree();
a.node_mut(&id4).push_sibling_tree(Side::Left, n6);

let n7 = b.node(&id7).as_copied_subtree();
a.node_mut(&id2).push_sibling_tree(Side::Right, n7);

// validate the trees

let bfs_a: Vec<_> = a.root().walk::<Bfs>().copied().collect();
assert_eq!(bfs_a, [0, 1, 2, 7, 3, 6, 4, 9, 10, 8]);

let bfs_b: Vec<_> = b.root().walk::<Bfs>().copied().collect();
assert_eq!(bfs_b, [5, 6, 7, 8, 9, 10]); // unchanged

II. Append Subtree taken out of another Tree

The source subtree rooted at the given node will be removed from the source tree.

Runs in O(n) time where n is the number of source nodes.

use orx_tree::*;

//     a          b
// -----------------------
//     0          5
//    ╱ ╲        ╱ ╲
//   1   2      6   7
//  ╱ ╲         |  ╱ ╲
// 3   4        8 9   10

// into_lazy_reclaim -> to keep indices valid
let mut a = DynTree::<_>::new(0).into_lazy_reclaim();
let [id1, id2] = a.root_mut().push_children([1, 2]);
a.node_mut(&id1).push_children([3, 4]);

// into_lazy_reclaim -> to keep indices valid
let mut b = DaryTree::<4, _>::new(5).into_lazy_reclaim();
let [id6, id7] = b.root_mut().push_children([6, 7]);
b.node_mut(&id6).push_child(8);
b.node_mut(&id7).push_children([9, 10]);

// move b.subtree(n7) under a.n2
// move a.subtree(n1) under b.n5
//     a          b
// -----------------------
//     0          5
//    ╱ ╲        ╱ ╲
//   7   2      6   1
//  ╱ ╲         |  ╱ ╲
// 9   10       8 3   4
//
//

let n7 = b.node_mut(&id7).into_subtree();
a.node_mut(&id2).push_sibling_tree(Side::Left, n7);

let n1 = a.node_mut(&id1).into_subtree();
b.node_mut(&id6).push_sibling_tree(Side::Right, n1);

// validate the trees

let bfs_a: Vec<_> = a.root().walk::<Bfs>().copied().collect();
assert_eq!(bfs_a, [0, 7, 2, 9, 10]);

let bfs_b: Vec<_> = b.root().walk::<Bfs>().copied().collect();
assert_eq!(bfs_b, [5, 6, 1, 8, 3, 4]);

III. Append Another Tree

The source tree will be moved into the target tree.

Runs in O(1) time.

use orx_tree::*;

//  tree    b      c
// ----------------------
//     0    4      2
//    ╱     |     ╱ ╲
//   1      7    5   6
//  ╱            |  ╱ ╲
// 3             8 9   10
// ----------------------
//      0
//     ╱ ╲
//    ╱   ╲
//   1     2
//  ╱ ╲   ╱ ╲
// 4   3 5   6
// |     |  ╱ ╲
// 7     8 9   10

let mut tree = DynTree::<_>::new(0);
let id0 = tree.root().idx();
let id1 = tree.node_mut(&id0).push_child(1);
let id3 = tree.node_mut(&id1).push_child(3);

let mut b = BinaryTree::<_>::new(4);
b.root_mut().push_child(7);

let mut c = DaryTree::<4, _>::new(2);
let [id5, id6] = c.root_mut().push_children([5, 6]);
c.node_mut(&id5).push_child(8);
c.node_mut(&id6).push_children([9, 10]);

// merge b & c into tree

let id4 = tree.node_mut(&id3).push_sibling_tree(Side::Left, b);
let id2 = tree.node_mut(&id1).push_sibling_tree(Side::Right, c);

assert_eq!(tree.node(&id2).data(), &2);
assert_eq!(tree.node(&id4).data(), &4);

// validate the tree

let bfs: Vec<_> = tree.root().walk::<Bfs>().copied().collect();
assert_eq!(bfs, [0, 1, 2, 4, 3, 5, 6, 7, 8, 9, 10]);

pub fn push_sibling_tree_within( &mut self, side: Side, subtree: impl SubTreeWithin<V>, ) -> NodeIdx<V>

Appends the entire subtree:

• as the immediate left-sibling of this node when side is Side::Left,
• as the immediate right-sibling of this node when side is Side::Right,

returns the NodeIdx of the sibling child node.

In other words, the root of the subtree will be immediate sibling of this node, and the other nodes of the subtree will also be added with the same orientation relative to the subtree root.

Subtree Variants

• I. Subtree moved out of this tree
  • The subtree will be moved from its original to child of this node.
  • Can be created by into_subtree_within method.
  • Panics if the root of the subtree is an ancestor of this node.
  • O(1)
• II. Cloned / copied subtree from this tree
  • A subtree cloned or copied from another tree.
  • The source tree remains unchanged.
  • Can be created by as_cloned_subtree_within and as_copied_subtree_within methods.
  • O(n)

Panics

• Panics if this node is the root; root node cannot have a sibling.
• Panics if the subtree is moved out of this tree created by into_subtree_within (I.) and the root of the subtree is an ancestor of this node. Notice that such a move would break structural properties of the tree. When we are not certain, we can test the relation using the the is_ancestor_of method.

Examples

I. Append Subtree moved from another position of this tree

use orx_tree::*;

//      1                1              1
//     ╱ ╲              ╱ ╲             |
//    ╱   ╲            ╱   ╲            |
//   2     3          2     3           2
//  ╱ ╲   ╱ ╲   =>   ╱|╲   ╱ ╲    =>   ╱|╲
// 4   5 6   7      4 8 5 6   7       ╱ | ╲
// |                                 ╱ ╱ ╲ ╲
// 8                                4 3   8 5
//                                   ╱ ╲
//                                  6   7

let mut tree = DynTree::<_>::new(1);

let [id2, id3] = tree.root_mut().push_children([2, 3]);
let [id4, id5] = tree.node_mut(&id2).push_children([4, 5]);
let id8 = tree.node_mut(&id4).push_child(8);
tree.node_mut(&id3).push_children([6, 7]);

// move subtree rooted at n8 (single node) as left sibling of n5
let st8 = id8.into_subtree_within();
tree.node_mut(&id5)
    .push_sibling_tree_within(Side::Left, st8);

// move subtree rooted at n3 (n3, n6 & n7) as right sibling of n4
let st3 = id3.into_subtree_within();
tree.node_mut(&id4)
    .push_sibling_tree_within(Side::Right, st3);

// validate the tree

let bfs: Vec<_> = tree.root().walk::<Bfs>().copied().collect();
assert_eq!(bfs, [1, 2, 4, 3, 8, 5, 6, 7]);

let dfs: Vec<_> = tree.root().walk::<Dfs>().copied().collect();
assert_eq!(dfs, [1, 2, 4, 3, 6, 7, 8, 5]);

II. Append Subtree cloned-copied from another position of this tree

Remains the source tree unchanged.

Runs in O(n) time where n is the number of source nodes.

use orx_tree::*;

//      1                1
//     ╱ ╲              ╱ ╲
//    ╱   ╲            ╱   ╲
//   2     3          2     3
//  ╱ ╲   ╱ ╲   =>   ╱|╲   ╱|╲
// 4   5 6   7      4 6 5 6 7 3
//     |                |    ╱ ╲
//     8                8   6   7
//
//

let mut tree = DynTree::<_>::new(1);

let [id2, id3] = tree.root_mut().push_children([2, 3]);
let [_, id5] = tree.node_mut(&id2).push_children([4, 5]);
tree.node_mut(&id5).push_child(8);
let [id6, id7] = tree.node_mut(&id3).push_children([6, 7]);

// clone subtree rooted at n6 as left sibling of n5
let st6 = id6.as_cloned_subtree_within();
tree.node_mut(&id5)
    .push_sibling_tree_within(Side::Left, st6);

// copy subtree rooted at n3 (n3, n6 & n7) as right sibling of n7
let st3 = id3.as_cloned_subtree_within();
tree.node_mut(&id7)
    .push_sibling_tree_within(Side::Right, st3);

// validate the tree

let bfs: Vec<_> = tree.root().walk::<Bfs>().copied().collect();
assert_eq!(bfs, [1, 2, 3, 4, 6, 5, 6, 7, 3, 8, 6, 7]);

let dfs: Vec<_> = tree.root().walk::<Dfs>().copied().collect();
assert_eq!(dfs, [1, 2, 4, 6, 5, 8, 3, 6, 7, 3, 6, 7]);

pub fn push_parent(&mut self, value: V::Item) -> NodeIdx<V>

O(1) Inserts a node with the given value as the parent of this node; and returns the NodeIdx of the new parent node.

As a result of this move:

• this node and all its descendants will be down-shifted by one level in depth
• this node will be the only child of the new parent node
• this node’s earlier parent will be the parent of the new parent node
• if this node was the root, the new parent will now be the root

Examples

use orx_tree::*;

//                       0
//                       |
//      1                1
//     ╱ ╲              ╱ ╲
//    ╱   ╲            ╱   ╲
//   2     3     =>   6     7
//        ╱ ╲         |     |
//       4   5        2     3
//                         ╱ ╲
//                        4   5

let mut tree = DynTree::new(1);

let mut root = tree.root_mut();
let [id2, id3] = root.push_children([2, 3]);

let mut n3 = tree.node_mut(&id3);
n3.push_children([4, 5]);

// push parent (insert a node vertically)

let id0 = tree.root_mut().push_parent(0);
let id6 = tree.node_mut(&id2).push_parent(6);
let id7 = tree.node_mut(&id3).push_parent(7);

// test inserted parent indices

assert!(tree.node(&id0).is_root());
assert_eq!(tree.node(&id6).data(), &6);
assert_eq!(tree.node(&id7).data(), &7);

// validate the tree

let bfs: Vec<_> = tree.root().walk::<Bfs>().copied().collect();
assert_eq!(bfs, [0, 1, 6, 7, 2, 3, 4, 5]);

let dfs: Vec<_> = tree.root().walk::<Dfs>().copied().collect();
assert_eq!(dfs, [0, 1, 6, 2, 7, 3, 4, 5]);

pub fn prune(self) -> V::Item

Removes this node and all of its descendants from the tree; and returns the data of this node.

(!) As a method that removes nodes from the tree, this method might result in invalidating indices that are cached earlier in the Auto mode, but not in the Lazy mode. Please see the documentation of MemoryPolicy for details of node index validity. Specifically, the examples in the “Lazy Memory Claim: Preventing Invalid Indices” section presents a convenient way that allows us to make sure that the indices are valid.

See also

Note that this method returns the data of this node, while the data of the descendants are dropped.

If the data of the entire subtree is required, you may use into_walk method with the desired traversal to define the order of the returned iterator.

Examples

use orx_tree::*;

//      1
//     ╱ ╲
//    ╱   ╲
//   2     3
//  ╱ ╲   ╱ ╲
// 4   5 6   7
// |     |  ╱ ╲
// 8     9 10  11

let mut tree = DynTree::new(1);

let mut root = tree.root_mut();
let [id2, id3] = root.push_children([2, 3]);

let mut n2 = tree.node_mut(&id2);
let [id4, _] = n2.push_children([4, 5]);

let id8 = tree.node_mut(&id4).push_child(8);

let mut n3 = tree.node_mut(&id3);
let [id6, id7] = n3.push_children([6, 7]);

tree.node_mut(&id6).push_child(9);
tree.node_mut(&id7).push_children([10, 11]);

// prune n4 (removes 4 and 8)

let data = tree.node_mut(&id4).prune();
assert_eq!(data, 4);

let values: Vec<_> = tree.root().walk::<Bfs>().copied().collect();
assert_eq!(values, [1, 2, 3, 5, 6, 7, 9, 10, 11]);

assert_eq!(tree.get_node(&id4), None);
assert_eq!(tree.try_node(&id8), Err(NodeIdxError::RemovedNode));

// prune n3 (3, 6, 7, 9, 10, 11)

let data = tree.node_mut(&id3).prune();
assert_eq!(data, 3);

let values: Vec<_> = tree.root().walk::<Bfs>().copied().collect();
assert_eq!(values, [1, 2, 5]);

// prune the root: clear the entire (remaining) tree

let data = tree.root_mut().prune();
assert_eq!(data, 1);
assert!(tree.is_empty());
assert_eq!(tree.get_root(), None);

pub fn take_out(self) -> V::Item

Removes this node and returns its data; and connects the children of this node to its parent.

Therefore, unlike prune, the resulting tree will contain only one less node.

Assume that this node’s parent had n children while this node is the i-th child. Further, assume that this node has m children. Then, the i-th element of the parent’s children will be replaced with the m children. After the move, the parent will contain n - 1 + m children.

(!) As a method that removes nodes from the tree, this method might result in invalidating indices that are cached earlier in the Auto mode, but not in the Lazy mode. Please see the documentation of MemoryPolicy for details of node index validity. Specifically, the examples in the “Lazy Memory Claim: Preventing Invalid Indices” section presents a convenient way that allows us to make sure that the indices are valid.

Panics

Due to the fact that the tree can contain only one root, this move panics:

• if this node is the root,
• and it has more than one child.

Examples

use orx_tree::*;

//      1                    1                  1
//     ╱ ╲                  ╱ ╲                ╱|╲
//    ╱   ╲                ╱   ╲              ╱ | ╲
//   2     3     (-n7)    2     3     (-n2)  4  5  3
//  ╱ ╲   ╱ ╲     =>     ╱ ╲   ╱| ╲    =>    |    ╱| ╲
// 4   5 6   7          4   5 6 10 11        8   6 10 11
// |     |  ╱ ╲         |     |                  |
// 8     9 10  11       8     9                  9

let mut tree = DynTree::new(1);

let mut root = tree.root_mut();
let [id2, id3] = root.push_children([2, 3]);

let mut n2 = tree.node_mut(&id2);
let [id4, _] = n2.push_children([4, 5]);

tree.node_mut(&id4).push_child(8);

let mut n3 = tree.node_mut(&id3);
let [id6, id7] = n3.push_children([6, 7]);

tree.node_mut(&id6).push_child(9);
tree.node_mut(&id7).push_children([10, 11]);

// take out n7

let d7 = tree.node_mut(&id7).take_out();
assert_eq!(d7, 7);
assert_eq!(tree.try_node(&id7), Err(NodeIdxError::RemovedNode));

let bfs: Vec<_> = tree.root().walk::<Bfs>().copied().collect();
assert_eq!(bfs, [1, 2, 3, 4, 5, 6, 10, 11, 8, 9]);

// take out n2

let d2 = tree.node_mut(&id2).take_out();
assert_eq!(d2, 2);
assert_eq!(tree.get_node(&id2), None);

let bfs: Vec<_> = tree.root().walk::<Bfs>().copied().collect();
assert_eq!(bfs, [1, 4, 5, 3, 8, 6, 10, 11, 9]);

pub fn remove_children(&mut self)

Removes all children of this node together with the subtrees rooted at the children. This node remains in the tree while it becomes a leaf node if it was not already.

Note that, node.remove_children() call is just a shorthand for:

for c in node.children_mut() {
    _ = c.prune();
}

Examples

use orx_tree::*;

//      1
//     ╱ ╲
//    ╱   ╲
//   2     3
//  ╱ ╲   ╱ ╲
// 4   5 6   7
// |     |  ╱ ╲
// 8     9 10  11
let mut tree = DynTree::new(1);
let [id2, id3] = tree.root_mut().push_children([2, 3]);
let [id4, _] = tree.node_mut(&id2).push_children([4, 5]);
tree.node_mut(&id4).push_child(8);
let [id6, id7] = tree.node_mut(&id3).push_children([6, 7]);
tree.node_mut(&id6).push_child(9);
tree.node_mut(&id7).push_children([10, 11]);

// let's remove children of node 3
tree.node_mut(&id3).remove_children();

let bfs: Vec<_> = tree.root().walk::<Bfs>().copied().collect();
assert_eq!(bfs, [1, 2, 3, 4, 5, 8]);

pub fn custom_walk_mut<F>( &mut self, next_node: F, ) -> impl Iterator<Item = &'a mut V::Item>

where F: Fn(Node<'a, V, M, P>) -> Option<Node<'a, V, M, P>>,

Creates a custom mutable walk starting from this node such that:

• the first element will be this node, say n1,
• the second element will be node n2 = next_node(n1),
• the third element will be node n3 = next_node(n2),
• …

The iteration will terminate as soon as the next_node returns None.

Examples

In the following example we create a custom iterator that walks down the tree as follows:

• if the current node is not the last of its siblings, the next node will be its next sibling;
• if the current node is the last of its siblings and if it has children, the next node will be its first child;
• otherwise, the iteration will terminate.

This walk strategy is implemented by the next_node function, and custom_walk is called with this strategy.

use orx_tree::*;

//      1
//     ╱ ╲
//    ╱   ╲
//   2     3
//  ╱ ╲   ╱ ╲
// 4   5 6   7

fn next_node<'a, T>(node: DynNode<'a, T>) -> Option<DynNode<'a, T>> {
    let sibling_idx = node.sibling_idx();
    let is_last_sibling = sibling_idx == node.num_siblings() - 1;

    match is_last_sibling {
        true => node.get_child(0),
        false => match node.parent() {
            Some(parent) => {
                let child_idx = sibling_idx + 1;
                parent.get_child(child_idx)
            }
            None => None,
        },
    }
}

let mut tree = DynTree::new(1);

let mut root = tree.root_mut();
let [id2, id3] = root.push_children([2, 3]);
tree.node_mut(&id2).push_children([4, 5]);
tree.node_mut(&id3).push_children([6, 7]);

let mut root = tree.root_mut();
for (i, x) in root.custom_walk_mut(next_node).enumerate() {
    *x += (i + 1) * 100;
}

let values: Vec<_> = tree.root().custom_walk(next_node).copied().collect();
assert_eq!(values, [101, 202, 303, 406, 507]);

let all_values: Vec<_> = tree.root().walk::<Bfs>().copied().collect();
assert_eq!(all_values, [101, 202, 303, 4, 5, 406, 507]);

pub fn get_child_mut( &mut self, child_index: usize, ) -> Option<NodeMut<'_, V, M, P>>

Returns the mutable node of the child-index-th child of this node; returns None if the child index is out of bounds.

See also into_child_mut for consuming traversal.

Examples

use orx_tree::*;

//       1
//      ╱ ╲
//     ╱   ╲
//    ╱     ╲
//   2       3
//  ╱ ╲    ╱ | ╲
// 3   4  4  5  6
// |   |  |  |  |
// 6   7  7  8  9

let mut tree = DynTree::<_>::new(1);

let mut root = tree.root_mut();
root.push_children([2, 3]);

for c in 0..root.num_children() {
    let mut node = root.get_child_mut(c).unwrap();

    let val = *node.data();
    let children = (0..val).map(|x| x + 1 + val);

    let _ = node.extend_children(children).count();

    for c in 0..node.num_children() {
        let mut node = node.get_child_mut(c).unwrap();
        node.push_child(*node.data() + 3);
    }
}

// validate the tree

let root = tree.root();

let bfs: Vec<_> = root.walk::<Bfs>().copied().collect();
assert_eq!(bfs, [1, 2, 3, 3, 4, 4, 5, 6, 6, 7, 7, 8, 9]);

let dfs: Vec<_> = root.walk::<Dfs>().copied().collect();
assert_eq!(dfs, [1, 2, 3, 6, 4, 7, 3, 4, 7, 5, 8, 6, 9]);

pub fn child_mut(&mut self, child_index: usize) -> NodeMut<'_, V, M, P>

Returns the mutable node of the child-index-th child of this node.

See also into_child_mut for consuming traversal.

Panics

Panics if the child index is out of bounds; i.e., child_index >= self.num_children().

Examples

use orx_tree::*;

//       1
//      ╱ ╲
//     ╱   ╲
//    ╱     ╲
//   2       3
//  ╱ ╲    ╱ | ╲
// 3   4  4  5  6
// |   |  |  |  |
// 6   7  7  8  9

let mut tree = DynTree::<_>::new(1);

let mut root = tree.root_mut();
root.push_children([2, 3]);

for c in 0..root.num_children() {
    let mut node = root.child_mut(c);

    let val = *node.data();
    let children = (0..val).map(|x| x + 1 + val);

    let _ = node.extend_children(children).count();

    for c in 0..node.num_children() {
        let mut node = node.child_mut(c);
        node.push_child(*node.data() + 3);
    }
}

// validate the tree

let root = tree.root();

let bfs: Vec<_> = root.walk::<Bfs>().copied().collect();
assert_eq!(bfs, [1, 2, 3, 3, 4, 4, 5, 6, 6, 7, 7, 8, 9]);

let dfs: Vec<_> = root.walk::<Dfs>().copied().collect();
assert_eq!(dfs, [1, 2, 3, 6, 4, 7, 3, 4, 7, 5, 8, 6, 9]);

pub fn into_child_mut(self, child_index: usize) -> Option<NodeMut<'a, V, M, P>>

Consumes this mutable node and returns the mutable node of the child-index-th child; returns None if the child index is out of bounds.

See also get_child_mut for non-consuming access.

Examples

The example below demonstrates one way to build a tree using into_parent_mut and into_child_mut methods. In this approach, we start from the mutable root node. Then, we convert one mutable node to another, always having only one mutable node.

See also index returning growth methods for an alternative tree building approach, such as push_child and push_children.

use orx_tree::*;

//        r
//       ╱ ╲
//      ╱   ╲
//     ╱     ╲
//    a       b
//  ╱ | ╲    ╱ ╲
// c  d  e  f   g
//            ╱ | ╲
//           h  i  j

let mut tree = DynTree::<char>::new('r');

let mut root = tree.root_mut();
root.push_children(['a', 'b']);

let mut a = root.into_child_mut(0).unwrap();
a.push_children(['c', 'd', 'e']);

let mut b = a.into_parent_mut().unwrap().into_child_mut(1).unwrap();
b.push_children(['f', 'g']);

let mut g = b.into_child_mut(1).unwrap();
g.push_children(['h', 'i', 'j']);

// validate the tree

let root = tree.root();

let bfs: Vec<_> = root.walk::<Bfs>().copied().collect();
assert_eq!(bfs, ['r', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j']);

let dfs: Vec<_> = root.walk::<Dfs>().copied().collect();
assert_eq!(dfs, ['r', 'a', 'c', 'd', 'e', 'b', 'f', 'g', 'h', 'i', 'j']);

pub fn children_mut( &mut self, ) -> impl ExactSizeIterator<Item = NodeMut<'_, V, M, P, NodeMutDown>> + DoubleEndedIterator + use<'_, 'a, V, M, P, MO>

Creates an iterator over mutable nodes of children of this node.

Safety

Mutable tree nodes; i.e. NodeMut, has two orientation for mutations:

• NodeMutUpAndDown: This is the default orientation which allows to mutate both ancestors and descendants of the node.
• NodeMutDown: This orientation allows only to mutate self and descendants of the node. For instance, a mutable node with this orientation does not implement parent_mut or into_parent_mut methods.

The children_mut iterator yields mutable nodes with the limited NodeMutDown orientation. Therefore, mutating children of a node is safe, since the node itself or its ancestors cannot be mutated during the iteration.

Examples

In the following example, we first build the tree; however:

• we do not add nodes 8 & 9; and
• we add nodes 11 & 12 with initial values of 711 & 712.

Later using children_mut of node 2, we grow the tree by adding nodes 8 & 9. This demonstrates that we can safely mutate the structure of the tree.

Then, using children_mut of node 7, we update values of its children. This demonstrates the mutation of node data.

use orx_tree::*;

//       1
//      ╱ ╲
//     ╱   ╲
//    ╱     ╲
//   2       3
//  ╱ ╲     ╱  ╲
// 4   5   6    7
// |   |   |   ╱ ╲
// *8  *9 10 *11 *12

let mut tree = DynTree::<_>::new(1);

let mut root = tree.root_mut();

let [id2, id3] = root.push_children([2, 3]);

let mut n2 = tree.node_mut(&id2);
n2.push_children([4, 5]);

let mut n3 = tree.node_mut(&id3);
let [id6, id7] = n3.push_children([6, 7]);

tree.node_mut(&id6).push_child(10);
tree.node_mut(&id7).push_children([711, 712]);

// push nodes 8 and 9 using children_mut of node 2

let mut n2 = tree.node_mut(&id2);
for mut child in n2.children_mut() {
    let child_val = *child.data(); // 4 & 5
    child.push_child(child_val + 4); // 8 & 9
}

// update values using children_mut of node 7

let mut n7 = tree.node_mut(&id7);
for mut child in n7.children_mut() {
    *child.data_mut() -= 700;
}

// validate the tree

let root = tree.root();

let bfs: Vec<_> = root.walk::<Bfs>().copied().collect();
assert_eq!(bfs, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]);

let dfs: Vec<_> = root.walk::<Dfs>().copied().collect();
assert_eq!(dfs, [1, 2, 4, 8, 5, 9, 3, 6, 10, 7, 11, 12]);

pub fn walk_mut<T>(&'a mut self) -> impl Iterator<Item = &'a mut V::Item>

where T: Traverser<OverData>,

Creates an iterator that yields mutable references to data of all nodes belonging to the subtree rooted at this node.

The order of the elements is determined by the generic Traverser parameter T. Available implementations are:

• Bfs for breadth-first (wikipedia)
• Dfs for (pre-order) depth-first (wikipedia)
• PostOrder for post-order (wikipedia)

See also walk and into_walk variants.

Note that tree traversing methods typically allocate a temporary data structure that is dropped once the iterator is dropped. In use cases where we repeatedly iterate using any of the walk methods over different nodes or different trees, we can avoid the allocation by creating the traverser only once and using walk_with, walk_mut_with and into_walk_with methods instead. These methods additionally allow for iterating over nodes rather than data; and yielding node depths and sibling indices in addition to node data.

Examples

use orx_tree::*;

//      1
//     ╱ ╲
//    ╱   ╲
//   2     3
//  ╱ ╲   ╱ ╲
// 4   5 6   7
// |     |  ╱ ╲
// 8     9 10  11

let mut tree = DynTree::new(1);
let [id2, id3] = tree.root_mut().push_children([2, 3]);
let [id4, _] = tree.node_mut(&id2).push_children([4, 5]);
tree.node_mut(&id4).push_child(8);
let [id6, id7] = tree.node_mut(&id3).push_children([6, 7]);
tree.node_mut(&id6).push_child(9);
tree.node_mut(&id7).push_children([10, 11]);

// walk over mutable references of nodes of any subtree
// rooted at a selected node with different traversals

let mut root = tree.root_mut();
{
    let mut bfs = root.walk_mut::<Bfs>();
    assert_eq!(bfs.next(), Some(&mut 1));
    assert_eq!(bfs.next(), Some(&mut 2)); // ...
}

let mut n3 = tree.node_mut(&id3);
{
    let mut dfs = n3.walk_mut::<Dfs>();
    assert_eq!(dfs.next(), Some(&mut 3));
    assert_eq!(dfs.next(), Some(&mut 6)); // ...
}

let mut n2 = tree.node_mut(&id2);
{
    let mut post_order = n2.walk_mut::<PostOrder>();
    assert_eq!(post_order.next(), Some(&mut 8));
    assert_eq!(post_order.next(), Some(&mut 4)); // ...
}

pub fn walk_mut_with<T, O>( &'a mut self, traverser: &'a mut T, ) -> impl Iterator<Item = <<O as Over>::Enumeration as Enumeration>::Item<<O as OverMut>::NodeItemMut<'a, V, M, P>>>

where O: OverMut, T: Traverser<O>,

Creates an iterator that traverses all nodes belonging to the subtree rooted at this node.

The order of the elements is determined by the type of the traverser which implements Traverser. Available implementations are:

• Bfs for breadth-first (wikipedia)
• Dfs for (pre-order) depth-first (wikipedia)
• PostOrder for post-order (wikipedia)

As opposed to walk_mut, this method does require internal allocation. Furthermore, it allows to attach node depths or sibling indices to the yield values. Please see the examples below.

Examples

Examples - Repeated Iterations without Allocation

use orx_tree::*;

//      1
//     ╱ ╲
//    ╱   ╲
//   2     3
//  ╱ ╲   ╱ ╲
// 4   5 6   7
// |     |  ╱ ╲
// 8     9 10  11

let mut tree = DynTree::new(1);

let mut root = tree.root_mut();
let [id2, id3] = root.push_children([2, 3]);

let mut n2 = tree.node_mut(&id2);
let [id4, _] = n2.push_children([4, 5]);

tree.node_mut(&id4).push_child(8);

let mut n3 = tree.node_mut(&id3);
let [id6, id7] = n3.push_children([6, 7]);

tree.node_mut(&id6).push_child(9);
tree.node_mut(&id7).push_children([10, 11]);

// create the traverser 'dfs' only once, use it many times
// to walk over references, mutable references or removed values
// without additional allocation

let mut dfs = Dfs::default();

let root = tree.root();
let values: Vec<_> = root.walk_with(&mut dfs).copied().collect();
assert_eq!(values, [1, 2, 4, 8, 5, 3, 6, 9, 7, 10, 11]);

let mut n7 = tree.node_mut(&id7);
for x in n7.walk_mut_with(&mut dfs) {
    *x += 100;
}
let values: Vec<_> = tree.root().walk_with(&mut dfs).copied().collect();
assert_eq!(values, [1, 2, 4, 8, 5, 3, 6, 9, 107, 110, 111]);

let n3 = tree.node_mut(&id3);
let removed: Vec<_> = n3.into_walk_with(&mut dfs).collect();
assert_eq!(removed, [3, 6, 9, 107, 110, 111]);

let remaining: Vec<_> = tree.root().walk_with(&mut dfs).copied().collect();
assert_eq!(remaining, [1, 2, 4, 8, 5]);

Examples - Yielding Different Items

use orx_tree::*;

//      1
//     ╱ ╲
//    ╱   ╲
//   2     3
//  ╱ ╲   ╱ ╲
// 4   5 6   7
// |     |  ╱ ╲
// 8     9 10  11

let mut tree = DynTree::new(1);

let mut root = tree.root_mut();
let [id2, id3] = root.push_children([2, 3]);

let mut n2 = tree.node_mut(&id2);
let [id4, _] = n2.push_children([4, 5]);

tree.node_mut(&id4).push_child(8);

let mut n3 = tree.node_mut(&id3);
let [id6, id7] = n3.push_children([6, 7]);

tree.node_mut(&id6).push_child(9);
tree.node_mut(&id7).push_children([10, 11]);

// create the traverser 'bfs' iterator
// to walk over nodes rather than data

let mut bfs = Bfs::default().over_nodes();
// OR: Bfs::<OverNode>::new();

let n7 = tree.node(&id7);
let mut iter = n7.walk_with(&mut bfs);
let node = iter.next().unwrap();
assert_eq!(node.num_children(), 2);
assert_eq!(node.get_child(1).map(|x| *x.data()), Some(11));

// or to additionally yield depth and/or sibling-idx

let mut dfs = Dfs::default().with_depth().with_sibling_idx();
// OR: Dfs::<OverDepthSiblingIdxData>::new()

let n3 = tree.node(&id3);
let result: Vec<_> = n3
    .walk_with(&mut dfs)
    .map(|(depth, sibling_idx, data)| (depth, sibling_idx, *data))
    .collect();
assert_eq!(
    result,
    [
        (0, 0, 3),
        (1, 0, 6),
        (2, 0, 9),
        (1, 1, 7),
        (2, 0, 10),
        (2, 1, 11)
    ]
);

pub fn into_walk<T>( self, ) -> impl Iterator<Item = V::Item> + use<'a, T, V, M, P, MO>

where T: Traverser<OverData>,

Creates an iterator that yields owned (removed) data of all nodes belonging to the subtree rooted at this node.

Note that once the returned iterator is dropped, regardless of whether it is completely used up or not, the subtree rooted at this node will be removed from the tree it belongs to. If this node is the root of the tree, the tree will be left empty.

The order of the elements is determined by the generic Traverser parameter T. Available implementations are:

• Bfs for breadth-first (wikipedia)
• Dfs for (pre-order) depth-first (wikipedia)
• PostOrder for post-order (wikipedia)

See also walk and walk_mut for iterators over shared and mutable references, respectively.

Note that tree traversing methods typically allocate a temporary data structure that is dropped once the iterator is dropped. In use cases where we repeatedly iterate using any of the walk methods over different nodes or different trees, we can avoid the allocation by creating the traverser only once and using walk_with, walk_mut_with and into_walk_with methods instead. These methods additionally allow for iterating over nodes rather than data; and yielding node depths and sibling indices in addition to node data.

(!) As a method that removes nodes from the tree, this method might result in invalidating indices that are cached earlier in the Auto mode, but not in the Lazy mode. Please see the documentation of MemoryPolicy for details of node index validity. Specifically, the examples in the “Lazy Memory Claim: Preventing Invalid Indices” section presents a convenient way that allows us to make sure that the indices are valid.

Examples

use orx_tree::*;

//      1
//     ╱ ╲
//    ╱   ╲
//   2     3
//  ╱ ╲   ╱ ╲
// 4   5 6   7
// |     |  ╱ ╲
// 8     9 10  11

// keep indices valid during removals
let mut tree = DynTree::new(1).into_lazy_reclaim();
let [id2, id3] = tree.root_mut().push_children([2, 3]);
let [id4, _] = tree.node_mut(&id2).push_children([4, 5]);
tree.node_mut(&id4).push_child(8);
let [id6, id7] = tree.node_mut(&id3).push_children([6, 7]);
tree.node_mut(&id6).push_child(9);
tree.node_mut(&id7).push_children([10, 11]);

// remove any subtree rooted at a selected node
// from the tree, and collect the node values
// in the order of different traversals

let n4 = tree.node_mut(&id4);
let removed: Vec<_> = n4.into_walk::<PostOrder>().collect();
assert_eq!(removed, [8, 4]);

let remaining: Vec<_> = tree.root().walk::<Bfs>().copied().collect();
assert_eq!(remaining, [1, 2, 3, 5, 6, 7, 9, 10, 11]);

let n3 = tree.node_mut(&id3);
let removed: Vec<_> = n3.into_walk::<Dfs>().collect();
assert_eq!(removed, [3, 6, 9, 7, 10, 11]);

let remaining: Vec<_> = tree.root().walk::<Bfs>().copied().collect();
assert_eq!(remaining, [1, 2, 5]);

let root = tree.root_mut();
let removed: Vec<_> = root.into_walk::<Bfs>().collect(); // empties the tree
assert_eq!(removed, [1, 2, 5]);

assert!(tree.is_empty());
assert_eq!(tree.get_root(), None);

pub fn into_walk_with<T, O>( self, traverser: &'a mut T, ) -> impl Iterator<Item = <<O as Over>::Enumeration as Enumeration>::Item<<V as Variant>::Item>>

where O: OverMut, T: Traverser<O>,

Creates an iterator that yields owned (removed) data of all nodes belonging to the subtree rooted at this node.

Note that once the returned iterator is dropped, regardless of whether it is completely used up or not, the subtree rooted at this node will be removed from the tree it belongs to. If this node is the root of the tree, the tree will be left empty.

The order of the elements is determined by the type of the traverser which implements Traverser. Available implementations are:

• Bfs for breadth-first (wikipedia)
• Dfs for (pre-order) depth-first (wikipedia)
• PostOrder for post-order (wikipedia)

As opposed to into_walk, this method does require internal allocation. Furthermore, it allows to attach node depths or sibling indices to the yield values. Please see the examples below.

(!) As a method that removes nodes from the tree, this method might result in invalidating indices that are cached earlier in the Auto mode, but not in the Lazy mode. Please see the documentation of MemoryPolicy for details of node index validity. Specifically, the examples in the “Lazy Memory Claim: Preventing Invalid Indices” section presents a convenient way that allows us to make sure that the indices are valid.

Examples

Examples - Repeated Iterations without Allocation

use orx_tree::*;

//      1
//     ╱ ╲
//    ╱   ╲
//   2     3
//  ╱ ╲   ╱ ╲
// 4   5 6   7
// |     |  ╱ ╲
// 8     9 10  11

// keep indices valid during removals
let mut tree = DynTree::new(1).into_lazy_reclaim();
let [id2, id3] = tree.root_mut().push_children([2, 3]);
let [id4, _] = tree.node_mut(&id2).push_children([4, 5]);
tree.node_mut(&id4).push_child(8);
let [id6, id7] = tree.node_mut(&id3).push_children([6, 7]);
tree.node_mut(&id6).push_child(9);
tree.node_mut(&id7).push_children([10, 11]);

// create the traverser 'dfs' only once, use it many times
// to walk over references, mutable references or removed values
// without additional allocation

let mut dfs = Dfs::default();

let root = tree.root();
let values: Vec<_> = root.walk_with(&mut dfs).copied().collect();
assert_eq!(values, [1, 2, 4, 8, 5, 3, 6, 9, 7, 10, 11]);

let mut n7 = tree.node_mut(&id7);
for x in n7.walk_mut_with(&mut dfs) {
    *x += 100;
}
let values: Vec<_> = tree.root().walk_with(&mut dfs).copied().collect();
assert_eq!(values, [1, 2, 4, 8, 5, 3, 6, 9, 107, 110, 111]);

let n3 = tree.node_mut(&id3);
let removed: Vec<_> = n3.into_walk_with(&mut dfs).collect();
assert_eq!(removed, [3, 6, 9, 107, 110, 111]);

let remaining: Vec<_> = tree.root().walk_with(&mut dfs).copied().collect();
assert_eq!(remaining, [1, 2, 4, 8, 5]);

Examples - Yielding Different Items

use orx_tree::*;

//      1
//     ╱ ╲
//    ╱   ╲
//   2     3
//  ╱ ╲   ╱ ╲
// 4   5 6   7
// |     |  ╱ ╲
// 8     9 10  11

let mut tree = DynTree::new(1);

let mut root = tree.root_mut();
let [id2, id3] = root.push_children([2, 3]);

let mut n2 = tree.node_mut(&id2);
let [id4, _] = n2.push_children([4, 5]);

tree.node_mut(&id4).push_child(8);

let mut n3 = tree.node_mut(&id3);
let [id6, id7] = n3.push_children([6, 7]);

tree.node_mut(&id6).push_child(9);
tree.node_mut(&id7).push_children([10, 11]);

// create the traverser 'bfs' iterator
// to walk over nodes rather than data

let mut bfs = Bfs::default().over_nodes();
// OR: Bfs::<OverNode>::new();

let n7 = tree.node(&id7);
let mut iter = n7.walk_with(&mut bfs);
let node = iter.next().unwrap();
assert_eq!(node.num_children(), 2);
assert_eq!(node.get_child(1).map(|x| *x.data()), Some(11));

// or to additionally yield depth and/or sibling-idx

let mut dfs = Dfs::default().with_depth().with_sibling_idx();
// OR: Dfs::<OverDepthSiblingIdxData>::new()

let n3 = tree.node(&id3);
let result: Vec<_> = n3
    .walk_with(&mut dfs)
    .map(|(depth, sibling_idx, data)| (depth, sibling_idx, *data))
    .collect();
assert_eq!(
    result,
    [
        (0, 0, 3),
        (1, 0, 6),
        (2, 0, 9),
        (1, 1, 7),
        (2, 0, 10),
        (2, 1, 11)
    ]
);

pub fn recursive_set( &mut self, compute_data: impl Fn(&V::Item, &[&V::Item]) -> V::Item, )

Recursively sets the data of all nodes belonging to the subtree rooted at this node using the compute_data function.

This method provides an expressive way to update the values of a tree where value of a node is a function of its prior value and values of its children. Since the values of its children subsequently depend on their own children, it immediately follows that the value of the node depends on values of all of its descendants that must be computed to be able to compute the node’s value.

The compute_data function takes two arguments:

• current value (data) of this node, and
• slice of values of children of this node that are computed recursively using compute_data (*);

and then, computes the new value of this node.

The method is named recursive (*) due to the fact that,

• before computing the value of this node;
• values of all of its children are also computed and set using the compute_data function.

Note that this method does not actually make recursive method calls. Instead, it internally uses the PostOrder traverser which ensures that all required values are computed before they are used for another computation. This is a guard against potential stack overflow issues, and hence, can be used for trees of arbitrary depth.

Examples

In the following example, we set the value of every node to the sum of values of all its descendants.

While building the tree, we set only the values of the leaves. We initially set values of all other nodes to zero as a placeholder. Then, we call recursive_set to compute them.

use orx_tree::*;

let mut tree = DynTree::<_>::new(0);
let [id1, id2] = tree.root_mut().push_children([0, 0]);
tree.node_mut(&id1).push_children([1, 3]);
tree.node_mut(&id2).push_children([7, 2, 4]);
//      0
//     ╱ ╲
//    ╱   ╲
//   0     0
//  ╱ ╲   ╱|╲
// 1   3 7 2 4

tree.root_mut()
    .recursive_set(
        |current_value, children_values| match children_values.is_empty() {
            true => *current_value, // is a leaf
            false => children_values.iter().copied().sum(),
        },
    );
//      17
//     ╱ ╲
//    ╱   ╲
//   4    13
//  ╱ ╲   ╱|╲
// 1   3 7 2 4

let bfs: Vec<_> = tree.root().walk::<Bfs>().copied().collect();
assert_eq!(bfs, [17, 4, 13, 1, 3, 7, 2, 4]);

The following is a similar example where leaf nodes represent deterministic outcomes of a process. The root represents the current state. The remaining nodes represent intermediate states that we can reach from its parent with the given probability. Our task is to compute expected_value of each state.

Since we know the value of the leaves with certainty, we set them while constructing the tree. Then, we call recursive_set to compute the expected value of every other node.

use orx_tree::*;

#[derive(Clone)]
struct State {
    /// Probability of reaching this state from its parent.
    probability: f64,
    /// Expected value of the state; i.e., average of values of all leaves weighted by
    /// the probability of being reached from this state.
    expected_value: f64,
}

fn state(probability: f64, expected_value: f64) -> State {
    State {
        probability,
        expected_value,
    }
}

//         (1.0, ???)
//         ╱         ╲
//        ╱           ╲
//       ╱             ╲
//      ╱               ╲
//  (.3, ???)        (.7, ???)
//   ╱     ╲          |    ╲
//  ╱       ╲         |     ╲
// (.2, 9) (.8, 2) (.9, 5) (.1, 4)

let mut tree = DynTree::<_>::new(state(1.0, 0.0));

let [id1, id2] = tree
    .root_mut()
    .push_children([state(0.3, 0.0), state(0.7, 0.0)]);
tree.node_mut(&id1)
    .push_children([state(0.2, 9.0), state(0.8, 2.0)]);
tree.node_mut(&id2)
    .push_children([state(0.9, 5.0), state(0.1, 4.0)]);

tree.root_mut()
    .recursive_set(
        |current_value, children_values| match children_values.is_empty() {
            true => current_value.clone(), // is a leaf, we know expected value
            false => {
                let expected_value = children_values
                    .iter()
                    .fold(0.0, |a, x| a + x.probability * x.expected_value);
                state(current_value.probability, expected_value)
            }
        },
    );
//         (1.0, 4.45)
//         ╱         ╲
//        ╱           ╲
//       ╱             ╲
//      ╱               ╲
//   (.3, 3.4)      (.7, 4.9)
//   ╱     ╲          |    ╲
//  ╱       ╲         |     ╲
// (.2, 9) (.8, 2) (.9, 5) (.1, 4)

let equals = |a: f64, b: f64| (a - b).abs() < 1e-5;

assert!(equals(tree.root().data().expected_value, 4.45));
assert!(equals(tree.node(&id1).data().expected_value, 3.40));
assert!(equals(tree.node(&id2).data().expected_value, 4.90));

pub fn into_subtree(self) -> MovedSubTree<'a, V, M, P, MO>

Creates a subtree view including this node as the root and all of its descendants with their orientation relative to this node.

Consuming the created subtree in methods such as push_child_tree or push_sibling_tree will remove the subtree from this tree and move it to the target tree. Please see Append Subtree taken out of another Tree section of the examples of these methods.

Otherwise, it has no impact on the tree.

pub fn into_new_tree<V2>(self) -> Tree<V2, Auto, P>

where V2: TreeVariant<Item = V::Item>, P::PinnedVec<V2>: Default,

Removes the subtree rooted at this node from its tree; moves it into a new tree where this node is the root.

See also clone_as_tree in order to keep the original tree unchanged.

Examples

use orx_tree::*;

//      1
//     ╱ ╲
//    ╱   ╲
//   2     3
//  ╱ ╲   ╱ ╲
// 4   5 6   7
// |     |  ╱ ╲
// 8     9 10  11
let mut tree = DynTree::new(1).into_lazy_reclaim(); // ensure index validity
let [id2, id3] = tree.root_mut().push_children([2, 3]);
let [id4, _] = tree.node_mut(&id2).push_children([4, 5]);
tree.node_mut(&id4).push_child(8);
let [id6, id7] = tree.node_mut(&id3).push_children([6, 7]);
tree.node_mut(&id6).push_child(9);
tree.node_mut(&id7).push_children([10, 11]);

// let's move subtree rooted at n2 into new tree: tree2
//   2
//  ╱ ╲
// 4   5
// |
// 8
let tree2: DynTree<_> = tree.node_mut(&id2).into_new_tree();
let bfs: Vec<_> = tree2.root().walk::<Bfs>().copied().collect();
assert_eq!(bfs, [2, 4, 5, 8]);

// let's move subtree rooted at n7 into new tree: tree7
// this time, the target tree is a BinaryTree
//   7
//  ╱ ╲
// 10  11
let tree7: BinaryTree<_> = tree.node_mut(&id7).into_new_tree();
let bfs: Vec<_> = tree7.root().walk::<Bfs>().copied().collect();
assert_eq!(bfs, [7, 10, 11]);

// these subtrees are removed from the original tree
// 1
//  ╲
//   ╲
//    3
//   ╱
//  6
//  |
//  9
let bfs: Vec<_> = tree.root().walk::<Bfs>().copied().collect();
assert_eq!(bfs, [1, 3, 6, 9]);

impl<'a, V, M, P> NodeMut<'a, V, M, P, NodeMutUpAndDown>

where V: TreeVariant, M: MemoryPolicy, P: PinnedStorage,

pub fn parent_mut(&mut self) -> Option<NodeMut<'_, V, M, P>>

Returns the mutable node of this node’s parent, returns None if this is the root node.

See also into_parent_mut for consuming traversal.

Examples

The example below demonstrates one way to build a tree using into_parent_mut and into_child_mut methods. In this approach, we start from the mutable root node. Then, we convert one mutable node to another, always having only one mutable node.

See also index returning growth methods for an alternative tree building approach, such as push_child and push_children.

use orx_tree::*;

//        x
//       ╱ ╲
//      ╱   ╲
//     ╱     ╲
//    a       b
//  ╱ | ╲    ╱ ╲
// c  d  e  f   g

let mut tree = DynTree::<char>::new('r');

let mut root = tree.root_mut();
let [id_a, id_b] = root.push_children(['a', 'b']);

let mut a = tree.node_mut(&id_a);
a.push_children(['c', 'd', 'e']);

let mut b = tree.node_mut(&id_b);
let [_, id_g] = b.push_children(['f', 'g']);

let mut g = tree.node_mut(&id_g);
let mut b = g.parent_mut().unwrap();
let mut root = b.parent_mut().unwrap();

*root.data_mut() = 'x';

// validate the tree

let root = tree.root();

let bfs: Vec<_> = root.walk::<Bfs>().copied().collect();
assert_eq!(bfs, ['x', 'a', 'b', 'c', 'd', 'e', 'f', 'g']);

let dfs: Vec<_> = root.walk::<Dfs>().copied().collect();
assert_eq!(dfs, ['x', 'a', 'c', 'd', 'e', 'b', 'f', 'g']);

pub fn into_parent_mut(self) -> Option<NodeMut<'a, V, M, P>>

Consumes this mutable node and returns the mutable node of its parent, returns None if this is the root node.

See also parent_mut for non-consuming access.

Examples

The example below demonstrates one way to build a tree using into_parent_mut and into_child_mut methods. In this approach, we start from the mutable root node. Then, we convert one mutable node to another, always having only one mutable node.

See also index returning growth methods for an alternative tree building approach, such as push_child and push_children.

use orx_tree::*;

//        r
//       ╱ ╲
//      ╱   ╲
//     ╱     ╲
//    a       b
//  ╱ | ╲    ╱ ╲
// c  d  e  f   g
//            ╱ | ╲
//           h  i  j

let mut tree = DynTree::<char>::new('r');

let mut root = tree.root_mut();
root.push_children(['a', 'b']);

let mut a = root.into_child_mut(0).unwrap();
a.push_children(['c', 'd', 'e']);

let mut b = a.into_parent_mut().unwrap().into_child_mut(1).unwrap();
b.push_children(['f', 'g']);

let mut g = b.into_child_mut(1).unwrap();
g.push_children(['h', 'i', 'j']);

// validate the tree

let root = tree.root();

let bfs: Vec<_> = root.walk::<Bfs>().copied().collect();
assert_eq!(bfs, ['r', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j']);

let dfs: Vec<_> = root.walk::<Dfs>().copied().collect();
assert_eq!(dfs, ['r', 'a', 'c', 'd', 'e', 'b', 'f', 'g', 'h', 'i', 'j']);

Trait Implementations

impl<V, M, P> Debug for NodeMut<'_, V, M, P>

where V: TreeVariant, M: MemoryPolicy, P: PinnedStorage, V::Item: Debug,

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<V, M, P> Display for NodeMut<'_, V, M, P>

where V: TreeVariant, M: MemoryPolicy, P: PinnedStorage, V::Item: Display,

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Creates a convenient-to-read string representation of the tree or a subtree rooted at a node.

Examples

use orx_tree::*;

//      1
//     ╱ ╲
//    ╱   ╲
//   2     3
//  ╱ ╲   ╱ ╲
// 4   5 6   7
// |     |  ╱ ╲
// 8     9 10  11

let mut tree = DynTree::new(1);

let mut root = tree.root_mut();
let [id2, id3] = root.push_children([2, 3]);
let [id4, _] = tree.node_mut(&id2).push_children([4, 5]);
tree.node_mut(&id4).push_child(8);
let [id6, id7] = tree.node_mut(&id3).push_children([6, 7]);
tree.node_mut(&id6).push_child(9);
tree.node_mut(&id7).push_children([10, 11]);

let expected_str = r#"1
├──2
│  ├──4
│  │  └──8
│  └──5
└──3
   ├──6
   │  └──9
   └──7
      ├──10
      └──11
"#;
assert_eq!(tree.to_string(), expected_str);

let expected_str = r#"3
├──6
│  └──9
└──7
   ├──10
   └──11
"#;
println!("{}", tree.node(&id3).to_string());
assert_eq!(tree.node(&id3).to_string(), expected_str);

impl<'a, V, M, P> PartialEq<Node<'a, V, M, P>> for NodeMut<'_, V, M, P>

where V: TreeVariant, M: MemoryPolicy, P: PinnedStorage,

fn eq(&self, other: &Node<'a, V, M, P>) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<'a, V, M, P> PartialEq<NodeMut<'a, V, M, P>> for Node<'_, V, M, P>

where V: TreeVariant, M: MemoryPolicy, P: PinnedStorage,

fn eq(&self, other: &NodeMut<'a, V, M, P>) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<V, M, P> PartialEq for NodeMut<'_, V, M, P>

where V: TreeVariant, M: MemoryPolicy, P: PinnedStorage,

fn eq(&self, other: &Self) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.