1 //===----------------------------------------------------------------------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is dual licensed under the MIT and the University of Illinois Open
6 // Source Licenses. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9
10 // <algorithm>
11
12 // template<class T, class Compare>
13 // pair<T, T>
14 // minmax(initializer_list<T> t, Compare comp);
15 //
16 // Complexity: At most (3/2) * t.size() applications of the corresponding predicate.
17
18 #include <algorithm>
19 #include <functional>
20 #include <cassert>
21
22 #include "counting_predicates.hpp"
23
all_equal(int a,int b)24 bool all_equal(int a, int b) { return false; } // everything is equal
25
26 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
test_all_equal(std::initializer_list<int> il)27 void test_all_equal(std::initializer_list<int> il)
28 {
29 binary_counting_predicate<bool(*)(int, int), int, int> pred (all_equal);
30 std::pair<int, int> p = std::minmax(il, std::ref(pred));
31 const int *ptr = il.end();
32 assert(p.first == *il.begin());
33 assert(p.second == *--ptr);
34 assert(pred.count() <= ((3 * il.size()) / 2));
35 }
36 #endif
37
main()38 int main()
39 {
40 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
41 assert((std::minmax({1, 2, 3}, std::greater<int>()) == std::pair<int, int>(3, 1)));
42 assert((std::minmax({1, 3, 2}, std::greater<int>()) == std::pair<int, int>(3, 1)));
43 assert((std::minmax({2, 1, 3}, std::greater<int>()) == std::pair<int, int>(3, 1)));
44 assert((std::minmax({2, 3, 1}, std::greater<int>()) == std::pair<int, int>(3, 1)));
45 assert((std::minmax({3, 1, 2}, std::greater<int>()) == std::pair<int, int>(3, 1)));
46 assert((std::minmax({3, 2, 1}, std::greater<int>()) == std::pair<int, int>(3, 1)));
47 assert((std::minmax({1, 2, 3}, all_equal ) == std::pair<int, int>(1, 3)));
48
49 binary_counting_predicate<std::greater<int>, int, int> pred ((std::greater<int>()));
50 assert((std::minmax({1, 2, 2, 3, 3, 3, 5, 5, 5, 5, 5, 3}, std::ref(pred)) == std::pair<int, int>(5, 1)));
51 assert(pred.count() <= 18); // size == 12
52
53 test_all_equal({0});
54 test_all_equal({0,1});
55 test_all_equal({0,1,2});
56 test_all_equal({0,1,2,3});
57 test_all_equal({0,1,2,3,4});
58 test_all_equal({0,1,2,3,4,5});
59 test_all_equal({0,1,2,3,4,5,6});
60 test_all_equal({0,1,2,3,4,5,6,7});
61 test_all_equal({0,1,2,3,4,5,6,7,8});
62 test_all_equal({0,1,2,3,4,5,6,7,8,9});
63 test_all_equal({0,1,2,3,4,5,6,7,8,9,10});
64 test_all_equal({0,1,2,3,4,5,6,7,8,9,10,11});
65
66 #if _LIBCPP_STD_VER > 11
67 {
68 static_assert((std::minmax({1, 2, 3}, std::greater<int>()) == std::pair<int, int>(3, 1)), "");
69 static_assert((std::minmax({1, 3, 2}, std::greater<int>()) == std::pair<int, int>(3, 1)), "");
70 static_assert((std::minmax({2, 1, 3}, std::greater<int>()) == std::pair<int, int>(3, 1)), "");
71 static_assert((std::minmax({2, 3, 1}, std::greater<int>()) == std::pair<int, int>(3, 1)), "");
72 static_assert((std::minmax({3, 1, 2}, std::greater<int>()) == std::pair<int, int>(3, 1)), "");
73 static_assert((std::minmax({3, 2, 1}, std::greater<int>()) == std::pair<int, int>(3, 1)), "");
74 }
75 #endif
76 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
77 }
78