[libc++][ranges] Implement `std::ranges::partition_{point,copy}`.

[var-const]

Use the actual patch number.

[var-const]

libcxx/include/__algorithm/ranges_partition_copy.h

43

These two algorithms seem borderline when choosing whether to delegate or reimplement. I'm quite open to delegate if you feel it would be beneficial.

libcxx/test/std/algorithms/alg.modifying.operations/alg.partitions/ranges_partition_copy.pass.cpp

200

I am concerned about the combinatorial explosion here. Perhaps it is sufficient to test with just the weakest and the "strongest" iterator types that satisfy the necessary constraints?

(Note that I think partition_copy is the only algorithm to have two different output iterator types)

[var-const]

Fix the CI.

[huixie90]

libcxx/test/std/algorithms/alg.modifying.operations/alg.partitions/ranges_partition_copy.pass.cpp

299

perhaps also tests "Complexity: Exactly last - first applications of pred and proj."

libcxx/test/std/algorithms/alg.modifying.operations/alg.partitions/ranges_partition_point.pass.cpp

170

can we have at least one test where the comparator is not is_odd?

[ldionne]

Leaving final approval to @huixie90

libcxx/include/__algorithm/ranges_partition_copy.h

43

I would have a preference for delegating. I'm also fine with a TODO to do it after the release, since you have it implemented right now and it works (according to the tests).

libcxx/test/std/algorithms/alg.modifying.operations/alg.partitions/ranges_partition_copy.pass.cpp

200

Yes, I think it's OK to test only the weakest and the strongest iterator types, with a comment.

209–211

Note that I would remove those and replace them by an explanation, otherwise it looks like you simply forgot to uncomment before committing.

[var-const]

Address feedback, rebase on main.

libcxx/include/__algorithm/ranges_partition_copy.h

43

Thanks! Added a TODO.

libcxx/test/std/algorithms/alg.modifying.operations/alg.partitions/ranges_partition_copy.pass.cpp

299

I want to consolidate these checks as well, but realistically won't have time before the branch cut. Added the test.

libcxx/test/std/algorithms/alg.modifying.operations/alg.partitions/ranges_partition_point.pass.cpp

170

Done (also in partition and stable_partition).

[var-const]

Quick fix

[var-const]

Rebase on main.

[var-const]

Rebase on main, fix new test.

[var-const]

Fix the CI.

[var-const]

Fix the CI and rebase on main.

[var-const]

Rebase on main.

[huixie90]

LGTM with nits

libcxx/include/__algorithm/ranges_partition_copy.h

44

nit:
_InIter can be a reference type if we don't do std::move on the caller. Since this is a local static function, it is unlikely to be used elsewhere. so it is ok to leave it as it is. If this were an __ function, I would either uncvref them, or pass them by value to make sure we have a partition_copy_result of value types

libcxx/test/std/algorithms/alg.modifying.operations/alg.partitions/ranges_partition_copy.pass.cpp

133–134

nit: It is OK to allocate N2 and N3 I think. In case the algorithm goes wrong and cause buffer overflow, the constexpr test would fail. It also simplifies the verification to just ranges::all_of(out1, pred)

143–144

can we also verify ranges::equal(out1, expected_true) and ranges::equal(out2, expected_false)
otherwise the test would still pass if the algorithm simply repeatedly copies the first element in the group

[var-const]

Address feedback.

libcxx/test/std/algorithms/alg.modifying.operations/alg.partitions/ranges_partition_copy.pass.cpp

133–134

Very good point re. constexpr. I dropped the checks for all_of altogether in favor of just comparing to expected_* explicitly.

143–144

Thanks for spotting this, this is an oversight on my part.

libcxx/docs/Status/RangesAlgorithms.csv

 Category,Algorithm,Assignee,CL,Complete
 Search,any_of,Nikolas Klauser,`D123016 <https://llvm.org/D123016>`_,✅
 Search,all_of,Nikolas Klauser,`D123016 <https://llvm.org/D123016>`_,✅
 Search,none_of,Nikolas Klauser,`D123016 <https://llvm.org/D123016>`_,✅
 Search,find,Nikolas Klauser,`D121248 <https://llvm.org/D121248>`_,✅
 Search,find_if,Nikolas Klauser,`D121248 <https://llvm.org/D121248>`_,✅
 Search,find_if_not,Nikolas Klauser,`D121248 <https://llvm.org/D121248>`_,✅
 Search,find_first_of,Nikolas Klauser,`D126529 <https://llvm.org/D126529>`_,✅
 Search,adjacent_find,Nikolas Klauser,`D126610 <https://llvm.org/D126610>`_,✅
 Search,mismatch,Nikolas Klauser,`D117817 <https://llvm.org/D117817>`_,✅
 Search,equal,Nikolas Klauser,`D123681 <https://llvm.org/D123681>`_,✅
 Search,lexicographical_compare,Nikolas Klauser,`D127130 <https://llvm.org/D127130>`_,✅
-Search,partition_point,Konstantin Varlamov,n/a,In progress
+Search,partition_point,Konstantin Varlamov,`D130070 <https://llvm.org/D130070>`_,✅
 Search,lower_bound,Nikolas Klauser,`D121964 <https://llvm.org/D121964>`_,✅
 Search,upper_bound,Nikolas Klauser,`D121964 <https://llvm.org/D121964>`_,✅
 Search,equal_range,Christopher Di Bella,n/a,Not started
 Search,binary_search,Nikolas Klauser,`D121964 <https://llvm.org/D121964>`_,✅
 Search,min,Nikolas Klauser,`D119589 <https://llvm.org/D119589>`_,✅
 Search,max,Nikolas Klauser,`D122002 <https://llvm.org/D122002>`_,✅
 Search,minmax,Nikolas Klauser,`D120637 <https://llvm.org/D120637>`_,✅
 Search,min_element,Nikolas Klauser,`D117025 <https://llvm.org/D117025>`_,✅

 Write,replace_if,Nikolas Klauser,`D126283 <https://llvm.org/D126283>`_,✅
 Write,replace_copy,Nikolas Klauser,`D129806 <https://llvm.org/D129806>`_,Under review
 Write,replace_copy_if,Nikolas Klauser,`D129806 <https://llvm.org/D129806>`_,Under review
 Write,swap_ranges,Nikolas Klauser,`D116303 <https://llvm.org/D116303>`_,✅
 Write,reverse_copy,Nikolas Klauser,`D127211 <https://llvm.org/D127211>`_,✅
 Write,rotate_copy,Nikolas Klauser,`D127211 <https://llvm.org/D127211>`_,✅
 Write,sample,Not assigned,n/a,Not started
 Write,unique_copy,Not assigned,n/a,Not started
-Write,partition_copy,Konstantin Varlamov,n/a,In progress
+Write,partition_copy,Konstantin Varlamov,`D130070 <https://llvm.org/D130070>`_,✅
 Write,partial_sort_copy,Not assigned,n/a,Not started
 Merge,merge,Hui Xie,`D128611 <https://llvm.org/D128611>`_,✅
 Merge,set_difference,Hui Xie,`D128983 <https://llvm.org/D128983>`_,✅
 Merge,set_intersection,Hui Xie,`D129233 <https://llvm.org/D129233>`_,✅
 Merge,set_symmetric_difference,Hui Xie,`D129520 <https://llvm.org/D129520>`_,✅
 Merge,set_union,Hui Xie,`D129657 <https://llvm.org/D129657>`_,✅
 Permutation,remove,Nikolas Klauser,`D128618 <https://llvm.org/D128618>`_,✅
 Permutation,remove_if,Nikolas Klauser,`D128618 <https://llvm.org/D128618>`_,✅

libcxx/include/__algorithm/ranges_partition_copy.h

 //===----------------------------------------------------------------------===//
 //
 // 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_PARTITION_COPY_H
 #define _LIBCPP___ALGORITHM_RANGES_PARTITION_COPY_H
 
 #include <__algorithm/in_out_out_result.h>
-#include <__algorithm/make_projected.h>
-#include <__algorithm/partition_copy.h>
 #include <__config>
 #include <__functional/identity.h>
 #include <__functional/invoke.h>
-#include <__functional/ranges_operations.h>
 #include <__iterator/concepts.h>
 #include <__iterator/iterator_traits.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 _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
 namespace ranges {
 
 template <class _InIter, class _OutIter1, class _OutIter2>
 using partition_copy_result = in_out_out_result<_InIter, _OutIter1, _OutIter2>;
 
 namespace __partition_copy {
 
 struct __fn {
 
+  // TODO(ranges): delegate to the classic algorithm.
+  template <class _InIter, class _Sent, class _OutIter1, class _OutIter2, class _Proj, class _Pred>
+  _LIBCPP_HIDE_FROM_ABI constexpr
+  static partition_copy_result<_InIter, _OutIter1, _OutIter2> __partition_copy_fn_impl(
+      _InIter&& __first, _Sent&& __last, _OutIter1&& __out_true, _OutIter2&& __out_false,
+      _Pred& __pred, _Proj& __proj) {
+    for (; __first != __last; ++__first) {
+      if (std::invoke(__pred, std::invoke(__proj, *__first))) {
+        *__out_true = *__first;
+        ++__out_true;
+
+      } else {
+        *__out_false = *__first;
+        ++__out_false;
+      }
+    }
+
+    return {std::move(__first), std::move(__out_true), std::move(__out_false)};
+  }
+
   template <input_iterator _InIter, sentinel_for<_InIter> _Sent,
             weakly_incrementable _OutIter1, weakly_incrementable _OutIter2,
             class _Proj = identity, indirect_unary_predicate<projected<_InIter, _Proj>> _Pred>
   requires indirectly_copyable<_InIter, _OutIter1> && indirectly_copyable<_InIter, _OutIter2>
   _LIBCPP_HIDE_FROM_ABI constexpr
   partition_copy_result<_InIter, _OutIter1, _OutIter2>
   operator()(_InIter __first, _Sent __last, _OutIter1 __out_true, _OutIter2 __out_false,
              _Pred __pred, _Proj __proj = {}) const {
-    // TODO: implement
-    (void)__first; (void)__last; (void)__out_true; (void)__out_false; (void)__pred; (void)__proj;
-    return {};
+    return __partition_copy_fn_impl(
+        std::move(__first), std::move(__last), std::move(__out_true), std::move(__out_false), __pred, __proj);
   }
 
   template <input_range _Range, weakly_incrementable _OutIter1, weakly_incrementable _OutIter2,
             class _Proj = identity, indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> _Pred>
   requires indirectly_copyable<iterator_t<_Range>, _OutIter1> && indirectly_copyable<iterator_t<_Range>, _OutIter2>
   _LIBCPP_HIDE_FROM_ABI constexpr
   partition_copy_result<borrowed_iterator_t<_Range>, _OutIter1, _OutIter2>
   operator()(_Range&& __range, _OutIter1 __out_true, _OutIter2 __out_false, _Pred __pred, _Proj __proj = {}) const {
-    // TODO: implement
-    (void)__range; (void)__out_true; (void)__out_false; (void)__pred; (void)__proj;
-    return {};
+    return __partition_copy_fn_impl(
+        ranges::begin(__range), ranges::end(__range), std::move(__out_true), std::move(__out_false), __pred, __proj);
   }
 
 };
 
 } // namespace __partition_copy
 
 inline namespace __cpo {
   inline constexpr auto partition_copy = __partition_copy::__fn{};
 } // namespace __cpo
 } // namespace ranges
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
 
 #endif // _LIBCPP___ALGORITHM_RANGES_PARTITION_COPY_H

libcxx/include/__algorithm/ranges_partition_point.h

 //===----------------------------------------------------------------------===//
 //
 // 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_PARTITION_POINT_H
 #define _LIBCPP___ALGORITHM_RANGES_PARTITION_POINT_H
 
-#include <__algorithm/make_projected.h>
-#include <__algorithm/partition_point.h>
+#include <__algorithm/half_positive.h>
 #include <__config>
 #include <__functional/identity.h>
 #include <__functional/invoke.h>
-#include <__functional/ranges_operations.h>
 #include <__iterator/concepts.h>
+#include <__iterator/distance.h>
 #include <__iterator/iterator_traits.h>
+#include <__iterator/next.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 _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
 namespace ranges {
 namespace __partition_point {
 
 struct __fn {
 
+  // TODO(ranges): delegate to the classic algorithm.
+  template <class _Iter, class _Sent, class _Proj, class _Pred>
+  _LIBCPP_HIDE_FROM_ABI constexpr
+  static _Iter __partition_point_fn_impl(_Iter&& __first, _Sent&& __last, _Pred& __pred, _Proj& __proj) {
+    auto __len = ranges::distance(__first, __last);
+
+    while (__len != 0) {
+      auto __half_len = std::__half_positive(__len);
+      auto __mid = ranges::next(__first, __half_len);
+
+      if (std::invoke(__pred, std::invoke(__proj, *__mid))) {
+        __first = ++__mid;
+        __len -= __half_len + 1;
+
+      } else {
+        __len = __half_len;
+      }
+    }
+
+    return __first;
+  }
+
   template <forward_iterator _Iter, sentinel_for<_Iter> _Sent, class _Proj = identity,
             indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
   _LIBCPP_HIDE_FROM_ABI constexpr
   _Iter operator()(_Iter __first, _Sent __last, _Pred __pred, _Proj __proj = {}) const {
-    // TODO: implement
-    (void)__first; (void)__last; (void)__pred; (void)__proj;
-    return {};
+    return __partition_point_fn_impl(std::move(__first), std::move(__last), __pred, __proj);
   }
 
   template <forward_range _Range, class _Proj = identity,
             indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> _Pred>
   _LIBCPP_HIDE_FROM_ABI constexpr
   borrowed_iterator_t<_Range> operator()(_Range&& __range, _Pred __pred, _Proj __proj = {}) const {
-    // TODO: implement
-    (void)__range; (void)__pred; (void)__proj;
-    return {};
+    return __partition_point_fn_impl(ranges::begin(__range), ranges::end(__range), __pred, __proj);
   }
 
 };
 
 } // namespace __partition_point
 
 inline namespace __cpo {
   inline constexpr auto partition_point = __partition_point::__fn{};
 } // namespace __cpo
 } // namespace ranges
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
 
 #endif // _LIBCPP___ALGORITHM_RANGES_PARTITION_POINT_H

libcxx/include/algorithm

template<input_iterator I, sentinel_for<I> S, weakly_incrementable O>
     constexpr ranges::move_result<I, O>
       ranges::move(I first, S last, O result);                                                      // since C++20
 
   template<input_range R, weakly_incrementable O>
     requires indirectly_movable<iterator_t<R>, O>
     constexpr ranges::move_result<borrowed_iterator_t<R>, O>
       ranges::move(R&& r, O result);                                                                // since C++20
 
+  template<class I, class O1, class O2>
+      using partition_copy_result = in_out_out_result<I, O1, O2>;                                   // since C++20
+
+  template<input_iterator I, sentinel_for<I> S,
+          weakly_incrementable O1, weakly_incrementable O2,
+          class Proj = identity, indirect_unary_predicate<projected<I, Proj>> Pred>
+    requires indirectly_copyable<I, O1> && indirectly_copyable<I, O2>
+    constexpr partition_copy_result<I, O1, O2>
+      partition_copy(I first, S last, O1 out_true, O2 out_false, Pred pred,
+                    Proj proj = {});                                                                // Since C++20
+
+  template<input_range R, weakly_incrementable O1, weakly_incrementable O2,
+          class Proj = identity,
+          indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
+    requires indirectly_copyable<iterator_t<R>, O1> &&
+            indirectly_copyable<iterator_t<R>, O2>
+    constexpr partition_copy_result<borrowed_iterator_t<R>, O1, O2>
+      partition_copy(R&& r, O1 out_true, O2 out_false, Pred pred, Proj proj = {});                  // Since C++20
+
+  template<forward_iterator I, sentinel_for<I> S, class Proj = identity,
+           indirect_unary_predicate<projected<I, Proj>> Pred>
+    constexpr I partition_point(I first, S last, Pred pred, Proj proj = {});                        // Since C++20
+
+  template<forward_range R, class Proj = identity,
+           indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
+    constexpr borrowed_iterator_t<R>
+      partition_point(R&& r, Pred pred, Proj proj = {});                                            // Since C++20
+
   template<class I1, class I2, class O>
     using merge_result = in_in_out_result<I1, I2, O>;                                               // since C++20
 
   template<input_iterator I1, sentinel_for<I1> S1, input_iterator I2, sentinel_for<I2> S2,
            weakly_incrementable O, class Comp = ranges::less, class Proj1 = identity,
            class Proj2 = identity>
     requires mergeable<I1, I2, O, Comp, Proj1, Proj2>
     constexpr merge_result<I1, I2, O>

 #include <__algorithm/ranges_minmax.h>
 #include <__algorithm/ranges_minmax_element.h>
 #include <__algorithm/ranges_mismatch.h>
 #include <__algorithm/ranges_move.h>
 #include <__algorithm/ranges_move_backward.h>
 #include <__algorithm/ranges_none_of.h>
 #include <__algorithm/ranges_nth_element.h>
 #include <__algorithm/ranges_partition.h>
+#include <__algorithm/ranges_partition_copy.h>
+#include <__algorithm/ranges_partition_point.h>
 #include <__algorithm/ranges_pop_heap.h>
 #include <__algorithm/ranges_push_heap.h>
 #include <__algorithm/ranges_remove.h>
 #include <__algorithm/ranges_remove_if.h>
 #include <__algorithm/ranges_replace.h>
 #include <__algorithm/ranges_replace_if.h>
 #include <__algorithm/ranges_reverse.h>
 #include <__algorithm/ranges_reverse_copy.h>

libcxx/test/libcxx/algorithms/ranges_robust_against_copying_comparators.pass.cpp

#endif
     (void)std::ranges::nth_element(first, mid, last, Less(&copies)); assert(copies == 0);
     (void)std::ranges::nth_element(a, mid, Less(&copies)); assert(copies == 0);
     //(void)std::ranges::partial_sort(first, mid, last, Less(&copies)); assert(copies == 0);
     //(void)std::ranges::partial_sort(a, mid, Less(&copies)); assert(copies == 0);
     //(void)std::ranges::partial_sort_copy(first, last, first2, mid2, Less(&copies)); assert(copies == 0);
     //(void)std::ranges::partial_sort_copy(a, b, Less(&copies)); assert(copies == 0);
     (void)std::ranges::partition(first, last, UnaryTrue(&copies)); assert(copies == 0);
     (void)std::ranges::partition(a, UnaryTrue(&copies)); assert(copies == 0);
-    //(void)std::ranges::partition_copy(first, last, first2, last2, UnaryTrue(&copies)); assert(copies == 0);
-    //(void)std::ranges::partition_copy(a, first2, last2, UnaryTrue(&copies)); assert(copies == 0);
-    //(void)std::ranges::partition_point(first, last, UnaryTrue(&copies)); assert(copies == 0);
-    //(void)std::ranges::partition_point(a, UnaryTrue(&copies)); assert(copies == 0);
+    (void)std::ranges::partition_copy(first, last, first2, last2, UnaryTrue(&copies)); assert(copies == 0);
+    (void)std::ranges::partition_copy(a, first2, last2, UnaryTrue(&copies)); assert(copies == 0);
+    (void)std::ranges::partition_point(first, last, UnaryTrue(&copies)); assert(copies == 0);
+    (void)std::ranges::partition_point(a, UnaryTrue(&copies)); assert(copies == 0);
     (void)std::ranges::pop_heap(first, last, Less(&copies)); assert(copies == 0);
     (void)std::ranges::pop_heap(a, Less(&copies)); assert(copies == 0);
     //(void)std::ranges::prev_permutation(first, last, Less(&copies)); assert(copies == 0);
     //(void)std::ranges::prev_permutation(a, Less(&copies)); assert(copies == 0);
     (void)std::ranges::push_heap(first, last, Less(&copies)); assert(copies == 0);
     (void)std::ranges::push_heap(a, Less(&copies)); assert(copies == 0);
     //(void)std::ranges::remove_copy_if(first, last, first2, UnaryTrue(&copies)); assert(copies == 0);
     //(void)std::ranges::remove_copy_if(a, first2, UnaryTrue(&copies)); assert(copies == 0);

libcxx/test/libcxx/algorithms/ranges_robust_against_copying_projections.pass.cpp

#endif
     (void)std::ranges::nth_element(first, mid, last, Less(), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::nth_element(a, mid, Less(), Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::partial_sort(first, mid, last, Less(), Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::partial_sort(a, mid, Less(), Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::partial_sort_copy(first, last, first2, mid2, Less(), Proj(&copies), Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::partial_sort_copy(a, b, Less(), Proj(&copies), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::partition(first, last, UnaryTrue(), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::partition(a, UnaryTrue(), Proj(&copies)); assert(copies == 0);
-    //(void)std::ranges::partition_copy(first, last, first2, last2, UnaryTrue(), Proj(&copies)); assert(copies == 0);
-    //(void)std::ranges::partition_copy(a, first2, last2, UnaryTrue(), Proj(&copies)); assert(copies == 0);
-    //(void)std::ranges::partition_point(first, last, UnaryTrue(), Proj(&copies)); assert(copies == 0);
-    //(void)std::ranges::partition_point(a, UnaryTrue(), Proj(&copies)); assert(copies == 0);
+    (void)std::ranges::partition_copy(first, last, first2, last2, UnaryTrue(), Proj(&copies)); assert(copies == 0);
+    (void)std::ranges::partition_copy(a, first2, last2, UnaryTrue(), Proj(&copies)); assert(copies == 0);
+    (void)std::ranges::partition_point(first, last, UnaryTrue(), Proj(&copies)); assert(copies == 0);
+    (void)std::ranges::partition_point(a, UnaryTrue(), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::pop_heap(first, last, Less(), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::pop_heap(a, Less(), Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::prev_permutation(first, last, Less(), Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::prev_permutation(a, Less(), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::push_heap(first, last, Less(), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::push_heap(a, Less(), Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::remove_copy(first, last, first2, value, Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::remove_copy(a, first2, value, Proj(&copies)); assert(copies == 0);

libcxx/test/std/algorithms/alg.modifying.operations/alg.partitions/ranges_partition.pass.cpp

 
 template <class T>
 using R = UncheckedRange<T>;
 
 static_assert(HasPartitionRange<R<int*>, UnaryPred>);
 
 // !forward_range<R>
 static_assert(!HasPartitionRange<ForwardRangeNotDerivedFrom, UnaryPred>);
-static_assert(!HasPartitionRange<ForwardIteratorNotIncrementable, UnaryPred>);
+static_assert(!HasPartitionRange<ForwardRangeNotIncrementable, UnaryPred>);
 
 // !indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
 static_assert(!HasPartitionRange<R<int*>, IndirectUnaryPredicateNotPredicate>);
 static_assert(!HasPartitionRange<R<int*>, IndirectUnaryPredicateNotCopyConstructible>);
 
 // !permutable<iterator_t<R>>
 static_assert(!HasPartitionRange<R<PermutableNotForwardIterator>, UnaryPred>);
 static_assert(!HasPartitionRange<R<PermutableNotSwappable>, UnaryPred>);
constexpr void test_iterators_2() {
   // All elements are the same and don't satisfy the predicate.
   test_one<Iter, Sent, 3>({2, 2, 2}, is_odd, 0);
   // Already partitioned.
   test_one<Iter, Sent, 6>({1, 3, 5, 4, 6, 8}, is_odd, 3);
   // Reverse-partitioned.
   test_one<Iter, Sent, 6>({4, 6, 8, 1, 3, 5}, is_odd, 3);
   // Repeating pattern.
   test_one<Iter, Sent, 6>({1, 2, 1, 2, 1, 2}, is_odd, 3);
+
+  auto is_negative = [](int x) { return x < 0; };
+  // Different comparator.
+  test_one<Iter, Sent, 5>({-3, 5, 7, -6, 2}, is_negative, 2);
 }
 
 template <class Iter>
 constexpr void test_iterators_1() {
   test_iterators_2<Iter, Iter>();
   test_iterators_2<Iter, sentinel_wrapper<Iter>>();
 }
 

libcxx/test/std/algorithms/alg.modifying.operations/alg.partitions/ranges_partition_copy.pass.cpp

 //   constexpr partition_copy_result<borrowed_iterator_t<R>, O1, O2>
 //     partition_copy(R&& r, O1 out_true, O2 out_false, Pred pred, Proj proj = {});                 // Since C++20
 
 #include <algorithm>
 #include <array>
 #include <concepts>
 #include <functional>
 #include <ranges>
+#include <utility>
 
 #include "almost_satisfies_types.h"
+#include "counting_predicates.h"
+#include "counting_projection.h"
 #include "test_iterators.h"
 
-// TODO: SFINAE tests.
+struct UnaryPred { bool operator()(int) const; };
+
+// Test constraints of the (iterator, sentinel) overload.
+// ======================================================
+
+template <class InIter = int*, class Sent = int*, class Output1 = int*, class Output2 = int*, class Pred = UnaryPred>
+concept HasPartitionCopyIter =
+    requires(InIter&& input, Sent&& sent, Output1&& output1, Output2&& output2, Pred&& pred) {
+      std::ranges::partition_copy(std::forward<InIter>(input), std::forward<Sent>(sent),
+          std::forward<Output1>(output1), std::forward<Output2>(output2), std::forward<Pred>(pred));
+    };
+
+static_assert(HasPartitionCopyIter<int*, int*, int*, int*, UnaryPred>);
+
+// !input_iterator<I>
+static_assert(!HasPartitionCopyIter<InputIteratorNotDerivedFrom>);
+static_assert(!HasPartitionCopyIter<InputIteratorNotIndirectlyReadable>);
+static_assert(!HasPartitionCopyIter<InputIteratorNotInputOrOutputIterator>);
+
+// !sentinel_for<S, I>
+static_assert(!HasPartitionCopyIter<int*, SentinelForNotSemiregular>);
+static_assert(!HasPartitionCopyIter<int*, SentinelForNotWeaklyEqualityComparableWith>);
+
+// !weakly_incrementable<O1>
+static_assert(!HasPartitionCopyIter<int*, int*, WeaklyIncrementableNotMovable>);
+
+// !weakly_incrementable<O2>
+static_assert(!HasPartitionCopyIter<int*, int*, int*, WeaklyIncrementableNotMovable>);
+
+// !indirect_unary_predicate<projected<I, Proj>>
+static_assert(!HasPartitionCopyIter<int*, int*, int*, int*, IndirectUnaryPredicateNotPredicate>);
+static_assert(!HasPartitionCopyIter<int*, int*, int*, int*, IndirectUnaryPredicateNotCopyConstructible>);
+
+struct Uncopyable {
+  Uncopyable(int&&);
+  Uncopyable(const int&) = delete;
+};
+// !indirectly_copyable<I, O1>
+static_assert(!HasPartitionCopyIter<int*, int*, Uncopyable*>);
+// !indirectly_copyable<I, O2>
+static_assert(!HasPartitionCopyIter<int*, int*, int*, Uncopyable*>);
+
+// Test constraints of the (range) overload.
+// =========================================
+
+template <class InputRange, class Output1 = int*, class Output2 = int*, class Pred = UnaryPred>
+concept HasPartitionCopyRange =
+    requires(InputRange&& input, Output1&& output1, Output2&& output2, Pred&& pred) {
+      std::ranges::partition_copy(std::forward<InputRange>(input),
+          std::forward<Output1>(output1), std::forward<Output2>(output2), std::forward<Pred>(pred));
+    };
+
+template <class T>
+using R = UncheckedRange<T>;
+
+static_assert(HasPartitionCopyRange<R<int*>, int*, int*, UnaryPred>);
+
+// !input_iterator<I>
+static_assert(!HasPartitionCopyRange<InputRangeNotDerivedFrom>);
+static_assert(!HasPartitionCopyRange<InputRangeNotIndirectlyReadable>);
+static_assert(!HasPartitionCopyRange<InputRangeNotInputOrOutputIterator>);
+
+// !weakly_incrementable<O1>
+static_assert(!HasPartitionCopyRange<R<int*>, WeaklyIncrementableNotMovable>);
+
+// !weakly_incrementable<O2>
+static_assert(!HasPartitionCopyRange<R<int*>, int*, WeaklyIncrementableNotMovable>);
+
+// !indirect_unary_predicate<projected<I, Proj>>
+static_assert(!HasPartitionCopyRange<R<int*>, int*, int*, IndirectUnaryPredicateNotPredicate>);
+static_assert(!HasPartitionCopyRange<R<int*>, int*, int*, IndirectUnaryPredicateNotCopyConstructible>);
+
+// !indirectly_copyable<I, O1>
+static_assert(!HasPartitionCopyRange<R<int*>, Uncopyable*>);
+// !indirectly_copyable<I, O2>
+static_assert(!HasPartitionCopyRange<R<int*>, int*, Uncopyable*>);
+
+static_assert(std::is_same_v<std::ranges::partition_copy_result<int, int, int>,
+    std::ranges::in_out_out_result<int, int, int>>);
+
+template <class Iter, class Sent, class OutIter1, class OutIter2, size_t N1, size_t N2, size_t N3, class Pred>
+constexpr void test_one(std::array<int, N1> input, Pred pred, std::array<int, N2> expected_true,
+    std::array<int, N3> expected_false) {
+  static_assert(N2 + N3 == N1);
+  using ResultT = std::ranges::partition_copy_result<Iter, OutIter1, OutIter2>;
+
+  auto begin = input.data();
+  auto end = input.data() + input.size();
+  auto neg_pred = [&](int x) { return !pred(x); };
+
+  { // (iterator, sentinel) overload.
+    std::array<int, N1> out1; // Allocate a bigger size in case of buffer overflow.
+    std::array<int, N1> out2;
+
+    std::same_as<ResultT> decltype(auto) result = std::ranges::partition_copy(
+        Iter(begin), Sent(Iter(end)), OutIter1(out1.begin()), OutIter2(out2.begin()), pred);
+
+    assert(base(result.in) == input.data() + input.size());
+    assert(base(result.out1) == out1.data() + expected_true.size());
+    assert(base(result.out2) == out2.data() + expected_false.size());
+
+    assert(std::ranges::all_of(out1.begin(), base(result.out1), pred));
+    assert(std::ranges::all_of(out2.begin(), base(result.out2), neg_pred));
+  }
+
+  { // (range) overload.
+    std::ranges::subrange range{Iter(begin), Sent(Iter(end))};
+    std::array<int, N1> out1; // Allocate a bigger size in case of buffer overflow.
+    std::array<int, N1> out2;
+
+    std::same_as<ResultT> decltype(auto) result = std::ranges::partition_copy(
+        range, OutIter1(out1.begin()), OutIter2(out2.begin()), pred);
+
+    assert(base(result.in) == input.data() + input.size());
+    assert(base(result.out1) == out1.data() + expected_true.size());
+    assert(base(result.out2) == out2.data() + expected_false.size());
+
+    assert(std::ranges::all_of(out1.begin(), base(result.out1), pred));
+    assert(std::ranges::all_of(out2.begin(), base(result.out2), neg_pred));
+  }
+}
+
+template <class InIter, class Sent, class Out1, class Out2>
+constexpr void test_iterators_in_sent_out1_out2() {
+  auto is_odd = [](int x) { return x % 2 != 0; };
+
+  // Empty sequence.
+  test_one<InIter, Sent, Out1, Out2, 0, 0, 0>({}, is_odd, {}, {});
+  // 1-element sequence, the element satisfies the predicate.
+  test_one<InIter, Sent, Out1, Out2, 1, 1, 0>({1}, is_odd, {1}, {});
+  // 1-element sequence, the element doesn't satisfy the predicate.
+  test_one<InIter, Sent, Out1, Out2, 1, 0, 1>({2}, is_odd, {}, {1});
+  // 2-element sequence, not in order.
+  test_one<InIter, Sent, Out1, Out2, 2, 1, 1>({2, 1}, is_odd, {1}, {2});
+  // 2-element sequence, already in order.
+  test_one<InIter, Sent, Out1, Out2, 2, 1, 1>({1, 2}, is_odd, {1}, {2});
+  // 3-element sequence.
+  test_one<InIter, Sent, Out1, Out2, 3, 2, 1>({2, 1, 3}, is_odd, {1, 3}, {2});
+  // Longer sequence.
+  test_one<InIter, Sent, Out1, Out2, 8, 4, 4>({2, 1, 3, 6, 8, 4, 11, 5}, is_odd, {1, 3, 11, 5}, {2, 6, 8, 4});
+  // Longer sequence with duplicates.
+  test_one<InIter, Sent, Out1, Out2, 8, 3, 5>({2, 1, 3, 6, 2, 8, 1, 6}, is_odd, {1, 3, 1}, {2, 6, 2, 8, 6});
+  // All elements are the same and satisfy the predicate.
+  test_one<InIter, Sent, Out1, Out2, 3, 3, 0>({1, 1, 1}, is_odd, {1, 1, 1}, {});
+  // All elements are the same and don't satisfy the predicate.
+  test_one<InIter, Sent, Out1, Out2, 3, 0, 3>({2, 2, 2}, is_odd, {}, {2, 2, 2});
+  // Already partitioned.
+  test_one<InIter, Sent, Out1, Out2, 6, 3, 3>({1, 3, 5, 4, 6, 8}, is_odd, {1, 3, 5}, {4, 6, 8});
+  // Reverse-partitioned.
+  test_one<InIter, Sent, Out1, Out2, 6, 3, 3>({4, 6, 8, 1, 3, 5}, is_odd, {1, 3, 5}, {4, 6, 8});
+  // Repeating pattern.
+  test_one<InIter, Sent, Out1, Out2, 6, 3, 3>({1, 2, 1, 2, 1, 2}, is_odd, {1, 1, 1}, {2, 2, 2});
+
+  auto is_negative = [](int x) { return x < 0; };
+  // Different comparator.
+  test_one<InIter, Sent, Out1, Out2, 5, 2, 3>({-3, 5, 7, -6, 2}, is_negative, {-3, -6}, {5, 7, 2});
+}
+
+template <class InIter, class Sent, class Out1>
+constexpr void test_iterators_in_sent_out1() {
+  test_iterators_in_sent_out1_out2<InIter, Sent, Out1, cpp17_output_iterator<int*>>();
+  test_iterators_in_sent_out1_out2<InIter, Sent, Out1, cpp20_output_iterator<int*>>();
+  test_iterators_in_sent_out1_out2<InIter, Sent, Out1, random_access_iterator<int*>>();
+  test_iterators_in_sent_out1_out2<InIter, Sent, Out1, int*>();
+}
+
+template <class InIter, class Sent>
+constexpr void test_iterators_in_sent() {
+  test_iterators_in_sent_out1<InIter, Sent, cpp17_output_iterator<int*>>();
+  test_iterators_in_sent_out1<InIter, Sent, cpp20_output_iterator<int*>>();
+  test_iterators_in_sent_out1<InIter, Sent, random_access_iterator<int*>>();
+  test_iterators_in_sent_out1<InIter, Sent, int*>();
+}
+
+template <class InIter>
+constexpr void test_iterators_in() {
+  if constexpr (std::sentinel_for<InIter, InIter>) {
+    test_iterators_in_sent<InIter, InIter>();
+  }
+  test_iterators_in_sent<InIter, sentinel_wrapper<InIter>>();
+}
+
+constexpr void test_iterators() {
+  // Note: deliberately testing with only the weakest and "strongest" iterator types to minimize combinatorial
+  // explosion.
+  test_iterators_in<cpp20_input_iterator<int*>>();
+  test_iterators_in<random_access_iterator<int*>>();
+  test_iterators_in<int*>();
+}
 
 constexpr bool test() {
-  // TODO: main tests.
-  // TODO: A custom comparator works.
-  // TODO: A custom projection works.
+  test_iterators();
+
+  { // A custom projection works.
+    const std::array in = {1, 3, 9, -2, -5, -8};
+    auto is_negative = [](int x) { return x < 0; };
+    auto negate = [](int x) { return -x; };
+    const std::array expected_negative = {-2, -5, -8};
+    const std::array expected_positive = {1, 3, 9};
+
+    { // (iterator, sentinel) overload.
+      {
+        std::array<int, 3> out1, out2;
+        std::ranges::partition_copy(in.begin(), in.end(), out1.begin(), out2.begin(), is_negative);
+        assert(out1 == expected_negative);
+        assert(out2 == expected_positive);
+      }
+      {
+        std::array<int, 3> out1, out2;
+        std::ranges::partition_copy(in.begin(), in.end(), out1.begin(), out2.begin(), is_negative, negate);
+        assert(out1 == expected_positive);
+        assert(out2 == expected_negative);
+      }
+    }
+
+    { // (range) overload.
+      {
+        std::array<int, 3> out1, out2;
+        std::ranges::partition_copy(in, out1.begin(), out2.begin(), is_negative);
+        assert(out1 == expected_negative);
+        assert(out2 == expected_positive);
+      }
+      {
+        std::array<int, 3> out1, out2;
+        std::ranges::partition_copy(in, out1.begin(), out2.begin(), is_negative, negate);
+        assert(out1 == expected_positive);
+        assert(out2 == expected_negative);
+      }
+    }
+  }
+
+  { // Complexity: Exactly `last - first` applications of `pred` and `proj`.
+    {
+      const std::array in = {-2, -5, -8, -11, -10, -5, 1, 3, 9, 6, 8, 2, 4, 2};
+      auto is_negative = [](int x) { return x < 0; };
+      std::array<int, 6> out1;
+      std::array<int, 8> out2;
+
+      int pred_count = 0, proj_count = 0;
+      counting_predicate pred(is_negative, pred_count);
+      counting_projection proj(proj_count);
+
+      {
+        std::ranges::partition_copy(in.begin(), in.end(), out1.begin(), out2.begin(), pred, proj);
+        assert(pred_count == in.size());
+        assert(proj_count == in.size());
+        pred_count = proj_count = 0;
+      }
+
+      {
+        std::ranges::partition_copy(in, out1.begin(), out2.begin(), pred, proj);
+        assert(pred_count == in.size());
+        assert(proj_count == in.size());
+        pred_count = proj_count = 0;
+      }
+    }
+  }
 
   return true;
 }
 
 int main(int, char**) {
   test();
   static_assert(test());
 
   return 0;
 }

libcxx/test/std/algorithms/alg.modifying.operations/alg.partitions/ranges_partition_point.pass.cpp

 //   constexpr borrowed_iterator_t<R>
 //     partition_point(R&& r, Pred pred, Proj proj = {});                                           // Since C++20
 
 #include <algorithm>
 #include <array>
 #include <concepts>
 #include <functional>
 #include <ranges>
+#include <utility>
 
 #include "almost_satisfies_types.h"
 #include "test_iterators.h"
 
-// TODO: SFINAE tests.
+struct UnaryPred { bool operator()(int) const; };
+
+// Test constraints of the (iterator, sentinel) overload.
+// ======================================================
+
+template <class Iter = int*, class Sent = int*, class Pred = UnaryPred>
+concept HasPartitionPointIter =
+    requires(Iter&& iter, Sent&& sent, Pred&& pred) {
+      std::ranges::partition_point(std::forward<Iter>(iter), std::forward<Sent>(sent), std::forward<Pred>(pred));
+    };
+
+static_assert(HasPartitionPointIter<int*, int*, UnaryPred>);
+
+// !forward_iterator<I>
+static_assert(!HasPartitionPointIter<ForwardIteratorNotDerivedFrom>);
+static_assert(!HasPartitionPointIter<ForwardIteratorNotIncrementable>);
+
+// !sentinel_for<S, I>
+static_assert(!HasPartitionPointIter<int*, SentinelForNotSemiregular>);
+static_assert(!HasPartitionPointIter<int*, SentinelForNotWeaklyEqualityComparableWith>);
+
+// !indirect_unary_predicate<projected<I, Proj>>
+static_assert(!HasPartitionPointIter<int*, int*, IndirectUnaryPredicateNotPredicate>);
+static_assert(!HasPartitionPointIter<int*, int*, IndirectUnaryPredicateNotCopyConstructible>);
+
+// Test constraints of the (range) overload.
+// =========================================
+
+template <class Range, class Pred>
+concept HasPartitionPointRange =
+    requires(Range&& range, Pred&& pred) {
+      std::ranges::partition_point(std::forward<Range>(range), std::forward<Pred>(pred));
+    };
+
+template <class T>
+using R = UncheckedRange<T>;
+
+static_assert(HasPartitionPointRange<R<int*>, UnaryPred>);
+
+// !forward_range<R>
+static_assert(!HasPartitionPointRange<ForwardRangeNotDerivedFrom, UnaryPred>);
+static_assert(!HasPartitionPointRange<ForwardRangeNotIncrementable, UnaryPred>);
+
+// !indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
+static_assert(!HasPartitionPointRange<R<int*>, IndirectUnaryPredicateNotPredicate>);
+static_assert(!HasPartitionPointRange<R<int*>, IndirectUnaryPredicateNotCopyConstructible>);
+
+template <class Iter, class Sent, size_t N, class Pred>
+constexpr void test_one(std::array<int, N> input, Pred pred, size_t partition_point) {
+  assert(std::ranges::is_partitioned(input, pred));
+
+  auto begin = Iter(input.data());
+  auto end = Sent(Iter(input.data() + input.size()));
+  auto neg_pred = [&](int x) { return !pred(x); };
+
+  { // (iterator, sentinel) overload.
+    std::same_as<Iter> decltype(auto) result = std::ranges::partition_point(begin, end, pred);
+
+    assert(base(result) == input.data() + partition_point);
+    assert(std::ranges::all_of(begin, result, pred));
+    assert(std::ranges::all_of(result, end, neg_pred));
+  }
+
+  { // (range) overload.
+    auto range = std::ranges::subrange(begin, end);
+    std::same_as<Iter> decltype(auto) result = std::ranges::partition_point(range, pred);
+
+    assert(base(result) == input.data() + partition_point);
+    assert(std::ranges::all_of(begin, result, pred));
+    assert(std::ranges::all_of(result, end, neg_pred));
+  }
+}
+
+template <class Iter, class Sent>
+constexpr void test_iterators_2() {
+  auto is_odd = [](int x) { return x % 2 != 0; };
+
+  // Empty sequence.
+  test_one<Iter, Sent, 0>({}, is_odd, 0);
+  // 1-element sequence, the element satisfies the predicate.
+  test_one<Iter, Sent, 1>({1}, is_odd, 1);
+  // 1-element sequence, the element doesn't satisfy the predicate.
+  test_one<Iter, Sent, 1>({2}, is_odd, 0);
+  // 2-element sequence.
+  test_one<Iter, Sent, 2>({1, 2}, is_odd, 1);
+  // 3-element sequence.
+  test_one<Iter, Sent, 3>({3, 1, 2}, is_odd, 2);
+  // Longer sequence.
+  test_one<Iter, Sent, 8>({1, 3, 11, 5, 6, 2, 8, 4}, is_odd, 4);
+  // Longer sequence with duplicates.
+  test_one<Iter, Sent, 8>({1, 3, 3, 4, 6, 2, 8, 2}, is_odd, 3);
+  // All elements are the same and satisfy the predicate.
+  test_one<Iter, Sent, 3>({1, 1, 1}, is_odd, 3);
+  // All elements are the same and don't satisfy the predicate.
+  test_one<Iter, Sent, 3>({2, 2, 2}, is_odd, 0);
+  // All non-satisfying and all satisfying elements are the same.
+  test_one<Iter, Sent, 6>({1, 1, 1, 2, 2, 2}, is_odd, 3);
+
+  auto is_negative = [](int x) { return x < 0; };
+  // Different comparator.
+  test_one<Iter, Sent, 5>({-3, -6, 5, 7, 2}, is_negative, 2);
+}
+
+template <class Iter>
+constexpr void test_iterators_1() {
+  test_iterators_2<Iter, Iter>();
+  test_iterators_2<Iter, sentinel_wrapper<Iter>>();
+}
+
+constexpr void test_iterators() {
+  test_iterators_1<forward_iterator<int*>>();
+  test_iterators_1<bidirectional_iterator<int*>>();
+  test_iterators_1<random_access_iterator<int*>>();
+  test_iterators_1<contiguous_iterator<int*>>();
+  test_iterators_1<int*>();
+}
 
 constexpr bool test() {
-  // TODO: main tests.
-  // TODO: A custom comparator works.
-  // TODO: A custom projection works.
+  test_iterators();
+
+  { // A custom projection works.
+    const std::array in = {1, 3, 4, 6, 8};
+    auto is_odd = [](int x) { return x % 2 != 0; };
+    auto x2 = [](int x) { return x * 2; };
+    auto expected_no_proj = in.begin() + 2;
+    auto expected_with_proj = in.begin();
+
+    { // (iterator, sentinel) overload.
+      auto result_no_proj = std::ranges::partition_point(in.begin(), in.end(), is_odd);
+      assert(result_no_proj == expected_no_proj);
+      auto result_with_proj = std::ranges::partition_point(in.begin(), in.end(), is_odd, x2);
+      assert(result_with_proj == expected_with_proj);
+    }
+
+    { // (range) overload.
+      auto result_no_proj = std::ranges::partition_point(in, is_odd);
+      assert(result_no_proj == expected_no_proj);
+      auto result_with_proj = std::ranges::partition_point(in, is_odd, x2);
+      assert(result_with_proj == expected_with_proj);
+    }
+  }
 
   return true;
 }
 
 int main(int, char**) {
   test();
   static_assert(test());
 
   return 0;
 }

libcxx/test/std/algorithms/alg.modifying.operations/alg.partitions/ranges_stable_partition.pass.cpp

void test_iterators_2() {
   // All elements are the same and don't satisfy the predicate.
   test_one<Iter, Sent, 3>({2, 2, 2}, is_odd, 0, {2, 2, 2});
   // Already partitioned.
   test_one<Iter, Sent, 6>({1, 3, 5, 4, 6, 8}, is_odd, 3, {1, 3, 5, 4, 6, 8});
   // Reverse-partitioned.
   test_one<Iter, Sent, 6>({4, 6, 8, 1, 3, 5}, is_odd, 3, {1, 3, 5, 4, 6, 8});
   // Repeating pattern.
   test_one<Iter, Sent, 6>({1, 2, 1, 2, 1, 2}, is_odd, 3, {1, 1, 1, 2, 2, 2});
+
+  auto is_negative = [](int x) { return x < 0; };
+  // Different comparator.
+  test_one<Iter, Sent, 5>({-3, 5, 7, -6, 2}, is_negative, {-3, -6, 5, 7, 2});
 }
 
 template <class Iter>
 void test_iterators_1() {
   test_iterators_2<Iter, Iter>();
   test_iterators_2<Iter, sentinel_wrapper<Iter>>();
 }
 

libcxx/test/std/algorithms/ranges_result_alias_declarations.compile.pass.cpp

 static_assert(std::is_same_v<in_out_result<int, long>, uninitialized_copy_result<int, long>>);
 static_assert(std::is_same_v<in_out_result<int, long>, uninitialized_copy_n_result<int, long>>);
 static_assert(std::is_same_v<in_out_result<int, long>, uninitialized_move_result<int, long>>);
 static_assert(std::is_same_v<in_out_result<int, long>, uninitialized_move_n_result<int, long>>);
 // static_assert(std::is_same_v<in_out_result<int, long>, unique_copy_result<int, long>>);
 
 static_assert(std::is_same_v<in_in_out_result<int, long, char>, binary_transform_result<int, long, char>>);
 static_assert(std::is_same_v<in_in_out_result<int, long, char>, merge_result<int, long, char>>);
-// static_assert(std::is_same_v<in_in_out_result<int, long, char>, set_symmetric_difference_result<int, long, char>>);
-// static_assert(std::is_same_v<in_in_out_result<int, long, char>, set_union_result<int, long, char>>);
-// static_assert(std::is_same_v<in_in_out_result<int, long, char>, set_intersection_result<int, long, char>>);
+static_assert(std::is_same_v<in_in_out_result<int, long, char>, set_symmetric_difference_result<int, long, char>>);
+static_assert(std::is_same_v<in_in_out_result<int, long, char>, set_union_result<int, long, char>>);
+static_assert(std::is_same_v<in_in_out_result<int, long, char>, set_intersection_result<int, long, char>>);
 
-// static_assert(std::is_same_v<in_out_out_result<int, long, char>, partition_copy_result<int, long, char>>);
+static_assert(std::is_same_v<in_out_out_result<int, long, char>, partition_copy_result<int, long, char>>);
 
 static_assert(std::is_same_v<min_max_result<int>, minmax_result<int>>);
 static_assert(std::is_same_v<min_max_result<int>, minmax_element_result<int>>);
 
 // static_assert(std::is_same_v<in_found_result<int>, next_permutation_result<int>>);
 // static_assert(std::is_same_v<in_found_result<int>, prev_permutation_result<int>>);
 
 // static_assert(std::is_same_v<out_value_result<int>, iota_result<int>>);

libcxx/test/std/algorithms/ranges_robust_against_nonbool_predicates.compile.pass.cpp

 
 void test_all() {
   std::array in = {1, 2, 3};
   std::array in2 = {4, 5, 6};
   auto mid = in.begin() + 1;
 
   std::array output = {4, 5, 6};
   auto out = output.begin();
-  //auto out2 = output.begin() + 1;
+  auto out2 = output.begin() + 1;
 
   int x = 2;
   int count = 1;
 
   in_pred(std::ranges::any_of, in, unary_pred);
   in_pred(std::ranges::all_of, in, unary_pred);
   in_pred(std::ranges::none_of, in, unary_pred);
   in_pred(std::ranges::find_if, in, unary_pred);
   in_pred(std::ranges::find_if_not, in, unary_pred);
   in2_pred(std::ranges::find_first_of, in, in2, binary_pred);
   in_pred(std::ranges::adjacent_find, in, binary_pred);
   in2_pred(std::ranges::mismatch, in, in2, binary_pred);
   in2_pred(std::ranges::equal, in, in2, binary_pred);
   in2_pred(std::ranges::lexicographical_compare, in, in2, binary_pred);
-  //in_pred(std::ranges::partition_point, unary_pred);
+  in_pred(std::ranges::partition_point, in, unary_pred);
   in_val_pred(std::ranges::lower_bound, in, x, binary_pred);
   in_val_pred(std::ranges::upper_bound, in, x, binary_pred);
   //in_val_pred(std::ranges::equal_range, in, x, binary_pred);
   in_val_pred(std::ranges::binary_search, in, x, binary_pred);
 
   // min
   std::ranges::min(1, 2, binary_pred);
   std::ranges::min(std::initializer_list<int>{1, 2}, binary_pred);
void test_all() {
   //std::ranges::replace_if(in.begin(), in.end(), unary_pred, x);
   //std::ranges::replace_if(in, unary_pred, x);
   // replace_copy_if
   //std::ranges::replace_copy_if(in.begin(), in.end(), out, unary_pred, x);
   //std::ranges::replace_copy_if(in, out, unary_pred, x);
 
   //in_out_pred(std::ranges::unique_copy, in, out, binary_pred);
   // partition_copy
-  //std::ranges::partition_copy(in.begin(), in.end(), out, out2, unary_pred);
-  //std::ranges::partition_copy(in, out, out2, unary_pred);
+  std::ranges::partition_copy(in.begin(), in.end(), out, out2, unary_pred);
+  std::ranges::partition_copy(in, out, out2, unary_pred);
   //in2_pred(std::ranges::partial_sort_copy, in, in2, binary_pred);
   in2_out_pred(std::ranges::merge, in, in2, out, binary_pred);
   in2_out_pred(std::ranges::set_difference, in, in2, out, binary_pred);
   in2_out_pred(std::ranges::set_intersection, in, in2, out, binary_pred);
   in2_out_pred(std::ranges::set_symmetric_difference, in, in2, out, binary_pred);
   in2_out_pred(std::ranges::set_union, in, in2, out, binary_pred);
   in_pred(std::ranges::remove_if, in, unary_pred);
   //in_pred(std::ranges::unique, in, binary_pred);

libcxx/test/std/algorithms/ranges_robust_against_omitting_invoke.compile.pass.cpp

 
 void test_all() {
   std::array in = {Bar{Foo{1}}, Bar{Foo{2}}, Bar{Foo{3}}};
   std::array in2 = {Bar{Foo{4}}, Bar{Foo{5}}, Bar{Foo{6}}};
   auto mid = in.begin() + 1;
 
   std::array output = {Bar{Foo{4}}, Bar{Foo{5}}, Bar{Foo{6}}};
   auto out = output.begin();
-  //auto out2 = output.begin() + 1;
+  auto out2 = output.begin() + 1;
 
   Bar a{Foo{1}};
   Bar b{Foo{2}};
   //Bar c{Foo{3}};
 
   Foo x{2};
   size_t count = 1;
 
   in_pred(std::ranges::any_of, in, &Foo::unary_pred, &Bar::val);
   in_pred(std::ranges::all_of, in, &Foo::unary_pred, &Bar::val);
   in_pred(std::ranges::none_of, in, &Foo::unary_pred, &Bar::val);
   in_val(std::ranges::find, in, x, &Bar::val);
   in_pred(std::ranges::find_if, in, &Foo::unary_pred, &Bar::val);
   in_pred(std::ranges::find_if_not, in, &Foo::unary_pred, &Bar::val);
   in2_pred(std::ranges::find_first_of, in, in2, &Foo::binary_pred, &Bar::val, &Bar::val);
   in_pred(std::ranges::adjacent_find, in, &Foo::binary_pred, &Bar::val);
   in2_pred(std::ranges::mismatch, in, in2, &Foo::binary_pred, &Bar::val, &Bar::val);
   in2_pred(std::ranges::equal, in, in2, &Foo::binary_pred, &Bar::val, &Bar::val);
   in2_pred(std::ranges::lexicographical_compare, in, in2, &Foo::binary_pred, &Bar::val, &Bar::val);
-  //in_pred(std::ranges::partition_point, in, &Foo::unary_pred, &Bar::val);
+  in_pred(std::ranges::partition_point, in, &Foo::unary_pred, &Bar::val);
   in_val_pred(std::ranges::lower_bound, in, x, &Foo::binary_pred, &Bar::val);
   in_val_pred(std::ranges::upper_bound, in, x, &Foo::binary_pred, &Bar::val);
   //in_val_pred(std::ranges::equal_range, in, x, &Foo::binary_pred, &Bar::val);
   in_val_pred(std::ranges::binary_search, in, x, &Foo::binary_pred, &Bar::val);
 
   // min
   std::ranges::min(a, b, &Foo::binary_pred, &Bar::val);
   std::ranges::min(std::initializer_list<Bar>{a, b}, &Foo::binary_pred, &Bar::val);
void test_all() {
   //std::ranges::replace_copy_if(in.begin(), in.end(), out, pred, a, &Bar::val);
   //std::ranges::replace_copy_if(in, out, pred, a, &Bar::val);
   // `swap_ranges` has neither a projection nor a predicate.
   // `reverse_copy` has neither a projection nor a predicate.
   // `rotate_copy` has neither a projection nor a predicate.
   // `sample` has no requirement that the given generator be invoked via `std::invoke`.
   //in_out_pred(std::ranges::unique_copy, in, out, &Foo::binary_pred, &Bar::val);
   // partition_copy
-  //std::ranges::partition_copy(in.begin(), in.end(), out, out2, &Foo::unary_pred, &Bar::val);
-  //std::ranges::partition_copy(in, out, out2, &Foo::unary_pred, &Bar::val);
+  std::ranges::partition_copy(in.begin(), in.end(), out, out2, &Foo::unary_pred, &Bar::val);
+  std::ranges::partition_copy(in, out, out2, &Foo::unary_pred, &Bar::val);
   //in2_pred(std::ranges::partial_sort_copy, in, in2, &Foo::binary_pred, &Bar::val);
   in2_out_pred(std::ranges::merge, in, in2, out, &Foo::binary_pred, &Bar::val, &Bar::val);
   in2_out_pred(std::ranges::set_difference, in, in2, out, &Foo::binary_pred, &Bar::val, &Bar::val);
   in2_out_pred(std::ranges::set_intersection, in, in2, out, &Foo::binary_pred, &Bar::val, &Bar::val);
   in2_out_pred(std::ranges::set_symmetric_difference, in, in2, out, &Foo::binary_pred, &Bar::val, &Bar::val);
   in2_out_pred(std::ranges::set_union, in, in2, out, &Foo::binary_pred, &Bar::val, &Bar::val);
   in_val(std::ranges::remove, in, x, &Bar::val);
   in_pred(std::ranges::remove_if, in, &Foo::unary_pred, &Bar::val);

libcxx/test/std/algorithms/ranges_robust_against_proxy_iterators.pass.cpp

constexpr void run_tests() {
   ProxyRange in{input};
   std::array input2 = {T{4}, T{5}, T{6}};
   ProxyRange in2{input2};
 
   auto mid = in.begin() + 1;
 
   std::array output = {T{4}, T{5}, T{6}, T{7}, T{8}, T{9}};
   ProxyIterator out{output.begin()};
-  //auto out2 = output.begin() + 1;
+  ProxyIterator out2{output.begin() + 1};
 
   T num{2};
   Proxy<T&> x{num};
   int count = 1;
 
   auto unary_pred = [](const Proxy<T&>&) { return true; };
   //auto binary_pred = [](const Proxy<T>&, const Proxy<T>&) { return return false; };
   auto binary_func = [](const Proxy<T>&, const Proxy<T>&) -> Proxy<T> { return Proxy<T>(T()); };
   //auto gen = [] { return Proxy<T>(T{42}); };
   //std::mt19937 rand_gen;
 
   test(std::ranges::any_of, in, unary_pred);
   test(std::ranges::all_of, in, unary_pred);
   test(std::ranges::none_of, in, unary_pred);
   test(std::ranges::find, in, x);
   test(std::ranges::find_if, in, unary_pred);
   test(std::ranges::find_if_not, in, unary_pred);
   test(std::ranges::find_first_of, in, in2);
   test(std::ranges::adjacent_find, in);
   test(std::ranges::mismatch, in, in2);
   test(std::ranges::equal, in, in2);
   test(std::ranges::lexicographical_compare, in, in2);
-  //test(std::ranges::partition_point, unary_pred);
+  test(std::ranges::partition_point, in, unary_pred);
   test(std::ranges::lower_bound, in, x);
   test(std::ranges::upper_bound, in, x);
   //test(std::ranges::equal_range, in, x);
   test(std::ranges::binary_search, in, x);
 
   test(std::ranges::min_element, in);
   test(std::ranges::max_element, in);
   test(std::ranges::minmax_element, in);
//test(std::ranges::remove_copy_if, in, out, unary_pred);
     //test(std::ranges::replace_copy, in, out, x, x);
     //test(std::ranges::replace_copy_if, in, out, unary_pred, x);
   }
   test(std::ranges::swap_ranges, in, in2);
   if constexpr (std::copyable<T>) {
     test(std::ranges::reverse_copy, in, out);
     test_mid(std::ranges::rotate_copy, in, mid, out);
     //test(std::ranges::unique_copy, in, out);
-    //test(std::ranges::partition_copy, in, out, out2, unary_pred);
+    test(std::ranges::partition_copy, in, out, out2, unary_pred);
     //test_mid(std::ranges::partial_sort_copy, in, in2);
     test(std::ranges::merge, in, in2, out);
     test(std::ranges::set_difference, in, in2, out);
     test(std::ranges::set_intersection, in, in2, out);
     test(std::ranges::set_symmetric_difference, in, in2, out);
     test(std::ranges::set_union, in, in2, out);
   }
   test(std::ranges::remove, in, x);
   test(std::ranges::remove_if, in, unary_pred);
   test(std::ranges::reverse, in);
   //test_mid(std::ranges::rotate, in, mid);
   //test(std::ranges::shuffle, in, rand_gen);
   //test(std::ranges::sample, in, out, count, rand_gen);
   //test(std::ranges::unique, in);
   test(std::ranges::partition, in, unary_pred);
-  if (!std::is_constant_evaluated())
-    test(std::ranges::stable_partition, in, unary_pred);
+  // TODO(ranges): `stable_partition` requires `ranges::rotate` to be implemented.
+  //if (!std::is_constant_evaluated())
+  //  test(std::ranges::stable_partition, in, unary_pred);
   test(std::ranges::sort, in);
-  // TODO: `stable_sort` requires `ranges::rotate` to be implemented.
+  // TODO(ranges): `stable_sort` requires `ranges::rotate` to be implemented.
   //if (!std::is_constant_evaluated())
   //  test(std::ranges::stable_sort, in);
   //test_mid(std::ranges::partial_sort, in, mid);
   test_mid(std::ranges::nth_element, in, mid);
   //if (!std::is_constant_evaluated())
   //  test_mid(std::ranges::inplace_merge, in, mid);
   test(std::ranges::make_heap, in);
   test(std::ranges::push_heap, in);

libcxx/test/std/library/description/conventions/customization.point.object/niebloid.compile.pass.cpp

 static_assert(test(std::ranges::move, a, a));
 static_assert(test(std::ranges::move_backward, a, a));
 //static_assert(test(std::ranges::next_permutation, a));
 static_assert(test(std::ranges::none_of, a, odd));
 static_assert(test(std::ranges::nth_element, a, a+5));
 //static_assert(test(std::ranges::partial_sort, a, a+5));
 //static_assert(test(std::ranges::partial_sort_copy, a, a));
 static_assert(test(std::ranges::partition, a, odd));
-//static_assert(test(std::ranges::partition_copy, a, a, a, odd));
-//static_assert(test(std::ranges::partition_point, a, odd));
+static_assert(test(std::ranges::partition_copy, a, a, a, odd));
+static_assert(test(std::ranges::partition_point, a, odd));
 static_assert(test(std::ranges::pop_heap, a));
 //static_assert(test(std::ranges::prev_permutation, a));
 static_assert(test(std::ranges::push_heap, a));
 static_assert(test(std::ranges::remove, a, 42));
 //static_assert(test(std::ranges::remove_copy, a, a, 42));
 //static_assert(test(std::ranges::remove_copy_if, a, a, odd));
 static_assert(test(std::ranges::remove_if, a, odd));
 static_assert(test(std::ranges::replace, a, 42, 43));

libcxx/test/support/counting_predicates.h

 //===----------------------------------------------------------------------===//
 //
 // 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 TEST_SUPPORT_COUNTING_PREDICATES_H
 #define TEST_SUPPORT_COUNTING_PREDICATES_H
 
 #include <cstddef>
+#include <utility>
 
 template <typename Predicate, typename Arg>
 struct unary_counting_predicate {
 public:
     typedef Arg argument_type;
     typedef bool result_type;
 
     unary_counting_predicate(Predicate p) : p_(p), count_(0) {}
public:
     size_t count() const { return count_; }
     void reset() { count_ = 0; }
 
 private:
     Predicate p_;
     mutable size_t count_;
 };
 
+#if TEST_STD_VER > 14
+
+template <class Predicate>
+class counting_predicate {
+  Predicate pred_;
+  int* count_ = nullptr;
+
+public:
+  constexpr counting_predicate() = default;
+  constexpr counting_predicate(Predicate pred, int& count) : pred_(std::move(pred)), count_(&count) {}
+
+  template <class... Args>
+  constexpr decltype(auto) operator()(Args&& ...args) const {
+    ++(*count_);
+    return pred_(std::forward<Args>(args)...);
+  }
+};
+
+template <class Predicate>
+counting_predicate(Predicate pred, int& count) -> counting_predicate<Predicate>;
+
+#endif
+
 #endif // TEST_SUPPORT_COUNTING_PREDICATES_H

libcxx/test/support/counting_projection.h

+//===----------------------------------------------------------------------===//
+//
+// 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 TEST_SUPPORT_COUNTING_PROJECTION_H
+#define TEST_SUPPORT_COUNTING_PROJECTION_H
+
+#include <functional>
+#include <utility>
+
+#if TEST_STD_VER > 14
+
+template <class Proj = std::identity>
+class counting_projection {
+  Proj proj_;
+  int* count_ = nullptr;
+
+public:
+  constexpr counting_projection() = default;
+  constexpr counting_projection(int& count) : count_(&count) {}
+  constexpr counting_projection(Proj proj, int& count) : proj_(std::move(proj)), count_(&count) {}
+
+  template <class T>
+  constexpr decltype(auto) operator()(T&& value) const {
+    ++(*count_);
+    return proj_(std::forward<T>(value));
+  }
+};
+
+counting_projection(int& count) -> counting_projection<std::identity>;
+template <class Proj>
+counting_projection(Proj proj, int& count) -> counting_projection<Proj>;
+
+#endif
+
+#endif // TEST_SUPPORT_COUNTING_PROJECTION_H