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
00060 #ifndef _CPP_BITS_STL_HEAP_H
00061 #define _CPP_BITS_STL_HEAP_H 1
00062
00063 namespace std
00064 {
00065
00066
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
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
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
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
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
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
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
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
00295 __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
00296 _RandomAccessIterator>)
00297
00298 while (__last - __first > 1)
00299 pop_heap(__first, __last--, __comp);
00300 }
00301
00302 }
00303
00304 #endif
00305
00306
00307
00308