Struct ForkTree

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

Tree of nodes. Each node contains a value of type T.

Implementations

impl<T> ForkTree<T>

pub fn new() -> Self

Initializes a new ForkTree.

pub fn with_capacity(cap: usize) -> Self

Initializes a new ForkTree with a certain pre-allocated capacity.

pub fn reserve(&mut self, additional: usize)

Reserves additional capacity for at least additional new blocks without allocating.

pub fn clear(&mut self)

Removes all elements in the tree, leaving it empty.

pub fn shrink_to_fit(&mut self)

Shrink the capacity of the tree as much as possible.

pub fn is_empty(&self) -> bool

Returns true if there isn’t any element in the tree.

pub fn len(&self) -> usize

Returns the number of elements in the tree.

pub fn iter_unordered(&self) -> impl Iterator<Item = (NodeIndex, &T)>

Returns an iterator to all the node values without any specific order.

pub fn iter_ancestry_order(&self) -> impl Iterator<Item = (NodeIndex, &T)>

Returns an iterator to all the node values. The returned items are guaranteed to be in an order in which the parents are found before their children.

pub fn contains(&self, index: NodeIndex) -> bool

Returns true if the given NodeIndex is valid.

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

Returns the value of the node with the given index.

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

Returns the value of the node with the given index.

pub fn map<U>(self, map: impl FnMut(T) -> U) -> ForkTree<U>

Modifies all the block user datas and returns a new map.

The returned tree keeps the same NodeIndexes as self.

pub fn ancestors(&self, node: NodeIndex) -> impl Iterator<Item = NodeIndex>

Returns the ancestors of the given node. The iterator is empty if the node doesn’t have any parent.

Panic

Panics if the NodeIndex is invalid.

pub fn parent(&self, node: NodeIndex) -> Option<NodeIndex>

Returns the parent of the given node. Returns None if the node doesn’t have any parent.

Panic

Panics if the NodeIndex is invalid.

pub fn children( &self, node: Option<NodeIndex>, ) -> impl Iterator<Item = NodeIndex>

Returns the list of children that have the given node as parent.

Panic

Panics if the NodeIndex is invalid.

pub fn prune_ancestors( &mut self, node_index: NodeIndex, ) -> PruneAncestorsIter<'_, T>

Removes from the tree:

• The node passed as parameter.
• The ancestors of the node passed as parameter.
• Any node not a descendant of the node passed as parameter.

Returns an iterator containing the removed elements. All elements are removed from the tree even if the returned iterator is dropped eagerly.

Elements are returned in an unspecified order. However, each element yielded is guaranteed to be yielded before its parent gets yielded. This can be more or less called “reverse hierarchical order”.

In other words, doing prune_ancestors(...).filter(|n| n.is_prune_target_ancestor) is guaranteed to return the elements in the same order as ForkTree::node_to_root_path does.

Panic

Panics if the NodeIndex is invalid.

pub fn prune_uncles( &mut self, node_index: NodeIndex, ) -> PruneAncestorsIter<'_, T>

Removes from the tree any node that isn’t either an ancestor or a descendant of the target node.

This function is similar to ForkTree::prune_ancestors, except that all nodes returned by the iterator are guaranteed to have PrunedNode::is_prune_target_ancestor equal to false.

Panic

Panics if the NodeIndex is invalid.

pub fn common_ancestor( &self, node1: NodeIndex, node2: NodeIndex, ) -> Option<NodeIndex>

Returns the common ancestor between node1 and node2, if any is known.

Panic

Panics if one of the NodeIndexs is invalid.

pub fn is_ancestor( &self, maybe_ancestor: NodeIndex, maybe_descendant: NodeIndex, ) -> bool

Returns true if maybe_ancestor is an ancestor of maybe_descendant. Also returns true if the two NodeIndex are equal.

Panic

Panics if one of the NodeIndexs is invalid.

pub fn ascend_and_descend( &self, node1: NodeIndex, node2: NodeIndex, ) -> (impl Iterator<Item = NodeIndex> + Clone, impl Iterator<Item = NodeIndex> + Clone)

Returns two iterators: the first iterator enumerates the nodes from node1 to the common ancestor of node1 and node2. The second iterator enumerates the nodes from that common ancestor to node2. The common ancestor isn’t included in either iterator. If node1 and node2 are equal then both iterators are empty, otherwise node1 is always included in the first iterator and node2 always included in the second iterator.

Panic

Panics if one of the NodeIndexs is invalid.

pub fn node_to_root_path( &self, node_index: NodeIndex, ) -> impl Iterator<Item = NodeIndex> + Clone

Enumerates all the nodes, starting from the given node, to the root. Each element returned by the iterator is a parent of the previous one. The iterator does include the node itself.

Panic

Panics if the NodeIndex is invalid.

pub fn root_to_node_path( &self, node_index: NodeIndex, ) -> impl Iterator<Item = NodeIndex> + Clone

Same as ForkTree::node_to_root_path, but gives the path in the reverse order.

Panic

Panics if the NodeIndex is invalid.

pub fn find(&self, cond: impl FnMut(&T) -> bool) -> Option<NodeIndex>

Finds the first node in the tree that matches the given condition.

pub fn insert(&mut self, parent: Option<NodeIndex>, child: T) -> NodeIndex

Inserts a new node in the tree.

Panic

Panics if parent isn’t a valid node index.

Trait Implementations

impl<T> Debug for ForkTree<T>

where T: Debug,

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

Formats the value using the given formatter.

impl<T> Default for ForkTree<T>

fn default() -> Self

Returns the “default value” for a type.