pub struct NodeId { /* private fields */ }
Expand description
Implementations§
source§impl NodeId
impl NodeId
sourcepub fn is_removed<T>(self, arena: &Arena<T>) -> bool
pub fn is_removed<T>(self, arena: &Arena<T>) -> bool
Return if the Node
of NodeId point to is removed.
sourcepub 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);
Examples found in repository?
3 4 5 6 7 8 9 10 11 12 13 14
pub fn main() {
// Create a new arena
let arena = &mut Arena::new();
// Add some new nodes to the arena
let a = arena.new_node(1);
let b = arena.new_node(2);
// Append a to b
a.append(b, arena);
assert_eq!(b.ancestors(arena).count(), 2);
}
sourcepub 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);
sourcepub 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);
sourcepub 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);
sourcepub 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);
sourcepub fn reverse_children<T>(self, arena: &Arena<T>) -> ReverseChildren<'_, T> ⓘ
pub fn reverse_children<T>(self, arena: &Arena<T>) -> ReverseChildren<'_, T> ⓘ
Returns an iterator of IDs of this node’s children, in reverse order.
§Examples
// arena
// `-- 1
// |-- 1_1 // #3
// | `-- 1_1_1
// |-- 1_2 // #2
// `-- 1_3 // #1
let mut iter = n1.reverse_children(&arena);
assert_eq!(iter.next(), Some(n1_3)); // #1
assert_eq!(iter.next(), Some(n1_2)); // #2
assert_eq!(iter.next(), Some(n1_1)); // #3
assert_eq!(iter.next(), None);
sourcepub 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);
sourcepub 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);
sourcepub 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);
sourcepub 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.
§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);
sourcepub 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
remove
d.
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);
Examples found in repository?
3 4 5 6 7 8 9 10 11 12 13 14
pub fn main() {
// Create a new arena
let arena = &mut Arena::new();
// Add some new nodes to the arena
let a = arena.new_node(1);
let b = arena.new_node(2);
// Append a to b
a.append(b, arena);
assert_eq!(b.ancestors(arena).count(), 2);
}
sourcepub 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 orself
isremove
d.
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());
sourcepub 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.
§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);
sourcepub 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
remove
d.
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);
sourcepub 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 orself
isremove
d.
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());
sourcepub 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
, or - the current node or the given new sibling was already
remove
d.
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);
sourcepub 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 orself
isremove
d.
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());
sourcepub 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
, or - the current node or the given new sibling was already
remove
d.
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);
sourcepub 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 orself
isremove
d.
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());
sourcepub 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()
.
§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);
sourcepub 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.
§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);
sourcepub 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. Node 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§
source§impl Into<NonZero<usize>> for NodeId
impl Into<NonZero<usize>> for NodeId
source§fn into(self) -> NonZeroUsize
fn into(self) -> NonZeroUsize
source§impl Ord for NodeId
impl Ord for NodeId
source§impl PartialEq for NodeId
impl PartialEq for NodeId
source§impl PartialOrd for NodeId
impl PartialOrd for NodeId
1.0.0 · source§fn le(&self, other: &Rhs) -> bool
fn le(&self, other: &Rhs) -> bool
self
and other
) and is used by the <=
operator. Read more