stl_heap.h

Go to the documentation of this file.
00001 // Heap implementation -*- C++ -*- 00002 00003 // Copyright (C) 2001 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 00060 #ifndef _CPP_BITS_STL_HEAP_H 00061 #define _CPP_BITS_STL_HEAP_H 1 00062 00063 namespace std 00064 { 00065 00066 // Heap-manipulation functions: push_heap, pop_heap, make_heap, sort_heap. 00067 00068 template<typename _RandomAccessIterator, typename _Distance, typename _Tp> 00069 void 00070 __push_heap(_RandomAccessIterator __first, 00071 _Distance __holeIndex, _Distance __topIndex, _Tp __value) 00072 { 00073 _Distance __parent = (__holeIndex - 1) / 2; 00074 while (__holeIndex > __topIndex && *(__first + __parent) < __value) { 00075 *(__first + __holeIndex) = *(__first + __parent); 00076 __holeIndex = __parent; 00077 __parent = (__holeIndex - 1) / 2; 00078 } 00079 *(__first + __holeIndex) = __value; 00080 } 00081 00082 template<typename _RandomAccessIterator> 00083 inline void 00084 push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) 00085 { 00086 typedef typename iterator_traits<_RandomAccessIterator>::value_type 00087 _ValueType; 00088 typedef typename iterator_traits<_RandomAccessIterator>::difference_type 00089 _DistanceType; 00090 00091 // concept requirements 00092 __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept< 00093 _RandomAccessIterator>) 00094 __glibcpp_function_requires(_LessThanComparableConcept<_ValueType>) 00095 00096 __push_heap(__first, _DistanceType((__last - __first) - 1), _DistanceType(0), 00097 _ValueType(*(__last - 1))); 00098 } 00099 00100 template<typename _RandomAccessIterator, typename _Distance, typename _Tp, 00101 typename _Compare> 00102 void 00103 __push_heap(_RandomAccessIterator __first, _Distance __holeIndex, 00104 _Distance __topIndex, _Tp __value, _Compare __comp) 00105 { 00106 _Distance __parent = (__holeIndex - 1) / 2; 00107 while (__holeIndex > __topIndex && __comp(*(__first + __parent), __value)) { 00108 *(__first + __holeIndex) = *(__first + __parent); 00109 __holeIndex = __parent; 00110 __parent = (__holeIndex - 1) / 2; 00111 } 00112 *(__first + __holeIndex) = __value; 00113 } 00114 00115 template<typename _RandomAccessIterator, typename _Compare> 00116 inline void 00117 push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, 00118 _Compare __comp) 00119 { 00120 typedef typename iterator_traits<_RandomAccessIterator>::value_type 00121 _ValueType; 00122 typedef typename iterator_traits<_RandomAccessIterator>::difference_type 00123 _DistanceType; 00124 00125 // concept requirements 00126 __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept< 00127 _RandomAccessIterator>) 00128 00129 __push_heap(__first, _DistanceType((__last - __first) - 1), _DistanceType(0), 00130 _ValueType(*(__last - 1)), __comp); 00131 } 00132 00133 template<typename _RandomAccessIterator, typename _Distance, typename _Tp> 00134 void 00135 __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex, 00136 _Distance __len, _Tp __value) 00137 { 00138 _Distance __topIndex = __holeIndex; 00139 _Distance __secondChild = 2 * __holeIndex + 2; 00140 while (__secondChild < __len) { 00141 if (*(__first + __secondChild) < *(__first + (__secondChild - 1))) 00142 __secondChild--; 00143 *(__first + __holeIndex) = *(__first + __secondChild); 00144 __holeIndex = __secondChild; 00145 __secondChild = 2 * (__secondChild + 1); 00146 } 00147 if (__secondChild == __len) { 00148 *(__first + __holeIndex) = *(__first + (__secondChild - 1)); 00149 __holeIndex = __secondChild - 1; 00150 } 00151 __push_heap(__first, __holeIndex, __topIndex, __value); 00152 } 00153 00154 template<typename _RandomAccessIterator, typename _Tp> 00155 inline void 00156 __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, 00157 _RandomAccessIterator __result, _Tp __value) 00158 { 00159 typedef typename iterator_traits<_RandomAccessIterator>::difference_type _Distance; 00160 *__result = *__first; 00161 __adjust_heap(__first, _Distance(0), _Distance(__last - __first), __value); 00162 } 00163 00164 template<typename _RandomAccessIterator> 00165 inline void 00166 pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) 00167 { 00168 typedef typename iterator_traits<_RandomAccessIterator>::value_type _ValueType; 00169 00170 // concept requirements 00171 __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept< 00172 _RandomAccessIterator>) 00173 __glibcpp_function_requires(_LessThanComparableConcept<_ValueType>) 00174 00175 __pop_heap(__first, __last - 1, __last - 1, _ValueType(*(__last - 1))); 00176 } 00177 00178 template<typename _RandomAccessIterator, typename _Distance, 00179 typename _Tp, typename _Compare> 00180 void 00181 __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex, 00182 _Distance __len, _Tp __value, _Compare __comp) 00183 { 00184 _Distance __topIndex = __holeIndex; 00185 _Distance __secondChild = 2 * __holeIndex + 2; 00186 while (__secondChild < __len) { 00187 if (__comp(*(__first + __secondChild), *(__first + (__secondChild - 1)))) 00188 __secondChild--; 00189 *(__first + __holeIndex) = *(__first + __secondChild); 00190 __holeIndex = __secondChild; 00191 __secondChild = 2 * (__secondChild + 1); 00192 } 00193 if (__secondChild == __len) { 00194 *(__first + __holeIndex) = *(__first + (__secondChild - 1)); 00195 __holeIndex = __secondChild - 1; 00196 } 00197 __push_heap(__first, __holeIndex, __topIndex, __value, __comp); 00198 } 00199 00200 template<typename _RandomAccessIterator, typename _Tp, typename _Compare> 00201 inline void 00202 __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, 00203 _RandomAccessIterator __result, _Tp __value, _Compare __comp) 00204 { 00205 typedef typename iterator_traits<_RandomAccessIterator>::difference_type _Distance; 00206 *__result = *__first; 00207 __adjust_heap(__first, _Distance(0), _Distance(__last - __first), 00208 __value, __comp); 00209 } 00210 00211 template<typename _RandomAccessIterator, typename _Compare> 00212 inline void 00213 pop_heap(_RandomAccessIterator __first, 00214 _RandomAccessIterator __last, _Compare __comp) 00215 { 00216 // concept requirements 00217 __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept< 00218 _RandomAccessIterator>) 00219 00220 typedef typename iterator_traits<_RandomAccessIterator>::value_type _ValueType; 00221 __pop_heap(__first, __last - 1, __last - 1, _ValueType(*(__last - 1)), __comp); 00222 } 00223 00224 template<typename _RandomAccessIterator> 00225 void 00226 make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) 00227 { 00228 typedef typename iterator_traits<_RandomAccessIterator>::value_type 00229 _ValueType; 00230 typedef typename iterator_traits<_RandomAccessIterator>::difference_type 00231 _DistanceType; 00232 00233 // concept requirements 00234 __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept< 00235 _RandomAccessIterator>) 00236 __glibcpp_function_requires(_LessThanComparableConcept<_ValueType>) 00237 00238 if (__last - __first < 2) return; 00239 _DistanceType __len = __last - __first; 00240 _DistanceType __parent = (__len - 2)/2; 00241 00242 while (true) { 00243 __adjust_heap(__first, __parent, __len, _ValueType(*(__first + __parent))); 00244 if (__parent == 0) return; 00245 __parent--; 00246 } 00247 } 00248 00249 template<typename _RandomAccessIterator, typename _Compare> 00250 inline void 00251 make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, 00252 _Compare __comp) 00253 { 00254 typedef typename iterator_traits<_RandomAccessIterator>::value_type 00255 _ValueType; 00256 typedef typename iterator_traits<_RandomAccessIterator>::difference_type 00257 _DistanceType; 00258 00259 // concept requirements 00260 __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept< 00261 _RandomAccessIterator>) 00262 00263 if (__last - __first < 2) return; 00264 _DistanceType __len = __last - __first; 00265 _DistanceType __parent = (__len - 2)/2; 00266 00267 while (true) { 00268 __adjust_heap(__first, __parent, __len, 00269 _ValueType(*(__first + __parent)), __comp); 00270 if (__parent == 0) return; 00271 __parent--; 00272 } 00273 } 00274 00275 template<typename _RandomAccessIterator> 00276 void 00277 sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) 00278 { 00279 // concept requirements 00280 __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept< 00281 _RandomAccessIterator>) 00282 __glibcpp_function_requires(_LessThanComparableConcept< 00283 typename iterator_traits<_RandomAccessIterator>::value_type>) 00284 00285 while (__last - __first > 1) 00286 pop_heap(__first, __last--); 00287 } 00288 00289 template<typename _RandomAccessIterator, typename _Compare> 00290 void 00291 sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, 00292 _Compare __comp) 00293 { 00294 // concept requirements 00295 __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept< 00296 _RandomAccessIterator>) 00297 00298 while (__last - __first > 1) 00299 pop_heap(__first, __last--, __comp); 00300 } 00301 00302 } // namespace std 00303 00304 #endif /* _CPP_BITS_STL_HEAP_H */ 00305 00306 // Local Variables: 00307 // mode:C++ 00308 // End:

Generated on Wed Sep 29 13:54:51 2004 for libstdc++-v3 Source by doxygen 1.3.7