lundi 30 novembre 2015

Enumerate all indices of multidimensional array at compile time

I want to generate a bunch of tuples of different combinations of types in generic number of dimensions. Each dimension have its own size. Say, I have a class template:

template< std::size_t i > struct T {};

For 3-dimensional "space" of sizes 5, 3, 2 I want to generate all possible combinations of 3-tuples of types T< I0 >, T< I1 >, T< I2 >, where I0, I1 and I2 are:

0 0 0
0 0 1
0 1 0
0 1 1
0 2 0
0 2 1
1 0 0
1 0 1
1 1 0
1 1 1
1 2 0
1 2 1
....
4 0 0
4 0 1
4 1 0
4 1 1
4 2 0
4 2 1

I wrote the following code:

#include <type_traits>
#include <utility>
#include <iterator>
#include <iostream>
#include <initializer_list>
#include <algorithm>

template< typename F, std::size_t ...indices >
struct enumerator
{
    static constexpr const std::size_t size_ = sizeof...(indices);
    static constexpr const std::size_t count_ = (indices * ...);

    template< typename I >
    struct decomposer;

    template< std::size_t ...I >
    struct decomposer< std::index_sequence< I... > >
    {
        F & f;

        static constexpr const std::size_t indices_[size_] = {indices...};

        static
        constexpr
        std::size_t
        order(std::size_t const i)
        {
            std::size_t o = 1;
            for (std::size_t n = i + 1; n < size_; ++n) {
                o *= indices_[n];
            }
            return o;
        }

        static constexpr std::size_t const orders_[size_] = {order(I)...};

        static
        constexpr
        std::size_t
        digit(std::size_t c, std::size_t const i)
        {
            for (std::size_t n = 0; n < i; ++n) {
                c = c % orders_[n];
            }
            return c / orders_[i];
        }

        template< std::size_t c >
        constexpr
        bool
        call() const
        {
            auto const i = {digit(c, I)...};
            std::copy(std::cbegin(i), std::cend(i), std::ostream_iterator< std::size_t >(std::cout, " "));
            std::cout << std::endl;
            return f.template operator () < digit(c, I)... >(); // error here
        }

    };

    decomposer< std::make_index_sequence< size_ > > decomposer_;

    constexpr
    bool
    operator () () const
    {
        return call(std::make_index_sequence< count_ >{});
    }

    template< std::size_t ...counter >
    constexpr
    bool
    call(std::index_sequence< counter... >) const
    {
        return (decomposer_.template call< counter >() && ...);
    }
};

#include <cstdlib>

struct print
{
    template< typename ...indices >
    constexpr
    bool
    operator () () const
    {
        std::cout << __PRETTY_FUNCTION__ << std::endl;
        return true;
    }
};

int
main()
{
    print const print_{};
    enumerator< print const, 11, 7, 3 >{{print_}}();
    return EXIT_SUCCESS;
}

LIVE EXAMPLE

It works fine except for the expression f.template operator () < index(c, I)... >(), where indices pack index(c, I)... recognized as not constexpr.

Why is it so? I know the workaround using std::index_sequence, but compilation time differs too much.

How to generate desired sequences at compile time?

Aucun commentaire:

Enregistrer un commentaire