search method

TreeSearchResult<T> search(ValuePredicate<T> predicate)

Traverses the tree looking for nodes that match the given predicate.

The returned TreeSearchResult contains all direct and indirect matches, i.e., a direct match means the predicate returned true for that given node, and an indirect match means the given node is not a match, but it has one or more matching nodes in its subtree.

The absence of a node in TreeSearchResult.matches.keys means that itself as well as its entire subtree didn't match the search predicate, or the given node was not reached during tree traversal.

Implementation

TreeSearchResult<T> search(ValuePredicate<T> predicate) {
  final Map<T, TreeSearchMatch> allMatches = <T, TreeSearchMatch>{};

  (int subtreeNodeCount, int subtreeMatchCount) traverse(Iterable<T> nodes) {
    int totalNodeCount = 0;
    int totalMatchCount = 0;

    for (final T child in nodes) {
      if (predicate(child)) {
        totalMatchCount++;
        allMatches[child] = const TreeSearchMatch();
      }

      final (int nodes, int matches) = traverse(childrenProvider(child));
      totalNodeCount += nodes + 1;
      totalMatchCount += matches;

      if (matches > 0) {
        allMatches[child] = TreeSearchMatch(
          isDirectMatch: allMatches[child]?.isDirectMatch ?? false,
          subtreeNodeCount: nodes,
          subtreeMatchCount: matches,
        );
      }
    }
    return (totalNodeCount, totalMatchCount);
  }

  final (int totalNodeCount, int totalMatchCount) = traverse(roots);
  return TreeSearchResult<T>(
    matches: allMatches,
    totalNodeCount: totalNodeCount,
    totalMatchCount: totalMatchCount,
  );
}