1
\$\begingroup\$

This is a follow-up question for A recursive_all_of Template Function Implementation in C++ and A recursive_count_if Function For Various Type Arbitrary Nested Iterable Implementation in C++. Besides recursive_all_of template function implementation, I am trying to implement recursive_any_of and recursive_none_of template functions.

The experimental implementation

  • Implementation of recursive_any_of and recursive_none_of template functions

    //  recursive_any_of template function implementation
    template<class T, class Proj = std::identity, class UnaryPredicate>
    constexpr auto recursive_any_of(T&& value, UnaryPredicate&& p, Proj proj = {})
    {
        return recursive_count_if_all(std::invoke(proj, value), p) > 0;
    }
    
    //  recursive_none_of template function implementation
    template<class T, class Proj = std::identity, class UnaryPredicate>
    constexpr auto recursive_none_of(T&& value, UnaryPredicate&& p, Proj proj = {})
    {
        return recursive_count_if_all(std::invoke(proj, value), p) == 0;
    }
    

Full Testing Code

The full testing code:

//  recursive_any_of and recursive_none_of Template Functions 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_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<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
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};
}

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

//  recursive_count_if template function implementation
template<class T, std::invocable<T> Pred>
constexpr std::size_t recursive_count_if_all(const T& input, const Pred& predicate)
{
    return predicate(input) ? std::size_t{1} : std::size_t{0};
}

template<std::ranges::input_range Range, class Pred>
requires (recursive_depth<Range>() != 0)
constexpr auto recursive_count_if_all(const Range& input, const Pred& predicate)
{
    return std::transform_reduce(std::ranges::cbegin(input), std::ranges::cend(input), std::size_t{}, std::plus<std::size_t>(), [predicate](auto&& element) {
        return recursive_count_if_all(element, predicate);
        });
}

template<std::size_t unwrap_level, class T, class Pred>
requires(unwrap_level <= recursive_depth<T>())
constexpr auto recursive_count_if(const T& input, const Pred& predicate)
{
    if constexpr (unwrap_level > 0)
    {
        return std::transform_reduce(std::ranges::cbegin(input), std::ranges::cend(input), std::size_t{}, std::plus<std::size_t>(), [predicate](auto&& element) {
            return recursive_count_if<unwrap_level - 1>(element, predicate);
            });
    }
    else
    {
        return predicate(input) ? 1 : 0;
    }
    
}

/*  recursive_all_of template function implementation
*/
template<class T, class Proj = std::identity, class UnaryPredicate>
constexpr auto recursive_all_of(T&& value, UnaryPredicate p, Proj proj = {}) {
    return std::invoke(p, std::invoke(proj, value));
}

template<std::ranges::input_range T, class Proj = std::identity, class UnaryPredicate>
constexpr auto recursive_all_of(T& inputRange, UnaryPredicate&& p, Proj proj = {}) {
    return std::ranges::all_of(inputRange, [&](auto&& range) {
        return recursive_all_of(range, std::forward<UnaryPredicate>(p), proj);
    }, proj);
}

//  recursive_any_of template function implementation
template<class T, class Proj = std::identity, class UnaryPredicate>
constexpr auto recursive_any_of(T&& value, UnaryPredicate&& p, Proj proj = {})
{
    return recursive_count_if_all(std::invoke(proj, value), p) > 0;
}

//  recursive_none_of template function implementation
template<class T, class Proj = std::identity, class UnaryPredicate>
constexpr auto recursive_none_of(T&& value, UnaryPredicate&& p, Proj proj = {})
{
    return recursive_count_if_all(std::invoke(proj, value), p) == 0;
}

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_any_of_tests()
{
    std::cout << "***recursive_any_of_tests function***\n";

    auto test_vectors_1 = n_dim_container_generator<std::vector, 4, int>(1, 3);
    test_vectors_1[0][0][0][0] = 3;
    std::cout << "Play with test_vectors_1:\n";
    
    if (recursive_any_of(test_vectors_1, [](int i) { return i == 2; }))
        std::cout << "2 is one of the elements in test_vectors_1\n";

    if (recursive_any_of(test_vectors_1, [](int i) { return i == 3; }))
        std::cout << "3 is one of the elements in test_vectors_1\n";
}

void recursive_none_of_tests()
{
    std::cout << "***recursive_none_of_tests function***\n";

    auto test_vectors_1 = n_dim_container_generator<std::vector, 4, int>(1, 3);
    test_vectors_1[0][0][0][0] = 3;
    std::cout << "Play with test_vectors_1:\n";
    
    if (recursive_none_of(test_vectors_1, [](int i) { return i == 0; }))
        std::cout << "None of the elements in test_vectors_1 is 0\n";
}

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

***recursive_any_of_tests function***
Play with test_vectors_1:
3 is one of the elements in test_vectors_1
***recursive_none_of_tests function***
Play with test_vectors_1:
None of the elements in test_vectors_1 is 0
Computation finished at Mon Jan 22 02:37:36 2024
elapsed time: 0.00119631

Godbolt link is here.

All suggestions are welcome.

The summary information:

\$\endgroup\$

1 Answer 1

1
\$\begingroup\$

This implementation is not short-circuiting

The standard library's std::any_of() and std::none_of() are short-circuiting: they stop iterating as soon as they know the answer. So for both std::any_of() and std::none_of(), it stops at the first position where the predicate returns true. Your version never stops until it has visited all the items.

Instead of counting, use finding to implement any_of(), all_of() and none_of(). You can still do that recursively.

Test all features of your functions

You wrote some test cases, but none of the tests use projection. As soon as you do you'll find out that your code doesn't handle projection correctly. You shouldn't handle it yourself anyway, ideally you just pass the projection on to recursive_count_if_all() (or better, a recursive_find_if()).

\$\endgroup\$
4
  • \$\begingroup\$ I found this one: en.cppreference.com/w/cpp/experimental/ranges/algorithm/find \$\endgroup\$
    – JimmyHu
    Commented Jan 22 at 9:19
  • \$\begingroup\$ > ...or better, a recursive_find_if()) I am thinking about the structure of recursive_find_if(), what kind return value it should be? A bool to indicate an element is found or not? \$\endgroup\$
    – JimmyHu
    Commented Jan 22 at 9:27
  • 1
    \$\begingroup\$ A bool would be one option, then it would be a bit like std::binary_search(). It's enough for any_of()/all_of()/none_of(), but maybe to make it more useful for other users, you could have it return a std::optional containing a tuple of a reference to the innermost container an item was found in, and an iterator into that container. \$\endgroup\$
    – G. Sliepen
    Commented Jan 22 at 9:41
  • \$\begingroup\$ Got it. Thank you for the suggestion. \$\endgroup\$
    – JimmyHu
    Commented Jan 22 at 9:56

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.