Struct NodeId
pub struct NodeId { /* private fields */ }Expand description
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
impl NodeId
pub fn is_removed<T>(self, arena: &Arena<T>) -> bool
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<NodeId>
pub fn parent<T>(self, arena: &Arena<T>) -> Option<NodeId>
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<NodeId>
pub fn first_child<T>(self, arena: &Arena<T>) -> Option<NodeId>
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<NodeId>
pub fn last_child<T>(self, arena: &Arena<T>) -> Option<NodeId>
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<NodeId>
pub fn next_sibling<T>(self, arena: &Arena<T>) -> Option<NodeId>
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<NodeId>
pub fn previous_sibling<T>(self, arena: &Arena<T>) -> Option<NodeId>
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
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
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
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> ⓘ
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> ⓘ
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> ⓘ
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> ⓘ
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> ⓘ
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
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
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>
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
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
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> ⓘ
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> ⓘ
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> ⓘ
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
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> ⓘ
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> ⓘ
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>
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>)
pub fn detach<T>(self, arena: &mut Arena<T>)
Detaches a node from its parent and siblings. Children are not affected.
Does nothing if the node was already removed, which includes stale IDs
whose slot has been reused by a new node, and IDs that are 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>)
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>
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 isself. - Returns [
NodeError::AppendAncestor] error if the given new child is an ancestor ofself. - Returns [
NodeError::Removed] error if the given new child orselfisremoved.
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
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, or selfwas alreadyremoved.
§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
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, or selfwas alreadyremoved.
§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>)
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>
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 isself. - Returns [
NodeError::PrependAncestor] error if the given new child is an ancestor ofself. - Returns [
NodeError::Removed] error if the given new child orselfisremoved.
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>)
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, - the current node or the given new sibling was already
removed, or - the given new sibling is an ancestor of
self.
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
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 selfwas alreadyremoved.
§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>
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 isself. - Returns [
NodeError::Removed] error if the given new sibling orselfisremoved. - Returns [
NodeError::AppendAncestor] error if the given new sibling is an ancestor ofself.
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>)
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, - the current node or the given new sibling was already
removed, or - the given new sibling is an ancestor of
self.
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
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 selfwas alreadyremoved.
§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>
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 isself. - Returns [
NodeError::Removed] error if the given new sibling orselfisremoved. - Returns [
NodeError::PrependAncestor] error if the given new sibling is an ancestor ofself.
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>
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>)
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().
Does nothing if the node was already removed, which includes stale IDs
whose slot has been reused by a new node, and IDs that are out of
bounds (e.g. after Arena::clear).
§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>
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>)
pub fn remove_subtree<T>(self, arena: &mut Arena<T>)
Removes a node and its descendants from the arena.
Does nothing if the node was already removed, which includes stale IDs
whose slot has been reused by a new node, and IDs that are out of
bounds (e.g. after Arena::clear).
§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>
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>)
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.
Does nothing if the node was already removed, which includes stale IDs
whose slot has been reused by a new node, and IDs that are out of
bounds (e.g. after Arena::clear).
§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>
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>)
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.
Does nothing if the node was already removed, which includes stale IDs
whose slot has been reused by a new node, and IDs that are out of
bounds (e.g. after Arena::clear).
§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>
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>)
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>(
self,
other: NodeId,
arena_self: &Arena<T>,
arena_other: &Arena<T>,
) -> boolwhere
T: PartialEq,
pub fn subtree_eq<T>(
self,
other: NodeId,
arena_self: &Arena<T>,
arena_other: &Arena<T>,
) -> boolwhere
T: PartialEq,
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>
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 Copy for NodeId
impl Eq for NodeId
§impl<T> Index<NodeId> for Arena<T>
Index by NodeId for convenient arena[id] access.
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.
§impl<T> IndexMut<NodeId> for Arena<T>
Mutable index by NodeId.
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.
§impl Ord for NodeId
impl Ord for NodeId
1.21.0 (const: unstable) · Source§fn max(self, other: Self) -> Selfwhere
Self: Sized,
fn max(self, other: Self) -> Selfwhere
Self: Sized,
§impl PartialOrd for NodeId
impl PartialOrd for NodeId
impl StructuralPartialEq for NodeId
Auto Trait Implementations§
impl Freeze for NodeId
impl RefUnwindSafe for NodeId
impl Send for NodeId
impl Sync for NodeId
impl Unpin for NodeId
impl UnsafeUnpin for NodeId
impl UnwindSafe for NodeId
Blanket Implementations§
Source§impl<T> BorrowMut<T> for Twhere
T: ?Sized,
impl<T> BorrowMut<T> for Twhere
T: ?Sized,
Source§fn borrow_mut(&mut self) -> &mut T
fn borrow_mut(&mut self) -> &mut T
impl<ST, DT> CastableFrom<ST, Initialized, Initialized> for DT
impl<ST, DT> CastableFrom<ST, Uninit, Uninit> for DT
Source§impl<T> CloneToUninit for Twhere
T: Clone,
impl<T> CloneToUninit for Twhere
T: Clone,
§impl<Q, K> Comparable<K> for Q
impl<Q, K> Comparable<K> for Q
§impl<T> Downcast for Twhere
T: Any,
impl<T> Downcast for Twhere
T: Any,
§fn into_any(self: Box<T>) -> Box<dyn Any>
fn into_any(self: Box<T>) -> Box<dyn Any>
Box<dyn Trait> (where Trait: Downcast) to Box<dyn Any>. Box<dyn Any> can
then be further downcast into Box<ConcreteType> where ConcreteType implements Trait.§fn into_any_rc(self: Rc<T>) -> Rc<dyn Any>
fn into_any_rc(self: Rc<T>) -> Rc<dyn Any>
Rc<Trait> (where Trait: Downcast) to Rc<Any>. Rc<Any> can then be
further downcast into Rc<ConcreteType> where ConcreteType implements Trait.§fn as_any(&self) -> &(dyn Any + 'static)
fn as_any(&self) -> &(dyn Any + 'static)
&Trait (where Trait: Downcast) to &Any. This is needed since Rust cannot
generate &Any’s vtable from &Trait’s.§fn as_any_mut(&mut self) -> &mut (dyn Any + 'static)
fn as_any_mut(&mut self) -> &mut (dyn Any + 'static)
&mut Trait (where Trait: Downcast) to &Any. This is needed since Rust cannot
generate &mut Any’s vtable from &mut Trait’s.§impl<T> Downcast for Twhere
T: Any,
impl<T> Downcast for Twhere
T: Any,
§fn into_any(self: Box<T>) -> Box<dyn Any>
fn into_any(self: Box<T>) -> Box<dyn Any>
Box<dyn Trait> (where Trait: Downcast) to Box<dyn Any>, which can then be
downcast into Box<dyn ConcreteType> where ConcreteType implements Trait.§fn into_any_rc(self: Rc<T>) -> Rc<dyn Any>
fn into_any_rc(self: Rc<T>) -> Rc<dyn Any>
Rc<Trait> (where Trait: Downcast) to Rc<Any>, which can then be further
downcast into Rc<ConcreteType> where ConcreteType implements Trait.§fn as_any(&self) -> &(dyn Any + 'static)
fn as_any(&self) -> &(dyn Any + 'static)
&Trait (where Trait: Downcast) to &Any. This is needed since Rust cannot
generate &Any’s vtable from &Trait’s.§fn as_any_mut(&mut self) -> &mut (dyn Any + 'static)
fn as_any_mut(&mut self) -> &mut (dyn Any + 'static)
&mut Trait (where Trait: Downcast) to &Any. This is needed since Rust cannot
generate &mut Any’s vtable from &mut Trait’s.§impl<T> DowncastSend for T
impl<T> DowncastSend for T
§impl<T> DowncastSync for T
impl<T> DowncastSync for T
§impl<T> DowncastSync for T
impl<T> DowncastSync for T
§impl<Q, K> Equivalent<K> for Q
impl<Q, K> Equivalent<K> for Q
§fn equivalent(&self, key: &K) -> bool
fn equivalent(&self, key: &K) -> bool
key and return true if they are equal.