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