1 | // Heap implementation -*- C++ -*- |
2 | |
3 | // Copyright (C) 2001-2021 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 | #include <bits/predefined_ops.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 | typename _Compare> |
73 | _GLIBCXX20_CONSTEXPR |
74 | _Distance |
75 | __is_heap_until(_RandomAccessIterator __first, _Distance __n, |
76 | _Compare& __comp) |
77 | { |
78 | _Distance __parent = 0; |
79 | for (_Distance __child = 1; __child < __n; ++__child) |
80 | { |
81 | if (__comp(__first + __parent, __first + __child)) |
82 | return __child; |
83 | if ((__child & 1) == 0) |
84 | ++__parent; |
85 | } |
86 | return __n; |
87 | } |
88 | |
89 | // __is_heap, a predicate testing whether or not a range is a heap. |
90 | // This function is an extension, not part of the C++ standard. |
91 | template<typename _RandomAccessIterator, typename _Distance> |
92 | _GLIBCXX20_CONSTEXPR |
93 | inline bool |
94 | __is_heap(_RandomAccessIterator __first, _Distance __n) |
95 | { |
96 | __gnu_cxx::__ops::_Iter_less_iter __comp; |
97 | return std::__is_heap_until(__first, __n, __comp) == __n; |
98 | } |
99 | |
100 | template<typename _RandomAccessIterator, typename _Compare, |
101 | typename _Distance> |
102 | _GLIBCXX20_CONSTEXPR |
103 | inline bool |
104 | __is_heap(_RandomAccessIterator __first, _Compare __comp, _Distance __n) |
105 | { |
106 | typedef __decltype(__comp) _Cmp; |
107 | __gnu_cxx::__ops::_Iter_comp_iter<_Cmp> __cmp(_GLIBCXX_MOVE(__comp)); |
108 | return std::__is_heap_until(__first, __n, __cmp) == __n; |
109 | } |
110 | |
111 | template<typename _RandomAccessIterator> |
112 | _GLIBCXX20_CONSTEXPR |
113 | inline bool |
114 | __is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) |
115 | { return std::__is_heap(__first, std::distance(__first, __last)); } |
116 | |
117 | template<typename _RandomAccessIterator, typename _Compare> |
118 | _GLIBCXX20_CONSTEXPR |
119 | inline bool |
120 | __is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, |
121 | _Compare __comp) |
122 | { |
123 | return std::__is_heap(__first, _GLIBCXX_MOVE(__comp), |
124 | std::distance(__first, __last)); |
125 | } |
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 | typename _Compare> |
132 | _GLIBCXX20_CONSTEXPR |
133 | void |
134 | __push_heap(_RandomAccessIterator __first, |
135 | _Distance __holeIndex, _Distance __topIndex, _Tp __value, |
136 | _Compare& __comp) |
137 | { |
138 | _Distance __parent = (__holeIndex - 1) / 2; |
139 | while (__holeIndex > __topIndex && __comp(__first + __parent, __value)) |
140 | { |
141 | *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __parent)); |
142 | __holeIndex = __parent; |
143 | __parent = (__holeIndex - 1) / 2; |
144 | } |
145 | *(__first + __holeIndex) = _GLIBCXX_MOVE(__value); |
146 | } |
147 | |
148 | /** |
149 | * @brief Push an element onto a heap. |
150 | * @param __first Start of heap. |
151 | * @param __last End of heap + element. |
152 | * @ingroup heap_algorithms |
153 | * |
154 | * This operation pushes the element at last-1 onto the valid heap |
155 | * over the range [__first,__last-1). After completion, |
156 | * [__first,__last) is a valid heap. |
157 | */ |
158 | template<typename _RandomAccessIterator> |
159 | _GLIBCXX20_CONSTEXPR |
160 | inline void |
161 | push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) |
162 | { |
163 | typedef typename iterator_traits<_RandomAccessIterator>::value_type |
164 | _ValueType; |
165 | typedef typename iterator_traits<_RandomAccessIterator>::difference_type |
166 | _DistanceType; |
167 | |
168 | // concept requirements |
169 | __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< |
170 | _RandomAccessIterator>) |
171 | __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>) |
172 | __glibcxx_requires_valid_range(__first, __last); |
173 | __glibcxx_requires_irreflexive(__first, __last); |
174 | __glibcxx_requires_heap(__first, __last - 1); |
175 | |
176 | __gnu_cxx::__ops::_Iter_less_val __comp; |
177 | _ValueType __value = _GLIBCXX_MOVE(*(__last - 1)); |
178 | std::__push_heap(__first, _DistanceType((__last - __first) - 1), |
179 | _DistanceType(0), _GLIBCXX_MOVE(__value), __comp); |
180 | } |
181 | |
182 | /** |
183 | * @brief Push an element onto a heap using comparison functor. |
184 | * @param __first Start of heap. |
185 | * @param __last End of heap + element. |
186 | * @param __comp Comparison functor. |
187 | * @ingroup heap_algorithms |
188 | * |
189 | * This operation pushes the element at __last-1 onto the valid |
190 | * heap over the range [__first,__last-1). After completion, |
191 | * [__first,__last) is a valid heap. Compare operations are |
192 | * performed using comp. |
193 | */ |
194 | template<typename _RandomAccessIterator, typename _Compare> |
195 | _GLIBCXX20_CONSTEXPR |
196 | inline void |
197 | push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, |
198 | _Compare __comp) |
199 | { |
200 | typedef typename iterator_traits<_RandomAccessIterator>::value_type |
201 | _ValueType; |
202 | typedef typename iterator_traits<_RandomAccessIterator>::difference_type |
203 | _DistanceType; |
204 | |
205 | // concept requirements |
206 | __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< |
207 | _RandomAccessIterator>) |
208 | __glibcxx_requires_valid_range(__first, __last); |
209 | __glibcxx_requires_irreflexive_pred(__first, __last, __comp); |
210 | __glibcxx_requires_heap_pred(__first, __last - 1, __comp); |
211 | |
212 | __decltype(__gnu_cxx::__ops::__iter_comp_val(_GLIBCXX_MOVE(__comp))) |
213 | __cmp(_GLIBCXX_MOVE(__comp)); |
214 | _ValueType __value = _GLIBCXX_MOVE(*(__last - 1)); |
215 | std::__push_heap(__first, _DistanceType((__last - __first) - 1), |
216 | _DistanceType(0), _GLIBCXX_MOVE(__value), __cmp); |
217 | } |
218 | |
219 | template<typename _RandomAccessIterator, typename _Distance, |
220 | typename _Tp, typename _Compare> |
221 | _GLIBCXX20_CONSTEXPR |
222 | void |
223 | __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex, |
224 | _Distance __len, _Tp __value, _Compare __comp) |
225 | { |
226 | const _Distance __topIndex = __holeIndex; |
227 | _Distance __secondChild = __holeIndex; |
228 | while (__secondChild < (__len - 1) / 2) |
229 | { |
230 | __secondChild = 2 * (__secondChild + 1); |
231 | if (__comp(__first + __secondChild, |
232 | __first + (__secondChild - 1))) |
233 | __secondChild--; |
234 | *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __secondChild)); |
235 | __holeIndex = __secondChild; |
236 | } |
237 | if ((__len & 1) == 0 && __secondChild == (__len - 2) / 2) |
238 | { |
239 | __secondChild = 2 * (__secondChild + 1); |
240 | *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first |
241 | + (__secondChild - 1))); |
242 | __holeIndex = __secondChild - 1; |
243 | } |
244 | __decltype(__gnu_cxx::__ops::__iter_comp_val(_GLIBCXX_MOVE(__comp))) |
245 | __cmp(_GLIBCXX_MOVE(__comp)); |
246 | std::__push_heap(__first, __holeIndex, __topIndex, |
247 | _GLIBCXX_MOVE(__value), __cmp); |
248 | } |
249 | |
250 | template<typename _RandomAccessIterator, typename _Compare> |
251 | _GLIBCXX20_CONSTEXPR |
252 | inline void |
253 | __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, |
254 | _RandomAccessIterator __result, _Compare& __comp) |
255 | { |
256 | typedef typename iterator_traits<_RandomAccessIterator>::value_type |
257 | _ValueType; |
258 | typedef typename iterator_traits<_RandomAccessIterator>::difference_type |
259 | _DistanceType; |
260 | |
261 | _ValueType __value = _GLIBCXX_MOVE(*__result); |
262 | *__result = _GLIBCXX_MOVE(*__first); |
263 | std::__adjust_heap(__first, _DistanceType(0), |
264 | _DistanceType(__last - __first), |
265 | _GLIBCXX_MOVE(__value), __comp); |
266 | } |
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 | _GLIBCXX20_CONSTEXPR |
281 | inline void |
282 | pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) |
283 | { |
284 | // concept requirements |
285 | __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< |
286 | _RandomAccessIterator>) |
287 | __glibcxx_function_requires(_LessThanComparableConcept< |
288 | typename iterator_traits<_RandomAccessIterator>::value_type>) |
289 | __glibcxx_requires_non_empty_range(__first, __last); |
290 | __glibcxx_requires_valid_range(__first, __last); |
291 | __glibcxx_requires_irreflexive(__first, __last); |
292 | __glibcxx_requires_heap(__first, __last); |
293 | |
294 | if (__last - __first > 1) |
295 | { |
296 | --__last; |
297 | __gnu_cxx::__ops::_Iter_less_iter __comp; |
298 | std::__pop_heap(__first, __last, __last, __comp); |
299 | } |
300 | } |
301 | |
302 | /** |
303 | * @brief Pop an element off a heap using comparison functor. |
304 | * @param __first Start of heap. |
305 | * @param __last End of heap. |
306 | * @param __comp Comparison functor to use. |
307 | * @ingroup heap_algorithms |
308 | * |
309 | * This operation pops the top of the heap. The elements __first |
310 | * and __last-1 are swapped and [__first,__last-1) is made into a |
311 | * heap. Comparisons are made using comp. |
312 | */ |
313 | template<typename _RandomAccessIterator, typename _Compare> |
314 | _GLIBCXX20_CONSTEXPR |
315 | inline void |
316 | pop_heap(_RandomAccessIterator __first, |
317 | _RandomAccessIterator __last, _Compare __comp) |
318 | { |
319 | // concept requirements |
320 | __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< |
321 | _RandomAccessIterator>) |
322 | __glibcxx_requires_valid_range(__first, __last); |
323 | __glibcxx_requires_irreflexive_pred(__first, __last, __comp); |
324 | __glibcxx_requires_non_empty_range(__first, __last); |
325 | __glibcxx_requires_heap_pred(__first, __last, __comp); |
326 | |
327 | if (__last - __first > 1) |
328 | { |
329 | typedef __decltype(__comp) _Cmp; |
330 | __gnu_cxx::__ops::_Iter_comp_iter<_Cmp> __cmp(_GLIBCXX_MOVE(__comp)); |
331 | --__last; |
332 | std::__pop_heap(__first, __last, __last, __cmp); |
333 | } |
334 | } |
335 | |
336 | template<typename _RandomAccessIterator, typename _Compare> |
337 | _GLIBCXX20_CONSTEXPR |
338 | void |
339 | __make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, |
340 | _Compare& __comp) |
341 | { |
342 | typedef typename iterator_traits<_RandomAccessIterator>::value_type |
343 | _ValueType; |
344 | typedef typename iterator_traits<_RandomAccessIterator>::difference_type |
345 | _DistanceType; |
346 | |
347 | if (__last - __first < 2) |
348 | return; |
349 | |
350 | const _DistanceType __len = __last - __first; |
351 | _DistanceType __parent = (__len - 2) / 2; |
352 | while (true) |
353 | { |
354 | _ValueType __value = _GLIBCXX_MOVE(*(__first + __parent)); |
355 | std::__adjust_heap(__first, __parent, __len, _GLIBCXX_MOVE(__value), |
356 | __comp); |
357 | if (__parent == 0) |
358 | return; |
359 | __parent--; |
360 | } |
361 | } |
362 | |
363 | /** |
364 | * @brief Construct a heap over a range. |
365 | * @param __first Start of heap. |
366 | * @param __last End of heap. |
367 | * @ingroup heap_algorithms |
368 | * |
369 | * This operation makes the elements in [__first,__last) into a heap. |
370 | */ |
371 | template<typename _RandomAccessIterator> |
372 | _GLIBCXX20_CONSTEXPR |
373 | inline void |
374 | make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) |
375 | { |
376 | // concept requirements |
377 | __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< |
378 | _RandomAccessIterator>) |
379 | __glibcxx_function_requires(_LessThanComparableConcept< |
380 | typename iterator_traits<_RandomAccessIterator>::value_type>) |
381 | __glibcxx_requires_valid_range(__first, __last); |
382 | __glibcxx_requires_irreflexive(__first, __last); |
383 | |
384 | __gnu_cxx::__ops::_Iter_less_iter __comp; |
385 | std::__make_heap(__first, __last, __comp); |
386 | } |
387 | |
388 | /** |
389 | * @brief Construct a heap over a range using comparison functor. |
390 | * @param __first Start of heap. |
391 | * @param __last End of heap. |
392 | * @param __comp Comparison functor to use. |
393 | * @ingroup heap_algorithms |
394 | * |
395 | * This operation makes the elements in [__first,__last) into a heap. |
396 | * Comparisons are made using __comp. |
397 | */ |
398 | template<typename _RandomAccessIterator, typename _Compare> |
399 | _GLIBCXX20_CONSTEXPR |
400 | inline void |
401 | make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, |
402 | _Compare __comp) |
403 | { |
404 | // concept requirements |
405 | __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< |
406 | _RandomAccessIterator>) |
407 | __glibcxx_requires_valid_range(__first, __last); |
408 | __glibcxx_requires_irreflexive_pred(__first, __last, __comp); |
409 | |
410 | typedef __decltype(__comp) _Cmp; |
411 | __gnu_cxx::__ops::_Iter_comp_iter<_Cmp> __cmp(_GLIBCXX_MOVE(__comp)); |
412 | std::__make_heap(__first, __last, __cmp); |
413 | } |
414 | |
415 | template<typename _RandomAccessIterator, typename _Compare> |
416 | _GLIBCXX20_CONSTEXPR |
417 | void |
418 | __sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, |
419 | _Compare& __comp) |
420 | { |
421 | while (__last - __first > 1) |
422 | { |
423 | --__last; |
424 | std::__pop_heap(__first, __last, __last, __comp); |
425 | } |
426 | } |
427 | |
428 | /** |
429 | * @brief Sort a heap. |
430 | * @param __first Start of heap. |
431 | * @param __last End of heap. |
432 | * @ingroup heap_algorithms |
433 | * |
434 | * This operation sorts the valid heap in the range [__first,__last). |
435 | */ |
436 | template<typename _RandomAccessIterator> |
437 | _GLIBCXX20_CONSTEXPR |
438 | inline void |
439 | sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) |
440 | { |
441 | // concept requirements |
442 | __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< |
443 | _RandomAccessIterator>) |
444 | __glibcxx_function_requires(_LessThanComparableConcept< |
445 | typename iterator_traits<_RandomAccessIterator>::value_type>) |
446 | __glibcxx_requires_valid_range(__first, __last); |
447 | __glibcxx_requires_irreflexive(__first, __last); |
448 | __glibcxx_requires_heap(__first, __last); |
449 | |
450 | __gnu_cxx::__ops::_Iter_less_iter __comp; |
451 | std::__sort_heap(__first, __last, __comp); |
452 | } |
453 | |
454 | /** |
455 | * @brief Sort a heap using comparison functor. |
456 | * @param __first Start of heap. |
457 | * @param __last End of heap. |
458 | * @param __comp Comparison functor to use. |
459 | * @ingroup heap_algorithms |
460 | * |
461 | * This operation sorts the valid heap in the range [__first,__last). |
462 | * Comparisons are made using __comp. |
463 | */ |
464 | template<typename _RandomAccessIterator, typename _Compare> |
465 | _GLIBCXX20_CONSTEXPR |
466 | inline void |
467 | sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, |
468 | _Compare __comp) |
469 | { |
470 | // concept requirements |
471 | __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< |
472 | _RandomAccessIterator>) |
473 | __glibcxx_requires_valid_range(__first, __last); |
474 | __glibcxx_requires_irreflexive_pred(__first, __last, __comp); |
475 | __glibcxx_requires_heap_pred(__first, __last, __comp); |
476 | |
477 | typedef __decltype(__comp) _Cmp; |
478 | __gnu_cxx::__ops::_Iter_comp_iter<_Cmp> __cmp(_GLIBCXX_MOVE(__comp)); |
479 | std::__sort_heap(__first, __last, __cmp); |
480 | } |
481 | |
482 | #if __cplusplus >= 201103L |
483 | /** |
484 | * @brief Search the end of a heap. |
485 | * @param __first Start of range. |
486 | * @param __last End of range. |
487 | * @return An iterator pointing to the first element not in the heap. |
488 | * @ingroup heap_algorithms |
489 | * |
490 | * This operation returns the last iterator i in [__first, __last) for which |
491 | * the range [__first, i) is a heap. |
492 | */ |
493 | template<typename _RandomAccessIterator> |
494 | _GLIBCXX20_CONSTEXPR |
495 | inline _RandomAccessIterator |
496 | is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last) |
497 | { |
498 | // concept requirements |
499 | __glibcxx_function_requires(_RandomAccessIteratorConcept< |
500 | _RandomAccessIterator>) |
501 | __glibcxx_function_requires(_LessThanComparableConcept< |
502 | typename iterator_traits<_RandomAccessIterator>::value_type>) |
503 | __glibcxx_requires_valid_range(__first, __last); |
504 | __glibcxx_requires_irreflexive(__first, __last); |
505 | |
506 | __gnu_cxx::__ops::_Iter_less_iter __comp; |
507 | return __first + |
508 | std::__is_heap_until(__first, std::distance(__first, __last), __comp); |
509 | } |
510 | |
511 | /** |
512 | * @brief Search the end of a heap using comparison functor. |
513 | * @param __first Start of range. |
514 | * @param __last End of range. |
515 | * @param __comp Comparison functor to use. |
516 | * @return An iterator pointing to the first element not in the heap. |
517 | * @ingroup heap_algorithms |
518 | * |
519 | * This operation returns the last iterator i in [__first, __last) for which |
520 | * the range [__first, i) is a heap. Comparisons are made using __comp. |
521 | */ |
522 | template<typename _RandomAccessIterator, typename _Compare> |
523 | _GLIBCXX20_CONSTEXPR |
524 | inline _RandomAccessIterator |
525 | is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last, |
526 | _Compare __comp) |
527 | { |
528 | // concept requirements |
529 | __glibcxx_function_requires(_RandomAccessIteratorConcept< |
530 | _RandomAccessIterator>) |
531 | __glibcxx_requires_valid_range(__first, __last); |
532 | __glibcxx_requires_irreflexive_pred(__first, __last, __comp); |
533 | |
534 | typedef __decltype(__comp) _Cmp; |
535 | __gnu_cxx::__ops::_Iter_comp_iter<_Cmp> __cmp(_GLIBCXX_MOVE(__comp)); |
536 | return __first |
537 | + std::__is_heap_until(__first, std::distance(__first, __last), __cmp); |
538 | } |
539 | |
540 | /** |
541 | * @brief Determines whether a range is a heap. |
542 | * @param __first Start of range. |
543 | * @param __last End of range. |
544 | * @return True if range is a heap, false otherwise. |
545 | * @ingroup heap_algorithms |
546 | */ |
547 | template<typename _RandomAccessIterator> |
548 | _GLIBCXX20_CONSTEXPR |
549 | inline bool |
550 | is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) |
551 | { return std::is_heap_until(__first, __last) == __last; } |
552 | |
553 | /** |
554 | * @brief Determines whether a range is a heap using comparison functor. |
555 | * @param __first Start of range. |
556 | * @param __last End of range. |
557 | * @param __comp Comparison functor to use. |
558 | * @return True if range is a heap, false otherwise. |
559 | * @ingroup heap_algorithms |
560 | */ |
561 | template<typename _RandomAccessIterator, typename _Compare> |
562 | _GLIBCXX20_CONSTEXPR |
563 | inline bool |
564 | is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, |
565 | _Compare __comp) |
566 | { |
567 | // concept requirements |
568 | __glibcxx_function_requires(_RandomAccessIteratorConcept< |
569 | _RandomAccessIterator>) |
570 | __glibcxx_requires_valid_range(__first, __last); |
571 | __glibcxx_requires_irreflexive_pred(__first, __last, __comp); |
572 | |
573 | const auto __dist = std::distance(__first, __last); |
574 | typedef __decltype(__comp) _Cmp; |
575 | __gnu_cxx::__ops::_Iter_comp_iter<_Cmp> __cmp(_GLIBCXX_MOVE(__comp)); |
576 | return std::__is_heap_until(__first, __dist, __cmp) == __dist; |
577 | } |
578 | #endif |
579 | |
580 | _GLIBCXX_END_NAMESPACE_VERSION |
581 | } // namespace |
582 | |
583 | #endif /* _STL_HEAP_H */ |
584 | |