1 // Copyright (C) 2013-2020 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
25 const bool A[] = { true, true, false, true, false, false, true, false };
26 const int B[] = { false, false, false, false, true, true, true, true };
27 const int C[] = { true, true, true, true, false, false, false, false };
28 const 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.
33 class Gt
34 {
35 public:
36 static int count() { return _S_count; }
37 static void reset() { _S_count = 0; }
38
39 bool
40 operator()(bool x, bool y) const
are_ordered(const rvalstruct & lhs,const rvalstruct & rhs)41 {
42 ++_S_count;
43 return x > y;
44 }
45
46 private:
47 static int _S_count;
check_make(int * array,int length)48 };
49
50 int 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).
55 void
56 test01()
57 {
58 // sort array s1 using push_heap/pop_heap
59 std::vector<bool> s1;
60 std::copy(A, A + N, std::back_inserter(s1));
61 VERIFY( std::equal(s1.begin(), s1.begin() + N, A) );
62
63 for (int i = 2; i <= N; ++i)
64 std::push_heap(s1.begin(), s1.begin() + i);
65
check_pop(int * array,int length)66 for (int i = N; i >= 2; --i)
67 std::pop_heap(s1.begin(), s1.begin() + i);
68
69 VERIFY( std::equal(s1.begin(), s1.begin() + N, B) );
70
71 // sort array s2 using make_heap/sort_heap
72 std::vector<bool> s2;
73 std::copy(A, A + N, std::back_inserter(s2));
74 VERIFY( std::equal(s2.begin(), s2.begin() + N, A) );
75
76 std::make_heap(s2.begin(), s2.begin() + N);
77 std::sort_heap(s2.begin(), s2.begin() + N);
78 VERIFY( std::equal(s2.begin(), s2.begin() + N, B) );
79 }
80
81 // Perform same tests as above but with the comparison predicate
82 // versions, and add complexity constraint checks.
83 void
check_sort(int * array,int length)84 test02()
85 {
86 Gt gt;
87
88 #ifndef _GLIBCXX_DEBUG
89 //const int logN = static_cast<int>(std::log(static_cast<double>(N)) + 0.5);
90 const int logN = 3;
91 #endif
92
93 std::vector<bool> s1;
94 std::copy(A, A + N, std::back_inserter(s1));
95 VERIFY(std::equal(s1.begin(), s1.begin() + N, A));
96
97 for (int i = 2; i <= N; ++i)
98 {
99 std::push_heap(s1.begin(), s1.begin() + i, gt);
100 #ifndef _GLIBCXX_DEBUG
101 VERIFY(gt.count() <= logN);
102 #endif
103 gt.reset();
104 }
105
106 for (int i = N; i >= 2; --i)
107 {
108 std::pop_heap(s1.begin(), s1.begin() + i, gt);
109 #ifndef _GLIBCXX_DEBUG
110 VERIFY(gt.count() <= 2 * logN);
111 #endif
112 gt.reset();
113 }
114
115 VERIFY(std::equal(s1.begin(), s1.begin() + N, C));
116
117 // sort array s2 using make_heap/sort_heap
118 std::vector<bool> s2;
119 std::copy(A, A + N, std::back_inserter(s2));
120 VERIFY(std::equal(s2.begin(), s2.begin() + N, A));
121
122 std::make_heap(s2.begin(), s2.begin() + N, gt);
123 #ifndef _GLIBCXX_DEBUG
124 VERIFY(gt.count() <= 3 * N);
125 #endif
126 gt.reset();
127
128 std::sort_heap(s2.begin(), s2.begin() + N, gt);
129 #ifndef _GLIBCXX_DEBUG
130 VERIFY(gt.count() <= N * logN);
131 #endif
132
133 VERIFY(std::equal(s2.begin(), s2.begin() + N, C));
134 }
135
136 int
137 main()
138 {
139 test01();
140 test02();
141 return 0;
142 }
143