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// UNSUPPORTED: c++98, c++03
11
12// <algorithm>
13
14// template<class T, class Compare>
15//   pair<T, T>
16//   minmax(initializer_list<T> t, Compare comp);
17//
18//  Complexity: At most (3/2) * t.size() applications of the corresponding predicate.
19
20#include <algorithm>
21#include <functional>
22#include <cassert>
23
24#include "test_macros.h"
25#include "counting_predicates.hpp"
26
27bool all_equal(int, int) { return false; } // everything is equal
28
29void test_all_equal(std::initializer_list<int> il)
30{
31    binary_counting_predicate<bool(*)(int, int), int, int> pred (all_equal);
32    std::pair<int, int> p = std::minmax(il, std::ref(pred));
33    const int *ptr = il.end();
34    assert(p.first == *il.begin());
35    assert(p.second == *--ptr);
36    assert(pred.count() <= ((3 * il.size()) / 2));
37}
38
39int main()
40{
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 TEST_STD_VER >= 14
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}
77