Compiletime transform of tree into tuple

user_3359751 0
Viewed 232

I'm stuck with the following problem:

given a tree represented by non-terminal nodes of type Node<> and terminal nodes of arbitrary types like A, B and so on (see below).

Because I don't want to use runtime-polymorphism I like to transform the tree into a std::tuple via a constexpr function like the immediately invoked lambda expression in the example below.

struct A {};
struct B {};
struct C {};
struct D {};
struct E {};

template<typename... T>
struct Node {
    constexpr Node(const T&... n) : mChildren{n...} {}
    std::tuple<T...> mChildren;
};

template<uint8_t N>
struct IndexNode {
    std::array<uint8_t, N> mChildren;
};

int main() {
    constexpr auto tree = []() {
        auto t = Node(A(), 
                       B(), 
                       Node(C(),
                            Node(D())), 
                       E());    

        // transform t into std::tuple<A, B, C, D, IndexNode<1>{3}, IndexNode<2>{2, 4}, E, IndexNode<4>{0, 1, 5, 6}>

        // return ...;        
    }();

}

The idea is to use an index to a tuple element as a "pointer" to the active (selected) node of the tree. The overall purpose is to implement a menu-system on a µC without using runtime-polymorphism.

If I can carry out this transformation at compiletime, I can use a special meta-function to retrieve the active tuple-element and call some function on it. This function I wrote already.

The missing link would surely be some sort of depth-first tree-traversal ... but I can't figure it out.

constexpr variadic-templates c++17 template-meta-programming c++
2 Answers

@wimalopaan did you read max66' answer or did you find another solution for your idea? I tried to tackle the problem by connecting input and output via an index mapping. However, that became more complicated than I expected. Here is how I trid to establish the index mapping:

For the output tuple, there is an obvious choice of indices. Swapping the storage order a bit (which is simpler for me to imagine), the indices read

using Tree = std::tuple<
  IndexNode<4>{1, 2, 3, 7},// 0
    A,                     // 1
    B,                     // 2
    IndexNode<2>{4, 5},    // 3
      C,                   // 4
      IndexNode<1>{6},     // 5
        D,                 // 6
    E                      // 7
>;

The input consists of nested tuples, so let us invent some multiindex:

Node(/* 1, 2, 3, 7 */ // 0, Vals<>
  A{},                // 1, Vals<0>
  B{},                // 2, Vals<1>
  Node(/* 4, 5 */     // 3, Vals<2>
    C{},              // 4, Vals<2, 0>
    Node(/* 6 */      // 5, Vals<2, 1>
      D{}             // 6, Vals<2, 1, 0>
    )
  ),
  E{}                 // 7, Vals<3>
);

For computing the indices in IndexNode it is useful to specify the "number of output indices consumed by a Node including its children". In max66's answer this is called cntT. Let us use the term rank for this quantity here and compute by function overload:

template<class> struct Type {};// helper to pass a type by value (for overloading)

template<class Terminal>
size_t rank_of(Type<Terminal>) {// break depth recursion for terminal node
  return 1;
}

template<class... Children>
size_t rank_of(Type<Node<Children...>>) {// continue recursion for non-terminal node
  return (
    1 +// count enclosing non-terminal node
    ... + rank_of(Type<Children>{})
  );
}

The same strategy can be applied to obtain the multiindices of each node in the input representation. The multiindices are accumulated (by depth recursion) into ParentInds.

#include "indexer.hpp"// helper for the "indices trick"
#include "merge.hpp"// tuple_cat for types
#include "types.hpp"// template<class...> struct Types {};
#include "vals.hpp"// helper wrapped around std::integer_sequence

template<class Terminal, class ParentInds=Vals<>>
auto indices_of(
  Type<Terminal>,// break depth recursion for terminal node
  ParentInds = ParentInds{}
) {
  std::cout << __PRETTY_FUNCTION__ << std::endl;
  return Types<ParentInds>{};// wrap in Types<...> for simple merging
}

template<class... Children, class ParentInds=Vals<>>
auto indices_of(
  Type<Node<Children...>>,// continue recursion for non-terminal node
  ParentInds parent_inds = ParentInds{}
) {
  return indexer<Children...>([&] (auto... child_inds) {
    return merge(
      Types<ParentInds>{},// indices for enclosing non-terminal node
      indices_of(
        Type<Children>{},
        parent_inds.append(child_inds)
      )...
    );
  });
}

Output with GCC 7.2:

auto indices_of(Type<Terminal>, ParentInds) [with Terminal = E; ParentInds = Vals<3>]
auto indices_of(Type<Terminal>, ParentInds) [with Terminal = D; ParentInds = Vals<2, 1, 0>]
auto indices_of(Type<Terminal>, ParentInds) [with Terminal = C; ParentInds = Vals<2, 0>]
auto indices_of(Type<Terminal>, ParentInds) [with Terminal = B; ParentInds = Vals<1>]
auto indices_of(Type<Terminal>, ParentInds) [with Terminal = A; ParentInds = Vals<0>]

With the index mapping computed by indices_of we can construct the output tuple like this:

template<class T>
constexpr auto transform(const T& t) {
  static_assert(
    std::is_same<
      T,
      Node<A, B, Node<C, Node<D> >, E>
    >{}
  );

  auto inds = indices_of(Type<T>{});

  static_assert(
    std::is_same<
      decltype(inds),
      Types<
        Vals<>,
          Vals<0>,
          Vals<1>,
          Vals<2>,
            Vals<2, 0>,
            Vals<2, 1>,
              Vals<2, 1, 0>,
          Vals<3>
      >
    >{}
  );

  return indexer(inds.size, [&] (auto... is) {// `is` are the tuple's output inds
    return std::make_tuple(// becomes the final output tuple
      transform_at(
        inds.construct_type_at(is),// multiindex `Vals<...>{}` for each tuple element
        t,// input tree
        is.next()// used by each `IndexNode`: offset for its index computation
      )...
    );
  });
}

Here is a complete (hopefully bug-free) working example (online demo):

#include <algorithm>
#include <iostream>
#include <tuple>
#include <numeric>

////////////////////////////////////////////////////////////////////////////////

template<size_t i>
struct Val : std::integral_constant<size_t, i> {
  template<size_t dist=1>
  constexpr auto next(Val<dist> = {}) {
    return Val<i+dist>{};
  }
};

template<size_t... is>
struct Vals {
  template<size_t i>
  constexpr auto append(Val<i>) {
    return Vals<is..., i>{};
  }
};

template<size_t i0, size_t... is>
constexpr auto front(Vals<i0, is...>) { return Val<i0>{}; }

template<size_t i0, size_t... is>
constexpr auto pop_front(Vals<i0, is...>) { return Vals<is...>{}; }

////////////////////////////////////////////////////////////////////////////////

template<class> struct Type {};

template<class... Ts>
struct Types {
  static constexpr auto size = Val<sizeof...(Ts)>{};

  template<std::size_t i, class... Args>
  constexpr auto construct_type_at(Val<i>, Args&&... args) {
    using Ret = std::tuple_element_t<i, std::tuple<Ts...>>;
    return Ret(std::forward<Args>(args)...);
  }
};

////////////////////////////////////////////////////////////////////////////////

template<std::size_t... is, class F>
constexpr decltype(auto) indexer_impl(std::index_sequence<is...>, F f) {
  return f(Val<is>{}...);
}

template<class... Ts, class F>
constexpr decltype(auto) indexer(F f) {
  return indexer_impl(std::index_sequence_for<Ts...>{}, f);
}

template<size_t N, class F>
constexpr decltype(auto) indexer(std::integral_constant<size_t, N>, F f) {
  return indexer_impl(std::make_index_sequence<N>{}, f);
}

////////////////////////////////////////////////////////////////////////////////

template<class... Ts>
auto merge(Types<Ts...> done) {
  return done;
}

template<class... Ts, class... Us, class... Vs>
auto merge(Types<Ts...>, Types<Us...>, Vs...) {
// TODO: if desired, switch to logarithmic recursion
// https://stackoverflow.com/a/46934308/2615118
  return merge(Types<Ts..., Us...>{}, Vs{}...);
}

////////////////////////////////////////////////////////////////////////////////

struct TerminalNode { const char* msg{""}; };// JUST FOR DEBUG

std::ostream& operator<<(std::ostream& os, const TerminalNode& tn) {
  return os << tn.msg << std::endl;// JUST FOR DEBUG
}

struct A : TerminalNode {};// INHERITANCE JUST FOR DEBUG
struct B : TerminalNode {};
struct C : TerminalNode {};
struct D : TerminalNode {};
struct E : TerminalNode {};

template<typename... T>
struct Node {
  constexpr Node(const T&... n) : mChildren{n...} {}
  std::tuple<T...> mChildren;
};

template<size_t N>
struct IndexNode {
  std::array<size_t, N> mChildren;
  constexpr IndexNode(std::array<size_t, N> arr) : mChildren(arr) {}

  friend std::ostream& operator<<(std::ostream& os, const IndexNode& self) {
    for(auto r : self.mChildren) os << r << ", ";// JUST FOR DEBUG
    return os << "\n";
  }
};

////////////////////////////////////////////////////////////////////////////////

template<class Terminal>
size_t rank_of(
  Type<Terminal>// break depth recursion for terminal node
) {
  return 1;
}
template<class... Children>
size_t rank_of(
  Type<Node<Children...>>// continue recursion for non-terminal node
) {
  return (
    1 +// count enclosing non-terminal node
    ... + rank_of(Type<Children>{})
  );
}

////////////////////////////////////////////////////////////////////////////////

template<class Terminal, class ParentInds=Vals<>>
auto indices_of(
  Type<Terminal>,// break depth recursion for terminal node
  ParentInds = ParentInds{}
) {
  std::cout << __PRETTY_FUNCTION__ << std::endl;
  return Types<ParentInds>{};// wrap in Types<...> for simple merging
}
template<class... Children, class ParentInds=Vals<>>
auto indices_of(
  Type<Node<Children...>>,// continue recursion for non-terminal node
  ParentInds parent_inds = ParentInds{}
) {
  return indexer<Children...>([&] (auto... child_inds) {
    return merge(
      Types<ParentInds>{},// indices for enclosing non-terminal node
      indices_of(
        Type<Children>{},
        parent_inds.append(child_inds)
      )...
    );
  });
}

////////////////////////////////////////////////////////////////////////////////

template<class It, class T>
constexpr It exclusive_scan(It first, It last, It out, T init) {
  for(auto it=first; it!=last; ++it) {
    auto in = *it;
    *out++ = init;
    init += in;
  }
  return out;
}

////////////////////////////////////////////////////////////////////////////////

template<size_t... child_inds, class Terminal, class Offset>
constexpr decltype(auto) transform_at(
  Vals<child_inds...> inds,
  const Terminal& terminal,
  Offset
) {
  static_assert(0 == sizeof...(child_inds));
  return terminal;
}

template<size_t... child_inds, class... Children, class Offset>
constexpr decltype(auto) transform_at(
  Vals<child_inds...> inds,
  const Node<Children...>& node,
  Offset offset = Offset{}
) {
  if constexpr(0 == sizeof...(child_inds)) {// the IndexNode is desired
    auto ranks = std::array{rank_of(Type<Children>{})...};
    exclusive_scan(std::begin(ranks), std::end(ranks), std::begin(ranks), 0);

    auto add_offset = [] (size_t& i) { i += Offset{}; };
    std::for_each(std::begin(ranks), std::end(ranks), add_offset);

    return IndexNode{ranks};
  }
  else {// some child of this enclosing node is desired
    return transform_at(
      pop_front(inds),
      std::get<front(inds)>(node.mChildren),
      offset
    );
  }
}

template<class T>
constexpr auto transform(const T& t) {
  auto inds = indices_of(Type<T>{});

  return indexer(inds.size, [&] (auto... is) {// is are the tuple output inds
    return std::make_tuple(// becomes the final output tuple
      transform_at(
        inds.construct_type_at(is),// multiindex for each tuple element
        t,// input tree
        is.next()// used by each `IndexNode`: offset for its index computation
      )...
    );
  });
}

////////////////////////////////////////////////////////////////////////////////

int main() {
  auto tree = []() {
    auto t = Node(    // 0, Val<>
      A{"FROM A"},    // 1, Val<0>
      B{"FROM B"},    // 2, Val<1>
      Node(           // 3, Val<2>
        C{"FROM C"},  // 4, Val<2, 0>
        Node(         // 5, Val<2, 1>
          D{"FROM D"} // 6, Val<2, 1, 0>
        )
      ),
      E{"FROM E"}     // 7, Val<3>
    );

    return transform(t);
  }();

  using Tree = decltype(tree);

  indexer(std::tuple_size<Tree>{}, [&] (auto... is) {
    (std::cout << ... << std::get<is>(tree));
  });

  return 0;
}
user_26151180
Related