1 // { dg-options "-std=gnu++0x" }
3 // Copyright (C) 2005, 2006, 2007, 2008, 2009, 2010
4 // Free Software Foundation, Inc.
6 // This file is part of the GNU ISO C++ Library. This library is free
7 // software; you can redistribute it and/or modify it under the
8 // terms of the GNU General Public License as published by the
9 // Free Software Foundation; either version 3, or (at your option)
12 // This library is distributed in the hope that it will be useful,
13 // but WITHOUT ANY WARRANTY; without Pred the implied warranty of
14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 // GNU General Public License for more details.
17 // You should have received a copy of the GNU General Public License along
18 // with this library; see the file COPYING3. If not see
19 // <http://www.gnu.org/licenses/>.
21 // { dg-options "-std=gnu++0x -DITERATIONS=5" { target simulator } }
23 // 25.3.6 Heap operations [lib.alg.heap.operations]
25 #undef _GLIBCXX_CONCEPT_CHECKS
27 // XXX FIXME: parallel-mode should deal correctly with moveable-only types
28 // per C++0x, at minimum smoothly fall back to serial.
29 #undef _GLIBCXX_PARALLEL
32 #include <testsuite_hooks.h>
33 #include <testsuite_iterators.h>
34 #include <testsuite_rvalref.h>
40 using __gnu_test::test_container
;
41 using __gnu_test::random_access_iterator_wrapper
;
42 using __gnu_test::rvalstruct
;
44 typedef test_container
<rvalstruct
, random_access_iterator_wrapper
> container
;
45 typedef test_container
<int, random_access_iterator_wrapper
> container_ref
;
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());
59 std::make_heap(makecon_ref
.begin(), makecon_ref
.end());
60 for (int z
= 0; z
< length
; ++z
)
61 VERIFY( makeheap
[z
] == makeheap_ref
[z
] );
62 VERIFY( std::__is_heap(makecon
.begin(), makecon
.end()) );
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());
79 std::pop_heap(popcon_ref
.begin(), popcon_ref
.end());
80 for (int z
= 0; z
< length
; ++z
)
81 VERIFY( popheap
[z
] == popheap_ref
[z
] );
82 VERIFY( (std::__is_heap(popheap
, popheap
+ length
- 1)) );
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());
99 std::sort_heap(sortcon_ref
.begin(), sortcon_ref
.end());
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());
121 std::push_heap(pushcon_ref
.begin(), pushcon_ref
.end());
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
))
143 check_sort(array
, i
);
144 for (int pushval
= -1; pushval
<= i
; ++pushval
)
145 check_push(array
, pushval
, i
);