permutation_range

permutation_range.cpp

#include <cassert>
#include <utility>
#include <tuple>
#include <functional>

#include <iostream>
#include <vector>
#include <array>
#include <list>
#include <memory>

template<bool UseConst = false>
struct Op
{
    template<class U>
    static auto begin(U&& u) { return std::begin(u); }
    template<class U>
    static auto end(U&& u) { return std::end(u); }
    
    template<class U>
    static auto begin(std::reference_wrapper<U> u) { return std::begin(u.get()); }
    template<class U>
    static auto end(std::reference_wrapper<U> u) { return std::end(u.get()); }
};

template<>
struct Op<true>
{
    template<class U>
    static auto begin(U const& u) { return std::begin(u); }
    template<class U>
    static auto end(U const& u) { return std::end(u); }
    
    template<class U>
    static auto begin(std::reference_wrapper<U> const u) { return std::begin(u.get()); }
    template<class U>
    static auto end(std::reference_wrapper<U> const u) { return std::end(u.get()); }
};
    
template<class... T>
struct permutation_range
{
private:
    template<int N>
    struct Int
    {
        static int const value = N;
    };
    
    template<class U>
    static auto wrap(U&& u)
    {
        return std::forward<U>(u);
    }

    template<class U>
    static auto wrap(U& u)
    {
        return std::ref(u);
    }

    template<class U>
    static auto wrap(const U& u)
    {
        return std::cref<U>(u);
    }
    
    using range_set = std::tuple<decltype(wrap(std::declval<T>()))...>;
    using this_type = permutation_range<T...>;

public:
    template<class OwnerType, bool UseConst>
    struct iterator_base;
    
    permutation_range(T&&... ranges)
    :   ranges_(wrap(std::forward<T>(ranges))...)
    {}
    
    using iterator = iterator_base<this_type, false>;
    using const_iterator = iterator_base<typename std::add_const<this_type>::type, true>;
    
    auto begin()
    {
        if(is_valid()) {
            return iterator(*this, init_with_begin{});
        } else {
            return end();
        }
    }
    
    auto begin() const
    {
        if(is_valid()) {
            return const_iterator(*this, init_with_begin{});
        } else {
            return end();
        }
    }
    
    auto end() { return iterator(*this); }
    auto end() const { return const_iterator(*this); }
    
    const_iterator cbegin() const { return begin(); }
    const_iterator cend() const { return end(); }
    
    struct init_with_begin {};
    
    template<class OwnerType, bool UseConst>
    struct iterator_base
    {        
        using this_type = iterator_base<OwnerType, UseConst>;
        using owner_type = OwnerType;
        using op = Op<UseConst>;
     
        using indices = std::index_sequence_for<T...>;
        using iterator_set = std::tuple<decltype(op::begin(std::declval<T>()))...>;
        
        // initialize with ends
        iterator_base(OwnerType& owner)
        :   owner_(&owner)
        ,   iters_(get_end_impl(owner, indices{}))
        {}
        
        iterator_base(OwnerType& owner, init_with_begin)
        :   owner_(&owner)
        ,   iters_(get_begin_impl(owner, indices{}))
        {}
        
        decltype(auto) operator*() 
        {
            assert(!is_end());
            return dereference(indices{});
        }
        
        this_type & operator++()
        {
            assert(!is_end());
            next(Int<sizeof...(T)-1>());
            return *this;
        }
                   
        this_type operator++(int)
        {
            auto ret = *this;
            next();
            return *ret;
        }
        
        bool operator==(this_type const &rhs)
        {
            assert(owner_ == rhs.owner_);
            return
                (is_end() && rhs.is_end())
                ||
                (iters_ == rhs.iters_);
        }
        
        bool operator!=(this_type const &rhs)
        {
            return !(*this == rhs);
        }
            
    private:
        template<class Ix, Ix... I>
        auto get_begin_impl(owner_type& owner, std::integer_sequence<Ix, I...>)
        {
            return std::make_tuple(op::begin(std::get<I>(owner.ranges_))...);
        }
        
        template<class Ix, Ix... I>
        auto get_end_impl(owner_type& owner, std::integer_sequence<Ix, I...>)
        {
            return std::make_tuple(op::end(std::get<I>(owner.ranges_))...);
        }

        template <class Ix, Ix... I>
        auto dereference(std::integer_sequence<Ix, I...>)
        {
            return std::make_tuple(wrap(*std::get<I>(iters_))...);
        }
                   
        bool is_end() const
        {
            return std::get<0>(iters_) == op::end(std::get<0>(owner_->ranges_));
        }
                   
        template<int N>
        void next(Int<N>)
        {        
            auto &iter = std::get<N>(iters_);
            auto &range = std::get<N>(owner_->ranges_);
            ++iter;

            if(iter == op::end(range)) {
                iter = op::begin(range);
                next(Int<N-1>());
            }
        }

        void next(Int<-1>)
        {
            std::get<0>(iters_) = op::end(std::get<0>(owner_->ranges_));
        }
        
    private:
        owner_type *owner_;
        iterator_set iters_;
    };
    
private:
    bool is_valid() const
    {
        return is_valid(Int<sizeof...(T)-1>());
    }
          
    template<int N>
    bool is_valid(Int<N>) const
    {
        auto &range = std::get<N>(ranges_);
        return (Op<true>::begin(range) != Op<true>::end(range)) && is_valid(Int<N-1>());
    }
    
    bool is_valid(Int<-1>) const { return true; }
    
    range_set ranges_;
};

template<class... Range>
auto make_permutation_range(Range&&... range)
{
    using result_type
        = permutation_range<decltype(std::forward<Range>(range))...>;
    return result_type(std::forward<Range>(range)...);
}

int main()
{
    std::vector<int> x = { 1, 2, 3 };
    std::list<std::string> y = { "Alice", "Bob", "Charlie" };
    double z[] = { 3.14159, 1.41421, 2.71828 };
    std::vector<std::unique_ptr<int>> ps;
    ps.push_back(std::make_unique<int>(10));
    ps.push_back(std::make_unique<int>(20));
    
    auto ranges = make_permutation_range(x, std::move(y), z, std::move(ps));

    auto begin = ranges.begin();
    auto end = ranges.end();
    
    for(auto it = begin; it != end; ++it) {
        auto v = *it;
        std::cout 
            << std::get<0>(v) << ", "
            << std::get<1>(v) << ", "
            << std::get<2>(v) << ", "
            << *std::get<3>(v) << ", "
            << std::endl;
    }
}