Struct NodeIdx

pub struct NodeIdx<V: TreeVariant>(/* private fields */);

An index associated only with the node it is created for.

• Similar to usize for an array, a NodeIdx provides direct constant time access to the node it is created for. Therefore, node indices are crucial for efficiency of certain programs.
• Unlike usize for an array, a NodeIdx is specific which provides additional safety features.
  • A node index is specific to only one node that it is created for, it can never return another node.
  • If we create a node index from one tree and use it on another tree, we get an error (OutOfBounds).
  • If we create a node index for a node, then we remove this node from the tree, and then we use the index, we get an error (RemovedNode).
  • If we create a node index for a node, then the nodes of the tree are reorganized to reclaim memory, we get an error (ReorganizedCollection) when we try to use the node index. This error is due to an implicit operation which is undesirable. However, we can conveniently avoid such errors using Auto and Lazy memory reclaim policies together. Please see the notes and examples in the MemoryPolicy.

Collecting Node Indices

There are three ways to get the index of a node.

1. During Growth

We can add child nodes by push_child, push_children and extend_children methods. These methods return the indices of the created nodes.

Similarly, horizontal growth methods push_sibling, push_siblings and extend_siblings also return the indices of new nodes.

adding a single child: push_child

use orx_tree::*;

//      1
//     ╱ ╲
//    ╱   ╲
//   2     3

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

let mut root = tree.root_mut();

let id2 = root.push_child(2);
let id3 = root.push_child(3);

// use id3 to directly access node 3
let n3 = tree.node(&id3);
assert_eq!(n3.data(), &3);

adding a constant number of children: push_children

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

adding a variable number of children: extend_children

use orx_tree::*;

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

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

let mut root = tree.root_mut();

// indices are collected into a vec
let indices: Vec<_> = root.extend_children(2..6).collect();

let id5 = &indices[3];
let n5 = tree.node(&id5);
assert_eq!(n5.data(), &5);

2. From the Node

A node index can be obtained from the node itself using the idx method. There are different ways to access the nodes:

• we can traverse the tree ourselves using child and parent methods,
• or we can traverse the tree OverNode.

use orx_tree::*;

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

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

let mut root = tree.root_mut();

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

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

// task: access node 5 and get its index
let root = tree.root();
let n2 = root.child(0);
let n5 = n2.child(1);
let id5 = n5.idx();

// now we can use idx5 to directly access node 5
let n5 = tree.node(&id5);
assert_eq!(n5.data(), &5);
assert_eq!(n5.parent(), Some(tree.node(&id2)));

Since we can traverse the node in various ways and access the nodes in various orders, we can also collect the indices in desired order.

use orx_tree::*;

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

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

let mut root = tree.root_mut();

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

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

// task: collect all indices in breadth first order
let mut bfs = Bfs::default().over_nodes();
let root = tree.root();
let indices: Vec<_> = root.walk_with(&mut bfs).map(|x| x.idx()).collect();

// or we can use the shorthand:
let indices: Vec<_> = root.indices::<Bfs>().collect();

// now we can use indices to directly access nodes
let id5 = &indices[4];
let n5 = tree.node(&id5);
assert_eq!(n5.data(), &5);
assert_eq!(n5.parent(), Some(tree.node(&id2)));

Validity of Node Indices

At the time it is created, the node index:

• is valid for the tree the node belongs to,
• is invalid for any other tree:
  • idx.is_valid_for(&other_tree) => false
  • idx.node(&other_tree) => panics!!!
  • idx.get_node(&other_tree) => None
  • idx.try_get_node(&other_tree) => Err(OutOfBounds)

However, it might later become invalid for the original tree due to two reasons.

The first reason is explicit. If the node is removed from the tree, directly or due to removal of any of its ancestors, the corresponding index becomes invalid:

• idx.is_valid_for(&correct_tree) => false
• idx.node(&correct_tree) => panics!!!
• idx.get_node(&correct_tree) => None
• idx.try_get_node(&correct_tree) => Err(RemovedNode)

The second reason is implicit and closely related to MemoryPolicy. If removals from the tree triggers a memory reclaim operation which reorganizes the nodes of the tree, all indices cached prior to the reorganization becomes invalid:

• idx.is_valid_for(&correct_tree) => false
• idx.node(&correct_tree) => panics!!!
• idx.get_node(&correct_tree) => None
• idx.try_get_node(&correct_tree) => Err(ReorganizedCollection)

The implicit invalidation is not desirable and can be avoided by using memory policies, please see the MemoryPolicy documentation and examples. In brief:

• Lazy policy never leads to implicit invalidation.
• Growth methods never lead to implicit invalidation.
• We can only experience implicit invalidation when we are using Auto (or auto with threshold) memory policy and remove nodes from the tree.

Implementations

impl<V: TreeVariant> NodeIdx<V>

pub fn into_subtree_within(&self) -> MovedSubTreeWithin<V>

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_within or push_sibling_tree_within will remove the subtree from its current position to the target position of the same tree.

Otherwise, it has no impact on the tree.

pub fn as_cloned_subtree_within(&self) -> ClonedSubTreeWithin<V>

where V::Item: Clone,

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_within or push_sibling_tree_within will create the same subtree structure in the target position with cloned values. This subtree remains unchanged.

pub fn as_copied_subtree_within(&self) -> CopiedSubTreeWithin<V>

where V::Item: Copy,

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_within or push_sibling_tree_within will create the same subtree structure in the target position with copied values. This subtree remains unchanged.

Trait Implementations

impl<V: TreeVariant> Clone for NodeIdx<V>

fn clone(&self) -> Self

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<V: TreeVariant> Debug for NodeIdx<V>

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

Formats the value using the given formatter.

impl<V: TreeVariant> PartialEq for NodeIdx<V>

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

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

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

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