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

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<'de, V, M, P> Deserialize<'de> for Tree<V, M, P>

where V: TreeVariant, M: MemoryPolicy, P: PinnedStorage, P::PinnedVec<V>: Default, V::Item: Deserialize<'de>,

fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>

where D: Deserializer<'de>,

Deserializes the tree from linearized DepthFirstSequence.

Examples

use orx_tree::*;

let json = "[]";
let result: Result<DaryTree<4, i32>, _> = serde_json::from_str(json);
let tree = result.unwrap();
assert!(tree.is_empty());

let json = "[[0,10]]";
let result: Result<DynTree<i32>, _> = serde_json::from_str(json);
let tree = result.unwrap();
assert_eq!(tree.len(), 1);
assert_eq!(tree.root().data(), &10);

//      0
//     ╱ ╲
//    ╱   ╲
//   1     2
//  ╱     ╱ ╲
// 3     4   5
// |         |
// 6         7
let json = "[[0, 0], [1, 1], [2, 3], [3, 6], [1, 2], [2, 4], [2, 5], [3, 7]]";
let result: Result<BinaryTree<i32>, _> = serde_json::from_str(json);
let tree = result.unwrap();
let bfs_values: Vec<_> = tree.root().walk::<Bfs>().copied().collect();
assert_eq!(bfs_values, [0, 1, 2, 3, 4, 5, 6, 7]);

// errors

// A. First element of DepthFirstSequence (root of the tree) must have depth 0;
// however, received a depth of 1.
let json = "[[1,10]]";
let result: Result<DynTree<i32>, _> = serde_json::from_str(json);
assert!(result.is_err());

// B. Let d1 and d2 be two consecutive depths in the depth-first sequence.
// Then, (i) d2=d1+1, (ii) d2=d1 or (iii) d2<d1 are valid cases.
// However, received the invalid case where d2>d1+1 (d1=1, d2=3).
let json = "[[0, 0], [1, 1], [3, 6], [1, 2], [2, 4], [2, 5], [3, 7]]";
let result: Result<BinaryTree<i32>, _> = serde_json::from_str(json);
assert!(result.is_err());

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 PinnedVec<Node<V>>>::Iter<'a>>

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 PinnedVec<Node<V>>>::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<V, M, P> Serialize for Tree<V, M, P>

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

fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>

where S: Serializer,

Serializes the tree into linearized DepthFirstSequence.

Examples

use orx_tree::*;

let tree = BinaryTree::<i32>::empty();
let json = serde_json::to_string(&tree).unwrap();
assert_eq!(json, "[]");

let tree = DynTree::new(10);
let json = serde_json::to_string(&tree).unwrap();
assert_eq!(json, "[[0,10]]");

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

let json = serde_json::to_string(&tree).unwrap();
assert_eq!(json, "[[0,0],[1,1],[2,3],[3,6],[1,2],[2,4],[2,5],[3,7]]");

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.