1// Heap implementation -*- C++ -*- 2 3// Copyright (C) 2001-2020 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 _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