Skip to content

Proposal for hybridApplyToTree()

This MR presents a refactor on the AccumulateValue meta-algorithms. The idea here is to be able to accumulate values and types at compile- and run-time depending on the tree. In other words, a hybrid traversal. To do so, I implemented hybridApplyToTree, a similar algorithm as in applyToTree with some key differences:

  • An initial value is always passed to the algorithm and to the visitor
  • The visitor returns a transformed value.
  • The result is always piped into the next operation.

Loops are much more complicated than a simple forEach because the resulting type may change on every loop. This is why I created the utility named left_fold, which applies a binary operator over a pack of indices while piping the results to the next binary operation.

Naturally, this resolves #12 (closed) since now we have hybrid accumulations on the tree. The nodeCount, leafCount, and isDynamic are the perfect showcase of how this algorithm works.


Example of usage: Declare a hybrid visitor (almost the same interface as what we are used to but it has an extra argument which is the carried value):

struct DynamicDepthVisitor
  : public DefaultHybridVisitor
  , public StaticTraversal
  , public VisitTree
{
  template<class Tree, class TreePath, class Carry>
  auto leaf(Tree&&, TreePath, Carry carry) const
  {
    std::size_t current_depth = treePathSize(TreePath{});
    current_depth += 1; // the TreePath is always one entry shorter than the actual depth of the tree
    return std::max(carry, current_depth);
  }
};

Once a visitor is defined, it could be traversed doing a depth-first traversal accumulation (same as in traversal applyToTree). The algorithm requires a tree, a visitor and an initial value.

std::size_t depth = hybridApplyToTree(tree, DynamicDepthVisitor{}, 0);

If we already have a depth-first traversal, why this is needed? The carried value type Carry may be transformed while doing the traversal. This is done with the return value of the visitor function. For example,

struct StaticDepthVisitor
  : public DefaultHybridVisitor
  , public StaticTraversal
  , public VisitTree
{
  template<class Tree, class TreePath, class Carry>
  auto leaf(Tree&&, TreePath, Carry) const
  {
    constexpr std::size_t current_depth = treePathSize(TreePath{}) + 1;
    // carry is an integral constant so we can use it at compile time
    auto new_depth = std::integral constant<std::size_t, std::max(Carry::value, current_depth)>{};
    // return type is entirely different from carried value
    return new_depth;
  }
};

The type carried in StaticDepthVisitor is different between applications of the visitor and therefore we can make static accumulations with integral types very easily...

auto depth = hybridApplyToTree(tree, StaticDepthVisitor{}, std::integral_constant<std::size_t,0>{});

Closes #12 (closed)

Edited by Santiago Ospina De Los Ríos

Merge request reports