1 //===----------------------------------------------------------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 
9 // UNSUPPORTED: c++03, c++11, c++14, c++17
10 // UNSUPPORTED: libcpp-has-no-incomplete-ranges
11 
12 // <algorithm>
13 
14 // template<input_iterator I1, sentinel_for<I1> S1,
15 //          random_access_iterator I2, sentinel_for<I2> S2,
16 //          class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity>
17 //   requires indirectly_copyable<I1, I2> && sortable<I2, Comp, Proj2> &&
18 //            indirect_strict_weak_order<Comp, projected<I1, Proj1>, projected<I2, Proj2>>
19 //   constexpr partial_sort_copy_result<I1, I2>
20 //     partial_sort_copy(I1 first, S1 last, I2 result_first, S2 result_last,
21 //                       Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});               // Since C++20
22 //
23 // template<input_range R1, random_access_range R2, class Comp = ranges::less,
24 //          class Proj1 = identity, class Proj2 = identity>
25 //   requires indirectly_copyable<iterator_t<R1>, iterator_t<R2>> &&
26 //            sortable<iterator_t<R2>, Comp, Proj2> &&
27 //            indirect_strict_weak_order<Comp, projected<iterator_t<R1>, Proj1>,
28 //                                       projected<iterator_t<R2>, Proj2>>
29 //   constexpr partial_sort_copy_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>>
30 //     partial_sort_copy(R1&& r, R2&& result_r, Comp comp = {},
31 //                       Proj1 proj1 = {}, Proj2 proj2 = {});                               // Since C++20
32 
33 #include <algorithm>
34 #include <array>
35 #include <concepts>
36 #include <functional>
37 #include <ranges>
38 #include <utility>
39 
40 #include "MoveOnly.h"
41 #include "almost_satisfies_types.h"
42 #include "test_iterators.h"
43 
44 // Test constraints of the (iterator, sentinel) overload.
45 // ======================================================
46 
47 template <class Iter1 = int*, class Sent1 = int*, class Iter2 = int*, class Sent2 = int*,
48           class Comp = std::ranges::less>
49 concept HasPartialSortCopyIter =
50     requires(Iter1&& first1, Sent1&& last1, Iter2&& first2, Sent2&& last2, Comp&& comp) {
51       std::ranges::partial_sort_copy(std::forward<Iter1>(first1), std::forward<Sent1>(last1),
52           std::forward<Iter2>(first2), std::forward<Sent2>(last2), std::forward<Comp>(comp));
53     };
54 
55 static_assert(HasPartialSortCopyIter<int*, int*, int*, int*, std::ranges::less>);
56 
57 // !input_iterator<I1>
58 static_assert(!HasPartialSortCopyIter<InputIteratorNotDerivedFrom>);
59 static_assert(!HasPartialSortCopyIter<InputIteratorNotIndirectlyReadable>);
60 static_assert(!HasPartialSortCopyIter<InputIteratorNotInputOrOutputIterator>);
61 
62 // !sentinel_for<S1, I1>
63 static_assert(!HasPartialSortCopyIter<int*, SentinelForNotSemiregular>);
64 static_assert(!HasPartialSortCopyIter<int*, SentinelForNotWeaklyEqualityComparableWith>);
65 
66 // !random_access_iterator<I2>
67 static_assert(!HasPartialSortCopyIter<int*, int*, RandomAccessIteratorNotDerivedFrom>);
68 static_assert(!HasPartialSortCopyIter<int*, int*, RandomAccessIteratorBadIndex>);
69 
70 // !sentinel_for<S2, I2>
71 static_assert(!HasPartialSortCopyIter<int*, int*, int*, SentinelForNotSemiregular>);
72 static_assert(!HasPartialSortCopyIter<int*, int*, int*, SentinelForNotWeaklyEqualityComparableWith>);
73 
74 // !indirect_unary_predicate<projected<I, Proj>>
75 static_assert(!HasPartialSortCopyIter<int*, int*, int*, int*, IndirectUnaryPredicateNotPredicate>);
76 static_assert(!HasPartialSortCopyIter<int*, int*, int*, int*, IndirectUnaryPredicateNotCopyConstructible>);
77 
78 // !indirectly_copyable<I1, I2>
79 static_assert(!HasPartialSortCopyIter<int*, int*, MoveOnly*>);
80 
81 // !sortable<I2, Comp, Proj2>
82 static_assert(!HasPartialSortCopyIter<int*, int*, const int*, const int*>);
83 
84 struct NoComparator {};
85 // !indirect_strict_weak_order<Comp, projected<I1, Proj1>, projected<I2, Proj2>>
86 static_assert(!HasPartialSortCopyIter<NoComparator*, NoComparator*, NoComparator*, NoComparator*>);
87 
88 // Test constraints of the (range) overload.
89 // ======================================================
90 
91 template <class T>
92 using R = UncheckedRange<T>;
93 
94 template <class Range1 = R<int*>, class Range2 = R<int*>, class Comp = std::ranges::less>
95 concept HasPartialSortCopyRange =
96     requires(Range1&& range1, Range2&& range2, Comp&& comp) {
97       std::ranges::partial_sort_copy(std::forward<Range1>(range1), std::forward<Range2>(range2),
98           std::forward<Comp>(comp));
99     };
100 
101 static_assert(HasPartialSortCopyRange<R<int*>, R<int*>, std::ranges::less>);
102 
103 // !input_range<R1>
104 static_assert(!HasPartialSortCopyRange<InputRangeNotDerivedFrom>);
105 static_assert(!HasPartialSortCopyRange<InputRangeNotIndirectlyReadable>);
106 static_assert(!HasPartialSortCopyRange<InputRangeNotInputOrOutputIterator>);
107 
108 // !random_access_range<R2>
109 static_assert(!HasPartialSortCopyRange<R<int*>, RandomAccessRangeNotDerivedFrom>);
110 static_assert(!HasPartialSortCopyRange<R<int*>, RandomAccessRangeBadIndex>);
111 
112 // !indirectly_copyable<iterator_t<R1>, iterator_t<R2>>
113 static_assert(!HasPartialSortCopyRange<R<int*>, R<MoveOnly*>>);
114 
115 // !sortable<iterator_t<R2>, Comp, Proj2>
116 static_assert(!HasPartialSortCopyRange<R<int*>, R<const int*>>);
117 
118 // !indirect_strict_weak_order<Comp, projected<iterator_t<R1>, Proj1>, projected<iterator_t<R2>, Proj2>>
119 static_assert(!HasPartialSortCopyRange<R<NoComparator*>, R<NoComparator*>>);
120 
121 static_assert(std::is_same_v<std::ranges::partial_sort_copy_result<int, int>, std::ranges::in_out_result<int, int>>);
122 
123 template <class Iter, class Sent, class OutIter, class OutSent, size_t N>
test_one(std::array<int,N> input,size_t input_size,size_t output_size,std::array<int,N> sorted)124 constexpr void test_one(
125     std::array<int, N> input, size_t input_size, size_t output_size, std::array<int, N> sorted) {
126   assert(input_size <= N);
127   assert(output_size <= N + 1); // To support testing the case where output size exceeds input size.
128 
129   using ResultT = std::ranges::partial_sort_copy_result<Iter, OutIter>;
130   // To support testing the case where output size exceeds input size; also makes sure calling `out.data() + int()` is
131   // valid.
132   constexpr size_t OutputSize = N + 1;
133   size_t result_size = std::ranges::min(input_size, output_size);
134 
135   auto begin = input.data();
136   auto end = input.data() + input_size;
137 
138   { // (iterator, sentinel) overload.
139     std::array<int, OutputSize> out;
140     auto out_begin = out.data();
141     auto out_end = out.data() + output_size;
142 
143     std::same_as<ResultT> decltype(auto) result = std::ranges::partial_sort_copy(
144         Iter(begin), Sent(Iter(end)), OutIter(out_begin), OutSent(OutIter(out_end)));
145 
146     assert(base(result.in) == input.data() + input_size);
147     assert(base(result.out) == out.data() + result_size);
148 
149     assert(std::ranges::equal(std::ranges::subrange(out.begin(), out.begin() + result_size),
150            std::ranges::subrange(sorted.begin(), sorted.begin() + result_size)));
151   }
152 
153   { // (range) overload.
154     std::array<int, OutputSize> out;
155     auto out_begin = out.data();
156     auto out_end = out.data() + output_size;
157     auto in_range = std::ranges::subrange(Iter(begin), Sent(Iter(end)));
158     auto out_range = std::ranges::subrange(OutIter(out_begin), OutSent(OutIter(out_end)));
159 
160     std::same_as<ResultT> decltype(auto) result = std::ranges::partial_sort_copy(in_range, out_range);
161 
162     assert(base(result.in) == input.data() + input_size);
163     assert(base(result.out) == out.data() + result_size);
164 
165     assert(std::ranges::equal(std::ranges::subrange(out.begin(), out.begin() + result_size),
166            std::ranges::subrange(sorted.begin(), sorted.begin() + result_size)));
167   }
168 
169 }
170 
171 template <class Iter, class Sent, class OutIter, class OutSent, size_t N>
test_all_subsequences(const std::array<int,N> input)172 constexpr void test_all_subsequences(const std::array<int, N> input) {
173   auto sorted = input;
174   std::sort(sorted.begin(), sorted.end());
175 
176   // Whole input, increasing output size. Also check the case when `output_size` exceeds input size.
177   for (size_t out_size = 0; out_size <= N + 1; ++out_size) {
178     test_one<Iter, Sent, OutIter, OutSent>(input, N, out_size, sorted);
179   }
180 }
181 
182 template <class InIter, class Sent1, class OutIter, class Sent2>
test_iterators_in_sent1_out_sent2()183 constexpr void test_iterators_in_sent1_out_sent2() {
184   // Empty sequence.
185   test_all_subsequences<InIter, Sent1, OutIter, Sent2, 0>({});
186 
187   // 1-element sequence.
188   test_all_subsequences<InIter, Sent1, OutIter, Sent2>(std::array{1});
189 
190   // 2-element sequence.
191   test_all_subsequences<InIter, Sent1, OutIter, Sent2>(std::array{2, 1});
192 
193   // 3-element sequence.
194   test_all_subsequences<InIter, Sent1, OutIter, Sent2>(std::array{2, 1, 3});
195 
196   // Longer sequence.
197   test_all_subsequences<InIter, Sent1, OutIter, Sent2>(std::array{2, 1, 3, 6, 8, 4, 11, 5});
198 
199   // Longer sequence with duplicates.
200   test_all_subsequences<InIter, Sent1, OutIter, Sent2>(std::array{2, 1, 3, 6, 2, 8, 6});
201 
202   // All elements are the same.
203   test_all_subsequences<InIter, Sent1, OutIter, Sent2>(std::array{1, 1, 1});
204 
205   // Already sorted.
206   test_all_subsequences<InIter, Sent1, OutIter, Sent2>(std::array{1, 2, 3, 4, 5});
207 
208   // Descending.
209   test_all_subsequences<InIter, Sent1, OutIter, Sent2>(std::array{5, 4, 3, 2, 1});
210 }
211 
212 template <class InIter, class Sent1, class OutIter>
test_iterators_in_sent1_out()213 constexpr void test_iterators_in_sent1_out() {
214   test_iterators_in_sent1_out_sent2<InIter, Sent1, OutIter, OutIter>();
215   test_iterators_in_sent1_out_sent2<InIter, Sent1, OutIter, sentinel_wrapper<OutIter>>();
216 }
217 
218 template <class InIter, class Sent1>
test_iterators_in_sent1()219 constexpr void test_iterators_in_sent1() {
220   test_iterators_in_sent1_out<InIter, Sent1, random_access_iterator<int*>>();
221 }
222 
223 template <class InIter>
test_iterators_in()224 constexpr void test_iterators_in() {
225   if constexpr (std::sentinel_for<InIter, InIter>) {
226     test_iterators_in_sent1<InIter, InIter>();
227   }
228   test_iterators_in_sent1<InIter, sentinel_wrapper<InIter>>();
229 }
230 
test_iterators()231 constexpr void test_iterators() {
232   test_iterators_in<cpp20_input_iterator<int*>>();
233   // Omitting other iterator types to reduce the combinatorial explosion.
234   test_iterators_in<random_access_iterator<int*>>();
235   test_iterators_in<const int*>();
236 }
237 
test()238 constexpr bool test() {
239   test_iterators();
240 
241   { // A custom comparator works.
242     const std::array in = {1, 2, 3, 4, 5};
243     std::ranges::greater comp;
244 
245     {
246       std::array<int, 2> out;
247 
248       auto result = std::ranges::partial_sort_copy(in.begin(), in.end(), out.begin(), out.end(), comp);
249       assert(std::ranges::equal(std::ranges::subrange(out.begin(), result.out), std::array{5, 4}));
250     }
251 
252     {
253       std::array<int, 2> out;
254 
255       auto result = std::ranges::partial_sort_copy(in, out, comp);
256       assert(std::ranges::equal(std::ranges::subrange(out.begin(), result.out), std::array{5, 4}));
257     }
258   }
259 
260   { // A custom projection works.
261     struct A {
262       int a;
263 
264       constexpr A() = default;
265       constexpr A(int value) : a(value) {}
266       constexpr auto operator<=>(const A&) const = default;
267     };
268 
269     const std::array in = {2, 1, 3};
270     auto proj1 = [](int value) { return value * -1; };
271     auto proj2 = [](A value) { return value.a * -1; };
272     // The projections negate the argument, so the array will appear to be sorted in descending order: [3, 2, 1]
273     // (the projections make it appear to the algorithm as [-3, -2, -1]).
274 
275     {
276       std::array<A, 2> out;
277 
278       // No projections: ascending order.
279       auto result = std::ranges::partial_sort_copy(in.begin(), in.end(), out.begin(), out.end(), {});
280       assert(std::ranges::equal(std::ranges::subrange(out.begin(), result.out), std::array{1, 2}));
281       // Using projections: descending order.
282       result = std::ranges::partial_sort_copy(in.begin(), in.end(), out.begin(), out.end(), {}, proj1, proj2);
283       assert(std::ranges::equal(std::ranges::subrange(out.begin(), result.out), std::array{3, 2}));
284     }
285 
286     {
287       std::array<int, 2> out;
288 
289       auto result = std::ranges::partial_sort_copy(in, out, {});
290       assert(std::ranges::equal(std::ranges::subrange(out.begin(), result.out), std::array{1, 2}));
291       result = std::ranges::partial_sort_copy(in, out, {}, proj1, proj2);
292       assert(std::ranges::equal(std::ranges::subrange(out.begin(), result.out), std::array{3, 2}));
293     }
294   }
295 
296   return true;
297 }
298 
main(int,char **)299 int main(int, char**) {
300   test();
301   static_assert(test());
302 
303   return 0;
304 }
305