breadthFirstSearch method
- Iterable<
T> ? startingNodes, - DescendCondition<
T> descendCondition = alwaysReturnsTrue, - ReturnCondition<
T> returnCondition = alwaysReturnsFalse, - Visitor<
T> ? onTraverse,
Traverses the subtrees of startingNodes
in breadth first order. If
startingNodes
is not provided, roots will be used instead.
descendCondition
is used to determine if the descendants of the node
passed to it should be traversed. When not provided, defaults to
alwaysReturnsTrue, a function that always returns true
which leads
to every node on the tree being visited by this traversal.
returnCondition
is used as a predicate to decide if the iteration should
be stopped. If this callback returns true
the node that was passed to
it is returned from this method. When not provided, defaults to
alwaysReturnsFalse, a function that always returns false
which leads
to every node on the tree being visited by this traversal.
An optional onTraverse
callback can be provided to apply an action to
each visited node. This callback is called prior to returnCondition
and
descendCondition
making it possible to update a node before checking
its properties.
Implementation
T? breadthFirstSearch({
Iterable<T>? startingNodes,
DescendCondition<T> descendCondition = alwaysReturnsTrue,
ReturnCondition<T> returnCondition = alwaysReturnsFalse,
Visitor<T>? onTraverse,
}) {
final List<T> nodes = List<T>.of(startingNodes ?? roots);
while (nodes.isNotEmpty) {
final T node = nodes.removeAt(0);
onTraverse?.call(node);
if (returnCondition(node)) {
return node;
}
if (descendCondition(node)) {
nodes.addAll(childrenProvider(node));
}
}
return null;
}