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<RandomAccessIterator Iter, StrictWeakOrder<auto, Iter::value_type> Compare>
13//   requires ShuffleIterator<Iter> && CopyConstructible<Compare>
14//   void
15//   make_heap(Iter first, Iter last, Compare comp);
16
17#include <algorithm>
18#include <functional>
19#include <cassert>
20
21#include "counting_predicates.hpp"
22
23#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
24#include <memory>
25
26struct indirect_less
27{
28    template <class P>
29    bool operator()(const P& x, const P& y)
30        {return *x < *y;}
31};
32
33#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
34
35void test(unsigned N)
36{
37    int* ia = new int [N];
38    {
39    for (int i = 0; i < N; ++i)
40        ia[i] = i;
41    std::random_shuffle(ia, ia+N);
42    std::make_heap(ia, ia+N, std::greater<int>());
43    assert(std::is_heap(ia, ia+N, std::greater<int>()));
44    }
45
46//  Ascending
47    {
48    binary_counting_predicate<std::greater<int>, int, int> pred ((std::greater<int>()));
49    for (int i = 0; i < N; ++i)
50        ia[i] = i;
51    std::make_heap(ia, ia+N, std::ref(pred));
52    assert(pred.count() <= 3*N);
53    assert(std::is_heap(ia, ia+N, pred));
54    }
55
56//  Descending
57    {
58    binary_counting_predicate<std::greater<int>, int, int> pred ((std::greater<int>()));
59    for (int i = 0; i < N; ++i)
60        ia[N-1-i] = i;
61    std::make_heap(ia, ia+N, std::ref(pred));
62    assert(pred.count() <= 3*N);
63    assert(std::is_heap(ia, ia+N, pred));
64    }
65
66//  Random
67    {
68    binary_counting_predicate<std::greater<int>, int, int> pred ((std::greater<int>()));
69    std::random_shuffle(ia, ia+N);
70    std::make_heap(ia, ia+N, std::ref(pred));
71    assert(pred.count() <= 3*N);
72    assert(std::is_heap(ia, ia+N, pred));
73    }
74
75    delete [] ia;
76}
77
78int main()
79{
80    test(0);
81    test(1);
82    test(2);
83    test(3);
84    test(10);
85    test(1000);
86    test(10000);
87    test(100000);
88
89#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
90    {
91    const int N = 1000;
92    std::unique_ptr<int>* ia = new std::unique_ptr<int> [N];
93    for (int i = 0; i < N; ++i)
94        ia[i].reset(new int(i));
95    std::random_shuffle(ia, ia+N);
96    std::make_heap(ia, ia+N, indirect_less());
97    assert(std::is_heap(ia, ia+N, indirect_less()));
98    delete [] ia;
99    }
100#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
101}
102