4
\$\begingroup\$

This is a follow-up question for A recursive_copy_if Template Function Implementation in C++ and recursive_invocable and recursive_project_invocable Concept Implementation in C++. I am trying to implement recursive_copy_if template function with unwrap level in this post.

The experimental implementation

  • recursive_copy_if Template Function

    //  recursive_copy_if function implementation with unwrap level
template <std::size_t unwrap_level, std::ranges::input_range Range, class UnaryPredicate>
requires(recursive_invocable<unwrap_level, UnaryPredicate, Range>)
constexpr auto recursive_copy_if(const Range& input, const UnaryPredicate& unary_predicate)
{
    if constexpr(unwrap_level > 1)
    {
        Range output{};

        std::ranges::transform(
            std::ranges::cbegin(input),
            std::ranges::cend(input),
            std::inserter(output, std::ranges::end(output)),
            [&unary_predicate](auto&& element) { return recursive_copy_if<unwrap_level - 1>(element, unary_predicate); }
            );
        return output;
    }
    else
    {
        Range output{};
        std::ranges::copy_if(std::ranges::cbegin(input), std::ranges::cend(input),
            std::inserter(output, std::ranges::end(output)),
            unary_predicate);
        return output;
    }
}

  • The used recursive_invocable concept

    //  is_recursive_invocable template function implementation
template<std::size_t unwrap_level, class F, class... T>
requires(unwrap_level <= recursive_depth<T...>())
static constexpr bool is_recursive_invocable()
{
    if constexpr (unwrap_level == 0) {
        return std::invocable<F, T...>;
    } else {
        return is_recursive_invocable<
                    unwrap_level - 1,
                    F,
                    std::ranges::range_value_t<T>...>();
    }
}

//  recursive_invocable concept
template<std::size_t unwrap_level, class F, class... T>
concept recursive_invocable =
        is_recursive_invocable<unwrap_level, F, T...>();

Full Testing Code

The full testing code:

//  A recursive_copy_if Template Function Implementation with Unwrap Level Implementation in C++

#include <algorithm>
#include <array>
#include <cassert>
#include <chrono>
#include <complex>
#include <concepts>
#include <deque>
#include <exception>
#include <execution>
#include <functional>
#include <iostream>
#include <iterator>
#include <list>
#include <ranges>
#include <stdexcept>
#include <string>
#include <type_traits>
#include <utility>
#include <vector>

template<typename T>
concept is_inserterable = requires(T x)
{
    std::inserter(x, std::ranges::end(x));
};

#ifdef USE_BOOST_MULTIDIMENSIONAL_ARRAY
template<typename T>
concept is_multi_array = requires(T x)
{
    x.num_dimensions();
    x.shape();
    boost::multi_array(x);
};
#endif

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

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

//  recursive_depth template 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};
}

//  is_recursive_invocable template function implementation
template<std::size_t unwrap_level, class F, class... T>
requires(unwrap_level <= recursive_depth<T...>())
static constexpr bool is_recursive_invocable()
{
    if constexpr (unwrap_level == 0) {
        return std::invocable<F, T...>;
    } else {
        return is_recursive_invocable<
                    unwrap_level - 1,
                    F,
                    std::ranges::range_value_t<T>...>();
    }
}

//  recursive_invocable concept
template<std::size_t unwrap_level, class F, class... T>
concept recursive_invocable =
        is_recursive_invocable<unwrap_level, F, T...>();

//  is_recursive_project_invocable template function implementation
template<std::size_t unwrap_level, class Proj, class F, class... T>
requires(unwrap_level <= recursive_depth<T...>() &&
        recursive_invocable<unwrap_level, Proj, T...>)
static constexpr bool is_recursive_project_invocable()
{
    if constexpr (unwrap_level == 0) {
        return std::invocable<F, std::invoke_result_t<Proj, T...>>;
    } else {
        return is_recursive_project_invocable<
                    unwrap_level - 1,
                    Proj,
                    F,
                    std::ranges::range_value_t<T>...>();
    }
}

//  recursive_project_invocable concept
template<std::size_t unwrap_level, class Proj, class F, class... T>
concept recursive_project_invocable =
        is_recursive_project_invocable<unwrap_level, Proj, F, T...>();

//  recursive_copy_if function implementation with unwrap level
template <std::size_t unwrap_level, std::ranges::input_range Range, class UnaryPredicate>
requires(recursive_invocable<unwrap_level, UnaryPredicate, Range>)
constexpr auto recursive_copy_if(const Range& input, const UnaryPredicate& unary_predicate)
{
    if constexpr(unwrap_level > 1)
    {
        Range output{};
    
        std::ranges::transform(
            std::ranges::cbegin(input),
            std::ranges::cend(input),
            std::inserter(output, std::ranges::end(output)),
            [&unary_predicate](auto&& element) { return recursive_copy_if<unwrap_level - 1>(element, unary_predicate); }
            );
        return output;
    }
    else
    {
        Range output{};
        std::ranges::copy_if(std::ranges::cbegin(input), std::ranges::cend(input),
            std::inserter(output, std::ranges::end(output)),
            unary_predicate);
        return output;
    }
}

//  recursive_print implementation
template<std::ranges::input_range Range>
constexpr auto recursive_print(const Range& input, const int level = 0)
{
    auto 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&& x)
        {
            std::cout << std::string(level, ' ') << x << std::endl;
            return x;
        }
    );
    return output;
}

template<std::ranges::input_range Range> requires (std::ranges::input_range<std::ranges::range_value_t<Range>>)
constexpr auto recursive_print(const Range& input, const int level = 0)
{
    auto 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;
}

//  recursive_invoke_result_t implementation
//  from https://stackoverflow.com/a/65504127/6667035
template<typename, typename>
struct recursive_invoke_result { };

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

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

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

template <std::ranges::range Range>
constexpr auto get_output_iterator(Range& output)
{
    return std::inserter(output, std::ranges::end(output));
}

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

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
    {
        auto element = n_dim_array_generator<dim - 1, times>(input);
        std::array<decltype(element), times> output;
        std::fill(std::begin(output), std::end(output), element);
        return output;
    }
}

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

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

template<std::size_t dim, template<class...> class Container = std::vector, 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<dim - 1, Container, T>(input, times));
    }
}

//  Copy from https://stackoverflow.com/a/37264642/6667035
#ifndef NDEBUG
#   define M_Assert(Expr, Msg) \
    __M_Assert(#Expr, Expr, __FILE__, __LINE__, Msg)
#else
#   define M_Assert(Expr, Msg) ;
#endif

void __M_Assert(const char* expr_str, bool expr, const char* file, int line, const char* msg)
{
    if (!expr)
    {
        std::cerr << "Assert failed:\t" << msg << "\n"
            << "Expected:\t" << expr_str << "\n"
            << "Source:\t\t" << file << ", line " << line << "\n";
        abort();
    }
}

void recursive_copy_if_tests()
{
    //  std::vector<int> test case
    std::vector<int> test_vector_1 = {
        1, 2, 3, 4, 5, 6
    };

    std::vector<int> expected_result_1 = {
        2, 4, 6
    };
    M_Assert(
        recursive_copy_if<1>(test_vector_1, [](auto&& x) { return (x % 2) == 0; }) ==
        expected_result_1,
        "std::vector<int> test case failed");

    //  std::vector<std::vector<int>> test case
    std::vector<decltype(test_vector_1)> test_vector_2 = {
        test_vector_1, test_vector_1, test_vector_1
    };
    std::vector<std::vector<int>> expected_result_2 = {
        expected_result_1, expected_result_1, expected_result_1
    };
    M_Assert(
        recursive_copy_if<2>(test_vector_2, [](auto&& x) { return (x % 2) == 0; }) ==
        expected_result_2,
        "std::vector<std::vector<int>> test case failed");
    
    //  std::vector<std::string> test case
    std::vector<std::string> test_vector_3 = {
        "1", "2", "3", "4", "5", "6"
    };
    std::vector<std::string> expected_result_3 = {
        "1"
    };
    M_Assert(
        recursive_copy_if<1>(test_vector_3, [](auto&& x) { return (x == "1"); }) ==
        expected_result_3,
        "std::vector<std::string> test case failed");
    

    //  std::vector<std::vector<std::string>> test case
    std::vector<std::vector<std::string>> test_vector_4 = {
        test_vector_3, test_vector_3, test_vector_3
    };
    std::vector<std::vector<std::string>> expected_result_4 = {
        expected_result_3, expected_result_3, expected_result_3
    };
    M_Assert(
        recursive_copy_if<2>(test_vector_4, [](auto&& x) { return (x == "1"); }) ==
        expected_result_4,
        "std::vector<std::vector<std::string>> test case failed");

    //  std::deque<int> test case
    std::deque<int> test_deque_1;
    test_deque_1.push_back(1);
    test_deque_1.push_back(2);
    test_deque_1.push_back(3);
    test_deque_1.push_back(4);
    test_deque_1.push_back(5);
    test_deque_1.push_back(6);
    std::deque<int> expected_result_5;
    expected_result_5.push_back(1);
    M_Assert(
        recursive_copy_if<1>(test_deque_1, [](auto&& x) { return (x == 1); }) ==
        expected_result_5,
        "std::deque<int> test case failed"
    );

    //  std::deque<std::deque<int>> test case
    std::deque<decltype(test_deque_1)> test_deque_2;
    test_deque_2.push_back(test_deque_1);
    test_deque_2.push_back(test_deque_1);
    test_deque_2.push_back(test_deque_1);
    std::deque<decltype(expected_result_5)> expected_result_6;
    expected_result_6.push_back(expected_result_5);
    expected_result_6.push_back(expected_result_5);
    expected_result_6.push_back(expected_result_5);
    M_Assert(
        recursive_copy_if<2>(test_deque_2, [](auto&& x) { return (x == 1); }) ==
        expected_result_6,
        "std::deque<std::deque<int>> test case failed"
    );

    //  std::list<int> test case
    std::list<int> test_list_1 = { 1, 2, 3, 4, 5, 6 };
    std::list<int> expected_result_7 = {2, 4, 6};
    M_Assert(
        recursive_copy_if<1>(test_list_1, [](int x) { return (x % 2) == 0; }) ==
        expected_result_7,
        "std::list<int> test case failed"
    );

    //  std::list<std::list<int>> test case
    std::list<std::list<int>> test_list_2 = { test_list_1, test_list_1, test_list_1, test_list_1 };
    std::list<std::list<int>> expected_result_8 = {
        expected_result_7, expected_result_7, expected_result_7, expected_result_7
    };
    M_Assert(
            recursive_copy_if<2>(test_list_2, [](int x) { return (x % 2) == 0; }) ==
            expected_result_8,
            "std::list<std::list<int>> test case failed"
        );
    std::cout << "All tests passed!\n";
}

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

All tests passed!
Computation finished at Fri Mar 29 07:36:41 2024
elapsed time: 0.00130443

Godbolt link is here.

All suggestions are welcome.

The summary information:

\$\endgroup\$

1 Answer 1

Reset to default
2
\$\begingroup\$

Range is not just an input range

This is something I missed in my reviews of your previous questions. The parameter input is clearly an input range, so it's natural to restrict its type to std::ranges::input_range. However, Range is also used to create a new object that is used as an output range. So clearly, the constraint it wrong.

You also require that it is a range that you can use std::inserter() on.

What if unwrap_level == 0?

From your code I can see that you intend unwrap_level to be at least 1. However, what if the caller passes in 0? I would add a static_assert() to catch this case.

\$\endgroup\$
2
  • \$\begingroup\$ > However, Range is also used to create a new object that is used as an output range. Which concept should I used in this case? \$\endgroup\$ Commented Mar 29, 2024 at 18:41
  • 1
    \$\begingroup\$ There is no std::ranges::input_and_output_range unfortunately, you have to create your concept that checks that it is both std::ranges::input_range and is_insertable. \$\endgroup\$ Commented Mar 29, 2024 at 18:47

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.