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