Branch data Line data Source code
1 : : // Heap implementation -*- C++ -*-
2 : :
3 : : // Copyright (C) 2001-2013 Free Software Foundation, Inc.
4 : : //
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)
9 : : // any later version.
10 : :
11 : : // This library is distributed in the hope that it will be useful,
12 : : // but WITHOUT ANY WARRANTY; without even the implied warranty of
13 : : // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 : : // GNU General Public License for more details.
15 : :
16 : : // Under Section 7 of GPL version 3, you are granted additional
17 : : // permissions described in the GCC Runtime Library Exception, version
18 : : // 3.1, as published by the Free Software Foundation.
19 : :
20 : : // You should have received a copy of the GNU General Public License and
21 : : // a copy of the GCC Runtime Library Exception along with this program;
22 : : // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
23 : : // <http://www.gnu.org/licenses/>.
24 : :
25 : : /*
26 : : *
27 : : * Copyright (c) 1994
28 : : * Hewlett-Packard Company
29 : : *
30 : : * Permission to use, copy, modify, distribute and sell this software
31 : : * and its documentation for any purpose is hereby granted without fee,
32 : : * provided that the above copyright notice appear in all copies and
33 : : * that both that copyright notice and this permission notice appear
34 : : * in supporting documentation. Hewlett-Packard Company makes no
35 : : * representations about the suitability of this software for any
36 : : * purpose. It is provided "as is" without express or implied warranty.
37 : : *
38 : : * Copyright (c) 1997
39 : : * Silicon Graphics Computer Systems, Inc.
40 : : *
41 : : * Permission to use, copy, modify, distribute and sell this software
42 : : * and its documentation for any purpose is hereby granted without fee,
43 : : * provided that the above copyright notice appear in all copies and
44 : : * that both that copyright notice and this permission notice appear
45 : : * in supporting documentation. Silicon Graphics makes no
46 : : * representations about the suitability of this software for any
47 : : * purpose. It is provided "as is" without express or implied warranty.
48 : : */
49 : :
50 : : /** @file bits/stl_heap.h
51 : : * This is an internal header file, included by other library headers.
52 : : * Do not attempt to use it directly. @headername{queue}
53 : : */
54 : :
55 : : #ifndef _STL_HEAP_H
56 : : #define _STL_HEAP_H 1
57 : :
58 : : #include <debug/debug.h>
59 : : #include <bits/move.h>
60 : :
61 : : namespace std _GLIBCXX_VISIBILITY(default)
62 : : {
63 : : _GLIBCXX_BEGIN_NAMESPACE_VERSION
64 : :
65 : : /**
66 : : * @defgroup heap_algorithms Heap
67 : : * @ingroup sorting_algorithms
68 : : */
69 : :
70 : : template<typename _RandomAccessIterator, typename _Distance>
71 : : _Distance
72 : : __is_heap_until(_RandomAccessIterator __first, _Distance __n)
73 : : {
74 : : _Distance __parent = 0;
75 : : for (_Distance __child = 1; __child < __n; ++__child)
76 : : {
77 : : if (__first[__parent] < __first[__child])
78 : : return __child;
79 : : if ((__child & 1) == 0)
80 : : ++__parent;
81 : : }
82 : : return __n;
83 : : }
84 : :
85 : : template<typename _RandomAccessIterator, typename _Distance,
86 : : typename _Compare>
87 : : _Distance
88 : : __is_heap_until(_RandomAccessIterator __first, _Distance __n,
89 : : _Compare __comp)
90 : : {
91 : : _Distance __parent = 0;
92 : : for (_Distance __child = 1; __child < __n; ++__child)
93 : : {
94 : : if (__comp(__first[__parent], __first[__child]))
95 : : return __child;
96 : : if ((__child & 1) == 0)
97 : : ++__parent;
98 : : }
99 : : return __n;
100 : : }
101 : :
102 : : // __is_heap, a predicate testing whether or not a range is a heap.
103 : : // This function is an extension, not part of the C++ standard.
104 : : template<typename _RandomAccessIterator, typename _Distance>
105 : : inline bool
106 : : __is_heap(_RandomAccessIterator __first, _Distance __n)
107 : : { return std::__is_heap_until(__first, __n) == __n; }
108 : :
109 : : template<typename _RandomAccessIterator, typename _Compare,
110 : : typename _Distance>
111 : : inline bool
112 : : __is_heap(_RandomAccessIterator __first, _Compare __comp, _Distance __n)
113 : : { return std::__is_heap_until(__first, __n, __comp) == __n; }
114 : :
115 : : template<typename _RandomAccessIterator>
116 : : inline bool
117 : : __is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
118 : : { return std::__is_heap(__first, std::distance(__first, __last)); }
119 : :
120 : : template<typename _RandomAccessIterator, typename _Compare>
121 : : inline bool
122 : : __is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
123 : : _Compare __comp)
124 : : { return std::__is_heap(__first, __comp, std::distance(__first, __last)); }
125 : :
126 : : // Heap-manipulation functions: push_heap, pop_heap, make_heap, sort_heap,
127 : : // + is_heap and is_heap_until in C++0x.
128 : :
129 : : template<typename _RandomAccessIterator, typename _Distance, typename _Tp>
130 : : void
131 : 0 : __push_heap(_RandomAccessIterator __first,
132 : : _Distance __holeIndex, _Distance __topIndex, _Tp __value)
133 : : {
134 : 0 : _Distance __parent = (__holeIndex - 1) / 2;
135 [ # # ][ # # ]: 0 : while (__holeIndex > __topIndex && *(__first + __parent) < __value)
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # ]
[ # ][ # ][ # ]
[ # ][ # ][ # ]
[ # # ][ # # ]
136 : : {
137 : 0 : *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __parent));
138 : 0 : __holeIndex = __parent;
139 : 0 : __parent = (__holeIndex - 1) / 2;
140 : : }
141 : 0 : *(__first + __holeIndex) = _GLIBCXX_MOVE(__value);
142 : 0 : }
143 : :
144 : : /**
145 : : * @brief Push an element onto a heap.
146 : : * @param __first Start of heap.
147 : : * @param __last End of heap + element.
148 : : * @ingroup heap_algorithms
149 : : *
150 : : * This operation pushes the element at last-1 onto the valid heap
151 : : * over the range [__first,__last-1). After completion,
152 : : * [__first,__last) is a valid heap.
153 : : */
154 : : template<typename _RandomAccessIterator>
155 : : inline void
156 : : push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
157 : : {
158 : : typedef typename iterator_traits<_RandomAccessIterator>::value_type
159 : : _ValueType;
160 : : typedef typename iterator_traits<_RandomAccessIterator>::difference_type
161 : : _DistanceType;
162 : :
163 : : // concept requirements
164 : : __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
165 : : _RandomAccessIterator>)
166 : : __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
167 : : __glibcxx_requires_valid_range(__first, __last);
168 : : __glibcxx_requires_heap(__first, __last - 1);
169 : :
170 : : _ValueType __value = _GLIBCXX_MOVE(*(__last - 1));
171 : : std::__push_heap(__first, _DistanceType((__last - __first) - 1),
172 : : _DistanceType(0), _GLIBCXX_MOVE(__value));
173 : : }
174 : :
175 : : template<typename _RandomAccessIterator, typename _Distance, typename _Tp,
176 : : typename _Compare>
177 : : void
178 : 107946 : __push_heap(_RandomAccessIterator __first, _Distance __holeIndex,
179 : : _Distance __topIndex, _Tp __value, _Compare __comp)
180 : : {
181 : 107946 : _Distance __parent = (__holeIndex - 1) / 2;
182 [ + + + + ]: 725440 : while (__holeIndex > __topIndex
[ # # ]
[ # # # # ]
[ # # ][ # # ]
[ # # ][ # # ]
[ # # # # ]
[ # # ][ # # ]
[ # # ]
[ # # # # ]
[ # # ][ + + ]
[ + + + + ]
[ + + ][ # # ]
[ # # # # ]
[ # # ]
183 [ # # ][ # # ]: 543864 : && __comp(*(__first + __parent), __value))
[ + # ][ # # ]
[ # # ][ # # ]
[ + + ][ + ]
[ # ][ # # ]
184 : : {
185 : 73630 : *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __parent));
186 : 73630 : __holeIndex = __parent;
187 : 73630 : __parent = (__holeIndex - 1) / 2;
188 : : }
189 : 107946 : *(__first + __holeIndex) = _GLIBCXX_MOVE(__value);
190 : 107946 : }
191 : :
192 : : /**
193 : : * @brief Push an element onto a heap using comparison functor.
194 : : * @param __first Start of heap.
195 : : * @param __last End of heap + element.
196 : : * @param __comp Comparison functor.
197 : : * @ingroup heap_algorithms
198 : : *
199 : : * This operation pushes the element at __last-1 onto the valid
200 : : * heap over the range [__first,__last-1). After completion,
201 : : * [__first,__last) is a valid heap. Compare operations are
202 : : * performed using comp.
203 : : */
204 : : template<typename _RandomAccessIterator, typename _Compare>
205 : : inline void
206 : 54000 : push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
207 : : _Compare __comp)
208 : : {
209 : : typedef typename iterator_traits<_RandomAccessIterator>::value_type
210 : : _ValueType;
211 : : typedef typename iterator_traits<_RandomAccessIterator>::difference_type
212 : : _DistanceType;
213 : :
214 : : // concept requirements
215 : : __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
216 : : _RandomAccessIterator>)
217 : : __glibcxx_requires_valid_range(__first, __last);
218 : : __glibcxx_requires_heap_pred(__first, __last - 1, __comp);
219 : :
220 [ + - ][ + - ]: 54000 : _ValueType __value = _GLIBCXX_MOVE(*(__last - 1));
221 : 54000 : std::__push_heap(__first, _DistanceType((__last - __first) - 1),
222 : 54000 : _DistanceType(0), _GLIBCXX_MOVE(__value), __comp);
223 : 54000 : }
224 : :
225 : : template<typename _RandomAccessIterator, typename _Distance, typename _Tp>
226 : : void
227 : 0 : __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
228 : : _Distance __len, _Tp __value)
229 : : {
230 : 0 : const _Distance __topIndex = __holeIndex;
231 : 0 : _Distance __secondChild = __holeIndex;
232 [ # # ][ # # ]: 0 : while (__secondChild < (__len - 1) / 2)
[ # # ][ # # ]
233 : : {
234 : 0 : __secondChild = 2 * (__secondChild + 1);
235 [ # # ][ # # ]: 0 : if (*(__first + __secondChild) < *(__first + (__secondChild - 1)))
[ # # ][ # # ]
[ # ][ # # ]
[ # # ]
236 : 0 : __secondChild--;
237 : 0 : *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __secondChild));
238 : 0 : __holeIndex = __secondChild;
239 : : }
240 [ # # ][ # # ]: 0 : if ((__len & 1) == 0 && __secondChild == (__len - 2) / 2)
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
241 : : {
242 : 0 : __secondChild = 2 * (__secondChild + 1);
243 : 0 : *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first
244 : : + (__secondChild - 1)));
245 : 0 : __holeIndex = __secondChild - 1;
246 : : }
247 : 0 : std::__push_heap(__first, __holeIndex, __topIndex,
248 : : _GLIBCXX_MOVE(__value));
249 : 0 : }
250 : :
251 : : template<typename _RandomAccessIterator>
252 : : inline void
253 : 0 : __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
254 : : _RandomAccessIterator __result)
255 : : {
256 : : typedef typename iterator_traits<_RandomAccessIterator>::value_type
257 : : _ValueType;
258 : : typedef typename iterator_traits<_RandomAccessIterator>::difference_type
259 : : _DistanceType;
260 : :
261 : 0 : _ValueType __value = _GLIBCXX_MOVE(*__result);
262 : 0 : *__result = _GLIBCXX_MOVE(*__first);
263 [ # # # # ]: 0 : std::__adjust_heap(__first, _DistanceType(0),
[ # # ]
264 : : _DistanceType(__last - __first),
265 [ # # ]: 0 : _GLIBCXX_MOVE(__value));
266 : 0 : }
267 : :
268 : : /**
269 : : * @brief Pop an element off a heap.
270 : : * @param __first Start of heap.
271 : : * @param __last End of heap.
272 : : * @pre [__first, __last) is a valid, non-empty range.
273 : : * @ingroup heap_algorithms
274 : : *
275 : : * This operation pops the top of the heap. The elements __first
276 : : * and __last-1 are swapped and [__first,__last-1) is made into a
277 : : * heap.
278 : : */
279 : : template<typename _RandomAccessIterator>
280 : : inline void
281 : : pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
282 : : {
283 : : typedef typename iterator_traits<_RandomAccessIterator>::value_type
284 : : _ValueType;
285 : :
286 : : // concept requirements
287 : : __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
288 : : _RandomAccessIterator>)
289 : : __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
290 : : __glibcxx_requires_non_empty_range(__first, __last);
291 : : __glibcxx_requires_valid_range(__first, __last);
292 : : __glibcxx_requires_heap(__first, __last);
293 : :
294 : : if (__last - __first > 1)
295 : : {
296 : : --__last;
297 : : std::__pop_heap(__first, __last, __last);
298 : : }
299 : : }
300 : :
301 : : template<typename _RandomAccessIterator, typename _Distance,
302 : : typename _Tp, typename _Compare>
303 : : void
304 : 53946 : __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
305 : : _Distance __len, _Tp __value, _Compare __comp)
306 : : {
307 : 53946 : const _Distance __topIndex = __holeIndex;
308 : 53946 : _Distance __secondChild = __holeIndex;
309 [ + + ][ + + ]: 458994 : while (__secondChild < (__len - 1) / 2)
[ # # ][ # # ]
310 : : {
311 : 405048 : __secondChild = 2 * (__secondChild + 1);
312 [ # # ]: 405048 : if (__comp(*(__first + __secondChild),
[ # # # # ]
[ # # # # ]
[ # # ]
[ + + + + ]
[ # # # # ]
313 : 405048 : *(__first + (__secondChild - 1))))
314 : 204556 : __secondChild--;
315 : 405048 : *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __secondChild));
316 : 405048 : __holeIndex = __secondChild;
317 : : }
318 [ + + ][ + + ]: 53946 : if ((__len & 1) == 0 && __secondChild == (__len - 2) / 2)
[ + + ][ + + ]
[ # # ][ # # ]
[ # # ][ # # ]
319 : : {
320 : 570 : __secondChild = 2 * (__secondChild + 1);
321 : 570 : *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first
322 : : + (__secondChild - 1)));
323 : 570 : __holeIndex = __secondChild - 1;
324 : : }
325 [ # # ]: 53946 : std::__push_heap(__first, __holeIndex, __topIndex,
326 : : _GLIBCXX_MOVE(__value), __comp);
327 : 53946 : }
328 : :
329 : : template<typename _RandomAccessIterator, typename _Compare>
330 : : inline void
331 : 53946 : __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
332 : : _RandomAccessIterator __result, _Compare __comp)
333 : : {
334 : : typedef typename iterator_traits<_RandomAccessIterator>::value_type
335 : : _ValueType;
336 : : typedef typename iterator_traits<_RandomAccessIterator>::difference_type
337 : : _DistanceType;
338 : :
339 : 53946 : _ValueType __value = _GLIBCXX_MOVE(*__result);
340 : 53946 : *__result = _GLIBCXX_MOVE(*__first);
341 [ # # # # ]: 53946 : std::__adjust_heap(__first, _DistanceType(0),
[ # # ]
342 : : _DistanceType(__last - __first),
343 [ # # ]: 53946 : _GLIBCXX_MOVE(__value), __comp);
344 : 53946 : }
345 : :
346 : : /**
347 : : * @brief Pop an element off a heap using comparison functor.
348 : : * @param __first Start of heap.
349 : : * @param __last End of heap.
350 : : * @param __comp Comparison functor to use.
351 : : * @ingroup heap_algorithms
352 : : *
353 : : * This operation pops the top of the heap. The elements __first
354 : : * and __last-1 are swapped and [__first,__last-1) is made into a
355 : : * heap. Comparisons are made using comp.
356 : : */
357 : : template<typename _RandomAccessIterator, typename _Compare>
358 : : inline void
359 : 0 : pop_heap(_RandomAccessIterator __first,
360 : : _RandomAccessIterator __last, _Compare __comp)
361 : : {
362 : : // concept requirements
363 : : __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
364 : : _RandomAccessIterator>)
365 : : __glibcxx_requires_valid_range(__first, __last);
366 : : __glibcxx_requires_non_empty_range(__first, __last);
367 : : __glibcxx_requires_heap_pred(__first, __last, __comp);
368 : :
369 [ # # ][ # # ]: 0 : if (__last - __first > 1)
370 : : {
371 : 0 : --__last;
372 : 0 : std::__pop_heap(__first, __last, __last, __comp);
373 : : }
374 : 0 : }
375 : :
376 : : /**
377 : : * @brief Construct a heap over a range.
378 : : * @param __first Start of heap.
379 : : * @param __last End of heap.
380 : : * @ingroup heap_algorithms
381 : : *
382 : : * This operation makes the elements in [__first,__last) into a heap.
383 : : */
384 : : template<typename _RandomAccessIterator>
385 : : void
386 : 0 : make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
387 : : {
388 : : typedef typename iterator_traits<_RandomAccessIterator>::value_type
389 : : _ValueType;
390 : : typedef typename iterator_traits<_RandomAccessIterator>::difference_type
391 : : _DistanceType;
392 : :
393 : : // concept requirements
394 : : __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
395 : : _RandomAccessIterator>)
396 : : __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
397 : : __glibcxx_requires_valid_range(__first, __last);
398 : :
399 [ # # ][ # # ]: 0 : if (__last - __first < 2)
[ # # ][ # # ]
[ # # ][ # ]
[ # # ][ # ]
400 : 0 : return;
401 : :
402 [ # # ][ # # ]: 0 : const _DistanceType __len = __last - __first;
[ # # ]
403 : 0 : _DistanceType __parent = (__len - 2) / 2;
404 : : while (true)
405 : : {
406 : 0 : _ValueType __value = _GLIBCXX_MOVE(*(__first + __parent));
407 [ # # # # : 0 : std::__adjust_heap(__first, __parent, __len, _GLIBCXX_MOVE(__value));
# # ]
[ # # # # ]
408 [ # # ][ # # ]: 0 : if (__parent == 0)
[ # # ][ # # ]
409 : 0 : return;
410 : 0 : __parent--;
411 : 0 : }
412 : : }
413 : :
414 : : /**
415 : : * @brief Construct a heap over a range using comparison functor.
416 : : * @param __first Start of heap.
417 : : * @param __last End of heap.
418 : : * @param __comp Comparison functor to use.
419 : : * @ingroup heap_algorithms
420 : : *
421 : : * This operation makes the elements in [__first,__last) into a heap.
422 : : * Comparisons are made using __comp.
423 : : */
424 : : template<typename _RandomAccessIterator, typename _Compare>
425 : : void
426 : 0 : make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
427 : : _Compare __comp)
428 : : {
429 : : typedef typename iterator_traits<_RandomAccessIterator>::value_type
430 : : _ValueType;
431 : : typedef typename iterator_traits<_RandomAccessIterator>::difference_type
432 : : _DistanceType;
433 : :
434 : : // concept requirements
435 : : __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
436 : : _RandomAccessIterator>)
437 : : __glibcxx_requires_valid_range(__first, __last);
438 : :
439 [ # # ][ # # ]: 0 : if (__last - __first < 2)
[ # # ][ # # ]
[ # # ][ # ]
[ # # ][ # ]
440 : 0 : return;
441 : :
442 [ # # ][ # # ]: 0 : const _DistanceType __len = __last - __first;
[ # # ]
443 : 0 : _DistanceType __parent = (__len - 2) / 2;
444 : : while (true)
445 : : {
446 : 0 : _ValueType __value = _GLIBCXX_MOVE(*(__first + __parent));
447 [ # # # # : 0 : std::__adjust_heap(__first, __parent, __len, _GLIBCXX_MOVE(__value),
# # ]
[ # # # # ]
448 : : __comp);
449 [ # # ][ # # ]: 0 : if (__parent == 0)
[ # # ][ # # ]
450 : 0 : return;
451 : 0 : __parent--;
452 : 0 : }
453 : : }
454 : :
455 : : /**
456 : : * @brief Sort a heap.
457 : : * @param __first Start of heap.
458 : : * @param __last End of heap.
459 : : * @ingroup heap_algorithms
460 : : *
461 : : * This operation sorts the valid heap in the range [__first,__last).
462 : : */
463 : : template<typename _RandomAccessIterator>
464 : : void
465 : 0 : sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
466 : : {
467 : : // concept requirements
468 : : __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
469 : : _RandomAccessIterator>)
470 : : __glibcxx_function_requires(_LessThanComparableConcept<
471 : : typename iterator_traits<_RandomAccessIterator>::value_type>)
472 : : __glibcxx_requires_valid_range(__first, __last);
473 : : __glibcxx_requires_heap(__first, __last);
474 : :
475 [ # # ][ # # ]: 0 : while (__last - __first > 1)
[ # # ][ # # ]
[ # ][ # ]
476 : : {
477 : 0 : --__last;
478 : 0 : std::__pop_heap(__first, __last, __last);
479 : : }
480 : 0 : }
481 : :
482 : : /**
483 : : * @brief Sort a heap using comparison functor.
484 : : * @param __first Start of heap.
485 : : * @param __last End of heap.
486 : : * @param __comp Comparison functor to use.
487 : : * @ingroup heap_algorithms
488 : : *
489 : : * This operation sorts the valid heap in the range [__first,__last).
490 : : * Comparisons are made using __comp.
491 : : */
492 : : template<typename _RandomAccessIterator, typename _Compare>
493 : : void
494 : 54 : sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
495 : : _Compare __comp)
496 : : {
497 : : // concept requirements
498 : : __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
499 : : _RandomAccessIterator>)
500 : : __glibcxx_requires_valid_range(__first, __last);
501 : : __glibcxx_requires_heap_pred(__first, __last, __comp);
502 : :
503 [ # + ][ # # ]: 54000 : while (__last - __first > 1)
[ # # ][ # # ]
[ + ][ + + ]
[ # ]
504 : : {
505 : 53946 : --__last;
506 : 53946 : std::__pop_heap(__first, __last, __last, __comp);
507 : : }
508 : 54 : }
509 : :
510 : : #if __cplusplus >= 201103L
511 : : /**
512 : : * @brief Search the end of a heap.
513 : : * @param __first Start of range.
514 : : * @param __last End of range.
515 : : * @return An iterator pointing to the first element not in the heap.
516 : : * @ingroup heap_algorithms
517 : : *
518 : : * This operation returns the last iterator i in [__first, __last) for which
519 : : * the range [__first, i) is a heap.
520 : : */
521 : : template<typename _RandomAccessIterator>
522 : : inline _RandomAccessIterator
523 : : is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last)
524 : : {
525 : : // concept requirements
526 : : __glibcxx_function_requires(_RandomAccessIteratorConcept<
527 : : _RandomAccessIterator>)
528 : : __glibcxx_function_requires(_LessThanComparableConcept<
529 : : typename iterator_traits<_RandomAccessIterator>::value_type>)
530 : : __glibcxx_requires_valid_range(__first, __last);
531 : :
532 : : return __first + std::__is_heap_until(__first, std::distance(__first,
533 : : __last));
534 : : }
535 : :
536 : : /**
537 : : * @brief Search the end of a heap using comparison functor.
538 : : * @param __first Start of range.
539 : : * @param __last End of range.
540 : : * @param __comp Comparison functor to use.
541 : : * @return An iterator pointing to the first element not in the heap.
542 : : * @ingroup heap_algorithms
543 : : *
544 : : * This operation returns the last iterator i in [__first, __last) for which
545 : : * the range [__first, i) is a heap. Comparisons are made using __comp.
546 : : */
547 : : template<typename _RandomAccessIterator, typename _Compare>
548 : : inline _RandomAccessIterator
549 : : is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last,
550 : : _Compare __comp)
551 : : {
552 : : // concept requirements
553 : : __glibcxx_function_requires(_RandomAccessIteratorConcept<
554 : : _RandomAccessIterator>)
555 : : __glibcxx_requires_valid_range(__first, __last);
556 : :
557 : : return __first + std::__is_heap_until(__first, std::distance(__first,
558 : : __last),
559 : : __comp);
560 : : }
561 : :
562 : : /**
563 : : * @brief Determines whether a range is a heap.
564 : : * @param __first Start of range.
565 : : * @param __last End of range.
566 : : * @return True if range is a heap, false otherwise.
567 : : * @ingroup heap_algorithms
568 : : */
569 : : template<typename _RandomAccessIterator>
570 : : inline bool
571 : : is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
572 : : { return std::is_heap_until(__first, __last) == __last; }
573 : :
574 : : /**
575 : : * @brief Determines whether a range is a heap using comparison functor.
576 : : * @param __first Start of range.
577 : : * @param __last End of range.
578 : : * @param __comp Comparison functor to use.
579 : : * @return True if range is a heap, false otherwise.
580 : : * @ingroup heap_algorithms
581 : : */
582 : : template<typename _RandomAccessIterator, typename _Compare>
583 : : inline bool
584 : : is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
585 : : _Compare __comp)
586 : : { return std::is_heap_until(__first, __last, __comp) == __last; }
587 : : #endif
588 : :
589 : : _GLIBCXX_END_NAMESPACE_VERSION
590 : : } // namespace
591 : :
592 : : #endif /* _STL_HEAP_H */
|