Struct Node

pub struct Node<'a, T> { /* private fields */ }

A slice of a Tree<T> or PolyTree<T>.

A node is essentially the same as a tree, except it does not own its data.

Navigating the subtree of a node is done using iterators.

It is planned to add a query type that allows querying nodes from subtrees using chains of conditions. Currently only some basic iterators are available.

Implementations

impl<'a, T> Node<'a, T>

pub fn from(verts: &[Vertex<T>]) -> Result<Node<'_, T>, ValidationError>

Turns a slice of vertices into a Node<T>, after performing some validations.

Returns an error in case of a failed validation. For the possible errors see ValidationError. For a more detailed description of the validation process see the safety section for from_unchecked.

To avoid running the validations; which have a significant cost for large trees; use the unsafe alternative from_unchecked.

pub unsafe fn from_unchecked(verts: &[Vertex<T>]) -> Node<'_, T>

Returns a slice of vertices as a Node<T>.

This is the unsafe alternative to from that skips all validations.

Safety

The caller must guarantee that all expected qualities of the vertex slice are fulfilled.

1. The vertex slice must not be empty.

2. The first vertex must span the entire slice.

   This means that the len of the first vertex is equal to verts.len() - 1.

3. The scope of all vertices must be contained within the scope of its parent vertex

   Here scope refers to the range starting from a nodes index to the nodes index plus its len inclusive.

pub fn data(self) -> &'a T

Returns a reference to the payload of the node.

pub fn rank(self) -> usize

Returns the rank of the node in the tree. The rank can be used to look up the node from the tree using get.

The rank also exposes information about the structure of the tree. Any node child with a rank greater than that of a node parent but not exceeding parent.rank() + parent.len() is a descendant of parent.

pub fn len(self) -> usize

Returns the number of descending nodes within the subtree of this node. A leaf node returns length 0.

pub fn is_empty(self) -> bool

Returns true if the node has no child nodes.

pub fn get(self, rank: usize) -> Option<Node<'a, T>>

Returns the node with the specified rank.

The rank must be relative to the trees root, or the most recently pruned node. See isolated for more information.

pub fn parent(self) -> Option<Node<'a, T>>

Returns the parent of the node or None if it does not have one.

pub fn children(self) -> Children<'a, T>

Returns an iterator over the child nodes of the node. See Children for more information about the iterator.

pub fn descendants(self) -> Descendants<'a, T>

Returns a depth first iterator of nodes. It iterates all nodes in the subtree of the node, including the node itself. See Descendants for more information about the iterator.

pub fn ancestors(self) -> Ancestors<'a, T>

Returns an iterator over the parent nodes. The parent of the node is first. The root of the tree is last. See Ancestors for more information about the iterator.

pub fn as_slice(self) -> &'a [Vertex<T>]

Returns the nodes internal vertex slice.

pub fn isolated(self) -> Node<'a, T>

Returns the node isolated from the rest of the tree.

An isolated node will always have rank 0, and it will be impossible to access its ancestors. It is still possible to explore the subtree below the node.

When getting nodes by rank you must get them from this or any descending node. If you use the rank in a node that is not affected by this isolation, it will return some other node. Think of the isolated node as an entirely new tree with its own ranking.

pub fn into_tree(self) -> Tree<T>

where T: Clone,

Clones the contents of the node into a new Tree<T>.

Similar to push_node this operation is cheaper if T implements Copy. It is internally based on Vec::extend_from_slice.

Trait Implementations

impl<'a, T> Clone for Node<'a, T>

fn clone(&self) -> Self

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<'a, T: Debug> Debug for Node<'a, T>

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

Formats the value using the given formatter.

impl<'a, T> Copy for Node<'a, T>