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