2
\$\begingroup\$

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

The experimental implementation

  • recursive_reverse_foreach_all template function implementation

    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_reverse_foreach_all helper function implementation

    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_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<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));
}

Full Testing Code

The full testing code:

//  A `recursive_fold_right_all` 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_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<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;
}

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;
}

struct Sum {
    void operator()(int n) { sum += n; }
    int sum {0};
};

void recursive_fold_left_all_tests()
{
    auto test_vectors = n_dim_container_generator<std::vector, 4, int>(1, 3);

    std::cout << "Play with test_vectors:\n\n";
    
    std::cout << "recursive_fold_left_all function test with vectors / std::plus<>(): \n";
    auto recursive_fold_left_all_result1 = recursive_fold_left_all(test_vectors, static_cast<int>(1), std::plus<>());
    std::cout << recursive_fold_left_all_result1 << "\n\n";

    std::cout << "recursive_fold_left_all function test with vectors / std::multiplies<>(): \n";
    auto recursive_fold_left_all_result2 = recursive_fold_left_all(test_vectors, static_cast<int>(2), std::multiplies<>());
    std::cout << recursive_fold_left_all_result2 << "\n\n";

    //  From: https://en.cppreference.com/w/cpp/algorithm/ranges/fold_left
    std::vector<std::pair<char, float>> data {{'A', 2.f}, {'B', 3.f}, {'C', 3.5f}};
    auto recursive_fold_left_all_result3 = recursive_fold_left_all
    (
        data | std::ranges::views::values, 2.0f, std::multiplies<>()
    );
    std::cout << "recursive_fold_left_all_result3: " << recursive_fold_left_all_result3 << '\n';

    std::vector<std::string> vs {"A", "B", "C", "D"};
    std::string initial_string = "A";
    // use a program defined function object (lambda-expression):
    auto recursive_fold_left_all_result4 = recursive_fold_left_all
    (
        vs, initial_string, std::plus<>()
    );
    std::cout << "recursive_fold_left_all_result4: " << recursive_fold_left_all_result4 << '\n';

    return;
}

void recursive_fold_right_all_tests()
{
    auto test_vectors = n_dim_container_generator<std::vector, 4, int>(1, 3);

    std::cout << "Play with test_vectors:\n\n";
    
    std::cout << "recursive_fold_right_all function test with vectors / std::plus<>(): \n";
    auto recursive_fold_right_all_result1 = recursive_fold_right_all(test_vectors, static_cast<int>(1), std::plus<>());
    std::cout << recursive_fold_right_all_result1 << "\n\n";

    std::cout << "recursive_fold_right_all function test with vectors / std::multiplies<>(): \n";
    auto recursive_fold_right_all_result2 = recursive_fold_right_all(test_vectors, static_cast<int>(2), std::multiplies<>());
    std::cout << recursive_fold_right_all_result2 << "\n\n";

    auto v = {1, 2, 3, 4, 5, 6, 7, 8};
    std::string initial_string = "A";
    // Use a program defined function object (lambda-expression):
    std::string recursive_fold_right_all_result3 = recursive_fold_right_all
    (
        v, initial_string, [](int x, std::string s) { return s + ':' + std::to_string(x); }
    );
    std::cout << "recursive_fold_right_all_result3: " << recursive_fold_right_all_result3 << '\n';

    std::vector<std::string> vs {"A", "B", "C", "D"};
    // use a program defined function object (lambda-expression):
    auto recursive_fold_right_all_result4 = recursive_fold_right_all
    (
        vs, initial_string, std::plus<>()
    );
    std::cout << "recursive_fold_right_all_result4: " << recursive_fold_right_all_result4 << '\n';

    return;
}

int main()
{
    auto start = std::chrono::system_clock::now();
    recursive_fold_right_all_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:

recursive_fold_right_all function test with vectors / std::plus<>(): 
82

recursive_fold_right_all function test with vectors / std::multiplies<>(): 
2

recursive_fold_right_all_result3: A:8:7:6:5:4:3:2:1
recursive_fold_right_all_result4: ABCDA
Computation finished at Thu Nov  9 05:34:39 2023
elapsed time: 0.00150025

Godbolt link is here.

All suggestions are welcome.

The summary information:

  • Which question it is a follow-up to?

    A recursive_fold_left_all Template Function Implementation in C++

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

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

  • Why a new review is being asked for?

    Please review recursive_fold_right_all template function implementation and all suggestions are welcome.

Improve this question
\$\endgroup\$

0

Reset to default

Your Answer

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