Struct NodeId 

pub struct NodeId { /* private fields */ }

A node identifier within a particular Arena.

This ID is used to get Node references from an Arena.

Cross-arena safety

A NodeId does not carry a reference to the arena it was created in. Using an ID from one arena to index into a different arena will either panic (if the index is out of bounds) or silently access the wrong node. It is the caller’s responsibility to use each NodeId only with its originating arena.

Implementations

impl NodeId

pub fn is_removed<T>(self, arena: &Arena<T>) -> bool

Returns true if the node this ID points to has been removed or is no longer present in the arena.

Unlike indexing with arena[id], this method does not panic when the node ID is out of bounds (e.g. after Arena::clear).

pub fn parent<T>(self, arena: &Arena<T>) -> Option<Self>

Returns the ID of the parent node, unless this node is the root of the tree.

Examples

// arena
// `-- 1
//     |-- 1_1
//     |-- 1_2
//     `-- 1_3
assert_eq!(n1.parent(&arena), None);
assert_eq!(n1_1.parent(&arena), Some(n1));
assert_eq!(n1_2.parent(&arena), Some(n1));
assert_eq!(n1_3.parent(&arena), Some(n1));

pub fn first_child<T>(self, arena: &Arena<T>) -> Option<Self>

Returns the ID of the first child of this node, unless it has no child.

Shorthand for arena[self].first_child().

Examples

let mut arena = Arena::new();
let n1 = arena.new_node("1");
let n1_1 = n1.append_value("1_1", &mut arena);

assert_eq!(n1.first_child(&arena), Some(n1_1));
assert_eq!(n1_1.first_child(&arena), None);

pub fn last_child<T>(self, arena: &Arena<T>) -> Option<Self>

Returns the ID of the last child of this node, unless it has no child.

Shorthand for arena[self].last_child().

Examples

let mut arena = Arena::new();
let n1 = arena.new_node("1");
let n1_1 = n1.append_value("1_1", &mut arena);
let n1_2 = n1.append_value("1_2", &mut arena);

assert_eq!(n1.last_child(&arena), Some(n1_2));
assert_eq!(n1_1.last_child(&arena), None);

pub fn next_sibling<T>(self, arena: &Arena<T>) -> Option<Self>

Returns the ID of the next sibling of this node.

Shorthand for arena[self].next_sibling().

Examples

let mut arena = Arena::new();
let n1 = arena.new_node("1");
let n1_1 = n1.append_value("1_1", &mut arena);
let n1_2 = n1.append_value("1_2", &mut arena);

assert_eq!(n1_1.next_sibling(&arena), Some(n1_2));
assert_eq!(n1_2.next_sibling(&arena), None);

pub fn previous_sibling<T>(self, arena: &Arena<T>) -> Option<Self>

Returns the ID of the previous sibling of this node.

Shorthand for arena[self].previous_sibling().

Examples

let mut arena = Arena::new();
let n1 = arena.new_node("1");
let n1_1 = n1.append_value("1_1", &mut arena);
let n1_2 = n1.append_value("1_2", &mut arena);

assert_eq!(n1_2.previous_sibling(&arena), Some(n1_1));
assert_eq!(n1_1.previous_sibling(&arena), None);

pub fn has_children<T>(self, arena: &Arena<T>) -> bool

Returns true if this node has at least one child.

Examples

let mut arena = Arena::new();
let n1 = arena.new_node("1");
let n1_1 = n1.append_value("1_1", &mut arena);

assert!(n1.has_children(&arena));
assert!(!n1_1.has_children(&arena));

pub fn is_leaf<T>(self, arena: &Arena<T>) -> bool

Returns true if this node has no children.

Examples

let mut arena = Arena::new();
let n1 = arena.new_node("1");
let n1_1 = n1.append_value("1_1", &mut arena);

assert!(!n1.is_leaf(&arena));
assert!(n1_1.is_leaf(&arena));

pub fn is_root<T>(self, arena: &Arena<T>) -> bool

Returns true if this node has no parent.

Examples

let mut arena = Arena::new();
let n1 = arena.new_node("1");
let n1_1 = n1.append_value("1_1", &mut arena);

assert!(n1.is_root(&arena));
assert!(!n1_1.is_root(&arena));

pub fn ancestors<T>(self, arena: &Arena<T>) -> Ancestors<'_, T>

Returns an iterator of IDs of this node and its ancestors.

Use .skip(1) or call .next() once on the iterator to skip the node itself.

Examples

// arena
// `-- 1                                                // #3
//     |-- 1_1                                          // #2
//     |   `-- 1_1_1 *                                  // #1
//     |       `-- 1_1_1_1
//     |-- 1_2
//     `-- 1_3

let mut iter = n1_1_1.ancestors(&arena);
assert_eq!(iter.next(), Some(n1_1_1));                  // #1
assert_eq!(iter.next(), Some(n1_1));                    // #2
assert_eq!(iter.next(), Some(n1));                      // #3
assert_eq!(iter.next(), None);

pub fn predecessors<T>(self, arena: &Arena<T>) -> Predecessors<'_, T>

Returns an iterator of IDs of this node and its predecessors.

Use .skip(1) or call .next() once on the iterator to skip the node itself.

Examples

// arena
// `-- 1                                                // #3
//     |-- 1_1                                          // #2
//     |   `-- 1_1_1 *                                  // #1
//     |       `-- 1_1_1_1
//     |-- 1_2
//     `-- 1_3

let mut iter = n1_1_1.predecessors(&arena);
assert_eq!(iter.next(), Some(n1_1_1));                  // #1
assert_eq!(iter.next(), Some(n1_1));                    // #2
assert_eq!(iter.next(), Some(n1));                      // #3
assert_eq!(iter.next(), None);

// arena
// `-- 1                                                // #4
//     |-- 1_1                                          // #3
//     |-- 1_2                                          // #2
//     |   `-- 1_2_1 *                                  // #1
//     |       `-- 1_2_1_1
//     |-- 1_3
//     `-- 1_4

let mut iter = n1_2_1.predecessors(&arena);
assert_eq!(iter.next(), Some(n1_2_1));                  // #1
assert_eq!(iter.next(), Some(n1_2));                    // #2
assert_eq!(iter.next(), Some(n1_1));                    // #3
assert_eq!(iter.next(), Some(n1));                      // #4
assert_eq!(iter.next(), None);

pub fn preceding_siblings<T>(self, arena: &Arena<T>) -> PrecedingSiblings<'_, T>

Returns an iterator of IDs of this node and the siblings before it.

Use .skip(1) or call .next() once on the iterator to skip the node itself.

Examples

// arena
// `-- 1
//     |-- 1_1                                          // #2
//     |   `-- 1_1_1
//     |-- 1_2                                          // #1
//     `-- 1_3

let mut iter = n1_2.preceding_siblings(&arena);
assert_eq!(iter.next(), Some(n1_2));                    // #1
assert_eq!(iter.next(), Some(n1_1));                    // #2
assert_eq!(iter.next(), None);

pub fn following_siblings<T>(self, arena: &Arena<T>) -> FollowingSiblings<'_, T>

Returns an iterator of IDs of this node and the siblings after it.

Use .skip(1) or call .next() once on the iterator to skip the node itself.

Examples

// arena
// `-- 1
//     |-- 1_1
//     |   `-- 1_1_1
//     |-- 1_2                                          // #1
//     `-- 1_3                                          // #2

let mut iter = n1_2.following_siblings(&arena);
assert_eq!(iter.next(), Some(n1_2));                    // #1
assert_eq!(iter.next(), Some(n1_3));                    // #2
assert_eq!(iter.next(), None);

pub fn children<T>(self, arena: &Arena<T>) -> Children<'_, T>

Returns an iterator of IDs of this node’s children.

Examples

// arena
// `-- 1
//     |-- 1_1                                          // #1
//     |   `-- 1_1_1
//     |-- 1_2                                          // #2
//     `-- 1_3                                          // #3

let mut iter = n1.children(&arena);
assert_eq!(iter.next(), Some(n1_1));                    // #1
assert_eq!(iter.next(), Some(n1_2));                    // #2
assert_eq!(iter.next(), Some(n1_3));                    // #3
assert_eq!(iter.next(), None);

pub fn child_count<T>(self, arena: &Arena<T>) -> usize

Returns the number of children of this node.

This traverses the sibling chain and is O(n) in the number of children. If you only need to check whether a node has children, prefer checking first_child() instead.

Examples

// arena
// `-- 1
//     |-- 1_1
//     |-- 1_2
//     `-- 1_3
assert_eq!(n1.child_count(&arena), 3);
assert_eq!(n1_1.child_count(&arena), 0);

pub fn depth<T>(self, arena: &Arena<T>) -> usize

Returns the depth (level) of this node in the tree.

A root node (no parent) has depth 0, its children have depth 1, etc. This traverses ancestors and is O(depth).

Examples

let mut arena = Arena::new();
let root = arena.new_node("root");
let child = root.append_value("child", &mut arena);
let grandchild = child.append_value("grandchild", &mut arena);

assert_eq!(root.depth(&arena), 0);
assert_eq!(child.depth(&arena), 1);
assert_eq!(grandchild.depth(&arena), 2);

pub fn nth_child<T>(self, n: usize, arena: &Arena<T>) -> Option<NodeId>

Returns the nth child of this node (zero-indexed).

Returns None if the node has fewer than n + 1 children. This is O(n) as it walks the sibling chain.

Examples

let mut arena = Arena::new();
let root = arena.new_node("root");
let c0 = root.append_value("c0", &mut arena);
let c1 = root.append_value("c1", &mut arena);
let c2 = root.append_value("c2", &mut arena);

assert_eq!(root.nth_child(0, &arena), Some(c0));
assert_eq!(root.nth_child(1, &arena), Some(c1));
assert_eq!(root.nth_child(2, &arena), Some(c2));
assert_eq!(root.nth_child(3, &arena), None);

pub fn is_ancestor_of<T>(self, other: NodeId, arena: &Arena<T>) -> bool

Returns true if this node is an ancestor of other.

A node is not considered an ancestor of itself.

Examples

let mut arena = Arena::new();
let root = arena.new_node("root");
let child = root.append_value("child", &mut arena);
let grandchild = child.append_value("grandchild", &mut arena);

assert!(root.is_ancestor_of(child, &arena));
assert!(root.is_ancestor_of(grandchild, &arena));
assert!(!child.is_ancestor_of(root, &arena));
assert!(!root.is_ancestor_of(root, &arena));

pub fn is_descendant_of<T>(self, other: NodeId, arena: &Arena<T>) -> bool

Returns true if this node is a descendant of other.

A node is not considered a descendant of itself.

Examples

let mut arena = Arena::new();
let root = arena.new_node("root");
let child = root.append_value("child", &mut arena);
let grandchild = child.append_value("grandchild", &mut arena);

assert!(grandchild.is_descendant_of(root, &arena));
assert!(child.is_descendant_of(root, &arena));
assert!(!root.is_descendant_of(child, &arena));
assert!(!root.is_descendant_of(root, &arena));

pub fn descendants<T>(self, arena: &Arena<T>) -> Descendants<'_, T>

An iterator of the IDs of a given node and its descendants, as a pre-order depth-first search where children are visited in insertion order.

i.e. node -> first child -> second child

Parent nodes appear before the descendants. Use .skip(1) or call .next() once on the iterator to skip the node itself.

Examples

// arena
// `-- 1                                                // #1
//     |-- 1_1                                          // #2
//     |   `-- 1_1_1                                    // #3
//     |       `-- 1_1_1_1                              // #4
//     |-- 1_2                                          // #5
//     `-- 1_3                                          // #6

let mut iter = n1.descendants(&arena);
assert_eq!(iter.next(), Some(n1));                      // #1
assert_eq!(iter.next(), Some(n1_1));                    // #2
assert_eq!(iter.next(), Some(n1_1_1));                  // #3
assert_eq!(iter.next(), Some(n1_1_1_1));                // #4
assert_eq!(iter.next(), Some(n1_2));                    // #5
assert_eq!(iter.next(), Some(n1_3));                    // #6
assert_eq!(iter.next(), None);

pub fn leaves<T>(self, arena: &Arena<T>) -> Leaves<'_, T>

Returns an iterator over the leaf nodes (nodes with no children) of this node’s subtree in pre-order depth-first order.

Examples

let mut arena = Arena::new();
let root = arena.new_node("root");
let a = root.append_value("a", &mut arena);
let b = a.append_value("b", &mut arena);
let c = root.append_value("c", &mut arena);

let leaves: Vec<_> = root.leaves(&arena).collect();
assert_eq!(leaves, vec![b, c]);

pub fn breadth_first<T>(self, arena: &Arena<T>) -> BreadthFirstTraversal<'_, T>

Returns an iterator that yields nodes in breadth-first (level-order) order, starting from this node.

Examples

let mut arena = Arena::new();
let root = arena.new_node(1);
let a = root.append_value(2, &mut arena);
let b = root.append_value(3, &mut arena);
let c = a.append_value(4, &mut arena);

let bfs: Vec<_> = root.breadth_first(&arena)
    .map(|id| *arena[id].get())
    .collect();
assert_eq!(bfs, vec![1, 2, 3, 4]);

pub fn descendant_count<T>(self, arena: &Arena<T>) -> usize

Returns the number of descendants of this node, including itself.

This is O(n) in the size of the subtree.

Examples

let mut arena = Arena::new();
let root = arena.new_node("root");
let a = root.append_value("a", &mut arena);
a.append_value("b", &mut arena);
root.append_value("c", &mut arena);

assert_eq!(root.descendant_count(&arena), 4);
assert_eq!(a.descendant_count(&arena), 2);

pub fn traverse<T>(self, arena: &Arena<T>) -> Traverse<'_, T>

An iterator of the “sides” of a node visited during a depth-first pre-order traversal, where node sides are visited start to end and children are visited in insertion order.

i.e. node.start -> first child -> second child -> node.end

Examples

// arena
// `-- 1                                                // #1, #10
//     |-- 1_1                                          // #2, #5
//     |   `-- 1_1_1                                    // #3, #4
//     |-- 1_2                                          // #6, #7
//     `-- 1_3                                          // #8, #9

let mut iter = n1.traverse(&arena);
assert_eq!(iter.next(), Some(NodeEdge::Start(n1)));     // #1
assert_eq!(iter.next(), Some(NodeEdge::Start(n1_1)));   // #2
assert_eq!(iter.next(), Some(NodeEdge::Start(n1_1_1))); // #3
assert_eq!(iter.next(), Some(NodeEdge::End(n1_1_1)));   // #4
assert_eq!(iter.next(), Some(NodeEdge::End(n1_1)));     // #5
assert_eq!(iter.next(), Some(NodeEdge::Start(n1_2)));   // #6
assert_eq!(iter.next(), Some(NodeEdge::End(n1_2)));     // #7
assert_eq!(iter.next(), Some(NodeEdge::Start(n1_3)));   // #8
assert_eq!(iter.next(), Some(NodeEdge::End(n1_3)));     // #9
assert_eq!(iter.next(), Some(NodeEdge::End(n1)));       // #10
assert_eq!(iter.next(), None);

pub fn reverse_traverse<T>(self, arena: &Arena<T>) -> ReverseTraverse<'_, T>

An iterator of the “sides” of a node visited during a depth-first pre-order traversal, where nodes are visited end to start and children are visited in reverse insertion order.

i.e. node.end -> second child -> first child -> node.start

Examples

// arena
// `-- 1                                                // #1, #10
//     |-- 1_1                                          // #6, #9
//     |   `-- 1_1_1                                    // #7, #8
//     |-- 1_2                                          // #4, #5
//     `-- 1_3                                          // #2, #3

let mut iter = n1.reverse_traverse(&arena);
assert_eq!(iter.next(), Some(NodeEdge::End(n1)));       // #1
assert_eq!(iter.next(), Some(NodeEdge::End(n1_3)));     // #2
assert_eq!(iter.next(), Some(NodeEdge::Start(n1_3)));   // #3
assert_eq!(iter.next(), Some(NodeEdge::End(n1_2)));     // #4
assert_eq!(iter.next(), Some(NodeEdge::Start(n1_2)));   // #5
assert_eq!(iter.next(), Some(NodeEdge::End(n1_1)));     // #6
assert_eq!(iter.next(), Some(NodeEdge::End(n1_1_1)));   // #7
assert_eq!(iter.next(), Some(NodeEdge::Start(n1_1_1))); // #8
assert_eq!(iter.next(), Some(NodeEdge::Start(n1_1)));   // #9
assert_eq!(iter.next(), Some(NodeEdge::Start(n1)));     // #10
assert_eq!(iter.next(), None);

// arena
// `-- 1                                                // #1, #10
//     |-- 1_1                                          // #6, #9
//     |   `-- 1_1_1                                    // #7, #8
//     |-- 1_2                                          // #4, #5
//     `-- 1_3                                          // #2, #3
let traverse = n1.traverse(&arena).collect::<Vec<_>>();
let mut reverse = n1.reverse_traverse(&arena).collect::<Vec<_>>();
reverse.reverse();
assert_eq!(traverse, reverse);

pub fn checked_detach<T>(self, arena: &mut Arena<T>) -> Result<(), NodeError>

Detaches a node from its parent and siblings. Children are not affected.

Failures

Returns NodeError::Removed if the node has been removed or the ID is stale.

Examples

let mut arena = Arena::new();
let root = arena.new_node("root");
let child = root.append_value("child", &mut arena);
assert!(child.checked_detach(&mut arena).is_ok());
assert!(child.parent(&arena).is_none());

pub fn detach<T>(self, arena: &mut Arena<T>)

Detaches a node from its parent and siblings. Children are not affected.

Panics

Panics if the node ID is out of bounds (e.g. after Arena::clear).

Examples

// arena
// `-- (implicit)
//     `-- 1
//         |-- 1_1
//         |   `-- 1_1_1
//         |-- 1_2 *
//         `-- 1_3

n1_2.detach(&mut arena);
// arena
// |-- (implicit)
// |   `-- 1
// |       |-- 1_1
// |       |   `-- 1_1_1
// |       `-- 1_3
// `-- (implicit)
//     `-- 1_2 *

assert!(arena[n1_2].parent().is_none());
assert!(arena[n1_2].previous_sibling().is_none());
assert!(arena[n1_2].next_sibling().is_none());

let mut iter = n1.descendants(&arena);
assert_eq!(iter.next(), Some(n1));
assert_eq!(iter.next(), Some(n1_1));
assert_eq!(iter.next(), Some(n1_1_1));
assert_eq!(iter.next(), Some(n1_3));
assert_eq!(iter.next(), None);

pub fn append<T>(self, new_child: NodeId, arena: &mut Arena<T>)

Appends a new child to this node, after existing children.

Panics

Panics if:

• the given new child is self, or
• the given new child is an ancestor of self, or
• the current node or the given new child was already removed.

To check if the node is removed or not, use Node::is_removed().

Examples

let mut arena = Arena::new();
let n1 = arena.new_node("1");
let n1_1 = arena.new_node("1_1");
n1.append(n1_1, &mut arena);
let n1_2 = arena.new_node("1_2");
n1.append(n1_2, &mut arena);
let n1_3 = arena.new_node("1_3");
n1.append(n1_3, &mut arena);

// arena
// `-- 1
//     |-- 1_1
//     |-- 1_2
//     `-- 1_3

let mut iter = n1.descendants(&arena);
assert_eq!(iter.next(), Some(n1));
assert_eq!(iter.next(), Some(n1_1));
assert_eq!(iter.next(), Some(n1_2));
assert_eq!(iter.next(), Some(n1_3));
assert_eq!(iter.next(), None);

pub fn checked_append<T>( self, new_child: NodeId, arena: &mut Arena<T>, ) -> Result<(), NodeError>

Appends a new child to this node, after existing children.

Failures

• Returns NodeError::AppendSelf error if the given new child is self.
• Returns NodeError::AppendAncestor error if the given new child is an ancestor of self.
• Returns NodeError::Removed error if the given new child or self is removed.

To check if the node is removed or not, use Node::is_removed().

Examples

let mut arena = Arena::new();
let n1 = arena.new_node("1");
assert!(n1.checked_append(n1, &mut arena).is_err());

let n1_1 = arena.new_node("1_1");
assert!(n1.checked_append(n1_1, &mut arena).is_ok());

pub fn append_value<T>(self, value: T, arena: &mut Arena<T>) -> NodeId

Creates and appends a new node (from its associated data) as the last child. This method is a fast path for the common case of appending a new node. It is quicker than append.

Panics

Panics if the arena already has usize::max_value() nodes.

Examples

let mut arena = Arena::new();
let n1 = arena.new_node("1");
let n1_1 = n1.append_value("1_1", &mut arena);
let n1_1_1 = n1_1.append_value("1_1_1", &mut arena);
let n1_1_2 = n1_1.append_value("1_1_2", &mut arena);

// arena
// `-- 1
//     `-- 1_1
//         |-- 1_1_1
//         `-- 1_1_2

let mut iter = n1.descendants(&arena);
assert_eq!(iter.next(), Some(n1));
assert_eq!(iter.next(), Some(n1_1));
assert_eq!(iter.next(), Some(n1_1_1));
assert_eq!(iter.next(), Some(n1_1_2));
assert_eq!(iter.next(), None);

pub fn prepend_value<T>(self, value: T, arena: &mut Arena<T>) -> NodeId

Creates and prepends a new node (from its associated data) as the first child. This method is a fast path for the common case of prepending a new node. It is quicker than prepend.

Panics

Panics if the arena already has usize::max_value() nodes.

Examples

let mut arena = Arena::new();
let n1 = arena.new_node("1");
let n1_1 = n1.prepend_value("1_1", &mut arena);
let n1_2 = n1.prepend_value("1_2", &mut arena);
let n1_3 = n1.prepend_value("1_3", &mut arena);

// arena
// `-- 1
//     |-- 1_3
//     |-- 1_2
//     `-- 1_1

let mut iter = n1.descendants(&arena);
assert_eq!(iter.next(), Some(n1));
assert_eq!(iter.next(), Some(n1_3));
assert_eq!(iter.next(), Some(n1_2));
assert_eq!(iter.next(), Some(n1_1));
assert_eq!(iter.next(), None);

pub fn prepend<T>(self, new_child: NodeId, arena: &mut Arena<T>)

Prepends a new child to this node, before existing children.

Panics

Panics if:

• the given new child is self, or
• the given new child is an ancestor of self, or
• the current node or the given new child was already removed.

To check if the node is removed or not, use Node::is_removed().

Examples

let mut arena = Arena::new();
let n1 = arena.new_node("1");
let n1_1 = arena.new_node("1_1");
n1.prepend(n1_1, &mut arena);
let n1_2 = arena.new_node("1_2");
n1.prepend(n1_2, &mut arena);
let n1_3 = arena.new_node("1_3");
n1.prepend(n1_3, &mut arena);

// arena
// `-- 1
//     |-- 1_3
//     |-- 1_2
//     `-- 1_1

let mut iter = n1.descendants(&arena);
assert_eq!(iter.next(), Some(n1));
assert_eq!(iter.next(), Some(n1_3));
assert_eq!(iter.next(), Some(n1_2));
assert_eq!(iter.next(), Some(n1_1));
assert_eq!(iter.next(), None);

pub fn checked_prepend<T>( self, new_child: NodeId, arena: &mut Arena<T>, ) -> Result<(), NodeError>

Prepends a new child to this node, before existing children.

Failures

• Returns NodeError::PrependSelf error if the given new child is self.
• Returns NodeError::PrependAncestor error if the given new child is an ancestor of self.
• Returns NodeError::Removed error if the given new child or self is removed.

To check if the node is removed or not, use Node::is_removed().

Examples

let mut arena = Arena::new();
let n1 = arena.new_node("1");
assert!(n1.checked_prepend(n1, &mut arena).is_err());

let n1_1 = arena.new_node("1_1");
assert!(n1.checked_prepend(n1_1, &mut arena).is_ok());

pub fn insert_after<T>(self, new_sibling: NodeId, arena: &mut Arena<T>)

Inserts a new sibling after this node.

Panics

Panics if:

• the given new sibling is self, or
• the current node or the given new sibling was already removed.

To check if the node is removed or not, use Node::is_removed().

Examples

// arena
// `-- 1
//     |-- 1_1 *
//     `-- 1_2

let n1_3 = arena.new_node("1_3");
n1_1.insert_after(n1_3, &mut arena);

// arena
// `-- 1
//     |-- 1_1
//     |-- 1_3 *
//     `-- 1_2

let mut iter = n1.descendants(&arena);
assert_eq!(iter.next(), Some(n1));
assert_eq!(iter.next(), Some(n1_1));
assert_eq!(iter.next(), Some(n1_3));
assert_eq!(iter.next(), Some(n1_2));
assert_eq!(iter.next(), None);

pub fn insert_after_value<T>(self, value: T, arena: &mut Arena<T>) -> NodeId

Creates and inserts a new sibling node after this node.

A convenience shorthand for creating a node via Arena::new_node and inserting it via insert_after.

Panics

Panics if:

• the arena already has usize::max_value() nodes, or
• self was already removed.

Examples

let mut arena = Arena::new();
let n1 = arena.new_node("1");
let n1_1 = n1.append_value("1_1", &mut arena);
let n1_3 = n1.append_value("1_3", &mut arena);
let n1_2 = n1_1.insert_after_value("1_2", &mut arena);

// arena
// `-- 1
//     |-- 1_1
//     |-- 1_2
//     `-- 1_3

let mut iter = n1.children(&arena);
assert_eq!(iter.next(), Some(n1_1));
assert_eq!(iter.next(), Some(n1_2));
assert_eq!(iter.next(), Some(n1_3));
assert_eq!(iter.next(), None);

pub fn checked_insert_after<T>( self, new_sibling: NodeId, arena: &mut Arena<T>, ) -> Result<(), NodeError>

Inserts a new sibling after this node.

Failures

• Returns NodeError::InsertAfterSelf error if the given new sibling is self.
• Returns NodeError::Removed error if the given new sibling or self is removed.

To check if the node is removed or not, use Node::is_removed().

Examples

let mut arena = Arena::new();
let n1 = arena.new_node("1");
assert!(n1.checked_insert_after(n1, &mut arena).is_err());

let n2 = arena.new_node("2");
assert!(n1.checked_insert_after(n2, &mut arena).is_ok());

pub fn insert_before<T>(self, new_sibling: NodeId, arena: &mut Arena<T>)

Inserts a new sibling before this node.

Panics

Panics if:

• the given new sibling is self, or
• the current node or the given new sibling was already removed.

To check if the node is removed or not, use Node::is_removed().

Examples

let mut arena = Arena::new();
let n1 = arena.new_node("1");
let n1_1 = arena.new_node("1_1");
n1.append(n1_1, &mut arena);
let n1_2 = arena.new_node("1_2");
n1.append(n1_2, &mut arena);

// arena
// `-- 1
//     |-- 1_1
//     `-- 1_2 *

let n1_3 = arena.new_node("1_3");
n1_2.insert_before(n1_3, &mut arena);

// arena
// `-- 1
//     |-- 1_1
//     |-- 1_3 *
//     `-- 1_2

let mut iter = n1.descendants(&arena);
assert_eq!(iter.next(), Some(n1));
assert_eq!(iter.next(), Some(n1_1));
assert_eq!(iter.next(), Some(n1_3));
assert_eq!(iter.next(), Some(n1_2));
assert_eq!(iter.next(), None);

pub fn insert_before_value<T>(self, value: T, arena: &mut Arena<T>) -> NodeId

Creates and inserts a new sibling node before this node.

A convenience shorthand for creating a node via Arena::new_node and inserting it via insert_before.

Panics

Panics if:

• the arena already has usize::max_value() nodes, or
• self was already removed.

Examples

let mut arena = Arena::new();
let n1 = arena.new_node("1");
let n1_1 = n1.append_value("1_1", &mut arena);
let n1_3 = n1.append_value("1_3", &mut arena);
let n1_2 = n1_3.insert_before_value("1_2", &mut arena);

// arena
// `-- 1
//     |-- 1_1
//     |-- 1_2
//     `-- 1_3

let mut iter = n1.children(&arena);
assert_eq!(iter.next(), Some(n1_1));
assert_eq!(iter.next(), Some(n1_2));
assert_eq!(iter.next(), Some(n1_3));
assert_eq!(iter.next(), None);

pub fn checked_insert_before<T>( self, new_sibling: NodeId, arena: &mut Arena<T>, ) -> Result<(), NodeError>

Inserts a new sibling before this node.

Failures

• Returns NodeError::InsertBeforeSelf error if the given new sibling is self.
• Returns NodeError::Removed error if the given new sibling or self is removed.

To check if the node is removed or not, use Node::is_removed().

Examples

let mut arena = Arena::new();
let n1 = arena.new_node("1");
assert!(n1.checked_insert_before(n1, &mut arena).is_err());

let n2 = arena.new_node("2");
assert!(n1.checked_insert_before(n2, &mut arena).is_ok());

pub fn checked_remove<T>(self, arena: &mut Arena<T>) -> Result<(), NodeError>

Removes a node from the arena, returning an error on failure.

Children of the removed node will be inserted in place of the removed node.

Failures

Returns NodeError::Removed if the node has been removed or the ID is stale.

Examples

let mut arena = Arena::new();
let n = arena.new_node("x");
assert!(n.checked_remove(&mut arena).is_ok());
assert!(matches!(n.checked_remove(&mut arena), Err(NodeError::Removed)));

pub fn remove<T>(self, arena: &mut Arena<T>)

Removes a node from the arena.

Children of the removed node will be inserted to the place where the removed node was.

Please note that the node will not be removed from the internal arena storage, but marked as removed. Traversing the arena returns a plain iterator and contains removed elements too.

To check if the node is removed or not, use Node::is_removed().

Panics

Panics if the node ID is out of bounds.

Examples

// arena
// `-- 1
//     |-- 1_1
//     |-- 1_2 *
//     |   |-- 1_2_1
//     |   `-- 1_2_2
//     `-- 1_3

n1_2.remove(&mut arena);

// arena
// `-- 1
//     |-- 1_1
//     |-- 1_2_1
//     |-- 1_2_2
//     `-- 1_3

let mut iter = n1.descendants(&arena);
assert_eq!(iter.next(), Some(n1));
assert_eq!(iter.next(), Some(n1_1));
assert_eq!(iter.next(), Some(n1_2_1));
assert_eq!(iter.next(), Some(n1_2_2));
assert_eq!(iter.next(), Some(n1_3));
assert_eq!(iter.next(), None);

pub fn checked_remove_subtree<T>( self, arena: &mut Arena<T>, ) -> Result<(), NodeError>

Removes a node and its descendants from the arena, returning an error on failure.

Failures

Returns NodeError::Removed if the node has been removed or the ID is stale.

Examples

let mut arena = Arena::new();
let n = arena.new_node("x");
n.append_value("child", &mut arena);
assert!(n.checked_remove_subtree(&mut arena).is_ok());
assert!(matches!(n.checked_remove_subtree(&mut arena), Err(NodeError::Removed)));

pub fn remove_subtree<T>(self, arena: &mut Arena<T>)

Removes a node and its descendants from the arena.

Panics

Panics if the node ID is out of bounds.

Examples

// arena
// `-- 1
//     |-- 1_1
//     |-- 1_2 *
//     |   |-- 1_2_1
//     |   `-- 1_2_2
//     `-- 1_3

n1_2.remove_subtree(&mut arena);

// arena
// `-- 1
//     |-- 1_1
//     `-- 1_3

let mut iter = n1.descendants(&arena);
assert_eq!(iter.next(), Some(n1));
assert_eq!(iter.next(), Some(n1_1));
assert_eq!(iter.next(), Some(n1_3));
assert_eq!(iter.next(), None);

pub fn checked_detach_children<T>( self, arena: &mut Arena<T>, ) -> Result<(), NodeError>

Detaches all children of this node, returning an error on failure.

Failures

Returns NodeError::Removed if the node has been removed or the ID is stale.

Examples

let mut arena = Arena::new();
let root = arena.new_node("root");
root.append_value("c1", &mut arena);
assert!(root.checked_detach_children(&mut arena).is_ok());
assert_eq!(root.children(&arena).count(), 0);

pub fn detach_children<T>(self, arena: &mut Arena<T>)

Detaches all children of this node, leaving them as independent toplevel nodes while keeping the node itself in its current position.

The children retain their own subtrees and sibling relationships with each other are removed.

Panics

Panics if the node ID is out of bounds.

Examples

// arena
// `-- 1
//     |-- 1_1
//     |-- 1_2
//     |   `-- 1_2_1
//     `-- 1_3

n1.detach_children(&mut arena);

// arena (all former children are now independent toplevel nodes)
// |-- 1
// |-- 1_1
// |-- 1_2
// |   `-- 1_2_1
// `-- 1_3

assert_eq!(n1.children(&arena).count(), 0);
assert!(!arena[n1_1].is_removed());
assert!(arena[n1_1].parent().is_none());
// 1_2's subtree is preserved
assert_eq!(arena[n1_2_1].parent(), Some(n1_2));

pub fn checked_remove_children<T>( self, arena: &mut Arena<T>, ) -> Result<(), NodeError>

Removes all children of this node from the arena, returning an error on failure.

Failures

Returns NodeError::Removed if the node has been removed or the ID is stale.

Examples

let mut arena = Arena::new();
let root = arena.new_node("root");
root.append_value("c1", &mut arena);
assert!(root.checked_remove_children(&mut arena).is_ok());
assert_eq!(root.children(&arena).count(), 0);

pub fn remove_children<T>(self, arena: &mut Arena<T>)

Removes all children of this node from the arena, keeping the node itself in its current position.

This is equivalent to calling remove_subtree on each child.

Panics

Panics if the node ID is out of bounds.

Examples

// arena
// `-- 1
//     |-- 1_1
//     |-- 1_2
//     |   `-- 1_2_1
//     `-- 1_3

n1.remove_children(&mut arena);

// arena
// `-- 1

assert_eq!(n1.children(&arena).count(), 0);
assert!(n1_1.is_removed(&arena));
assert!(n1_2.is_removed(&arena));
assert!(n1_2_1.is_removed(&arena));
assert!(n1_3.is_removed(&arena));

pub fn checked_reparent<T>( self, new_parent: NodeId, arena: &mut Arena<T>, ) -> Result<(), NodeError>

Moves this node (and its subtree) to become the last child of new_parent, returning an error on failure.

Failures

Returns the same errors as checked_append.

Examples

let mut arena = Arena::new();
let a = arena.new_node("a");
let b = a.append_value("b", &mut arena);
let c = arena.new_node("c");
assert!(b.checked_reparent(c, &mut arena).is_ok());
assert_eq!(b.parent(&arena), Some(c));

pub fn reparent<T>(self, new_parent: NodeId, arena: &mut Arena<T>)

Moves this node (and its subtree) to become the last child of new_parent.

This is a convenience wrapper around detach followed by append.

Panics

Panics if new_parent is self or a descendant of self, or if either node has been removed.

Examples

let mut arena = Arena::new();
let a = arena.new_node("a");
let b = a.append_value("b", &mut arena);
let c = arena.new_node("c");

b.reparent(c, &mut arena);

assert_eq!(b.parent(&arena), Some(c));
assert_eq!(a.children(&arena).count(), 0);
assert_eq!(c.first_child(&arena), Some(b));

pub fn subtree_eq<T: PartialEq>( self, other: NodeId, arena_self: &Arena<T>, arena_other: &Arena<T>, ) -> bool

Returns true if the subtree rooted at this node is structurally equal to the subtree rooted at other, comparing node data with PartialEq.

Two subtrees are equal if they have the same shape and the same data at every corresponding position.

The two nodes may be in the same or different arenas.

Examples

let mut a1 = Arena::new();
let r1 = a1.new_node(1);
r1.append_value(2, &mut a1);
r1.append_value(3, &mut a1);

let mut a2 = Arena::new();
let r2 = a2.new_node(1);
r2.append_value(2, &mut a2);
r2.append_value(3, &mut a2);

assert!(r1.subtree_eq(r2, &a1, &a2));

pub fn debug_pretty_print<'a, T>( &'a self, arena: &'a Arena<T>, ) -> DebugPrettyPrint<'a, T>

Returns the pretty-printable proxy object to the node and descendants.

(No) guarantees

This is provided mainly for debugging purpose. Note that the output format is not guaranteed to be stable, and any format changes won’t be considered as breaking changes.

Examples

//  arena
//  `-- "root"
//      |-- "0"
//      |   |-- "0\n0"
//      |   `-- "0\n1"
//      |-- "1"
//      `-- "2"
//          `-- "2\n0"
//              `-- "2\n0\n0"

let printable = root.debug_pretty_print(&arena);

let expected_debug = r#""root"
|-- "0"
|   |-- "0\n0"
|   `-- "0\n1"
|-- "1"
`-- "2"
    `-- "2\n0"
        `-- "2\n0\n0""#;
assert_eq!(format!("{:?}", printable), expected_debug);

let expected_display = r#"root
|-- 0
|   |-- 0
|   |   0
|   `-- 0
|       1
|-- 1
`-- 2
    `-- 2
        0
        `-- 2
            0
            0"#;
assert_eq!(printable.to_string(), expected_display);

Alternate styles ({:#?} and {:#}) are also supported.

//  arena
//  `-- Ok(42)
//      `-- Err("err")

let printable = root.debug_pretty_print(&arena);

let expected_debug = r#"Ok(42)
`-- Err("err")"#;
assert_eq!(format!("{:?}", printable), expected_debug);

let expected_debug_alternate = r#"Ok(
    42,
)
`-- Err(
        "err",
    )"#;
assert_eq!(format!("{:#?}", printable), expected_debug_alternate);

Trait Implementations

impl Clone for NodeId

fn clone(&self) -> NodeId

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl Copy for NodeId

impl Debug for NodeId

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

Formats the value using the given formatter.

impl Display for NodeId

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

Formats the value using the given formatter.

impl Eq for NodeId

impl From<NodeId> for NonZeroUsize

fn from(value: NodeId) -> NonZeroUsize

Converts to this type from the input type.

impl From<NodeId> for usize

fn from(value: NodeId) -> usize

Converts to this type from the input type.

impl Hash for NodeId

fn hash<__H: Hasher>(&self, state: &mut __H)

Feeds this value into the given Hasher.

fn hash_slice<H>(data: &[Self], state: &mut H)

where H: Hasher, Self: Sized,

Feeds a slice of this type into the given Hasher.

impl<T> Index<NodeId> for Arena<T>

Index by NodeId for convenient arena[id] access.

Unlike Arena::get, this does not validate the node’s stamp, so it may silently return data from a reused slot if the NodeId is stale. For safe access, prefer Arena::get or Arena::get_mut.

Panics

Panics if node is out of bounds. Note that indexing does not validate that the NodeId originated from this arena. Using an ID from a different arena may silently access the wrong node or panic.

type Output = Node<T>

The returned type after indexing.

fn index(&self, node: NodeId) -> &Node<T>

Performs the indexing (container[index]) operation.

impl<T> IndexMut<NodeId> for Arena<T>

Mutable index by NodeId.

Like Index<NodeId>, this does not validate the node’s stamp. For safe access, prefer Arena::get_mut.

Panics

Panics if node is out of bounds.

fn index_mut(&mut self, node: NodeId) -> &mut Node<T>

Performs the mutable indexing (container[index]) operation.

impl Ord for NodeId

fn cmp(&self, other: &NodeId) -> Ordering

This method returns an Ordering between self and other.

fn max(self, other: Self) -> Self

where Self: Sized,

Compares and returns the maximum of two values.

fn min(self, other: Self) -> Self

where Self: Sized,

Compares and returns the minimum of two values.

fn clamp(self, min: Self, max: Self) -> Self

where Self: Sized,

Restrict a value to a certain interval.

impl PartialEq for NodeId

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

Equality operator ==.

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

Inequality operator !=.

impl PartialOrd for NodeId

fn partial_cmp(&self, other: &NodeId) -> Option<Ordering>

This method returns an ordering between self and other values if one exists.

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

Tests less than (for self and other) and is used by the < operator.

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

Tests less than or equal to (for self and other) and is used by the <= operator.

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

Tests greater than (for self and other) and is used by the > operator.

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

Tests greater than or equal to (for self and other) and is used by the >= operator.

impl StructuralPartialEq for NodeId