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