00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040
00041
00042
00043
00044
00045
00046
00047
00048
00049
00050
00051
00052
00053
00054
00055
00056
00057
00058
00059 #ifndef _CPP_BITS_STL_HEAP_H
00060 #define _CPP_BITS_STL_HEAP_H 1
00061
00062 namespace std
00063 {
00064
00065
00066
00067 template <class _RandomAccessIterator, class _Distance, class _Tp>
00068 void
00069 __push_heap(_RandomAccessIterator __first,
00070 _Distance __holeIndex, _Distance __topIndex, _Tp __value)
00071 {
00072 _Distance __parent = (__holeIndex - 1) / 2;
00073 while (__holeIndex > __topIndex && *(__first + __parent) < __value) {
00074 *(__first + __holeIndex) = *(__first + __parent);
00075 __holeIndex = __parent;
00076 __parent = (__holeIndex - 1) / 2;
00077 }
00078 *(__first + __holeIndex) = __value;
00079 }
00080
00081 template <class _RandomAccessIterator, class _Distance, class _Tp>
00082 inline void
00083 __push_heap_aux(_RandomAccessIterator __first,
00084 _RandomAccessIterator __last, _Distance*, _Tp*)
00085 {
00086 __push_heap(__first, _Distance((__last - __first) - 1), _Distance(0),
00087 _Tp(*(__last - 1)));
00088 }
00089
00090 template <class _RandomAccessIterator>
00091 inline void
00092 push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
00093 {
00094
00095 __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
00096 _RandomAccessIterator>);
00097 __glibcpp_function_requires(_LessThanComparableConcept<
00098 typename iterator_traits<_RandomAccessIterator>::value_type>);
00099
00100 __push_heap_aux(__first, __last,
00101 __distance_type(__first), __value_type(__first));
00102 }
00103
00104 template <class _RandomAccessIterator, class _Distance, class _Tp,
00105 class _Compare>
00106 void
00107 __push_heap(_RandomAccessIterator __first, _Distance __holeIndex,
00108 _Distance __topIndex, _Tp __value, _Compare __comp)
00109 {
00110 _Distance __parent = (__holeIndex - 1) / 2;
00111 while (__holeIndex > __topIndex && __comp(*(__first + __parent), __value)) {
00112 *(__first + __holeIndex) = *(__first + __parent);
00113 __holeIndex = __parent;
00114 __parent = (__holeIndex - 1) / 2;
00115 }
00116 *(__first + __holeIndex) = __value;
00117 }
00118
00119 template <class _RandomAccessIterator, class _Compare,
00120 class _Distance, class _Tp>
00121 inline void
00122 __push_heap_aux(_RandomAccessIterator __first,
00123 _RandomAccessIterator __last, _Compare __comp,
00124 _Distance*, _Tp*)
00125 {
00126 __push_heap(__first, _Distance((__last - __first) - 1), _Distance(0),
00127 _Tp(*(__last - 1)), __comp);
00128 }
00129
00130 template <class _RandomAccessIterator, class _Compare>
00131 inline void
00132 push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
00133 _Compare __comp)
00134 {
00135
00136 __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
00137 _RandomAccessIterator>);
00138
00139 __push_heap_aux(__first, __last, __comp,
00140 __distance_type(__first), __value_type(__first));
00141 }
00142
00143 template <class _RandomAccessIterator, class _Distance, class _Tp>
00144 void
00145 __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
00146 _Distance __len, _Tp __value)
00147 {
00148 _Distance __topIndex = __holeIndex;
00149 _Distance __secondChild = 2 * __holeIndex + 2;
00150 while (__secondChild < __len) {
00151 if (*(__first + __secondChild) < *(__first + (__secondChild - 1)))
00152 __secondChild--;
00153 *(__first + __holeIndex) = *(__first + __secondChild);
00154 __holeIndex = __secondChild;
00155 __secondChild = 2 * (__secondChild + 1);
00156 }
00157 if (__secondChild == __len) {
00158 *(__first + __holeIndex) = *(__first + (__secondChild - 1));
00159 __holeIndex = __secondChild - 1;
00160 }
00161 __push_heap(__first, __holeIndex, __topIndex, __value);
00162 }
00163
00164 template <class _RandomAccessIterator, class _Tp, class _Distance>
00165 inline void
00166 __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
00167 _RandomAccessIterator __result, _Tp __value, _Distance*)
00168 {
00169 *__result = *__first;
00170 __adjust_heap(__first, _Distance(0), _Distance(__last - __first), __value);
00171 }
00172
00173 template <class _RandomAccessIterator, class _Tp>
00174 inline void
00175 __pop_heap_aux(_RandomAccessIterator __first, _RandomAccessIterator __last,
00176 _Tp*)
00177 {
00178 __pop_heap(__first, __last - 1, __last - 1,
00179 _Tp(*(__last - 1)), __distance_type(__first));
00180 }
00181
00182 template <class _RandomAccessIterator>
00183 inline void pop_heap(_RandomAccessIterator __first,
00184 _RandomAccessIterator __last)
00185 {
00186
00187 __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
00188 _RandomAccessIterator>);
00189 __glibcpp_function_requires(_LessThanComparableConcept<
00190 typename iterator_traits<_RandomAccessIterator>::value_type>);
00191
00192 __pop_heap_aux(__first, __last, __value_type(__first));
00193 }
00194
00195 template <class _RandomAccessIterator, class _Distance,
00196 class _Tp, class _Compare>
00197 void
00198 __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
00199 _Distance __len, _Tp __value, _Compare __comp)
00200 {
00201 _Distance __topIndex = __holeIndex;
00202 _Distance __secondChild = 2 * __holeIndex + 2;
00203 while (__secondChild < __len) {
00204 if (__comp(*(__first + __secondChild), *(__first + (__secondChild - 1))))
00205 __secondChild--;
00206 *(__first + __holeIndex) = *(__first + __secondChild);
00207 __holeIndex = __secondChild;
00208 __secondChild = 2 * (__secondChild + 1);
00209 }
00210 if (__secondChild == __len) {
00211 *(__first + __holeIndex) = *(__first + (__secondChild - 1));
00212 __holeIndex = __secondChild - 1;
00213 }
00214 __push_heap(__first, __holeIndex, __topIndex, __value, __comp);
00215 }
00216
00217 template <class _RandomAccessIterator, class _Tp, class _Compare,
00218 class _Distance>
00219 inline void
00220 __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
00221 _RandomAccessIterator __result, _Tp __value, _Compare __comp,
00222 _Distance*)
00223 {
00224 *__result = *__first;
00225 __adjust_heap(__first, _Distance(0), _Distance(__last - __first),
00226 __value, __comp);
00227 }
00228
00229 template <class _RandomAccessIterator, class _Tp, class _Compare>
00230 inline void
00231 __pop_heap_aux(_RandomAccessIterator __first,
00232 _RandomAccessIterator __last, _Tp*, _Compare __comp)
00233 {
00234 __pop_heap(__first, __last - 1, __last - 1, _Tp(*(__last - 1)), __comp,
00235 __distance_type(__first));
00236 }
00237
00238 template <class _RandomAccessIterator, class _Compare>
00239 inline void
00240 pop_heap(_RandomAccessIterator __first,
00241 _RandomAccessIterator __last, _Compare __comp)
00242 {
00243
00244 __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
00245 _RandomAccessIterator>);
00246
00247 __pop_heap_aux(__first, __last, __value_type(__first), __comp);
00248 }
00249
00250 template <class _RandomAccessIterator, class _Tp, class _Distance>
00251 void
00252 __make_heap(_RandomAccessIterator __first,
00253 _RandomAccessIterator __last, _Tp*, _Distance*)
00254 {
00255 if (__last - __first < 2) return;
00256 _Distance __len = __last - __first;
00257 _Distance __parent = (__len - 2)/2;
00258
00259 while (true) {
00260 __adjust_heap(__first, __parent, __len, _Tp(*(__first + __parent)));
00261 if (__parent == 0) return;
00262 __parent--;
00263 }
00264 }
00265
00266 template <class _RandomAccessIterator>
00267 inline void
00268 make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
00269 {
00270
00271 __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
00272 _RandomAccessIterator>);
00273 __glibcpp_function_requires(_LessThanComparableConcept<
00274 typename iterator_traits<_RandomAccessIterator>::value_type>);
00275
00276 __make_heap(__first, __last,
00277 __value_type(__first), __distance_type(__first));
00278 }
00279
00280 template <class _RandomAccessIterator, class _Compare,
00281 class _Tp, class _Distance>
00282 void
00283 __make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
00284 _Compare __comp, _Tp*, _Distance*)
00285 {
00286 if (__last - __first < 2) return;
00287 _Distance __len = __last - __first;
00288 _Distance __parent = (__len - 2)/2;
00289
00290 while (true) {
00291 __adjust_heap(__first, __parent, __len, _Tp(*(__first + __parent)),
00292 __comp);
00293 if (__parent == 0) return;
00294 __parent--;
00295 }
00296 }
00297
00298 template <class _RandomAccessIterator, class _Compare>
00299 inline void
00300 make_heap(_RandomAccessIterator __first,
00301 _RandomAccessIterator __last, _Compare __comp)
00302 {
00303
00304 __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
00305 _RandomAccessIterator>);
00306
00307 __make_heap(__first, __last, __comp,
00308 __value_type(__first), __distance_type(__first));
00309 }
00310
00311 template <class _RandomAccessIterator>
00312 void sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
00313 {
00314
00315 __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
00316 _RandomAccessIterator>);
00317 __glibcpp_function_requires(_LessThanComparableConcept<
00318 typename iterator_traits<_RandomAccessIterator>::value_type>);
00319
00320 while (__last - __first > 1)
00321 pop_heap(__first, __last--);
00322 }
00323
00324 template <class _RandomAccessIterator, class _Compare>
00325 void
00326 sort_heap(_RandomAccessIterator __first,
00327 _RandomAccessIterator __last, _Compare __comp)
00328 {
00329
00330 __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
00331 _RandomAccessIterator>);
00332
00333 while (__last - __first > 1)
00334 pop_heap(__first, __last--, __comp);
00335 }
00336
00337 }
00338
00339 #endif
00340
00341
00342
00343