1// Copyright (C) 2013-2015 Free Software Foundation, Inc. 2// 3// This file is part of the GNU ISO C++ Library. This library is free 4// software; you can redistribute it and/or modify it under the 5// terms of the GNU General Public License as published by the 6// Free Software Foundation; either version 3, or (at your option) 7// any later version. 8 9// This library is distributed in the hope that it will be useful, 10// but WITHOUT ANY WARRANTY; without even the implied warranty of 11// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 12// GNU General Public License for more details. 13 14// You should have received a copy of the GNU General Public License along 15// with this library; see the file COPYING3. If not see 16// <http://www.gnu.org/licenses/>. 17 18// 25.3.6 Heap operations [lib.alg.heap.operations] 19 20#include <iterator> 21#include <vector> 22#include <algorithm> 23#include <testsuite_hooks.h> 24 25const bool A[] = { true, true, false, true, false, false, true, false }; 26const int B[] = { false, false, false, false, true, true, true, true }; 27const int C[] = { true, true, true, true, false, false, false, false }; 28const int N = sizeof(A) / sizeof(bool); 29 30// This functor has the equivalent functionality of std::greater<>, 31// but there is no dependency on <functional> and it also tracks the 32// number of invocations since creation. 33class Gt 34{ 35public: 36 static int count() { return _S_count; } 37 static void reset() { _S_count = 0; } 38 39 bool 40 operator()(bool x, bool y) const 41 { 42 ++_S_count; 43 return x > y; 44 } 45 46private: 47 static int _S_count; 48}; 49 50int Gt::_S_count = 0; 51 52// Exercise all of the heap functions for operator<. The intermediate 53// results between push_heap and pop_heap and make_heap and sort_heap 54// are not checked (they could be). 55void 56test01() 57{ 58 bool test __attribute__((unused)) = true; 59 60 // sort array s1 using push_heap/pop_heap 61 std::vector<bool> s1; 62 std::copy(A, A + N, std::back_inserter(s1)); 63 VERIFY( std::equal(s1.begin(), s1.begin() + N, A) ); 64 65 for (int i = 2; i <= N; ++i) 66 std::push_heap(s1.begin(), s1.begin() + i); 67 68 for (int i = N; i >= 2; --i) 69 std::pop_heap(s1.begin(), s1.begin() + i); 70 71 VERIFY( std::equal(s1.begin(), s1.begin() + N, B) ); 72 73 // sort array s2 using make_heap/sort_heap 74 std::vector<bool> s2; 75 std::copy(A, A + N, std::back_inserter(s2)); 76 VERIFY( std::equal(s2.begin(), s2.begin() + N, A) ); 77 78 std::make_heap(s2.begin(), s2.begin() + N); 79 std::sort_heap(s2.begin(), s2.begin() + N); 80 VERIFY( std::equal(s2.begin(), s2.begin() + N, B) ); 81} 82 83// Perform same tests as above but with the comparison predicate 84// versions, and add complexity constraint checks. 85void 86test02() 87{ 88 bool test __attribute__((unused)) = true; 89 90 Gt gt; 91 92#ifndef _GLIBCXX_DEBUG 93 //const int logN = static_cast<int>(std::log(static_cast<double>(N)) + 0.5); 94 const int logN = 3; 95#endif 96 97 std::vector<bool> s1; 98 std::copy(A, A + N, std::back_inserter(s1)); 99 VERIFY(std::equal(s1.begin(), s1.begin() + N, A)); 100 101 for (int i = 2; i <= N; ++i) 102 { 103 std::push_heap(s1.begin(), s1.begin() + i, gt); 104#ifndef _GLIBCXX_DEBUG 105 VERIFY(gt.count() <= logN); 106#endif 107 gt.reset(); 108 } 109 110 for (int i = N; i >= 2; --i) 111 { 112 std::pop_heap(s1.begin(), s1.begin() + i, gt); 113#ifndef _GLIBCXX_DEBUG 114 VERIFY(gt.count() <= 2 * logN); 115#endif 116 gt.reset(); 117 } 118 119 VERIFY(std::equal(s1.begin(), s1.begin() + N, C)); 120 121 // sort array s2 using make_heap/sort_heap 122 std::vector<bool> s2; 123 std::copy(A, A + N, std::back_inserter(s2)); 124 VERIFY(std::equal(s2.begin(), s2.begin() + N, A)); 125 126 std::make_heap(s2.begin(), s2.begin() + N, gt); 127#ifndef _GLIBCXX_DEBUG 128 VERIFY(gt.count() <= 3 * N); 129#endif 130 gt.reset(); 131 132 std::sort_heap(s2.begin(), s2.begin() + N, gt); 133#ifndef _GLIBCXX_DEBUG 134 VERIFY(gt.count() <= N * logN); 135#endif 136 137 VERIFY(std::equal(s2.begin(), s2.begin() + N, C)); 138} 139 140int 141main() 142{ 143 test01(); 144 test02(); 145 return 0; 146} 147