Struct PathTree

pub struct PathTree<T>
where
    T: PathTreeTypes,
{ /* private fields */ }

Cheaply clonable path tree structure.

Could be shared safely between multiple threads.

Implementations

impl<T: PathTreeTypes> PathTree<T>

pub fn new(new_node_id: T::NewNodeId, root_node_value: NodeValue<T>) -> Self

Create a new path tree with the given root node.

pub const fn root_node_id(&self) -> T::NodeId

pub fn root_node(&self) -> &Arc<TreeNode<T>>

pub fn lookup_node(&self, id: T::NodeId) -> Option<&Arc<TreeNode<T>>>

pub fn find_node(&self, path: &T::RootPath) -> Option<&Arc<TreeNode<T>>>

Find a node by its path.

pub fn contains_node(&self, node: &Arc<TreeNode<T>>) -> bool

pub fn resolve_node_path<'a>( &'a self, path: &T::RootPath, match_path: MatchNodePath, ) -> Option<NodePathResolved<'a, T>>

Find a node by its path.

Returns the found node and the number of resolved path segments.

pub fn insert_or_update_node_value( &mut self, path: &T::RootPath, new_value: NodeValue<T>, new_inner_value: &mut impl FnMut() -> T::InnerValue, try_clone_leaf_into_inner_value: impl FnOnce(&T::LeafValue) -> Option<T::InnerValue>, ) -> Result<NodeInsertedOrUpdated<T>, InsertOrUpdateNodeValueError<T>>

Insert or update a node in the tree.

All missing parent nodes are created recursively and initialized with the value returned by new_inner_value.

If the parent node exists and is a leaf node then it is replaced with an inner node by calling try_clone_leaf_into_inner_value.

Returns the updated parent node and the inserted/updated child node. The parent node is None if the root node has been updated.

In case of an error, the new value is returned back to the caller.

pub fn insert_or_update_child_node_value( &mut self, parent_node: &Arc<TreeNode<T>>, child_path_segment: &T::PathSegment, old_child_path_segment: Option<&T::PathSegment>, new_value: NodeValue<T>, ) -> Result<NodeInsertedOrUpdated<T>, InsertOrUpdateNodeValueError<T>>

Insert or update a child node in the tree.

The parent node must exist and it must be an inner node.

By providing old_child_path_segment an existing node could be renamed and updated. This will retain its NodeId.

Returns the updated parent node and the inserted/updated child node.

In case of an error, the new value is returned back to the caller.

pub fn update_node_value( &mut self, node: &Arc<TreeNode<T>>, new_value: NodeValue<T>, ) -> Result<Arc<TreeNode<T>>, UpdateNodeValueError<T>>

Update a node value in the tree.

Inner nodes with children could only be updated with an inner value.

Returns the updated node with the new value.

In case of an error, the new value is returned back to the caller.

Undefined behavior if the given node does not belong to the tree. This precondition is only checked by debug assertions.

pub fn remove_subtree_by_id( &mut self, node_id: T::NodeId, ) -> Option<SubtreeRemoved<T>>

Remove a node and its children from the tree.

Removes and returns the entire subtree rooted at the given node.

The root node cannot be removed and the tree remains unchanged.

Returns the removed subtree or None if unchanged. The node ids in the removed subtree remain unchanged.

pub fn insert_or_replace_subtree( &mut self, parent_node: &Arc<TreeNode<T>>, child_path_segment: &T::PathSegment, old_child_path_segment: Option<&T::PathSegment>, subtree: Self, ) -> Result<SubtreeInsertedOrReplaced<T>, InsertOrUpdateNodeValueError<T>>

Insert a subtree.

The root node of the subtree will replace an existing node. The existing node must node have any children, otherwise the insertion will fail.

The inserted nodes from the subtree will be assigned new ids that are generated by this tree.

By providing old_child_path_segment an existing node could be renamed and replaced by the subtree. This will retain its NodeId.

pub fn retain_nodes(&mut self, predicate: impl FnMut(&TreeNode<T>) -> bool)

Retain only the nodes that match the given predicate.

The root node is always retained and cannot be removed.

Returns the number of nodes that have been removed.

pub fn nodes(&self) -> impl ExactSizeIterator<Item = &Arc<TreeNode<T>>>

All nodes in no particular order.

pub fn nodes_count(&self) -> NonZeroUsize

Total number of nodes in the tree.

Executed in constant time, i.e. O(1). But only if not both debug assertions and the feature “expensive-debug-assertions” are enabled.

pub fn ancestor_nodes<'a>( &'a self, node: &'a Arc<TreeNode<T>>, ) -> impl Iterator<Item = HalfEdgeTreeNode<'_, T>> + Clone

Iterator over all ancestor nodes of the given node.

Returns the parent node and the respective path segment from the child node in bottom-up order.

pub fn ancestor_nodes_count(&self, node: &Arc<TreeNode<T>>) -> usize

The number of parent nodes of the given node up to the root node.

pub fn descendant_nodes<'a>( &'a self, node: &'a Arc<TreeNode<T>>, ) -> impl Iterator<Item = HalfEdge<'a, T>>

Returns an iterator over all descendants of this node

Recursively traverses the subtree.

The ordering of nodes is undefined and an implementation detail. Only parent nodes are guaranteed to be visited before their children.

pub fn descendant_nodes_count(&self, node: &Arc<TreeNode<T>>) -> usize

Number of child nodes of the given node (recursively).

Trait Implementations

impl<T> Clone for PathTree<T>

where T: PathTreeTypes + Clone, T::NodeId: Clone, T::NewNodeId: Clone,

fn clone(&self) -> PathTree<T>

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<T> Debug for PathTree<T>

where T: PathTreeTypes + Debug, T::NodeId: Debug, T::NewNodeId: Debug,

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

Formats the value using the given formatter.