Trait NodeRef

pub trait NodeRef<'a, V, M, P>: NodeRefCore<'a, V, M, P>
where
    V: TreeVariant + 'a,
    M: MemoryPolicy,
    P: PinnedStorage,
{
    // Provided methods
    fn idx(&self) -> NodeIdx<V> { ... }
    fn is_root(&self) -> bool { ... }
    fn is_leaf(&self) -> bool { ... }
    fn data(&self) -> &'a V::Item { ... }
    fn num_children(&self) -> usize { ... }
    fn num_siblings(&self) -> usize { ... }
    fn children(&'a self) -> impl ExactSizeIterator<Item = Node<'a, V, M, P>> { ... }
    fn get_child(&self, child_index: usize) -> Option<Node<'_, V, M, P>> { ... }
    fn child(&self, child_index: usize) -> Node<'_, V, M, P> { ... }
    fn parent(&self) -> Option<Node<'_, V, M, P>> { ... }
    fn sibling_idx(&self) -> usize { ... }
    fn depth(&self) -> usize { ... }
    fn ancestors(&'a self) -> impl Iterator<Item = Node<'a, V, M, P>> { ... }
    fn is_ancestor_of(&self, idx: &NodeIdx<V>) -> bool { ... }
    fn height(&self) -> usize { ... }
    fn walk<T>(&'a self) -> impl Iterator<Item = &'a V::Item>
       where T: Traverser<OverData>,
             Self: Sized { ... }
    fn walk_with<'t, T, O>(
        &'a self,
        traverser: &'t mut T,
    ) -> impl Iterator<Item = <<O as Over>::Enumeration as Enumeration>::Item<<O as Over>::NodeItem<'a, V, M, P>>>
       where O: Over,
             T: Traverser<O>,
             Self: Sized,
             't: 'a { ... }
    fn paths<T>(
        &'a self,
    ) -> impl Iterator<Item = impl Iterator<Item = &'a V::Item>>
       where T: Traverser<OverData> { ... }
    fn paths_with<T, O>(
        &'a self,
        traverser: &'a mut T,
    ) -> impl Iterator<Item = impl Iterator<Item = <O as Over>::NodeItem<'a, V, M, P>>>
       where O: Over<Enumeration = Val>,
             T: Traverser<O> { ... }
    fn clone_as_tree<V2>(&'a self) -> Tree<V2, M, P>
       where V2: TreeVariant<Item = V::Item> + 'a,
             P::PinnedVec<V2>: Default,
             V::Item: Clone { ... }
    fn leaves<T>(&'a self) -> impl Iterator<Item = &'a V::Item>
       where T: Traverser<OverData> { ... }
    fn leaves_with<T, O>(
        &'a self,
        traverser: &'a mut T,
    ) -> impl Iterator<Item = <<O as Over>::Enumeration as Enumeration>::Item<<O as Over>::NodeItem<'a, V, M, P>>>
       where O: Over,
             T: Traverser<O> { ... }
    fn indices<T>(&self) -> impl Iterator<Item = NodeIdx<V>>
       where T: Traverser<OverData>,
             V: 'static { ... }
    fn indices_with<T, O>(
        &self,
        traverser: &mut T,
    ) -> impl Iterator<Item = <O::Enumeration as Enumeration>::Item<NodeIdx<V>>>
       where O: Over,
             T: Traverser<O>,
             V: 'static,
             Self: Sized { ... }
    fn as_cloned_subtree(self) -> ClonedSubTree<'a, V, M, P, Self>
       where V::Item: Clone,
             Self: Sized { ... }
    fn as_copied_subtree(self) -> CopiedSubTree<'a, V, M, P, Self>
       where V::Item: Copy,
             Self: Sized { ... }
}

Reference to a tree node.

Provided Methods

fn idx(&self) -> NodeIdx<V>

Returns the node index of this node.

Note that a NodeIdx is used to provide safe and constant time access to any node in the tree.

Validity of node indices is crucial, while it is conveniently possible to have complete control on this. Please see the documentation of NodeIdx and MemoryPolicy for details.

fn is_root(&self) -> bool

Returns true if this is the root node; equivalently, if its parent is none.

Examples

use orx_tree::*;

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

let mut root = tree.root_mut();
assert!(root.is_root());

root.push_children(['a', 'b']);
for node in root.children() {
    assert!(!node.is_root());
}

fn is_leaf(&self) -> bool

Returns true if this is a leaf node; equivalently, if num_children is zero.

use orx_tree::*;

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

let mut tree = DynTree::new(1);
assert_eq!(tree.get_root().unwrap().is_leaf(), true); // both root & leaf

let mut root = tree.root_mut();
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);
let [id6] = n3.push_children([6]);

// walk over any subtree rooted at a selected node
// with different traversals

assert_eq!(tree.get_root().unwrap().is_leaf(), false);
assert_eq!(tree.node(&id2).is_leaf(), false);
assert_eq!(tree.node(&id3).is_leaf(), false);

assert_eq!(tree.node(&id4).is_leaf(), true);
assert_eq!(tree.node(&id5).is_leaf(), true);
assert_eq!(tree.node(&id6).is_leaf(), true);

fn data(&self) -> &'a V::Item

Returns a reference to the data of the node.

Examples

use orx_tree::*;

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

let mut root = tree.root_mut();
assert_eq!(root.data(), &0);

let [id_a] = root.push_children([1]);
let a = tree.node(&id_a);
assert_eq!(a.data(), &1);

fn num_children(&self) -> usize

Returns the number of child nodes of this node.

Examples

use orx_tree::*;

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

let mut root = tree.root_mut();
assert_eq!(root.num_children(), 0);

let [id_a, id_b] = root.push_children([1, 2]);
assert_eq!(root.num_children(), 2);

let mut node = tree.node_mut(&id_a);
node.push_child(3);
node.push_children([4, 5, 6]);
assert_eq!(node.num_children(), 4);

assert_eq!(tree.node(&id_b).num_children(), 0);

fn num_siblings(&self) -> usize

Returns the number of siblings including this node. In other words, it returns the num_children of its parent; or returns 1 if this is the root.

Examples

use orx_tree::*;

let mut tree = DynTree::new(0);
let [id1, id2, id3] = tree.root_mut().push_children([1, 2, 3]);
let id4 = tree.node_mut(&id3).push_child(4);

assert_eq!(tree.root().num_siblings(), 1);
assert_eq!(tree.node(&id1).num_siblings(), 3);
assert_eq!(tree.node(&id2).num_siblings(), 3);
assert_eq!(tree.node(&id3).num_siblings(), 3);
assert_eq!(tree.node(&id4).num_siblings(), 1);

fn children(&'a self) -> impl ExactSizeIterator<Item = Node<'a, V, M, P>>

Returns an exact-sized iterator of children nodes of this node.

Examples

use orx_tree::*;

// build the tree:
// r
// |-- a
//     |-- c, d, e
// |-- b
let mut tree = DynTree::<char>::new('r');

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

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

// iterate over children of nodes

let root = tree.root();
let depth1: Vec<_> = root.children().map(|x| *x.data()).collect();
assert_eq!(depth1, ['a', 'b']);

let b = root.children().nth(0).unwrap();
let depth2: Vec<_> = b.children().map(|x| *x.data()).collect();
assert_eq!(depth2, ['c', 'd', 'e']);

// depth first - two levels deep
let mut data = vec![];
for node in root.children() {
    data.push(*node.data());

    for child in node.children() {
        data.push(*child.data());
    }
}

assert_eq!(data, ['a', 'c', 'd', 'e', 'b']);

fn get_child(&self, child_index: usize) -> Option<Node<'_, V, M, P>>

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

Examples

use orx_tree::*;

// build the tree:
// r
// |-- a
//     |-- c, d, e
// |-- b
let mut tree = DynTree::<char>::new('r');

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

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

// use child to access lower level nodes

let root = tree.root();

let a = root.get_child(0).unwrap();
assert_eq!(a.data(), &'a');
assert_eq!(a.num_children(), 3);

assert_eq!(a.get_child(1).unwrap().data(), &'d');
assert_eq!(a.get_child(3), None);

fn child(&self, child_index: usize) -> Node<'_, V, M, P>

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

Panics

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

Examples

use orx_tree::*;

// build the tree:
// r
// |-- a
//     |-- c, d, e
// |-- b
let mut tree = DynTree::<char>::new('r');

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

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

// use child to access lower level nodes

let root = tree.root();

let a = root.child(0);
assert_eq!(a.data(), &'a');
assert_eq!(a.num_children(), 3);

assert_eq!(a.child(1).data(), &'d');
// let child = a.child(3); // out-of-bounds, panics!

fn parent(&self) -> Option<Node<'_, V, M, P>>

Returns the parent of this node; returns None if this is the root node.

Examples

use orx_tree::*;

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

let mut root = tree.root_mut();
assert_eq!(root.parent(), None);

root.push_children(['a', 'b']);
for node in root.children() {
    assert_eq!(node.parent().unwrap(), root);
}

fn sibling_idx(&self) -> usize

Returns the position of this node in the children collection of its parent; returns 0 if this is the root node (root has no other siblings).

O(S) where S is the number of siblings; i.e., requires linear search over the children of the parent of this node. Therefore, S depends on the tree size. It bounded by 2 in a BinaryTree, by 4 in a DaryTree with D=4. In a DynTree the children list can grow arbitrarily, therefore, it is not bounded.

Examples

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();
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 [id_h, id_i, id_j] = g.push_children(['h', 'i', 'j']);

// check sibling positions

let root = tree.root();
assert_eq!(root.sibling_idx(), 0);

for (i, node) in root.children().enumerate() {
    assert_eq!(node.sibling_idx(), i);
}

assert_eq!(tree.node(&id_h).sibling_idx(), 0);
assert_eq!(tree.node(&id_i).sibling_idx(), 1);
assert_eq!(tree.node(&id_j).sibling_idx(), 2);

fn depth(&self) -> usize

Returns the depth of this node with respect to the root of the tree which has a depth of 0.

O(D) requires linear time in maximum depth of the tree.

Examples

use orx_tree::*;

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

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, id5] = n2.push_children([4, 5]);

let [id8] = tree.node_mut(&id4).push_children([8]);

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

// access the leaves in different orders that is determined by traversal

assert_eq!(tree.root().depth(), 0);

assert_eq!(tree.node(&id2).depth(), 1);
assert_eq!(tree.node(&id3).depth(), 1);

assert_eq!(tree.node(&id4).depth(), 2);
assert_eq!(tree.node(&id5).depth(), 2);
assert_eq!(tree.node(&id6).depth(), 2);
assert_eq!(tree.node(&id7).depth(), 2);

assert_eq!(tree.node(&id8).depth(), 3);

fn ancestors(&'a self) -> impl Iterator<Item = Node<'a, V, M, P>>

Returns an iterator starting from this node moving upwards until the root:

• yields all ancestors of this node including this node,
• the first element is always this node, and
• the last element is always the root node of the tree.

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]);

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);
let [id10, _] = tree.node_mut(&id7).push_children([10, 11]);

// ancestors iterator over nodes
// upwards from the node to the root

let root = tree.root();
let mut iter = root.ancestors();
assert_eq!(iter.next().as_ref(), Some(&root));
assert_eq!(iter.next(), None);

let n10 = tree.node(&id10);
let ancestors_data: Vec<_> = n10.ancestors().map(|x| *x.data()).collect();
assert_eq!(ancestors_data, [10, 7, 3, 1]);

let n4 = tree.node(&id4);
let ancestors_data: Vec<_> = n4.ancestors().map(|x| *x.data()).collect();
assert_eq!(ancestors_data, [4, 2, 1]);

fn is_ancestor_of(&self, idx: &NodeIdx<V>) -> bool

Returns true if this node is an ancestor of the node with the given idx; false otherwise.

Searches in O(D) where D is the depth of the tree.

Note that the node is not an ancestor of itself.

Examples

use orx_tree::*;

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

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, id5] = n2.push_children([4, 5]);

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

// ancestor tests

assert!(tree.root().is_ancestor_of(&id4));
assert!(tree.root().is_ancestor_of(&id7));

assert!(tree.node(&id2).is_ancestor_of(&id5));
assert!(tree.node(&id3).is_ancestor_of(&id6));

// the other way around
assert!(!tree.node(&id6).is_ancestor_of(&id3));

// a node is not an ancestor of itself
assert!(!tree.node(&id6).is_ancestor_of(&id6));

// nodes belong to independent subtrees
assert!(!tree.node(&id2).is_ancestor_of(&id6));

fn height(&self) -> usize

Returns the height of this node relative to the deepest leaf of the subtree rooted at this node.

Equivalently, returns the maximum of depths of leaf nodes belonging to the subtree rooted at this node.

If this is a leaf node, height will be 0 which is the depth of the root (itself).

Examples

use orx_tree::*;

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

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]);
let [id6, _] = tree.node_mut(&id3).push_children([6, 7]);
tree.node_mut(&id6).push_child(8);

assert_eq!(tree.root().height(), 3); // max depth of the tree
assert_eq!(tree.node(&id2).height(), 1);
assert_eq!(tree.node(&id3).height(), 2);
assert_eq!(tree.node(&id4).height(), 0); // subtree with only the root
assert_eq!(tree.node(&id6).height(), 1);

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

where T: Traverser<OverData>, Self: Sized,

Creates an iterator that yields 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)
• Bfs for (pre-order) depth-first (wikipedia)
• PostOrder for post-order (wikipedia)

See also

See also walk_mut and into_walk for iterators over mutable references and owned (removed) values, 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.

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]);

// walk over any subtree rooted at a selected node
// with different traversals

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]);

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

let n2 = tree.node(&id2);
let post_order: Vec<_> = n2.walk::<PostOrder>().copied().collect();
assert_eq!(post_order, [8, 4, 5, 2]);

fn walk_with<'t, T, O>( &'a self, traverser: &'t mut T, ) -> impl Iterator<Item = <<O as Over>::Enumeration as Enumeration>::Item<<O as Over>::NodeItem<'a, V, M, P>>>

where O: Over, T: Traverser<O>, Self: Sized, 't: 'a,

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, this method does require internal allocation. Furthermore, it allows to iterate over nodes rather than data; and 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.get_root().unwrap().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.get_root().unwrap().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)
    ]
);

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

where T: Traverser<OverData>,

Returns an iterator of paths from all leaves of the subtree rooted at this node upwards to this node.

The iterator yields one path per leaf node.

The order of the leaves, and hence the corresponding paths, is determined by the generic Traverser parameter T.

See also

• paths_with: (i) to iterate using a cached traverser to minimize allocation for repeated traversals, or (ii) to iterate over nodes rather than only the data.

Yields

• Iterator::Item => impl Iterator<Item = &'a V::Item>

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]);

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]);

// paths from all leaves to the root

let root = tree.root();

// sorted in the order of leaves by breadth-first:
// 5, 8, 9, 10, 11
let paths: Vec<_> = root
    .paths::<Bfs>()
    .map(|x| x.copied().collect::<Vec<_>>())
    .collect();

assert_eq!(
    paths,
    [
        vec![5, 2, 1],
        vec![8, 4, 2, 1],
        vec![9, 6, 3, 1],
        vec![10, 7, 3, 1],
        vec![11, 7, 3, 1]
    ]
);

// paths from all leaves of subtree rooted at n3

let n3 = tree.node(&id3);

let paths: Vec<_> = n3
    .paths::<Dfs>()
    .map(|x| x.copied().collect::<Vec<_>>())
    .collect();

assert_eq!(paths, [vec![9, 6, 3], vec![10, 7, 3], vec![11, 7, 3]]);

fn paths_with<T, O>( &'a self, traverser: &'a mut T, ) -> impl Iterator<Item = impl Iterator<Item = <O as Over>::NodeItem<'a, V, M, P>>>

where O: Over<Enumeration = Val>, T: Traverser<O>,

Returns an iterator of paths from all leaves of the subtree rooted at this node upwards to this node.

The iterator yields one path per leaf node.

The order of the leaves, and hence the corresponding paths, is determined by explicit type of the Traverser argument traverser.

Yields

• Iterator::Item => impl Iterator<Item = &'a V::Item> when T: Traverser<OverData>
• Iterator::Item => impl Iterator<Item = Node<_>> when T: Traverser<OverNode>

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]);

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 a depth first traverser and reuse it

let mut dfs = Traversal.dfs(); // OverData by default

// paths from leaves as data of the nodes

let root = tree.root();
let paths: Vec<_> = root
    .paths_with(&mut dfs)
    .map(|path_data| path_data.copied().collect::<Vec<_>>())
    .collect();

assert_eq!(
    paths,
    [
        vec![8, 4, 2, 1],
        vec![5, 2, 1],
        vec![9, 6, 3, 1],
        vec![10, 7, 3, 1],
        vec![11, 7, 3, 1]
    ]
);

// paths of subtree rooted at n3; as nodes rather than data.

let mut dfs = dfs.over_nodes(); // transform from OverData to OverNode

let n3 = tree.node(&id3);

let paths: Vec<_> = n3
    .paths_with(&mut dfs)
    .map(|path_nodes| {
        path_nodes
            .map(|node| (*node.data(), node.depth()))
            .collect::<Vec<_>>()
    })
    .collect();

assert_eq!(
    paths,
    [
        [(9, 3), (6, 2), (3, 1)],
        [(10, 3), (7, 2), (3, 1)],
        [(11, 3), (7, 2), (3, 1)]
    ]
);

fn clone_as_tree<V2>(&'a self) -> Tree<V2, M, P>

where V2: TreeVariant<Item = V::Item> + 'a, P::PinnedVec<V2>: Default, V::Item: Clone,

Clone the subtree rooted at this node as a separate tree.

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, 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]);

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

// clone the subtree rooted at node 2 into another tree
// which might be a different tree type

let clone: BinaryTree<i32> = tree.node(&id2).clone_as_tree();

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

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

where T: Traverser<OverData>,

Returns an iterator of references to data of leaves of 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)

Note that leaves is a shorthand of a chain of iterator methods over the more general walk_with method. This is demonstrated in the example below.

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]);

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]);

// access the leaves in different orders that is determined by traversal

let root = tree.root();

let bfs_leaves: Vec<_> = root.leaves::<Bfs>().copied().collect();
assert_eq!(bfs_leaves, [5, 8, 9, 10, 11]);

let dfs_leaves: Vec<_> = root.leaves::<Dfs>().copied().collect();
assert_eq!(dfs_leaves, [8, 5, 9, 10, 11]);

// get the leaves from any node

let n3 = tree.node(&id3);
let leaves: Vec<_> = n3.leaves::<PostOrder>().copied().collect();
assert_eq!(leaves, [9, 10, 11]);

// ALTERNATIVELY: get the leaves with walk_with

let mut tr = Traversal.bfs().over_nodes(); // we need Node to filter leaves

let bfs_leaves: Vec<_> = root
    .walk_with(&mut tr)
    .filter(|x| x.is_leaf())
    .map(|x| *x.data())
    .collect();
assert_eq!(bfs_leaves, [5, 8, 9, 10, 11]);

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

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

Returns an iterator of leaves of 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)

Note that leaves is a shorthand of a chain of iterator methods over the more general walk_with method. This is demonstrated in the example below.

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]);

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]);

// access leaves with re-usable traverser

let mut bfs = Traversal.bfs();
assert_eq!(
    tree.root().leaves_with(&mut bfs).collect::<Vec<_>>(),
    [&5, &8, &9, &10, &11]
);
assert_eq!(
    tree.node(&id3).leaves_with(&mut bfs).collect::<Vec<_>>(),
    [&9, &10, &11]
);

// access leaf nodes instead of data

let mut dfs = Traversal.dfs().over_nodes();

let root = tree.root();
let mut leaves = root.leaves_with(&mut dfs);

let leaf: Node<_> = leaves.next().unwrap();
assert!(leaf.is_leaf());
assert_eq!(leaf.data(), &8);
assert_eq!(leaf.parent(), Some(tree.node(&id4)));

// add depth and/or sibling-idx to the iteration items

let mut dfs = Traversal.dfs().over_nodes().with_depth().with_sibling_idx();
let mut leaves = root.leaves_with(&mut dfs);
let (depth, sibling_idx, leaf) = leaves.next().unwrap();
assert_eq!(depth, 3);
assert_eq!(sibling_idx, 0);
assert_eq!(leaf.data(), &8);

fn indices<T>(&self) -> impl Iterator<Item = NodeIdx<V>>

where T: Traverser<OverData>, V: 'static,

Returns an iterator of node indices.

The order of the indices is determined by the generic Traverser parameter T.

See also

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 indices_with methods instead. This method additionally allow for yielding node depths and sibling indices in addition to node indices.

Examples

use orx_tree::*;

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

let mut a = DynTree::new(0);
let [a1, a2] = a.root_mut().push_children([1, 2]);
let [a3, _] = a.node_mut(&a1).push_children([3, 4]);
a.node_mut(&a3).push_child(7);
let [a5, a6] = a.node_mut(&a2).push_children([5, 6]);
a.node_mut(&a5).push_child(8);
a.node_mut(&a6).push_children([9, 10]);

// collect indices in breadth-first order

let a0 = a.root();
let bfs_indices: Vec<_> = a0.indices::<Bfs>().collect();

assert_eq!(a.node(&bfs_indices[0]).data(), &0);
assert_eq!(a.node(&bfs_indices[1]).data(), &1);
assert_eq!(a.node(&bfs_indices[2]).data(), &2);
assert_eq!(a.node(&bfs_indices[3]).data(), &3);

// collect indices in depth-first order
// we may also re-use a traverser

let mut t = Traversal.dfs();

let a0 = a.root();
let dfs_indices: Vec<_> = a0.indices_with(&mut t).collect();

assert_eq!(a.node(&dfs_indices[0]).data(), &0);
assert_eq!(a.node(&dfs_indices[1]).data(), &1);
assert_eq!(a.node(&dfs_indices[2]).data(), &3);
assert_eq!(a.node(&dfs_indices[3]).data(), &7);

fn indices_with<T, O>( &self, traverser: &mut T, ) -> impl Iterator<Item = <O::Enumeration as Enumeration>::Item<NodeIdx<V>>>

where O: Over, T: Traverser<O>, V: 'static, Self: Sized,

Returns an iterator of node indices.

The order of the indices is determined by the generic Traverser parameter T of the given traverser.

Depending on the traverser type, the iterator might yield:

• NodeIdx
• (depth, NodeIdx)
• (sibling_idx, NodeIdx)
• (depth, sibling_idx, NodeIdx)

See also

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 indices_with methods instead. This method additionally allow for yielding node depths and sibling indices in addition to node indices.

fn as_cloned_subtree(self) -> ClonedSubTree<'a, V, M, P, Self>

where V::Item: Clone, Self: Sized,

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 create the same subtree structure in the target tree with cloned values. This subtree and the tree it belongs to remain unchanged. Please see Append Subtree cloned-copied from another Tree section of the examples of these methods.

Otherwise, it has no impact on the tree.

fn as_copied_subtree(self) -> CopiedSubTree<'a, V, M, P, Self>

where V::Item: Copy, Self: Sized,

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 create the same subtree structure in the target tree with copied values. This subtree and the tree it belongs to remain unchanged. Please see Append Subtree cloned-copied from another Tree section of the examples of these methods.

Otherwise, it has no impact on the tree.

Dyn Compatibility

This trait is not dyn compatible.

In older versions of Rust, dyn compatibility was called "object safety", so this trait is not object safe.

Implementors

impl<'a, V, M, P, X> NodeRef<'a, V, M, P> for X

where V: TreeVariant + 'a, M: MemoryPolicy, P: PinnedStorage, X: NodeRefCore<'a, V, M, P>,