vendor/llvm-project/llvmorg-15-init-17485-ga3e38b4a206b

1 files changed, 122 insertions, 0 deletions

diff --git a/libcxx/include/algorithm b/libcxx/include/algorithm
index f616a031960e..5958ad1a95af 100644
--- a/libcxx/include/algorithm
+++ b/libcxx/include/algorithm
@@ -360,6 +360,17 @@ namespace ranges {
     borrowed_iterator_t<R>
       ranges::stable_sort(R&& r, Comp comp = {}, Proj proj = {});                           // since C++20
 
+  template<random_access_iterator I, sentinel_for<I> S, class Comp = ranges::less,
+           class Proj = identity>
+    requires sortable<I, Comp, Proj>
+    constexpr I
+      ranges::partial_sort(I first, I middle, S last, Comp comp = {}, Proj proj = {});      // since C++20
+
+  template<random_access_range R, class Comp = ranges::less, class Proj = identity>
+    requires sortable<iterator_t<R>, Comp, Proj>
+    constexpr borrowed_iterator_t<R>
+      ranges::partial_sort(R&& r, iterator_t<R> middle, Comp comp = {}, Proj proj = {});    // since C++20
+
   template<class T, output_iterator<const T&> O, sentinel_for<O> S>
     constexpr O ranges::fill(O first, S last, const T& value);                              // since C++20
 
@@ -464,6 +475,28 @@ namespace ranges {
              ranges::less>
     constexpr bool binary_search(R&& r, const T& value, Comp comp = {},
                                          Proj proj = {});                                     // since C++20
+
+  template<permutable I, sentinel_for<I> S, class Proj = identity,
+           indirect_unary_predicate<projected<I, Proj>> Pred>
+    constexpr subrange<I>
+      partition(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>
+    requires permutable<iterator_t<R>>
+    constexpr borrowed_subrange_t<R>
+      partition(R&& r, Pred pred, Proj proj = {});                                            // Since C++20
+
+  template<bidirectional_iterator I, sentinel_for<I> S, class Proj = identity,
+           indirect_unary_predicate<projected<I, Proj>> Pred>
+    requires permutable<I>
+    subrange<I> stable_partition(I first, S last, Pred pred, Proj proj = {});                 // Since C++20
+
+  template<bidirectional_range R, class Proj = identity,
+           indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
+    requires permutable<iterator_t<R>>
+    borrowed_subrange_t<R> stable_partition(R&& r, Pred pred, Proj proj = {});                // Since C++20
+
   template<input_iterator I1, sentinel_for<I1> S1, forward_iterator I2, sentinel_for<I2> S2,
            class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity>
     requires indirectly_comparable<I1, I2, Pred, Proj1, Proj2>
@@ -548,6 +581,34 @@ namespace ranges {
     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
 
@@ -649,6 +710,16 @@ namespace ranges {
     constexpr ranges::rotate_copy_result<borrowed_iterator_t<R>, O>
       ranges::rotate_copy(R&& r, iterator_t<R> middle, O result);                                   // since C++20
 
+  template<random_access_iterator I, sentinel_for<I> S, class Gen>
+    requires permutable<I> &&
+            uniform_random_bit_generator<remove_reference_t<Gen>>
+    I shuffle(I first, S last, Gen&& g);                                                           // Since C++20
+
+  template<random_access_range R, class Gen>
+    requires permutable<iterator_t<R>> &&
+            uniform_random_bit_generator<remove_reference_t<Gen>>
+    borrowed_iterator_t<R> shuffle(R&& r, Gen&& g);                                                // Since C++20
+
   template<forward_iterator I1, sentinel_for<I1> S1, forward_iterator I2,
            sentinel_for<I2> S2, class Pred = ranges::equal_to,
            class Proj1 = identity, class Proj2 = identity>
@@ -711,7 +782,49 @@ namespace ranges {
                                                       borrowed_iterator_t<R2>, O>
       set_symmetric_difference(R1&& r1, R2&& r2, O result, Comp comp = {},
                                Proj1 proj1 = {}, Proj2 proj2 = {});                                 // since C++20
+
+  template<forward_iterator I, sentinel_for<I> S, class T, class Proj = identity,
+           indirect_strict_weak_order<const T*, projected<I, Proj>> Comp = ranges::less>
+    constexpr subrange<I>
+      equal_range(I first, S last, const T& value, Comp comp = {}, Proj proj = {});                 // since C++20
+  
+  template<forward_range R, class T, class Proj = identity,
+           indirect_strict_weak_order<const T*, projected<iterator_t<R>, Proj>> Comp =
+             ranges::less>
+    constexpr borrowed_subrange_t<R>
+      equal_range(R&& r, const T& value, Comp comp = {}, Proj proj = {});                           // since C++20
+  
+  template<class I1, class I2, class O>
+    using set_union_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 set_union_result<I1, I2, O>
+      set_union(I1 first1, S1 last1, I2 first2, S2 last2, O result, Comp comp = {},
+                Proj1 proj1 = {}, Proj2 proj2 = {});                                                // since C++20
+
+  template<input_range R1, input_range R2, weakly_incrementable O,
+           class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity>
+    requires mergeable<iterator_t<R1>, iterator_t<R2>, O, Comp, Proj1, Proj2>
+    constexpr set_union_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>, O>
+      set_union(R1&& r1, R2&& r2, O result, Comp comp = {},
+                Proj1 proj1 = {}, Proj2 proj2 = {});                                                // since C++20
+
+  template<input_iterator I1, sentinel_for<I1> S1, input_iterator I2, sentinel_for<I2> S2,
+           class Proj1 = identity, class Proj2 = identity,
+           indirect_strict_weak_order<projected<I1, Proj1>, projected<I2, Proj2>> Comp =
+             ranges::less>
+    constexpr bool includes(I1 first1, S1 last1, I2 first2, S2 last2, Comp comp = {},
+                            Proj1 proj1 = {}, Proj2 proj2 = {});                                   // Since C++20
   
+  template<input_range R1, input_range R2, class Proj1 = identity,
+           class Proj2 = identity,
+           indirect_strict_weak_order<projected<iterator_t<R1>, Proj1>,
+                                      projected<iterator_t<R2>, Proj2>> Comp = ranges::less>
+    constexpr bool includes(R1&& r1, R2&& r2, Comp comp = {},
+                            Proj1 proj1 = {}, Proj2 proj2 = {});                                   // Since C++20
 }
 
     constexpr bool     // constexpr in C++20
@@ -1452,6 +1565,7 @@ template <class BidirectionalIterator, class Compare>
 #include <__algorithm/ranges_count.h>
 #include <__algorithm/ranges_count_if.h>
 #include <__algorithm/ranges_equal.h>
+#include <__algorithm/ranges_equal_range.h>
 #include <__algorithm/ranges_fill.h>
 #include <__algorithm/ranges_fill_n.h>
 #include <__algorithm/ranges_find.h>
@@ -1461,6 +1575,7 @@ template <class BidirectionalIterator, class Compare>
 #include <__algorithm/ranges_find_if_not.h>
 #include <__algorithm/ranges_for_each.h>
 #include <__algorithm/ranges_for_each_n.h>
+#include <__algorithm/ranges_includes.h>
 #include <__algorithm/ranges_is_partitioned.h>
 #include <__algorithm/ranges_is_sorted.h>
 #include <__algorithm/ranges_is_sorted_until.h>
@@ -1479,6 +1594,10 @@ template <class BidirectionalIterator, class Compare>
 #include <__algorithm/ranges_move_backward.h>
 #include <__algorithm/ranges_none_of.h>
 #include <__algorithm/ranges_nth_element.h>
+#include <__algorithm/ranges_partial_sort.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>
@@ -1493,8 +1612,11 @@ template <class BidirectionalIterator, class Compare>
 #include <__algorithm/ranges_set_difference.h>
 #include <__algorithm/ranges_set_intersection.h>
 #include <__algorithm/ranges_set_symmetric_difference.h>
+#include <__algorithm/ranges_set_union.h>
+#include <__algorithm/ranges_shuffle.h>
 #include <__algorithm/ranges_sort.h>
 #include <__algorithm/ranges_sort_heap.h>
+#include <__algorithm/ranges_stable_partition.h>
 #include <__algorithm/ranges_stable_sort.h>
 #include <__algorithm/ranges_swap_ranges.h>
 #include <__algorithm/ranges_transform.h>