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_findTemplate Functiontemplate<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_findTemplate Function with Execution Policytemplate<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_notTemplate 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 All suggestions are welcome.
The summary information:
Which question it is a follow-up to?
A recursive_find_if Template Function with Unwrap Level Implementation in C++ and
recursive_invocable and recursive_project_invocable Concept Implementation in C++
What changes has been made in the code since last question?
I am trying to implement
recursive_findandrecursive_find_if_nottemplate functions in this post.Why a new review is being asked for?
Please review the implementation of
recursive_findandrecursive_find_if_nottemplate functions.
