1// Heap implementation -*- C++ -*- 2 3// Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009 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 stl_heap.h 52 * This is an internal header file, included by other library headers. 53 * You should not attempt to use it directly. 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_GLIBCXX_BEGIN_NAMESPACE(std) 63 64 /** 65 * @defgroup heap_algorithms Heap 66 * @ingroup sorting_algorithms 67 */ 68 69 template<typename _RandomAccessIterator, typename _Distance> 70 _Distance 71 __is_heap_until(_RandomAccessIterator __first, _Distance __n) 72 { 73 _Distance __parent = 0; 74 for (_Distance __child = 1; __child < __n; ++__child) 75 { 76 if (__first[__parent] < __first[__child]) 77 return __child; 78 if ((__child & 1) == 0) 79 ++__parent; 80 } 81 return __n; 82 } 83 84 template<typename _RandomAccessIterator, typename _Distance, 85 typename _Compare> 86 _Distance 87 __is_heap_until(_RandomAccessIterator __first, _Distance __n, 88 _Compare __comp) 89 { 90 _Distance __parent = 0; 91 for (_Distance __child = 1; __child < __n; ++__child) 92 { 93 if (__comp(__first[__parent], __first[__child])) 94 return __child; 95 if ((__child & 1) == 0) 96 ++__parent; 97 } 98 return __n; 99 } 100 101 // __is_heap, a predicate testing whether or not a range is a heap. 102 // This function is an extension, not part of the C++ standard. 103 template<typename _RandomAccessIterator, typename _Distance> 104 inline bool 105 __is_heap(_RandomAccessIterator __first, _Distance __n) 106 { return std::__is_heap_until(__first, __n) == __n; } 107 108 template<typename _RandomAccessIterator, typename _Compare, 109 typename _Distance> 110 inline bool 111 __is_heap(_RandomAccessIterator __first, _Compare __comp, _Distance __n) 112 { return std::__is_heap_until(__first, __n, __comp) == __n; } 113 114 template<typename _RandomAccessIterator> 115 inline bool 116 __is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) 117 { return std::__is_heap(__first, std::distance(__first, __last)); } 118 119 template<typename _RandomAccessIterator, typename _Compare> 120 inline bool 121 __is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, 122 _Compare __comp) 123 { return std::__is_heap(__first, __comp, std::distance(__first, __last)); } 124 125 // Heap-manipulation functions: push_heap, pop_heap, make_heap, sort_heap, 126 // + is_heap and is_heap_until in C++0x. 127 128 template<typename _RandomAccessIterator, typename _Distance, typename _Tp> 129 void 130 __push_heap(_RandomAccessIterator __first, 131 _Distance __holeIndex, _Distance __topIndex, _Tp __value) 132 { 133 _Distance __parent = (__holeIndex - 1) / 2; 134 while (__holeIndex > __topIndex && *(__first + __parent) < __value) 135 { 136 *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __parent)); 137 __holeIndex = __parent; 138 __parent = (__holeIndex - 1) / 2; 139 } 140 *(__first + __holeIndex) = _GLIBCXX_MOVE(__value); 141 } 142 143 /** 144 * @brief Push an element onto a heap. 145 * @param first Start of heap. 146 * @param last End of heap + element. 147 * @ingroup heap_algorithms 148 * 149 * This operation pushes the element at last-1 onto the valid heap over the 150 * range [first,last-1). After completion, [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_heap(__first, __last - 1); 167 168 _ValueType __value = _GLIBCXX_MOVE(*(__last - 1)); 169 std::__push_heap(__first, _DistanceType((__last - __first) - 1), 170 _DistanceType(0), _GLIBCXX_MOVE(__value)); 171 } 172 173 template<typename _RandomAccessIterator, typename _Distance, typename _Tp, 174 typename _Compare> 175 void 176 __push_heap(_RandomAccessIterator __first, _Distance __holeIndex, 177 _Distance __topIndex, _Tp __value, _Compare __comp) 178 { 179 _Distance __parent = (__holeIndex - 1) / 2; 180 while (__holeIndex > __topIndex 181 && __comp(*(__first + __parent), __value)) 182 { 183 *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __parent)); 184 __holeIndex = __parent; 185 __parent = (__holeIndex - 1) / 2; 186 } 187 *(__first + __holeIndex) = _GLIBCXX_MOVE(__value); 188 } 189 190 /** 191 * @brief Push an element onto a heap using comparison functor. 192 * @param first Start of heap. 193 * @param last End of heap + element. 194 * @param comp Comparison functor. 195 * @ingroup heap_algorithms 196 * 197 * This operation pushes the element at last-1 onto the valid heap over the 198 * range [first,last-1). After completion, [first,last) is a valid heap. 199 * Compare operations are performed using comp. 200 */ 201 template<typename _RandomAccessIterator, typename _Compare> 202 inline void 203 push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, 204 _Compare __comp) 205 { 206 typedef typename iterator_traits<_RandomAccessIterator>::value_type 207 _ValueType; 208 typedef typename iterator_traits<_RandomAccessIterator>::difference_type 209 _DistanceType; 210 211 // concept requirements 212 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 213 _RandomAccessIterator>) 214 __glibcxx_requires_valid_range(__first, __last); 215 __glibcxx_requires_heap_pred(__first, __last - 1, __comp); 216 217 _ValueType __value = _GLIBCXX_MOVE(*(__last - 1)); 218 std::__push_heap(__first, _DistanceType((__last - __first) - 1), 219 _DistanceType(0), _GLIBCXX_MOVE(__value), __comp); 220 } 221 222 template<typename _RandomAccessIterator, typename _Distance, typename _Tp> 223 void 224 __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex, 225 _Distance __len, _Tp __value) 226 { 227 const _Distance __topIndex = __holeIndex; 228 _Distance __secondChild = __holeIndex; 229 while (__secondChild < (__len - 1) / 2) 230 { 231 __secondChild = 2 * (__secondChild + 1); 232 if (*(__first + __secondChild) < *(__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 std::__push_heap(__first, __holeIndex, __topIndex, 245 _GLIBCXX_MOVE(__value)); 246 } 247 248 template<typename _RandomAccessIterator> 249 inline void 250 __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, 251 _RandomAccessIterator __result) 252 { 253 typedef typename iterator_traits<_RandomAccessIterator>::value_type 254 _ValueType; 255 typedef typename iterator_traits<_RandomAccessIterator>::difference_type 256 _DistanceType; 257 258 _ValueType __value = _GLIBCXX_MOVE(*__result); 259 *__result = _GLIBCXX_MOVE(*__first); 260 std::__adjust_heap(__first, _DistanceType(0), 261 _DistanceType(__last - __first), 262 _GLIBCXX_MOVE(__value)); 263 } 264 265 /** 266 * @brief Pop an element off a heap. 267 * @param first Start of heap. 268 * @param last End of heap. 269 * @ingroup heap_algorithms 270 * 271 * This operation pops the top of the heap. The elements first and last-1 272 * are swapped and [first,last-1) is made into a heap. 273 */ 274 template<typename _RandomAccessIterator> 275 inline void 276 pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) 277 { 278 typedef typename iterator_traits<_RandomAccessIterator>::value_type 279 _ValueType; 280 281 // concept requirements 282 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 283 _RandomAccessIterator>) 284 __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>) 285 __glibcxx_requires_valid_range(__first, __last); 286 __glibcxx_requires_heap(__first, __last); 287 288 --__last; 289 std::__pop_heap(__first, __last, __last); 290 } 291 292 template<typename _RandomAccessIterator, typename _Distance, 293 typename _Tp, typename _Compare> 294 void 295 __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex, 296 _Distance __len, _Tp __value, _Compare __comp) 297 { 298 const _Distance __topIndex = __holeIndex; 299 _Distance __secondChild = __holeIndex; 300 while (__secondChild < (__len - 1) / 2) 301 { 302 __secondChild = 2 * (__secondChild + 1); 303 if (__comp(*(__first + __secondChild), 304 *(__first + (__secondChild - 1)))) 305 __secondChild--; 306 *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __secondChild)); 307 __holeIndex = __secondChild; 308 } 309 if ((__len & 1) == 0 && __secondChild == (__len - 2) / 2) 310 { 311 __secondChild = 2 * (__secondChild + 1); 312 *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first 313 + (__secondChild - 1))); 314 __holeIndex = __secondChild - 1; 315 } 316 std::__push_heap(__first, __holeIndex, __topIndex, 317 _GLIBCXX_MOVE(__value), __comp); 318 } 319 320 template<typename _RandomAccessIterator, typename _Compare> 321 inline void 322 __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, 323 _RandomAccessIterator __result, _Compare __comp) 324 { 325 typedef typename iterator_traits<_RandomAccessIterator>::value_type 326 _ValueType; 327 typedef typename iterator_traits<_RandomAccessIterator>::difference_type 328 _DistanceType; 329 330 _ValueType __value = _GLIBCXX_MOVE(*__result); 331 *__result = _GLIBCXX_MOVE(*__first); 332 std::__adjust_heap(__first, _DistanceType(0), 333 _DistanceType(__last - __first), 334 _GLIBCXX_MOVE(__value), __comp); 335 } 336 337 /** 338 * @brief Pop an element off a heap using comparison functor. 339 * @param first Start of heap. 340 * @param last End of heap. 341 * @param comp Comparison functor to use. 342 * @ingroup heap_algorithms 343 * 344 * This operation pops the top of the heap. The elements first and last-1 345 * are swapped and [first,last-1) is made into a heap. Comparisons are 346 * made using comp. 347 */ 348 template<typename _RandomAccessIterator, typename _Compare> 349 inline void 350 pop_heap(_RandomAccessIterator __first, 351 _RandomAccessIterator __last, _Compare __comp) 352 { 353 // concept requirements 354 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 355 _RandomAccessIterator>) 356 __glibcxx_requires_valid_range(__first, __last); 357 __glibcxx_requires_heap_pred(__first, __last, __comp); 358 359 --__last; 360 std::__pop_heap(__first, __last, __last, __comp); 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 void 373 make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) 374 { 375 typedef typename iterator_traits<_RandomAccessIterator>::value_type 376 _ValueType; 377 typedef typename iterator_traits<_RandomAccessIterator>::difference_type 378 _DistanceType; 379 380 // concept requirements 381 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 382 _RandomAccessIterator>) 383 __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>) 384 __glibcxx_requires_valid_range(__first, __last); 385 386 if (__last - __first < 2) 387 return; 388 389 const _DistanceType __len = __last - __first; 390 _DistanceType __parent = (__len - 2) / 2; 391 while (true) 392 { 393 _ValueType __value = _GLIBCXX_MOVE(*(__first + __parent)); 394 std::__adjust_heap(__first, __parent, __len, _GLIBCXX_MOVE(__value)); 395 if (__parent == 0) 396 return; 397 __parent--; 398 } 399 } 400 401 /** 402 * @brief Construct a heap over a range using comparison functor. 403 * @param first Start of heap. 404 * @param last End of heap. 405 * @param comp Comparison functor to use. 406 * @ingroup heap_algorithms 407 * 408 * This operation makes the elements in [first,last) into a heap. 409 * Comparisons are made using comp. 410 */ 411 template<typename _RandomAccessIterator, typename _Compare> 412 void 413 make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, 414 _Compare __comp) 415 { 416 typedef typename iterator_traits<_RandomAccessIterator>::value_type 417 _ValueType; 418 typedef typename iterator_traits<_RandomAccessIterator>::difference_type 419 _DistanceType; 420 421 // concept requirements 422 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 423 _RandomAccessIterator>) 424 __glibcxx_requires_valid_range(__first, __last); 425 426 if (__last - __first < 2) 427 return; 428 429 const _DistanceType __len = __last - __first; 430 _DistanceType __parent = (__len - 2) / 2; 431 while (true) 432 { 433 _ValueType __value = _GLIBCXX_MOVE(*(__first + __parent)); 434 std::__adjust_heap(__first, __parent, __len, _GLIBCXX_MOVE(__value), 435 __comp); 436 if (__parent == 0) 437 return; 438 __parent--; 439 } 440 } 441 442 /** 443 * @brief Sort a heap. 444 * @param first Start of heap. 445 * @param last End of heap. 446 * @ingroup heap_algorithms 447 * 448 * This operation sorts the valid heap in the range [first,last). 449 */ 450 template<typename _RandomAccessIterator> 451 void 452 sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) 453 { 454 // concept requirements 455 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 456 _RandomAccessIterator>) 457 __glibcxx_function_requires(_LessThanComparableConcept< 458 typename iterator_traits<_RandomAccessIterator>::value_type>) 459 __glibcxx_requires_valid_range(__first, __last); 460 __glibcxx_requires_heap(__first, __last); 461 462 while (__last - __first > 1) 463 { 464 --__last; 465 std::__pop_heap(__first, __last, __last); 466 } 467 } 468 469 /** 470 * @brief Sort a heap using comparison functor. 471 * @param first Start of heap. 472 * @param last End of heap. 473 * @param comp Comparison functor to use. 474 * @ingroup heap_algorithms 475 * 476 * This operation sorts the valid heap in the range [first,last). 477 * Comparisons are made using comp. 478 */ 479 template<typename _RandomAccessIterator, typename _Compare> 480 void 481 sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, 482 _Compare __comp) 483 { 484 // concept requirements 485 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 486 _RandomAccessIterator>) 487 __glibcxx_requires_valid_range(__first, __last); 488 __glibcxx_requires_heap_pred(__first, __last, __comp); 489 490 while (__last - __first > 1) 491 { 492 --__last; 493 std::__pop_heap(__first, __last, __last, __comp); 494 } 495 } 496 497#ifdef __GXX_EXPERIMENTAL_CXX0X__ 498 /** 499 * @brief Search the end of a heap. 500 * @param first Start of range. 501 * @param last End of range. 502 * @return An iterator pointing to the first element not in the heap. 503 * @ingroup heap_algorithms 504 * 505 * This operation returns the last iterator i in [first, last) for which 506 * the range [first, i) is a heap. 507 */ 508 template<typename _RandomAccessIterator> 509 inline _RandomAccessIterator 510 is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last) 511 { 512 // concept requirements 513 __glibcxx_function_requires(_RandomAccessIteratorConcept< 514 _RandomAccessIterator>) 515 __glibcxx_function_requires(_LessThanComparableConcept< 516 typename iterator_traits<_RandomAccessIterator>::value_type>) 517 __glibcxx_requires_valid_range(__first, __last); 518 519 return __first + std::__is_heap_until(__first, std::distance(__first, 520 __last)); 521 } 522 523 /** 524 * @brief Search the end of a heap using comparison functor. 525 * @param first Start of range. 526 * @param last End of range. 527 * @param comp Comparison functor to use. 528 * @return An iterator pointing to the first element not in the heap. 529 * @ingroup heap_algorithms 530 * 531 * This operation returns the last iterator i in [first, last) for which 532 * the range [first, i) is a heap. Comparisons are made using comp. 533 */ 534 template<typename _RandomAccessIterator, typename _Compare> 535 inline _RandomAccessIterator 536 is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last, 537 _Compare __comp) 538 { 539 // concept requirements 540 __glibcxx_function_requires(_RandomAccessIteratorConcept< 541 _RandomAccessIterator>) 542 __glibcxx_requires_valid_range(__first, __last); 543 544 return __first + std::__is_heap_until(__first, std::distance(__first, 545 __last), 546 __comp); 547 } 548 549 /** 550 * @brief Determines whether a range is a heap. 551 * @param first Start of range. 552 * @param last End of range. 553 * @return True if range is a heap, false otherwise. 554 * @ingroup heap_algorithms 555 */ 556 template<typename _RandomAccessIterator> 557 inline bool 558 is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) 559 { return std::is_heap_until(__first, __last) == __last; } 560 561 /** 562 * @brief Determines whether a range is a heap using comparison functor. 563 * @param first Start of range. 564 * @param last End of range. 565 * @param comp Comparison functor to use. 566 * @return True if range is a heap, false otherwise. 567 * @ingroup heap_algorithms 568 */ 569 template<typename _RandomAccessIterator, typename _Compare> 570 inline bool 571 is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, 572 _Compare __comp) 573 { return std::is_heap_until(__first, __last, __comp) == __last; } 574#endif 575 576_GLIBCXX_END_NAMESPACE 577 578#endif /* _STL_HEAP_H */ 579