libstdc++
|
00001 // Heap implementation -*- C++ -*- 00002 00003 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009 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 stl_heap.h 00052 * This is an internal header file, included by other library headers. 00053 * You should not attempt to use it directly. 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 _GLIBCXX_BEGIN_NAMESPACE(std) 00063 00064 /** 00065 * @defgroup heap_algorithms Heap Algorithms 00066 * @ingroup sorting_algorithms 00067 */ 00068 00069 template<typename _RandomAccessIterator, typename _Distance> 00070 _Distance 00071 __is_heap_until(_RandomAccessIterator __first, _Distance __n) 00072 { 00073 _Distance __parent = 0; 00074 for (_Distance __child = 1; __child < __n; ++__child) 00075 { 00076 if (__first[__parent] < __first[__child]) 00077 return __child; 00078 if ((__child & 1) == 0) 00079 ++__parent; 00080 } 00081 return __n; 00082 } 00083 00084 template<typename _RandomAccessIterator, typename _Distance, 00085 typename _Compare> 00086 _Distance 00087 __is_heap_until(_RandomAccessIterator __first, _Distance __n, 00088 _Compare __comp) 00089 { 00090 _Distance __parent = 0; 00091 for (_Distance __child = 1; __child < __n; ++__child) 00092 { 00093 if (__comp(__first[__parent], __first[__child])) 00094 return __child; 00095 if ((__child & 1) == 0) 00096 ++__parent; 00097 } 00098 return __n; 00099 } 00100 00101 // __is_heap, a predicate testing whether or not a range is a heap. 00102 // This function is an extension, not part of the C++ standard. 00103 template<typename _RandomAccessIterator, typename _Distance> 00104 inline bool 00105 __is_heap(_RandomAccessIterator __first, _Distance __n) 00106 { return std::__is_heap_until(__first, __n) == __n; } 00107 00108 template<typename _RandomAccessIterator, typename _Compare, 00109 typename _Distance> 00110 inline bool 00111 __is_heap(_RandomAccessIterator __first, _Compare __comp, _Distance __n) 00112 { return std::__is_heap_until(__first, __n, __comp) == __n; } 00113 00114 template<typename _RandomAccessIterator> 00115 inline bool 00116 __is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) 00117 { return std::__is_heap(__first, std::distance(__first, __last)); } 00118 00119 template<typename _RandomAccessIterator, typename _Compare> 00120 inline bool 00121 __is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, 00122 _Compare __comp) 00123 { return std::__is_heap(__first, __comp, std::distance(__first, __last)); } 00124 00125 // Heap-manipulation functions: push_heap, pop_heap, make_heap, sort_heap, 00126 // + is_heap and is_heap_until in C++0x. 00127 00128 template<typename _RandomAccessIterator, typename _Distance, typename _Tp> 00129 void 00130 __push_heap(_RandomAccessIterator __first, 00131 _Distance __holeIndex, _Distance __topIndex, _Tp __value) 00132 { 00133 _Distance __parent = (__holeIndex - 1) / 2; 00134 while (__holeIndex > __topIndex && *(__first + __parent) < __value) 00135 { 00136 *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __parent)); 00137 __holeIndex = __parent; 00138 __parent = (__holeIndex - 1) / 2; 00139 } 00140 *(__first + __holeIndex) = _GLIBCXX_MOVE(__value); 00141 } 00142 00143 /** 00144 * @brief Push an element onto a heap. 00145 * @param first Start of heap. 00146 * @param last End of heap + element. 00147 * @ingroup heap_algorithms 00148 * 00149 * This operation pushes the element at last-1 onto the valid heap over the 00150 * range [first,last-1). After completion, [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_heap(__first, __last - 1); 00167 00168 _ValueType __value = _GLIBCXX_MOVE(*(__last - 1)); 00169 std::__push_heap(__first, _DistanceType((__last - __first) - 1), 00170 _DistanceType(0), _GLIBCXX_MOVE(__value)); 00171 } 00172 00173 template<typename _RandomAccessIterator, typename _Distance, typename _Tp, 00174 typename _Compare> 00175 void 00176 __push_heap(_RandomAccessIterator __first, _Distance __holeIndex, 00177 _Distance __topIndex, _Tp __value, _Compare __comp) 00178 { 00179 _Distance __parent = (__holeIndex - 1) / 2; 00180 while (__holeIndex > __topIndex 00181 && __comp(*(__first + __parent), __value)) 00182 { 00183 *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __parent)); 00184 __holeIndex = __parent; 00185 __parent = (__holeIndex - 1) / 2; 00186 } 00187 *(__first + __holeIndex) = _GLIBCXX_MOVE(__value); 00188 } 00189 00190 /** 00191 * @brief Push an element onto a heap using comparison functor. 00192 * @param first Start of heap. 00193 * @param last End of heap + element. 00194 * @param comp Comparison functor. 00195 * @ingroup heap_algorithms 00196 * 00197 * This operation pushes the element at last-1 onto the valid heap over the 00198 * range [first,last-1). After completion, [first,last) is a valid heap. 00199 * Compare operations are performed using comp. 00200 */ 00201 template<typename _RandomAccessIterator, typename _Compare> 00202 inline void 00203 push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, 00204 _Compare __comp) 00205 { 00206 typedef typename iterator_traits<_RandomAccessIterator>::value_type 00207 _ValueType; 00208 typedef typename iterator_traits<_RandomAccessIterator>::difference_type 00209 _DistanceType; 00210 00211 // concept requirements 00212 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 00213 _RandomAccessIterator>) 00214 __glibcxx_requires_valid_range(__first, __last); 00215 __glibcxx_requires_heap_pred(__first, __last - 1, __comp); 00216 00217 _ValueType __value = _GLIBCXX_MOVE(*(__last - 1)); 00218 std::__push_heap(__first, _DistanceType((__last - __first) - 1), 00219 _DistanceType(0), _GLIBCXX_MOVE(__value), __comp); 00220 } 00221 00222 template<typename _RandomAccessIterator, typename _Distance, typename _Tp> 00223 void 00224 __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex, 00225 _Distance __len, _Tp __value) 00226 { 00227 const _Distance __topIndex = __holeIndex; 00228 _Distance __secondChild = __holeIndex; 00229 while (__secondChild < (__len - 1) / 2) 00230 { 00231 __secondChild = 2 * (__secondChild + 1); 00232 if (*(__first + __secondChild) < *(__first + (__secondChild - 1))) 00233 __secondChild--; 00234 *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __secondChild)); 00235 __holeIndex = __secondChild; 00236 } 00237 if ((__len & 1) == 0 && __secondChild == (__len - 2) / 2) 00238 { 00239 __secondChild = 2 * (__secondChild + 1); 00240 *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first 00241 + (__secondChild - 1))); 00242 __holeIndex = __secondChild - 1; 00243 } 00244 std::__push_heap(__first, __holeIndex, __topIndex, 00245 _GLIBCXX_MOVE(__value)); 00246 } 00247 00248 template<typename _RandomAccessIterator> 00249 inline void 00250 __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, 00251 _RandomAccessIterator __result) 00252 { 00253 typedef typename iterator_traits<_RandomAccessIterator>::value_type 00254 _ValueType; 00255 typedef typename iterator_traits<_RandomAccessIterator>::difference_type 00256 _DistanceType; 00257 00258 _ValueType __value = _GLIBCXX_MOVE(*__result); 00259 *__result = _GLIBCXX_MOVE(*__first); 00260 std::__adjust_heap(__first, _DistanceType(0), 00261 _DistanceType(__last - __first), 00262 _GLIBCXX_MOVE(__value)); 00263 } 00264 00265 /** 00266 * @brief Pop an element off a heap. 00267 * @param first Start of heap. 00268 * @param last End of heap. 00269 * @ingroup heap_algorithms 00270 * 00271 * This operation pops the top of the heap. The elements first and last-1 00272 * are swapped and [first,last-1) is made into a heap. 00273 */ 00274 template<typename _RandomAccessIterator> 00275 inline void 00276 pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) 00277 { 00278 typedef typename iterator_traits<_RandomAccessIterator>::value_type 00279 _ValueType; 00280 00281 // concept requirements 00282 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 00283 _RandomAccessIterator>) 00284 __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>) 00285 __glibcxx_requires_valid_range(__first, __last); 00286 __glibcxx_requires_heap(__first, __last); 00287 00288 --__last; 00289 std::__pop_heap(__first, __last, __last); 00290 } 00291 00292 template<typename _RandomAccessIterator, typename _Distance, 00293 typename _Tp, typename _Compare> 00294 void 00295 __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex, 00296 _Distance __len, _Tp __value, _Compare __comp) 00297 { 00298 const _Distance __topIndex = __holeIndex; 00299 _Distance __secondChild = __holeIndex; 00300 while (__secondChild < (__len - 1) / 2) 00301 { 00302 __secondChild = 2 * (__secondChild + 1); 00303 if (__comp(*(__first + __secondChild), 00304 *(__first + (__secondChild - 1)))) 00305 __secondChild--; 00306 *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __secondChild)); 00307 __holeIndex = __secondChild; 00308 } 00309 if ((__len & 1) == 0 && __secondChild == (__len - 2) / 2) 00310 { 00311 __secondChild = 2 * (__secondChild + 1); 00312 *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first 00313 + (__secondChild - 1))); 00314 __holeIndex = __secondChild - 1; 00315 } 00316 std::__push_heap(__first, __holeIndex, __topIndex, 00317 _GLIBCXX_MOVE(__value), __comp); 00318 } 00319 00320 template<typename _RandomAccessIterator, typename _Compare> 00321 inline void 00322 __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, 00323 _RandomAccessIterator __result, _Compare __comp) 00324 { 00325 typedef typename iterator_traits<_RandomAccessIterator>::value_type 00326 _ValueType; 00327 typedef typename iterator_traits<_RandomAccessIterator>::difference_type 00328 _DistanceType; 00329 00330 _ValueType __value = _GLIBCXX_MOVE(*__result); 00331 *__result = _GLIBCXX_MOVE(*__first); 00332 std::__adjust_heap(__first, _DistanceType(0), 00333 _DistanceType(__last - __first), 00334 _GLIBCXX_MOVE(__value), __comp); 00335 } 00336 00337 /** 00338 * @brief Pop an element off a heap using comparison functor. 00339 * @param first Start of heap. 00340 * @param last End of heap. 00341 * @param comp Comparison functor to use. 00342 * @ingroup heap_algorithms 00343 * 00344 * This operation pops the top of the heap. The elements first and last-1 00345 * are swapped and [first,last-1) is made into a heap. Comparisons are 00346 * made using comp. 00347 */ 00348 template<typename _RandomAccessIterator, typename _Compare> 00349 inline void 00350 pop_heap(_RandomAccessIterator __first, 00351 _RandomAccessIterator __last, _Compare __comp) 00352 { 00353 // concept requirements 00354 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 00355 _RandomAccessIterator>) 00356 __glibcxx_requires_valid_range(__first, __last); 00357 __glibcxx_requires_heap_pred(__first, __last, __comp); 00358 00359 --__last; 00360 std::__pop_heap(__first, __last, __last, __comp); 00361 } 00362 00363 /** 00364 * @brief Construct a heap over a range. 00365 * @param first Start of heap. 00366 * @param last End of heap. 00367 * @ingroup heap_algorithms 00368 * 00369 * This operation makes the elements in [first,last) into a heap. 00370 */ 00371 template<typename _RandomAccessIterator> 00372 void 00373 make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) 00374 { 00375 typedef typename iterator_traits<_RandomAccessIterator>::value_type 00376 _ValueType; 00377 typedef typename iterator_traits<_RandomAccessIterator>::difference_type 00378 _DistanceType; 00379 00380 // concept requirements 00381 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 00382 _RandomAccessIterator>) 00383 __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>) 00384 __glibcxx_requires_valid_range(__first, __last); 00385 00386 if (__last - __first < 2) 00387 return; 00388 00389 const _DistanceType __len = __last - __first; 00390 _DistanceType __parent = (__len - 2) / 2; 00391 while (true) 00392 { 00393 _ValueType __value = _GLIBCXX_MOVE(*(__first + __parent)); 00394 std::__adjust_heap(__first, __parent, __len, _GLIBCXX_MOVE(__value)); 00395 if (__parent == 0) 00396 return; 00397 __parent--; 00398 } 00399 } 00400 00401 /** 00402 * @brief Construct a heap over a range using comparison functor. 00403 * @param first Start of heap. 00404 * @param last End of heap. 00405 * @param comp Comparison functor to use. 00406 * @ingroup heap_algorithms 00407 * 00408 * This operation makes the elements in [first,last) into a heap. 00409 * Comparisons are made using comp. 00410 */ 00411 template<typename _RandomAccessIterator, typename _Compare> 00412 void 00413 make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, 00414 _Compare __comp) 00415 { 00416 typedef typename iterator_traits<_RandomAccessIterator>::value_type 00417 _ValueType; 00418 typedef typename iterator_traits<_RandomAccessIterator>::difference_type 00419 _DistanceType; 00420 00421 // concept requirements 00422 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 00423 _RandomAccessIterator>) 00424 __glibcxx_requires_valid_range(__first, __last); 00425 00426 if (__last - __first < 2) 00427 return; 00428 00429 const _DistanceType __len = __last - __first; 00430 _DistanceType __parent = (__len - 2) / 2; 00431 while (true) 00432 { 00433 _ValueType __value = _GLIBCXX_MOVE(*(__first + __parent)); 00434 std::__adjust_heap(__first, __parent, __len, _GLIBCXX_MOVE(__value), 00435 __comp); 00436 if (__parent == 0) 00437 return; 00438 __parent--; 00439 } 00440 } 00441 00442 /** 00443 * @brief Sort a heap. 00444 * @param first Start of heap. 00445 * @param last End of heap. 00446 * @ingroup heap_algorithms 00447 * 00448 * This operation sorts the valid heap in the range [first,last). 00449 */ 00450 template<typename _RandomAccessIterator> 00451 void 00452 sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) 00453 { 00454 // concept requirements 00455 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 00456 _RandomAccessIterator>) 00457 __glibcxx_function_requires(_LessThanComparableConcept< 00458 typename iterator_traits<_RandomAccessIterator>::value_type>) 00459 __glibcxx_requires_valid_range(__first, __last); 00460 __glibcxx_requires_heap(__first, __last); 00461 00462 while (__last - __first > 1) 00463 { 00464 --__last; 00465 std::__pop_heap(__first, __last, __last); 00466 } 00467 } 00468 00469 /** 00470 * @brief Sort a heap using comparison functor. 00471 * @param first Start of heap. 00472 * @param last End of heap. 00473 * @param comp Comparison functor to use. 00474 * @ingroup heap_algorithms 00475 * 00476 * This operation sorts the valid heap in the range [first,last). 00477 * Comparisons are made using comp. 00478 */ 00479 template<typename _RandomAccessIterator, typename _Compare> 00480 void 00481 sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, 00482 _Compare __comp) 00483 { 00484 // concept requirements 00485 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 00486 _RandomAccessIterator>) 00487 __glibcxx_requires_valid_range(__first, __last); 00488 __glibcxx_requires_heap_pred(__first, __last, __comp); 00489 00490 while (__last - __first > 1) 00491 { 00492 --__last; 00493 std::__pop_heap(__first, __last, __last, __comp); 00494 } 00495 } 00496 00497 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00498 /** 00499 * @brief Search the end of a heap. 00500 * @param first Start of range. 00501 * @param last End of range. 00502 * @return An iterator pointing to the first element not in the heap. 00503 * @ingroup heap_algorithms 00504 * 00505 * This operation returns the last iterator i in [first, last) for which 00506 * the range [first, i) is a heap. 00507 */ 00508 template<typename _RandomAccessIterator> 00509 inline _RandomAccessIterator 00510 is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last) 00511 { 00512 // concept requirements 00513 __glibcxx_function_requires(_RandomAccessIteratorConcept< 00514 _RandomAccessIterator>) 00515 __glibcxx_function_requires(_LessThanComparableConcept< 00516 typename iterator_traits<_RandomAccessIterator>::value_type>) 00517 __glibcxx_requires_valid_range(__first, __last); 00518 00519 return __first + std::__is_heap_until(__first, std::distance(__first, 00520 __last)); 00521 } 00522 00523 /** 00524 * @brief Search the end of a heap using comparison functor. 00525 * @param first Start of range. 00526 * @param last End of range. 00527 * @param comp Comparison functor to use. 00528 * @return An iterator pointing to the first element not in the heap. 00529 * @ingroup heap_algorithms 00530 * 00531 * This operation returns the last iterator i in [first, last) for which 00532 * the range [first, i) is a heap. Comparisons are made using comp. 00533 */ 00534 template<typename _RandomAccessIterator, typename _Compare> 00535 inline _RandomAccessIterator 00536 is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last, 00537 _Compare __comp) 00538 { 00539 // concept requirements 00540 __glibcxx_function_requires(_RandomAccessIteratorConcept< 00541 _RandomAccessIterator>) 00542 __glibcxx_requires_valid_range(__first, __last); 00543 00544 return __first + std::__is_heap_until(__first, std::distance(__first, 00545 __last), 00546 __comp); 00547 } 00548 00549 /** 00550 * @brief Determines whether a range is a heap. 00551 * @param first Start of range. 00552 * @param last End of range. 00553 * @return True if range is a heap, false otherwise. 00554 * @ingroup heap_algorithms 00555 */ 00556 template<typename _RandomAccessIterator> 00557 inline bool 00558 is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) 00559 { return std::is_heap_until(__first, __last) == __last; } 00560 00561 /** 00562 * @brief Determines whether a range is a heap using comparison functor. 00563 * @param first Start of range. 00564 * @param last End of range. 00565 * @param comp Comparison functor to use. 00566 * @return True if range is a heap, false otherwise. 00567 * @ingroup heap_algorithms 00568 */ 00569 template<typename _RandomAccessIterator, typename _Compare> 00570 inline bool 00571 is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, 00572 _Compare __comp) 00573 { return std::is_heap_until(__first, __last, __comp) == __last; } 00574 #endif 00575 00576 _GLIBCXX_END_NAMESPACE 00577 00578 #endif /* _STL_HEAP_H */