1
\$\begingroup\$

I'll define template <typename...> class VariadicTree with the following example:

VariadicTree<A,B,C,D,E,F,G,H,I,J,K,L,M,N,O> is a binary tree whose type for insertion, removal, searching, etc... is A. But it will also accept insertions, removals, searches, etc... of objects of type B,C,D,E,F,G,H,I,J,K,L,M,N, or O as well. The hierarchy of these possible types is depicted in this following diagram:

             A
         /       \
        /         \
       B           C
    /    \       /    \
   D      E     F      G
  / \    / \   / \    / \
 H   I  J   K L   M  N   O

So if VariadicTree<A,B,C,D,E,F,G,H,I,J,K,L,M,N,O> inserts, removes, or searches for an object of type, say E, then it will pass that object to its "left sub-variadic tree" VariadicTree<B,D,E,H,I,J,K>, which in turn will pass that object to its "right sub-variadic tree" VariadicTree<E,J,K>. Thus, not only is insertion, removal, searches of object of type A by VariadicTree<A,B,C,D,E,F,G,H,I,J,K,L,M,N,O> done in logarithmic time, but the search for the correct "sub-variadic tree" when the object is not of type A is also done in logarithmic time. This is done through the ordering H < D < I < B < J < E < K < A < L < F < M < C < N < G < O (which is computed during compile-time as std::tuple<H,D,I,B,J,E,K,A,L,F,M,C,N,G,O>).

VariadicTree<A,B,C,...> is actually an alias for VariadicTreeWithComparators<A, default_comparator<A>, B, default_comparator<B>, C, default_comparator<C>, ...>, where default_comparator is defined by

template <typename T>
struct default_comparator {
    bool operator()(const T& a, const T& b) const { return a < b; }
};

Thus if custom comparators need to be used for each type A,B,C,..., then VariadicTreeWithComparators can be used instead.

The following code may be difficult to read, but the above synopsis should help facilitate the reading of the meta-programming involved. Removal of nodes has not been coded yet, because that will make the code even more difficult to read.

I welcome other designs of what a "variadic tree" can be, and will even take it on if the design seems better than mine, as I like this concept very much.

#include <iostream>
#include <tuple>
#include <memory>
#include <type_traits>
#include <utility>
#include <string>

enum Side {Left, Right};

constexpr std::size_t power (int base, std::size_t exponent) {
    return (exponent == 0) ? 1 : base * power(base, exponent - 1);
}

namespace detail {
    // Building the indices for the left and right variadic subtree types.
    template <Side> constexpr std::size_t index_offset (std::size_t);

    template <> constexpr std::size_t index_offset<Left> (std::size_t n) {
        return power(2,n+1) - 2;
    }

    template <> constexpr std::size_t index_offset<Right> (std::size_t n) {
        return power(2,n+1) + power(2,n) - 2;
    }

    template <Side S, std::size_t Max, std::size_t Row, std::size_t Count = 0, typename Output = std::index_sequence<>, typename = void>
    struct build_indices_impl {
        using type = Output;
    };

    template <Side S, std::size_t Max, std::size_t Row, std::size_t Count, std::size_t... Is>
    struct build_indices_impl<S, Max, Row, Count, std::index_sequence<Is...>,
        std::enable_if_t<(Count < power(2,Row) && index_offset<S>(Row) + Count < Max)>> :
            build_indices_impl<S, Max, Row, Count+1, std::index_sequence<Is..., index_offset<S>(Row) + Count>> {};

    template <Side S, std::size_t Max, std::size_t Row, std::size_t Count, std::size_t... Is>
    struct build_indices_impl<S, Max, Row, Count, std::index_sequence<Is...>,
        std::enable_if_t<(Count == power(2,Row) && index_offset<S>(Row) + Count < Max)>> :
            build_indices_impl<S, Max, Row+1, 0, std::index_sequence<Is...>> {};

    template <Side S, std::size_t Max>
    using build_indices = typename build_indices_impl<S, Max, 1>::type;

    // Determining if a type is "less than" another type based on the ordering of types in a given pack.
    template <typename T, typename U, typename Ordering> struct less_than;

    template <typename T, typename U, template <typename...> class P, typename First, typename... Rest>
    struct less_than<T, U, P<First, Rest...>> : less_than<T, U, P<Rest...>> {};

    template <typename T, typename U, template <typename...> class P, typename... Rest>
    struct less_than<T, U, P<T, Rest...>> : std::true_type {};

    template <typename T, typename U, template <typename...> class P, typename... Rest>
    struct less_than<T, U, P<U, Rest...>> : std::false_type {};

    template <typename T, typename U, template <typename...> class P>
    struct less_than<T, U, P<>> : std::false_type {};

    template <typename T, template <typename...> class P, typename First, typename... Rest>
    struct less_than<T, T, P<First, Rest...>> : std::false_type {};

    template <typename T, template <typename...> class P, typename... Rest>
    struct less_than<T, T, P<T, Rest...>> : std::false_type {};

    // Concatenating std::index_sequences or packs of types.
    template <typename... Packs> struct concat;

    template <template <typename...> class P, typename... Ts, typename... Us>
    struct concat<P<Ts...>, P<Us...>> {
        using type = P<Ts..., Us...>;
    };

    template <std::size_t... Is, std::size_t... Js>
    struct concat<std::index_sequence<Is...>, std::index_sequence<Js...>> {
        using type = std::index_sequence<Is..., Js...>;
    };

    template <typename Pack1, typename Pack2, typename... Packs>
    struct concat<Pack1, Pack2, Packs...> : concat<Pack1, typename concat<Pack2, Packs...>::type> {};

    // Inorder traversal for a complete binary tree whose level-order traversal is 0,1,2, ..., Max-1.
    template <std::size_t Start, std::size_t Max, typename = void>
    struct inorder {
        using type = std::index_sequence<>;  // So that concatenating changes nothing and ends the recursion.
    };

    template <std::size_t Start, std::size_t Max>  // Recursive call.
    struct inorder<Start, Max, std::enable_if_t<(Start < Max)>> : concat<
        typename inorder<2*Start + 1, Max>::type, 
        std::index_sequence<Start>,
        typename inorder<2*Start + 2, Max>::type> {};

    // Reorder a tuple according to a list of indices.
    template <typename Tuple, typename Sequence> struct order_by_indices;

    template <typename Tuple, std::size_t... Is>
    struct order_by_indices<Tuple, std::index_sequence<Is...>> {
        using type = std::tuple<std::tuple_element_t<Is, Tuple>...>;
    };

    template <typename Tuple>
    using inorder_sort = typename order_by_indices<Tuple, typename inorder<0, std::tuple_size<Tuple>::value>::type>::type;

    // variadic_expand
    template <template <typename...> class Template, typename Pack> struct class_pack;

    template <template <typename...> class Template, template <typename...> class P, typename... Ts>
    struct class_pack<Template, P<Ts...>> {
        using type = Template<Ts...>;
    };

    template <template <typename...> class Template, template <typename...> class C, typename... Ts>
    struct variadic_expand : class_pack<Template, typename concat<std::tuple<Ts, C<Ts>>...>::type> {};

    // alternating_pack
    template <typename Pack, typename Output = std::tuple<>> struct alternating_pack;

    template <template <typename...> class P, typename First, typename Second, typename... Rest, typename... Ts>
    struct alternating_pack<P<First, Second, Rest...>, std::tuple<Ts...>> : alternating_pack<P<Rest...>, std::tuple<Ts..., First>> {};

    template <template <typename...> class P, typename... Ts>
    struct alternating_pack<P<>, std::tuple<Ts...>> {
        using type = P<Ts...>;
    };
}

template <typename...> class VariadicTreeWithComparators;

template <>
class VariadicTreeWithComparators<> {
public:
    using value_type = void;
};

template <typename T, typename Comparator, typename... Ts>
class VariadicTreeWithComparators<T, Comparator, Ts...> {
    template <typename Tuple, typename Indices> struct SubVariadicTreeHelper;
    template <Side S>
    using SubVariadicTree = typename SubVariadicTreeHelper<std::tuple<T, Comparator, Ts...>, detail::build_indices<S, sizeof...(Ts) + 2>>::type;
    using Ordering = detail::inorder_sort<typename detail::alternating_pack<std::tuple<T, Comparator, Ts...>>::type>;
    // We use alternating_pack because we skip all the comparators in determining the ordering of the types.  In the example in main(), this is std::tuple<double, std::string, char, int, std::size_t>.
    struct Node {
        VariadicTreeWithComparators<T, Comparator, Ts...>& tree;  // Every VariadicTreeWithComparators<T, Comparator, Ts...>::Node must belong to a VariadicTreeWithComparators<T, Comparator, Ts...>.
        T item;
        std::shared_ptr<Node> left = nullptr, right = nullptr;
        Node (VariadicTreeWithComparators<T, Comparator, Ts...>& tr, const T& t) : tree(tr), item(t) {}
        std::shared_ptr<Node> insert (VariadicTreeWithComparators<T, Comparator, Ts...>& tr, const T& t, std::shared_ptr<Node>& node) {
            if (!node) {
                std::shared_ptr<Node> newNode = std::make_shared<Node>(tr, t);
                node = newNode;
                std::cout << "Node established with item: " << t << '\n';  //////
                return newNode;
            }
            if (comparator(t, item)) {
                std::cout << "Inserting into left subtree...\n";  //////
                std::shared_ptr<Node> newLeft = insert(tr, t, node->left);
                left = newLeft;
            }
            else {
                std::cout << "Inserting into right subtree...\n";  //////
                std::shared_ptr<Node> newRight = insert(tr, t, node->right);
                right = newRight;
            }
            return node;
        }
        std::shared_ptr<Node> search (const T& t, const std::shared_ptr<Node>& node) {
            if (comparator(t, node->item))
                return search(t, node->left);
            else if (comparator(node->item, t))
                return search(t, node->right);
            return node;
        }
    };
std::shared_ptr<Node> root;
std::shared_ptr<SubVariadicTree<Left>> leftSubtree = std::make_shared<SubVariadicTree<Left>>();
std::shared_ptr<SubVariadicTree<Right>> rightSubtree = std::make_shared<SubVariadicTree<Right>>();
static const Comparator comparator;
public:
    using value_type = T;
    std::shared_ptr<Node> insert (const T& t) { return root->insert(*this, t, root); }
    template <typename U>
    auto insert (const U& u, std::enable_if_t<detail::less_than<U,T, Ordering>::value>* = nullptr) {  // Using 'std::enable_if_t<detail::less_than<U,T, Ordering>::value, std::shared_ptr<Node>>' as the return type won't compile since we don't know the Node type of which variadic subtree type we want.
        std::cout << "Inserting in left variadic subtree...\n";  /////
        return leftSubtree->insert(u);
    }
    template <typename U>
    auto insert (const U& u, std::enable_if_t<detail::less_than<T,U, Ordering>::value>* = nullptr) {
        std::cout << "Inserting in right variadic subtree...\n";  /////
        return rightSubtree->insert(u);
    }
    std::shared_ptr<Node> search (const T& t) { return root->search(t, root); }
    template <typename U>
    auto search (const U& u, std::enable_if_t<detail::less_than<U,T, Ordering>::value>* = nullptr) {
        std::cout << "Searching in left variadic subtree for '" << u << "'\n";  /////
        return leftSubtree->search(u);
    }
    template <typename U>
    auto search (const U& u, std::enable_if_t<detail::less_than<T,U, Ordering>::value>* = nullptr) {
        std::cout << "Searching in right variadic subtree for '" << u << "'\n";  /////
        return rightSubtree->search(u);
    }
};
template <typename T, typename Comparator, typename... Ts> const Comparator VariadicTreeWithComparators<T, Comparator, Ts...>::comparator = Comparator();

template <typename T, typename Comparator, typename... Ts>
template <typename Tuple, std::size_t... Is>
struct VariadicTreeWithComparators<T, Comparator, Ts...>::SubVariadicTreeHelper<Tuple, std::index_sequence<Is...>> {
    using type = VariadicTreeWithComparators<std::tuple_element_t<Is, Tuple>...>;
};

template <typename T>
struct default_comparator {
    bool operator()(const T& a, const T& b) const { return a < b; }
};

template <typename... Ts>
using VariadicTree = typename detail::variadic_expand<VariadicTreeWithComparators, default_comparator, Ts...>::type;
// i.e. VariadicTreeWithComparators<A, default_comparator<A>, B, default_comparator<B>, C, default_comparator<C>, ...>

int main() {
    VariadicTree<int, std::string, bool, double, char, std::size_t> tree;
    // int is the root type, std::string is left child of int, bool is right child of int, double is left child of std::string, char is right child of std::string, std::size_t is right child of bool.
    std::cout << std::boolalpha;
    tree.insert(5);
    tree.insert(std::string("hello"));
    tree.insert(true);
    tree.insert(false);
    tree.insert(3.14);

    static_assert (detail::less_than<int, char, std::tuple<int, long, bool, char>>::value, "");
    static_assert (detail::less_than<bool, char, std::tuple<int, long, bool, char>>::value, "");
    static_assert (!detail::less_than<char, bool, std::tuple<int, long, bool, char>>::value, "");

//  static_assert (std::is_same<
//      VariadicTree<int, std::string, bool, double, char, std::size_t>::SubVariadicTree<Left>,
//      VariadicTree<std::string, double, char>
//  >::value, "");  // This static assertion passes only if SubVariadicTree is declared public in the VariadicTreeWithComparators class.

    struct A{};  struct B{};  struct C{};  struct D{};  struct E{};  struct F{};  struct G{};  struct H{};  struct I{};  struct J{};  struct K{};  struct L{};  struct M{};  struct N{};
    static_assert (std::is_same<
        detail::inorder_sort<std::tuple<A,B,C,D,E,F,G,H,I,J,K,L,M,N>>,
        std::tuple<H,D,I,B,J,E,K,A,L,F,M,C,N,G>
    >::value, "");

    const auto node1 = tree.search(5);  std::cout << "Node with item '" << node1->item << "' found.\n";
    const auto node2 = tree.search(true);  std::cout << "Node with item '" << node2->item << "' found.\n";
    const auto node3 = tree.search(false);  std::cout << "Node with item '" << node3->item << "' found.\n";
    const auto node4 = tree.search(std::string("hello"));  std::cout << "Node with item '" << node4->item << "' found.\n";
    const auto node5 = tree.search(3.14);  std::cout << "Node with item '" << node5->item << "' found.\n";
    std::cin.get();
}

Output:

Node established with item: 5
Inserting in left variadic subtree...
Node established with item: hello
Inserting in right variadic subtree...
Node established with item: true
Inserting in right variadic subtree...
Inserting into left subtree...
Node established with item: false
Inserting in left variadic subtree...
Inserting in left variadic subtree...
Node established with item: 3.14
Node with item '5' found.
Searching in right variadic subtree for 'true'
Node with item 'true' found.
Searching in right variadic subtree for 'false'
Node with item 'false' found.
Searching in left variadic subtree for 'hello'
Node with item 'hello' found.
Searching in left variadic subtree for '3.14'
Searching in left variadic subtree for '3.14'
Node with item '3.14' found.
\$\endgroup\$
2
\$\begingroup\$

From your prose description, I have two design comments already:

  • "This is done through the ordering H < D < I < B < J < ..." sounds like a horrible UI. Wouldn't the user naturally expect A < B < C < D < E < ..., just like in English (and just like the order of the arguments in the source code, for that matter)? Assigning labels to the tree breadth-first doesn't seem to serve any purpose except to prove that you can.

  • Your description of the tree's interface makes it sound an awful lot like a boost::variant<tree<A>, tree<B>, tree<C>, ..., tree<O>>. If you care about the metaprogramming more than the functionality, maybe you should try your hand at building variant from scratch instead of lumping the tree stuff in with it; OTOH if you care about the functionality more than the metaprogramming details, I'd strongly recommend scrapping all the metaprogramming and implementing your desired functionality in terms of variant.

Also, what does your code currently do with VariadicTree<int,int>, and what do you think it should do with it?

Now comments on your code itself:


You wrote a generic constexpr power function, but the only thing you ever use it for is power(2, n), which can already be written in constexpr form as (1 << n). Use the simpler form, both for clarity and to reduce your compile times.

If you were going to keep power, it should have gone in your detail namespace anyway, to avoid cluttering the global namespace.


template <Side S, std::size_t Max, std::size_t Row, std::size_t Count = 0, typename Output = std::index_sequence<>, typename = void>
struct build_indices_impl {
    using type = Output;
};

Prefer to omit the names of unused parameters:

template <Side, size_t, size_t, size_t = 0, typename Output = std::index_sequence<>, typename = void>
struct build_indices_impl {
    using type = Output;
};

However, then it gets kind of confusing... which might indicate that you have too many template parameters here.

I ran your code through Wandbox and observed the index_sequences that you construct for build_indices<Left, 10> and build_indices<Right, 10>. The former has length 6 and the latter has length 2. This certainly seems wrong for a binary search tree... and in the one place you use build_indices, you use it with a second argument of sizeof...(Ts) + 2 instead of simply sizeof...(Ts), possibly indicating that you know there's an off-by-one-or-maybe-off-by-two error in there somewhere.

You should use 0-based indexing consistently. The above examples make it seem to me as if you're using 1-based or maybe 2-based indexing for your build_indices, which is odd.


The code dealing with comparators would be clearer if you replaced code like

Comparator comparator;
if (comparator(a, b)) ...

with

Comparator less;
if (less(a, b)) ...

When I try to insert a value of an unsupported type into a VariadicTree, I get a horrible spew of template error messages:

prog.cc: In instantiation of 'auto VariadicTreeWithComparators<T, Comparator, Ts ...>::insert(const U&, std::enable_if_t<detail::less_than<T, U, typename detail::order_by_indices<typename detail::alternating_pack<std::tuple<T, Comparator, Ts ...> >::type, typename detail::inorder<0ul, std::tuple_size<typename detail::alternating_pack<std::tuple<T, Comparator, Ts ...> >::type>::value, void>::type>::type>::value>*) [with U = unsigned int; T = int; Comparator = default_comparator<int>; Ts = {int, default_comparator<int>}; std::enable_if_t<detail::less_than<T, U, typename detail::order_by_indices<typename detail::alternating_pack<std::tuple<T, Comparator, Ts ...> >::type, typename detail::inorder<0ul, std::tuple_size<typename detail::alternating_pack<std::tuple<T, Comparator, Ts ...> >::type>::value, void>::type>::type>::value> = void]':
prog.cc:189:38:   required from 'auto VariadicTreeWithComparators<T, Comparator, Ts ...>::insert(const U&, std::enable_if_t<detail::less_than<T, U, typename detail::order_by_indices<typename detail::alternating_pack<std::tuple<T, Comparator, Ts ...> >::type, typename detail::inorder<0ul, std::tuple_size<typename detail::alternating_pack<std::tuple<T, Comparator, Ts ...> >::type>::value, void>::type>::type>::value>*) [with U = unsigned int; T = int; Comparator = default_comparator<int>; Ts = {int, default_comparator<int>, int, default_comparator<int>, int, default_comparator<int>, int, default_comparator<int>, int, default_comparator<int>}; std::enable_if_t<detail::less_than<T, U, typename detail::order_by_indices<typename detail::alternating_pack<std::tuple<T, Comparator, Ts ...> >::type, typename detail::inorder<0ul, std::tuple_size<typename detail::alternating_pack<std::tuple<T, Comparator, Ts ...> >::type>::value, void>::type>::type>::value> = void]'
prog.cc:223:19:   required from here
prog.cc:189:30: error: 'class VariadicTreeWithComparators<>' has no member named 'insert'
         return rightSubtree->insert(u);
                ~~~~~~~~~~~~~~^~~~~~

(StackOverflow's non-line-wrapping code view doesn't do it justice, I'm afraid. For a good time, click in the code view above and scroll right.)

You could fix that issue by adding a single static_assert in a default implementation of insert. That is, instead of writing the non-template (and therefore implicit-conversion-allowing) member function

std::shared_ptr<Node> insert (const T& t) {
    return root->insert(*this, t, root);
}

you should write

template<typename U>
void insert(const U&) { static_assert(false, "unsupported type"); }

template<typename U>
std::shared_ptr<Node> insert (const U& u, std::enable_if_t<std::is_same<U,T>::value>* = nullptr) {
    return root->insert(*this, u, root);
}

and you should also modify your detail::less_than<T,U,Ordering> metafunction to return false when U is not an element of Ordering at all. That is to say, less_than<int, unsigned, tuple<int>> should inherit from false_type, not true_type.

When I made those two modifications to your code, the error message above reduced itself to this:

prog.cc: In member function 'void VariadicTreeWithComparators<T, Comparator, Ts ...>::insert(const U&)':
prog.cc:187:29: error: static assertion failed: unsupported type
     void insert(const U&) { static_assert(false, "unsupported type"); }
                             ^~~~~~~~~~~~~

On the subject of VariadicTreeWithComparators, I think it's odd that you chose to write

template <typename... Ts>
using VariadicTree = typename detail::variadic_expand<VariadicTreeWithComparators, default_comparator, Ts...>::type;
// i.e. VariadicTreeWithComparators<A, default_comparator<A>, B, default_comparator<B>, C, default_comparator<C>, ...>

instead of choosing a simpler representation for VariadicTreeWithComparators that would have allowed you to write

template <typename... Ts>
using VariadicTree = VariadicTreeWithComparators<detail::typelist<Ts...>, detail::map<default_comparator, detail::typelist<Ts...>>;
// i.e. VariadicTreeWithComparators<typelist<A, B, C,...>, typelist<default_comparator<A>, default_comparator<B>, default_comparator<C>, ...>>

You could then extract the Ith type and its corresponding Ith comparator directly, using std::get<I>(Types) and std::get<I>(Comparators), instead of having to do arithmetic to interleave them and then later to undo the interleaving.


Speaking of comparators, what does your search member function do if my comparator is std::less<>? What do you think it should do?

\$\endgroup\$
6
  • \$\begingroup\$ @ Quuxplusone Thanks for your review. I thought of the ordering A < B < C < D < E < ... but wouldn't that require a linear search for the correct type rather than the logarithmic search that I have now? That the whole point of having a tree, right? To allow binary search instead of linear search? \$\endgroup\$ – prestokeys May 15 '16 at 14:52
  • \$\begingroup\$ You could still use a binary search; it would just mean that the root of your tree-containing-A-through-O would be H instead of A, and that build_indices<Left, 10> and build_indices<Right, 10> would have the same number of elements instead of being unbalanced, and so on. I'm pretty sure you could do it almost entirely by removing code from your current implementation. :) \$\endgroup\$ – Quuxplusone May 15 '16 at 19:26
  • 1
    \$\begingroup\$ static_assert(false, "stuff"); is allowed to fire unconditionally. You need a dependent expression. \$\endgroup\$ – T.C. May 20 '16 at 20:36
  • \$\begingroup\$ @T.C. Good catch. Is there a common idiom for getting such a "falsey-dependent-expression"? I guess it would logically be spelled false_v<T>, analogous to std::void_t<T>, but how's it really spelled? \$\endgroup\$ – Quuxplusone May 20 '16 at 22:21
  • \$\begingroup\$ I don't know of one. Personally, I'd likely just use std::is_same<U,T>::value here. (You probably want to double check that overload set, too; I don't think it's right.) \$\endgroup\$ – T.C. May 20 '16 at 23:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.