[−][src]Trait treelike::treelike::Treelike
The main Trait of the crate. Provides many kinds of iterations and searches on trees.
Just like Iterator most functions are provided, only children and content need to be implemented.
Should probably be implemented on references of the node-type, unless your node itself is already Copy. See LinTree for an example of that.
no_std note
The callback_* functions allow operating on the trees without allocations in a
no_std-compatible way by calling a provided function on each visited element.
This is a bit unwieldy. Additional restrictions are listed in the no_std notes for each function.
The iter_* functions allocate, but return an Iterator, providing a more comfortable
interface.
Graph warning
If you implement Treelike for anything more complex then a DAG you will run into infinite loops with the provided methods. Make sure to avoid loops or override.
Traversals and searches
Most traversals take a Filter attribute. By passing () you get a pure traversal. By filtering you get a search.
Associated Types
type Content
The content of the current node.
If the node does not always contain something make Content an Option.
type ChildIterator: Iterator<Item = Self>
You will have to specify the precise type you use for child iteration. This also implies that you have to move any closures into free standing functions. This is an Iterator over the children, not the contents of the children.
Required methods
fn children(self) -> Self::ChildIterator
Has to return an Iterator over all this nodes direct children.
The exact type sadly has to be specified in ChildIterator as impl Trait is not (yet) usable in Traits.
fn content(self) -> Self::Content
Has to produce this nodes Content.
Provided methods
fn left(self) -> Option<Self>
Returns leftmost direct child of this Node. Mostly useful for binary trees.
fn right(self) -> Option<Self>
Returns rightmost direct child of this Node. Mostly useful for binary trees.
fn first(self) -> Self::Content
Recursively traverses the tree to the very first/leftmost node.
fn last(self) -> Self::Content
Recursively traverses the tree to the very last/rightmost node.
fn callback_dft<CB: FnMut(Self::Content, usize), F: FilterBuilder<Self>>(
self,
callback: CB,
child_filter: F
)
self,
callback: CB,
child_filter: F
)
Traverses the tree depth first, post order, i.e. children's contents are visited before their parents.
The provided callback gets called on each visited node.
You can optionally provide child_filter. It is used to determine which children of a node to visit. child_filter can be anything that FilterBuilder is implemented for.
Examples
Pass () as filter to just visit all children.
node.callback_dft( |content, depth| { dbg!((content, depth)); }, (), )
Pass an Fn(Self::Content, depth: usize, child: Self) -> bool to filter.
For example stop at depth 1 and nodes with content 4:
node.callback_dft( |content, depth| { dbg!((content, depth)); }, (|content, depth, child| **content != 4 && depth <= 1) as for<'r, 's> fn(&'r &usize, usize, &'s LinTree<'_, usize>) -> _, )
no_std note
A stack is necessary for depth-first traversals. This method uses the call-stack to get around not using allocations. This should not cause additional runtime costs.
fn callback_dft_pre<CB: FnMut(Self::Content, usize), F: FilterBuilder<Self>>(
self,
callback: CB,
child_filter: F
)
self,
callback: CB,
child_filter: F
)
like callback_dft but the parents content is visited before the children's.
fn callback_bft<CB: FnMut(Self::Content, usize)>(self, callback: CB)
Traverses the tree breadth-first, i.e. one depth-layer at a time.
Example
let base = [3, 4, 5, 6, 7]; let node = LinTree::new(0, &base); let mut order = Vec::new(); node.callback_bft(|content, depth| order.push(*content)); assert_eq!(&order, &base);
Performance warning
The default implementation is no_std-compatible, using no allocations. It pays a
substantial performance price for that.
Specifically each node is visited depth - total_depth times.
Custom implementations are able and encouraged to override this if possible. LinTree for example replaces this iterating over its slice.
no_std Note
A queue is necessary for breadth-first traversals. This method repeatedly traverses to deeper and deeper depths. This causes additional runtime costs.
fn callback_bft_filtered<CB: FnMut(Self::Content, usize), F: FilterBuilder<Self>>(
self,
callback: CB,
filter: F
)
self,
callback: CB,
filter: F
)
Like callback_bft but allows filtering, thereby disallowing some optimizations.
ⓘImportant traits for DFT<T, F>fn iter_dft<F: FilterBuilder<Self>>(self, filter: F) -> DFT<Self, F>
ⓘImportant traits for DFTP<T, F>fn iter_dft_pre<F: FilterBuilder<Self>>(self, filter: F) -> DFTP<Self, F>
fn iter_bft<F: FilterBuilder<Self>>(
self,
filter: F
) -> Chain<Once<Self::Content>, BFT<Self, F>>
self,
filter: F
) -> Chain<Once<Self::Content>, BFT<Self, F>>
Implementors
impl<'a, T: Debug> Treelike for LinTree<'a, T>[src]
type Content = &'a T
type ChildIterator = FlatMap<Zip<Chain<Once<usize>, Once<usize>>, Repeat<&'a [T]>>, Option<LinTree<'a, T>>, fn(_: (usize, &'a [T])) -> Option<LinTree<'a, T>>>
fn content(self) -> Self::Content[src]
fn children(self) -> Self::ChildIterator[src]
fn callback_bft<CB: FnMut(Self::Content, usize)>(self, callback: CB)[src]
This is also an example of overriding the Treelikes default implementations where necessary. LinTree can provide breadth-first traversal with a simple iteration