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.

\$\endgroup\$

0

Your Answer

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