libstdc++
|
00001 // Heap implementation -*- C++ -*- 00002 00003 // Copyright (C) 2001-2019 Free Software Foundation, Inc. 00004 // 00005 // This file is part of the GNU ISO C++ Library. This library is free 00006 // software; you can redistribute it and/or modify it under the 00007 // terms of the GNU General Public License as published by the 00008 // Free Software Foundation; either version 3, or (at your option) 00009 // any later version. 00010 00011 // This library is distributed in the hope that it will be useful, 00012 // but WITHOUT ANY WARRANTY; without even the implied warranty of 00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00014 // GNU General Public License for more details. 00015 00016 // Under Section 7 of GPL version 3, you are granted additional 00017 // permissions described in the GCC Runtime Library Exception, version 00018 // 3.1, as published by the Free Software Foundation. 00019 00020 // You should have received a copy of the GNU General Public License and 00021 // a copy of the GCC Runtime Library Exception along with this program; 00022 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 00023 // <http://www.gnu.org/licenses/>. 00024 00025 /* 00026 * 00027 * Copyright (c) 1994 00028 * Hewlett-Packard Company 00029 * 00030 * Permission to use, copy, modify, distribute and sell this software 00031 * and its documentation for any purpose is hereby granted without fee, 00032 * provided that the above copyright notice appear in all copies and 00033 * that both that copyright notice and this permission notice appear 00034 * in supporting documentation. Hewlett-Packard Company makes no 00035 * representations about the suitability of this software for any 00036 * purpose. It is provided "as is" without express or implied warranty. 00037 * 00038 * Copyright (c) 1997 00039 * Silicon Graphics Computer Systems, Inc. 00040 * 00041 * Permission to use, copy, modify, distribute and sell this software 00042 * and its documentation for any purpose is hereby granted without fee, 00043 * provided that the above copyright notice appear in all copies and 00044 * that both that copyright notice and this permission notice appear 00045 * in supporting documentation. Silicon Graphics makes no 00046 * representations about the suitability of this software for any 00047 * purpose. It is provided "as is" without express or implied warranty. 00048 */ 00049 00050 /** @file bits/stl_heap.h 00051 * This is an internal header file, included by other library headers. 00052 * Do not attempt to use it directly. @headername{queue} 00053 */ 00054 00055 #ifndef _STL_HEAP_H 00056 #define _STL_HEAP_H 1 00057 00058 #include <debug/debug.h> 00059 #include <bits/move.h> 00060 #include <bits/predefined_ops.h> 00061 00062 namespace std _GLIBCXX_VISIBILITY(default) 00063 { 00064 _GLIBCXX_BEGIN_NAMESPACE_VERSION 00065 00066 /** 00067 * @defgroup heap_algorithms Heap 00068 * @ingroup sorting_algorithms 00069 */ 00070 00071 template<typename _RandomAccessIterator, typename _Distance, 00072 typename _Compare> 00073 _Distance 00074 __is_heap_until(_RandomAccessIterator __first, _Distance __n, 00075 _Compare& __comp) 00076 { 00077 _Distance __parent = 0; 00078 for (_Distance __child = 1; __child < __n; ++__child) 00079 { 00080 if (__comp(__first + __parent, __first + __child)) 00081 return __child; 00082 if ((__child & 1) == 0) 00083 ++__parent; 00084 } 00085 return __n; 00086 } 00087 00088 // __is_heap, a predicate testing whether or not a range is a heap. 00089 // This function is an extension, not part of the C++ standard. 00090 template<typename _RandomAccessIterator, typename _Distance> 00091 inline bool 00092 __is_heap(_RandomAccessIterator __first, _Distance __n) 00093 { 00094 __gnu_cxx::__ops::_Iter_less_iter __comp; 00095 return std::__is_heap_until(__first, __n, __comp) == __n; 00096 } 00097 00098 template<typename _RandomAccessIterator, typename _Compare, 00099 typename _Distance> 00100 inline bool 00101 __is_heap(_RandomAccessIterator __first, _Compare __comp, _Distance __n) 00102 { 00103 typedef __decltype(__comp) _Cmp; 00104 __gnu_cxx::__ops::_Iter_comp_iter<_Cmp> __cmp(_GLIBCXX_MOVE(__comp)); 00105 return std::__is_heap_until(__first, __n, __cmp) == __n; 00106 } 00107 00108 template<typename _RandomAccessIterator> 00109 inline bool 00110 __is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) 00111 { return std::__is_heap(__first, std::distance(__first, __last)); } 00112 00113 template<typename _RandomAccessIterator, typename _Compare> 00114 inline bool 00115 __is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, 00116 _Compare __comp) 00117 { 00118 return std::__is_heap(__first, _GLIBCXX_MOVE(__comp), 00119 std::distance(__first, __last)); 00120 } 00121 00122 // Heap-manipulation functions: push_heap, pop_heap, make_heap, sort_heap, 00123 // + is_heap and is_heap_until in C++0x. 00124 00125 template<typename _RandomAccessIterator, typename _Distance, typename _Tp, 00126 typename _Compare> 00127 void 00128 __push_heap(_RandomAccessIterator __first, 00129 _Distance __holeIndex, _Distance __topIndex, _Tp __value, 00130 _Compare& __comp) 00131 { 00132 _Distance __parent = (__holeIndex - 1) / 2; 00133 while (__holeIndex > __topIndex && __comp(__first + __parent, __value)) 00134 { 00135 *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __parent)); 00136 __holeIndex = __parent; 00137 __parent = (__holeIndex - 1) / 2; 00138 } 00139 *(__first + __holeIndex) = _GLIBCXX_MOVE(__value); 00140 } 00141 00142 /** 00143 * @brief Push an element onto a heap. 00144 * @param __first Start of heap. 00145 * @param __last End of heap + element. 00146 * @ingroup heap_algorithms 00147 * 00148 * This operation pushes the element at last-1 onto the valid heap 00149 * over the range [__first,__last-1). After completion, 00150 * [__first,__last) is a valid heap. 00151 */ 00152 template<typename _RandomAccessIterator> 00153 inline void 00154 push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) 00155 { 00156 typedef typename iterator_traits<_RandomAccessIterator>::value_type 00157 _ValueType; 00158 typedef typename iterator_traits<_RandomAccessIterator>::difference_type 00159 _DistanceType; 00160 00161 // concept requirements 00162 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 00163 _RandomAccessIterator>) 00164 __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>) 00165 __glibcxx_requires_valid_range(__first, __last); 00166 __glibcxx_requires_irreflexive(__first, __last); 00167 __glibcxx_requires_heap(__first, __last - 1); 00168 00169 __gnu_cxx::__ops::_Iter_less_val __comp; 00170 _ValueType __value = _GLIBCXX_MOVE(*(__last - 1)); 00171 std::__push_heap(__first, _DistanceType((__last - __first) - 1), 00172 _DistanceType(0), _GLIBCXX_MOVE(__value), __comp); 00173 } 00174 00175 /** 00176 * @brief Push an element onto a heap using comparison functor. 00177 * @param __first Start of heap. 00178 * @param __last End of heap + element. 00179 * @param __comp Comparison functor. 00180 * @ingroup heap_algorithms 00181 * 00182 * This operation pushes the element at __last-1 onto the valid 00183 * heap over the range [__first,__last-1). After completion, 00184 * [__first,__last) is a valid heap. Compare operations are 00185 * performed using comp. 00186 */ 00187 template<typename _RandomAccessIterator, typename _Compare> 00188 inline void 00189 push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, 00190 _Compare __comp) 00191 { 00192 typedef typename iterator_traits<_RandomAccessIterator>::value_type 00193 _ValueType; 00194 typedef typename iterator_traits<_RandomAccessIterator>::difference_type 00195 _DistanceType; 00196 00197 // concept requirements 00198 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 00199 _RandomAccessIterator>) 00200 __glibcxx_requires_valid_range(__first, __last); 00201 __glibcxx_requires_irreflexive_pred(__first, __last, __comp); 00202 __glibcxx_requires_heap_pred(__first, __last - 1, __comp); 00203 00204 __decltype(__gnu_cxx::__ops::__iter_comp_val(_GLIBCXX_MOVE(__comp))) 00205 __cmp(_GLIBCXX_MOVE(__comp)); 00206 _ValueType __value = _GLIBCXX_MOVE(*(__last - 1)); 00207 std::__push_heap(__first, _DistanceType((__last - __first) - 1), 00208 _DistanceType(0), _GLIBCXX_MOVE(__value), __cmp); 00209 } 00210 00211 template<typename _RandomAccessIterator, typename _Distance, 00212 typename _Tp, typename _Compare> 00213 void 00214 __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex, 00215 _Distance __len, _Tp __value, _Compare __comp) 00216 { 00217 const _Distance __topIndex = __holeIndex; 00218 _Distance __secondChild = __holeIndex; 00219 while (__secondChild < (__len - 1) / 2) 00220 { 00221 __secondChild = 2 * (__secondChild + 1); 00222 if (__comp(__first + __secondChild, 00223 __first + (__secondChild - 1))) 00224 __secondChild--; 00225 *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __secondChild)); 00226 __holeIndex = __secondChild; 00227 } 00228 if ((__len & 1) == 0 && __secondChild == (__len - 2) / 2) 00229 { 00230 __secondChild = 2 * (__secondChild + 1); 00231 *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first 00232 + (__secondChild - 1))); 00233 __holeIndex = __secondChild - 1; 00234 } 00235 __decltype(__gnu_cxx::__ops::__iter_comp_val(_GLIBCXX_MOVE(__comp))) 00236 __cmp(_GLIBCXX_MOVE(__comp)); 00237 std::__push_heap(__first, __holeIndex, __topIndex, 00238 _GLIBCXX_MOVE(__value), __cmp); 00239 } 00240 00241 template<typename _RandomAccessIterator, typename _Compare> 00242 inline void 00243 __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, 00244 _RandomAccessIterator __result, _Compare& __comp) 00245 { 00246 typedef typename iterator_traits<_RandomAccessIterator>::value_type 00247 _ValueType; 00248 typedef typename iterator_traits<_RandomAccessIterator>::difference_type 00249 _DistanceType; 00250 00251 _ValueType __value = _GLIBCXX_MOVE(*__result); 00252 *__result = _GLIBCXX_MOVE(*__first); 00253 std::__adjust_heap(__first, _DistanceType(0), 00254 _DistanceType(__last - __first), 00255 _GLIBCXX_MOVE(__value), __comp); 00256 } 00257 00258 /** 00259 * @brief Pop an element off a heap. 00260 * @param __first Start of heap. 00261 * @param __last End of heap. 00262 * @pre [__first, __last) is a valid, non-empty range. 00263 * @ingroup heap_algorithms 00264 * 00265 * This operation pops the top of the heap. The elements __first 00266 * and __last-1 are swapped and [__first,__last-1) is made into a 00267 * heap. 00268 */ 00269 template<typename _RandomAccessIterator> 00270 inline void 00271 pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) 00272 { 00273 // concept requirements 00274 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 00275 _RandomAccessIterator>) 00276 __glibcxx_function_requires(_LessThanComparableConcept< 00277 typename iterator_traits<_RandomAccessIterator>::value_type>) 00278 __glibcxx_requires_non_empty_range(__first, __last); 00279 __glibcxx_requires_valid_range(__first, __last); 00280 __glibcxx_requires_irreflexive(__first, __last); 00281 __glibcxx_requires_heap(__first, __last); 00282 00283 if (__last - __first > 1) 00284 { 00285 --__last; 00286 __gnu_cxx::__ops::_Iter_less_iter __comp; 00287 std::__pop_heap(__first, __last, __last, __comp); 00288 } 00289 } 00290 00291 /** 00292 * @brief Pop an element off a heap using comparison functor. 00293 * @param __first Start of heap. 00294 * @param __last End of heap. 00295 * @param __comp Comparison functor to use. 00296 * @ingroup heap_algorithms 00297 * 00298 * This operation pops the top of the heap. The elements __first 00299 * and __last-1 are swapped and [__first,__last-1) is made into a 00300 * heap. Comparisons are made using comp. 00301 */ 00302 template<typename _RandomAccessIterator, typename _Compare> 00303 inline void 00304 pop_heap(_RandomAccessIterator __first, 00305 _RandomAccessIterator __last, _Compare __comp) 00306 { 00307 // concept requirements 00308 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 00309 _RandomAccessIterator>) 00310 __glibcxx_requires_valid_range(__first, __last); 00311 __glibcxx_requires_irreflexive_pred(__first, __last, __comp); 00312 __glibcxx_requires_non_empty_range(__first, __last); 00313 __glibcxx_requires_heap_pred(__first, __last, __comp); 00314 00315 if (__last - __first > 1) 00316 { 00317 typedef __decltype(__comp) _Cmp; 00318 __gnu_cxx::__ops::_Iter_comp_iter<_Cmp> __cmp(_GLIBCXX_MOVE(__comp)); 00319 --__last; 00320 std::__pop_heap(__first, __last, __last, __cmp); 00321 } 00322 } 00323 00324 template<typename _RandomAccessIterator, typename _Compare> 00325 void 00326 __make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, 00327 _Compare& __comp) 00328 { 00329 typedef typename iterator_traits<_RandomAccessIterator>::value_type 00330 _ValueType; 00331 typedef typename iterator_traits<_RandomAccessIterator>::difference_type 00332 _DistanceType; 00333 00334 if (__last - __first < 2) 00335 return; 00336 00337 const _DistanceType __len = __last - __first; 00338 _DistanceType __parent = (__len - 2) / 2; 00339 while (true) 00340 { 00341 _ValueType __value = _GLIBCXX_MOVE(*(__first + __parent)); 00342 std::__adjust_heap(__first, __parent, __len, _GLIBCXX_MOVE(__value), 00343 __comp); 00344 if (__parent == 0) 00345 return; 00346 __parent--; 00347 } 00348 } 00349 00350 /** 00351 * @brief Construct a heap over a range. 00352 * @param __first Start of heap. 00353 * @param __last End of heap. 00354 * @ingroup heap_algorithms 00355 * 00356 * This operation makes the elements in [__first,__last) into a heap. 00357 */ 00358 template<typename _RandomAccessIterator> 00359 inline void 00360 make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) 00361 { 00362 // concept requirements 00363 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 00364 _RandomAccessIterator>) 00365 __glibcxx_function_requires(_LessThanComparableConcept< 00366 typename iterator_traits<_RandomAccessIterator>::value_type>) 00367 __glibcxx_requires_valid_range(__first, __last); 00368 __glibcxx_requires_irreflexive(__first, __last); 00369 00370 __gnu_cxx::__ops::_Iter_less_iter __comp; 00371 std::__make_heap(__first, __last, __comp); 00372 } 00373 00374 /** 00375 * @brief Construct a heap over a range using comparison functor. 00376 * @param __first Start of heap. 00377 * @param __last End of heap. 00378 * @param __comp Comparison functor to use. 00379 * @ingroup heap_algorithms 00380 * 00381 * This operation makes the elements in [__first,__last) into a heap. 00382 * Comparisons are made using __comp. 00383 */ 00384 template<typename _RandomAccessIterator, typename _Compare> 00385 inline void 00386 make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, 00387 _Compare __comp) 00388 { 00389 // concept requirements 00390 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 00391 _RandomAccessIterator>) 00392 __glibcxx_requires_valid_range(__first, __last); 00393 __glibcxx_requires_irreflexive_pred(__first, __last, __comp); 00394 00395 typedef __decltype(__comp) _Cmp; 00396 __gnu_cxx::__ops::_Iter_comp_iter<_Cmp> __cmp(_GLIBCXX_MOVE(__comp)); 00397 std::__make_heap(__first, __last, __cmp); 00398 } 00399 00400 template<typename _RandomAccessIterator, typename _Compare> 00401 void 00402 __sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, 00403 _Compare& __comp) 00404 { 00405 while (__last - __first > 1) 00406 { 00407 --__last; 00408 std::__pop_heap(__first, __last, __last, __comp); 00409 } 00410 } 00411 00412 /** 00413 * @brief Sort a heap. 00414 * @param __first Start of heap. 00415 * @param __last End of heap. 00416 * @ingroup heap_algorithms 00417 * 00418 * This operation sorts the valid heap in the range [__first,__last). 00419 */ 00420 template<typename _RandomAccessIterator> 00421 inline void 00422 sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) 00423 { 00424 // concept requirements 00425 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 00426 _RandomAccessIterator>) 00427 __glibcxx_function_requires(_LessThanComparableConcept< 00428 typename iterator_traits<_RandomAccessIterator>::value_type>) 00429 __glibcxx_requires_valid_range(__first, __last); 00430 __glibcxx_requires_irreflexive(__first, __last); 00431 __glibcxx_requires_heap(__first, __last); 00432 00433 __gnu_cxx::__ops::_Iter_less_iter __comp; 00434 std::__sort_heap(__first, __last, __comp); 00435 } 00436 00437 /** 00438 * @brief Sort a heap using comparison functor. 00439 * @param __first Start of heap. 00440 * @param __last End of heap. 00441 * @param __comp Comparison functor to use. 00442 * @ingroup heap_algorithms 00443 * 00444 * This operation sorts the valid heap in the range [__first,__last). 00445 * Comparisons are made using __comp. 00446 */ 00447 template<typename _RandomAccessIterator, typename _Compare> 00448 inline void 00449 sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, 00450 _Compare __comp) 00451 { 00452 // concept requirements 00453 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 00454 _RandomAccessIterator>) 00455 __glibcxx_requires_valid_range(__first, __last); 00456 __glibcxx_requires_irreflexive_pred(__first, __last, __comp); 00457 __glibcxx_requires_heap_pred(__first, __last, __comp); 00458 00459 typedef __decltype(__comp) _Cmp; 00460 __gnu_cxx::__ops::_Iter_comp_iter<_Cmp> __cmp(_GLIBCXX_MOVE(__comp)); 00461 std::__sort_heap(__first, __last, __cmp); 00462 } 00463 00464 #if __cplusplus >= 201103L 00465 /** 00466 * @brief Search the end of a heap. 00467 * @param __first Start of range. 00468 * @param __last End of range. 00469 * @return An iterator pointing to the first element not in the heap. 00470 * @ingroup heap_algorithms 00471 * 00472 * This operation returns the last iterator i in [__first, __last) for which 00473 * the range [__first, i) is a heap. 00474 */ 00475 template<typename _RandomAccessIterator> 00476 inline _RandomAccessIterator 00477 is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last) 00478 { 00479 // concept requirements 00480 __glibcxx_function_requires(_RandomAccessIteratorConcept< 00481 _RandomAccessIterator>) 00482 __glibcxx_function_requires(_LessThanComparableConcept< 00483 typename iterator_traits<_RandomAccessIterator>::value_type>) 00484 __glibcxx_requires_valid_range(__first, __last); 00485 __glibcxx_requires_irreflexive(__first, __last); 00486 00487 __gnu_cxx::__ops::_Iter_less_iter __comp; 00488 return __first + 00489 std::__is_heap_until(__first, std::distance(__first, __last), __comp); 00490 } 00491 00492 /** 00493 * @brief Search the end of a heap using comparison functor. 00494 * @param __first Start of range. 00495 * @param __last End of range. 00496 * @param __comp Comparison functor to use. 00497 * @return An iterator pointing to the first element not in the heap. 00498 * @ingroup heap_algorithms 00499 * 00500 * This operation returns the last iterator i in [__first, __last) for which 00501 * the range [__first, i) is a heap. Comparisons are made using __comp. 00502 */ 00503 template<typename _RandomAccessIterator, typename _Compare> 00504 inline _RandomAccessIterator 00505 is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last, 00506 _Compare __comp) 00507 { 00508 // concept requirements 00509 __glibcxx_function_requires(_RandomAccessIteratorConcept< 00510 _RandomAccessIterator>) 00511 __glibcxx_requires_valid_range(__first, __last); 00512 __glibcxx_requires_irreflexive_pred(__first, __last, __comp); 00513 00514 typedef __decltype(__comp) _Cmp; 00515 __gnu_cxx::__ops::_Iter_comp_iter<_Cmp> __cmp(_GLIBCXX_MOVE(__comp)); 00516 return __first 00517 + std::__is_heap_until(__first, std::distance(__first, __last), __cmp); 00518 } 00519 00520 /** 00521 * @brief Determines whether a range is a heap. 00522 * @param __first Start of range. 00523 * @param __last End of range. 00524 * @return True if range is a heap, false otherwise. 00525 * @ingroup heap_algorithms 00526 */ 00527 template<typename _RandomAccessIterator> 00528 inline bool 00529 is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) 00530 { return std::is_heap_until(__first, __last) == __last; } 00531 00532 /** 00533 * @brief Determines whether a range is a heap using comparison functor. 00534 * @param __first Start of range. 00535 * @param __last End of range. 00536 * @param __comp Comparison functor to use. 00537 * @return True if range is a heap, false otherwise. 00538 * @ingroup heap_algorithms 00539 */ 00540 template<typename _RandomAccessIterator, typename _Compare> 00541 inline bool 00542 is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, 00543 _Compare __comp) 00544 { 00545 // concept requirements 00546 __glibcxx_function_requires(_RandomAccessIteratorConcept< 00547 _RandomAccessIterator>) 00548 __glibcxx_requires_valid_range(__first, __last); 00549 __glibcxx_requires_irreflexive_pred(__first, __last, __comp); 00550 00551 const auto __dist = std::distance(__first, __last); 00552 typedef __decltype(__comp) _Cmp; 00553 __gnu_cxx::__ops::_Iter_comp_iter<_Cmp> __cmp(_GLIBCXX_MOVE(__comp)); 00554 return std::__is_heap_until(__first, __dist, __cmp) == __dist; 00555 } 00556 #endif 00557 00558 _GLIBCXX_END_NAMESPACE_VERSION 00559 } // namespace 00560 00561 #endif /* _STL_HEAP_H */