Struct Tree

pub struct Tree<V, M = Auto, P = SplitRecursive>(/* private fields */)
where
    V: TreeVariant,
    M: MemoryPolicy,
    P: PinnedStorage;

Core tree structure.

Implementations

impl<V, M, P> Tree<V, M, P>

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

pub fn memory_utilization(&self) -> Utilization

Returns current node utilization of the collection.

impl<V, P> Tree<V, Auto, P>

where V: TreeVariant, P: PinnedStorage,

pub fn into_lazy_reclaim(self) -> Tree<V, Lazy, P>

Transforms the tree’s memory reclaim policy from Auto to Lazy:

• Tree<V> => Tree<V, Lazy> // Auto can be omitted on since it is the default
• DynTree<u62> => DynTree<u32, Lazy>
• BinaryTree<u62> => BinaryTree<u32, Lazy>

This is free operation and does not require any allocation or copies.

impl<const D: usize, V, P> Tree<V, AutoWithThreshold<D>, P>

where V: TreeVariant, P: PinnedStorage,

pub fn into_lazy_reclaim(self) -> Tree<V, Lazy, P>

Transforms the tree’s memory reclaim policy from AutoWithThreshold to Lazy:

• Tree<V, AutoWithThreshold<3>> => Tree<V, Lazy>
• DynTree<u62, AutoWithThreshold<4>> => DynTree<u32, Lazy>
• BinaryTree<u62, AutoWithThreshold<1>> => BinaryTree<u32, Lazy>

This is free operation and does not require any allocation or copies.

impl<V, P> Tree<V, Lazy, P>

where V: TreeVariant, P: PinnedStorage,

pub fn into_auto_reclaim(self) -> Tree<V, Auto, P>

Transforms the tree’s memory reclaim policy from Lazy to Auto:

• Tree<V, Lazy> => Tree<V> // Auto can be omitted on since it is the default
• DynTree<u62, Lazy> => DynTree<u32>
• BinaryTree<u62, Lazy> => BinaryTree<u32>

This is free operation and does not require any allocation or copies.

pub fn into_auto_reclaim_with_threshold<const D: usize>( self, ) -> Tree<V, AutoWithThreshold<D>, P>

Transforms the tree’s memory reclaim policy from Lazy to AutoWithThreshold:

• Tree<V, Lazy> => Tree<V, AutoWithThreshold<3>>
• DynTree<u62, Lazy> => DynTree<u32, AutoWithThreshold<1>>
• BinaryTree<u62, Lazy> => BinaryTree<u32, AutoWithThreshold<4>>

This is free operation and does not require any allocation or copies.

impl<V> Tree<V, Auto, SplitRecursive>

where V: TreeVariant,

pub fn new(root_value: V::Item) -> Self

Creates a new tree including the root node with the given root_value.

Note that the following is the preferred constructor for non-empty trees

let tree = DynTree::new(42);

while it is equivalent and shorthand for the following:

let mut tree = DynTree::empty();
tree.push_root(42);

Examples

use orx_tree::*;

let tree = DynTree::new(42);

assert_eq!(tree.len(), 1);
assert_eq!(tree.root().data(), &42);

pub fn empty() -> Self

Creates an empty tree.

You may call push_root to instantiate the empty tree.

Examples

use orx_tree::*;

let tree = DynTree::<String>::empty();

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

impl<V, M, P> Tree<V, M, P>

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

pub fn len(&self) -> usize

O(1) Returns the number of nodes in the tree.

Examples

use orx_tree::*;

let mut tree: DynTree<i32> = DynTree::new(42);
assert_eq!(tree.len(), 1);

let mut root = tree.root_mut();
let [_, idx] = root.push_children([4, 2]);

assert_eq!(tree.len(), 3);

let mut node = tree.node_mut(&idx);
node.push_child(7);

assert_eq!(tree.len(), 4);

pub fn is_empty(&self) -> bool

Returns true if the tree is empty.

pub fn push_root(&mut self, root_value: V::Item) -> NodeIdx<V>

Pushes the root to the empty tree.

Panics

Panics if push_root is called when the tree is not empty.

Examples

use orx_tree::*;

let mut tree: DynTree<i32> = DynTree::empty();

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

tree.push_root(42);
assert!(!tree.is_empty());
assert_eq!(tree.len(), 1);
assert_eq!(tree.root().data(), &42);

pub fn clear(&mut self)

Removes all the nodes including the root of the tree.

Examples

use orx_tree::*;

let mut tree: BinaryTree<i32> = BinaryTree::new(42);

let mut root = tree.root_mut();
root.push_child(4);
let [idx] = root.push_children([2]);

let mut node = tree.node_mut(&idx);
node.push_child(7);

assert_eq!(tree.len(), 4);
assert_eq!(tree.root().data(), &42);

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

pub fn root(&self) -> Node<'_, V, M, P>

Returns the root node of the tree.

Panics

Panics if the tree is empty and has no root.

When not certain, you may use is_empty or get_root methods to have a safe access.

Examples

use orx_tree::*;

// initiate a rooted tree
let mut tree = DynTree::<_>::new('a');
assert_eq!(tree.root().data(), &'a');

tree.clear();
// assert_eq!(tree.get_root().data(), 'x'); // panics!

// initiate an empty tree
let mut tree = BinaryTree::<_>::empty();
// assert_eq!(tree.get_root().data(), 'x'); // panics!

tree.push_root('a');
assert_eq!(tree.root().data(), &'a');

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

Returns the mutable root node of the tree.

Panics

Panics if the tree is empty and has no root.

When not certain, you may use is_empty or get_root_mut methods to have a safe access.

Examples

use orx_tree::*;

// initiate a rooted tree
let mut tree = DynTree::<_>::new('a');
*tree.root_mut().data_mut() = 'x';
assert_eq!(tree.root().data(), &'x');

tree.clear();
// *tree.root_mut().data_mut() = 'x'; // panics!

// initiate an empty tree
let mut tree = BinaryTree::<_>::empty();
// *tree.root_mut().data_mut() = 'x'; // panics!

tree.push_root('a');

// build the tree from the root
let mut root = tree.root_mut();
assert_eq!(root.data(), &'a');

let [b, c] = root.push_children(['b', 'c']);
tree.node_mut(&b).push_child('d');
tree.node_mut(&c).push_children(['e', 'f']);

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

Returns the root node of the tree; None if the tree is empty.

Examples

use orx_tree::*;

// initiate a rooted tree
let mut tree = DynTree::<_>::new('a');
assert_eq!(tree.root().data(), &'a');

tree.clear();
assert_eq!(tree.get_root(), None);

// initiate an empty tree
let mut tree = BinaryTree::<_>::empty();
assert_eq!(tree.get_root(), None);

tree.push_root('a');
assert_eq!(tree.root().data(), &'a');

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

Returns the root as a mutable node of the tree; None if the tree is empty.

Examples

use orx_tree::*;

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

let mut root = tree.root_mut();

assert_eq!(root.data(), &'a');
*root.data_mut() = 'x';
assert_eq!(root.data(), &'x');

root.push_child('b');
let idx = root.push_child('c');

tree.clear();
assert_eq!(tree.get_root_mut(), None);

pub fn is_node_idx_valid(&self, node_idx: &NodeIdx<V>) -> bool

Returns true if the node_idx is valid for this tree.

Returns false if any of the following holds:

• the node index is created from a different tree => NodeIdxError::OutOfBounds
• the node that this index is created for is removed from the tree => NodeIdxError::RemovedNode
• the tree is using Auto memory reclaim policy and nodes are reorganized due to node removals => NodeIdxError::ReorganizedCollection

Please see NodeIdx documentation for details on the validity of node indices.

• If is_node_idx_valid is true, then node_idx_error is None;
• If is_node_idx_valid is false, then node_idx_error is Some.

pub fn node_idx_error(&self, node_idx: &NodeIdx<V>) -> Option<NodeIdxError>

Returns the node index error if the node_idx is invalid. Returns None if the index is valid for this tree.

Returns Some if any of the following holds:

• the node index is created from a different tree => NodeIdxError::OutOfBounds

• the node that this index is created for is removed from the tree => NodeIdxError::RemovedNode

• the tree is using Auto memory reclaim policy and nodes are reorganized due to node removals => NodeIdxError::ReorganizedCollection

• If is_node_idx_valid is true, then node_idx_error is None;

• If is_node_idx_valid is false, then node_idx_error is Some.

pub fn node(&self, node_idx: &NodeIdx<V>) -> Node<'_, V, M, P>

Returns the node with the given node_idx.

Panics

Panics if this node index is not valid for the given tree; i.e., when either of the following holds:

• the node index is created from a different tree => NodeIdxError::OutOfBounds
• the node that this index is created for is removed from the tree => NodeIdxError::RemovedNode
• the tree is using Auto memory reclaim policy and nodes are reorganized due to node removals => NodeIdxError::ReorganizedCollection

When not certain, you may use is_node_idx_valid or get_node methods to have a safe access.

Please see NodeIdx documentation for details on the validity of node indices.

Examples

use orx_tree::*;

//      1
//     ╱ ╲
//    ╱   ╲
//   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 n2 = tree.node(&id2);
assert_eq!(n2.data(), &2);

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

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

pub fn node_mut(&mut self, node_idx: &NodeIdx<V>) -> NodeMut<'_, V, M, P>

Returns the mutable node with the given node_idx.

Panics

Panics if this node index is not valid for the given tree; i.e., when either of the following holds:

• the node index is created from a different tree => NodeIdxError::OutOfBounds
• the node that this index is created for is removed from the tree => NodeIdxError::RemovedNode
• the tree is using Auto memory reclaim policy and nodes are reorganized due to node removals => NodeIdxError::ReorganizedCollection

When not certain, you may use is_node_idx_valid or get_node_mut methods to have a safe access.

Please see NodeIdx documentation for details on the validity of node indices.

Examples

use orx_tree::*;

//      1
//     ╱ ╲
//    ╱   ╲
//   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 n2 = tree.node(&id2);
assert_eq!(n2.data(), &2);

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

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

pub fn get_node(&self, node_idx: &NodeIdx<V>) -> Option<Node<'_, V, M, P>>

Returns the node with the given node_idx; returns None if the node index is invalid.

The node index is invalid if any of the following holds:

• the node index is created from a different tree => NodeIdxError::OutOfBounds
• the node that this index is created for is removed from the tree => NodeIdxError::RemovedNode
• the tree is using Auto memory reclaim policy and nodes are reorganized due to node removals => NodeIdxError::ReorganizedCollection

You may use try_node method to get the underlying reason when the index is invalid.

Please see NodeIdx documentation for details on the validity of node indices.

pub fn get_node_mut( &mut self, node_idx: &NodeIdx<V>, ) -> Option<NodeMut<'_, V, M, P>>

Returns the mutable node with the given node_idx; returns None if the node index is invalid.

The node index is invalid if any of the following holds:

• the node index is created from a different tree => NodeIdxError::OutOfBounds
• the node that this index is created for is removed from the tree => NodeIdxError::RemovedNode
• the tree is using Auto memory reclaim policy and nodes are reorganized due to node removals => NodeIdxError::ReorganizedCollection

You may use try_node_mut method to get the underlying reason when the index is invalid.

Please see NodeIdx documentation for details on the validity of node indices.

pub fn try_node( &self, node_idx: &NodeIdx<V>, ) -> Result<Node<'_, V, M, P>, NodeIdxError>

Returns the node with the given node_idx; returns the corresponding error if the node index is invalid.

The node index is invalid if any of the following holds:

• the node index is created from a different tree => NodeIdxError::OutOfBounds
• the node that this index is created for is removed from the tree => NodeIdxError::RemovedNode
• the tree is using Auto memory reclaim policy and nodes are reorganized due to node removals => NodeIdxError::ReorganizedCollection

Please see NodeIdx documentation for details on the validity of node indices.

pub fn try_node_mut( &mut self, node_idx: &NodeIdx<V>, ) -> Result<NodeMut<'_, V, M, P>, NodeIdxError>

Returns the node with the given node_idx; returns the corresponding error if the node index is invalid.

The node index is invalid if any of the following holds:

• the node index is created from a different tree => NodeIdxError::OutOfBounds
• the node that this index is created for is removed from the tree => NodeIdxError::RemovedNode
• the tree is using Auto memory reclaim policy and nodes are reorganized due to node removals => NodeIdxError::ReorganizedCollection

Please see NodeIdx documentation for details on the validity of node indices.

pub unsafe fn node_unchecked(&self, node_idx: &NodeIdx<V>) -> Node<'_, V, M, P>

Returns the node with the given node_idx.

Safety

It omits the index validity assertions that node method performs; hence it is only safe to use this method when we are certain that ‘is_node_idx_valid’ would have returned true.

pub unsafe fn node_mut_unchecked( &mut self, node_idx: &NodeIdx<V>, ) -> NodeMut<'_, V, M, P>

Returns the mutable node with the given node_idx.

Safety

It omits the index validity assertions that node_mut method performs; hence it is only safe to use this method when we are certain that ‘is_node_idx_valid’ would have returned true.

pub fn swap_subtrees(&mut self, first_idx: &NodeIdx<V>, second_idx: &NodeIdx<V>)

O(1) Tries to swap the nodes together with their subtrees rooted at the given first_idx and second_idx in constant time (*).

The indices remain valid.

In order to have a valid swap operation, the two subtrees must be independent of each other without any shared node. Necessary and sufficient condition is then as follows:

• node with the first_idx is not an ancestor of the node with the second_idx,
• and vice versa.

Swap operation will succeed if both indices are valid and the above condition holds. Panics …

Panics

• Panics if either of the node indices is invalid.
• Panics if node with the first_idx is an ancestor of the node with the second_idx; or vice versa.

See also

(*) Validation of the independence of the subtrees is performed in O(D) time where D is the maximum depth of the tree. When we are certain that the subtrees do not intersect, we can use the unsafe variant swap_subtrees_unchecked to bypass the validation.

See also:

• swap_data_with
• swap_subtrees
• try_swap_nodes
• swap_subtrees_unchecked

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

// we can swap n2 & n7
//      1
//     ╱ ╲
//    ╱   ╲
//   7     3
//  ╱ ╲   ╱ ╲
// 10 11 6   2
//       |  ╱ ╲
//       9 4   5
//         |
//         8

tree.swap_subtrees(&id2, &id7);

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

pub fn try_swap_nodes( &mut self, first_idx: &NodeIdx<V>, second_idx: &NodeIdx<V>, ) -> Result<(), NodeSwapError>

O(1) Tries to swap the nodes together with their subtrees rooted at the given first_idx and second_idx in constant time (*). Returns the error if the swap operation is invalid.

The indices remain valid.

In order to have a valid swap operation, the two subtrees must be independent of each other without any shared node. Necessary and sufficient condition is then as follows:

• node with the first_idx is not an ancestor of the node with the second_idx,
• and vice versa.

Swap operation will succeed and return Ok if both indices are valid and the above condition holds. It will the corresponding NodeSwapError otherwise.

See also

(*) Validation of the independence of the subtrees is performed in O(D) time where D is the maximum depth of the tree. When we are certain that the subtrees do not intersect, we can use the unsafe variant swap_subtrees_unchecked to bypass the validation.

See also:

• swap_data_with
• swap_subtrees
• try_swap_nodes
• swap_subtrees_unchecked

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 id1 = root.idx();
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]);

// cannot swap n3 & n10

assert_eq!(
    tree.try_swap_nodes(&id3, &id10),
    Err(NodeSwapError::FirstNodeIsAncestorOfSecond)
);

// cannot swap n4 & n1 (root)

assert_eq!(
    tree.try_swap_nodes(&id4, &id1),
    Err(NodeSwapError::SecondNodeIsAncestorOfFirst)
);

// we can swap n2 & n7
//      1
//     ╱ ╲
//    ╱   ╲
//   7     3
//  ╱ ╲   ╱ ╲
// 10 11 6   2
//       |  ╱ ╲
//       9 4   5
//         |
//         8

let result = tree.try_swap_nodes(&id2, &id7);
assert_eq!(result, Ok(()));

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

pub unsafe fn swap_subtrees_unchecked( &mut self, first_idx: &NodeIdx<V>, second_idx: &NodeIdx<V>, )

O(1) Swaps the nodes together with their subtrees rooted at the given first_idx and second_idx.

The indices remain valid.

In order to have a valid swap operation, the two subtrees must be independent of each other without any shared node. Necessary and sufficient condition is then as follows:

• node with the first_idx is not an ancestor of the node with the second_idx,
• and vice versa.

Panics

Panics if either of the node indices is invalid.

Safety

It is safe to use this method only when the swap operation is valid; i.e., abovementioned independence condition of the subtrees holds.

See also

• swap_data_with
• swap_subtrees
• try_swap_nodes
• swap_subtrees_unchecked

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

// we can swap n2 & n5
//      1
//     ╱ ╲
//    ╱   ╲
//   7     3
//  ╱ ╲   ╱ ╲
// 10 11 6   2
//       |  ╱ ╲
//       9 4   5
//         |
//         8

unsafe { tree.swap_subtrees_unchecked(&id2, &id7) };

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

pub fn par(&self) -> impl ParIter<Item = &V::Item>

where V::Item: Send + Sync, for<'a> &'a <P as PinnedStorage>::PinnedVec<V>: IntoConcurrentIter<Item = &'a Node<V>>,

Creates a parallel iterator over references to the elements of the tree in arbitrary order.

Note that par is parallel counterpart of iter.

In order to iterate over data in a particular order, please use traversers with walk, walk_mut or into_walk methods.

Please see ParIter for details of the parallel computation. In brief, computation is defined as chain of iterator transformations and parallelization is handled by the underlying parallel executor.

Requires orx-parallel feature.

Examples

use orx_tree::*;

let num_children = 4;
let total_depth = 10;

let mut tree = DynTree::new(0.to_string());
let mut dfs = Traversal.dfs().over_nodes();

for _ in 0..total_depth {
    let root = tree.root();
    let leaves: Vec<_> = root.leaves_with(&mut dfs).map(|x| x.idx()).collect();
    for idx in leaves {
        let count = tree.len();
        let mut node = tree.node_mut(&idx);
        for j in 0..num_children {
            node.push_child((count + j).to_string());
        }
    }
}

let seq_result: usize = tree
    .iter()
    .filter_map(|x| x.parse::<usize>().ok())
    .filter(|x| x % 2 == 0)
    .sum();

// compute in parallel with default configuration
let par_result = tree
    .par() // replace iter() with par()
    .filter_map(|x| x.parse::<usize>().ok())
    .filter(|x| x % 2 == 0)
    .sum();
assert_eq!(seq_result, par_result);

// configure parallel computation
let par_result = tree
    .par()
    .num_threads(4)
    .chunk_size(64)
    .filter_map(|x| x.parse::<usize>().ok())
    .filter(|x| x % 2 == 0)
    .sum();
assert_eq!(seq_result, par_result);

pub fn into_par(self) -> impl ParIter<Item = V::Item>

where V::Item: Send + Sync + Clone, <P as PinnedStorage>::PinnedVec<V>: IntoConcurrentIter<Item = Node<V>>,

Consumes the tree and creates a parallel iterator over owned elements of the tree in arbitrary order.

Note that into_par is parallel counterpart of into_iter.

In order to iterate over data in a particular order, please use traversers with walk, walk_mut or into_walk methods.

Please see ParIter for details of the parallel computation. In brief, computation is defined as chain of iterator transformations and parallelization is handled by the underlying parallel executor.

Requires orx-parallel feature.

Examples

use orx_tree::*;

let num_children = 4;
let total_depth = 10;

let mut tree = DynTree::new(0.to_string());
let mut dfs = Traversal.dfs().over_nodes();

for _ in 0..total_depth {
    let root = tree.root();
    let leaves: Vec<_> = root.leaves_with(&mut dfs).map(|x| x.idx()).collect();
    for idx in leaves {
        let count = tree.len();
        let mut node = tree.node_mut(&idx);
        for j in 0..num_children {
            node.push_child((count + j).to_string());
        }
    }
}

let seq_result: usize = tree
    .clone()
    .into_iter()
    .filter_map(|x| x.parse::<usize>().ok())
    .filter(|x| x % 2 == 0)
    .sum();

// compute in parallel with default configuration
let par_result = tree
    .clone()
    .into_par() // replace into_iter() with into_par()
    .filter_map(|x| x.parse::<usize>().ok())
    .filter(|x| x % 2 == 0)
    .sum();
assert_eq!(seq_result, par_result);

// configure parallel computation
let par_result = tree
    .into_par()
    .num_threads(4)
    .chunk_size(64)
    .filter_map(|x| x.parse::<usize>().ok())
    .filter(|x| x % 2 == 0)
    .sum();
assert_eq!(seq_result, par_result);

Trait Implementations

impl<V, M, P> Clone for Tree<V, M, P>

where V: TreeVariant, M: MemoryPolicy, P: PinnedStorage, P::PinnedVec<V>: Default, V::Item: Clone,

fn clone(&self) -> Self

Clones the tree.

See also

• clone_as_tree: to clone a subtree rooted at a given 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 entire tree

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

// indices are valid only for their trees

let indices: Vec<_> = clone.root().indices::<Bfs>().collect();

assert_eq!(tree.get_node(&indices[2]), None);
assert_eq!(tree.try_node(&indices[2]), Err(NodeIdxError::OutOfBounds));

assert_eq!(clone.get_node(&id2), None);
assert_eq!(clone.try_node(&id2), Err(NodeIdxError::OutOfBounds));

assert_eq!(clone.node(&indices[2]).data(), &2);

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<V, M, P> Debug for Tree<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> Default for Tree<V, M, P>

where V: TreeVariant, M: MemoryPolicy, P: PinnedStorage, P::PinnedVec<V>: Default,

fn default() -> Self

Returns the “default value” for a type.

impl<V, M, P> Display for Tree<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> IntoIterator for &'a Tree<V, M, P>

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

fn into_iter(self) -> Self::IntoIter

Creates an iterator over references to the data of the nodes of the tree in a deterministic but an arbitrary order.

In order to iterate over the values the tree nodes in a particular order, you may use walk method on the root of the tree (or on any subtree) with the desired traverser.

Examples

use orx_tree::*;

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

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

// iterate over the tree in an arbitrary order

let values: Vec<_> = (&tree).into_iter().copied().collect();
assert_eq!(values, [0, 1, 2, 3, 4, 7, 5, 6]);

// since Tree auto-implements orx_iterable::Collection
let values: Vec<_> = tree.iter().copied().collect();
assert_eq!(values, [0, 1, 2, 3, 4, 7, 5, 6]);

type Item = &'a <V as Variant>::Item

The type of the elements being iterated over.

type IntoIter = TreeIter<'a, V, <<<P as PinnedStorage>::PinnedVec<V> as Collection>::Iterable<'a> as Iterable>::Iter>

Which kind of iterator are we turning this into?

impl<'a, V, M, P> IntoIterator for &'a mut Tree<V, M, P>

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

fn into_iter(self) -> Self::IntoIter

Creates a mutable iterator over references to the data of the nodes of the tree in a deterministic but an arbitrary order.

In order to iterate over the values the tree nodes in a particular order, you may use walk_mut method on the root of the tree (or on any subtree) with the desired traverser.

Examples

use orx_tree::*;

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

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

// mutably iterate over the tree in an arbitrary order

for x in (&mut tree).into_iter() {
    *x += 5;
}

// since Tree auto-implements orx_iterable::CollectionMut

for x in tree.iter_mut() {
    *x += 5;
}

// validate

let values: Vec<_> = tree.root().walk::<Bfs>().copied().collect();
assert_eq!(values, [10, 11, 12, 13, 14, 15, 16, 17]);

type Item = &'a mut <V as Variant>::Item

The type of the elements being iterated over.

type IntoIter = TreeIterMut<'a, V, <<P as PinnedStorage>::PinnedVec<V> as CollectionMut>::IterMut<'a>>

Which kind of iterator are we turning this into?

impl<V, M, P> IntoIterator for Tree<V, M, P>

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

fn into_iter(self) -> Self::IntoIter

Consumes the tree and creates an iterator over the data of the nodes of the tree in a deterministic but an arbitrary order.

In order to take the values out of the tree in a particular order, you may use into_walk method on the root of the tree (or on any subtree) with the desired traverser.

Examples

use orx_tree::*;

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

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

// transform the tree into an arbitrary order iterator

let values: Vec<_> = tree.into_iter().collect();
assert_eq!(values, [0, 1, 2, 3, 4, 7, 5, 6]);

type Item = <V as Variant>::Item

The type of the elements being iterated over.

type IntoIter = TreeIntoIter<V, <<P as PinnedStorage>::PinnedVec<V> as IntoIterator>::IntoIter>

Which kind of iterator are we turning this into?

impl<V1, M1, P1, V2, M2, P2> PartialEq<Tree<V1, M1, P1>> for Tree<V2, M2, P2>

where V1: TreeVariant, M1: MemoryPolicy, P1: PinnedStorage, V2: TreeVariant<Item = V1::Item>, M2: MemoryPolicy, P2: PinnedStorage, V1::Item: PartialEq,

fn eq(&self, other: &Tree<V1, M1, P1>) -> 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<I, V, M, P> TryFrom<DepthFirstSequence<<V as Variant>::Item, I>> for Tree<V, M, P>

where V: TreeVariant, M: MemoryPolicy, P: PinnedStorage, P::PinnedVec<V>: Default, I: IntoIterator<Item = (usize, V::Item)>,

fn try_from(value: DepthFirstSequence<V::Item, I>) -> Result<Self, Self::Error>

Tries to convert a depth-first sequence into a valid tree. Returns the corresponding DepthFirstSequenceError if the sequence is invalid.

Note that:

• A DepthFirstSequence is just a wrapper of any IntoIterator<Item = (usize, T)> implementor that can be crated using the From trait => DepthFirstSequence::from([(0, "a"), (1, "b")]).
• However, not all IntoIterator<Item = (usize, T)> instances represent a valid depth first sequence. Therefore, the conversion is fallible.

type Error = DepthFirstSequenceError

The type returned in the event of a conversion error.