2
\$\begingroup\$

This is a follow-up question for A recursive_foreach_all Template Function Implementation in C++. I am trying to implement recursive_all_of template function in this post.

The experimental implementation

  • recursive_all_of Template Functions Implementation

    namespace impl {

    template<std::ranges::input_range T, class UnaryPredicate>
    constexpr auto recursive_all_of(T& value, UnaryPredicate p) {
        return std::all_of(std::ranges::begin(value), std::ranges::end(value), p);
    }

    template<std::ranges::input_range T, class UnaryPredicate>
    requires(std::ranges::input_range<std::ranges::range_value_t<T>>)
    constexpr auto recursive_all_of(T& inputRange, UnaryPredicate p) {
        for (auto& item: inputRange)
        {
            if(impl::recursive_all_of(item, p) == false)
                return false;
        }
        return true;
    }
}

/*  recursive_all_of template function
*/
template<std::ranges::input_range T, class UnaryPredicate>
constexpr auto recursive_all_of(T& inputRange, UnaryPredicate p)
{
    return impl::recursive_all_of(inputRange, p);
}

//  A `recursive_all_of` Function Implementation in C++

#include <algorithm>
#include <array>
#include <chrono>
#include <concepts>
#include <deque>
#include <execution>
#include <exception>
#include <functional>
#include <iostream>
#include <ranges>
#include <string>
#include <utility>
#include <vector>

//  is_reservable concept
template<class T>
concept is_reservable = requires(T input)
{
    input.reserve(1);
};

//  is_sized concept, https://codereview.stackexchange.com/a/283581/231235
template<class T>
concept is_sized = requires(T x)
{
    std::size(x);
};

template<typename T>
concept is_summable = requires(T x) { x + x; };

//  recursive_unwrap_type_t struct implementation
template<std::size_t, typename, typename...>
struct recursive_unwrap_type { };

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

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

template<std::size_t unwrap_level, typename T1, typename... Ts>
using recursive_unwrap_type_t = typename recursive_unwrap_type<unwrap_level, T1, Ts...>::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;

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

template<   typename F, 
            template<class, std::size_t> class Container,
            typename T,
            std::size_t N>
struct recursive_array_invoke_result<1, F, Container<T, N>>
{
    using type = Container<
        std::invoke_result_t<F, std::ranges::range_value_t<Container<T, N>>>,
        N>;
};

template<   std::size_t unwrap_level,
            typename F, 
            template<class, std::size_t> class Container,
            typename T,
            std::size_t N>
requires (  std::ranges::input_range<Container<T, N>> &&
            requires { typename recursive_array_invoke_result<
                                    unwrap_level - 1,
                                    F,
                                    std::ranges::range_value_t<Container<T, N>>>::type; })                //  The rest arguments are ranges
struct recursive_array_invoke_result<unwrap_level, F, Container<T, N>>
{
    using type = Container<
        typename recursive_array_invoke_result<
        unwrap_level - 1,
        F,
        std::ranges::range_value_t<Container<T, N>>
        >::type, N>;
};

template<   std::size_t unwrap_level,
            typename F,
            template<class, std::size_t> class Container,
            typename T,
            std::size_t N>
using recursive_array_invoke_result_t = typename recursive_array_invoke_result<unwrap_level, F, Container<T, N>>::type;

//  recursive_array_unwrap_type struct implementation, https://stackoverflow.com/a/76347485/6667035
template<std::size_t, typename>
struct recursive_array_unwrap_type { };

template<template<class, std::size_t> class Container,
              typename T,
              std::size_t N>
struct recursive_array_unwrap_type<1, Container<T, N>>
{
    using type = std::ranges::range_value_t<Container<T, N>>;
};

template<std::size_t unwrap_level, template<class, std::size_t> class Container,
              typename T,
              std::size_t N>
requires (  std::ranges::input_range<Container<T, N>> &&
            requires { typename recursive_array_unwrap_type<
                                    unwrap_level - 1,
                                    std::ranges::range_value_t<Container<T, N>>>::type; })                //  The rest arguments are ranges
struct recursive_array_unwrap_type<unwrap_level, Container<T, N>>
{
    using type = typename recursive_array_unwrap_type<
        unwrap_level - 1,
        std::ranges::range_value_t<Container<T, N>>
        >::type;
};

template<std::size_t unwrap_level, class Container>
using recursive_array_unwrap_type_t = typename recursive_array_unwrap_type<unwrap_level, Container>::type;

//  https://codereview.stackexchange.com/a/253039/231235
template<template<class...> class Container = std::vector, std::size_t dim, class T>
constexpr auto n_dim_container_generator(T input, std::size_t times)
{
    if constexpr (dim == 0)
    {
        return input;
    }
    else
    {
        return Container(times, n_dim_container_generator<Container, dim - 1, T>(input, times));
    }
}

template<std::size_t dim, std::size_t times, class T>
constexpr auto n_dim_array_generator(T input)
{
    if constexpr (dim == 0)
    {
        return input;
    }
    else
    {
        std::array<decltype(n_dim_array_generator<dim - 1, times>(input)), times> output;
        for (size_t i = 0; i < times; i++)
        {
            output[i] = n_dim_array_generator<dim - 1, times>(input);
        }
        return output;
    }
}

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

template<typename T_Base, std::ranges::input_range Range>
requires (!std::same_as<Range, T_Base>)
constexpr std::size_t recursive_depth()
{
    return recursive_depth<T_Base, std::ranges::range_value_t<Range>>() + std::size_t{1};
}

/*  recursive_foreach_all template function performs specific function on input container exhaustively
    https://codereview.stackexchange.com/a/286525/231235
*/
namespace impl {

    template<class F, class Proj = std::identity>
    struct recursive_for_each_state {
        F f;
        Proj proj;
    };

    template<class T, class State>
    requires(!std::ranges::input_range<T>)
    constexpr void recursive_foreach_all(T& value, State& state) {
        std::invoke(state.f, std::invoke(state.proj, value));
    }

    template<std::ranges::input_range T, class State>
    constexpr void recursive_foreach_all(T& inputRange, State& state) {
        for (auto& item: inputRange)
            impl::recursive_foreach_all(item, state);
    }

    template<class T, class State>
    requires(!std::ranges::input_range<T>)
    constexpr void recursive_reverse_foreach_all(T& value, State& state) {
        std::invoke(state.f, std::invoke(state.proj, value));
    }

    template<std::ranges::input_range T, class State>
    constexpr void recursive_reverse_foreach_all(T& inputRange, State& state) {
        for (auto& item: inputRange | std::views::reverse)
            impl::recursive_reverse_foreach_all(item, state);
    }

    template<std::ranges::input_range T, class UnaryPredicate>
    constexpr auto recursive_all_of(T& value, UnaryPredicate p) {
        return std::all_of(std::ranges::begin(value), std::ranges::end(value), p);
    }

    template<std::ranges::input_range T, class UnaryPredicate>
    requires(std::ranges::input_range<std::ranges::range_value_t<T>>)
    constexpr auto recursive_all_of(T& inputRange, UnaryPredicate p) {
        for (auto& item: inputRange)
        {
            if(impl::recursive_all_of(item, p) == false)
                return false;
        }
        return true;
    }
}

template<class T, class Proj = std::identity, class F>
constexpr auto recursive_foreach_all(T& inputRange, F f, Proj proj = {})
{
    impl::recursive_for_each_state state(std::move(f), std::move(proj));
    impl::recursive_foreach_all(inputRange, state);
    return std::make_pair(inputRange.end(), std::move(state.f));
}

template<class T, class Proj = std::identity, class F>
constexpr auto recursive_reverse_foreach_all(T& inputRange, F f, Proj proj = {})
{
    impl::recursive_for_each_state state(std::move(f), std::move(proj));
    impl::recursive_reverse_foreach_all(inputRange, state);
    return std::make_pair(inputRange.end(), std::move(state.f));
}

template<class T, class I, class F>
constexpr auto recursive_fold_left_all(const T& inputRange, I init, F f)
{
    recursive_foreach_all(inputRange, [&](auto& value) {
        init = std::invoke(f, init, value);
    });

    return init;
}

template<class T, class I, class F>
constexpr auto recursive_fold_right_all(const T& inputRange, I init, F f)
{
    recursive_reverse_foreach_all(inputRange, [&](auto& value) {
        init = std::invoke(f, value, init);
    });

    return init;
}

/*  recursive_all_of template function
*/
template<std::ranges::input_range T, class UnaryPredicate>
constexpr auto recursive_all_of(T& inputRange, UnaryPredicate p)
{
    return impl::recursive_all_of(inputRange, p);
}

template<std::ranges::input_range T>
constexpr auto recursive_print(const T& input, const int level = 0)
{
    T output = input;
    std::cout << std::string(level, ' ') << "Level " << level << ":" << std::endl;
    std::transform(input.cbegin(), input.cend(), output.begin(), 
        [level](auto&& x)
        {
            std::cout << std::string(level, ' ') << x << std::endl;
            return x;
        }
    );
    return output;
}

template<std::ranges::input_range T>
requires (std::ranges::input_range<std::ranges::range_value_t<T>>)
constexpr T recursive_print(const T& input, const int level = 0)
{
    T output = input;
    std::cout << std::string(level, ' ') << "Level " << level << ":" << std::endl;
    std::ranges::transform(std::ranges::cbegin(input), std::ranges::cend(input), std::ranges::begin(output),
        [level](auto&& element)
        {
            return recursive_print(element, level + 1);
        }
    );
    return output;
}

void recursive_all_of_tests()
{
    auto test_vectors_1 = n_dim_container_generator<std::vector, 4, int>(1, 3);
    test_vectors_1[0][0][0][0] = 2;
    std::cout << "Play with test_vectors_1:\n";
    
    if (recursive_all_of(test_vectors_1, [](int i) { return i % 2 == 0; }))
        std::cout << "All numbers are even\n";

    auto test_vectors_2 = n_dim_container_generator<std::vector, 4, int>(2, 3);
    test_vectors_2[0][0][0][0] = 4;
    std::cout << "Play with test_vectors_2:\n";
    
    if (recursive_all_of(test_vectors_2, [](int i) { return i % 2 == 0; }))
        std::cout << "All numbers are even\n";
    return;
}

int main()
{
    auto start = std::chrono::system_clock::now();
    recursive_all_of_tests();
    auto end = std::chrono::system_clock::now();
    std::chrono::duration<double> elapsed_seconds = end - start;
    std::time_t end_time = std::chrono::system_clock::to_time_t(end);
    std::cout << "Computation finished at " << std::ctime(&end_time) << "elapsed time: " << elapsed_seconds.count() << '\n';
    return 0;
}

The output of the test code above:

Play with test_vectors_1:
Play with test_vectors_2:
All numbers are even
Computation finished at Fri Jan 19 12:05:11 2024
elapsed time: 4.4001e-05

Godbolt link is here.

All suggestions are welcome.

The summary information:

  • Which question it is a follow-up to?

    A recursive_foreach_all Template Function Implementation in C++

  • What changes has been made in the code since last question?

    I am trying to implement recursive_all_of template function in this post.

  • Why a new review is being asked for?

    Please review the recursive_all_of template function and all suggestions are welcome.

\$\endgroup\$

2 Answers 2

Reset to default
1
\$\begingroup\$

Match the interface of std::ranges::all_of()

When you implement a recursive version of a STL algorithm, make sure you match the interface of the STL algorithm as best as possible.

Note how std::ranges::all_of() takes the input by forwarding reference. This is important since it will be able to take anything as a parameter, including r-value references, which your code does not.

Another difference is that std::ranges::all_of() allows you to specify a projection.

The STL also puts constraints on the type of the unary predicate. This helps produce somewhat better error messages in case an incompatible predicate is passed.

Make more use of std::ranges::all_of()

The recursing case can be implemented using std::ranges::all_of() instead of using a for-loop:

template<std::ranges::input_range T, class UnaryPredicate>
requires(std::ranges::input_range<std::ranges::range_value_t<T>>)
constexpr auto recursive_all_of(T&& inputRange, UnaryPredicate p) {
    return std::ranges::all_of(inputRange, [&](auto&& range) {
        return impl::recursive_all_of(range, p);
    });
}

Simplify the base case

The code is a little bit more complex than necessary because you made the innermost range the base case. But if you instead use the values of the innermost range the base case your code can look like:

template<class T, class UnaryPredicate>
constexpr auto recursive_all_of(T&& value, UnaryPredicate p) {
    return std::invoke(p, value);
}

template<std::ranges::input_range T, class UnaryPredicate>
constexpr auto recursive_all_of(T& inputRange, UnaryPredicate p) {
    return std::ranges::all_of(inputRange, [&](auto&& range) {
        return impl::recursive_all_of(range, p);
    });
}

There should be no impact on performance. Also, the declaration of recursive_all_of() outside namespace impl can stay the same, so it will still be an error to try to call it on something that isn't a range to begin with.

Consider passing the predicate by reference to the implementation

Predicates can be function objects or lambdas that contain state. By passing it by value to recursive calls, copies of the state are made, but that might be unexpected for the caller. I mentioned the same issue in the review of your recursive_foreach_all(). I think a simple fix is to have the predicate passed by reference to impl::recursive_all_of().

\$\endgroup\$
0
\$\begingroup\$

To support std::string

It is not generic enough! Considering the following cases of std::string.

void recursive_all_of_tests()
{
    //  Failed to support test cases with std::string
    auto test_vector_string = n_dim_container_generator<std::vector, 4, std::string>("1", 3);
    if(recursive_all_of(test_vector_string, [](std::string i) { return i == "1"; }))
        std::cout << "All string elements are 1\n";
    if(recursive_all_of(test_vector_string, [](std::string i) { return i == "2"; }))
        std::cout << "All string elements are 2\n";
    return;
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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