1 // { dg-options "-std=gnu++0x" }
3 // Copyright (C) 2009 Free Software Foundation, Inc.
5 // This file is part of the GNU ISO C++ Library. This library is free
6 // software; you can redistribute it and/or modify it under the
7 // terms of the GNU General Public License as published by the
8 // Free Software Foundation; either version 3, or (at your option)
11 // This library is distributed in the hope that it will be useful,
12 // but WITHOUT ANY WARRANTY; without Pred the implied warranty of
13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 // GNU General Public License for more details.
16 // You should have received a copy of the GNU General Public License along
17 // with this library; see the file COPYING3. If not see
18 // <http://www.gnu.org/licenses/>.
20 // { dg-options "-std=gnu++0x -DITERATIONS=5" { target simulator } }
22 // 25.3.6 Heap operations [lib.alg.heap.operations]
24 #undef _GLIBCXX_CONCEPT_CHECKS
27 #include <testsuite_hooks.h>
28 #include <testsuite_iterators.h>
29 #include <testsuite_rvalref.h>
35 using __gnu_test::test_container
;
36 using __gnu_test::random_access_iterator_wrapper
;
37 using __gnu_test::rvalstruct
;
39 typedef test_container
<rvalstruct
, random_access_iterator_wrapper
> container
;
40 typedef test_container
<int, random_access_iterator_wrapper
> container_ref
;
42 bool are_ordered(const rvalstruct
& lhs
, const rvalstruct
& rhs
)
45 bool are_ordered_int(const int& lhs
, const int& rhs
)
49 check_make(int* array
, int length
)
51 bool test
__attribute__((unused
)) = true;
53 rvalstruct makeheap
[9];
55 std::copy(array
, array
+ length
, makeheap
);
56 std::copy(array
, array
+ length
, makeheap_ref
);
57 container
makecon(makeheap
, makeheap
+ length
);
58 container_ref
makecon_ref(makeheap_ref
, makeheap_ref
+ length
);
59 std::make_heap(makecon
.begin(), makecon
.end(), are_ordered
);
60 std::make_heap(makecon_ref
.begin(), makecon_ref
.end(), are_ordered_int
);
61 for (int z
= 0; z
< length
; ++z
)
62 VERIFY( makeheap
[z
] == makeheap_ref
[z
] );
63 VERIFY( std::__is_heap(makecon
.begin(), makecon
.end(), are_ordered
) );
64 for (int z
= 0; z
< length
; ++z
)
65 VERIFY( makeheap
[z
].valid
);
69 check_pop(int* array
, int length
)
71 bool test
__attribute__((unused
)) = true;
73 rvalstruct popheap
[9];
75 std::copy(array
, array
+ length
, popheap
);
76 std::copy(array
, array
+ length
, popheap_ref
);
77 container
popcon(popheap
, popheap
+ length
);
78 container_ref
popcon_ref(popheap_ref
, popheap_ref
+ length
);
79 std::pop_heap(popcon
.begin(), popcon
.end(), are_ordered
);
80 std::pop_heap(popcon_ref
.begin(), popcon_ref
.end(), are_ordered_int
);
81 for (int z
= 0; z
< length
; ++z
)
82 VERIFY( popheap
[z
] == popheap_ref
[z
] );
83 VERIFY( (std::__is_heap(popheap
, popheap
+ length
- 1), are_ordered
) );
84 for (int z
= 0; z
< length
; ++z
)
85 VERIFY( popheap
[z
].val
<= popheap
[length
-1].val
&& popheap
[z
].valid
);
89 check_sort(int* array
, int length
)
91 bool test
__attribute__((unused
)) = true;
93 rvalstruct sortheap
[9];
95 std::copy(array
, array
+ length
, sortheap
);
96 std::copy(array
, array
+ length
, sortheap_ref
);
97 container
sortcon(sortheap
, sortheap
+ length
);
98 container_ref
sortcon_ref(sortheap_ref
, sortheap_ref
+ length
);
99 std::sort_heap(sortcon
.begin(), sortcon
.end(), are_ordered
);
100 std::sort_heap(sortcon_ref
.begin(), sortcon_ref
.end(), are_ordered_int
);
101 for (int z
= 0; z
< length
; ++z
)
102 VERIFY( sortheap
[z
] == sortheap_ref
[z
] );
103 for (int z
= 0; z
< length
- 1; ++z
)
104 VERIFY( sortheap
[z
].val
<= sortheap
[z
+ 1].val
&& sortheap
[z
].valid
);
105 VERIFY( sortheap
[length
- 1].valid
);
109 check_push(int* array
, int pushval
, int length
)
111 bool test
__attribute__((unused
)) = true;
113 rvalstruct pushheap
[10];
114 int pushheap_ref
[10];
115 std::copy(array
, array
+ length
, pushheap
);
116 std::copy(array
, array
+ length
, pushheap_ref
);
117 pushheap
[length
] = pushval
;
118 pushheap_ref
[length
] = pushval
;
119 container
pushcon(pushheap
, pushheap
+ length
+ 1);
120 container_ref
pushcon_ref(pushheap_ref
, pushheap_ref
+ length
+ 1);
121 std::push_heap(pushcon
.begin(), pushcon
.end(), are_ordered
);
122 std::push_heap(pushcon_ref
.begin(), pushcon_ref
.end(), are_ordered_int
);
123 for (int z
= 0; z
< length
+ 1; ++z
)
124 VERIFY( pushheap
[z
] == pushheap_ref
[z
] );
125 VERIFY( std::__is_heap(pushheap
, pushheap
+ length
+ 1) );
126 for (int z
= 0; z
< length
+ 1; ++z
)
127 VERIFY( pushheap
[z
].valid
);
134 for (int i
= 1; i
< ITERATIONS
; ++i
)
136 for(int z
= 0; z
< i
; ++z
)
138 while (std::next_permutation(array
, array
+ i
))
140 check_make(array
, i
);
141 if (std::__is_heap(array
, array
+ i
, are_ordered_int
))
144 check_sort(array
, i
);
145 for (int pushval
= -1; pushval
<= i
; ++pushval
)
146 check_push(array
, pushval
, i
);