libstdc++-v3 Source: stl_heap.h Source File

00001 // Heap implementation -*- C++ -*- 00002 00003 // Copyright (C) 2001, 2004 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 2, 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 // You should have received a copy of the GNU General Public License along 00017 // with this library; see the file COPYING. If not, write to the Free 00018 // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, 00019 // USA. 00020 00021 // As a special exception, you may use this file as part of a free software 00022 // library without restriction. Specifically, if other files instantiate 00023 // templates or use macros or inline functions from this file, or you compile 00024 // this file and link it with other files to produce an executable, this 00025 // file does not by itself cause the resulting executable to be covered by 00026 // the GNU General Public License. This exception does not however 00027 // invalidate any other reasons why the executable file might be covered by 00028 // the GNU General Public License. 00029 00030 /* 00031 * 00032 * Copyright (c) 1994 00033 * Hewlett-Packard Company 00034 * 00035 * Permission to use, copy, modify, distribute and sell this software 00036 * and its documentation for any purpose is hereby granted without fee, 00037 * provided that the above copyright notice appear in all copies and 00038 * that both that copyright notice and this permission notice appear 00039 * in supporting documentation. Hewlett-Packard Company makes no 00040 * representations about the suitability of this software for any 00041 * purpose. It is provided "as is" without express or implied warranty. 00042 * 00043 * Copyright (c) 1997 00044 * Silicon Graphics Computer Systems, Inc. 00045 * 00046 * Permission to use, copy, modify, distribute and sell this software 00047 * and its documentation for any purpose is hereby granted without fee, 00048 * provided that the above copyright notice appear in all copies and 00049 * that both that copyright notice and this permission notice appear 00050 * in supporting documentation. Silicon Graphics makes no 00051 * representations about the suitability of this software for any 00052 * purpose. It is provided "as is" without express or implied warranty. 00053 */ 00054 00055 /** @file stl_heap.h 00056 * This is an internal header file, included by other library headers. 00057 * You should not attempt to use it directly. 00058 */ 00059 00060 #ifndef _STL_HEAP_H 00061 #define _STL_HEAP_H 1 00062 00063 #include <debug/debug.h> 00064 00065 namespace std 00066 { 00067 // is_heap, a predicate testing whether or not a range is 00068 // a heap. This function is an extension, not part of the C++ 00069 // standard. 00070 template<typename _RandomAccessIterator, typename _Distance> 00071 bool 00072 __is_heap(_RandomAccessIterator __first, _Distance __n) 00073 { 00074 _Distance __parent = 0; 00075 for (_Distance __child = 1; __child < __n; ++__child) 00076 { 00077 if (__first[__parent] < __first[__child]) 00078 return false; 00079 if ((__child & 1) == 0) 00080 ++__parent; 00081 } 00082 return true; 00083 } 00084 00085 template<typename _RandomAccessIterator, typename _Distance, 00086 typename _StrictWeakOrdering> 00087 bool 00088 __is_heap(_RandomAccessIterator __first, _StrictWeakOrdering __comp, 00089 _Distance __n) 00090 { 00091 _Distance __parent = 0; 00092 for (_Distance __child = 1; __child < __n; ++__child) 00093 { 00094 if (__comp(__first[__parent], __first[__child])) 00095 return false; 00096 if ((__child & 1) == 0) 00097 ++__parent; 00098 } 00099 return true; 00100 } 00101 00102 template<typename _RandomAccessIterator> 00103 bool 00104 __is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) 00105 { return std::__is_heap(__first, std::distance(__first, __last)); } 00106 00107 template<typename _RandomAccessIterator, typename _StrictWeakOrdering> 00108 bool 00109 __is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, 00110 _StrictWeakOrdering __comp) 00111 { return std::__is_heap(__first, __comp, std::distance(__first, __last)); } 00112 00113 // Heap-manipulation functions: push_heap, pop_heap, make_heap, sort_heap. 00114 00115 template<typename _RandomAccessIterator, typename _Distance, typename _Tp> 00116 void 00117 __push_heap(_RandomAccessIterator __first, 00118 _Distance __holeIndex, _Distance __topIndex, _Tp __value) 00119 { 00120 _Distance __parent = (__holeIndex - 1) / 2; 00121 while (__holeIndex > __topIndex && *(__first + __parent) < __value) 00122 { 00123 *(__first + __holeIndex) = *(__first + __parent); 00124 __holeIndex = __parent; 00125 __parent = (__holeIndex - 1) / 2; 00126 } 00127 *(__first + __holeIndex) = __value; 00128 } 00129 00130 /** 00131 * @brief Push an element onto a heap. 00132 * @param first Start of heap. 00133 * @param last End of heap + element. 00134 * @ingroup heap 00135 * 00136 * This operation pushes the element at last-1 onto the valid heap over the 00137 * range [first,last-1). After completion, [first,last) is a valid heap. 00138 */ 00139 template<typename _RandomAccessIterator> 00140 inline void 00141 push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) 00142 { 00143 typedef typename iterator_traits<_RandomAccessIterator>::value_type 00144 _ValueType; 00145 typedef typename iterator_traits<_RandomAccessIterator>::difference_type 00146 _DistanceType; 00147 00148 // concept requirements 00149 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 00150 _RandomAccessIterator>) 00151 __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>) 00152 __glibcxx_requires_valid_range(__first, __last); 00153 // __glibcxx_requires_heap(__first, __last - 1); 00154 00155 std::__push_heap(__first, _DistanceType((__last - __first) - 1), 00156 _DistanceType(0), _ValueType(*(__last - 1))); 00157 } 00158 00159 template<typename _RandomAccessIterator, typename _Distance, typename _Tp, 00160 typename _Compare> 00161 void 00162 __push_heap(_RandomAccessIterator __first, _Distance __holeIndex, 00163 _Distance __topIndex, _Tp __value, _Compare __comp) 00164 { 00165 _Distance __parent = (__holeIndex - 1) / 2; 00166 while (__holeIndex > __topIndex 00167 && __comp(*(__first + __parent), __value)) 00168 { 00169 *(__first + __holeIndex) = *(__first + __parent); 00170 __holeIndex = __parent; 00171 __parent = (__holeIndex - 1) / 2; 00172 } 00173 *(__first + __holeIndex) = __value; 00174 } 00175 00176 /** 00177 * @brief Push an element onto a heap using comparison functor. 00178 * @param first Start of heap. 00179 * @param last End of heap + element. 00180 * @param comp Comparison functor. 00181 * @ingroup heap 00182 * 00183 * This operation pushes the element at last-1 onto the valid heap over the 00184 * range [first,last-1). After completion, [first,last) is a valid heap. 00185 * Compare operations are 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_heap_pred(__first, __last - 1, __comp); 00202 00203 std::__push_heap(__first, _DistanceType((__last - __first) - 1), 00204 _DistanceType(0), _ValueType(*(__last - 1)), __comp); 00205 } 00206 00207 template<typename _RandomAccessIterator, typename _Distance, typename _Tp> 00208 void 00209 __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex, 00210 _Distance __len, _Tp __value) 00211 { 00212 const _Distance __topIndex = __holeIndex; 00213 _Distance __secondChild = 2 * __holeIndex + 2; 00214 while (__secondChild < __len) 00215 { 00216 if (*(__first + __secondChild) < *(__first + (__secondChild - 1))) 00217 __secondChild--; 00218 *(__first + __holeIndex) = *(__first + __secondChild); 00219 __holeIndex = __secondChild; 00220 __secondChild = 2 * (__secondChild + 1); 00221 } 00222 if (__secondChild == __len) 00223 { 00224 *(__first + __holeIndex) = *(__first + (__secondChild - 1)); 00225 __holeIndex = __secondChild - 1; 00226 } 00227 std::__push_heap(__first, __holeIndex, __topIndex, __value); 00228 } 00229 00230 template<typename _RandomAccessIterator, typename _Tp> 00231 inline void 00232 __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, 00233 _RandomAccessIterator __result, _Tp __value) 00234 { 00235 typedef typename iterator_traits<_RandomAccessIterator>::difference_type 00236 _Distance; 00237 *__result = *__first; 00238 std::__adjust_heap(__first, _Distance(0), _Distance(__last - __first), 00239 __value); 00240 } 00241 00242 /** 00243 * @brief Pop an element off a heap. 00244 * @param first Start of heap. 00245 * @param last End of heap. 00246 * @ingroup heap 00247 * 00248 * This operation pops the top of the heap. The elements first and last-1 00249 * are swapped and [first,last-1) is made into a heap. 00250 */ 00251 template<typename _RandomAccessIterator> 00252 inline void 00253 pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) 00254 { 00255 typedef typename iterator_traits<_RandomAccessIterator>::value_type 00256 _ValueType; 00257 00258 // concept requirements 00259 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 00260 _RandomAccessIterator>) 00261 __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>) 00262 __glibcxx_requires_valid_range(__first, __last); 00263 __glibcxx_requires_heap(__first, __last); 00264 00265 std::__pop_heap(__first, __last - 1, __last - 1, 00266 _ValueType(*(__last - 1))); 00267 } 00268 00269 template<typename _RandomAccessIterator, typename _Distance, 00270 typename _Tp, typename _Compare> 00271 void 00272 __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex, 00273 _Distance __len, _Tp __value, _Compare __comp) 00274 { 00275 const _Distance __topIndex = __holeIndex; 00276 _Distance __secondChild = 2 * __holeIndex + 2; 00277 while (__secondChild < __len) 00278 { 00279 if (__comp(*(__first + __secondChild), 00280 *(__first + (__secondChild - 1)))) 00281 __secondChild--; 00282 *(__first + __holeIndex) = *(__first + __secondChild); 00283 __holeIndex = __secondChild; 00284 __secondChild = 2 * (__secondChild + 1); 00285 } 00286 if (__secondChild == __len) 00287 { 00288 *(__first + __holeIndex) = *(__first + (__secondChild - 1)); 00289 __holeIndex = __secondChild - 1; 00290 } 00291 std::__push_heap(__first, __holeIndex, __topIndex, __value, __comp); 00292 } 00293 00294 template<typename _RandomAccessIterator, typename _Tp, typename _Compare> 00295 inline void 00296 __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, 00297 _RandomAccessIterator __result, _Tp __value, _Compare __comp) 00298 { 00299 typedef typename iterator_traits<_RandomAccessIterator>::difference_type 00300 _Distance; 00301 *__result = *__first; 00302 std::__adjust_heap(__first, _Distance(0), _Distance(__last - __first), 00303 __value, __comp); 00304 } 00305 00306 /** 00307 * @brief Pop an element off a heap using comparison functor. 00308 * @param first Start of heap. 00309 * @param last End of heap. 00310 * @param comp Comparison functor to use. 00311 * @ingroup heap 00312 * 00313 * This operation pops the top of the heap. The elements first and last-1 00314 * are swapped and [first,last-1) is made into a heap. Comparisons are 00315 * made using comp. 00316 */ 00317 template<typename _RandomAccessIterator, typename _Compare> 00318 inline void 00319 pop_heap(_RandomAccessIterator __first, 00320 _RandomAccessIterator __last, _Compare __comp) 00321 { 00322 // concept requirements 00323 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 00324 _RandomAccessIterator>) 00325 __glibcxx_requires_valid_range(__first, __last); 00326 __glibcxx_requires_heap_pred(__first, __last, __comp); 00327 00328 typedef typename iterator_traits<_RandomAccessIterator>::value_type 00329 _ValueType; 00330 std::__pop_heap(__first, __last - 1, __last - 1, 00331 _ValueType(*(__last - 1)), __comp); 00332 } 00333 00334 /** 00335 * @brief Construct a heap over a range. 00336 * @param first Start of heap. 00337 * @param last End of heap. 00338 * @ingroup heap 00339 * 00340 * This operation makes the elements in [first,last) into a heap. 00341 */ 00342 template<typename _RandomAccessIterator> 00343 void 00344 make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) 00345 { 00346 typedef typename iterator_traits<_RandomAccessIterator>::value_type 00347 _ValueType; 00348 typedef typename iterator_traits<_RandomAccessIterator>::difference_type 00349 _DistanceType; 00350 00351 // concept requirements 00352 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 00353 _RandomAccessIterator>) 00354 __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>) 00355 __glibcxx_requires_valid_range(__first, __last); 00356 00357 if (__last - __first < 2) 00358 return; 00359 00360 const _DistanceType __len = __last - __first; 00361 _DistanceType __parent = (__len - 2) / 2; 00362 while (true) 00363 { 00364 std::__adjust_heap(__first, __parent, __len, 00365 _ValueType(*(__first + __parent))); 00366 if (__parent == 0) 00367 return; 00368 __parent--; 00369 } 00370 } 00371 00372 /** 00373 * @brief Construct a heap over a range using comparison functor. 00374 * @param first Start of heap. 00375 * @param last End of heap. 00376 * @param comp Comparison functor to use. 00377 * @ingroup heap 00378 * 00379 * This operation makes the elements in [first,last) into a heap. 00380 * Comparisons are made using comp. 00381 */ 00382 template<typename _RandomAccessIterator, typename _Compare> 00383 inline void 00384 make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, 00385 _Compare __comp) 00386 { 00387 typedef typename iterator_traits<_RandomAccessIterator>::value_type 00388 _ValueType; 00389 typedef typename iterator_traits<_RandomAccessIterator>::difference_type 00390 _DistanceType; 00391 00392 // concept requirements 00393 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 00394 _RandomAccessIterator>) 00395 __glibcxx_requires_valid_range(__first, __last); 00396 00397 if (__last - __first < 2) 00398 return; 00399 00400 const _DistanceType __len = __last - __first; 00401 _DistanceType __parent = (__len - 2) / 2; 00402 while (true) 00403 { 00404 std::__adjust_heap(__first, __parent, __len, 00405 _ValueType(*(__first + __parent)), __comp); 00406 if (__parent == 0) 00407 return; 00408 __parent--; 00409 } 00410 } 00411 00412 /** 00413 * @brief Sort a heap. 00414 * @param first Start of heap. 00415 * @param last End of heap. 00416 * @ingroup heap 00417 * 00418 * This operation sorts the valid heap in the range [first,last). 00419 */ 00420 template<typename _RandomAccessIterator> 00421 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_heap(__first, __last); 00431 00432 while (__last - __first > 1) 00433 std::pop_heap(__first, __last--); 00434 } 00435 00436 /** 00437 * @brief Sort a heap using comparison functor. 00438 * @param first Start of heap. 00439 * @param last End of heap. 00440 * @param comp Comparison functor to use. 00441 * @ingroup heap 00442 * 00443 * This operation sorts the valid heap in the range [first,last). 00444 * Comparisons are made using comp. 00445 */ 00446 template<typename _RandomAccessIterator, typename _Compare> 00447 void 00448 sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, 00449 _Compare __comp) 00450 { 00451 // concept requirements 00452 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 00453 _RandomAccessIterator>) 00454 __glibcxx_requires_valid_range(__first, __last); 00455 __glibcxx_requires_heap_pred(__first, __last, __comp); 00456 00457 while (__last - __first > 1) 00458 std::pop_heap(__first, __last--, __comp); 00459 } 00460 00461 } // namespace std 00462 00463 #endif /* _STL_HEAP_H */ 00464 00465 // Local Variables: 00466 // mode:C++ 00467 // End: