1 // Copyright (C) 2009-2016 Free Software Foundation, Inc.
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)
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.
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/>.
18 // { dg-options "-DITERATIONS=5" { target simulator } }
19 // { dg-do run { target c++11 } }
21 // 25.3.6 Heap operations [lib.alg.heap.operations]
23 #undef _GLIBCXX_CONCEPT_CHECKS
26 #include <testsuite_hooks.h>
27 #include <testsuite_iterators.h>
28 #include <testsuite_rvalref.h>
34 using __gnu_test::test_container
;
35 using __gnu_test::random_access_iterator_wrapper
;
36 using __gnu_test::rvalstruct
;
38 typedef test_container
<rvalstruct
, random_access_iterator_wrapper
> container
;
39 typedef test_container
<int, random_access_iterator_wrapper
> container_ref
;
41 bool are_ordered(const rvalstruct
& lhs
, const rvalstruct
& rhs
)
44 bool are_ordered_int(const int& lhs
, const int& rhs
)
48 check_make(int* array
, int length
)
50 bool test
__attribute__((unused
)) = true;
52 rvalstruct makeheap
[9];
54 std::copy(array
, array
+ length
, makeheap
);
55 std::copy(array
, array
+ length
, makeheap_ref
);
56 container
makecon(makeheap
, makeheap
+ length
);
57 container_ref
makecon_ref(makeheap_ref
, makeheap_ref
+ length
);
58 std::make_heap(makecon
.begin(), makecon
.end(), are_ordered
);
59 std::make_heap(makecon_ref
.begin(), makecon_ref
.end(), are_ordered_int
);
60 for (int z
= 0; z
< length
; ++z
)
61 VERIFY( makeheap
[z
] == makeheap_ref
[z
] );
62 VERIFY( std::__is_heap(makecon
.begin(), makecon
.end(), are_ordered
) );
63 for (int z
= 0; z
< length
; ++z
)
64 VERIFY( makeheap
[z
].valid
);
68 check_pop(int* array
, int length
)
70 bool test
__attribute__((unused
)) = true;
72 rvalstruct popheap
[9];
74 std::copy(array
, array
+ length
, popheap
);
75 std::copy(array
, array
+ length
, popheap_ref
);
76 container
popcon(popheap
, popheap
+ length
);
77 container_ref
popcon_ref(popheap_ref
, popheap_ref
+ length
);
78 std::pop_heap(popcon
.begin(), popcon
.end(), are_ordered
);
79 std::pop_heap(popcon_ref
.begin(), popcon_ref
.end(), are_ordered_int
);
80 for (int z
= 0; z
< length
; ++z
)
81 VERIFY( popheap
[z
] == popheap_ref
[z
] );
82 VERIFY( (std::__is_heap(popheap
, popheap
+ length
- 1), are_ordered
) );
83 for (int z
= 0; z
< length
; ++z
)
84 VERIFY( popheap
[z
].val
<= popheap
[length
-1].val
&& popheap
[z
].valid
);
88 check_sort(int* array
, int length
)
90 bool test
__attribute__((unused
)) = true;
92 rvalstruct sortheap
[9];
94 std::copy(array
, array
+ length
, sortheap
);
95 std::copy(array
, array
+ length
, sortheap_ref
);
96 container
sortcon(sortheap
, sortheap
+ length
);
97 container_ref
sortcon_ref(sortheap_ref
, sortheap_ref
+ length
);
98 std::sort_heap(sortcon
.begin(), sortcon
.end(), are_ordered
);
99 std::sort_heap(sortcon_ref
.begin(), sortcon_ref
.end(), are_ordered_int
);
100 for (int z
= 0; z
< length
; ++z
)
101 VERIFY( sortheap
[z
] == sortheap_ref
[z
] );
102 for (int z
= 0; z
< length
- 1; ++z
)
103 VERIFY( sortheap
[z
].val
<= sortheap
[z
+ 1].val
&& sortheap
[z
].valid
);
104 VERIFY( sortheap
[length
- 1].valid
);
108 check_push(int* array
, int pushval
, int length
)
110 bool test
__attribute__((unused
)) = true;
112 rvalstruct pushheap
[10];
113 int pushheap_ref
[10];
114 std::copy(array
, array
+ length
, pushheap
);
115 std::copy(array
, array
+ length
, pushheap_ref
);
116 pushheap
[length
] = pushval
;
117 pushheap_ref
[length
] = pushval
;
118 container
pushcon(pushheap
, pushheap
+ length
+ 1);
119 container_ref
pushcon_ref(pushheap_ref
, pushheap_ref
+ length
+ 1);
120 std::push_heap(pushcon
.begin(), pushcon
.end(), are_ordered
);
121 std::push_heap(pushcon_ref
.begin(), pushcon_ref
.end(), are_ordered_int
);
122 for (int z
= 0; z
< length
+ 1; ++z
)
123 VERIFY( pushheap
[z
] == pushheap_ref
[z
] );
124 VERIFY( std::__is_heap(pushheap
, pushheap
+ length
+ 1) );
125 for (int z
= 0; z
< length
+ 1; ++z
)
126 VERIFY( pushheap
[z
].valid
);
133 for (int i
= 1; i
< ITERATIONS
; ++i
)
135 for(int z
= 0; z
< i
; ++z
)
137 while (std::next_permutation(array
, array
+ i
))
139 check_make(array
, i
);
140 if (std::__is_heap(array
, array
+ i
, are_ordered_int
))
143 check_sort(array
, i
);
144 for (int pushval
= -1; pushval
<= i
; ++pushval
)
145 check_push(array
, pushval
, i
);