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