4 * Hewlett-Packard Company
6 * Permission to use, copy, modify, distribute and sell this software
7 * and its documentation for any purpose is hereby granted without fee,
8 * provided that the above copyright notice appear in all copies and
9 * that both that copyright notice and this permission notice appear
10 * in supporting documentation. Hewlett-Packard Company makes no
11 * representations about the suitability of this software for any
12 * purpose. It is provided "as is" without express or implied warranty.
15 * Silicon Graphics Computer Systems, Inc.
17 * Permission to use, copy, modify, distribute and sell this software
18 * and its documentation for any purpose is hereby granted without fee,
19 * provided that the above copyright notice appear in all copies and
20 * that both that copyright notice and this permission notice appear
21 * in supporting documentation. Silicon Graphics makes no
22 * representations about the suitability of this software for any
23 * purpose. It is provided "as is" without express or implied warranty.
26 /* NOTE: This is an internal header file, included by other STL headers.
27 * You should not attempt to use it directly.
30 #ifndef _CPP_BITS_STL_HEAP_H
31 #define _CPP_BITS_STL_HEAP_H 1
36 // Heap-manipulation functions: push_heap, pop_heap, make_heap, sort_heap.
38 template <class _RandomAccessIterator
, class _Distance
, class _Tp
>
40 __push_heap(_RandomAccessIterator __first
,
41 _Distance __holeIndex
, _Distance __topIndex
, _Tp __value
)
43 _Distance __parent
= (__holeIndex
- 1) / 2;
44 while (__holeIndex
> __topIndex
&& *(__first
+ __parent
) < __value
) {
45 *(__first
+ __holeIndex
) = *(__first
+ __parent
);
46 __holeIndex
= __parent
;
47 __parent
= (__holeIndex
- 1) / 2;
49 *(__first
+ __holeIndex
) = __value
;
52 template <class _RandomAccessIterator
, class _Distance
, class _Tp
>
54 __push_heap_aux(_RandomAccessIterator __first
,
55 _RandomAccessIterator __last
, _Distance
*, _Tp
*)
57 __push_heap(__first
, _Distance((__last
- __first
) - 1), _Distance(0),
61 template <class _RandomAccessIterator
>
63 push_heap(_RandomAccessIterator __first
, _RandomAccessIterator __last
)
65 // concept requirements
66 glibcpp_function_requires(Mutable_RandomAccessIteratorConcept
<
67 _RandomAccessIterator
>);
68 glibcpp_function_requires(LessThanComparableConcept
<
69 typename iterator_traits
<_RandomAccessIterator
>::value_type
>);
71 __push_heap_aux(__first
, __last
,
72 __distance_type(__first
), __value_type(__first
));
75 template <class _RandomAccessIterator
, class _Distance
, class _Tp
,
78 __push_heap(_RandomAccessIterator __first
, _Distance __holeIndex
,
79 _Distance __topIndex
, _Tp __value
, _Compare __comp
)
81 _Distance __parent
= (__holeIndex
- 1) / 2;
82 while (__holeIndex
> __topIndex
&& __comp(*(__first
+ __parent
), __value
)) {
83 *(__first
+ __holeIndex
) = *(__first
+ __parent
);
84 __holeIndex
= __parent
;
85 __parent
= (__holeIndex
- 1) / 2;
87 *(__first
+ __holeIndex
) = __value
;
90 template <class _RandomAccessIterator
, class _Compare
,
91 class _Distance
, class _Tp
>
93 __push_heap_aux(_RandomAccessIterator __first
,
94 _RandomAccessIterator __last
, _Compare __comp
,
97 __push_heap(__first
, _Distance((__last
- __first
) - 1), _Distance(0),
98 _Tp(*(__last
- 1)), __comp
);
101 template <class _RandomAccessIterator
, class _Compare
>
103 push_heap(_RandomAccessIterator __first
, _RandomAccessIterator __last
,
106 // concept requirements
107 glibcpp_function_requires(Mutable_RandomAccessIteratorConcept
<
108 _RandomAccessIterator
>);
110 __push_heap_aux(__first
, __last
, __comp
,
111 __distance_type(__first
), __value_type(__first
));
114 template <class _RandomAccessIterator
, class _Distance
, class _Tp
>
116 __adjust_heap(_RandomAccessIterator __first
, _Distance __holeIndex
,
117 _Distance __len
, _Tp __value
)
119 _Distance __topIndex
= __holeIndex
;
120 _Distance __secondChild
= 2 * __holeIndex
+ 2;
121 while (__secondChild
< __len
) {
122 if (*(__first
+ __secondChild
) < *(__first
+ (__secondChild
- 1)))
124 *(__first
+ __holeIndex
) = *(__first
+ __secondChild
);
125 __holeIndex
= __secondChild
;
126 __secondChild
= 2 * (__secondChild
+ 1);
128 if (__secondChild
== __len
) {
129 *(__first
+ __holeIndex
) = *(__first
+ (__secondChild
- 1));
130 __holeIndex
= __secondChild
- 1;
132 __push_heap(__first
, __holeIndex
, __topIndex
, __value
);
135 template <class _RandomAccessIterator
, class _Tp
, class _Distance
>
137 __pop_heap(_RandomAccessIterator __first
, _RandomAccessIterator __last
,
138 _RandomAccessIterator __result
, _Tp __value
, _Distance
*)
140 *__result
= *__first
;
141 __adjust_heap(__first
, _Distance(0), _Distance(__last
- __first
), __value
);
144 template <class _RandomAccessIterator
, class _Tp
>
146 __pop_heap_aux(_RandomAccessIterator __first
, _RandomAccessIterator __last
,
149 __pop_heap(__first
, __last
- 1, __last
- 1,
150 _Tp(*(__last
- 1)), __distance_type(__first
));
153 template <class _RandomAccessIterator
>
154 inline void pop_heap(_RandomAccessIterator __first
,
155 _RandomAccessIterator __last
)
157 // concept requirements
158 glibcpp_function_requires(Mutable_RandomAccessIteratorConcept
<
159 _RandomAccessIterator
>);
160 glibcpp_function_requires(LessThanComparableConcept
<
161 typename iterator_traits
<_RandomAccessIterator
>::value_type
>);
163 __pop_heap_aux(__first
, __last
, __value_type(__first
));
166 template <class _RandomAccessIterator
, class _Distance
,
167 class _Tp
, class _Compare
>
169 __adjust_heap(_RandomAccessIterator __first
, _Distance __holeIndex
,
170 _Distance __len
, _Tp __value
, _Compare __comp
)
172 _Distance __topIndex
= __holeIndex
;
173 _Distance __secondChild
= 2 * __holeIndex
+ 2;
174 while (__secondChild
< __len
) {
175 if (__comp(*(__first
+ __secondChild
), *(__first
+ (__secondChild
- 1))))
177 *(__first
+ __holeIndex
) = *(__first
+ __secondChild
);
178 __holeIndex
= __secondChild
;
179 __secondChild
= 2 * (__secondChild
+ 1);
181 if (__secondChild
== __len
) {
182 *(__first
+ __holeIndex
) = *(__first
+ (__secondChild
- 1));
183 __holeIndex
= __secondChild
- 1;
185 __push_heap(__first
, __holeIndex
, __topIndex
, __value
, __comp
);
188 template <class _RandomAccessIterator
, class _Tp
, class _Compare
,
191 __pop_heap(_RandomAccessIterator __first
, _RandomAccessIterator __last
,
192 _RandomAccessIterator __result
, _Tp __value
, _Compare __comp
,
195 *__result
= *__first
;
196 __adjust_heap(__first
, _Distance(0), _Distance(__last
- __first
),
200 template <class _RandomAccessIterator
, class _Tp
, class _Compare
>
202 __pop_heap_aux(_RandomAccessIterator __first
,
203 _RandomAccessIterator __last
, _Tp
*, _Compare __comp
)
205 __pop_heap(__first
, __last
- 1, __last
- 1, _Tp(*(__last
- 1)), __comp
,
206 __distance_type(__first
));
209 template <class _RandomAccessIterator
, class _Compare
>
211 pop_heap(_RandomAccessIterator __first
,
212 _RandomAccessIterator __last
, _Compare __comp
)
214 // concept requirements
215 glibcpp_function_requires(Mutable_RandomAccessIteratorConcept
<
216 _RandomAccessIterator
>);
218 __pop_heap_aux(__first
, __last
, __value_type(__first
), __comp
);
221 template <class _RandomAccessIterator
, class _Tp
, class _Distance
>
223 __make_heap(_RandomAccessIterator __first
,
224 _RandomAccessIterator __last
, _Tp
*, _Distance
*)
226 if (__last
- __first
< 2) return;
227 _Distance __len
= __last
- __first
;
228 _Distance __parent
= (__len
- 2)/2;
231 __adjust_heap(__first
, __parent
, __len
, _Tp(*(__first
+ __parent
)));
232 if (__parent
== 0) return;
237 template <class _RandomAccessIterator
>
239 make_heap(_RandomAccessIterator __first
, _RandomAccessIterator __last
)
241 // concept requirements
242 glibcpp_function_requires(Mutable_RandomAccessIteratorConcept
<
243 _RandomAccessIterator
>);
244 glibcpp_function_requires(LessThanComparableConcept
<
245 typename iterator_traits
<_RandomAccessIterator
>::value_type
>);
247 __make_heap(__first
, __last
,
248 __value_type(__first
), __distance_type(__first
));
251 template <class _RandomAccessIterator
, class _Compare
,
252 class _Tp
, class _Distance
>
254 __make_heap(_RandomAccessIterator __first
, _RandomAccessIterator __last
,
255 _Compare __comp
, _Tp
*, _Distance
*)
257 if (__last
- __first
< 2) return;
258 _Distance __len
= __last
- __first
;
259 _Distance __parent
= (__len
- 2)/2;
262 __adjust_heap(__first
, __parent
, __len
, _Tp(*(__first
+ __parent
)),
264 if (__parent
== 0) return;
269 template <class _RandomAccessIterator
, class _Compare
>
271 make_heap(_RandomAccessIterator __first
,
272 _RandomAccessIterator __last
, _Compare __comp
)
274 // concept requirements
275 glibcpp_function_requires(Mutable_RandomAccessIteratorConcept
<
276 _RandomAccessIterator
>);
278 __make_heap(__first
, __last
, __comp
,
279 __value_type(__first
), __distance_type(__first
));
282 template <class _RandomAccessIterator
>
283 void sort_heap(_RandomAccessIterator __first
, _RandomAccessIterator __last
)
285 // concept requirements
286 glibcpp_function_requires(Mutable_RandomAccessIteratorConcept
<
287 _RandomAccessIterator
>);
288 glibcpp_function_requires(LessThanComparableConcept
<
289 typename iterator_traits
<_RandomAccessIterator
>::value_type
>);
291 while (__last
- __first
> 1)
292 pop_heap(__first
, __last
--);
295 template <class _RandomAccessIterator
, class _Compare
>
297 sort_heap(_RandomAccessIterator __first
,
298 _RandomAccessIterator __last
, _Compare __comp
)
300 // concept requirements
301 glibcpp_function_requires(Mutable_RandomAccessIteratorConcept
<
302 _RandomAccessIterator
>);
304 while (__last
- __first
> 1)
305 pop_heap(__first
, __last
--, __comp
);
310 #endif /* _CPP_BITS_STL_HEAP_H */