diff --git a/libcxx/docs/Status/RangesAlgorithms.csv b/libcxx/docs/Status/RangesAlgorithms.csv --- a/libcxx/docs/Status/RangesAlgorithms.csv +++ b/libcxx/docs/Status/RangesAlgorithms.csv @@ -2,9 +2,9 @@ Search,any_of,Christopher Di Bella,`D105793 `_ Search,all_of,Christopher Di Bella,`D105793 `_ Search,none_of,Christopher Di Bella,`D105793 `_ -Search,find,Christopher Di Bella,`D105456 `_ -Search,find_if,Christopher Di Bella,`D105792 `_ -Search,find_if_not,Christopher Di Bella,`D105792 `_ +Search,find,Nikolas Klauser,n/a, Complete +Search,find_if,Nikolas Klauser,n/a, Complete +Search,find_if_not,Nikolas Klauser,n/a, Complete Search,find_first_of,Not assigned,n/a,Not started Search,adjacent_find,Not assigned,n/a,Not started Search,mismatch,Not assigned,n/a,Not started diff --git a/libcxx/include/CMakeLists.txt b/libcxx/include/CMakeLists.txt --- a/libcxx/include/CMakeLists.txt +++ b/libcxx/include/CMakeLists.txt @@ -66,6 +66,9 @@ __algorithm/pop_heap.h __algorithm/prev_permutation.h __algorithm/push_heap.h + __algorithm/ranges_find.h + __algorithm/ranges_find_if.h + __algorithm/ranges_find_if_not.h __algorithm/ranges_max_element.h __algorithm/ranges_min_element.h __algorithm/ranges_swap_ranges.h diff --git a/libcxx/include/__algorithm/ranges_find.h b/libcxx/include/__algorithm/ranges_find.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__algorithm/ranges_find.h @@ -0,0 +1,62 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP___ALGORITHM_RANGES_FIND_H +#define _LIBCPP___ALGORITHM_RANGES_FIND_H + +#include <__algorithm/ranges_find_if.h> +#include <__config> +#include <__functional/identity.h> +#include <__functional/invoke.h> +#include <__functional/ranges_operations.h> +#include <__iterator/concepts.h> +#include <__iterator/projected.h> +#include <__ranges/access.h> +#include <__ranges/concepts.h> +#include <__ranges/dangling.h> +#include <__utility/move.h> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +#if !defined(_LIBCPP_HAS_NO_CONCEPTS) && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +_LIBCPP_BEGIN_NAMESPACE_STD + +namespace ranges { +namespace __find { +struct __fn { + template _Sp, class _Tp, class _Proj = identity> + requires indirect_binary_predicate, const _Tp*> + _LIBCPP_HIDE_FROM_ABI constexpr + _Ip operator()(_Ip __first, _Sp __last, const _Tp& __value, _Proj __proj = {}) const { + auto __pred = [&](const auto& __e) { return __value == __e; }; + return __find_if::__fn::__go(std::move(__first), std::move(__last), __pred, __proj); + } + + template + requires indirect_binary_predicate, _Proj>, const _Tp*> + _LIBCPP_HIDE_FROM_ABI constexpr + borrowed_iterator_t<_Rp> operator()(_Rp&& __r, const _Tp& __value, _Proj __proj = {}) const { + auto __pred = [&](const auto& __e) { return __value == __e; }; + return __find_if::__fn::__go(ranges::begin(__r), ranges::end(__r), __pred, __proj); + } +}; +} // namespace __find + +inline namespace __cpo { + inline constexpr auto find = __find::__fn{}; +} // namespace __cpo +} // namespace ranges + +_LIBCPP_END_NAMESPACE_STD + +#endif // !defined(_LIBCPP_HAS_NO_CONCEPTS) && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +#endif // _LIBCPP___ALGORITHM_RANGES_FIND_H diff --git a/libcxx/include/__algorithm/ranges_find_if.h b/libcxx/include/__algorithm/ranges_find_if.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__algorithm/ranges_find_if.h @@ -0,0 +1,69 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP___ALGORITHM_RANGES_FIND_IF_H +#define _LIBCPP___ALGORITHM_RANGES_FIND_IF_H + +#include <__config> +#include <__functional/identity.h> +#include <__functional/invoke.h> +#include <__functional/ranges_operations.h> +#include <__iterator/concepts.h> +#include <__iterator/projected.h> +#include <__ranges/access.h> +#include <__ranges/concepts.h> +#include <__ranges/dangling.h> +#include <__utility/move.h> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +#if !defined(_LIBCPP_HAS_NO_CONCEPTS) && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +_LIBCPP_BEGIN_NAMESPACE_STD + +namespace ranges { +namespace __find_if { +struct __fn { + template + _LIBCPP_HIDE_FROM_ABI static constexpr + _Ip __go(_Ip __first, _Sp __last, _Pred& __pred, _Proj& __proj) { + for (; __first != __last; ++__first) { + if (std::invoke(__pred, std::invoke(__proj, *__first))) + break; + } + return __first; + } + + template _Sp, class _Proj = identity, + indirect_unary_predicate> _Pred> + _LIBCPP_HIDE_FROM_ABI constexpr + _Ip operator()(_Ip __first, _Sp __last, _Pred __pred, _Proj __proj = {}) const { + return __go(std::move(__first), std::move(__last), __pred, __proj); + } + + template , _Proj>> _Pred> + _LIBCPP_HIDE_FROM_ABI constexpr + borrowed_iterator_t<_Rp> operator()(_Rp&& __r, _Pred __pred, _Proj __proj = {}) const { + return __go(ranges::begin(__r), ranges::end(__r), __pred, __proj); + } +}; +} // namespace __find_if + +inline namespace __cpo { + inline constexpr auto find_if = __find_if::__fn{}; +} // namespace __cpo +} // namespace ranges + +_LIBCPP_END_NAMESPACE_STD + +#endif // !defined(_LIBCPP_HAS_NO_CONCEPTS) && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +#endif // _LIBCPP___ALGORITHM_RANGES_FIND_IF_H diff --git a/libcxx/include/__algorithm/ranges_find_if_not.h b/libcxx/include/__algorithm/ranges_find_if_not.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__algorithm/ranges_find_if_not.h @@ -0,0 +1,63 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP___ALGORITHM_RANGES_FIND_IF_NOT_H +#define _LIBCPP___ALGORITHM_RANGES_FIND_IF_NOT_H + +#include <__algorithm/ranges_find_if.h> +#include <__config> +#include <__functional/identity.h> +#include <__functional/invoke.h> +#include <__functional/ranges_operations.h> +#include <__iterator/concepts.h> +#include <__iterator/projected.h> +#include <__ranges/access.h> +#include <__ranges/concepts.h> +#include <__ranges/dangling.h> +#include <__utility/forward.h> +#include <__utility/move.h> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +#if !defined(_LIBCPP_HAS_NO_CONCEPTS) && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +_LIBCPP_BEGIN_NAMESPACE_STD + +namespace ranges { +namespace __find_if_not { +struct __fn { + template _Sp, class _Proj = identity, + indirect_unary_predicate> _Pred> + _LIBCPP_HIDE_FROM_ABI constexpr + _Ip operator()(_Ip __first, _Sp __last, _Pred __pred, _Proj __proj = {}) const { + auto __pred2 = [&](auto&& __e) { return !std::invoke(__pred, std::forward(__e)); }; + return __find_if::__fn::__go(std::move(__first), std::move(__last), __pred2, __proj); + } + + template , _Proj>> _Pred> + _LIBCPP_HIDE_FROM_ABI constexpr + borrowed_iterator_t<_Rp> operator()(_Rp&& __r, _Pred __pred, _Proj __proj = {}) const { + auto __pred2 = [&](auto&& __e) { return !std::invoke(__pred, std::forward(__e)); }; + return __find_if::__fn::__go(ranges::begin(__r), ranges::end(__r), __pred2, __proj); + } +}; +} // namespace __find_if_not + +inline namespace __cpo { + inline constexpr auto find_if_not = __find_if_not::__fn{}; +} // namespace __cpo +} // namespace ranges + +_LIBCPP_END_NAMESPACE_STD + +#endif // !defined(_LIBCPP_HAS_NO_CONCEPTS) && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +#endif // _LIBCPP___ALGORITHM_RANGES_FIND_IF_NOT_H diff --git a/libcxx/include/algorithm b/libcxx/include/algorithm --- a/libcxx/include/algorithm +++ b/libcxx/include/algorithm @@ -44,6 +44,31 @@ template, Proj>> Comp = ranges::less> // since C++20 constexpr borrowed_iterator_t min_element(R&& r, Comp comp = {}, Proj proj = {}); + + template S, class T, class Proj = identity> + requires indirect_binary_predicate, const T*> + constexpr I find(I first, S last, const T& value, Proj proj = {}); // since C++20 + template + requires indirect_binary_predicate, Proj>, const T*> + constexpr borrowed_iterator_t + find(R&& r, const T& value, Proj proj = {}); // since C++20 + + template S, class Proj = identity, + indirect_unary_predicate> Pred> + constexpr I find_if(I first, S last, Pred pred, Proj proj = {}); // since C++20 + template, Proj>> Pred> + constexpr borrowed_iterator_t + find_if(R&& r, Pred pred, Proj proj = {}); // since C++20 + + template S, class Proj = identity, + indirect_unary_predicate> Pred> + constexpr I find_if_not(I first, S last, Pred pred, Proj proj = {}); // since C++20 + + template, Proj>> Pred> + constexpr borrowed_iterator_t + find_if_not(R&& r, Pred pred, Proj proj = {}); // since C++20 } template @@ -763,6 +788,9 @@ #include <__algorithm/pop_heap.h> #include <__algorithm/prev_permutation.h> #include <__algorithm/push_heap.h> +#include <__algorithm/ranges_find.h> +#include <__algorithm/ranges_find_if.h> +#include <__algorithm/ranges_find_if_not.h> #include <__algorithm/ranges_max_element.h> #include <__algorithm/ranges_min_element.h> #include <__algorithm/ranges_swap_ranges.h> diff --git a/libcxx/include/module.modulemap b/libcxx/include/module.modulemap --- a/libcxx/include/module.modulemap +++ b/libcxx/include/module.modulemap @@ -294,6 +294,9 @@ module pop_heap { private header "__algorithm/pop_heap.h" } module prev_permutation { private header "__algorithm/prev_permutation.h" } module push_heap { private header "__algorithm/push_heap.h" } + module ranges_find { private header "__algorithm/ranges_find.h" } + module ranges_find_if { private header "__algorithm/ranges_find_if.h" } + module ranges_find_if_not { private header "__algorithm/ranges_find_if_not.h" } module ranges_max_element { private header "__algorithm/ranges_max_element.h" } module ranges_min_element { private header "__algorithm/ranges_min_element.h" } module ranges_swap_ranges { private header "__algorithm/ranges_swap_ranges.h" } diff --git a/libcxx/test/libcxx/diagnostics/detail.headers/algorithm/ranges_find.module.verify.cpp b/libcxx/test/libcxx/diagnostics/detail.headers/algorithm/ranges_find.module.verify.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/libcxx/diagnostics/detail.headers/algorithm/ranges_find.module.verify.cpp @@ -0,0 +1,15 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +// REQUIRES: modules-build + +// WARNING: This test was generated by 'generate_private_header_tests.py' +// and should not be edited manually. + +// expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_find.h'}} +#include <__algorithm/ranges_find.h> diff --git a/libcxx/test/libcxx/diagnostics/detail.headers/algorithm/ranges_find_if.module.verify.cpp b/libcxx/test/libcxx/diagnostics/detail.headers/algorithm/ranges_find_if.module.verify.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/libcxx/diagnostics/detail.headers/algorithm/ranges_find_if.module.verify.cpp @@ -0,0 +1,15 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +// REQUIRES: modules-build + +// WARNING: This test was generated by 'generate_private_header_tests.py' +// and should not be edited manually. + +// expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_find_if.h'}} +#include <__algorithm/ranges_find_if.h> diff --git a/libcxx/test/libcxx/diagnostics/detail.headers/algorithm/ranges_find_if_not.module.verify.cpp b/libcxx/test/libcxx/diagnostics/detail.headers/algorithm/ranges_find_if_not.module.verify.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/libcxx/diagnostics/detail.headers/algorithm/ranges_find_if_not.module.verify.cpp @@ -0,0 +1,15 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +// REQUIRES: modules-build + +// WARNING: This test was generated by 'generate_private_header_tests.py' +// and should not be edited manually. + +// expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_find_if_not.h'}} +#include <__algorithm/ranges_find_if_not.h> diff --git a/libcxx/test/std/algorithms/alg.nonmodifying/alg.find/ranges.find.pass.cpp b/libcxx/test/std/algorithms/alg.nonmodifying/alg.find/ranges.find.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/algorithms/alg.nonmodifying/alg.find/ranges.find.pass.cpp @@ -0,0 +1,112 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +// + +// UNSUPPORTED: c++03, c++11, c++14, c++17 +// UNSUPPORTED: libcpp-no-concepts +// UNSUPPORTED: libcpp-has-no-incomplete-ranges + +// template S, class T, class Proj = identity> +// requires indirect_binary_predicate, const T*> +// constexpr I ranges::find(I first, S last, const T& value, Proj proj = {}); +// template +// requires indirect_binary_predicate, Proj>, const T*> +// constexpr borrowed_iterator_t +// ranges::find(R&& r, const T& value, Proj proj = {}); + +#include +#include +#include +#include + +#include "test_iterators.h" + +template +constexpr void test_iterators() { + { + int a[] = {1, 2, 3, 4}; + std::same_as auto ret = std::ranges::find(It(a), Sent(It(a + 4)), 4); + assert(base(ret) == a + 3); + assert(*ret == 4); + } + { + int a[] = {1, 2, 3, 4}; + auto range = std::ranges::subrange(It(a), Sent(It(a + 4))); + std::same_as auto ret = std::ranges::find(range, 4); + assert(base(ret) == a + 3); + assert(*ret == 4); + } +} + +constexpr bool test() { + test_iterators, sentinel_wrapper>>(); + test_iterators>(); + test_iterators>(); + test_iterators>(); + + { // check that projections are used properly + { + int a[] = {1, 2, 3, 4}; + auto ret = std::ranges::find(a, a + 4, a + 3, [](int& i){ return &i; }); + assert(ret == a + 3); + } + { + int a[] = {1, 2, 3, 4}; + auto ret = std::ranges::find(a, a + 4, a + 3, [](int& i){ return &i; }); + assert(ret == a + 3); + } + } + + { // check that ranges::dangling is returned + [[maybe_unused]] std::same_as auto ret = + std::ranges::find(std::array {1, 2}, 3); + } + + { // check that an iterator is returned with a borrowing range + int a[] = {1, 2, 3, 4}; + std::same_as auto ret = std::ranges::find(std::views::all(a), 1); + assert(ret == a); + assert(*ret == 1); + } + + { // check that std::invoke is used + struct S { int i; }; + S a[] = { S{1}, S{3}, S{2} }; + std::same_as auto ret = std::ranges::find(a, 4, &S::i); + assert(ret == a + 3); + } + + { // count predicate invocation count + { + int a[] = {1, 2, 3, 4}; + int projection_count = 0; + auto ret = std::ranges::find(a, a + 4, 2, [&](int i) { ++projection_count; return i; }); + assert(ret == a + 1); + assert(*ret == 2); + assert(projection_count == 2); + } + { + int a[] = {1, 2, 3, 4}; + int projection_count = 0; + auto ret = std::ranges::find(a, 2, [&](int i) { ++projection_count; return i; }); + assert(ret == a + 1); + assert(*ret == 2); + assert(projection_count == 2); + } + } + + return true; +} + +int main(int, char**) { + test(); + static_assert(test()); + + return 0; +} diff --git a/libcxx/test/std/algorithms/alg.nonmodifying/alg.find/ranges.find_if.pass.cpp b/libcxx/test/std/algorithms/alg.nonmodifying/alg.find/ranges.find_if.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/algorithms/alg.nonmodifying/alg.find/ranges.find_if.pass.cpp @@ -0,0 +1,120 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +// + +// UNSUPPORTED: c++03, c++11, c++14, c++17 +// UNSUPPORTED: libcpp-no-concepts +// UNSUPPORTED: libcpp-has-no-incomplete-ranges + +// template S, class Proj = identity, +// indirect_unary_predicate> Pred> +// constexpr I ranges::find_if(I first, S last, Pred pred, Proj proj = {}); +// template, Proj>> Pred> +// constexpr borrowed_iterator_t +// ranges::find_if(R&& r, Pred pred, Proj proj = {}); + +#include +#include +#include +#include + +#include "test_iterators.h" + +template +constexpr void test_iterators() { + { + int a[] = {1, 2, 3, 4}; + std::same_as auto ret = std::ranges::find_if(It(a), Sent(It(a + 4)), [c = 0](int) mutable { return c++ > 2; }); + assert(base(ret) == a + 3); + assert(*ret == 4); + } + { + int a[] = {1, 2, 3, 4}; + auto range = std::ranges::subrange(It(a), Sent(It(a + 4))); + std::same_as auto ret = std::ranges::find_if(range, [c = 0](int) mutable { return c++ > 2; }); + assert(base(ret) == a + 3); + assert(*ret == 4); + } +} + +constexpr bool test() { + test_iterators, sentinel_wrapper>>(); + test_iterators>(); + test_iterators>(); + test_iterators>(); + + { // check that projections are used properly + { + int a[] = {1, 2, 3, 4}; + auto ret = std::ranges::find_if(a, a + 4, [&](int* p) { return p == a + 3; }, [](int& i){ return &i; }); + assert(ret == a + 3); + } + { + int a[] = {1, 2, 3, 4}; + auto ret = std::ranges::find_if(a, [&](int* p) { return p == a + 3; }, [](int& i){ return &i; }); + assert(ret == a + 3); + } + } + + { // check that ranges::dangling is returned + [[maybe_unused]] std::same_as auto ret = + std::ranges::find_if(std::array {1, 2}, [](int){ return false; }); + } + + { // check that an iterator is returned with a borrowing range + int a[] = {1, 2, 3, 4}; + std::same_as auto ret = std::ranges::find_if(std::views::all(a), [](int){ return true; }); + assert(ret == a); + assert(*ret == 1); + } + + { // check that std::invoke is used + struct S { int i; }; + S a[] = { S{1}, S{3}, S{2} }; + std::same_as auto ret = std::ranges::find_if(a, [](int) { return false; }, &S::i); + assert(ret == a + 3); + } + + { // count projection and predicate invocation count + { + int a[] = {1, 2, 3, 4}; + int predicate_count = 0; + int projection_count = 0; + auto ret = std::ranges::find_if(a, a + 4, + [&](int i) { ++predicate_count; return i == 2; }, + [&](int i) { ++projection_count; return i; }); + assert(ret == a + 1); + assert(*ret == 2); + assert(predicate_count == 2); + assert(projection_count == 2); + } + { + int a[] = {1, 2, 3, 4}; + int predicate_count = 0; + int projection_count = 0; + auto ret = std::ranges::find_if(a, + [&](int i) { ++predicate_count; return i == 2; }, + [&](int i) { ++projection_count; return i; }); + assert(ret == a + 1); + assert(*ret == 2); + assert(predicate_count == 2); + assert(projection_count == 2); + } + } + + return true; +} + +int main(int, char**) { + test(); + static_assert(test()); + + return 0; +} diff --git a/libcxx/test/std/algorithms/alg.nonmodifying/alg.find/ranges.find_if_not.pass.cpp b/libcxx/test/std/algorithms/alg.nonmodifying/alg.find/ranges.find_if_not.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/algorithms/alg.nonmodifying/alg.find/ranges.find_if_not.pass.cpp @@ -0,0 +1,120 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +// + +// UNSUPPORTED: c++03, c++11, c++14, c++17 +// UNSUPPORTED: libcpp-no-concepts +// UNSUPPORTED: libcpp-has-no-incomplete-ranges + +// template S, class Proj = identity, +// indirect_unary_predicate> Pred> +// constexpr I ranges::find_if_not(I first, S last, Pred pred, Proj proj = {}); +// template, Proj>> Pred> +// constexpr borrowed_iterator_t +// ranges::find_if_not(R&& r, Pred pred, Proj proj = {}); + +#include +#include +#include +#include + +#include "test_iterators.h" + +template +constexpr void test_iterators() { + { + int a[] = {1, 2, 3, 4}; + std::same_as auto ret = std::ranges::find_if_not(It(a), Sent(It(a + 4)), [c = 0](int) mutable { return c++ <= 2; }); + assert(base(ret) == a + 3); + assert(*ret == 4); + } + { + int a[] = {1, 2, 3, 4}; + auto range = std::ranges::subrange(It(a), Sent(It(a + 4))); + std::same_as auto ret = std::ranges::find_if_not(range, [c = 0](int) mutable { return c++ <= 2; }); + assert(base(ret) == a + 3); + assert(*ret == 4); + } +} + +constexpr bool test() { + test_iterators, sentinel_wrapper>>(); + test_iterators>(); + test_iterators>(); + test_iterators>(); + + { // check that projections are used properly + { + int a[] = {1, 2, 3, 4}; + auto ret = std::ranges::find_if_not(a, a + 4, [&](int* p) { return p != a + 3; }, [](int& i){ return &i; }); + assert(ret == a + 3); + } + { + int a[] = {1, 2, 3, 4}; + auto ret = std::ranges::find_if_not(a, [&](int* p) { return p != a + 3; }, [](int& i){ return &i; }); + assert(ret == a + 3); + } + } + + { // check that ranges::dangling is returned + [[maybe_unused]] std::same_as auto ret = + std::ranges::find_if_not(std::array {1, 2}, [](int){ return true; }); + } + + { // check that an iterator is returned with a borrowing range + int a[] = {1, 2, 3, 4}; + std::same_as auto ret = std::ranges::find_if_not(std::views::all(a), [](int){ return false; }); + assert(ret == a); + assert(*ret == 1); + } + + { // check that std::invoke is used + struct S { int i; }; + S a[] = { S{1}, S{3}, S{2} }; + std::same_as auto ret = std::ranges::find_if_not(a, [](int) { return true; }, &S::i); + assert(ret == a + 3); + } + + { // count projection and predicate invocation count + { + int a[] = {1, 2, 3, 4}; + int predicate_count = 0; + int projection_count = 0; + auto ret = std::ranges::find_if_not(a, a + 4, + [&](int i) { ++predicate_count; return i != 2; }, + [&](int i) { ++projection_count; return i; }); + assert(ret == a + 1); + assert(*ret == 2); + assert(predicate_count == 2); + assert(projection_count == 2); + } + { + int a[] = {1, 2, 3, 4}; + int predicate_count = 0; + int projection_count = 0; + auto ret = std::ranges::find_if_not(a, + [&](int i) { ++predicate_count; return i != 2; }, + [&](int i) { ++projection_count; return i; }); + assert(ret == a + 1); + assert(*ret == 2); + assert(predicate_count == 2); + assert(projection_count == 2); + } + } + + return true; +} + +int main(int, char**) { + test(); + static_assert(test()); + + return 0; +}