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