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 <memory> 20 #include <random> 21 #include <cassert> 22 23 #include "test_macros.h" 24 #include "counting_predicates.hpp" 25 26 struct indirect_less 27 { 28 template <class P> 29 bool operator()(const P& x, const P& y) 30 {return *x < *y;} 31 }; 32 33 std::mt19937 randomness; 34 35 void test(int N) 36 { 37 int* ia = new int [N]; 38 { 39 for (int i = 0; i < N; ++i) 40 ia[i] = i; 41 std::shuffle(ia, ia+N, randomness); 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() <= 3u*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() <= 3u*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::shuffle(ia, ia+N, randomness); 70 std::make_heap(ia, ia+N, std::ref(pred)); 71 assert(pred.count() <= 3u*N); 72 assert(std::is_heap(ia, ia+N, pred)); 73 } 74 75 delete [] ia; 76 } 77 78 int 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 #if TEST_STD_VER >= 11 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::shuffle(ia, ia+N, randomness); 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 101 } 102
