1 // { dg-options "-std=gnu++0x" }
3 // Copyright (C) 2005, 2007 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 2, 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 COPYING. If not, write to the Free
18 // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
21 // 25.3.6 Heap operations [lib.alg.heap.operations]
23 #undef _GLIBCXX_CONCEPT_CHECKS
24 #define _GLIBCXX_TESTSUITE_ALLOW_RVALREF_ALIASING
27 #include <testsuite_hooks.h>
28 #include <testsuite_iterators.h>
29 #include <testsuite_rvalref.h>
31 using __gnu_test::test_container
;
32 using __gnu_test::random_access_iterator_wrapper
;
33 using __gnu_test::rvalstruct
;
35 typedef test_container
<rvalstruct
, random_access_iterator_wrapper
> container
;
36 typedef test_container
<int, random_access_iterator_wrapper
> container_ref
;
38 bool test
__attribute__((unused
)) = true;
41 check_make(int* array
, int length
)
43 rvalstruct makeheap
[9];
45 std::copy(array
, array
+ length
, makeheap
);
46 std::copy(array
, array
+ length
, makeheap_ref
);
47 container
makecon(makeheap
, makeheap
+ length
);
48 container_ref
makecon_ref(makeheap_ref
, makeheap_ref
+ length
);
49 std::make_heap(makecon
.begin(), makecon
.end());
50 std::make_heap(makecon_ref
.begin(), makecon_ref
.end());
51 for (int z
= 0; z
< length
; ++z
)
52 VERIFY( makeheap
[z
] == makeheap_ref
[z
] );
53 VERIFY( std::__is_heap(makecon
.begin(), makecon
.end()) );
54 for (int z
= 0; z
< length
; ++z
)
55 VERIFY( makeheap
[z
].valid
);
59 check_pop(int* array
, int length
)
61 rvalstruct popheap
[9];
63 std::copy(array
, array
+ length
, popheap
);
64 std::copy(array
, array
+ length
, popheap_ref
);
65 container
popcon(popheap
, popheap
+ length
);
66 container_ref
popcon_ref(popheap_ref
, popheap_ref
+ length
);
67 std::pop_heap(popcon
.begin(), popcon
.end());
68 std::pop_heap(popcon_ref
.begin(), popcon_ref
.end());
69 for (int z
= 0; z
< length
; ++z
)
70 VERIFY( popheap
[z
] == popheap_ref
[z
] );
71 VERIFY( (std::__is_heap(popheap
, popheap
+ length
- 1)) );
72 for (int z
= 0; z
< length
; ++z
)
73 VERIFY( popheap
[z
].val
<= popheap
[length
-1].val
&& popheap
[z
].valid
);
77 check_sort(int* array
, int length
)
79 rvalstruct sortheap
[9];
81 std::copy(array
, array
+ length
, sortheap
);
82 std::copy(array
, array
+ length
, sortheap_ref
);
83 container
sortcon(sortheap
, sortheap
+ length
);
84 container_ref
sortcon_ref(sortheap_ref
, sortheap_ref
+ length
);
85 std::sort_heap(sortcon
.begin(), sortcon
.end());
86 std::sort_heap(sortcon_ref
.begin(), sortcon_ref
.end());
87 for (int z
= 0; z
< length
; ++z
)
88 VERIFY( sortheap
[z
] == sortheap_ref
[z
] );
89 for (int z
= 0; z
< length
- 1; ++z
)
90 VERIFY( sortheap
[z
].val
<= sortheap
[z
+ 1].val
&& sortheap
[z
].valid
);
91 VERIFY( sortheap
[length
- 1].valid
);
95 check_push(int* array
, int pushval
, int length
)
97 rvalstruct pushheap
[10];
99 std::copy(array
, array
+ length
, pushheap
);
100 std::copy(array
, array
+ length
, pushheap_ref
);
101 pushheap
[length
] = pushval
;
102 pushheap_ref
[length
] = pushval
;
103 container
pushcon(pushheap
, pushheap
+ length
+ 1);
104 container_ref
pushcon_ref(pushheap_ref
, pushheap_ref
+ length
+ 1);
105 std::push_heap(pushcon
.begin(), pushcon
.end());
106 std::push_heap(pushcon_ref
.begin(), pushcon_ref
.end());
107 for (int z
= 0; z
< length
+ 1; ++z
)
108 VERIFY( pushheap
[z
] == pushheap_ref
[z
] );
109 VERIFY( std::__is_heap(pushheap
, pushheap
+ length
+ 1) );
110 for (int z
= 0; z
< length
+ 1; ++z
)
111 VERIFY( pushheap
[z
].valid
);
118 for (int i
= 1; i
< 9; ++i
)
120 for(int z
= 0; z
< i
; ++z
)
122 while (std::next_permutation(array
, array
+ i
))
124 check_make(array
, i
);
125 if (std::__is_heap(array
, array
+ i
))
128 check_sort(array
, i
);
129 for (int pushval
= -1; pushval
<= i
; ++pushval
)
130 check_push(array
, pushval
, i
);