All geek questions in one place

Compiletime tree to tuple conversion

I am stuck in the following problem:

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

Since I don’t want to use the runtime politometer, I like to convert the tree to std::tupleusing a function constexpr, for example, a directly called 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 the index for the tuple element as a "pointer" to the active (selected) node of the tree. The overall goal is to implement a menu system on μC without using run-time polymorphism.

compiletime, - tuple . .

, , ... .

+4
2

std::tuple_cat, std::index_sequence ?

#include <tuple>
#include <array>
#include <iostream>

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

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

   std::tuple<T...> mChildren;
 };

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

template <typename>
struct cntT : public std::integral_constant<std::size_t, 1U>
 { };

template <typename ... Ts>
struct cntT<Node<Ts...>>
   : public std::integral_constant<std::size_t, 1U + (cntT<Ts>::value + ...)>
 { };

template <typename T>
struct getT
 {
   constexpr auto operator() (T const & t, std::size_t & cnt)
    { ++cnt; return std::make_tuple(t); }
 };

template <typename ... Ts>
struct getT<Node<Ts...>>
 {
   template <std::size_t ... Is>
   constexpr auto func (std::tuple<Ts...> const & t,
                        std::index_sequence<Is...> const &,
                        std::size_t & cnt)
    {
      std::size_t val { cnt };

      IndexNode<sizeof...(Ts)> in
          { { { uint8_t(val += cntT<Ts>::value)... } } };

      return std::tuple_cat(getT<Ts>()(std::get<Is>(t), cnt)...,
                            std::make_tuple(in));
    }

   constexpr auto operator() (Node<Ts...> const & n, std::size_t & cnt)
    {
      return func(n.mChildren, std::make_index_sequence<sizeof...(Ts)>{},
                  cnt);
    }
 };

template <typename ... Ts>
constexpr auto linearNode (Node<Ts...> const & n)
 { 
   std::size_t cnt ( -1 );

   return getT<Node<Ts...>>()(n, cnt);
 }

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

      return linearNode(t);
    }();

   static_assert( std::is_same<
      decltype(tree),
      std::tuple<A, B, C, D, IndexNode<1>, IndexNode<2>, E,
                 IndexNode<4>> const>::value, "!");

   std::cout << "IndexNode<1> { ";

   for ( auto const & v : std::get<4U>(tree).mChildren )
      std::cout << int(v) << ", ";

   std::cout << "}" << std::endl; // print IndexNode<1> { 3, }

   std::cout << "IndexNode<2> { ";

   for ( auto const & v : std::get<5U>(tree).mChildren )
      std::cout << int(v) << ", ";

   std::cout << "}" << std::endl; // print IndexNode<2> { 2, 4, }

   std::cout << "IndexNode<4> { ";

   for ( auto const & v : std::get<7U>(tree).mChildren )
      std::cout << int(v) << ", ";

   std::cout << "}" << std::endl; // print IndexNode<4> { 0, 1, 5, 6, }
 }
+1

@wimalopaan max66 ' ? , . , . :

. ( ),

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
>;

, :

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>
);

IndexNode " , Node, ". max66 cntT. rank :

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>{})
  );
}

Node . ( ) 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)
      )...
    );
  });
}

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>]

, indices_of, :

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 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
      )...
    );
  });
}

(, ) (-):

#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;
}
0

Source: https://habr.com/ru/post/1680963/

More articles:


All Articles