libstdc++
|
00001 // Heap implementation -*- C++ -*- 00002 00003 // Copyright (C) 2001-2015 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 return std::__is_heap_until(__first, __n, 00095 __gnu_cxx::__ops::__iter_less_iter()) == __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 return std::__is_heap_until(__first, __n, 00104 __gnu_cxx::__ops::__iter_comp_iter(__comp)) == __n; 00105 } 00106 00107 template<typename _RandomAccessIterator> 00108 inline bool 00109 __is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) 00110 { return std::__is_heap(__first, std::distance(__first, __last)); } 00111 00112 template<typename _RandomAccessIterator, typename _Compare> 00113 inline bool 00114 __is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, 00115 _Compare __comp) 00116 { return std::__is_heap(__first, __comp, std::distance(__first, __last)); } 00117 00118 // Heap-manipulation functions: push_heap, pop_heap, make_heap, sort_heap, 00119 // + is_heap and is_heap_until in C++0x. 00120 00121 template<typename _RandomAccessIterator, typename _Distance, typename _Tp, 00122 typename _Compare> 00123 void 00124 __push_heap(_RandomAccessIterator __first, 00125 _Distance __holeIndex, _Distance __topIndex, _Tp __value, 00126 _Compare __comp) 00127 { 00128 _Distance __parent = (__holeIndex - 1) / 2; 00129 while (__holeIndex > __topIndex && __comp(__first + __parent, __value)) 00130 { 00131 *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __parent)); 00132 __holeIndex = __parent; 00133 __parent = (__holeIndex - 1) / 2; 00134 } 00135 *(__first + __holeIndex) = _GLIBCXX_MOVE(__value); 00136 } 00137 00138 /** 00139 * @brief Push an element onto a heap. 00140 * @param __first Start of heap. 00141 * @param __last End of heap + element. 00142 * @ingroup heap_algorithms 00143 * 00144 * This operation pushes the element at last-1 onto the valid heap 00145 * over the range [__first,__last-1). After completion, 00146 * [__first,__last) is a valid heap. 00147 */ 00148 template<typename _RandomAccessIterator> 00149 inline void 00150 push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) 00151 { 00152 typedef typename iterator_traits<_RandomAccessIterator>::value_type 00153 _ValueType; 00154 typedef typename iterator_traits<_RandomAccessIterator>::difference_type 00155 _DistanceType; 00156 00157 // concept requirements 00158 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 00159 _RandomAccessIterator>) 00160 __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>) 00161 __glibcxx_requires_valid_range(__first, __last); 00162 __glibcxx_requires_heap(__first, __last - 1); 00163 00164 _ValueType __value = _GLIBCXX_MOVE(*(__last - 1)); 00165 std::__push_heap(__first, _DistanceType((__last - __first) - 1), 00166 _DistanceType(0), _GLIBCXX_MOVE(__value), 00167 __gnu_cxx::__ops::__iter_less_val()); 00168 } 00169 00170 /** 00171 * @brief Push an element onto a heap using comparison functor. 00172 * @param __first Start of heap. 00173 * @param __last End of heap + element. 00174 * @param __comp Comparison functor. 00175 * @ingroup heap_algorithms 00176 * 00177 * This operation pushes the element at __last-1 onto the valid 00178 * heap over the range [__first,__last-1). After completion, 00179 * [__first,__last) is a valid heap. Compare operations are 00180 * performed using comp. 00181 */ 00182 template<typename _RandomAccessIterator, typename _Compare> 00183 inline void 00184 push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, 00185 _Compare __comp) 00186 { 00187 typedef typename iterator_traits<_RandomAccessIterator>::value_type 00188 _ValueType; 00189 typedef typename iterator_traits<_RandomAccessIterator>::difference_type 00190 _DistanceType; 00191 00192 // concept requirements 00193 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 00194 _RandomAccessIterator>) 00195 __glibcxx_requires_valid_range(__first, __last); 00196 __glibcxx_requires_heap_pred(__first, __last - 1, __comp); 00197 00198 _ValueType __value = _GLIBCXX_MOVE(*(__last - 1)); 00199 std::__push_heap(__first, _DistanceType((__last - __first) - 1), 00200 _DistanceType(0), _GLIBCXX_MOVE(__value), 00201 __gnu_cxx::__ops::__iter_comp_val(__comp)); 00202 } 00203 00204 template<typename _RandomAccessIterator, typename _Distance, 00205 typename _Tp, typename _Compare> 00206 void 00207 __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex, 00208 _Distance __len, _Tp __value, _Compare __comp) 00209 { 00210 const _Distance __topIndex = __holeIndex; 00211 _Distance __secondChild = __holeIndex; 00212 while (__secondChild < (__len - 1) / 2) 00213 { 00214 __secondChild = 2 * (__secondChild + 1); 00215 if (__comp(__first + __secondChild, 00216 __first + (__secondChild - 1))) 00217 __secondChild--; 00218 *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __secondChild)); 00219 __holeIndex = __secondChild; 00220 } 00221 if ((__len & 1) == 0 && __secondChild == (__len - 2) / 2) 00222 { 00223 __secondChild = 2 * (__secondChild + 1); 00224 *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first 00225 + (__secondChild - 1))); 00226 __holeIndex = __secondChild - 1; 00227 } 00228 std::__push_heap(__first, __holeIndex, __topIndex, 00229 _GLIBCXX_MOVE(__value), 00230 __gnu_cxx::__ops::__iter_comp_val(__comp)); 00231 } 00232 00233 template<typename _RandomAccessIterator, typename _Compare> 00234 inline void 00235 __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, 00236 _RandomAccessIterator __result, _Compare __comp) 00237 { 00238 typedef typename iterator_traits<_RandomAccessIterator>::value_type 00239 _ValueType; 00240 typedef typename iterator_traits<_RandomAccessIterator>::difference_type 00241 _DistanceType; 00242 00243 _ValueType __value = _GLIBCXX_MOVE(*__result); 00244 *__result = _GLIBCXX_MOVE(*__first); 00245 std::__adjust_heap(__first, _DistanceType(0), 00246 _DistanceType(__last - __first), 00247 _GLIBCXX_MOVE(__value), __comp); 00248 } 00249 00250 /** 00251 * @brief Pop an element off a heap. 00252 * @param __first Start of heap. 00253 * @param __last End of heap. 00254 * @pre [__first, __last) is a valid, non-empty range. 00255 * @ingroup heap_algorithms 00256 * 00257 * This operation pops the top of the heap. The elements __first 00258 * and __last-1 are swapped and [__first,__last-1) is made into a 00259 * heap. 00260 */ 00261 template<typename _RandomAccessIterator> 00262 inline void 00263 pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) 00264 { 00265 typedef typename iterator_traits<_RandomAccessIterator>::value_type 00266 _ValueType; 00267 00268 // concept requirements 00269 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 00270 _RandomAccessIterator>) 00271 __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>) 00272 __glibcxx_requires_non_empty_range(__first, __last); 00273 __glibcxx_requires_valid_range(__first, __last); 00274 __glibcxx_requires_heap(__first, __last); 00275 00276 if (__last - __first > 1) 00277 { 00278 --__last; 00279 std::__pop_heap(__first, __last, __last, 00280 __gnu_cxx::__ops::__iter_less_iter()); 00281 } 00282 } 00283 00284 /** 00285 * @brief Pop an element off a heap using comparison functor. 00286 * @param __first Start of heap. 00287 * @param __last End of heap. 00288 * @param __comp Comparison functor to use. 00289 * @ingroup heap_algorithms 00290 * 00291 * This operation pops the top of the heap. The elements __first 00292 * and __last-1 are swapped and [__first,__last-1) is made into a 00293 * heap. Comparisons are made using comp. 00294 */ 00295 template<typename _RandomAccessIterator, typename _Compare> 00296 inline void 00297 pop_heap(_RandomAccessIterator __first, 00298 _RandomAccessIterator __last, _Compare __comp) 00299 { 00300 // concept requirements 00301 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 00302 _RandomAccessIterator>) 00303 __glibcxx_requires_valid_range(__first, __last); 00304 __glibcxx_requires_non_empty_range(__first, __last); 00305 __glibcxx_requires_heap_pred(__first, __last, __comp); 00306 00307 if (__last - __first > 1) 00308 { 00309 --__last; 00310 std::__pop_heap(__first, __last, __last, 00311 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 00312 } 00313 } 00314 00315 template<typename _RandomAccessIterator, typename _Compare> 00316 void 00317 __make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, 00318 _Compare __comp) 00319 { 00320 typedef typename iterator_traits<_RandomAccessIterator>::value_type 00321 _ValueType; 00322 typedef typename iterator_traits<_RandomAccessIterator>::difference_type 00323 _DistanceType; 00324 00325 if (__last - __first < 2) 00326 return; 00327 00328 const _DistanceType __len = __last - __first; 00329 _DistanceType __parent = (__len - 2) / 2; 00330 while (true) 00331 { 00332 _ValueType __value = _GLIBCXX_MOVE(*(__first + __parent)); 00333 std::__adjust_heap(__first, __parent, __len, _GLIBCXX_MOVE(__value), 00334 __comp); 00335 if (__parent == 0) 00336 return; 00337 __parent--; 00338 } 00339 } 00340 00341 /** 00342 * @brief Construct a heap over a range. 00343 * @param __first Start of heap. 00344 * @param __last End of heap. 00345 * @ingroup heap_algorithms 00346 * 00347 * This operation makes the elements in [__first,__last) into a heap. 00348 */ 00349 template<typename _RandomAccessIterator> 00350 inline void 00351 make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) 00352 { 00353 // concept requirements 00354 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 00355 _RandomAccessIterator>) 00356 __glibcxx_function_requires(_LessThanComparableConcept< 00357 typename iterator_traits<_RandomAccessIterator>::value_type>) 00358 __glibcxx_requires_valid_range(__first, __last); 00359 00360 std::__make_heap(__first, __last, 00361 __gnu_cxx::__ops::__iter_less_iter()); 00362 } 00363 00364 /** 00365 * @brief Construct a heap over a range using comparison functor. 00366 * @param __first Start of heap. 00367 * @param __last End of heap. 00368 * @param __comp Comparison functor to use. 00369 * @ingroup heap_algorithms 00370 * 00371 * This operation makes the elements in [__first,__last) into a heap. 00372 * Comparisons are made using __comp. 00373 */ 00374 template<typename _RandomAccessIterator, typename _Compare> 00375 inline void 00376 make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, 00377 _Compare __comp) 00378 { 00379 // concept requirements 00380 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 00381 _RandomAccessIterator>) 00382 __glibcxx_requires_valid_range(__first, __last); 00383 00384 std::__make_heap(__first, __last, 00385 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 00386 } 00387 00388 template<typename _RandomAccessIterator, typename _Compare> 00389 void 00390 __sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, 00391 _Compare __comp) 00392 { 00393 while (__last - __first > 1) 00394 { 00395 --__last; 00396 std::__pop_heap(__first, __last, __last, __comp); 00397 } 00398 } 00399 00400 /** 00401 * @brief Sort a heap. 00402 * @param __first Start of heap. 00403 * @param __last End of heap. 00404 * @ingroup heap_algorithms 00405 * 00406 * This operation sorts the valid heap in the range [__first,__last). 00407 */ 00408 template<typename _RandomAccessIterator> 00409 inline void 00410 sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) 00411 { 00412 // concept requirements 00413 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 00414 _RandomAccessIterator>) 00415 __glibcxx_function_requires(_LessThanComparableConcept< 00416 typename iterator_traits<_RandomAccessIterator>::value_type>) 00417 __glibcxx_requires_valid_range(__first, __last); 00418 __glibcxx_requires_heap(__first, __last); 00419 00420 std::__sort_heap(__first, __last, 00421 __gnu_cxx::__ops::__iter_less_iter()); 00422 } 00423 00424 /** 00425 * @brief Sort a heap using comparison functor. 00426 * @param __first Start of heap. 00427 * @param __last End of heap. 00428 * @param __comp Comparison functor to use. 00429 * @ingroup heap_algorithms 00430 * 00431 * This operation sorts the valid heap in the range [__first,__last). 00432 * Comparisons are made using __comp. 00433 */ 00434 template<typename _RandomAccessIterator, typename _Compare> 00435 inline void 00436 sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, 00437 _Compare __comp) 00438 { 00439 // concept requirements 00440 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 00441 _RandomAccessIterator>) 00442 __glibcxx_requires_valid_range(__first, __last); 00443 __glibcxx_requires_heap_pred(__first, __last, __comp); 00444 00445 std::__sort_heap(__first, __last, 00446 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 00447 } 00448 00449 #if __cplusplus >= 201103L 00450 /** 00451 * @brief Search the end of a heap. 00452 * @param __first Start of range. 00453 * @param __last End of range. 00454 * @return An iterator pointing to the first element not in the heap. 00455 * @ingroup heap_algorithms 00456 * 00457 * This operation returns the last iterator i in [__first, __last) for which 00458 * the range [__first, i) is a heap. 00459 */ 00460 template<typename _RandomAccessIterator> 00461 inline _RandomAccessIterator 00462 is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last) 00463 { 00464 // concept requirements 00465 __glibcxx_function_requires(_RandomAccessIteratorConcept< 00466 _RandomAccessIterator>) 00467 __glibcxx_function_requires(_LessThanComparableConcept< 00468 typename iterator_traits<_RandomAccessIterator>::value_type>) 00469 __glibcxx_requires_valid_range(__first, __last); 00470 00471 return __first + 00472 std::__is_heap_until(__first, std::distance(__first, __last), 00473 __gnu_cxx::__ops::__iter_less_iter()); 00474 } 00475 00476 /** 00477 * @brief Search the end of a heap using comparison functor. 00478 * @param __first Start of range. 00479 * @param __last End of range. 00480 * @param __comp Comparison functor to use. 00481 * @return An iterator pointing to the first element not in the heap. 00482 * @ingroup heap_algorithms 00483 * 00484 * This operation returns the last iterator i in [__first, __last) for which 00485 * the range [__first, i) is a heap. Comparisons are made using __comp. 00486 */ 00487 template<typename _RandomAccessIterator, typename _Compare> 00488 inline _RandomAccessIterator 00489 is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last, 00490 _Compare __comp) 00491 { 00492 // concept requirements 00493 __glibcxx_function_requires(_RandomAccessIteratorConcept< 00494 _RandomAccessIterator>) 00495 __glibcxx_requires_valid_range(__first, __last); 00496 00497 return __first 00498 + std::__is_heap_until(__first, std::distance(__first, __last), 00499 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 00500 } 00501 00502 /** 00503 * @brief Determines whether a range is a heap. 00504 * @param __first Start of range. 00505 * @param __last End of range. 00506 * @return True if range is a heap, false otherwise. 00507 * @ingroup heap_algorithms 00508 */ 00509 template<typename _RandomAccessIterator> 00510 inline bool 00511 is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) 00512 { return std::is_heap_until(__first, __last) == __last; } 00513 00514 /** 00515 * @brief Determines whether a range is a heap using comparison functor. 00516 * @param __first Start of range. 00517 * @param __last End of range. 00518 * @param __comp Comparison functor to use. 00519 * @return True if range is a heap, false otherwise. 00520 * @ingroup heap_algorithms 00521 */ 00522 template<typename _RandomAccessIterator, typename _Compare> 00523 inline bool 00524 is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, 00525 _Compare __comp) 00526 { return std::is_heap_until(__first, __last, __comp) == __last; } 00527 #endif 00528 00529 _GLIBCXX_END_NAMESPACE_VERSION 00530 } // namespace 00531 00532 #endif /* _STL_HEAP_H */