]>
Commit | Line | Data |
---|---|---|
7adcbafe | 1 | // Copyright (C) 2005-2022 Free Software Foundation, Inc. |
f5783e34 CJ |
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 | |
748086b7 | 6 | // Free Software Foundation; either version 3, or (at your option) |
f5783e34 CJ |
7 | // any later version. |
8 | ||
9 | // This library is distributed in the hope that it will be useful, | |
2328b1de | 10 | // but WITHOUT ANY WARRANTY; without even the implied warranty of |
f5783e34 CJ |
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 | |
748086b7 JJ |
15 | // with this library; see the file COPYING3. If not see |
16 | // <http://www.gnu.org/licenses/>. | |
f5783e34 | 17 | |
18a20f3f JW |
18 | // { dg-options "-DITERATIONS=5" { target simulator } } |
19 | // { dg-do run { target c++11 } } | |
8ef20cae | 20 | |
f5783e34 CJ |
21 | // 25.3.6 Heap operations [lib.alg.heap.operations] |
22 | ||
23 | #undef _GLIBCXX_CONCEPT_CHECKS | |
f5783e34 CJ |
24 | |
25 | #include <algorithm> | |
26 | #include <testsuite_hooks.h> | |
27 | #include <testsuite_iterators.h> | |
28 | #include <testsuite_rvalref.h> | |
29 | ||
8ef20cae MM |
30 | #ifndef ITERATIONS |
31 | #define ITERATIONS 9 | |
32 | #endif | |
33 | ||
f5783e34 CJ |
34 | using __gnu_test::test_container; |
35 | using __gnu_test::random_access_iterator_wrapper; | |
36 | using __gnu_test::rvalstruct; | |
37 | ||
38 | typedef test_container<rvalstruct, random_access_iterator_wrapper> container; | |
a6bda7d0 | 39 | typedef test_container<int, random_access_iterator_wrapper> container_ref; |
f5783e34 | 40 | |
f5783e34 CJ |
41 | void |
42 | check_make(int* array, int length) | |
43 | { | |
44 | rvalstruct makeheap[9]; | |
a6bda7d0 | 45 | int makeheap_ref[9]; |
f5783e34 | 46 | std::copy(array, array + length, makeheap); |
a6bda7d0 | 47 | std::copy(array, array + length, makeheap_ref); |
f5783e34 | 48 | container makecon(makeheap, makeheap + length); |
a6bda7d0 | 49 | container_ref makecon_ref(makeheap_ref, makeheap_ref + length); |
f5783e34 | 50 | std::make_heap(makecon.begin(), makecon.end()); |
a6bda7d0 PC |
51 | std::make_heap(makecon_ref.begin(), makecon_ref.end()); |
52 | for (int z = 0; z < length; ++z) | |
53 | VERIFY( makeheap[z] == makeheap_ref[z] ); | |
54 | VERIFY( std::__is_heap(makecon.begin(), makecon.end()) ); | |
55 | for (int z = 0; z < length; ++z) | |
56 | VERIFY( makeheap[z].valid ); | |
f5783e34 CJ |
57 | } |
58 | ||
59 | void | |
60 | check_pop(int* array, int length) | |
61 | { | |
62 | rvalstruct popheap[9]; | |
a6bda7d0 PC |
63 | int popheap_ref[9]; |
64 | std::copy(array, array + length, popheap); | |
65 | std::copy(array, array + length, popheap_ref); | |
f5783e34 | 66 | container popcon(popheap, popheap + length); |
a6bda7d0 | 67 | container_ref popcon_ref(popheap_ref, popheap_ref + length); |
f5783e34 | 68 | std::pop_heap(popcon.begin(), popcon.end()); |
a6bda7d0 PC |
69 | std::pop_heap(popcon_ref.begin(), popcon_ref.end()); |
70 | for (int z = 0; z < length; ++z) | |
71 | VERIFY( popheap[z] == popheap_ref[z] ); | |
72 | VERIFY( (std::__is_heap(popheap, popheap + length - 1)) ); | |
73 | for (int z = 0; z < length; ++z) | |
74 | VERIFY( popheap[z].val <= popheap[length-1].val && popheap[z].valid ); | |
f5783e34 CJ |
75 | } |
76 | ||
77 | void | |
78 | check_sort(int* array, int length) | |
79 | { | |
80 | rvalstruct sortheap[9]; | |
a6bda7d0 PC |
81 | int sortheap_ref[9]; |
82 | std::copy(array, array + length, sortheap); | |
83 | std::copy(array, array + length, sortheap_ref); | |
f5783e34 | 84 | container sortcon(sortheap, sortheap + length); |
a6bda7d0 | 85 | container_ref sortcon_ref(sortheap_ref, sortheap_ref + length); |
f5783e34 | 86 | std::sort_heap(sortcon.begin(), sortcon.end()); |
a6bda7d0 PC |
87 | std::sort_heap(sortcon_ref.begin(), sortcon_ref.end()); |
88 | for (int z = 0; z < length; ++z) | |
89 | VERIFY( sortheap[z] == sortheap_ref[z] ); | |
90 | for (int z = 0; z < length - 1; ++z) | |
91 | VERIFY( sortheap[z].val <= sortheap[z + 1].val && sortheap[z].valid ); | |
92 | VERIFY( sortheap[length - 1].valid ); | |
f5783e34 CJ |
93 | } |
94 | ||
95 | void | |
96 | check_push(int* array, int pushval, int length) | |
97 | { | |
98 | rvalstruct pushheap[10]; | |
a6bda7d0 | 99 | int pushheap_ref[10]; |
f5783e34 | 100 | std::copy(array, array + length, pushheap); |
a6bda7d0 | 101 | std::copy(array, array + length, pushheap_ref); |
f5783e34 | 102 | pushheap[length] = pushval; |
a6bda7d0 PC |
103 | pushheap_ref[length] = pushval; |
104 | container pushcon(pushheap, pushheap + length + 1); | |
105 | container_ref pushcon_ref(pushheap_ref, pushheap_ref + length + 1); | |
f5783e34 | 106 | std::push_heap(pushcon.begin(), pushcon.end()); |
a6bda7d0 PC |
107 | std::push_heap(pushcon_ref.begin(), pushcon_ref.end()); |
108 | for (int z = 0; z < length + 1; ++z) | |
109 | VERIFY( pushheap[z] == pushheap_ref[z] ); | |
110 | VERIFY( std::__is_heap(pushheap, pushheap + length + 1) ); | |
111 | for (int z = 0; z < length + 1; ++z) | |
112 | VERIFY( pushheap[z].valid ); | |
f5783e34 CJ |
113 | } |
114 | ||
f5783e34 CJ |
115 | void |
116 | test01() | |
117 | { | |
118 | int array[9]; | |
8ef20cae | 119 | for (int i = 1; i < ITERATIONS; ++i) |
f5783e34 | 120 | { |
a6bda7d0 PC |
121 | for(int z = 0; z < i; ++z) |
122 | array[z] = z; | |
123 | while (std::next_permutation(array, array + i)) | |
124 | { | |
125 | check_make(array, i); | |
126 | if (std::__is_heap(array, array + i)) | |
127 | { | |
128 | check_pop(array, i); | |
129 | check_sort(array, i); | |
130 | for (int pushval = -1; pushval <= i; ++pushval) | |
131 | check_push(array, pushval, i); | |
132 | } | |
133 | } | |
f5783e34 | 134 | } |
f5783e34 CJ |
135 | } |
136 | ||
137 | int | |
138 | main() | |
139 | { | |
140 | test01(); | |
141 | return 0; | |
142 | } |