accumulate_static.hh

// -*- tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*-
// vi: set et ts=4 sw=2 sts=2:
 
#ifndef DUNE_TYPETREE_ACCUMULATE_STATIC_HH
#define DUNE_TYPETREE_ACCUMULATE_STATIC_HH
 
#include <dune/common/typetraits.hh>
#include <dune/typetree/nodeinterface.hh>
#include <dune/typetree/nodetags.hh>
#include <dune/typetree/treepath.hh>
 
 
namespace Dune {
  namespace TypeTree {
 
    template<typename result_type>
    struct or_
    {
      template<result_type r1, result_type r2>
      struct reduce
      {
        static const result_type result = r1 || r2;
      };
    };
 
    template<typename result_type>
    struct and_
    {
      template<result_type r1, result_type r2>
      struct reduce
      {
        static const result_type result = r1 && r2;
      };
    };
 
    template<typename result_type>
    struct plus
    {
      template<result_type r1, result_type r2>
      struct reduce
      {
        static const result_type result = r1 + r2;
      };
    };
 
    template<typename result_type>
    struct minus
    {
      template<result_type r1, result_type r2>
      struct reduce
      {
        static const result_type result = r1 - r2;
      };
    };
 
    template<typename result_type>
    struct multiply
    {
      template<result_type r1, result_type r2>
      struct reduce
      {
        static const result_type result = r1 * r2;
      };
    };
 
    template<typename result_type>
    struct min
    {
      template<result_type r1, result_type r2>
      struct reduce
      {
        static const result_type result = r1 < r2 ? r1 : r2;
      };
    };
 
    template<typename result_type>
    struct max
    {
      template<result_type r1, result_type r2>
      struct reduce
      {
        static const result_type result = r1 > r2 ? r1 : r2;
      };
    };
 
 
    namespace {
 
      // implementation of the traversal algorithm
 
      template<typename Node, typename Functor, typename Reduction, typename Functor::result_type current_value, typename TreePath, bool doVisit>
      struct accumulate_node_helper
      {
 
        typedef typename Functor::result_type result_type;
 
        static const result_type result = current_value;
 
      };
 
      template<typename Node, typename Functor, typename Reduction, typename Functor::result_type current_value, typename TreePath>
      struct accumulate_node_helper<Node,Functor,Reduction,current_value,TreePath,true>
      {
 
        typedef typename Functor::result_type result_type;
 
        static const result_type result = Reduction::template reduce<current_value,Functor::template visit<Node,TreePath>::result>::result;
 
      };
 
      template<typename Tree, typename Functor, typename Reduction, typename ParentChildReduction, typename Functor::result_type current_value, typename TreePath, typename Tag>
      struct accumulate_value;
 
      template<typename LeafNode, typename Functor, typename Reduction, typename ParentChildReduction, typename Functor::result_type current_value, typename TreePath>
      struct accumulate_value<LeafNode,Functor,Reduction,ParentChildReduction,current_value,TreePath,LeafNodeTag>
      {
 
        typedef typename Functor::result_type result_type;
 
        static const result_type result =
 
          accumulate_node_helper<LeafNode,Functor,Reduction,current_value,TreePath,Functor::template doVisit<LeafNode,TreePath>::value>::result;
 
      };
 
      template<typename Node, typename Functor, typename Reduction, typename ParentChildReduction, typename Functor::result_type current_value, typename TreePath, std::size_t i, std::size_t n>
      struct accumulate_over_children
      {
 
        typedef typename Functor::result_type result_type;
 
        typedef decltype(push_back(TreePath{},index_constant<i>{})) child_tree_path;
 
        typedef typename Node::template Child<i>::Type child;
 
        static const result_type child_result = accumulate_value<child,Functor,Reduction,ParentChildReduction,current_value,child_tree_path,NodeTag<child>>::result;
 
        static const result_type result = accumulate_over_children<Node,Functor,Reduction,ParentChildReduction,child_result,TreePath,i+1,n>::result;
 
      };
 
      template<typename Node, typename Functor, typename Reduction, typename ParentChildReduction, typename Functor::result_type current_value, typename TreePath, std::size_t n>
      struct accumulate_over_children<Node,Functor,Reduction,ParentChildReduction,current_value,TreePath,n,n>
      {
 
        typedef typename Functor::result_type result_type;
 
        static const result_type result = current_value;
 
      };
 
      template<typename Node, typename Functor, typename Reduction, typename ParentChildReduction, typename Functor::result_type current_value, typename TreePath>
      struct accumulate_value_generic_composite_node
      {
 
        typedef typename Functor::result_type result_type;
 
        static const result_type child_result = accumulate_over_children<Node,Functor,Reduction,ParentChildReduction,current_value,TreePath,0,StaticDegree<Node>::value>::result;
 
        static const result_type result =
          accumulate_node_helper<Node,Functor,ParentChildReduction,child_result,TreePath,Functor::template doVisit<Node,TreePath>::value>::result;
 
 
      };
 
      template<typename PowerNode, typename Functor, typename Reduction, typename ParentChildReduction, typename Functor::result_type current_value, typename TreePath>
      struct accumulate_value<PowerNode,Functor,Reduction,ParentChildReduction,current_value,TreePath,PowerNodeTag>
        : public accumulate_value_generic_composite_node<PowerNode,Functor,Reduction,ParentChildReduction,current_value,TreePath>
      {};
 
      template<typename CompositeNode, typename Functor, typename Reduction, typename ParentChildReduction, typename Functor::result_type current_value, typename TreePath>
      struct accumulate_value<CompositeNode,Functor,Reduction,ParentChildReduction,current_value,TreePath,CompositeNodeTag>
        : public accumulate_value_generic_composite_node<CompositeNode,Functor,Reduction,ParentChildReduction,current_value,TreePath>
      {};
 
    } // anonymous namespace
 
 
    template<typename Tree, typename Functor, typename Reduction, typename Functor::result_type startValue, typename ParentChildReduction = Reduction>
    struct AccumulateValue
    {
 
      typedef typename Functor::result_type result_type;
 
      static const result_type result = accumulate_value<Tree,Functor,Reduction,ParentChildReduction,startValue,HybridTreePath<>,NodeTag<Tree>>::result;
 
    };
 
    struct flattened_reduction;
 
    struct bottom_up_reduction;
 
    namespace {
 
      // implementation of the traversal algorithm
 
      template<typename Node, typename Functor, typename Reduction, typename current_type, typename TreePath, bool doVisit>
      struct accumulate_type_node_helper
      {
 
        typedef current_type type;
 
      };
 
      template<typename Node, typename Functor, typename Reduction, typename current_type, typename TreePath>
      struct accumulate_type_node_helper<Node,Functor,Reduction,current_type,TreePath,true>
      {
 
        typedef typename Reduction::template reduce<
          current_type,
          typename Functor::template visit<
            Node,
            TreePath
            >::type
          >::type type;
 
      };
 
      template<typename Tree, typename Policy, typename current_type, typename TreePath, typename Tag>
      struct accumulate_type;
 
      template<typename LeafNode, typename Policy, typename current_type, typename TreePath>
      struct accumulate_type<LeafNode,Policy,current_type,TreePath,LeafNodeTag>
      {
 
        typedef typename accumulate_type_node_helper<
          LeafNode,
          typename Policy::functor,
          typename Policy::sibling_reduction,
          current_type,
          TreePath,
          Policy::functor::template doVisit<
            LeafNode,
            TreePath>::value
          >::type type;
 
      };
 
 
      template<typename current_type, typename tree_path, typename start_type, typename reduction_strategy>
      struct propagate_type_down_tree;
 
      template<typename current_type, typename tree_path, typename start_type>
      struct propagate_type_down_tree<
        current_type,
        tree_path,
        start_type,
        bottom_up_reduction
        >
      {
        typedef current_type type;
      };
 
      template<typename current_type, typename tree_path, typename start_type>
      struct propagate_type_down_tree<
        current_type,
        tree_path,
        start_type,
        flattened_reduction
        >
      {
        typedef typename std::conditional<
          TreePathBack<tree_path>::value == 0,
          start_type,
          current_type
          >::type type;
      };
 
 
      template<typename Node, typename Policy, typename current_type, typename TreePath, std::size_t i, std::size_t n>
      struct accumulate_type_over_children
      {
 
        typedef decltype(push_back(TreePath{},index_constant<i>{})) child_tree_path;
 
        typedef typename Node::template Child<i>::Type child;
 
        typedef typename accumulate_type<
          child,
          Policy,
          // apply reduction choice (flat / hierarchic)
          typename propagate_type_down_tree<
            current_type,
            child_tree_path,
            typename Policy::start_type,
            typename Policy::reduction_strategy
            >::type,
          child_tree_path,
          NodeTag<child>
          >::type child_result_type;
 
        typedef typename accumulate_type_over_children<
          Node,
          Policy,
          child_result_type,
          TreePath,
          i+1,
          n
          >::type type;
 
      };
 
      template<typename Node, typename Policy, typename current_type, typename TreePath, std::size_t n>
      struct accumulate_type_over_children<Node,Policy,current_type,TreePath,n,n>
      {
 
        typedef current_type type;
 
      };
 
 
      template<typename Node, typename Policy, typename current_type, typename TreePath>
      struct accumulate_type_generic_composite_node
      {
 
        typedef typename accumulate_type_over_children<
          Node,
          Policy,
          current_type,
          TreePath,
          0,
          StaticDegree<Node>::value
          >::type children_result_type;
 
        typedef typename accumulate_type_node_helper<
          Node,
          typename Policy::functor,
          typename Policy::parent_child_reduction,
          children_result_type,
          TreePath,
          Policy::functor::template doVisit<
            Node,
            TreePath
            >::value
          >::type type;
 
      };
 
      template<typename PowerNode, typename Policy, typename current_type, typename TreePath>
      struct accumulate_type<PowerNode,Policy,current_type,TreePath,PowerNodeTag>
        : public accumulate_type_generic_composite_node<PowerNode,Policy,current_type,TreePath>
      {};
 
      template<typename CompositeNode, typename Policy, typename current_type, typename TreePath>
      struct accumulate_type<CompositeNode,Policy,current_type,TreePath,CompositeNodeTag>
        : public accumulate_type_generic_composite_node<CompositeNode,Policy,current_type,TreePath>
      {};
 
    } // anonymous namespace
 
 
    template<
      typename Functor,
      typename Reduction,
      typename StartType,
      typename ParentChildReduction = Reduction,
      typename ReductionAlgorithm = flattened_reduction
      >
    struct TypeAccumulationPolicy
    {
 
      typedef Functor functor;
 
      typedef Reduction sibling_reduction;
 
      typedef ParentChildReduction parent_child_reduction;
 
      typedef StartType start_type;
 
      typedef ReductionAlgorithm reduction_strategy;
    };
 
 
 
    template<typename Tree, typename Policy>
    struct AccumulateType
    {
 
      typedef typename accumulate_type<
        Tree,
        Policy,
        typename Policy::start_type,
        HybridTreePath<>,
        NodeTag<Tree>
        >::type type;
 
    };
 
 
 
 
 
    /***************************************************/
 
    namespace Experimental {
      namespace Impl {
 
        template<class T, class TreePath, class V, class U,
          std::enable_if_t<std::decay_t<T>::isLeaf, int> = 0>
        auto hybridApplyToTree(T&& tree, TreePath treePath, V&& visitor, U&& current_val)
        {
          return visitor.leaf(tree, treePath, std::forward<U>(current_val));
        }
 
        template<class T, class TreePath, class V, class U,
          std::enable_if_t<not std::decay_t<T>::isLeaf, int> = 0>
        auto hybridApplyToTree(T&& tree, TreePath treePath, V&& visitor, U&& current_val)
        {
          using Tree = std::remove_reference_t<T>;
          using Visitor = std::remove_reference_t<V>;
          auto pre_val = visitor.pre(tree, treePath, std::forward<U>(current_val));
 
          // check which type of traversal is supported by the tree
          using allowDynamicTraversal = Dune::Std::is_detected<Detail::DynamicTraversalConcept,Tree>;
          using allowStaticTraversal = Dune::Std::is_detected<Detail::StaticTraversalConcept,Tree>;
 
          // the tree must support either dynamic or static traversal
          static_assert(allowDynamicTraversal::value || allowStaticTraversal::value);
 
          // the visitor may specify preferred dynamic traversal
          using preferDynamicTraversal = std::bool_constant<Visitor::treePathType == TreePathType::dynamic>;
 
          // declare rule that applies visitor and current value to a child i. Returns next value
          auto apply_i = [&](auto&& value, const auto& i){
            auto&& child = tree.child(i);
            using Child = std::decay_t<decltype(child)>;
 
            auto val_before = visitor.beforeChild(tree, child, treePath, i, std::move(value));
 
            // visits between children
            auto val_in = Hybrid::ifElse(
              Hybrid::equals(i,Indices::_0),
                [&](auto id){return std::move(val_before);},
                [&](auto id){return visitor.in(tree, treePath, std::move(val_before));}
            );
 
            constexpr bool visitChild = Visitor::template VisitChild<Tree,Child,TreePath>::value;
            auto val_visit = [&](){
              if constexpr (visitChild) {
                auto childTreePath = Dune::TypeTree::push_back(treePath, i);
                return hybridApplyToTree(child, childTreePath, visitor, std::move(val_in));
              }
              else
                return std::move(val_in);
            }();
 
            return visitor.afterChild(tree, child, treePath, i, std::move(val_visit));
          };
 
          // apply visitor to children
          auto in_val = [&](){
            if constexpr (allowStaticTraversal::value && not preferDynamicTraversal::value) {
              // get list of static indices
              auto indices = std::make_index_sequence<Tree::degree()>{};
 
              // unfold apply_i left to right
              return unpackIntegerSequence([&](auto... i) {
                return left_fold(std::move(apply_i),std::move(pre_val), i...);
              }, indices);
 
            } else {
              // unfold first child to get type
              auto i_val = apply_i(std::move(pre_val),std::size_t{0});
              // dynamically loop rest of the children to accumulate remindng values
              for(std::size_t i = 1; i < tree.degree(); i++)
                i_val = apply_i(i_val,i);
              return i_val;
            }
          }();
 
          return visitor.post(tree, treePath, in_val);
        }
 
      }
 
      template<typename Tree, typename Visitor, typename Init>
      auto hybridApplyToTree(Tree&& tree, Visitor&& visitor, Init&& init)
      {
        return Impl::hybridApplyToTree(tree, hybridTreePath(), visitor, init);
      }
 
    } // namespace Experimental
 
  } // namespace TypeTree
} //namespace Dune
 
#endif // DUNE_TYPETREE_ACCUMULATE_STATIC_HH