1 // Copyright 2020 The Chromium Authors
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 #include "base/ranges/algorithm.h"
6
7 #include <algorithm>
8 #include <functional>
9 #include <initializer_list>
10 #include <iterator>
11 #include <random>
12 #include <utility>
13
14 #include "base/ranges/functional.h"
15 #include "testing/gmock/include/gmock/gmock.h"
16 #include "testing/gtest/include/gtest/gtest.h"
17
18 using ::testing::ElementsAre;
19 using ::testing::Field;
20 using ::testing::Ge;
21 using ::testing::Gt;
22 using ::testing::Le;
23 using ::testing::Lt;
24 using ::testing::Pair;
25
26 namespace base {
27
28 namespace {
29
30 // A macro to work around the fact that lambdas are not constexpr in C++14.
31 // This will define an unnamed struct with a constexpr call operator, similarly
32 // to how lambdas behave in C++17+.
33 // Note that this does not support capture groups, so all lambdas defined like
34 // this must be stateless.
35 // Example Usage: `CONSTEXPR_LAMBDA((int i, int j) { return i + j; }) lambda;`
36 // TODO(crbug.com/752720): Remove once we have constexpr lambdas for real.
37 #define CONSTEXPR_LAMBDA(fun) \
38 constexpr struct { constexpr bool operator() fun }
39
40 struct Int {
41 constexpr Int() = default;
Intbase::__anon0995d6740111::Int42 constexpr Int(int value) : value(value) {}
43
44 int value = 0;
45 };
46
operator ==(Int lhs,Int rhs)47 constexpr bool operator==(Int lhs, Int rhs) {
48 return lhs.value == rhs.value;
49 }
50
operator <(Int lhs,Int rhs)51 constexpr bool operator<(Int lhs, Int rhs) {
52 return lhs.value < rhs.value;
53 }
54
operator >(Int lhs,Int rhs)55 constexpr bool operator>(Int lhs, Int rhs) {
56 return lhs.value > rhs.value;
57 }
58
operator <=(Int lhs,Int rhs)59 constexpr bool operator<=(Int lhs, Int rhs) {
60 return lhs.value <= rhs.value;
61 }
62
operator >=(Int lhs,Int rhs)63 constexpr bool operator>=(Int lhs, Int rhs) {
64 return lhs.value >= rhs.value;
65 }
66
67 // Move-only int that clears `value` when moving out.
68 struct MoveOnlyInt {
MoveOnlyIntbase::__anon0995d6740111::MoveOnlyInt69 MoveOnlyInt(int value) : value(value) {}
MoveOnlyIntbase::__anon0995d6740111::MoveOnlyInt70 MoveOnlyInt(MoveOnlyInt&& other) : value(std::exchange(other.value, 0)) {}
71
operator =base::__anon0995d6740111::MoveOnlyInt72 MoveOnlyInt& operator=(MoveOnlyInt&& other) {
73 value = std::exchange(other.value, 0);
74 return *this;
75 }
76
77 int value = 0;
78 };
79
is_even(int i)80 constexpr bool is_even(int i) {
81 return i % 2 == 0;
82 }
83
is_odd(int i)84 bool is_odd(int i) {
85 return i % 2 == 1;
86 }
87
88 template <typename Iter>
make_vector(Iter begin,Iter end)89 auto make_vector(Iter begin, Iter end) {
90 using T = typename std::iterator_traits<Iter>::value_type;
91 return std::vector<T>(begin, end);
92 }
93
94 } // namespace
95
TEST(RangesTest,AllOf)96 TEST(RangesTest, AllOf) {
97 // Note: Lambdas don't have a constexpr call operator prior to C++17, thus we
98 // are providing our own anonyomous struct here.
99 constexpr struct {
100 constexpr bool operator()(int i) { return i != 0; }
101 } is_non_zero;
102
103 constexpr int array[] = {0, 1, 2, 3, 4, 5};
104
105 static_assert(ranges::all_of(array + 1, array + 6, is_non_zero), "");
106 static_assert(!ranges::all_of(array, is_non_zero), "");
107
108 constexpr Int values[] = {0, 2, 4, 5};
109 static_assert(
110 ranges::all_of(values + 1, ranges::end(values), is_non_zero, &Int::value),
111 "");
112 static_assert(!ranges::all_of(values, is_non_zero, &Int::value), "");
113 }
114
TEST(RangesTest,AnyOf)115 TEST(RangesTest, AnyOf) {
116 constexpr int array[] = {0, 1, 2, 3, 4, 5};
117
118 static_assert(!ranges::any_of(array + 5, array + 6, is_even), "");
119 static_assert(ranges::any_of(array, is_even), "");
120
121 constexpr Int values[] = {{0}, {2}, {4}, {5}};
122 static_assert(
123 !ranges::any_of(values + 3, ranges::end(values), is_even, &Int::value),
124 "");
125 static_assert(ranges::any_of(values, is_even, &Int::value), "");
126 }
127
TEST(RangesTest,NoneOf)128 TEST(RangesTest, NoneOf) {
129 // Note: Lambdas don't have a constexpr call operator prior to C++17, thus we
130 // are providing our own anonyomous struct here.
131 constexpr struct {
132 constexpr bool operator()(int i) { return i == 0; }
133 } is_zero;
134 constexpr int array[] = {0, 1, 2, 3, 4, 5};
135
136 static_assert(ranges::none_of(array + 1, array + 6, is_zero), "");
137 static_assert(!ranges::none_of(array, is_zero), "");
138
139 constexpr Int values[] = {{0}, {2}, {4}, {5}};
140 static_assert(
141 ranges::none_of(values + 1, ranges::end(values), is_zero, &Int::value),
142 "");
143 static_assert(!ranges::none_of(values, is_zero, &Int::value), "");
144 }
145
TEST(RangesTest,ForEach)146 TEST(RangesTest, ForEach) {
147 auto times_two = [](int& i) { i *= 2; };
148 int array[] = {0, 1, 2, 3, 4, 5};
149
150 auto result = ranges::for_each(array, array + 3, times_two);
151 EXPECT_EQ(result.in, array + 3);
152 // TODO(https://crbug.com/1191256): Fix googletest and switch this back to
153 // EXPECT_EQ.
154 EXPECT_TRUE(result.fun == times_two);
155 EXPECT_THAT(array, ElementsAre(0, 2, 4, 3, 4, 5));
156
157 ranges::for_each(array + 3, array + 6, times_two);
158 EXPECT_EQ(result.in, array + 3);
159 // TODO(https://crbug.com/1191256): Fix googletest and switch this back to
160 // EXPECT_EQ.
161 EXPECT_TRUE(result.fun == times_two);
162 EXPECT_THAT(array, ElementsAre(0, 2, 4, 6, 8, 10));
163
164 // TODO(https://crbug.com/1191256): Fix googletest and switch this back to
165 // EXPECT_EQ.
166 EXPECT_TRUE(times_two == ranges::for_each(array, times_two).fun);
167 EXPECT_THAT(array, ElementsAre(0, 4, 8, 12, 16, 20));
168
169 Int values[] = {0, 2, 4, 5};
170 // TODO(https://crbug.com/1191256): Fix googletest and switch this back to
171 // EXPECT_EQ.
172 EXPECT_TRUE(times_two ==
173 ranges::for_each(values, times_two, &Int::value).fun);
174 EXPECT_THAT(values,
175 ElementsAre(Field(&Int::value, 0), Field(&Int::value, 4),
176 Field(&Int::value, 8), Field(&Int::value, 10)));
177 }
178
TEST(RangesTest,ForEachN)179 TEST(RangesTest, ForEachN) {
180 auto times_two = [](int& i) { i *= 2; };
181 int array[] = {0, 1, 2, 3, 4, 5};
182
183 auto result = ranges::for_each_n(array, 3, times_two);
184 EXPECT_EQ(result.in, array + 3);
185 // TODO(https://crbug.com/1191256): Fix googletest and switch this back to
186 // EXPECT_EQ.
187 EXPECT_TRUE(result.fun == times_two);
188 EXPECT_THAT(array, ElementsAre(0, 2, 4, 3, 4, 5));
189
190 Int values[] = {0, 2, 4, 5};
191 // TODO(https://crbug.com/1191256): Fix googletest and switch this back to
192 // EXPECT_EQ.
193 EXPECT_TRUE(times_two ==
194 ranges::for_each_n(values, 4, times_two, &Int::value).fun);
195 EXPECT_THAT(values,
196 ElementsAre(Field(&Int::value, 0), Field(&Int::value, 4),
197 Field(&Int::value, 8), Field(&Int::value, 10)));
198 }
199
TEST(RangesTest,Find)200 TEST(RangesTest, Find) {
201 constexpr int array[] = {0, 1, 2, 3, 4, 5};
202
203 static_assert(array + 6 == ranges::find(array + 1, array + 6, 0), "");
204 static_assert(array == ranges::find(array, 0), "");
205
206 constexpr Int values[] = {{0}, {2}, {4}, {5}};
207 static_assert(values == ranges::find(values, values, 0, &Int::value), "");
208 static_assert(ranges::end(values) == ranges::find(values, 3, &Int::value),
209 "");
210 }
211
TEST(RangesTest,FindIf)212 TEST(RangesTest, FindIf) {
213 auto is_at_least_5 = [](int i) { return i >= 5; };
214 int array[] = {0, 1, 2, 3, 4, 5};
215
216 EXPECT_EQ(array + 5, ranges::find_if(array, array + 5, is_at_least_5));
217 EXPECT_EQ(array + 5, ranges::find_if(array, is_at_least_5));
218
219 Int values[] = {{0}, {2}, {4}, {5}};
220 EXPECT_EQ(values + 3,
221 ranges::find_if(values, values + 3, is_odd, &Int::value));
222 EXPECT_EQ(values + 3, ranges::find_if(values, is_odd, &Int::value));
223 }
224
TEST(RangesTest,FindIfNot)225 TEST(RangesTest, FindIfNot) {
226 auto is_less_than_5 = [](int i) { return i < 5; };
227 int array[] = {0, 1, 2, 3, 4, 5};
228
229 EXPECT_EQ(array + 5, ranges::find_if_not(array, array + 5, is_less_than_5));
230 EXPECT_EQ(array + 5, ranges::find_if_not(array, is_less_than_5));
231
232 Int values[] = {{0}, {2}, {4}, {5}};
233 EXPECT_EQ(values + 3,
234 ranges::find_if_not(values, values + 3, is_even, &Int::value));
235 EXPECT_EQ(values + 3, ranges::find_if_not(values, is_even, &Int::value));
236 }
237
TEST(RangesTest,FindEnd)238 TEST(RangesTest, FindEnd) {
239 int array1[] = {0, 1, 2};
240 int array2[] = {4, 5, 6};
241 int array3[] = {0, 1, 2, 3, 4, 5, 0, 1, 2, 3, 4,
242 0, 1, 2, 3, 0, 1, 2, 0, 1, 0};
243
244 EXPECT_EQ(array3 + 15, ranges::find_end(array3, ranges::end(array3), array1,
245 ranges::end(array1)));
246 EXPECT_EQ(ranges::end(array3), ranges::find_end(array3, ranges::end(array3),
247 array2, ranges::end(array2)));
248 EXPECT_EQ(array3 + 4,
249 ranges::find_end(array3, ranges::end(array3), array2, array2 + 2));
250
251 Int ints1[] = {{0}, {1}, {2}};
252 Int ints2[] = {{4}, {5}, {6}};
253
254 EXPECT_EQ(array3 + 15, ranges::find_end(array3, ints1, ranges::equal_to{},
255 std::identity{}, &Int::value));
256 EXPECT_EQ(ranges::end(array3),
257 ranges::find_end(array3, ints2, ranges::equal_to{}, std::identity{},
258 &Int::value));
259 }
260
TEST(RangesTest,FindFirstOf)261 TEST(RangesTest, FindFirstOf) {
262 int array1[] = {1, 2, 3};
263 int array2[] = {7, 8, 9};
264 int array3[] = {0, 1, 2, 3, 4, 5, 0, 1, 2, 3};
265
266 EXPECT_EQ(array3 + 1, ranges::find_first_of(array3, ranges::end(array3),
267 array1, ranges::end(array1)));
268 EXPECT_EQ(ranges::end(array3),
269 ranges::find_first_of(array3, ranges::end(array3), array2,
270 ranges::end(array2)));
271 Int ints1[] = {{1}, {2}, {3}};
272 Int ints2[] = {{7}, {8}, {9}};
273
274 EXPECT_EQ(array3 + 1, ranges::find_first_of(array3, ints1, ranges::equal_to{},
275 std::identity{}, &Int::value));
276 EXPECT_EQ(ranges::end(array3),
277 ranges::find_first_of(array3, ints2, ranges::equal_to{},
278 std::identity{}, &Int::value));
279 }
280
TEST(RangesTest,AdjacentFind)281 TEST(RangesTest, AdjacentFind) {
282 constexpr int array[] = {1, 2, 3, 3};
283 static_assert(array + 2 == ranges::adjacent_find(array, ranges::end(array)),
284 "");
285 static_assert(
286 array == ranges::adjacent_find(array, ranges::end(array), ranges::less{}),
287 "");
288
289 constexpr Int ints[] = {{6}, {6}, {5}, {4}};
290 static_assert(
291 ints == ranges::adjacent_find(ints, ranges::equal_to{}, &Int::value), "");
292 static_assert(ranges::end(ints) ==
293 ranges::adjacent_find(ints, ranges::less{}, &Int::value),
294 "");
295 }
296
TEST(RangesTest,Count)297 TEST(RangesTest, Count) {
298 int array[] = {1, 2, 3, 3};
299 EXPECT_EQ(1, ranges::count(array, array + 4, 1));
300 EXPECT_EQ(1, ranges::count(array, array + 4, 2));
301 EXPECT_EQ(1, ranges::count(array, array + 3, 3));
302 EXPECT_EQ(2, ranges::count(array, array + 4, 3));
303
304 Int ints[] = {{1}, {2}, {3}, {3}};
305 EXPECT_EQ(1, ranges::count(ints, 1, &Int::value));
306 EXPECT_EQ(1, ranges::count(ints, 2, &Int::value));
307 EXPECT_EQ(2, ranges::count(ints, 3, &Int::value));
308 }
309
TEST(RangesTest,CountIf)310 TEST(RangesTest, CountIf) {
311 int array[] = {1, 2, 3, 3};
312 EXPECT_EQ(0, ranges::count_if(array, array + 1, is_even));
313 EXPECT_EQ(1, ranges::count_if(array, array + 2, is_even));
314 EXPECT_EQ(1, ranges::count_if(array, array + 3, is_even));
315 EXPECT_EQ(1, ranges::count_if(array, array + 4, is_even));
316
317 Int ints[] = {{1}, {2}, {3}, {3}};
318 EXPECT_EQ(1, ranges::count_if(ints, is_even, &Int::value));
319 EXPECT_EQ(3, ranges::count_if(ints, is_odd, &Int::value));
320 }
321
TEST(RangesTest,Mismatch)322 TEST(RangesTest, Mismatch) {
323 int array1[] = {1, 3, 6, 7};
324 int array2[] = {1, 3};
325 int array3[] = {1, 3, 5, 7};
326 EXPECT_EQ(std::make_pair(array1 + 2, array2 + 2),
327 ranges::mismatch(array1, array1 + 4, array2, array2 + 2));
328 EXPECT_EQ(std::make_pair(array1 + 2, array3 + 2),
329 ranges::mismatch(array1, array1 + 4, array3, array3 + 4));
330
331 EXPECT_EQ(std::make_pair(array1 + 2, array2 + 2),
332 ranges::mismatch(array1, array2));
333 EXPECT_EQ(std::make_pair(array1 + 2, array3 + 2),
334 ranges::mismatch(array1, array3));
335 }
336
TEST(RangesTest,Equal)337 TEST(RangesTest, Equal) {
338 static constexpr int array1[] = {1, 3, 6, 7};
339 static constexpr int array2[] = {1, 3, 5, 7};
340
341 static_assert(ranges::equal(array1, array1 + 2, array2, array2 + 2), "");
342 EXPECT_TRUE(ranges::equal(array1, array1 + 2, array2, array2 + 2));
343
344 static_assert(!ranges::equal(array1, array1 + 4, array2, array2 + 4), "");
345 EXPECT_FALSE(ranges::equal(array1, array1 + 4, array2, array2 + 4));
346
347 static_assert(!ranges::equal(array1, array1 + 2, array2, array2 + 3), "");
348 EXPECT_FALSE(ranges::equal(array1, array1 + 2, array2, array2 + 3));
349
350 static constexpr Int ints[] = {{1}, {3}, {5}, {7}};
351
352 CONSTEXPR_LAMBDA((Int lhs, int rhs) { return lhs.value == rhs; }) lambda;
353 static_assert(ranges::equal(ints, array2, lambda), "");
354 EXPECT_TRUE(ranges::equal(ints, array2, lambda));
355
356 static_assert(ranges::equal(array2, ints, ranges::equal_to{}, std::identity{},
357 &Int::value),
358 "");
359 EXPECT_TRUE(ranges::equal(array2, ints, ranges::equal_to{}, std::identity{},
360 &Int::value));
361 }
362
TEST(RangesTest,IsPermutation)363 TEST(RangesTest, IsPermutation) {
364 int array1[] = {1, 3, 6, 7};
365 int array2[] = {7, 3, 1, 6};
366 int array3[] = {1, 3, 5, 7};
367
368 EXPECT_TRUE(ranges::is_permutation(array1, array1 + 4, array2, array2 + 4));
369 EXPECT_FALSE(ranges::is_permutation(array1, array1 + 4, array3, array3 + 4));
370
371 EXPECT_TRUE(ranges::is_permutation(array1, array2));
372 EXPECT_FALSE(ranges::is_permutation(array1, array3));
373
374 Int ints1[] = {{1}, {3}, {5}, {7}};
375 Int ints2[] = {{1}, {5}, {3}, {7}};
376 EXPECT_TRUE(ranges::is_permutation(
377 ints1, ints2, [](Int lhs, Int rhs) { return lhs.value == rhs.value; }));
378
379 EXPECT_TRUE(
380 ranges::is_permutation(ints1, ints2, ranges::equal_to{}, &Int::value));
381
382 EXPECT_FALSE(ranges::is_permutation(array1, ints2, ranges::equal_to{}, {},
383 &Int::value));
384 EXPECT_TRUE(ranges::is_permutation(array3, ints2, ranges::equal_to{}, {},
385 &Int::value));
386 }
387
TEST(RangesTest,Search)388 TEST(RangesTest, Search) {
389 int array1[] = {0, 1, 2, 3};
390 int array2[] = {0, 1, 5, 3};
391 int array3[] = {0, 1, 2, 0, 1, 2, 3, 0, 1, 2, 3, 4};
392
393 EXPECT_EQ(array3 + 3,
394 ranges::search(array3, array3 + 12, array1, array1 + 4));
395 EXPECT_EQ(array3 + 12,
396 ranges::search(array3, array3 + 12, array2, array2 + 4));
397
398 EXPECT_EQ(array3 + 3, ranges::search(array3, array1));
399 EXPECT_EQ(array3 + 12, ranges::search(array3, array2));
400
401 Int ints1[] = {{0}, {1}, {2}, {3}};
402 Int ints2[] = {{0}, {1}, {5}, {3}};
403
404 EXPECT_EQ(ints1 + 4, ranges::search(ints1, ints2, ranges::equal_to{},
405 &Int::value, &Int::value));
406
407 EXPECT_EQ(array3 + 3, ranges::search(array3, ints1, {}, {}, &Int::value));
408 EXPECT_EQ(array3 + 12, ranges::search(array3, ints2, {}, {}, &Int::value));
409 }
410
TEST(RangesTest,SearchN)411 TEST(RangesTest, SearchN) {
412 int array[] = {0, 0, 1, 1, 2, 2};
413
414 EXPECT_EQ(array, ranges::search_n(array, array + 6, 1, 0));
415 EXPECT_EQ(array + 2, ranges::search_n(array, array + 6, 1, 1));
416 EXPECT_EQ(array + 4, ranges::search_n(array, array + 6, 1, 2));
417 EXPECT_EQ(array + 6, ranges::search_n(array, array + 6, 1, 3));
418
419 EXPECT_EQ(array, ranges::search_n(array, array + 6, 2, 0));
420 EXPECT_EQ(array + 2, ranges::search_n(array, array + 6, 2, 1));
421 EXPECT_EQ(array + 4, ranges::search_n(array, array + 6, 2, 2));
422 EXPECT_EQ(array + 6, ranges::search_n(array, array + 6, 2, 3));
423
424 EXPECT_EQ(array + 6, ranges::search_n(array, array + 6, 3, 0));
425 EXPECT_EQ(array + 6, ranges::search_n(array, array + 6, 3, 1));
426 EXPECT_EQ(array + 6, ranges::search_n(array, array + 6, 3, 2));
427 EXPECT_EQ(array + 6, ranges::search_n(array, array + 6, 3, 3));
428
429 Int ints[] = {{0}, {0}, {1}, {1}, {2}, {2}};
430 EXPECT_EQ(ints, ranges::search_n(ints, 1, 0, {}, &Int::value));
431 EXPECT_EQ(ints + 2, ranges::search_n(ints, 1, 1, {}, &Int::value));
432 EXPECT_EQ(ints + 4, ranges::search_n(ints, 1, 2, {}, &Int::value));
433 EXPECT_EQ(ints + 6, ranges::search_n(ints, 1, 3, {}, &Int::value));
434
435 EXPECT_EQ(ints, ranges::search_n(ints, 2, 0, {}, &Int::value));
436 EXPECT_EQ(ints + 2, ranges::search_n(ints, 2, 1, {}, &Int::value));
437 EXPECT_EQ(ints + 4, ranges::search_n(ints, 2, 2, {}, &Int::value));
438 EXPECT_EQ(ints + 6, ranges::search_n(ints, 2, 3, {}, &Int::value));
439
440 EXPECT_EQ(ints + 6, ranges::search_n(ints, 3, 0, {}, &Int::value));
441 EXPECT_EQ(ints + 6, ranges::search_n(ints, 3, 1, {}, &Int::value));
442 EXPECT_EQ(ints + 6, ranges::search_n(ints, 3, 2, {}, &Int::value));
443 EXPECT_EQ(ints + 6, ranges::search_n(ints, 3, 3, {}, &Int::value));
444 }
445
TEST(RangesTest,Copy)446 TEST(RangesTest, Copy) {
447 int input[] = {1, 2, 3, 4, 5};
448 int output[] = {6, 6, 6, 6, 6, 6, 6};
449 auto equals_six = [](int i) { return i == 6; };
450
451 EXPECT_EQ(output + 3, ranges::copy(input, input + 3, output));
452 EXPECT_TRUE(std::equal(input, input + 3, output, output + 3));
453 EXPECT_TRUE(std::all_of(output + 3, output + 7, equals_six));
454
455 EXPECT_EQ(output + 5, ranges::copy(input, output));
456 EXPECT_TRUE(std::equal(input, input + 5, output, output + 5));
457 EXPECT_TRUE(std::all_of(output + 5, output + 7, equals_six));
458 }
459
TEST(RangesTest,CopyN)460 TEST(RangesTest, CopyN) {
461 int input[] = {1, 2, 3, 4, 5};
462 int output[] = {6, 6, 6, 6, 6, 6, 6};
463 auto equals_six = [](int i) { return i == 6; };
464
465 EXPECT_EQ(output + 4, ranges::copy_n(input, 4, output));
466 EXPECT_TRUE(std::equal(input, input + 4, output, output + 4));
467 EXPECT_TRUE(std::all_of(output + 4, output + 7, equals_six));
468 }
469
TEST(RangesTest,CopyIf)470 TEST(RangesTest, CopyIf) {
471 int input[] = {2, 4, 6, 8, 6};
472 int output[] = {0, 0, 0, 0, 0, 0};
473 auto equals_six = [](int i) { return i == 6; };
474 auto equals_zero = [](int i) { return i == 0; };
475
476 EXPECT_EQ(output + 1, ranges::copy_if(input, input + 4, output, equals_six));
477 EXPECT_TRUE(std::all_of(output, output + 1, equals_six));
478 EXPECT_TRUE(std::all_of(output + 1, output + 6, equals_zero));
479
480 Int ints_in[] = {{2}, {4}, {6}, {8}, {6}};
481 Int ints_out[] = {{0}, {0}, {0}, {0}, {0}, {0}};
482 EXPECT_EQ(ints_out + 2,
483 ranges::copy_if(ints_in, ints_out, equals_six, &Int::value));
484
485 EXPECT_TRUE(ranges::all_of(ints_out, ints_out + 2, equals_six, &Int::value));
486 EXPECT_TRUE(
487 ranges::all_of(ints_out + 2, ints_out + 6, equals_zero, &Int::value));
488 }
489
TEST(RangesTest,CopyBackward)490 TEST(RangesTest, CopyBackward) {
491 int input[] = {2, 4, 6, 8, 6};
492 int output[] = {0, 0, 0, 0, 0, 0};
493
494 EXPECT_EQ(output + 1, ranges::copy_backward(input, input + 5, output + 6));
495 EXPECT_THAT(output, ElementsAre(0, 2, 4, 6, 8, 6));
496
497 Int ints_in[] = {{2}, {4}, {6}, {8}, {6}};
498 Int ints_out[] = {{0}, {0}, {0}, {0}, {0}, {0}};
499
500 EXPECT_EQ(ints_out, ranges::copy_backward(ints_in, ints_out + 5));
501 EXPECT_TRUE(std::equal(ints_in, ints_in + 5, ints_out, ints_out + 5,
502 [](Int i, Int j) { return i.value == j.value; }));
503 }
504
TEST(RangesTest,Move)505 TEST(RangesTest, Move) {
506 MoveOnlyInt input[] = {6, 6, 6, 6, 6};
507 MoveOnlyInt output[] = {0, 0, 0, 0, 0};
508 auto equals_zero = [](const auto& i) { return i.value == 0; };
509 auto equals_six = [](const auto& i) { return i.value == 6; };
510
511 EXPECT_EQ(output + 3, ranges::move(input, input + 3, output));
512 EXPECT_TRUE(std::all_of(input, input + 3, equals_zero));
513 EXPECT_TRUE(std::all_of(input + 3, input + 5, equals_six));
514 EXPECT_TRUE(std::all_of(output, output + 3, equals_six));
515 EXPECT_TRUE(std::all_of(output + 3, output + 5, equals_zero));
516
517 for (auto& in : input)
518 in = 6;
519
520 EXPECT_EQ(output + 5, ranges::move(input, output));
521 EXPECT_TRUE(ranges::all_of(input, equals_zero));
522 EXPECT_TRUE(ranges::all_of(output, equals_six));
523 }
524
TEST(RangesTest,MoveBackward)525 TEST(RangesTest, MoveBackward) {
526 MoveOnlyInt input[] = {6, 6, 6, 6, 6};
527 MoveOnlyInt output[] = {0, 0, 0, 0, 0};
528 auto equals_zero = [](const auto& i) { return i.value == 0; };
529 auto equals_six = [](const auto& i) { return i.value == 6; };
530
531 EXPECT_EQ(output + 2, ranges::move_backward(input, input + 3, output + 5));
532 EXPECT_TRUE(std::all_of(input, input + 3, equals_zero));
533 EXPECT_TRUE(std::all_of(input + 3, input + 5, equals_six));
534 EXPECT_TRUE(std::all_of(output, output + 2, equals_zero));
535 EXPECT_TRUE(std::all_of(output + 2, output + 5, equals_six));
536
537 for (auto& in : input)
538 in = 6;
539
540 EXPECT_EQ(output, ranges::move_backward(input, output + 5));
541 EXPECT_TRUE(ranges::all_of(input, equals_zero));
542 EXPECT_TRUE(ranges::all_of(output, equals_six));
543 }
544
TEST(RangesTest,SwapRanges)545 TEST(RangesTest, SwapRanges) {
546 int ints1[] = {0, 0, 0, 0, 0};
547 int ints2[] = {6, 6, 6, 6, 6};
548
549 // Test that swap_ranges does not exceed `last2`.
550 EXPECT_EQ(ints2 + 3, ranges::swap_ranges(ints1, ints1 + 5, ints2, ints2 + 3));
551 EXPECT_THAT(ints1, ElementsAre(6, 6, 6, 0, 0));
552 EXPECT_THAT(ints2, ElementsAre(0, 0, 0, 6, 6));
553
554 // Test that swap_ranges does not exceed `last1`.
555 EXPECT_EQ(ints2 + 3, ranges::swap_ranges(ints1, ints1 + 3, ints2, ints2 + 5));
556 EXPECT_THAT(ints1, ElementsAre(0, 0, 0, 0, 0));
557 EXPECT_THAT(ints2, ElementsAre(6, 6, 6, 6, 6));
558
559 EXPECT_EQ(ints2 + 5,
560 ranges::swap_ranges(ints1 + 3, ints1 + 5, ints2 + 3, ints2 + 5));
561 EXPECT_THAT(ints1, ElementsAre(0, 0, 0, 6, 6));
562 EXPECT_THAT(ints2, ElementsAre(6, 6, 6, 0, 0));
563
564 EXPECT_EQ(ints2 + 5, ranges::swap_ranges(ints1, ints2));
565 EXPECT_THAT(ints1, ElementsAre(6, 6, 6, 0, 0));
566 EXPECT_THAT(ints2, ElementsAre(0, 0, 0, 6, 6));
567 }
568
TEST(RangesTest,UnaryTransform)569 TEST(RangesTest, UnaryTransform) {
570 int input[] = {1, 2, 3, 4, 5};
571 auto plus_1 = [](int i) { return i + 1; };
572 auto times_2 = [](int i) { return i * 2; };
573
574 EXPECT_EQ(input + 4,
575 ranges::transform(input + 1, input + 4, input + 1, plus_1));
576 EXPECT_THAT(input, ElementsAre(1, 3, 4, 5, 5));
577
578 int output[] = {0, 0, 0, 0, 0};
579 EXPECT_EQ(output + 3,
580 ranges::transform(input + 1, input + 4, output, times_2));
581 EXPECT_THAT(output, ElementsAre(6, 8, 10, 0, 0));
582
583 Int values[] = {{0}, {2}, {4}, {5}};
584 EXPECT_EQ(values + 4,
585 ranges::transform(values, values, times_2, &Int::value));
586 EXPECT_THAT(values, ElementsAre(Int{0}, Int{4}, Int{8}, Int{10}));
587 }
588
TEST(RangesTest,BinaryTransform)589 TEST(RangesTest, BinaryTransform) {
590 int input[] = {1, 2, 3, 4, 5};
591 int output[] = {0, 0, 0, 0, 0};
592
593 EXPECT_EQ(output + 2, ranges::transform(input, input + 2, input + 3,
594 input + 5, output, std::plus<>{}));
595 EXPECT_THAT(output, ElementsAre(5, 7, 0, 0, 0));
596
597 EXPECT_EQ(output + 5,
598 ranges::transform(input, input, output, std::multiplies<>{}));
599 EXPECT_THAT(output, ElementsAre(1, 4, 9, 16, 25));
600
601 Int values[] = {{0}, {2}, {4}, {5}};
602 EXPECT_EQ(values + 4,
603 ranges::transform(values, values, values, std::minus<>{},
604 &Int::value, &Int::value));
605 EXPECT_THAT(values, ElementsAre(Int{0}, Int{0}, Int{0}, Int{0}));
606 }
607
TEST(RangesTest,Replace)608 TEST(RangesTest, Replace) {
609 int input[] = {0, 0, 0, 0, 0};
610
611 EXPECT_EQ(input + 2, ranges::replace(input, input + 2, 0, 2));
612 EXPECT_THAT(input, ElementsAre(2, 2, 0, 0, 0));
613
614 EXPECT_EQ(input + 5, ranges::replace(input, 0, 3));
615 EXPECT_THAT(input, ElementsAre(2, 2, 3, 3, 3));
616 }
617
TEST(RangesTest,ReplaceIf)618 TEST(RangesTest, ReplaceIf) {
619 int input[] = {0, 1, 2, 3, 4};
620
621 EXPECT_EQ(input + 3, ranges::replace_if(input, input + 3, is_even, 9));
622 EXPECT_THAT(input, ElementsAre(9, 1, 9, 3, 4));
623
624 EXPECT_EQ(input + 5, ranges::replace_if(input, is_odd, 0));
625 EXPECT_THAT(input, ElementsAre(0, 0, 0, 0, 4));
626
627 Int ints[] = {0, 0, 1, 1, 0};
628 EXPECT_EQ(ints + 5, ranges::replace_if(ints, is_odd, 3, &Int::value));
629 EXPECT_THAT(ints, ElementsAre(0, 0, 3, 3, 0));
630 }
631
TEST(RangesTest,ReplaceCopy)632 TEST(RangesTest, ReplaceCopy) {
633 int input[] = {0, 0, 0, 0, 0};
634 int output[] = {1, 1, 1, 1, 1};
635
636 EXPECT_EQ(input + 2, ranges::replace_copy(input, input + 2, output, 0, 2));
637 EXPECT_THAT(input, ElementsAre(0, 0, 0, 0, 0));
638 EXPECT_THAT(output, ElementsAre(2, 2, 1, 1, 1));
639
640 EXPECT_EQ(input + 5, ranges::replace_copy(input, output, 0, 3));
641 EXPECT_THAT(input, ElementsAre(0, 0, 0, 0, 0));
642 EXPECT_THAT(output, ElementsAre(3, 3, 3, 3, 3));
643 }
644
TEST(RangesTest,ReplaceCopyIf)645 TEST(RangesTest, ReplaceCopyIf) {
646 Int input[] = {0, 1, 2, 3, 4};
647 Int output[] = {0, 0, 0, 0, 0};
648
649 EXPECT_EQ(output + 3, ranges::replace_copy_if(input, input + 3, output,
650 is_even, 9, &Int::value));
651 EXPECT_THAT(input, ElementsAre(0, 1, 2, 3, 4));
652 EXPECT_THAT(output, ElementsAre(9, 1, 9, 0, 0));
653
654 EXPECT_EQ(output + 5,
655 ranges::replace_copy_if(input, output, is_odd, 0, &Int::value));
656 EXPECT_THAT(output, ElementsAre(0, 0, 2, 0, 4));
657 }
658
TEST(RangesTest,Fill)659 TEST(RangesTest, Fill) {
660 int input[] = {1, 2, 3, 4, 5};
661
662 EXPECT_EQ(input + 3, ranges::fill(input, input + 3, 0));
663 EXPECT_THAT(input, ElementsAre(0, 0, 0, 4, 5));
664
665 EXPECT_EQ(input + 5, ranges::fill(input, 1));
666 EXPECT_THAT(input, ElementsAre(1, 1, 1, 1, 1));
667 }
668
TEST(RangesTest,FillN)669 TEST(RangesTest, FillN) {
670 int input[] = {0, 0, 0, 0, 0};
671
672 EXPECT_EQ(input + 5, ranges::fill_n(input, 5, 5));
673 EXPECT_THAT(input, ElementsAre(5, 5, 5, 5, 5));
674
675 EXPECT_EQ(input + 3, ranges::fill_n(input, 3, 3));
676 EXPECT_THAT(input, ElementsAre(3, 3, 3, 5, 5));
677 }
678
TEST(RangesTest,Generate)679 TEST(RangesTest, Generate) {
680 int input[] = {0, 0, 0, 0, 0};
681
682 auto gen = [count = 0]() mutable { return ++count; };
683 EXPECT_EQ(input + 3, ranges::generate(input, input + 3, gen));
684 EXPECT_THAT(input, ElementsAre(1, 2, 3, 0, 0));
685
686 EXPECT_EQ(input + 5, ranges::generate(input, gen));
687 EXPECT_THAT(input, ElementsAre(1, 2, 3, 4, 5));
688 }
689
TEST(RangesTest,GenerateN)690 TEST(RangesTest, GenerateN) {
691 int input[] = {0, 0, 0, 0, 0};
692
693 auto gen = [count = 0]() mutable { return ++count; };
694 EXPECT_EQ(input + 4, ranges::generate_n(input, 4, gen));
695 EXPECT_THAT(input, ElementsAre(1, 2, 3, 4, 0));
696 }
697
TEST(RangesTest,Remove)698 TEST(RangesTest, Remove) {
699 int input[] = {1, 0, 1, 1, 0};
700
701 EXPECT_EQ(input + 3, ranges::remove(input + 1, input + 5, 1));
702 EXPECT_EQ(input[0], 1);
703 EXPECT_EQ(input[1], 0);
704 EXPECT_EQ(input[2], 0);
705
706 Int ints[] = {2, 2, 1, 1, 2, 2};
707 EXPECT_EQ(ints + 2, ranges::remove(ints, 2, &Int::value));
708 EXPECT_EQ(ints[0], 1);
709 EXPECT_EQ(ints[1], 1);
710 }
711
TEST(RangesTest,RemoveIf)712 TEST(RangesTest, RemoveIf) {
713 int input[] = {0, 1, 2, 3, 4};
714
715 EXPECT_EQ(input + 2, ranges::remove_if(input, input + 4, is_even));
716 EXPECT_EQ(input[0], 1);
717 EXPECT_EQ(input[1], 3);
718 EXPECT_EQ(input[4], 4);
719
720 Int ints[] = {2, 2, 1, 1, 2, 2};
721 EXPECT_EQ(ints + 2, ranges::remove_if(ints, is_even, &Int::value));
722 EXPECT_EQ(ints[0], 1);
723 EXPECT_EQ(ints[1], 1);
724 }
725
TEST(RangesTest,RemoveCopy)726 TEST(RangesTest, RemoveCopy) {
727 int input[] = {0, 1, 2, 3, 4};
728 int output[] = {0, 0, 0, 0, 0};
729
730 EXPECT_EQ(output + 1, ranges::remove_copy(input, input + 2, output, 0));
731 EXPECT_THAT(input, ElementsAre(0, 1, 2, 3, 4));
732 EXPECT_THAT(output, ElementsAre(1, 0, 0, 0, 0));
733
734 EXPECT_EQ(output + 4, ranges::remove_copy(input, output, 4));
735 EXPECT_THAT(input, ElementsAre(0, 1, 2, 3, 4));
736 EXPECT_THAT(output, ElementsAre(0, 1, 2, 3, 0));
737 }
738
TEST(RangesTest,RemovCopyIf)739 TEST(RangesTest, RemovCopyIf) {
740 Int input[] = {0, 1, 2, 3, 4};
741 Int output[] = {0, 0, 0, 0, 0};
742
743 EXPECT_EQ(output + 2, ranges::remove_copy_if(input, input + 4, output,
744 is_even, &Int::value));
745 EXPECT_THAT(input, ElementsAre(0, 1, 2, 3, 4));
746 EXPECT_THAT(output, ElementsAre(1, 3, 0, 0, 0));
747
748 EXPECT_EQ(output + 3,
749 ranges::remove_copy_if(input, output, is_odd, &Int::value));
750 EXPECT_THAT(input, ElementsAre(0, 1, 2, 3, 4));
751 EXPECT_THAT(output, ElementsAre(0, 2, 4, 0, 0));
752 }
753
TEST(RangesTest,Unique)754 TEST(RangesTest, Unique) {
755 int input[] = {0, 0, 1, 1, 2};
756
757 EXPECT_EQ(input + 2, ranges::unique(input, input + 3));
758 EXPECT_EQ(input[0], 0);
759 EXPECT_EQ(input[1], 1);
760 EXPECT_EQ(input[3], 1);
761 EXPECT_EQ(input[4], 2);
762
763 Int ints[] = {2, 2, 1, 1, 2, 2};
764 EXPECT_EQ(ints + 3, ranges::unique(ints, {}, &Int::value));
765 EXPECT_EQ(ints[0], 2);
766 EXPECT_EQ(ints[1], 1);
767 EXPECT_EQ(ints[2], 2);
768 }
769
TEST(RangesTest,UniqueCopy)770 TEST(RangesTest, UniqueCopy) {
771 Int input[] = {0, 0, 1, 2, 2};
772 Int output[] = {0, 0, 0, 0, 0};
773
774 EXPECT_EQ(output + 3,
775 ranges::unique_copy(input, input + 4, output, {}, &Int::value));
776 EXPECT_THAT(input, ElementsAre(0, 0, 1, 2, 2));
777 EXPECT_THAT(output, ElementsAre(0, 1, 2, 0, 0));
778
779 EXPECT_EQ(output + 3, ranges::unique_copy(input, output, {}, &Int::value));
780 EXPECT_THAT(input, ElementsAre(0, 0, 1, 2, 2));
781 EXPECT_THAT(output, ElementsAre(0, 1, 2, 0, 0));
782 }
783
TEST(RangesTest,Reverse)784 TEST(RangesTest, Reverse) {
785 int input[] = {0, 1, 2, 3, 4};
786
787 EXPECT_EQ(input + 4, ranges::reverse(input + 2, input + 4));
788 EXPECT_THAT(input, ElementsAre(0, 1, 3, 2, 4));
789
790 EXPECT_EQ(input + 5, ranges::reverse(input));
791 EXPECT_THAT(input, ElementsAre(4, 2, 3, 1, 0));
792 }
793
TEST(RangesTest,ReverseCopy)794 TEST(RangesTest, ReverseCopy) {
795 int input[] = {0, 1, 2, 3, 4};
796 int output[] = {0, 0, 0, 0, 0};
797
798 EXPECT_EQ(output + 2, ranges::reverse_copy(input + 2, input + 4, output));
799 EXPECT_THAT(input, ElementsAre(0, 1, 2, 3, 4));
800 EXPECT_THAT(output, ElementsAre(3, 2, 0, 0, 0));
801
802 EXPECT_EQ(output + 5, ranges::reverse_copy(input, output));
803 EXPECT_THAT(input, ElementsAre(0, 1, 2, 3, 4));
804 EXPECT_THAT(output, ElementsAre(4, 3, 2, 1, 0));
805 }
806
TEST(RangesTest,Rotate)807 TEST(RangesTest, Rotate) {
808 int input[] = {0, 1, 2, 3, 4};
809
810 EXPECT_EQ(input + 3, ranges::rotate(input + 2, input + 3, input + 4));
811 EXPECT_THAT(input, ElementsAre(0, 1, 3, 2, 4));
812
813 EXPECT_EQ(input + 3, ranges::rotate(input, input + 2));
814 EXPECT_THAT(input, ElementsAre(3, 2, 4, 0, 1));
815 }
816
TEST(RangesTest,RotateCopy)817 TEST(RangesTest, RotateCopy) {
818 int input[] = {0, 1, 2, 3, 4};
819 int output[] = {0, 0, 0, 0, 0};
820
821 EXPECT_EQ(output + 2,
822 ranges::rotate_copy(input + 2, input + 3, input + 4, output));
823 EXPECT_THAT(input, ElementsAre(0, 1, 2, 3, 4));
824 EXPECT_THAT(output, ElementsAre(3, 2, 0, 0, 0));
825
826 EXPECT_EQ(output + 5, ranges::rotate_copy(input, input + 3, output));
827 EXPECT_THAT(input, ElementsAre(0, 1, 2, 3, 4));
828 EXPECT_THAT(output, ElementsAre(3, 4, 0, 1, 2));
829 }
830
TEST(RangesTest,Shuffle)831 TEST(RangesTest, Shuffle) {
832 int input[] = {0, 1, 2, 3, 4};
833
834 // Shuffles input[2] and input[3], thus we can't be certain about their
835 // positions.
836 EXPECT_EQ(input + 4, ranges::shuffle(input + 2, input + 4,
837 std::default_random_engine()));
838 EXPECT_EQ(input[0], 0);
839 EXPECT_EQ(input[1], 1);
840 EXPECT_EQ(input[4], 4);
841 EXPECT_THAT(input, ::testing::UnorderedElementsAre(0, 1, 2, 3, 4));
842
843 EXPECT_EQ(input + 5, ranges::shuffle(input, std::default_random_engine()));
844 EXPECT_THAT(input, ::testing::UnorderedElementsAre(0, 1, 2, 3, 4));
845 }
846
TEST(RangesTest,Sort)847 TEST(RangesTest, Sort) {
848 int input[] = {3, 1, 2, 0, 4};
849 EXPECT_EQ(input + 4, ranges::sort(input, input + 4));
850 EXPECT_THAT(input, ElementsAre(0, 1, 2, 3, 4));
851
852 EXPECT_EQ(input + 5, ranges::sort(input, input + 5, ranges::greater()));
853 EXPECT_THAT(input, ElementsAre(4, 3, 2, 1, 0));
854
855 Int ints[] = {6, 7, 9, 8, 5};
856 EXPECT_EQ(ints + 5, ranges::sort(ints, {}, &Int::value));
857 EXPECT_THAT(ints, ElementsAre(5, 6, 7, 8, 9));
858
859 EXPECT_EQ(ints + 5, ranges::sort(ints, ranges::greater(), &Int::value));
860 EXPECT_THAT(ints, ElementsAre(9, 8, 7, 6, 5));
861 }
862
TEST(RangesTest,StableSort)863 TEST(RangesTest, StableSort) {
864 // Integer divide each element by 2 to check stability of elements that
865 // compare equal.
866 auto idiv2 = [](int i) { return i / 2; };
867
868 int input[] = {3, 1, 2, 0, 4};
869 EXPECT_EQ(input + 4, ranges::stable_sort(input, input + 4, {}, idiv2));
870 EXPECT_THAT(input, ElementsAre(1, 0, 3, 2, 4));
871
872 EXPECT_EQ(input + 5,
873 ranges::stable_sort(input, input + 5, ranges::greater()));
874 EXPECT_THAT(input, ElementsAre(4, 3, 2, 1, 0));
875
876 auto Idiv2 = [](Int i) { return i.value / 2; };
877 Int ints[] = {6, 7, 9, 8, 5};
878 EXPECT_EQ(ints + 5, ranges::stable_sort(ints, {}, Idiv2));
879 EXPECT_THAT(ints, ElementsAre(5, 6, 7, 9, 8));
880
881 EXPECT_EQ(ints + 5, ranges::stable_sort(ints, ranges::greater(), Idiv2));
882 EXPECT_THAT(ints, ElementsAre(9, 8, 6, 7, 5));
883 }
884
TEST(RangesTest,PartialSort)885 TEST(RangesTest, PartialSort) {
886 int input[] = {3, 1, 2, 0, 4};
887 EXPECT_EQ(input + 4, ranges::partial_sort(input, input + 2, input + 4));
888 EXPECT_EQ(input[0], 0);
889 EXPECT_EQ(input[1], 1);
890
891 EXPECT_EQ(input + 5, ranges::partial_sort(input, input + 3, input + 5,
892 ranges::greater()));
893 EXPECT_EQ(input[0], 4);
894 EXPECT_EQ(input[1], 3);
895 EXPECT_EQ(input[2], 2);
896
897 Int ints[] = {6, 7, 9, 8, 5};
898 EXPECT_EQ(ints + 5, ranges::partial_sort(ints, ints + 4, {}, &Int::value));
899 EXPECT_EQ(ints[0], 5);
900 EXPECT_EQ(ints[1], 6);
901 EXPECT_EQ(ints[2], 7);
902 EXPECT_EQ(ints[3], 8);
903
904 EXPECT_EQ(ints + 5, ranges::partial_sort(ints, ints + 3, ranges::greater(),
905 &Int::value));
906 EXPECT_EQ(ints[0], 9);
907 EXPECT_EQ(ints[1], 8);
908 EXPECT_EQ(ints[2], 7);
909 }
910
TEST(RangesTest,PartialSortCopy)911 TEST(RangesTest, PartialSortCopy) {
912 int input[] = {3, 1, 2, 0, 4};
913 int output[] = {0, 0, 0, 0, 0};
914 EXPECT_EQ(output + 2,
915 ranges::partial_sort_copy(input, input + 2, output, output + 4));
916 EXPECT_THAT(input, ElementsAre(3, 1, 2, 0, 4));
917 EXPECT_THAT(output, ElementsAre(1, 3, 0, 0, 0));
918
919 EXPECT_EQ(output + 5,
920 ranges::partial_sort_copy(input, input + 3, output + 3, output + 5,
921 ranges::greater()));
922 EXPECT_THAT(input, ElementsAre(3, 1, 2, 0, 4));
923 EXPECT_THAT(output, ElementsAre(1, 3, 0, 3, 2));
924
925 Int ints[] = {3, 1, 2, 0, 4};
926 Int outs[] = {0, 0, 0};
927 EXPECT_EQ(outs + 3, ranges::partial_sort_copy(ints, outs, {}, &Int::value,
928 &Int::value));
929 EXPECT_THAT(ints, ElementsAre(3, 1, 2, 0, 4));
930 EXPECT_THAT(outs, ElementsAre(0, 1, 2));
931
932 EXPECT_EQ(outs + 3, ranges::partial_sort_copy(ints, outs, ranges::greater(),
933 &Int::value, &Int::value));
934 EXPECT_THAT(ints, ElementsAre(3, 1, 2, 0, 4));
935 EXPECT_THAT(outs, ElementsAre(4, 3, 2));
936
937 EXPECT_EQ(outs + 3,
938 ranges::partial_sort_copy(input, outs, {}, {}, &Int::value));
939 }
940
TEST(RangesTest,IsSorted)941 TEST(RangesTest, IsSorted) {
942 constexpr int input[] = {3, 1, 2, 0, 4};
943 static_assert(ranges::is_sorted(input + 1, input + 3), "");
944 static_assert(!ranges::is_sorted(input + 1, input + 4), "");
945 static_assert(ranges::is_sorted(input, input + 2, ranges::greater()), "");
946
947 constexpr Int ints[] = {0, 1, 2, 3, 4};
948 static_assert(ranges::is_sorted(ints, {}, &Int::value), "");
949 static_assert(!ranges::is_sorted(ints, ranges::greater(), &Int::value), "");
950 }
951
TEST(RangesTest,IsSortedUntil)952 TEST(RangesTest, IsSortedUntil) {
953 constexpr int input[] = {3, 1, 2, 0, 4};
954 static_assert(input + 3 == ranges::is_sorted_until(input + 1, input + 3), "");
955 static_assert(input + 3 == ranges::is_sorted_until(input + 1, input + 4), "");
956 static_assert(
957 input + 2 == ranges::is_sorted_until(input, input + 2, ranges::greater()),
958 "");
959
960 constexpr Int ints[] = {0, 1, 2, 3, 4};
961 static_assert(ints + 5 == ranges::is_sorted_until(ints, {}, &Int::value), "");
962 static_assert(
963 ints + 1 == ranges::is_sorted_until(ints, ranges::greater(), &Int::value),
964 "");
965 }
966
TEST(RangesTest,NthElement)967 TEST(RangesTest, NthElement) {
968 int input[] = {3, 1, 2, 0, 4};
969 EXPECT_EQ(input + 5, ranges::nth_element(input, input + 2, input + 5));
970 EXPECT_THAT(input, ElementsAre(Lt(2), Lt(2), 2, Gt(2), Gt(2)));
971
972 Int ints[] = {0, 1, 2, 3, 4};
973 EXPECT_EQ(ints + 5, ranges::nth_element(ints, ints + 2, ranges::greater(),
974 &Int::value));
975 EXPECT_THAT(ints, ElementsAre(Gt(2), Gt(2), 2, Lt(2), Lt(2)));
976 }
977
TEST(RangesTest,LowerBound)978 TEST(RangesTest, LowerBound) {
979 int array[] = {0, 0, 1, 1, 2, 2};
980
981 EXPECT_EQ(array, ranges::lower_bound(array, array + 6, -1));
982 EXPECT_EQ(array, ranges::lower_bound(array, array + 6, 0));
983 EXPECT_EQ(array + 2, ranges::lower_bound(array, array + 6, 1));
984 EXPECT_EQ(array + 4, ranges::lower_bound(array, array + 6, 2));
985 EXPECT_EQ(array + 6, ranges::lower_bound(array, array + 6, 3));
986
987 Int ints[] = {0, 0, 1, 1, 2, 2};
988
989 EXPECT_EQ(ints, ranges::lower_bound(ints, -1, {}, &Int::value));
990 EXPECT_EQ(ints, ranges::lower_bound(ints, 0, {}, &Int::value));
991 EXPECT_EQ(ints + 2, ranges::lower_bound(ints, 1, {}, &Int::value));
992 EXPECT_EQ(ints + 4, ranges::lower_bound(ints, 2, {}, &Int::value));
993 EXPECT_EQ(ints + 6, ranges::lower_bound(ints, 3, {}, &Int::value));
994
995 const auto proj = [](const Int& i) { return 2 - i.value; };
996 EXPECT_EQ(ints, ranges::lower_bound(ints, 3, ranges::greater{}, proj));
997 EXPECT_EQ(ints, ranges::lower_bound(ints, 2, ranges::greater{}, proj));
998 EXPECT_EQ(ints + 2, ranges::lower_bound(ints, 1, ranges::greater{}, proj));
999 EXPECT_EQ(ints + 4, ranges::lower_bound(ints, 0, ranges::greater{}, proj));
1000 EXPECT_EQ(ints + 6, ranges::lower_bound(ints, -1, ranges::greater{}, proj));
1001 }
1002
TEST(RangesTest,UpperBound)1003 TEST(RangesTest, UpperBound) {
1004 int array[] = {0, 0, 1, 1, 2, 2};
1005
1006 EXPECT_EQ(array, ranges::upper_bound(array, array + 6, -1));
1007 EXPECT_EQ(array + 2, ranges::upper_bound(array, array + 6, 0));
1008 EXPECT_EQ(array + 4, ranges::upper_bound(array, array + 6, 1));
1009 EXPECT_EQ(array + 6, ranges::upper_bound(array, array + 6, 2));
1010 EXPECT_EQ(array + 6, ranges::upper_bound(array, array + 6, 3));
1011
1012 Int ints[] = {0, 0, 1, 1, 2, 2};
1013
1014 EXPECT_EQ(ints, ranges::upper_bound(ints, -1, {}, &Int::value));
1015 EXPECT_EQ(ints + 2, ranges::upper_bound(ints, 0, {}, &Int::value));
1016 EXPECT_EQ(ints + 4, ranges::upper_bound(ints, 1, {}, &Int::value));
1017 EXPECT_EQ(ints + 6, ranges::upper_bound(ints, 2, {}, &Int::value));
1018 EXPECT_EQ(ints + 6, ranges::upper_bound(ints, 3, {}, &Int::value));
1019
1020 const auto proj = [](const Int& i) { return 2 - i.value; };
1021 EXPECT_EQ(ints, ranges::upper_bound(ints, 3, ranges::greater{}, proj));
1022 EXPECT_EQ(ints + 2, ranges::upper_bound(ints, 2, ranges::greater{}, proj));
1023 EXPECT_EQ(ints + 4, ranges::upper_bound(ints, 1, ranges::greater{}, proj));
1024 EXPECT_EQ(ints + 6, ranges::upper_bound(ints, 0, ranges::greater{}, proj));
1025 EXPECT_EQ(ints + 6, ranges::upper_bound(ints, -1, ranges::greater{}, proj));
1026 }
1027
TEST(RangesTest,EqualRange)1028 TEST(RangesTest, EqualRange) {
1029 int array[] = {0, 0, 1, 1, 2, 2};
1030
1031 EXPECT_THAT(ranges::equal_range(array, array + 6, -1), Pair(array, array));
1032 EXPECT_THAT(ranges::equal_range(array, array + 6, 0), Pair(array, array + 2));
1033 EXPECT_THAT(ranges::equal_range(array, array + 6, 1),
1034 Pair(array + 2, array + 4));
1035 EXPECT_THAT(ranges::equal_range(array, array + 6, 2),
1036 Pair(array + 4, array + 6));
1037 EXPECT_THAT(ranges::equal_range(array, array + 6, 3),
1038 Pair(array + 6, array + 6));
1039
1040 Int ints[] = {0, 0, 1, 1, 2, 2};
1041
1042 EXPECT_THAT(ranges::equal_range(ints, -1, {}, &Int::value), Pair(ints, ints));
1043 EXPECT_THAT(ranges::equal_range(ints, 0, {}, &Int::value),
1044 Pair(ints, ints + 2));
1045 EXPECT_THAT(ranges::equal_range(ints, 1, {}, &Int::value),
1046 Pair(ints + 2, ints + 4));
1047 EXPECT_THAT(ranges::equal_range(ints, 2, {}, &Int::value),
1048 Pair(ints + 4, ints + 6));
1049 EXPECT_THAT(ranges::equal_range(ints, 3, {}, &Int::value),
1050 Pair(ints + 6, ints + 6));
1051
1052 const auto proj = [](const Int& i) { return 2 - i.value; };
1053 EXPECT_THAT(ranges::equal_range(ints, 3, ranges::greater{}, proj),
1054 Pair(ints, ints));
1055 EXPECT_THAT(ranges::equal_range(ints, 2, ranges::greater{}, proj),
1056 Pair(ints, ints + 2));
1057 EXPECT_THAT(ranges::equal_range(ints, 1, ranges::greater{}, proj),
1058 Pair(ints + 2, ints + 4));
1059 EXPECT_THAT(ranges::equal_range(ints, 0, ranges::greater{}, proj),
1060 Pair(ints + 4, ints + 6));
1061 EXPECT_THAT(ranges::equal_range(ints, -1, ranges::greater{}, proj),
1062 Pair(ints + 6, ints + 6));
1063 }
1064
TEST(RangesTest,BinarySearch)1065 TEST(RangesTest, BinarySearch) {
1066 int array[] = {0, 0, 1, 1, 2, 2};
1067
1068 EXPECT_FALSE(ranges::binary_search(array, array + 6, -1));
1069 EXPECT_TRUE(ranges::binary_search(array, array + 6, 0));
1070 EXPECT_TRUE(ranges::binary_search(array, array + 6, 1));
1071 EXPECT_TRUE(ranges::binary_search(array, array + 6, 2));
1072 EXPECT_FALSE(ranges::binary_search(array, array + 6, 3));
1073
1074 Int ints[] = {0, 0, 1, 1, 2, 2};
1075
1076 EXPECT_FALSE(ranges::binary_search(ints, -1, {}, &Int::value));
1077 EXPECT_TRUE(ranges::binary_search(ints, 0, {}, &Int::value));
1078 EXPECT_TRUE(ranges::binary_search(ints, 1, {}, &Int::value));
1079 EXPECT_TRUE(ranges::binary_search(ints, 2, {}, &Int::value));
1080 EXPECT_FALSE(ranges::binary_search(ints, 3, {}, &Int::value));
1081
1082 const auto proj = [](const Int& i) { return 2 - i.value; };
1083 EXPECT_FALSE(ranges::binary_search(ints, 3, ranges::greater{}, proj));
1084 EXPECT_TRUE(ranges::binary_search(ints, 2, ranges::greater{}, proj));
1085 EXPECT_TRUE(ranges::binary_search(ints, 1, ranges::greater{}, proj));
1086 EXPECT_TRUE(ranges::binary_search(ints, 0, ranges::greater{}, proj));
1087 EXPECT_FALSE(ranges::binary_search(ints, -1, ranges::greater{}, proj));
1088 }
1089
TEST(RangesTest,IsPartitioned)1090 TEST(RangesTest, IsPartitioned) {
1091 int input[] = {1, 3, 5, 0, 4, 2};
1092 EXPECT_TRUE(ranges::is_partitioned(input, input, is_odd));
1093 EXPECT_TRUE(ranges::is_partitioned(input, input + 6, is_odd));
1094 EXPECT_TRUE(ranges::is_partitioned(input, input, is_even));
1095 EXPECT_FALSE(ranges::is_partitioned(input, input + 6, is_even));
1096
1097 Int ints[] = {1, 0, 4, 3, 2};
1098 auto lt_2 = [](const Int& i) { return i.value < 2; };
1099 EXPECT_TRUE(ranges::is_partitioned(ints, lt_2, &Int::value));
1100 }
1101
TEST(RangesTest,Partition)1102 TEST(RangesTest, Partition) {
1103 int input[] = {3, 1, 2, 0, 4};
1104 EXPECT_EQ(input + 3, ranges::partition(input, input + 5, is_even));
1105 EXPECT_TRUE(is_even(input[0]));
1106 EXPECT_TRUE(is_even(input[1]));
1107 EXPECT_TRUE(is_even(input[2]));
1108 EXPECT_TRUE(is_odd(input[3]));
1109 EXPECT_TRUE(is_odd(input[4]));
1110
1111 Int ints[] = {6, 7, 9, 8, 5};
1112 EXPECT_EQ(ints + 3, ranges::partition(ints, is_odd, &Int::value));
1113 EXPECT_TRUE(is_odd(ints[0].value));
1114 EXPECT_TRUE(is_odd(ints[1].value));
1115 EXPECT_TRUE(is_odd(ints[2].value));
1116 EXPECT_TRUE(is_even(ints[3].value));
1117 EXPECT_TRUE(is_even(ints[4].value));
1118 }
1119
TEST(RangesTest,StablePartition)1120 TEST(RangesTest, StablePartition) {
1121 int input[] = {3, 1, 2, 0, 4};
1122 EXPECT_EQ(input + 3, ranges::stable_partition(input, input + 5, is_even));
1123 EXPECT_THAT(input, ElementsAre(2, 0, 4, 3, 1));
1124
1125 Int ints[] = {6, 7, 9, 8, 5};
1126 EXPECT_EQ(ints + 3, ranges::stable_partition(ints, is_odd, &Int::value));
1127 EXPECT_THAT(ints, ElementsAre(7, 9, 5, 6, 8));
1128 }
1129
TEST(RangesTest,PartitionCopy)1130 TEST(RangesTest, PartitionCopy) {
1131 int input[] = {3, 1, 2, 0, 4};
1132 int evens[5] = {};
1133 int odds[5] = {};
1134 EXPECT_THAT(ranges::partition_copy(input, input + 5, evens, odds, is_even),
1135 Pair(evens + 3, odds + 2));
1136 EXPECT_THAT(input, ElementsAre(3, 1, 2, 0, 4));
1137 EXPECT_THAT(evens, ElementsAre(2, 0, 4, 0, 0));
1138 EXPECT_THAT(odds, ElementsAre(3, 1, 0, 0, 0));
1139
1140 Int ints[] = {6, 7, 9, 8, 5};
1141 Int odd_ints[5] = {};
1142 Int even_ints[5] = {};
1143 EXPECT_THAT(
1144 ranges::partition_copy(ints, odd_ints, even_ints, is_odd, &Int::value),
1145 Pair(odd_ints + 3, even_ints + 2));
1146 EXPECT_THAT(ints, ElementsAre(6, 7, 9, 8, 5));
1147 EXPECT_THAT(odd_ints, ElementsAre(7, 9, 5, 0, 0));
1148 EXPECT_THAT(even_ints, ElementsAre(6, 8, 0, 0, 0));
1149 }
1150
TEST(RangesTest,PartitionPoint)1151 TEST(RangesTest, PartitionPoint) {
1152 int input[] = {1, 3, 5, 0, 4, 2};
1153 EXPECT_EQ(input, ranges::partition_point(input, input, is_odd));
1154 EXPECT_EQ(input + 3, ranges::partition_point(input, input + 6, is_odd));
1155 EXPECT_EQ(input, ranges::partition_point(input, input, is_even));
1156
1157 Int ints[] = {1, 0, 4, 3, 2};
1158 auto lt_2 = [](const Int& i) { return i.value < 2; };
1159 EXPECT_EQ(ints + 2, ranges::partition_point(ints, lt_2, &Int::value));
1160 }
1161
TEST(RangesTest,Merge)1162 TEST(RangesTest, Merge) {
1163 int input1[] = {0, 2, 4, 6, 8};
1164 int input2[] = {1, 3, 5, 7, 9};
1165 int output[10];
1166 EXPECT_EQ(output + 10,
1167 ranges::merge(input1, input1 + 5, input2, input2 + 5, output));
1168 EXPECT_THAT(output, ElementsAre(0, 1, 2, 3, 4, 5, 6, 7, 8, 9));
1169
1170 Int ints1[] = {0, 2, 4, 6, 8};
1171 Int ints2[] = {1, 3, 5, 7, 9};
1172 Int outs[10];
1173 EXPECT_EQ(outs + 10,
1174 ranges::merge(ints1, ints2, outs, {}, &Int::value, &Int::value));
1175 EXPECT_THAT(outs, ElementsAre(0, 1, 2, 3, 4, 5, 6, 7, 8, 9));
1176
1177 EXPECT_EQ(outs + 10, ranges::merge(input1, ints1, outs, {}, {}, &Int::value));
1178 EXPECT_THAT(outs, ElementsAre(0, 0, 2, 2, 4, 4, 6, 6, 8, 8));
1179
1180 EXPECT_EQ(outs + 10, ranges::merge(ints2, input2, outs, {}, &Int::value, {}));
1181 EXPECT_THAT(outs, ElementsAre(1, 1, 3, 3, 5, 5, 7, 7, 9, 9));
1182 }
1183
TEST(RangesTest,InplaceMerge)1184 TEST(RangesTest, InplaceMerge) {
1185 int input[] = {0, 2, 4, 6, 8, 1, 3, 5, 7, 9};
1186 EXPECT_EQ(input + 10, ranges::inplace_merge(input, input + 5, input + 10));
1187 EXPECT_THAT(input, ElementsAre(0, 1, 2, 3, 4, 5, 6, 7, 8, 9));
1188
1189 Int ints[] = {8, 6, 4, 2, 0, 9, 7, 5, 3, 1};
1190 EXPECT_EQ(ints + 10, ranges::inplace_merge(ints, ints + 5, ranges::greater(),
1191 &Int::value));
1192 EXPECT_THAT(ints, ElementsAre(9, 8, 7, 6, 5, 4, 3, 2, 1, 0));
1193 }
1194
TEST(RangesTest,Includes)1195 TEST(RangesTest, Includes) {
1196 int evens[] = {0, 2, 4, 6, 8};
1197 int odds[] = {1, 3, 5, 7, 9};
1198 int fours[] = {0, 4, 8};
1199
1200 EXPECT_TRUE(ranges::includes(evens, evens + 5, fours, fours + 3));
1201 EXPECT_FALSE(ranges::includes(fours, fours + 3, evens, evens + 5));
1202 EXPECT_FALSE(ranges::includes(evens, evens + 5, odds, odds + 5));
1203 EXPECT_FALSE(ranges::includes(odds, odds + 5, evens, evens + 5));
1204
1205 Int even_ints[] = {0, 2, 4, 6, 8};
1206 Int odd_ints[] = {1, 3, 5, 7, 9};
1207
1208 EXPECT_TRUE(ranges::includes(even_ints, fours, {}, &Int::value));
1209 EXPECT_FALSE(ranges::includes(fours, even_ints, {}, {}, &Int::value));
1210 EXPECT_FALSE(
1211 ranges::includes(even_ints, odd_ints, {}, &Int::value, &Int::value));
1212 EXPECT_FALSE(
1213 ranges::includes(odd_ints, even_ints, {}, &Int::value, &Int::value));
1214 }
1215
TEST(RangesTest,SetUnion)1216 TEST(RangesTest, SetUnion) {
1217 int evens[] = {0, 2, 4, 6, 8};
1218 int odds[] = {1, 3, 5, 7, 9};
1219 int fours[] = {0, 4, 8};
1220 int result[10];
1221
1222 EXPECT_EQ(result + 10,
1223 ranges::set_union(evens, evens + 5, odds, odds + 5, result));
1224 EXPECT_THAT(result, ElementsAre(0, 1, 2, 3, 4, 5, 6, 7, 8, 9));
1225
1226 EXPECT_EQ(result + 5,
1227 ranges::set_union(evens, evens + 5, fours, fours + 3, result));
1228 EXPECT_THAT(make_vector(result, result + 5), ElementsAre(0, 2, 4, 6, 8));
1229
1230 Int even_ints[] = {0, 2, 4, 6, 8};
1231 Int odd_ints[] = {1, 3, 5, 7, 9};
1232 Int result_ints[10];
1233
1234 EXPECT_EQ(result_ints + 10,
1235 ranges::set_union(even_ints, odd_ints, result_ints, {}, &Int::value,
1236 &Int::value));
1237 EXPECT_THAT(result_ints, ElementsAre(0, 1, 2, 3, 4, 5, 6, 7, 8, 9));
1238
1239 EXPECT_EQ(result_ints + 5,
1240 ranges::set_union(even_ints, fours, result_ints, {}, &Int::value));
1241 EXPECT_THAT(make_vector(result_ints, result_ints + 5),
1242 ElementsAre(0, 2, 4, 6, 8));
1243
1244 EXPECT_EQ(result_ints + 8, ranges::set_union(fours, odd_ints, result_ints, {},
1245 {}, &Int::value));
1246 EXPECT_THAT(make_vector(result_ints, result_ints + 8),
1247 ElementsAre(0, 1, 3, 4, 5, 7, 8, 9));
1248 }
1249
TEST(RangesTest,SetIntersection)1250 TEST(RangesTest, SetIntersection) {
1251 int evens[] = {0, 2, 4, 6, 8};
1252 int odds[] = {1, 3, 5, 7, 9};
1253 int fours[] = {0, 4, 8};
1254 int result[10];
1255
1256 EXPECT_EQ(result,
1257 ranges::set_intersection(evens, evens + 5, odds, odds + 5, result));
1258
1259 EXPECT_EQ(result + 3, ranges::set_intersection(evens, evens + 5, fours,
1260 fours + 3, result));
1261 EXPECT_THAT(make_vector(result, result + 3), ElementsAre(0, 4, 8));
1262
1263 Int even_ints[] = {0, 2, 4, 6, 8};
1264 Int odd_ints[] = {1, 3, 5, 7, 9};
1265 Int result_ints[10];
1266
1267 EXPECT_EQ(result_ints,
1268 ranges::set_intersection(even_ints, odd_ints, result_ints, {},
1269 &Int::value, &Int::value));
1270
1271 EXPECT_EQ(
1272 result_ints + 3,
1273 ranges::set_intersection(even_ints, fours, result_ints, {}, &Int::value));
1274 EXPECT_THAT(make_vector(result_ints, result_ints + 3), ElementsAre(0, 4, 8));
1275
1276 EXPECT_EQ(result_ints, ranges::set_intersection(fours, odd_ints, result_ints,
1277 {}, {}, &Int::value));
1278 }
1279
TEST(RangesTest,SetDifference)1280 TEST(RangesTest, SetDifference) {
1281 int evens[] = {0, 2, 4, 6, 8};
1282 int odds[] = {1, 3, 5, 7, 9};
1283 int fours[] = {0, 4, 8};
1284 int result[5];
1285
1286 EXPECT_EQ(result + 5,
1287 ranges::set_difference(evens, evens + 5, odds, odds + 5, result));
1288 EXPECT_THAT(result, ElementsAre(0, 2, 4, 6, 8));
1289
1290 EXPECT_EQ(result + 2,
1291 ranges::set_difference(evens, evens + 5, fours, fours + 3, result));
1292 EXPECT_THAT(make_vector(result, result + 2), ElementsAre(2, 6));
1293
1294 Int even_ints[] = {0, 2, 4, 6, 8};
1295 Int odd_ints[] = {1, 3, 5, 7, 9};
1296 Int result_ints[5];
1297
1298 EXPECT_EQ(result_ints + 5,
1299 ranges::set_difference(even_ints, odd_ints, result_ints, {},
1300 &Int::value, &Int::value));
1301 EXPECT_THAT(result_ints, ElementsAre(0, 2, 4, 6, 8));
1302
1303 EXPECT_EQ(
1304 result_ints + 2,
1305 ranges::set_difference(even_ints, fours, result_ints, {}, &Int::value));
1306 EXPECT_THAT(make_vector(result_ints, result_ints + 2), ElementsAre(2, 6));
1307
1308 EXPECT_EQ(result_ints + 3,
1309 ranges::set_difference(fours, odd_ints, result_ints, {}, {},
1310 &Int::value));
1311 EXPECT_THAT(make_vector(result_ints, result_ints + 3), ElementsAre(0, 4, 8));
1312 }
1313
TEST(RangesTest,SetSymmetricDifference)1314 TEST(RangesTest, SetSymmetricDifference) {
1315 int evens[] = {0, 2, 4, 6, 8};
1316 int odds[] = {1, 3, 5, 7, 9};
1317 int fours[] = {0, 4, 8};
1318 int result[10];
1319
1320 EXPECT_EQ(result + 10, ranges::set_symmetric_difference(
1321 evens, evens + 5, odds, odds + 5, result));
1322 EXPECT_THAT(result, ElementsAre(0, 1, 2, 3, 4, 5, 6, 7, 8, 9));
1323
1324 EXPECT_EQ(result + 2, ranges::set_symmetric_difference(
1325 evens, evens + 5, fours, fours + 3, result));
1326 EXPECT_THAT(make_vector(result, result + 2), ElementsAre(2, 6));
1327
1328 Int even_ints[] = {0, 2, 4, 6, 8};
1329 Int odd_ints[] = {1, 3, 5, 7, 9};
1330 Int result_ints[10];
1331
1332 EXPECT_EQ(result_ints + 10,
1333 ranges::set_symmetric_difference(even_ints, odd_ints, result_ints,
1334 {}, &Int::value, &Int::value));
1335 EXPECT_THAT(result_ints, ElementsAre(0, 1, 2, 3, 4, 5, 6, 7, 8, 9));
1336
1337 EXPECT_EQ(result_ints + 2,
1338 ranges::set_symmetric_difference(even_ints, fours, result_ints, {},
1339 &Int::value));
1340 EXPECT_THAT(make_vector(result_ints, result_ints + 2), ElementsAre(2, 6));
1341
1342 EXPECT_EQ(result_ints + 8,
1343 ranges::set_symmetric_difference(fours, odd_ints, result_ints, {},
1344 {}, &Int::value));
1345 EXPECT_THAT(make_vector(result_ints, result_ints + 8),
1346 ElementsAre(0, 1, 3, 4, 5, 7, 8, 9));
1347 }
1348
TEST(RangesTest,PushHeap)1349 TEST(RangesTest, PushHeap) {
1350 int heap[] = {6, 4, 3, 2, 1, 0, 5};
1351 EXPECT_EQ(heap + 7, ranges::push_heap(heap, heap + 7));
1352 EXPECT_THAT(heap, ElementsAre(6, Ge(4), Ge(4), Le(3), Le(3), Le(3), Le(3)));
1353
1354 Int heap_int[] = {1, 2, 3, 4, 5, 6, 0};
1355 EXPECT_EQ(heap_int + 7,
1356 ranges::push_heap(heap_int, ranges::greater(), &Int::value));
1357 EXPECT_THAT(heap_int, ElementsAre(0, 2, 1, 4, 5, 6, 3));
1358 EXPECT_THAT(heap_int,
1359 ElementsAre(0, Le(2), Le(2), Ge(3), Ge(3), Ge(3), Ge(3)));
1360 }
1361
TEST(RangesTest,PopHeap)1362 TEST(RangesTest, PopHeap) {
1363 int heap[] = {6, 5, 4, 3, 2, 1, 0};
1364 EXPECT_EQ(heap + 7, ranges::pop_heap(heap, heap + 7));
1365 EXPECT_THAT(heap, ElementsAre(5, Ge(3), Ge(3), Le(2), Le(2), Le(2), 6));
1366
1367 Int heap_int[] = {0, 1, 2, 3, 4, 5, 6};
1368 EXPECT_EQ(heap_int + 7,
1369 ranges::pop_heap(heap_int, ranges::greater(), &Int::value));
1370 EXPECT_THAT(heap_int, ElementsAre(1, Le(3), Le(3), Ge(4), Ge(4), Ge(4), 0));
1371 }
1372
TEST(RangesTest,MakeHeap)1373 TEST(RangesTest, MakeHeap) {
1374 int heap[] = {0, 1, 2, 3, 4, 5, 6};
1375 EXPECT_EQ(heap + 7, ranges::make_heap(heap, heap + 7));
1376 EXPECT_THAT(heap, ElementsAre(6, Ge(4), Ge(4), Le(3), Le(3), Le(3), Le(3)));
1377
1378 Int heap_int[] = {6, 5, 4, 3, 2, 1, 0};
1379 EXPECT_EQ(heap_int + 7,
1380 ranges::make_heap(heap_int, ranges::greater(), &Int::value));
1381 EXPECT_THAT(heap_int,
1382 ElementsAre(0, Le(2), Le(2), Ge(3), Ge(3), Ge(3), Ge(3)));
1383 }
1384
TEST(RangesTest,SortHeap)1385 TEST(RangesTest, SortHeap) {
1386 int heap[] = {6, 4, 5, 0, 1, 2, 3};
1387 EXPECT_EQ(heap + 7, ranges::sort_heap(heap, heap + 7));
1388 EXPECT_THAT(heap, ElementsAre(0, 1, 2, 3, 4, 5, 6));
1389
1390 Int heap_int[] = {0, 2, 1, 4, 3, 6, 5};
1391 EXPECT_EQ(heap_int + 7,
1392 ranges::sort_heap(heap_int, ranges::greater(), &Int::value));
1393 EXPECT_THAT(heap_int, ElementsAre(6, 5, 4, 3, 2, 1, 0));
1394 }
1395
TEST(RangesTest,IsHeap)1396 TEST(RangesTest, IsHeap) {
1397 int heap[] = {6, 4, 5, 0, 1, 2, 3};
1398 EXPECT_TRUE(ranges::is_heap(heap, heap + 7));
1399 EXPECT_FALSE(ranges::is_heap(heap, heap + 7, ranges::greater()));
1400
1401 Int heap_int[] = {0, 2, 1, 4, 3, 6, 5};
1402 EXPECT_TRUE(ranges::is_heap(heap_int, ranges::greater(), &Int::value));
1403 EXPECT_FALSE(ranges::is_heap(heap_int, {}, &Int::value));
1404 }
1405
TEST(RangesTest,IsHeapUntil)1406 TEST(RangesTest, IsHeapUntil) {
1407 int heap[] = {6, 4, 5, 0, 1, 2, 3};
1408 EXPECT_EQ(heap + 7, ranges::is_heap_until(heap, heap + 7));
1409 EXPECT_EQ(heap + 1, ranges::is_heap_until(heap, heap + 7, ranges::greater()));
1410
1411 Int heap_int[] = {0, 2, 1, 4, 3, 6, 5};
1412 EXPECT_EQ(heap_int + 7,
1413 ranges::is_heap_until(heap_int, ranges::greater(), &Int::value));
1414 EXPECT_EQ(heap_int + 1, ranges::is_heap_until(heap_int, {}, &Int::value));
1415 }
1416
TEST(RangesTest,Min)1417 TEST(RangesTest, Min) {
1418 constexpr int k1 = 1;
1419 constexpr int k2 = 2;
1420 static_assert(&ranges::min(k1, k1) == &k1, "");
1421 static_assert(&ranges::min(k1, k2) == &k1, "");
1422 static_assert(&ranges::min(k2, k1) == &k1, "");
1423 static_assert(&ranges::min(k2, k2) == &k2, "");
1424
1425 constexpr Int k3 = 3;
1426 constexpr Int k4 = 4;
1427 static_assert(&ranges::min(k3, k3, ranges::greater(), &Int::value) == &k3,
1428 "");
1429 static_assert(&ranges::min(k3, k4, ranges::greater(), &Int::value) == &k4,
1430 "");
1431 static_assert(&ranges::min(k4, k3, ranges::greater(), &Int::value) == &k4,
1432 "");
1433 static_assert(&ranges::min(k4, k4, ranges::greater(), &Int::value) == &k4,
1434 "");
1435
1436 constexpr Int array[] = {2, 6, 4, 3, 5, 1};
1437 static_assert(ranges::min({5, 3, 4, 2, 1, 6}) == 1, "");
1438 static_assert(ranges::min(array, ranges::greater(), &Int::value) == 6, "");
1439 }
1440
TEST(RangesTest,Max)1441 TEST(RangesTest, Max) {
1442 constexpr int k1 = 1;
1443 constexpr int k2 = 2;
1444 static_assert(&ranges::max(k1, k2) == &k2, "");
1445 static_assert(&ranges::max(k1, k2) == &k2, "");
1446 static_assert(&ranges::max(k2, k1) == &k2, "");
1447 static_assert(&ranges::max(k2, k1) == &k2, "");
1448
1449 constexpr Int k3 = 3;
1450 constexpr Int k4 = 4;
1451 static_assert(&ranges::max(k3, k3, ranges::greater(), &Int::value) == &k3,
1452 "");
1453 static_assert(&ranges::max(k3, k4, ranges::greater(), &Int::value) == &k3,
1454 "");
1455 static_assert(&ranges::max(k4, k3, ranges::greater(), &Int::value) == &k3,
1456 "");
1457 static_assert(&ranges::max(k4, k4, ranges::greater(), &Int::value) == &k4,
1458 "");
1459
1460 constexpr Int array[] = {2, 6, 4, 3, 5, 1};
1461 static_assert(ranges::max({5, 3, 4, 2, 1, 6}) == 6, "");
1462 static_assert(ranges::max(array, ranges::greater(), &Int::value) == 1, "");
1463 }
1464
TEST(RangesTest,Minmax)1465 TEST(RangesTest, Minmax) {
1466 constexpr int k1 = 1;
1467 constexpr int k2 = 2;
1468 static_assert(&ranges::minmax(k1, k1).first == &k1, "");
1469 static_assert(&ranges::minmax(k1, k1).second == &k1, "");
1470 static_assert(&ranges::minmax(k1, k2).first == &k1, "");
1471 static_assert(&ranges::minmax(k1, k2).second == &k2, "");
1472 static_assert(&ranges::minmax(k2, k1).first == &k1, "");
1473 static_assert(&ranges::minmax(k2, k1).second == &k2, "");
1474 static_assert(&ranges::minmax(k2, k2).first == &k2, "");
1475 static_assert(&ranges::minmax(k2, k2).second == &k2, "");
1476
1477 static constexpr Int k3 = 3;
1478 static constexpr Int k4 = 4;
1479 {
1480 constexpr auto kResult =
1481 ranges::minmax(k3, k3, ranges::greater(), &Int::value);
1482 static_assert(&kResult.first == &k3, "");
1483 static_assert(&kResult.second == &k3, "");
1484 }
1485 {
1486 constexpr auto kResult =
1487 ranges::minmax(k3, k4, ranges::greater(), &Int::value);
1488 static_assert(&kResult.first == &k4, "");
1489 static_assert(&kResult.second == &k3, "");
1490 }
1491 {
1492 constexpr auto kResult =
1493 ranges::minmax(k4, k3, ranges::greater(), &Int::value);
1494 static_assert(&kResult.first == &k4, "");
1495 static_assert(&kResult.second == &k3, "");
1496 }
1497 {
1498 constexpr auto kResult =
1499 ranges::minmax(k4, k4, ranges::greater(), &Int::value);
1500 static_assert(&kResult.first == &k4, "");
1501 static_assert(&kResult.second == &k4, "");
1502 }
1503
1504 static_assert(ranges::minmax({5, 3, 4, 2, 1, 6}).first == 1, "");
1505 static_assert(ranges::minmax({5, 3, 4, 2, 1, 6}).second == 6, "");
1506
1507 constexpr Int array[] = {2, 6, 4, 3, 5, 1};
1508 static_assert(
1509 ranges::minmax(array, ranges::greater(), &Int::value).first == 6, "");
1510 static_assert(
1511 ranges::minmax(array, ranges::greater(), &Int::value).second == 1, "");
1512 }
1513
TEST(RangesTest,MinElement)1514 TEST(RangesTest, MinElement) {
1515 constexpr int array[] = {2, 6, 4, 3, 5, 1};
1516 constexpr Int ints[] = {2, 6, 4, 3, 5, 1};
1517 static_assert(*ranges::min_element(array, array + 6) == 1, "");
1518 static_assert(*ranges::min_element(ints, ranges::greater(), &Int::value) == 6,
1519 "");
1520 }
1521
TEST(RangesTest,MaxElement)1522 TEST(RangesTest, MaxElement) {
1523 constexpr int array[] = {2, 6, 4, 3, 5, 1};
1524 constexpr Int ints[] = {2, 6, 4, 3, 5, 1};
1525 static_assert(*ranges::max_element(array, array + 6) == 6, "");
1526 static_assert(*ranges::max_element(ints, ranges::greater(), &Int::value) == 1,
1527 "");
1528 }
1529
TEST(RangesTest,MinmaxElement)1530 TEST(RangesTest, MinmaxElement) {
1531 constexpr int array[] = {2, 6, 4, 3, 5, 1};
1532 static_assert(*ranges::minmax_element(array, array + 6).first == 1, "");
1533 static_assert(*ranges::minmax_element(array, array + 6).second == 6, "");
1534
1535 constexpr Int ints[] = {2, 6, 4, 3, 5, 1};
1536 static_assert(
1537 *ranges::minmax_element(ints, ranges::greater(), &Int::value).first == 6,
1538 "");
1539 static_assert(
1540 *ranges::minmax_element(ints, ranges::greater(), &Int::value).second == 1,
1541 "");
1542 }
1543
TEST(RangesTest,Clamp)1544 TEST(RangesTest, Clamp) {
1545 constexpr int k1 = 1;
1546 constexpr int k2 = 2;
1547 constexpr int k3 = 3;
1548
1549 static_assert(&ranges::clamp(k1, k1, k1) == &k1, "");
1550 static_assert(&ranges::clamp(k1, k1, k2) == &k1, "");
1551 static_assert(&ranges::clamp(k1, k1, k3) == &k1, "");
1552 static_assert(&ranges::clamp(k1, k2, k2) == &k2, "");
1553 static_assert(&ranges::clamp(k1, k2, k3) == &k2, "");
1554 static_assert(&ranges::clamp(k1, k3, k3) == &k3, "");
1555
1556 static_assert(&ranges::clamp(k2, k1, k1) == &k1, "");
1557 static_assert(&ranges::clamp(k2, k1, k2) == &k2, "");
1558 static_assert(&ranges::clamp(k2, k1, k3) == &k2, "");
1559 static_assert(&ranges::clamp(k2, k2, k2) == &k2, "");
1560 static_assert(&ranges::clamp(k2, k2, k3) == &k2, "");
1561 static_assert(&ranges::clamp(k2, k3, k3) == &k3, "");
1562
1563 static_assert(&ranges::clamp(k3, k1, k1) == &k1, "");
1564 static_assert(&ranges::clamp(k3, k1, k2) == &k2, "");
1565 static_assert(&ranges::clamp(k3, k1, k3) == &k3, "");
1566 static_assert(&ranges::clamp(k3, k2, k2) == &k2, "");
1567 static_assert(&ranges::clamp(k3, k2, k3) == &k3, "");
1568 static_assert(&ranges::clamp(k3, k3, k3) == &k3, "");
1569
1570 constexpr Int k4 = 4;
1571 constexpr Int k5 = 5;
1572 constexpr Int k6 = 6;
1573
1574 static_assert(
1575 &ranges::clamp(k6, k6, k6, ranges::greater(), &Int::value) == &k6, "");
1576 static_assert(
1577 &ranges::clamp(k6, k6, k5, ranges::greater(), &Int::value) == &k6, "");
1578 static_assert(
1579 &ranges::clamp(k6, k6, k4, ranges::greater(), &Int::value) == &k6, "");
1580 static_assert(
1581 &ranges::clamp(k6, k5, k5, ranges::greater(), &Int::value) == &k5, "");
1582 static_assert(
1583 &ranges::clamp(k6, k5, k4, ranges::greater(), &Int::value) == &k5, "");
1584 static_assert(
1585 &ranges::clamp(k6, k4, k4, ranges::greater(), &Int::value) == &k4, "");
1586
1587 static_assert(
1588 &ranges::clamp(k5, k6, k6, ranges::greater(), &Int::value) == &k6, "");
1589 static_assert(
1590 &ranges::clamp(k5, k6, k5, ranges::greater(), &Int::value) == &k5, "");
1591 static_assert(
1592 &ranges::clamp(k5, k6, k4, ranges::greater(), &Int::value) == &k5, "");
1593 static_assert(
1594 &ranges::clamp(k5, k5, k5, ranges::greater(), &Int::value) == &k5, "");
1595 static_assert(
1596 &ranges::clamp(k5, k5, k4, ranges::greater(), &Int::value) == &k5, "");
1597 static_assert(
1598 &ranges::clamp(k5, k4, k4, ranges::greater(), &Int::value) == &k4, "");
1599
1600 static_assert(
1601 &ranges::clamp(k4, k6, k6, ranges::greater(), &Int::value) == &k6, "");
1602 static_assert(
1603 &ranges::clamp(k4, k6, k5, ranges::greater(), &Int::value) == &k5, "");
1604 static_assert(
1605 &ranges::clamp(k4, k6, k4, ranges::greater(), &Int::value) == &k4, "");
1606 static_assert(
1607 &ranges::clamp(k4, k5, k5, ranges::greater(), &Int::value) == &k5, "");
1608 static_assert(
1609 &ranges::clamp(k4, k5, k4, ranges::greater(), &Int::value) == &k4, "");
1610 static_assert(
1611 &ranges::clamp(k4, k4, k4, ranges::greater(), &Int::value) == &k4, "");
1612 }
1613
TEST(RangesTest,LexicographicalCompare)1614 TEST(RangesTest, LexicographicalCompare) {
1615 constexpr int inputs1[] = {0, 1, 2, 3, 4, 5};
1616 constexpr int inputs2[] = {0, 1, 2, 3, 5, 4};
1617 static_assert(!ranges::lexicographical_compare(inputs1, inputs1 + 6, inputs1,
1618 inputs1 + 6),
1619 "");
1620 static_assert(ranges::lexicographical_compare(inputs1, inputs1 + 6, inputs2,
1621 inputs2 + 6),
1622 "");
1623 static_assert(!ranges::lexicographical_compare(inputs2, inputs2 + 6, inputs1,
1624 inputs1 + 6),
1625 "");
1626 static_assert(!ranges::lexicographical_compare(inputs2, inputs2 + 6, inputs2,
1627 inputs2 + 6),
1628 "");
1629
1630 constexpr Int ints1[] = {0, 1, 2, 3, 4, 5};
1631 constexpr Int ints2[] = {5, 4, 3, 2, 1, 0};
1632 static_assert(
1633 !ranges::lexicographical_compare(inputs1, ints1, {}, {}, &Int::value),
1634 "");
1635 static_assert(
1636 !ranges::lexicographical_compare(ints1, inputs1, {}, &Int::value), "");
1637
1638 static_assert(
1639 !ranges::lexicographical_compare(inputs2, ints1, {}, {}, &Int::value),
1640 "");
1641 static_assert(
1642 ranges::lexicographical_compare(ints1, inputs2, {}, &Int::value), "");
1643
1644 static_assert(ranges::lexicographical_compare(ints1, ints2, {}, &Int::value,
1645 &Int::value),
1646 "");
1647 static_assert(!ranges::lexicographical_compare(ints2, ints1, {}, &Int::value,
1648 &Int::value),
1649 "");
1650
1651 static_assert(!ranges::lexicographical_compare(
1652 ints1, ints2, ranges::greater(), &Int::value, &Int::value),
1653 "");
1654 static_assert(ranges::lexicographical_compare(ints2, ints1, ranges::greater(),
1655 &Int::value, &Int::value),
1656 "");
1657
1658 using List = std::initializer_list<int>;
1659 static_assert(
1660 ranges::lexicographical_compare(List{0, 1, 2}, List{0, 1, 2, 3}), "");
1661 static_assert(
1662 !ranges::lexicographical_compare(List{0, 1, 2, 3}, List{0, 1, 2}), "");
1663 static_assert(
1664 ranges::lexicographical_compare(List{0, 1, 2, 3}, List{0, 1, 2, 4}), "");
1665 static_assert(
1666 !ranges::lexicographical_compare(List{0, 1, 2, 4}, List{0, 1, 2, 3}), "");
1667 }
1668
TEST(RangesTest,NextPermutation)1669 TEST(RangesTest, NextPermutation) {
1670 int input[] = {5, 4, 3, 2, 0, 1};
1671 EXPECT_TRUE(ranges::next_permutation(input, input + 6));
1672 EXPECT_THAT(input, ElementsAre(5, 4, 3, 2, 1, 0));
1673
1674 EXPECT_FALSE(ranges::next_permutation(input, input + 6));
1675 EXPECT_THAT(input, ElementsAre(0, 1, 2, 3, 4, 5));
1676
1677 Int ints[] = {0, 1, 2, 3, 5, 4};
1678 EXPECT_TRUE(ranges::next_permutation(ints, ranges::greater(), &Int::value));
1679 EXPECT_THAT(ints, ElementsAre(0, 1, 2, 3, 4, 5));
1680
1681 EXPECT_FALSE(ranges::next_permutation(ints, ranges::greater(), &Int::value));
1682 EXPECT_THAT(ints, ElementsAre(5, 4, 3, 2, 1, 0));
1683
1684 int bits[] = {0, 0, 1, 0, 0};
1685 EXPECT_TRUE(ranges::next_permutation(bits));
1686 EXPECT_THAT(bits, ElementsAre(0, 1, 0, 0, 0));
1687 }
1688
TEST(RangesTest,PrevPermutation)1689 TEST(RangesTest, PrevPermutation) {
1690 int input[] = {0, 1, 2, 3, 5, 4};
1691 EXPECT_TRUE(ranges::prev_permutation(input, input + 6));
1692 EXPECT_THAT(input, ElementsAre(0, 1, 2, 3, 4, 5));
1693
1694 EXPECT_FALSE(ranges::prev_permutation(input, input + 6));
1695 EXPECT_THAT(input, ElementsAre(5, 4, 3, 2, 1, 0));
1696
1697 Int ints[] = {5, 4, 3, 2, 0, 1};
1698 EXPECT_TRUE(ranges::prev_permutation(ints, ranges::greater(), &Int::value));
1699 EXPECT_THAT(ints, ElementsAre(5, 4, 3, 2, 1, 0));
1700
1701 EXPECT_FALSE(ranges::prev_permutation(ints, ranges::greater(), &Int::value));
1702 EXPECT_THAT(ints, ElementsAre(0, 1, 2, 3, 4, 5));
1703
1704 int bits[] = {0, 0, 1, 0, 0};
1705 EXPECT_TRUE(ranges::prev_permutation(bits));
1706 EXPECT_THAT(bits, ElementsAre(0, 0, 0, 1, 0));
1707 }
1708
1709 namespace internal {
1710 struct TestPair {
1711 int a;
1712 int b;
1713 };
1714 } // namespace internal
1715
1716 } // namespace base
1717