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