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//   pop_heap(Iter first, Iter last, Compare comp);
16
17#include <algorithm>
18#include <functional>
19#include <cassert>
20#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
21#include <memory>
22
23struct indirect_less
24{
25    template <class P>
26    bool operator()(const P& x, const P& y)
27        {return *x < *y;}
28};
29
30#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
31
32void test(unsigned N)
33{
34    int* ia = new int [N];
35    for (int i = 0; i < N; ++i)
36        ia[i] = i;
37    std::random_shuffle(ia, ia+N);
38    std::make_heap(ia, ia+N, std::greater<int>());
39    for (int i = N; i > 0; --i)
40    {
41        std::pop_heap(ia, ia+i, std::greater<int>());
42        assert(std::is_heap(ia, ia+i-1, std::greater<int>()));
43    }
44    std::pop_heap(ia, ia, std::greater<int>());
45    delete [] ia;
46}
47
48int main()
49{
50    test(1000);
51
52#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
53    {
54    const int N = 1000;
55    std::unique_ptr<int>* ia = new std::unique_ptr<int> [N];
56    for (int i = 0; i < N; ++i)
57        ia[i].reset(new int(i));
58    std::random_shuffle(ia, ia+N);
59    std::make_heap(ia, ia+N, indirect_less());
60    for (int i = N; i > 0; --i)
61    {
62        std::pop_heap(ia, ia+i, indirect_less());
63        assert(std::is_heap(ia, ia+i-1, indirect_less()));
64    }
65    delete [] ia;
66    }
67#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
68}
69