Module splashsurf_lib::generic_tree

Generic tree visitation functions that can be used with tree-like structures

In order to use these algorithms, the data structure has to implement the TreeNode and for mutable access the TreeNodeMut trait. These traits only require to give access to a slice of child nodes of a node.

This module provides algorithms for breadth-first and depth-first visitation. Overview of the traits:

• VisitableTree provides non-mutable sequential iteration.
• MutVisitableTree provides sequential visitation using a visitor function with mutable access to the current node.
• ParVisitableTree provides parallel visitation using a visitor function, parallelized using rayon.
• ParMutVisitableTree provides parallel visitation using a visitor function with mutable access to the current node, parallelized using rayon.

Note that the mutation of nodes during visitation is safe as the mutation is only possible either before the children are enqueued or after the children were already processed.

Structs

• BfsIter
  Breadth-first search iterator returned by the VisitableTree::bfs_iter function
• DfsIter
  Depth-first search iterator returned by the VisitableTree::dfs_iter function

Traits

• MutVisitableTree
  Trait for sequential tree visitation algorithms that support mutation during visitation. Automatically implemented for types that implement TreeNodeMut.
• ParMutVisitableTree
  Trait for mutable parallel tree visitation algorithms. Automatically implemented for types that implement TreeNodeMut and ThreadSafe.
• ParVisitableTree
  Trait for non-mutable parallel tree visitation algorithms. Automatically implemented for types that implement TreeNode and ThreadSafe.
• TreeNode
  Trait that has to be implemented by tree-like structures to make them visitable
• TreeNodeMut
  Trait that has to be implemented by tree-like structures to visit and mutate them
• VisitableTree
  Trait for non-mutable sequential tree iteration algorithms. Automatically implemented for types that implement TreeNode.