型Listを継承順になるようにsortする

やりたいこと

依存管理のコンパイル時解決などの目的で 「型Listを継承順になるようにsortする」何かがほしい

struct hoge3_1{};
struct hoge2_1:hoge3_1{};
struct hoge2_2:hoge3_1{};
struct hoge1_1:hoge2_1,hoge2_2{};


using input = std::tuple<hoge1_1,hoge3_1,hoge2_1,hoge3_1,hoge2_1,hoge1_1>;

inherit_sort<input>::type; // => std::tuple<hoge3_1,hoge3_1,hoge2_1,hoge2_1,hoge1_1,hoge1_1>
// ↑ こういうのがほしい

型リストのトポロジカル的なソートと継承

下の型のような、依存しているクラスを包含している型をソートの対象としている場合、適当に木をたどればsortできる気がする

struct hoge1_1{using deps=std::tuple<hoge2_1,hoge2_2>;}

しかし、包含ではなく継承している場合、C++では親クラスのリストの取得はできないため「適当に木をたどれば」ということができない。
これをどうにかしなければならない

解決案

X → 入力のうちXを継承したもの を示せる、下の Treeのような概念を構築すればできる

template<class InputTypeList>
struct sort{
  template<class D>
  struct Tree{
    using child = InputTypeList.filter([](T){return !std::is_same_v<T,D> && std::is_base_of_v<T,D> }).map([](T){return Tree<T> }); // 疑似コード
  };
}

実装例

template<class>struct inherit_sort;

template<class...T>
struct inherit_sort<std::tuple<T...>>{
    using input = std::tuple<T...>;
    // 親クラスより 子クラスのほうが大きいvalueになるようにしてる
    template<class D>
    struct Priority{
        static constexpr std::size_t value = ((std::conditional_t< !std::is_same_v<T,D> && std::is_base_of_v<T,D>, Priority<T>,std::integral_constant<std::size_t,0> >::value)+...+1);
    };

    static constexpr auto index = []{ // `N番目の型Priority::value`でsortした(0,1,2...)
        std::array<std::size_t,sizeof...(T)> index_list={};
        sprout::iota(index_list.begin(),index_list.end(),0); 
        std::array<std::size_t,sizeof...(T)> p = {Priority<T>::value...};
        return sprout::stable_sort(index_list,[&](std::size_t lhs,std::size_t rhs){return p[lhs] < p[rhs];}); // constexpr なsortがC++17のstd::* に無いので sproutを使っている
    }();

    template<std::size_t...i>
    static auto trans(std::index_sequence<i...>) -> std::tuple<std::tuple_element_t<index[i],input>...>;

    using type = decltype(trans(std::make_index_sequence<sizeof...(T)>{}));
};

main.cpp

struct hoge3_1{static inline std::string name="hoge3_1";};
struct hoge2_1:hoge3_1{static inline std::string name="hoge2_1";};
struct hoge2_2:hoge3_1{static inline std::string name="hoge2_2";};
struct hoge1_1:hoge2_1,hoge2_2{static inline std::string name="hoge1_1";};

int main()
{
    using in = std::tuple<hoge1_1,hoge3_1,hoge2_1,hoge3_1,hoge2_1,hoge1_1>;
    using out = deps_sort<in>::type;

    std::cout<<"in"<<std::endl;
    std::apply([](auto...e){
        for(auto s:{e.name...}) std::cout<<s<<" ";
    },in{});
    std::cout<<std::endl;

    std::cout<<"out"<<std::endl;
    std::apply([](auto...e){
        for(auto s:{e.name...}) std::cout<<s<<" ";
    },out{});
    std::cout<<std::endl;
}

実行結果

in
hoge1_1 hoge3_1 hoge2_1 hoge3_1 hoge2_1 hoge1_1 
out
hoge3_1 hoge3_1 hoge2_1 hoge2_1 hoge1_1 hoge1_1