2
\$\begingroup\$

This is a follow-up question for A recursive_find_if Template Function with Unwrap Level Implementation in C++ and recursive_invocable and recursive_project_invocable Concept Implementation in C++. I am trying to implement recursive_find and recursive_find_if_not template functions in this post.

The experimental implementation

  • recursive_find Template Function

    template<std::size_t unwrap_level, class R, class T, class Proj = std::identity>
requires(recursive_invocable<unwrap_level, Proj, R>)
constexpr auto recursive_find(R&& range, T&& target, Proj&& proj = {})
{
    if constexpr (unwrap_level)
    {
        return std::ranges::find_if(range, [&](auto& element) {
            return recursive_find<unwrap_level - 1>(element, target, proj);
        }) != std::ranges::end(range);
    }
    else
    {
        return range == std::invoke(proj, target);
    }
}

  • recursive_find Template Function with Execution Policy

    template<std::size_t unwrap_level, class ExecutionPolicy, class R, class T, class Proj = std::identity>
requires(recursive_invocable<unwrap_level, Proj, R>&&
         std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>>)
constexpr auto recursive_find(ExecutionPolicy execution_policy, R&& range, T&& target, Proj&& proj = {})
{
    if constexpr (unwrap_level)
    {
        return std::find_if(execution_policy,
                    std::ranges::begin(range),
                    std::ranges::end(range),
                    [&](auto& element) {
            return recursive_find<unwrap_level - 1>(execution_policy, element, target, proj);
        }) != std::ranges::end(range);
    }
    else
    {
        return range == std::invoke(proj, target);
    }
}

  • recursive_find_if_not Template Function

    /*  recursive_find_if_not template function implementation with unwrap level
*/
template<std::size_t unwrap_level, class T, class Proj = std::identity, 
         recursive_projected_invocable<unwrap_level, Proj, T> UnaryPredicate>
constexpr auto recursive_find_if_not(T&& value, UnaryPredicate&& p, Proj&& proj = {}) {
    if constexpr (unwrap_level > 0)
    {
        return std::ranges::find_if(value, [&](auto& element) {
            return recursive_find_if_not<unwrap_level - 1>(element, p, proj);
        }) != std::ranges::end(value);
    }
    else
    {
        return !std::invoke(p, std::invoke(proj, value));
    }
}

Full Testing Code

The full testing code:

//  recursive_find and recursive_find_if_not Template Functions Implementation in C++

#include <algorithm>
#include <array>
#include <cassert>
#include <chrono>
#include <concepts>
#include <deque>
#include <execution>
#include <exception>
//#include <experimental/ranges/algorithm>
#include <experimental/array>
#include <functional>
#include <iostream>
#include <iterator>
#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<std::size_t dim, class T, template<class...> class Container = std::vector>
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, T, Container>(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
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 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<class F, std::size_t unwrap_level, class Proj, class... T>
concept recursive_projected_invocable =
        is_recursive_project_invocable<unwrap_level, Proj, F, T...>();

/*  recursive_all_of template function implementation with unwrap level
*/
template<std::size_t unwrap_level, class T, class Proj = std::identity, 
         recursive_projected_invocable<unwrap_level, Proj, T> UnaryPredicate>
constexpr auto recursive_all_of(T&& value, UnaryPredicate&& p, Proj&& proj = {}) {
    if constexpr (unwrap_level > 0)
    {
        return std::ranges::all_of(value, [&](auto&& element) {
            return recursive_all_of<unwrap_level - 1>(element, p, proj);
        });
    }
    else
    {
        return std::invoke(p, std::invoke(proj, value));
    }
}

/*  recursive_find template function implementation with unwrap level
*/
template<std::size_t unwrap_level, class R, class T, class Proj = std::identity>
requires(recursive_invocable<unwrap_level, Proj, R>)
constexpr auto recursive_find(R&& range, T&& target, Proj&& proj = {})
{
    if constexpr (unwrap_level)
    {
        return std::ranges::find_if(range, [&](auto& element) {
            return recursive_find<unwrap_level - 1>(element, target, proj);
        }) != std::ranges::end(range);
    }
    else
    {
        return range == std::invoke(proj, target);
    }
}

template<std::size_t unwrap_level, class ExecutionPolicy, class R, class T, class Proj = std::identity>
requires(recursive_invocable<unwrap_level, Proj, R>&&
         std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>>)
constexpr auto recursive_find(ExecutionPolicy execution_policy, R&& range, T&& target, Proj&& proj = {})
{
    if constexpr (unwrap_level)
    {
        return std::find_if(execution_policy,
                    std::ranges::begin(range),
                    std::ranges::end(range),
                    [&](auto& element) {
            return recursive_find<unwrap_level - 1>(execution_policy, element, target, proj);
        }) != std::ranges::end(range);
    }
    else
    {
        return range == std::invoke(proj, target);
    }
}

/*  recursive_find_if template function implementation with unwrap level
*/
template<std::size_t unwrap_level, class T, class Proj = std::identity, 
         recursive_projected_invocable<unwrap_level, Proj, T> UnaryPredicate>
constexpr auto recursive_find_if(T&& value, UnaryPredicate&& p, Proj&& proj = {}) {
    if constexpr (unwrap_level > 0)
    {
        return std::ranges::find_if(value, [&](auto& element) {
            return recursive_find_if<unwrap_level - 1>(element, p, proj);
        }) != std::ranges::end(value);
    }
    else
    {
        return std::invoke(p, std::invoke(proj, value));
    }
}

/*  recursive_find_if_not template function implementation with unwrap level
*/
template<std::size_t unwrap_level, class T, class Proj = std::identity, 
         recursive_projected_invocable<unwrap_level, Proj, T> UnaryPredicate>
constexpr auto recursive_find_if_not(T&& value, UnaryPredicate&& p, Proj&& proj = {}) {
    if constexpr (unwrap_level > 0)
    {
        return std::ranges::find_if(value, [&](auto& element) {
            return recursive_find_if_not<unwrap_level - 1>(element, p, proj);
        }) != std::ranges::end(value);
    }
    else
    {
        return !std::invoke(p, std::invoke(proj, value));
    }
}

//  recursive_any_of template function implementation with unwrap level
template<std::size_t unwrap_level, class T, class Proj = std::identity, 
         recursive_projected_invocable<unwrap_level, Proj, T> UnaryPredicate>
constexpr auto recursive_any_of(T&& value, UnaryPredicate&& p, Proj&& proj = {})
{
    return recursive_find_if<unwrap_level>(value, p, proj);
}

//  recursive_none_of template function implementation with unwrap level
template<std::size_t unwrap_level, class T, class Proj = std::identity, 
         recursive_projected_invocable<unwrap_level, Proj, T> UnaryPredicate>
constexpr auto recursive_none_of(T&& value, UnaryPredicate&& p, Proj&& proj = {})
{
    return !recursive_any_of<unwrap_level>(value, p, proj);
}

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_find_tests()
{
    auto test_vectors_1 = n_dim_container_generator<4, int, std::vector>(1, 3);
    test_vectors_1[0][0][0][0] = 2;
    assert(recursive_find<4>(test_vectors_1, 2));
    assert(recursive_find<4>(std::execution::par, test_vectors_1, 2));

    auto test_vectors_2 = n_dim_container_generator<4, int, std::vector>(3, 3);
    assert(recursive_find<4>(test_vectors_2, 2) == false);
    assert(recursive_find<4>(test_vectors_2, 3));
    assert(recursive_find<4>(test_vectors_2, 4) == false);
    
    //  Tests with std::string
    auto test_vector_string = n_dim_container_generator<4, std::string, std::vector>("1", 3);
    assert(recursive_find<4>(test_vector_string, "1"));
    assert(recursive_find<4>(test_vector_string, "2") == false);

    //  Tests with std::string, projection
    assert(recursive_find<4>(
        test_vector_string,
        "1",
        [](auto&& element) {return std::to_string(std::stoi(element) + 1); }) == false);
    
    //  Tests with std::array of std::string
    std::array<std::string, 3> word_array1 = {"foo", "foo", "foo"};
    assert(recursive_find<1>(word_array1, "foo"));
    assert(recursive_find<1>(word_array1, "bar") == false);

    //  Tests with std::deque of std::string
    std::deque<std::string> word_deque1 = {"foo", "foo", "foo", "bar"};
    assert(recursive_find<1>(word_deque1, "foo"));
    assert(recursive_find<1>(word_deque1, "bar"));
    assert(recursive_find<1>(word_deque1, "abcd") == false);
    assert(recursive_find<2>(word_deque1, 'a'));
    assert(recursive_find<2>(word_deque1, 'b'));
    assert(recursive_find<2>(word_deque1, 'c') == false);

    std::vector<std::wstring> wstring_vector1{};
    for(int i = 0; i < 4; ++i)
    {
        wstring_vector1.push_back(std::to_wstring(1));
    }
    assert(recursive_find<1>(wstring_vector1, std::to_wstring(1)));
    assert(recursive_find<1>(wstring_vector1, std::to_wstring(2)) == false);

    std::vector<std::u8string> u8string_vector1{};
    for(int i = 0; i < 4; ++i)
    {
        u8string_vector1.push_back(u8"\u20AC2.00");
    }
    assert(recursive_find<1>(u8string_vector1, u8"\u20AC2.00"));
    assert(recursive_find<1>(u8string_vector1, u8"\u20AC1.00") == false);
    
    std::pmr::string pmr_string1 = "123";
    std::vector<std::pmr::string> pmr_string_vector1 = {pmr_string1, pmr_string1, pmr_string1};
    assert(recursive_find<1>(pmr_string_vector1, "123"));
    assert(recursive_find<1>(pmr_string_vector1, "456") == false);
    
    std::cout << "All tests passed!\n";

    return;
}

void recursive_find_if_not_tests()
{
    auto test_vectors_1 = n_dim_container_generator<4, int, std::vector>(1, 3);
    test_vectors_1[0][0][0][0] = 2;
    assert(recursive_find_if_not<4>(test_vectors_1, [](auto&& i) { return i == 1; }));

    auto test_vectors_2 = n_dim_container_generator<4, int, std::vector>(3, 3);
    assert(recursive_find_if_not<4>(test_vectors_2, [](auto&& i) { return i == 3; }) == false);

    //  Tests with std::string
    auto test_vector_string = n_dim_container_generator<4, std::string, std::vector>("1", 3);
    assert(recursive_find_if_not<4>(test_vector_string, [](auto&& i) { return i == "1"; }) == false);
    assert(recursive_find_if_not<4>(test_vector_string, [](auto&& i) { return i == "2"; }));
    assert(recursive_find_if_not<4>(test_vector_string, [](auto&& i) { return i == "3"; }));

    //  Tests with std::string, projection
    assert(recursive_find_if_not<4>(
        test_vector_string,
        [](auto&& i) { return i == "1"; },
        [](auto&& element) {return std::to_string(std::stoi(element) + 1); }));
    assert(recursive_find_if_not<4>(
        test_vector_string,
        [](auto&& i) { return i == "2"; },
        [](auto&& element) {return std::to_string(std::stoi(element) + 1); }) == false);

    //  Tests with std::array of std::string
    std::array<std::string, 3> word_array1 = {"foo", "foo", "foo"};
    assert(recursive_find_if_not<1>(word_array1, [](auto&& i) { return i == "foo"; }) == false);
    assert(recursive_find_if_not<1>(word_array1, [](auto&& i) { return i == "bar"; }));

    std::cout << "All tests passed!\n";

    return;
}

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

The output of the test code above:

All tests passed!
All tests passed!
Computation finished at Sat Feb 24 02:56:36 2024
elapsed time: 0.00221348

Godbolt link is here.

All suggestions are welcome.

The summary information:

\$\endgroup\$
1
  • 1
    \$\begingroup\$ A recursive unwrap view and using the normal algorithms would probably be better... \$\endgroup\$ Commented Feb 26, 2024 at 12:44

1 Answer 1

Reset to default
1
\$\begingroup\$

Looks good, except for one issue that I see I also missed in my previous reviews of your recursive find algorithms:

The projection is applied incorrectly

The projection should always be applied to the elements of the range, not to the target value. So you should write this instead:

return target == std::invoke(proj, range);

This also means that your tests that are using projection are wrong.

\$\endgroup\$
1
  • \$\begingroup\$ Oh, indeed. Great catch! \$\endgroup\$ Commented Feb 24, 2024 at 9:11

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.