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