1 // Heap implementation -*- C++ -*- 2 3 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 4 // 2011 Free Software Foundation, Inc. 5 // 6 // This file is part of the GNU ISO C++ Library. This library is free 7 // software; you can redistribute it and/or modify it under the 8 // terms of the GNU General Public License as published by the 9 // Free Software Foundation; either version 3, or (at your option) 10 // any later version. 11 12 // This library is distributed in the hope that it will be useful, 13 // but WITHOUT ANY WARRANTY; without even the implied warranty of 14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15 // GNU General Public License for more details. 16 17 // Under Section 7 of GPL version 3, you are granted additional 18 // permissions described in the GCC Runtime Library Exception, version 19 // 3.1, as published by the Free Software Foundation. 20 21 // You should have received a copy of the GNU General Public License and 22 // a copy of the GCC Runtime Library Exception along with this program; 23 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 24 // <http://www.gnu.org/licenses/>. 25 26 /* 27 * 28 * Copyright (c) 1994 29 * Hewlett-Packard Company 30 * 31 * Permission to use, copy, modify, distribute and sell this software 32 * and its documentation for any purpose is hereby granted without fee, 33 * provided that the above copyright notice appear in all copies and 34 * that both that copyright notice and this permission notice appear 35 * in supporting documentation. Hewlett-Packard Company makes no 36 * representations about the suitability of this software for any 37 * purpose. It is provided "as is" without express or implied warranty. 38 * 39 * Copyright (c) 1997 40 * Silicon Graphics Computer Systems, Inc. 41 * 42 * Permission to use, copy, modify, distribute and sell this software 43 * and its documentation for any purpose is hereby granted without fee, 44 * provided that the above copyright notice appear in all copies and 45 * that both that copyright notice and this permission notice appear 46 * in supporting documentation. Silicon Graphics makes no 47 * representations about the suitability of this software for any 48 * purpose. It is provided "as is" without express or implied warranty. 49 */ 50 51 /** @file bits/stl_heap.h 52 * This is an internal header file, included by other library headers. 53 * Do not attempt to use it directly. @headername{queue} 54 */ 55 56 #ifndef _STL_HEAP_H 57 #define _STL_HEAP_H 1 58 59 #include <debug/debug.h> 60 #include <bits/move.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 _Distance 73 __is_heap_until(_RandomAccessIterator __first, _Distance __n) 74 { 75 _Distance __parent = 0; 76 for (_Distance __child = 1; __child < __n; ++__child) 77 { 78 if (__first[__parent] < __first[__child]) 79 return __child; 80 if ((__child & 1) == 0) 81 ++__parent; 82 } 83 return __n; 84 } 85 86 template<typename _RandomAccessIterator, typename _Distance, 87 typename _Compare> 88 _Distance 89 __is_heap_until(_RandomAccessIterator __first, _Distance __n, 90 _Compare __comp) 91 { 92 _Distance __parent = 0; 93 for (_Distance __child = 1; __child < __n; ++__child) 94 { 95 if (__comp(__first[__parent], __first[__child])) 96 return __child; 97 if ((__child & 1) == 0) 98 ++__parent; 99 } 100 return __n; 101 } 102 103 // __is_heap, a predicate testing whether or not a range is a heap. 104 // This function is an extension, not part of the C++ standard. 105 template<typename _RandomAccessIterator, typename _Distance> 106 inline bool 107 __is_heap(_RandomAccessIterator __first, _Distance __n) 108 { return std::__is_heap_until(__first, __n) == __n; } 109 110 template<typename _RandomAccessIterator, typename _Compare, 111 typename _Distance> 112 inline bool 113 __is_heap(_RandomAccessIterator __first, _Compare __comp, _Distance __n) 114 { return std::__is_heap_until(__first, __n, __comp) == __n; } 115 116 template<typename _RandomAccessIterator> 117 inline bool 118 __is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) 119 { return std::__is_heap(__first, std::distance(__first, __last)); } 120 121 template<typename _RandomAccessIterator, typename _Compare> 122 inline bool 123 __is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, 124 _Compare __comp) 125 { return std::__is_heap(__first, __comp, std::distance(__first, __last)); } 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 void 132 __push_heap(_RandomAccessIterator __first, 133 _Distance __holeIndex, _Distance __topIndex, _Tp __value) 134 { 135 _Distance __parent = (__holeIndex - 1) / 2; 136 while (__holeIndex > __topIndex && *(__first + __parent) < __value) 137 { 138 *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __parent)); 139 __holeIndex = __parent; 140 __parent = (__holeIndex - 1) / 2; 141 } 142 *(__first + __holeIndex) = _GLIBCXX_MOVE(__value); 143 } 144 145 /** 146 * @brief Push an element onto a heap. 147 * @param __first Start of heap. 148 * @param __last End of heap + element. 149 * @ingroup heap_algorithms 150 * 151 * This operation pushes the element at last-1 onto the valid heap 152 * over the range [__first,__last-1). After completion, 153 * [__first,__last) is a valid heap. 154 */ 155 template<typename _RandomAccessIterator> 156 inline void 157 push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) 158 { 159 typedef typename iterator_traits<_RandomAccessIterator>::value_type 160 _ValueType; 161 typedef typename iterator_traits<_RandomAccessIterator>::difference_type 162 _DistanceType; 163 164 // concept requirements 165 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 166 _RandomAccessIterator>) 167 __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>) 168 __glibcxx_requires_valid_range(__first, __last); 169 __glibcxx_requires_heap(__first, __last - 1); 170 171 _ValueType __value = _GLIBCXX_MOVE(*(__last - 1)); 172 std::__push_heap(__first, _DistanceType((__last - __first) - 1), 173 _DistanceType(0), _GLIBCXX_MOVE(__value)); 174 } 175 176 template<typename _RandomAccessIterator, typename _Distance, typename _Tp, 177 typename _Compare> 178 void 179 __push_heap(_RandomAccessIterator __first, _Distance __holeIndex, 180 _Distance __topIndex, _Tp __value, _Compare __comp) 181 { 182 _Distance __parent = (__holeIndex - 1) / 2; 183 while (__holeIndex > __topIndex 184 && __comp(*(__first + __parent), __value)) 185 { 186 *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __parent)); 187 __holeIndex = __parent; 188 __parent = (__holeIndex - 1) / 2; 189 } 190 *(__first + __holeIndex) = _GLIBCXX_MOVE(__value); 191 } 192 193 /** 194 * @brief Push an element onto a heap using comparison functor. 195 * @param __first Start of heap. 196 * @param __last End of heap + element. 197 * @param __comp Comparison functor. 198 * @ingroup heap_algorithms 199 * 200 * This operation pushes the element at __last-1 onto the valid 201 * heap over the range [__first,__last-1). After completion, 202 * [__first,__last) is a valid heap. Compare operations are 203 * performed using comp. 204 */ 205 template<typename _RandomAccessIterator, typename _Compare> 206 inline void 207 push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, 208 _Compare __comp) 209 { 210 typedef typename iterator_traits<_RandomAccessIterator>::value_type 211 _ValueType; 212 typedef typename iterator_traits<_RandomAccessIterator>::difference_type 213 _DistanceType; 214 215 // concept requirements 216 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 217 _RandomAccessIterator>) 218 __glibcxx_requires_valid_range(__first, __last); 219 __glibcxx_requires_heap_pred(__first, __last - 1, __comp); 220 221 _ValueType __value = _GLIBCXX_MOVE(*(__last - 1)); 222 std::__push_heap(__first, _DistanceType((__last - __first) - 1), 223 _DistanceType(0), _GLIBCXX_MOVE(__value), __comp); 224 } 225 226 template<typename _RandomAccessIterator, typename _Distance, typename _Tp> 227 void 228 __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex, 229 _Distance __len, _Tp __value) 230 { 231 const _Distance __topIndex = __holeIndex; 232 _Distance __secondChild = __holeIndex; 233 while (__secondChild < (__len - 1) / 2) 234 { 235 __secondChild = 2 * (__secondChild + 1); 236 if (*(__first + __secondChild) < *(__first + (__secondChild - 1))) 237 __secondChild--; 238 *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __secondChild)); 239 __holeIndex = __secondChild; 240 } 241 if ((__len & 1) == 0 && __secondChild == (__len - 2) / 2) 242 { 243 __secondChild = 2 * (__secondChild + 1); 244 *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first 245 + (__secondChild - 1))); 246 __holeIndex = __secondChild - 1; 247 } 248 std::__push_heap(__first, __holeIndex, __topIndex, 249 _GLIBCXX_MOVE(__value)); 250 } 251 252 template<typename _RandomAccessIterator> 253 inline void 254 __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, 255 _RandomAccessIterator __result) 256 { 257 typedef typename iterator_traits<_RandomAccessIterator>::value_type 258 _ValueType; 259 typedef typename iterator_traits<_RandomAccessIterator>::difference_type 260 _DistanceType; 261 262 _ValueType __value = _GLIBCXX_MOVE(*__result); 263 *__result = _GLIBCXX_MOVE(*__first); 264 std::__adjust_heap(__first, _DistanceType(0), 265 _DistanceType(__last - __first), 266 _GLIBCXX_MOVE(__value)); 267 } 268 269 /** 270 * @brief Pop an element off a heap. 271 * @param __first Start of heap. 272 * @param __last End of heap. 273 * @pre [__first, __last) is a valid, non-empty range. 274 * @ingroup heap_algorithms 275 * 276 * This operation pops the top of the heap. The elements __first 277 * and __last-1 are swapped and [__first,__last-1) is made into a 278 * heap. 279 */ 280 template<typename _RandomAccessIterator> 281 inline void 282 pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) 283 { 284 typedef typename iterator_traits<_RandomAccessIterator>::value_type 285 _ValueType; 286 287 // concept requirements 288 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 289 _RandomAccessIterator>) 290 __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>) 291 __glibcxx_requires_non_empty_range(__first, __last); 292 __glibcxx_requires_valid_range(__first, __last); 293 __glibcxx_requires_heap(__first, __last); 294 295 --__last; 296 std::__pop_heap(__first, __last, __last); 297 } 298 299 template<typename _RandomAccessIterator, typename _Distance, 300 typename _Tp, typename _Compare> 301 void 302 __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex, 303 _Distance __len, _Tp __value, _Compare __comp) 304 { 305 const _Distance __topIndex = __holeIndex; 306 _Distance __secondChild = __holeIndex; 307 while (__secondChild < (__len - 1) / 2) 308 { 309 __secondChild = 2 * (__secondChild + 1); 310 if (__comp(*(__first + __secondChild), 311 *(__first + (__secondChild - 1)))) 312 __secondChild--; 313 *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __secondChild)); 314 __holeIndex = __secondChild; 315 } 316 if ((__len & 1) == 0 && __secondChild == (__len - 2) / 2) 317 { 318 __secondChild = 2 * (__secondChild + 1); 319 *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first 320 + (__secondChild - 1))); 321 __holeIndex = __secondChild - 1; 322 } 323 std::__push_heap(__first, __holeIndex, __topIndex, 324 _GLIBCXX_MOVE(__value), __comp); 325 } 326 327 template<typename _RandomAccessIterator, typename _Compare> 328 inline void 329 __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, 330 _RandomAccessIterator __result, _Compare __comp) 331 { 332 typedef typename iterator_traits<_RandomAccessIterator>::value_type 333 _ValueType; 334 typedef typename iterator_traits<_RandomAccessIterator>::difference_type 335 _DistanceType; 336 337 _ValueType __value = _GLIBCXX_MOVE(*__result); 338 *__result = _GLIBCXX_MOVE(*__first); 339 std::__adjust_heap(__first, _DistanceType(0), 340 _DistanceType(__last - __first), 341 _GLIBCXX_MOVE(__value), __comp); 342 } 343 344 /** 345 * @brief Pop an element off a heap using comparison functor. 346 * @param __first Start of heap. 347 * @param __last End of heap. 348 * @param __comp Comparison functor to use. 349 * @ingroup heap_algorithms 350 * 351 * This operation pops the top of the heap. The elements __first 352 * and __last-1 are swapped and [__first,__last-1) is made into a 353 * heap. Comparisons are made using comp. 354 */ 355 template<typename _RandomAccessIterator, typename _Compare> 356 inline void 357 pop_heap(_RandomAccessIterator __first, 358 _RandomAccessIterator __last, _Compare __comp) 359 { 360 // concept requirements 361 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 362 _RandomAccessIterator>) 363 __glibcxx_requires_valid_range(__first, __last); 364 __glibcxx_requires_non_empty_range(__first, __last); 365 __glibcxx_requires_heap_pred(__first, __last, __comp); 366 367 --__last; 368 std::__pop_heap(__first, __last, __last, __comp); 369 } 370 371 /** 372 * @brief Construct a heap over a range. 373 * @param __first Start of heap. 374 * @param __last End of heap. 375 * @ingroup heap_algorithms 376 * 377 * This operation makes the elements in [__first,__last) into a heap. 378 */ 379 template<typename _RandomAccessIterator> 380 void 381 make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) 382 { 383 typedef typename iterator_traits<_RandomAccessIterator>::value_type 384 _ValueType; 385 typedef typename iterator_traits<_RandomAccessIterator>::difference_type 386 _DistanceType; 387 388 // concept requirements 389 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 390 _RandomAccessIterator>) 391 __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>) 392 __glibcxx_requires_valid_range(__first, __last); 393 394 if (__last - __first < 2) 395 return; 396 397 const _DistanceType __len = __last - __first; 398 _DistanceType __parent = (__len - 2) / 2; 399 while (true) 400 { 401 _ValueType __value = _GLIBCXX_MOVE(*(__first + __parent)); 402 std::__adjust_heap(__first, __parent, __len, _GLIBCXX_MOVE(__value)); 403 if (__parent == 0) 404 return; 405 __parent--; 406 } 407 } 408 409 /** 410 * @brief Construct a heap over a range using comparison functor. 411 * @param __first Start of heap. 412 * @param __last End of heap. 413 * @param __comp Comparison functor to use. 414 * @ingroup heap_algorithms 415 * 416 * This operation makes the elements in [__first,__last) into a heap. 417 * Comparisons are made using __comp. 418 */ 419 template<typename _RandomAccessIterator, typename _Compare> 420 void 421 make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, 422 _Compare __comp) 423 { 424 typedef typename iterator_traits<_RandomAccessIterator>::value_type 425 _ValueType; 426 typedef typename iterator_traits<_RandomAccessIterator>::difference_type 427 _DistanceType; 428 429 // concept requirements 430 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 431 _RandomAccessIterator>) 432 __glibcxx_requires_valid_range(__first, __last); 433 434 if (__last - __first < 2) 435 return; 436 437 const _DistanceType __len = __last - __first; 438 _DistanceType __parent = (__len - 2) / 2; 439 while (true) 440 { 441 _ValueType __value = _GLIBCXX_MOVE(*(__first + __parent)); 442 std::__adjust_heap(__first, __parent, __len, _GLIBCXX_MOVE(__value), 443 __comp); 444 if (__parent == 0) 445 return; 446 __parent--; 447 } 448 } 449 450 /** 451 * @brief Sort a heap. 452 * @param __first Start of heap. 453 * @param __last End of heap. 454 * @ingroup heap_algorithms 455 * 456 * This operation sorts the valid heap in the range [__first,__last). 457 */ 458 template<typename _RandomAccessIterator> 459 void 460 sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) 461 { 462 // concept requirements 463 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 464 _RandomAccessIterator>) 465 __glibcxx_function_requires(_LessThanComparableConcept< 466 typename iterator_traits<_RandomAccessIterator>::value_type>) 467 __glibcxx_requires_valid_range(__first, __last); 468 __glibcxx_requires_heap(__first, __last); 469 470 while (__last - __first > 1) 471 { 472 --__last; 473 std::__pop_heap(__first, __last, __last); 474 } 475 } 476 477 /** 478 * @brief Sort a heap using comparison functor. 479 * @param __first Start of heap. 480 * @param __last End of heap. 481 * @param __comp Comparison functor to use. 482 * @ingroup heap_algorithms 483 * 484 * This operation sorts the valid heap in the range [__first,__last). 485 * Comparisons are made using __comp. 486 */ 487 template<typename _RandomAccessIterator, typename _Compare> 488 void 489 sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, 490 _Compare __comp) 491 { 492 // concept requirements 493 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 494 _RandomAccessIterator>) 495 __glibcxx_requires_valid_range(__first, __last); 496 __glibcxx_requires_heap_pred(__first, __last, __comp); 497 498 while (__last - __first > 1) 499 { 500 --__last; 501 std::__pop_heap(__first, __last, __last, __comp); 502 } 503 } 504 505 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 506 /** 507 * @brief Search the end of a heap. 508 * @param __first Start of range. 509 * @param __last End of range. 510 * @return An iterator pointing to the first element not in the heap. 511 * @ingroup heap_algorithms 512 * 513 * This operation returns the last iterator i in [__first, __last) for which 514 * the range [__first, i) is a heap. 515 */ 516 template<typename _RandomAccessIterator> 517 inline _RandomAccessIterator 518 is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last) 519 { 520 // concept requirements 521 __glibcxx_function_requires(_RandomAccessIteratorConcept< 522 _RandomAccessIterator>) 523 __glibcxx_function_requires(_LessThanComparableConcept< 524 typename iterator_traits<_RandomAccessIterator>::value_type>) 525 __glibcxx_requires_valid_range(__first, __last); 526 527 return __first + std::__is_heap_until(__first, std::distance(__first, 528 __last)); 529 } 530 531 /** 532 * @brief Search the end of a heap using comparison functor. 533 * @param __first Start of range. 534 * @param __last End of range. 535 * @param __comp Comparison functor to use. 536 * @return An iterator pointing to the first element not in the heap. 537 * @ingroup heap_algorithms 538 * 539 * This operation returns the last iterator i in [__first, __last) for which 540 * the range [__first, i) is a heap. Comparisons are made using __comp. 541 */ 542 template<typename _RandomAccessIterator, typename _Compare> 543 inline _RandomAccessIterator 544 is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last, 545 _Compare __comp) 546 { 547 // concept requirements 548 __glibcxx_function_requires(_RandomAccessIteratorConcept< 549 _RandomAccessIterator>) 550 __glibcxx_requires_valid_range(__first, __last); 551 552 return __first + std::__is_heap_until(__first, std::distance(__first, 553 __last), 554 __comp); 555 } 556 557 /** 558 * @brief Determines whether a range is a heap. 559 * @param __first Start of range. 560 * @param __last End of range. 561 * @return True if range is a heap, false otherwise. 562 * @ingroup heap_algorithms 563 */ 564 template<typename _RandomAccessIterator> 565 inline bool 566 is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) 567 { return std::is_heap_until(__first, __last) == __last; } 568 569 /** 570 * @brief Determines whether a range is a heap using comparison functor. 571 * @param __first Start of range. 572 * @param __last End of range. 573 * @param __comp Comparison functor to use. 574 * @return True if range is a heap, false otherwise. 575 * @ingroup heap_algorithms 576 */ 577 template<typename _RandomAccessIterator, typename _Compare> 578 inline bool 579 is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, 580 _Compare __comp) 581 { return std::is_heap_until(__first, __last, __comp) == __last; } 582 #endif 583 584 _GLIBCXX_END_NAMESPACE_VERSION 585 } // namespace 586 587 #endif /* _STL_HEAP_H */ 588
