diff --git a/libcxx/include/__algorithm/is_partitioned.h b/libcxx/include/__algorithm/is_partitioned.h --- a/libcxx/include/__algorithm/is_partitioned.h +++ b/libcxx/include/__algorithm/is_partitioned.h @@ -9,7 +9,17 @@ #ifndef _LIBCPP___ALGORITHM_IS_PARTITIONED_H #define _LIBCPP___ALGORITHM_IS_PARTITIONED_H +#include <__algorithm/find_if.h> +#include <__algorithm/find_if_not.h> #include <__config> +#include <__function_like.h> +#include <__functional/identity.h> +#include <__functional/reference_wrapper.h> +#include <__iterator/concepts.h> +#include <__iterator/projected.h> +#include <__ranges/access.h> +#include <__ranges/concepts.h> +#include <__utility/move.h> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) #pragma GCC system_header @@ -36,6 +46,41 @@ return true; } +#if !defined(_LIBCPP_HAS_NO_RANGES) + +namespace ranges { + struct __is_partitioned_fn final : __function_like { + constexpr explicit __is_partitioned_fn(__tag __x) noexcept : __function_like(__x) {} + + template _Sp, class _Proj = identity, + indirect_unary_predicate> _Pred> + _LIBCPP_NODISCARD_EXT constexpr + bool operator()(_Ip __first, _Sp __last, _Pred __pred, _Proj __proj = {}) const { + auto __pred_ref = _VSTD::ref(__pred); + auto __proj_ref = _VSTD::ref(__proj); + + __first = ranges::find_if_not(_VSTD::move(__first), __last, __pred_ref, __proj_ref); + if (__first == __last) { + return true; + } + + ++__first; + return ranges::find_if(_VSTD::move(__first), _VSTD::move(__last), __pred_ref, __proj_ref) == __last; + } + + template, _Proj>> _Pred> + _LIBCPP_NODISCARD_EXT constexpr + bool operator()(_Rp&& __r, _Pred __pred, _Proj __proj = {}) const { + return (*this)(ranges::begin(__r), ranges::end(__r), _VSTD::ref(__pred), _VSTD::ref(__proj)); + } + }; + + inline constexpr auto is_partitioned = __is_partitioned_fn(__function_like::__tag()); +} // namespace ranges + +#endif // !defined(_LIBCPP_HAS_NO_RANGES) + _LIBCPP_END_NAMESPACE_STD _LIBCPP_POP_MACROS diff --git a/libcxx/include/__algorithm/partition_point.h b/libcxx/include/__algorithm/partition_point.h --- a/libcxx/include/__algorithm/partition_point.h +++ b/libcxx/include/__algorithm/partition_point.h @@ -10,8 +10,23 @@ #define _LIBCPP___ALGORITHM_PARTITION_POINT_H #include <__config> +#include <__debug> #include <__algorithm/half_positive.h> -#include +#include <__algorithm/is_partitioned.h> +#include <__function_like.h> +#include <__functional/identity.h> +#include <__functional/invoke.h> +#include <__functional/reference_wrapper.h> +#include <__iterator/advance.h> +#include <__iterator/distance.h> +#include <__iterator/next.h> +#include <__iterator/iterator_traits.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 @@ -44,6 +59,55 @@ return __first; } +#if !defined(_LIBCPP_HAS_NO_RANGES) + +namespace ranges { + struct __partition_point_fn final : __function_like { + constexpr explicit __partition_point_fn(__tag __x) noexcept : __function_like(__x) {} + + template _Sp, class _Proj = identity, + indirect_unary_predicate> _Pred> + _LIBCPP_NODISCARD_EXT constexpr + _Ip operator()(_Ip __first, const _Sp __last, _Pred __pred, _Proj __proj = {}) const { + // This assertion breaks the logarithmic complexity requirement, but since it is only evaluated + // when a user opts into a debug level, the non-conformance is deemed acceptable, since it is + // useful for catching violated precondition bugs. + _LIBCPP_ASSERT(ranges::is_partitioned(__first, __last, _VSTD::ref(__pred), _VSTD::ref(__proj)), + "partition_point precondition:\n" + "\tthe projected elements of the range [`first`, `last`) are partitioned with respect to `pred`."); + + auto __distance = 0; + for (auto __i = __first; __i != __last; ++__i) ++__distance; // FIXME: replace with ranges::distance + + while (__distance != 0) { + const auto __half_distance = _VSTD::__half_positive(__distance); + auto __midpoint = _VSTD::next(__first, __half_distance); + + if (_VSTD::invoke(__pred, _VSTD::invoke(__proj, *__midpoint))) { + __first = _VSTD::next(_VSTD::move(__midpoint)); + __distance -= __half_distance + 1; + } + else { + __distance = __half_distance; + } + } + + return __first; + } + + template, _Proj>> _Pred> + _LIBCPP_NODISCARD_EXT constexpr + borrowed_iterator_t<_Rp> operator()(_Rp&& __r, _Pred __pred, _Proj __proj = {}) const { + return (*this)(ranges::begin(__r), ranges::end(__r), _VSTD::ref(__pred), _VSTD::ref(__proj)); + } + }; + + inline constexpr auto partition_point = __partition_point_fn(__function_like::__tag()); +} // namespace ranges + +#endif // !defined(_LIBCPP_HAS_NO_RANGES) + _LIBCPP_END_NAMESPACE_STD _LIBCPP_POP_MACROS diff --git a/libcxx/include/algorithm b/libcxx/include/algorithm --- a/libcxx/include/algorithm +++ b/libcxx/include/algorithm @@ -366,6 +366,14 @@ constexpr bool // constexpr in C++20 is_partitioned(InputIterator first, InputIterator last, Predicate pred); +template S, class Proj = identity, + indirect_unary_predicate> Pred> + constexpr bool ranges::is_partitioned(I first, S last, Pred pred, Proj proj = {}); + +template, Proj>> Pred> + constexpr bool ranges::is_partitioned(R&& r, Pred pred, Proj proj = {}); + template constexpr ForwardIterator // constexpr in C++20 partition(ForwardIterator first, ForwardIterator last, Predicate pred); @@ -385,6 +393,14 @@ constexpr ForwardIterator // constexpr in C++20 partition_point(ForwardIterator first, ForwardIterator last, Predicate pred); +template S, class Proj = identity, + indirect_unary_predicate> Pred> + constexpr I ranges::partition_point(I first, S last, Pred pred, Proj proj = {}); // since C++20 +template, Proj>> Pred> + constexpr borrowed_iterator_t + ranges::partition_point(R&& r, Pred pred, Proj proj = {}); // since C++20 + template constexpr bool // constexpr in C++20 is_sorted(ForwardIterator first, ForwardIterator last); diff --git a/libcxx/include/module.modulemap b/libcxx/include/module.modulemap --- a/libcxx/include/module.modulemap +++ b/libcxx/include/module.modulemap @@ -265,7 +265,10 @@ module inplace_merge { header "__algorithm/inplace_merge.h" } module is_heap { header "__algorithm/is_heap.h" } module is_heap_until { header "__algorithm/is_heap_until.h" } - module is_partitioned { header "__algorithm/is_partitioned.h" } + module is_partitioned { + header "__algorithm/is_partitioned.h" + export __function_like + } module is_permutation { header "__algorithm/is_permutation.h" } module is_sorted { header "__algorithm/is_sorted.h" } module is_sorted_until { header "__algorithm/is_sorted_until.h" } @@ -292,7 +295,10 @@ module partial_sort_copy { header "__algorithm/partial_sort_copy.h" } module partition { header "__algorithm/partition.h" } module partition_copy { header "__algorithm/partition_copy.h" } - module partition_point { header "__algorithm/partition_point.h" } + module partition_point { + header "__algorithm/partition_point.h" + export __function_like + } module pop_heap { header "__algorithm/pop_heap.h" } module prev_permutation { header "__algorithm/prev_permutation.h" } module push_heap { header "__algorithm/push_heap.h" } diff --git a/libcxx/test/libcxx/diagnostics/nodiscard_ranges_extensions.pass.cpp b/libcxx/test/libcxx/diagnostics/nodiscard_ranges_extensions.pass.cpp --- a/libcxx/test/libcxx/diagnostics/nodiscard_ranges_extensions.pass.cpp +++ b/libcxx/test/libcxx/diagnostics/nodiscard_ranges_extensions.pass.cpp @@ -48,5 +48,11 @@ ranges::find_if_not(ranges::begin(arr), ranges::end(arr), [](auto) { return true; }); ranges::find_if_not(arr, [](auto) { return true; }); + ranges::is_partitioned(ranges::begin(arr), ranges::end(arr), [](auto) { return true; }); + ranges::is_partitioned(arr, [](auto) { return true; }); + + ranges::partition_point(ranges::begin(arr), ranges::end(arr), [](auto) { return true; }); + ranges::partition_point(arr, [](auto) { return true; }); + return 0; } diff --git a/libcxx/test/libcxx/diagnostics/nodiscard_ranges_extensions.verify.cpp b/libcxx/test/libcxx/diagnostics/nodiscard_ranges_extensions.verify.cpp --- a/libcxx/test/libcxx/diagnostics/nodiscard_ranges_extensions.verify.cpp +++ b/libcxx/test/libcxx/diagnostics/nodiscard_ranges_extensions.verify.cpp @@ -65,4 +65,16 @@ // expected-warning-re@+1 {{ignoring return value of function declared with {{'nodiscard'|warn_unused_result}} attribute}} ranges::find_if_not(arr, [](auto) { return true; }); + + // expected-warning-re@+1 {{ignoring return value of function declared with {{'nodiscard'|warn_unused_result}} attribute}} + ranges::is_partitioned(ranges::begin(arr), ranges::end(arr), [](auto) { return true; }); + + // expected-warning-re@+1 {{ignoring return value of function declared with {{'nodiscard'|warn_unused_result}} attribute}} + ranges::is_partitioned(arr, [](auto) { return true; }); + + // expected-warning-re@+1 {{ignoring return value of function declared with {{'nodiscard'|warn_unused_result}} attribute}} + ranges::partition_point(ranges::begin(arr), ranges::end(arr), [](auto) { return true; }); + + // expected-warning-re@+1 {{ignoring return value of function declared with {{'nodiscard'|warn_unused_result}} attribute}} + ranges::partition_point(arr, [](auto) { return true; }); } diff --git a/libcxx/test/std/algorithms/alg.modifying.operations/alg.partitions/ranges_is_partitioned/ranges_is_partitioned.pass.cpp b/libcxx/test/std/algorithms/alg.modifying.operations/alg.partitions/ranges_is_partitioned/ranges_is_partitioned.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/algorithms/alg.modifying.operations/alg.partitions/ranges_is_partitioned/ranges_is_partitioned.pass.cpp @@ -0,0 +1,237 @@ +//===----------------------------------------------------------------------===// +// +// 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: gcc-10 + +// + +// ranges::is_partition + +#include + +#include +#include +#include +#include + +#include "test_algorithm.h" +#include "test_iterators.h" +#include "test_macros.h" + +template class I, class T> +constexpr bool check_is_partitioned() { + namespace ranges = std::ranges; + + auto all_even = std::array{0, 2, 4, 6, 8}; + auto all_odd = std::array{1, 3, 5, 7, 9}; + auto odd_first = std::array{1, 3, 5, 7, 9, 0, 2, 4, 6, 8}; + auto even_first = std::array{0, 2, 4, 6, 8, 1, 3, 5, 7, 9}; + auto no_partition = std::array{1, 3, 5, 9, 0, 2, 4, 6, 7, 8}; + + auto is_odd = [](T const x) { return static_cast(x) % 2 != 0; }; + auto successor = [](T const x) { return x + 1; }; + + { + { + auto pred = complexity_invocable(is_odd); + auto range = ranges::subrange(I(all_odd.begin()), sentinel_wrapper(all_odd.end())); + assert(ranges::is_partitioned(range.begin(), range.end(), std::ref(pred))); + assert(pred.count() <= ranges::ssize(all_odd)); + } + { + auto pred = complexity_invocable(is_odd); + auto range = ranges::subrange(I(all_odd.begin()), sentinel_wrapper(all_odd.end())); + assert(ranges::is_partitioned(range, std::ref(pred))); + assert(pred.count() <= ranges::ssize(all_odd)); + } + } + { + { + auto pred = complexity_invocable(is_odd); + auto range = ranges::subrange(I(all_even.begin()), sentinel_wrapper(all_even.end())); + assert(ranges::is_partitioned(range.begin(), range.end(), std::ref(pred))); + assert(pred.count() <= ranges::ssize(all_even)); + } + { + auto pred = complexity_invocable(is_odd); + auto range = ranges::subrange(I(all_even.begin()), sentinel_wrapper(all_even.end())); + assert(ranges::is_partitioned(range, std::ref(pred))); + assert(pred.count() <= ranges::ssize(all_even)); + } + } + { + { + auto pred = complexity_invocable(is_odd); + auto range = ranges::subrange(I(odd_first.begin()), sentinel_wrapper(odd_first.end())); + assert(ranges::is_partitioned(range.begin(), range.end(), std::ref(pred))); + assert(pred.count() <= ranges::ssize(odd_first)); + } + { + auto pred = complexity_invocable(is_odd); + auto range = ranges::subrange(I(odd_first.begin()), sentinel_wrapper(odd_first.end())); + assert(ranges::is_partitioned(range, std::ref(pred))); + assert(pred.count() <= ranges::ssize(odd_first)); + } + } + { + { + auto pred = complexity_invocable(is_odd); + auto range = ranges::subrange(I(even_first.begin()), sentinel_wrapper(even_first.end())); + assert(!ranges::is_partitioned(range.begin(), range.end(), std::ref(pred))); + assert(pred.count() <= ranges::ssize(even_first)); + } + { + auto pred = complexity_invocable(is_odd); + auto range = ranges::subrange(I(even_first.begin()), sentinel_wrapper(even_first.end())); + assert(!ranges::is_partitioned(range, std::ref(pred))); + assert(pred.count() <= ranges::ssize(even_first)); + } + } + { + { + auto pred = complexity_invocable(is_odd); + auto range = ranges::subrange(I(no_partition.begin()), sentinel_wrapper(no_partition.end())); + assert(!ranges::is_partitioned(range.begin(), range.end(), std::ref(pred))); + assert(pred.count() <= ranges::ssize(no_partition)); + } + { + auto pred = complexity_invocable(is_odd); + auto range = ranges::subrange(I(no_partition.begin()), sentinel_wrapper(no_partition.end())); + assert(!ranges::is_partitioned(range, std::ref(pred))); + assert(pred.count() <= ranges::ssize(no_partition)); + } + } + { + { + auto pred = complexity_invocable(is_odd); + auto proj = complexity_invocable(successor); + auto range = ranges::subrange(I(all_odd.begin()), sentinel_wrapper(all_odd.end())); + assert(ranges::is_partitioned(range.begin(), range.end(), std::ref(pred), std::ref(proj))); + assert(pred.count() <= ranges::ssize(all_odd)); + assert(proj.count() == pred.count()); + } + { + auto pred = complexity_invocable(is_odd); + auto proj = complexity_invocable(successor); + auto range = ranges::subrange(I(all_odd.begin()), sentinel_wrapper(all_odd.end())); + assert(ranges::is_partitioned(range, std::ref(pred), std::ref(proj))); + assert(pred.count() <= ranges::ssize(all_odd)); + assert(proj.count() == pred.count()); + } + } + { + { + auto pred = complexity_invocable(is_odd); + auto proj = complexity_invocable(successor); + auto range = ranges::subrange(I(all_even.begin()), sentinel_wrapper(all_even.end())); + assert(ranges::is_partitioned(range.begin(), range.end(), std::ref(pred), std::ref(proj))); + assert(pred.count() <= ranges::ssize(all_even)); + assert(proj.count() == pred.count()); + } + { + auto pred = complexity_invocable(is_odd); + auto proj = complexity_invocable(successor); + auto range = ranges::subrange(I(all_even.begin()), sentinel_wrapper(all_even.end())); + assert(ranges::is_partitioned(range, std::ref(pred), std::ref(proj))); + assert(pred.count() <= ranges::ssize(all_even)); + assert(proj.count() == pred.count()); + } + } + { + { + auto pred = complexity_invocable(is_odd); + auto proj = complexity_invocable(successor); + auto range = ranges::subrange(I(odd_first.begin()), sentinel_wrapper(odd_first.end())); + assert(!ranges::is_partitioned(range.begin(), range.end(), std::ref(pred), std::ref(proj))); + assert(pred.count() <= ranges::ssize(odd_first)); + assert(proj.count() == pred.count()); + } + { + auto pred = complexity_invocable(is_odd); + auto proj = complexity_invocable(successor); + auto range = ranges::subrange(I(odd_first.begin()), sentinel_wrapper(odd_first.end())); + assert(!ranges::is_partitioned(range, std::ref(pred), std::ref(proj))); + assert(pred.count() <= ranges::ssize(odd_first)); + assert(proj.count() == pred.count()); + } + } + { + { + auto pred = complexity_invocable(is_odd); + auto proj = complexity_invocable(successor); + auto range = ranges::subrange(I(even_first.begin()), sentinel_wrapper(even_first.end())); + assert(ranges::is_partitioned(range.begin(), range.end(), std::ref(pred), std::ref(proj))); + assert(pred.count() <= ranges::ssize(even_first)); + assert(proj.count() == pred.count()); + } + { + auto pred = complexity_invocable(is_odd); + auto proj = complexity_invocable(successor); + auto range = ranges::subrange(I(even_first.begin()), sentinel_wrapper(even_first.end())); + assert(ranges::is_partitioned(range, std::ref(pred), std::ref(proj))); + assert(pred.count() <= ranges::ssize(even_first)); + assert(proj.count() == pred.count()); + } + } + { + { + auto pred = complexity_invocable(is_odd); + auto proj = complexity_invocable(successor); + auto range = ranges::subrange(I(no_partition.begin()), sentinel_wrapper(no_partition.end())); + assert(!ranges::is_partitioned(range.begin(), range.end(), std::ref(pred), std::ref(proj))); + assert(pred.count() <= ranges::ssize(no_partition)); + assert(proj.count() == pred.count()); + } + { + auto pred = complexity_invocable(is_odd); + auto proj = complexity_invocable(successor); + auto range = ranges::subrange(I(no_partition.begin()), sentinel_wrapper(no_partition.end())); + assert(!ranges::is_partitioned(range, std::ref(pred), std::ref(proj))); + assert(pred.count() <= ranges::ssize(no_partition)); + assert(proj.count() == pred.count()); + } + } + + return true; +} + +int main(int, char**) { + static_assert(check_is_partitioned()); + static_assert(check_is_partitioned()); + check_is_partitioned(); + check_is_partitioned(); + + static_assert(check_is_partitioned()); + static_assert(check_is_partitioned()); + check_is_partitioned(); + check_is_partitioned(); + + static_assert(check_is_partitioned()); + static_assert(check_is_partitioned()); + check_is_partitioned(); + check_is_partitioned(); + + static_assert(check_is_partitioned()); + static_assert(check_is_partitioned()); + check_is_partitioned(); + check_is_partitioned(); + + static_assert(check_is_partitioned()); + static_assert(check_is_partitioned()); + check_is_partitioned(); + check_is_partitioned(); + + static_assert(check_is_partitioned()); + static_assert(check_is_partitioned()); + check_is_partitioned(); + check_is_partitioned(); + + return 0; +} diff --git a/libcxx/test/std/algorithms/alg.modifying.operations/alg.partitions/ranges_is_partitioned/special_function.compile.pass.cpp b/libcxx/test/std/algorithms/alg.modifying.operations/alg.partitions/ranges_is_partitioned/special_function.compile.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/algorithms/alg.modifying.operations/alg.partitions/ranges_is_partitioned/special_function.compile.pass.cpp @@ -0,0 +1,111 @@ +//===----------------------------------------------------------------------===// +// +// 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: gcc-10 + +// ranges::is_partitioned + +#include + +#include +#include +#include +#include + +#include "test_range.h" +#include "test_standard_function.h" + +static_assert(is_function_like()); + +namespace ranges = std::ranges; + +namespace std::ranges { + template + class basic_istream_view { + struct iterator; + public: + iterator begin(); + default_sentinel_t end() const; + }; +} // namespace std::ranges + +auto f = [](auto) { return true; }; + +// The entities defined in the std::ranges namespace in this Clause are not found by argument-dependent +// name lookup ([basic.lookup.argdep]). When found by unqualified ([basic.lookup.unqual]) name lookup for +// the postfix-expression in a function call ([expr.call]), they inhibit argument-dependent name lookup. +template +constexpr bool no_unqualified_lookup() { + auto identity = ranges::basic_istream_view(); + static_assert(!requires { is_partitioned(ranges::begin(identity), ranges::end(identity), f); }); + static_assert(!requires { is_partitioned(ranges::begin(identity), ranges::end(identity), f, &T::first); }); + static_assert(!requires { is_partitioned(identity, f); }); + static_assert(!requires { is_partitioned(identity, f, &T::first); }); + return true; +}; + +static_assert(no_unqualified_lookup>()); + +namespace test { +template +struct iterator { + using value_type = std::pair; + using difference_type = std::ptrdiff_t; + using iterator_category = std::forward_iterator_tag; + + iterator() = default; + + value_type operator*() const; + iterator& operator++(); + iterator operator++(int); + + bool operator==(iterator const&) const = default; +}; + +template +struct range { + std::pair const* begin() const; + std::pair const* end() const; +}; + +template +void is_partitioned(iterator, iterator, auto) { + static_assert(std::same_as); +} + +template +void is_partitioned(iterator, iterator, auto, auto) { + static_assert(std::same_as); +} + +template +void is_partitioned(R&&, auto) { + static_assert(std::same_as); +} + +template +void is_partitioned(R&&, auto, auto) { + static_assert(std::same_as); +} +} // namespace test + +// When found by unqualified ([basic.lookup.unqual]) name lookup for the postfix-expression in a +// function call ([expr.call]), they inhibit argument-dependent name lookup. +void adl_inhibition() { + using std::ranges::is_partitioned; + + test::iterator*> x; + (void)is_partitioned(x, x, f); + (void)is_partitioned(x, x, f, &std::pair::first); + + test::range r; + (void)is_partitioned(r, f); + (void)is_partitioned(r, f, &std::pair::first); +} diff --git a/libcxx/test/std/algorithms/alg.modifying.operations/alg.partitions/ranges_partition_point/ranges_partition_point.pass.cpp b/libcxx/test/std/algorithms/alg.modifying.operations/alg.partitions/ranges_partition_point/ranges_partition_point.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/algorithms/alg.modifying.operations/alg.partitions/ranges_partition_point/ranges_partition_point.pass.cpp @@ -0,0 +1,158 @@ +//===----------------------------------------------------------------------===// +// +// 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: gcc-10 + +// ranges::partition_point + +#include + +#include +#include +#include +#include +#include + +#include "test_algorithm.h" +#include "test_iterators.h" +#include "test_macros.h" + +template class I, class T> +constexpr bool check_partition_point() { + namespace ranges = std::ranges; + + auto all_odd = std::array{1, 3, 5, 7, 9}; + auto all_even = std::array{0, 2, 4, 6, 8}; + auto odd_first = std::array{1, 3, 5, 7, 9, 0, 2, 4, 6, 8}; + auto even_first = std::array{0, 2, 4, 6, 8, 1, 3, 5, 7, 9}; + + auto is_odd = [](T const x) { return static_cast(x) % 2 != 0; }; + auto successor = [](T const x) { return x + 1; }; + + { + auto const range = ranges::subrange(I(all_odd.begin()), sentinel_wrapper(all_odd.end())); + { + auto pred = complexity_invocable(is_odd); + assert(ranges::partition_point(range.begin(), range.end(), std::ref(pred)) == range.end()); + assert(pred.count() == 2); + } + { + auto pred = complexity_invocable(is_odd); + assert(ranges::partition_point(range, std::ref(pred)) == range.end()); + assert(pred.count() == 2); + } + { + auto pred = complexity_invocable(is_odd); + auto proj = complexity_invocable(successor); + assert(ranges::partition_point(range.begin(), range.end(), std::ref(pred), std::ref(proj)) == range.begin()); + assert(pred.count() == 3); + assert(proj.count() == 3); + } + { + auto pred = complexity_invocable(is_odd); + auto proj = complexity_invocable(successor); + assert(ranges::partition_point(range, std::ref(pred), std::ref(proj)) == range.begin()); + assert(pred.count() == 3); + assert(proj.count() == 3); + } + } + { + auto const range = ranges::subrange(I(all_even.begin()), sentinel_wrapper(all_even.end())); + + { + auto pred = complexity_invocable(is_odd); + assert(ranges::partition_point(range.begin(), range.end(), std::ref(pred)) == range.begin()); + assert(pred.count() == 3); + } + { + auto pred = complexity_invocable(is_odd); + assert(ranges::partition_point(range, std::ref(pred)) == range.begin()); + assert(pred.count() == 3); + } + { + auto pred = complexity_invocable(is_odd); + auto proj = complexity_invocable(successor); + assert(ranges::partition_point(range.begin(), range.end(), std::ref(pred), std::ref(proj)) == range.end()); + assert(pred.count() == 2); + assert(proj.count() == 2); + } + { + auto pred = complexity_invocable(is_odd); + auto proj = complexity_invocable(successor); + assert(ranges::partition_point(range, std::ref(pred), std::ref(proj)) == range.end()); + assert(pred.count() == 2); + assert(proj.count() == 2); + } + } + { + auto const range = ranges::subrange(I(odd_first.begin()), sentinel_wrapper(odd_first.end())); + + { + auto pred = complexity_invocable(is_odd); + assert(ranges::partition_point(range.begin(), range.end(), std::ref(pred)).base() == odd_first.begin() + 5); + assert(pred.count() == 3); + } + { + auto pred = complexity_invocable(is_odd); + assert(ranges::partition_point(range, std::ref(pred)).base() == odd_first.begin() + 5); + assert(pred.count() == 3); + } + } + { + auto const range = ranges::subrange(I(even_first.begin()), sentinel_wrapper(even_first.end())); + + { + auto pred = complexity_invocable(is_odd); + auto proj = complexity_invocable(successor); + assert(ranges::partition_point(range.begin(), range.end(), std::ref(pred), std::ref(proj)).base() == even_first.begin() + 5); + assert(pred.count() == 3); + assert(proj.count() == 3); + } + { + auto pred = complexity_invocable(is_odd); + auto proj = complexity_invocable(successor); + assert(ranges::partition_point(range, std::ref(pred), std::ref(proj)).base() == even_first.begin() + 5); + assert(pred.count() == 3); + assert(proj.count() == 3); + } + } + { + ASSERT_SAME_TYPE(decltype(ranges::partition_point(std::vector(all_odd.begin(), all_odd.end()), is_odd)), + ranges::dangling); + ASSERT_SAME_TYPE(decltype(ranges::partition_point(std::vector(all_odd.begin(), all_odd.end()), is_odd, successor)), + ranges::dangling); + } + + return true; +} + +int main(int, char**) { + static_assert(check_partition_point()); + static_assert(check_partition_point()); + check_partition_point(); + check_partition_point(); + + static_assert(check_partition_point()); + static_assert(check_partition_point()); + check_partition_point(); + check_partition_point(); + + static_assert(check_partition_point()); + static_assert(check_partition_point()); + check_partition_point(); + check_partition_point(); + + static_assert(check_partition_point()); + static_assert(check_partition_point()); + check_partition_point(); + check_partition_point(); + + return 0; +} diff --git a/libcxx/test/std/algorithms/alg.modifying.operations/alg.partitions/ranges_partition_point/special_function.compile.pass.cpp b/libcxx/test/std/algorithms/alg.modifying.operations/alg.partitions/ranges_partition_point/special_function.compile.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/algorithms/alg.modifying.operations/alg.partitions/ranges_partition_point/special_function.compile.pass.cpp @@ -0,0 +1,111 @@ +//===----------------------------------------------------------------------===// +// +// 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: gcc-10 + +// ranges::partition_point + +#include + +#include +#include +#include +#include + +#include "test_range.h" +#include "test_standard_function.h" + +static_assert(is_function_like()); + +namespace ranges = std::ranges; + +namespace std::ranges { + template + class basic_istream_view { + struct iterator; + public: + iterator begin(); + default_sentinel_t end() const; + }; +} // namespace std::ranges + +auto f = [](auto) { return true; }; + +// The entities defined in the std::ranges namespace in this Clause are not found by argument-dependent +// name lookup ([basic.lookup.argdep]). When found by unqualified ([basic.lookup.unqual]) name lookup for +// the postfix-expression in a function call ([expr.call]), they inhibit argument-dependent name lookup. +template +constexpr bool no_unqualified_lookup() { + auto identity = ranges::basic_istream_view(); + static_assert(!requires { partition_point(ranges::begin(identity), ranges::end(identity), f); }); + static_assert(!requires { partition_point(ranges::begin(identity), ranges::end(identity), f, &T::first); }); + static_assert(!requires { partition_point(identity, f); }); + static_assert(!requires { partition_point(identity, f, &T::first); }); + return true; +}; + +static_assert(no_unqualified_lookup>()); + +namespace test { +template +struct iterator { + using value_type = std::pair; + using difference_type = std::ptrdiff_t; + using iterator_category = std::forward_iterator_tag; + + iterator() = default; + + value_type operator*() const; + iterator& operator++(); + iterator operator++(int); + + bool operator==(iterator const&) const = default; +}; + +template +struct range { + std::pair const* begin() const; + std::pair const* end() const; +}; + +template +void partition_point(iterator, iterator, auto) { + static_assert(std::same_as); +} + +template +void partition_point(iterator, iterator, auto, auto) { + static_assert(std::same_as); +} + +template +void partition_point(R&&, auto) { + static_assert(std::same_as); +} + +template +void partition_point(R&&, auto, auto) { + static_assert(std::same_as); +} +} // namespace test + +// When found by unqualified ([basic.lookup.unqual]) name lookup for the postfix-expression in a +// function call ([expr.call]), they inhibit argument-dependent name lookup. +void adl_inhibition() { + using std::ranges::partition_point; + + test::iterator*> x; + (void)partition_point(x, x, f); + (void)partition_point(x, x, f, &std::pair::first); + + test::range r; + (void)partition_point(r, f); + (void)partition_point(r, f, &std::pair::first); +}