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