Struct Tree

pub struct Tree<T> { /* private fields */ }

A tree structure containing multiple nodes of generic type T.

Each node in the tree is indexed by its position in the internal vector. The tree supports operations for adding, accessing, and traversing nodes.

Example

use easy_tree::Tree;

let mut tree = Tree::new();
let root = tree.add_node("root");
let child = tree.add_child(root, "child");

Implementations

impl<T> Tree<T>

pub fn new() -> Self

Creates a new, empty tree.

Returns

A Tree instance with no nodes.

Example

use easy_tree::Tree;

let tree: Tree<i32> = Tree::new();

Examples found in repository

examples/basic.rs (line 4)

fn main() {
    let mut tree = Tree::new();
    let root = tree.add_node("root");
    let child = tree.add_child(root, "child");
    let grandchild = tree.add_child(child, "grandchild");

    assert_eq!(tree.get(root), Some(&"root"));
    assert_eq!(tree.get(grandchild), Some(&"grandchild"));
}

examples/traversal.rs (line 4)

fn main() {
    let mut tree = Tree::new();
    let root = tree.add_node("root");
    let child1 = tree.add_child(root, "child1");
    let _grandchild1 = tree.add_child(child1, "grandchild1");
    let _child2 = tree.add_child(root, "child2");

    let mut log = vec![];
    tree.traverse(
        |idx, data, log| log.push(format!("Visiting node {}: {}", idx, data)),
        |idx, data, log| log.push(format!("Finished node {}: {}", idx, data)),
        &mut log,
    );

    println!("{:?}", log);
}

pub fn add_node(&mut self, data: T) -> usize

Adds a new node to the tree.

This method is typically used to add a root node or a disconnected node.

Parameters

• data: The data to associate with the new node.

Returns

The index of the newly added node.

Example

use easy_tree::Tree;

let mut tree = Tree::new();
let root = tree.add_node("root");

Examples found in repository

examples/basic.rs (line 5)

fn main() {
    let mut tree = Tree::new();
    let root = tree.add_node("root");
    let child = tree.add_child(root, "child");
    let grandchild = tree.add_child(child, "grandchild");

    assert_eq!(tree.get(root), Some(&"root"));
    assert_eq!(tree.get(grandchild), Some(&"grandchild"));
}

examples/traversal.rs (line 5)

fn main() {
    let mut tree = Tree::new();
    let root = tree.add_node("root");
    let child1 = tree.add_child(root, "child1");
    let _grandchild1 = tree.add_child(child1, "grandchild1");
    let _child2 = tree.add_child(root, "child2");

    let mut log = vec![];
    tree.traverse(
        |idx, data, log| log.push(format!("Visiting node {}: {}", idx, data)),
        |idx, data, log| log.push(format!("Finished node {}: {}", idx, data)),
        &mut log,
    );

    println!("{:?}", log);
}

pub fn add_child(&mut self, parent: usize, data: T) -> usize

Adds a child node to an existing node in the tree.

Parameters

• parent: The index of the parent node.
• data: The data to associate with the new child node.

Returns

The index of the newly added child node.

Example

use easy_tree::Tree;

let mut tree = Tree::new();
let root = tree.add_node("root");
let child = tree.add_child(root, "child");

Examples found in repository

examples/basic.rs (line 6)

fn main() {
    let mut tree = Tree::new();
    let root = tree.add_node("root");
    let child = tree.add_child(root, "child");
    let grandchild = tree.add_child(child, "grandchild");

    assert_eq!(tree.get(root), Some(&"root"));
    assert_eq!(tree.get(grandchild), Some(&"grandchild"));
}

examples/traversal.rs (line 6)

fn main() {
    let mut tree = Tree::new();
    let root = tree.add_node("root");
    let child1 = tree.add_child(root, "child1");
    let _grandchild1 = tree.add_child(child1, "grandchild1");
    let _child2 = tree.add_child(root, "child2");

    let mut log = vec![];
    tree.traverse(
        |idx, data, log| log.push(format!("Visiting node {}: {}", idx, data)),
        |idx, data, log| log.push(format!("Finished node {}: {}", idx, data)),
        &mut log,
    );

    println!("{:?}", log);
}

pub fn add_child_to_root(&mut self, data: T) -> usize

Adds a child node to the tree root.

Parameters

• data: The data to associate with the new child node.

Returns

The index of the newly added child node.

Example

use easy_tree::Tree;

let mut tree = Tree::new();
let root = tree.add_node("root");
let child = tree.add_child_to_root("child");

pub fn get(&self, index: usize) -> Option<&T>

Retrieves a reference to the data stored in a node.

Parameters

• index: The index of the node to access.

Returns

Some(&T) if the node exists, or None if the index is out of bounds.

Example

use easy_tree::Tree;

let mut tree = Tree::new();
let root = tree.add_node(42);
assert_eq!(tree.get(root), Some(&42));

Examples found in repository

examples/basic.rs (line 9)

fn main() {
    let mut tree = Tree::new();
    let root = tree.add_node("root");
    let child = tree.add_child(root, "child");
    let grandchild = tree.add_child(child, "grandchild");

    assert_eq!(tree.get(root), Some(&"root"));
    assert_eq!(tree.get(grandchild), Some(&"grandchild"));
}

pub fn get_unchecked(&self, index: usize) -> &T

Retrieves a reference to the data stored in a node without bounds checking.

This method is faster than Tree::get because it does not perform any bounds checking. However, it is unsafe to use if the provided index is out of bounds or invalid.

Parameters

• index: The index of the node to access.

Returns

A reference to the data stored in the node.

Safety

Ensure that:

• The index is within the valid range of node indices in the tree (0 to Tree::len() - 1).
• The node at the given index exists and has not been removed (if applicable).

Example

use easy_tree::Tree;

let mut tree = Tree::new();
let root = tree.add_node(42);

// Safe use: The index is valid.
assert_eq!(tree.get_unchecked(root), &42);

// Unsafe use: Accessing an invalid index would cause undefined behavior.
// let invalid = tree.get_unchecked(999); // Avoid this!

pub fn get_mut(&mut self, index: usize) -> Option<&mut T>

Retrieves a mutable reference to the data stored in a node.

Parameters

• index: The index of the node to access.

Returns

Some(&mut T) if the node exists, or None if the index is out of bounds.

Example

use easy_tree::Tree;

let mut tree = Tree::new();
let root = tree.add_node(42);
*tree.get_mut(root).unwrap() = 43;
assert_eq!(tree.get(root), Some(&43));

pub fn get_unchecked_mut(&mut self, index: usize) -> &mut T

Retrieves a mutable reference to the data stored in a node without bounds checking.

This method is faster than Tree::get_mut because it does not perform any bounds checking. However, it is unsafe to use if the provided index is out of bounds or invalid.

Parameters

• index: The index of the node to access.

Returns

A mutable reference to the data stored in the node.

Safety

Ensure that:

• The index is within the valid range of node indices in the tree (0 to Tree::len() - 1).
• The node at the given index exists and has not been removed (if applicable).
• No other references to the same node are active during this call, to avoid data races or aliasing violations.

Example

use easy_tree::Tree;

let mut tree = Tree::new();
let root = tree.add_node(42);

// Safe use: The index is valid.
*tree.get_unchecked_mut(root) = 99;
assert_eq!(tree.get_unchecked(root), &99);

// Unsafe use: Accessing an invalid index would cause undefined behavior.
// let invalid = tree.get_unchecked_mut(999); // Avoid this!

pub fn parent_index_unchecked(&self, index: usize) -> Option<usize>

Returns the parent index of a node, if it has a parent.

Parameters

• index: The index of the node.

Returns

Some(parent_index) if the node has a parent, or None otherwise.

Panics

This method panics if the index is out of bounds.

Example

use easy_tree::Tree;

let mut tree = Tree::new();
let root = tree.add_node(42);
let child = tree.add_child(root, 99);
assert_eq!(tree.parent_index_unchecked(child), Some(root));

pub fn children(&self, index: usize) -> &[usize]

Returns a slice of the indices of the children of a node.

Parameters

• index: The index of the node.

Returns

A slice containing the indices of the node’s children.

Panics

This method panics if the index is out of bounds.

Example

use easy_tree::Tree;

let mut tree = Tree::new();
let root = tree.add_node("root");
let child = tree.add_child(root, "child");
assert_eq!(tree.children(root), &[child]);

pub fn traverse<'a, S>( &'a self, before_processing_children: impl FnMut(usize, &'a T, &mut S), after_processing_the_subtree: impl FnMut(usize, &'a T, &mut S), s: &mut S, )

Traverses the tree in a depth-first manner.

The traversal applies two callbacks:

• before_processing_children: Called before processing the children of a node.
• after_processing_the_subtree: Called after processing all children of a node.

Parameters

• before_processing_children: A function to apply before visiting children.
• after_processing_the_subtree: A function to apply after visiting children.
• state: Mutable state to share across callbacks.

Example

use easy_tree::Tree;

let mut tree = Tree::new();
let root = tree.add_node("root");
let child = tree.add_child(root, "child");

let mut log = vec![];
tree.traverse(
    |idx, data, log| log.push(format!("Entering node {}: {}", idx, data)),
    |idx, data, log| log.push(format!("Leaving node {}: {}", idx, data)),
    &mut log,
);

Examples found in repository

examples/traversal.rs (lines 11-15)

fn main() {
    let mut tree = Tree::new();
    let root = tree.add_node("root");
    let child1 = tree.add_child(root, "child1");
    let _grandchild1 = tree.add_child(child1, "grandchild1");
    let _child2 = tree.add_child(root, "child2");

    let mut log = vec![];
    tree.traverse(
        |idx, data, log| log.push(format!("Visiting node {}: {}", idx, data)),
        |idx, data, log| log.push(format!("Finished node {}: {}", idx, data)),
        &mut log,
    );

    println!("{:?}", log);
}

pub fn traverse_mut<S>( &mut self, before_processing_children: impl FnMut(usize, &mut T, &mut S), after_processing_the_subtree: impl FnMut(usize, &mut T, &mut S), s: &mut S, )

Walks the tree recursively, applying the given functions before and after processing the children of each node. This version allows for mutable access to the nodes.

pub fn iter(&self) -> impl Iterator<Item = (usize, &T)>

Returns an iterator over the indices and data of the nodes in the tree.

pub fn iter_mut(&mut self) -> impl Iterator<Item = (usize, &mut T)>

Returns a mutable iterator over the indices and data of the nodes in the tree.

pub fn is_empty(&self) -> bool

Returns true if the tree contains no nodes.

pub fn len(&self) -> usize

Returns the number of nodes in the tree.

pub fn clear(&mut self)

Removes all nodes from the tree.

impl<T: Send + Sync> Tree<T>

pub fn par_iter(&self) -> impl ParallelIterator<Item = (usize, &T)>

Returns a parallel iterator over the indices and data of the nodes in the tree.

pub fn par_iter_mut(&mut self) -> impl ParallelIterator<Item = (usize, &mut T)>

Returns a mutable parallel iterator over the indices and data of the nodes in the tree.

Trait Implementations

impl<T: Clone> Clone for Tree<T>

fn clone(&self) -> Tree<T>

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<T> Default for Tree<T>

fn default() -> Self

Returns the “default value” for a type.