3
\$\begingroup\$

This is a follow-up question for A recursive_transform Template Function with Execution Policy, A recursive_transform Template Function Implementation with std::invocable Concept and Execution Policy in C++, A recursive_transform Template Function with Unwrap Level for Various Type Arbitrary Nested Iterable Implementation in C++ and A recursive_depth function for calculating depth of nested types implementation in C++. Considering that the previous std::for_each version recursive_transform doesn’t ensure deterministic behavior, the individual results could be emplaced into the output container in an arbitrary order because of the multiple factors. Therefore, another version recursive_transform template function which is order guaranteed and unwrap_level controlled has been proposed in this post. Referencing the latest call signature of std::ranges::transform, the concept std::copy_constructible is used on the input function parameter. Also, the similar way is used here.

The experimental implementation

  • Order guaranteed recursive_transform template function implementation:

    //  recursive_invoke_result_t implementation
    template<std::size_t, typename, typename>
    struct recursive_invoke_result { };
    
    template<typename T, std::copy_constructible F>
    struct recursive_invoke_result<0, F, T> { using type = std::invoke_result_t<F, T>; };
    
    template<std::size_t unwrap_level, typename F, template<typename...> typename Container, typename... Ts>
    requires (std::ranges::input_range<Container<Ts...>> &&
            requires { typename recursive_invoke_result<unwrap_level - 1, F, std::ranges::range_value_t<Container<Ts...>>>::type; })
    struct recursive_invoke_result<unwrap_level, F, Container<Ts...>>
    {
        using type = Container<typename recursive_invoke_result<unwrap_level - 1, F, std::ranges::range_value_t<Container<Ts...>>>::type>;
    };
    
    template<std::size_t unwrap_level, typename F, typename T>
    using recursive_invoke_result_t = typename recursive_invoke_result<unwrap_level, F, T>::type;
    
    //  recursive_variadic_invoke_result_t implementation
    template<std::size_t, typename, typename, typename...>
    struct recursive_variadic_invoke_result { };
    
    template<typename F, class...Ts1, template<class...>class Container1, typename... Ts>
    struct recursive_variadic_invoke_result<1, F, Container1<Ts1...>, Ts...>
    {
        using type = Container1<std::invoke_result_t<F,
            std::ranges::range_value_t<Container1<Ts1...>>,
            std::ranges::range_value_t<Ts>...>>;
    };
    
    template<std::size_t unwrap_level, typename F, class...Ts1, template<class...>class Container1, typename... Ts>
    requires (  std::ranges::input_range<Container1<Ts1...>> &&
                requires { typename recursive_variadic_invoke_result<
                                        unwrap_level - 1,
                                        F,
                                        std::ranges::range_value_t<Container1<Ts1...>>,
                                        std::ranges::range_value_t<Ts>...>::type; })                //  The rest arguments are ranges
    struct recursive_variadic_invoke_result<unwrap_level, F, Container1<Ts1...>, Ts...>
    {
        using type = Container1<
            typename recursive_variadic_invoke_result<
            unwrap_level - 1,
            F,
            std::ranges::range_value_t<Container1<Ts1...>>,
            std::ranges::range_value_t<Ts>...
            >::type>;
    };
    
    template<std::size_t unwrap_level, typename F, typename T1, typename... Ts>
    using recursive_variadic_invoke_result_t = typename recursive_variadic_invoke_result<unwrap_level, F, T1, Ts...>::type;
    
    template<typename OutputIt, std::copy_constructible NAryOperation, typename InputIt, typename... InputIts>
    OutputIt transform(OutputIt d_first, NAryOperation op, InputIt first, InputIt last, InputIts... rest) {
        while (first != last) {
            *d_first++ = op(*first++, (*rest++)...);
        }
        return d_first;
    }
    
    //  recursive_transform for the multiple parameters cases (the version with unwrap_level)
    template<std::size_t unwrap_level = 1, class F, class Arg1, class... Args>
    constexpr auto recursive_transform(const F& f, const Arg1& arg1, const Args&... args)
    {
        if constexpr (unwrap_level > 0)
        {
            static_assert(unwrap_level <= recursive_depth<Arg1>(),
                "unwrap level higher than recursion depth of input");
            recursive_variadic_invoke_result_t<unwrap_level, F, Arg1, Args...> output{};
            transform(
                std::inserter(output, std::ranges::end(output)),
                [&f](auto&& element1, auto&&... elements) { return recursive_transform<unwrap_level - 1>(f, element1, elements...); },
                std::ranges::cbegin(arg1),
                std::ranges::cend(arg1),
                std::ranges::cbegin(args)...
            );
            return output;
        }
        else
        {
            return f(arg1, args...);
        }
    }
    
    //  recursive_transform implementation (the version with unwrap_level, with execution policy)
    template<std::size_t unwrap_level = 1, class ExPo, class T, class F>
    requires (std::is_execution_policy_v<std::remove_cvref_t<ExPo>>)
    constexpr auto recursive_transform(ExPo execution_policy, const F& f, const T& input)
    {
        if constexpr (unwrap_level > 0)
        {
            static_assert(unwrap_level <= recursive_depth<T>(),
                "unwrap level higher than recursion depth of input");
            recursive_invoke_result_t<unwrap_level, F, T> output{};
            output.resize(input.size());
            std::mutex mutex;
            std::transform(execution_policy, std::ranges::cbegin(input), std::ranges::cend(input), std::ranges::begin(output),
                [&](auto&& element)
                {
                    std::lock_guard lock(mutex);
                    return recursive_transform<unwrap_level - 1>(execution_policy, f, element);
                });
            return output;
        }
        else
        {
            return f(input);
        }
    }
    

Full Testing Code

The full testing code:

#include <algorithm>
#include <cassert>
#include <concepts>
#include <execution>
#include <functional>
#include <iostream>
#include <iterator>
#include <ranges>
#include <string>
#include <vector>

//  recursive_depth function implementation
template<typename T>
constexpr std::size_t recursive_depth()
{
    return 0;
}

template<std::ranges::input_range Range>
constexpr std::size_t recursive_depth()
{
    return recursive_depth<std::ranges::range_value_t<Range>>() + 1;
}

//  recursive_invoke_result_t implementation
template<std::size_t, typename, typename>
struct recursive_invoke_result { };

template<typename T, typename F>
struct recursive_invoke_result<0, F, T> { using type = std::invoke_result_t<F, T>; };

template<std::size_t unwrap_level, typename F, template<typename...> typename Container, typename... Ts>
requires (std::ranges::input_range<Container<Ts...>> &&
        requires { typename recursive_invoke_result<unwrap_level - 1, F, std::ranges::range_value_t<Container<Ts...>>>::type; })
struct recursive_invoke_result<unwrap_level, F, Container<Ts...>>
{
    using type = Container<typename recursive_invoke_result<unwrap_level - 1, F, std::ranges::range_value_t<Container<Ts...>>>::type>;
};

template<std::size_t unwrap_level, typename F, typename T>
using recursive_invoke_result_t = typename recursive_invoke_result<unwrap_level, F, T>::type;

//  recursive_variadic_invoke_result_t implementation
template<std::size_t, typename, typename, typename...>
struct recursive_variadic_invoke_result { };

template<typename F, class...Ts1, template<class...>class Container1, typename... Ts>
struct recursive_variadic_invoke_result<1, F, Container1<Ts1...>, Ts...>
{
    using type = Container1<std::invoke_result_t<F,
        std::ranges::range_value_t<Container1<Ts1...>>,
        std::ranges::range_value_t<Ts>...>>;
};

template<std::size_t unwrap_level, typename F, class...Ts1, template<class...>class Container1, typename... Ts>
requires (  std::ranges::input_range<Container1<Ts1...>> &&
            requires { typename recursive_variadic_invoke_result<
                                    unwrap_level - 1,
                                    F,
                                    std::ranges::range_value_t<Container1<Ts1...>>,
                                    std::ranges::range_value_t<Ts>...>::type; })                //  The rest arguments are ranges
struct recursive_variadic_invoke_result<unwrap_level, F, Container1<Ts1...>, Ts...>
{
    using type = Container1<
        typename recursive_variadic_invoke_result<
        unwrap_level - 1,
        F,
        std::ranges::range_value_t<Container1<Ts1...>>,
        std::ranges::range_value_t<Ts>...
        >::type>;
};

template<std::size_t unwrap_level, typename F, typename T1, typename... Ts>
using recursive_variadic_invoke_result_t = typename recursive_variadic_invoke_result<unwrap_level, F, T1, Ts...>::type;

template<typename OutputIt, std::copy_constructible NAryOperation, typename InputIt, typename... InputIts>
OutputIt transform(OutputIt d_first, NAryOperation op, InputIt first, InputIt last, InputIts... rest) {
    while (first != last) {
        *d_first++ = op(*first++, (*rest++)...);
    }
    return d_first;
}

//  recursive_transform for the multiple parameters cases (the version with unwrap_level)
template<std::size_t unwrap_level = 1, class F, class Arg1, class... Args>
constexpr auto recursive_transform(const F& f, const Arg1& arg1, const Args&... args)
{
    if constexpr (unwrap_level > 0)
    {
        static_assert(unwrap_level <= recursive_depth<Arg1>(),
            "unwrap level higher than recursion depth of input");
        recursive_variadic_invoke_result_t<unwrap_level, F, Arg1, Args...> output{};
        transform(
            std::inserter(output, std::ranges::end(output)),
            [&f](auto&& element1, auto&&... elements) { return recursive_transform<unwrap_level - 1>(f, element1, elements...); },
            std::ranges::cbegin(arg1),
            std::ranges::cend(arg1),
            std::ranges::cbegin(args)...
        );
        return output;
    }
    else
    {
        return f(arg1, args...);
    }
}

//  recursive_transform implementation (the version with unwrap_level, with execution policy)
template<std::size_t unwrap_level = 1, class ExPo, class T, class F>
requires (std::is_execution_policy_v<std::remove_cvref_t<ExPo>>)
constexpr auto recursive_transform(ExPo execution_policy, const F& f, const T& input)
{
    if constexpr (unwrap_level > 0)
    {
        static_assert(unwrap_level <= recursive_depth<T>(),
            "unwrap level higher than recursion depth of input");
        recursive_invoke_result_t<unwrap_level, F, T> output{};
        output.resize(input.size());
        std::mutex mutex;
        std::transform(execution_policy, std::ranges::cbegin(input), std::ranges::cend(input), std::ranges::begin(output),
            [&](auto&& element)
            {
                std::lock_guard lock(mutex);
                return recursive_transform<unwrap_level - 1>(execution_policy, f, element);
            });
        return output;
    }
    else
    {
        return f(input);
    }
}

template<std::size_t dim, class T>
constexpr auto n_dim_vector_generator(T input, std::size_t times)
{
    if constexpr (dim == 0)
    {
        return input;
    }
    else
    {
        auto element = n_dim_vector_generator<dim - 1>(input, times);
        std::vector<decltype(element)> output(times, element);
        return output;
    }
}

void recursiveTransformTest();

int main()
{
    recursiveTransformTest();
    return 0;
}

void recursiveTransformTest()
{
    for (std::size_t N = 1; N < 10; N++)
    {
        std::size_t N1 = N, N2 = N, N3 = N;
        auto test_vector = n_dim_vector_generator<3>(0, 10);

        for (std::size_t z = 1; z <= N3; z++)
        {
            for (std::size_t y = 1; y <= N2; y++)
            {
                for (std::size_t x = 1; x <= N1; x++)
                {
                    test_vector.at(z - 1).at(y - 1).at(x - 1) = x * 100 + y * 10 + z;
                }
            }
        }
        auto expected = recursive_transform<3>([](auto&& element) {return element + 1; }, test_vector);
        auto actual = recursive_transform<3>(std::execution::par, [](auto&& element) {return element + 1; }, test_vector);
        std::cout << "N = " << N << ": " << std::to_string(actual == expected) << '\n';
    }
}

The output of the testing code above:

N = 1: 1
N = 2: 1
N = 3: 1
N = 4: 1
N = 5: 1
N = 6: 1
N = 7: 1
N = 8: 1
N = 9: 1

A Godbolt link is here.

All suggestions are welcome.

The summary information:

\$\endgroup\$

0

Your Answer

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

Browse other questions tagged or ask your own question.