00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012 #ifndef HEAPPLUS_H_
00013 #define HEAPPLUS_H_
00014
00015 #include <iterator>
00016
00017 namespace std {
00018 template<typename _RandomAccessIterator, typename _Distance, typename _Tp,
00019 typename _Compare, typename _Updatepos>
00020 void
00021 __push_heap(_RandomAccessIterator __first, _Distance __holeIndex,
00022 _Distance __topIndex, _Tp __value, _Compare __comp, _Updatepos __updatepos)
00023 {
00024 _Distance __parent = (__holeIndex - 1) / 2;
00025 while (__holeIndex > __topIndex
00026 && __comp(*(__first + __parent), __value))
00027 {
00028 *(__first + __holeIndex) = *(__first + __parent);
00029 __updatepos(*(__first + __holeIndex), __holeIndex);
00030 __holeIndex = __parent;
00031 __parent = (__holeIndex - 1) / 2;
00032 }
00033 *(__first + __holeIndex) = __value;
00034 __updatepos(*(__first + __holeIndex), __holeIndex);
00035 }
00036
00037 template<typename _RandomAccessIterator, typename _Compare, typename _Updatepos>
00038 inline void
00039 push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
00040 _Compare __comp, _Updatepos __updatepos)
00041 {
00042 typedef typename iterator_traits<_RandomAccessIterator>::value_type
00043 _ValueType;
00044 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
00045 _DistanceType;
00046
00047 std::__push_heap(__first, _DistanceType((__last - __first) - 1),
00048 _DistanceType(0), _ValueType(*(__last - 1)), __comp, __updatepos);
00049 }
00050
00051 template<typename _RandomAccessIterator, typename _Distance,
00052 typename _Tp, typename _Compare, typename _Updatepos>
00053 void
00054 __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
00055 _Distance __len, _Tp __value, _Compare __comp, _Updatepos __updatepos)
00056 {
00057 const _Distance __topIndex = __holeIndex;
00058 _Distance __secondChild = 2 * __holeIndex + 2;
00059 while (__secondChild < __len)
00060 {
00061 if (__comp(*(__first + __secondChild),
00062 *(__first + (__secondChild - 1))))
00063 __secondChild--;
00064 *(__first + __holeIndex) = *(__first + __secondChild);
00065 __updatepos(*(__first + __holeIndex), __holeIndex);
00066 __holeIndex = __secondChild;
00067 __secondChild = 2 * (__secondChild + 1);
00068 }
00069 if (__secondChild == __len)
00070 {
00071 *(__first + __holeIndex) = *(__first + (__secondChild - 1));
00072 __updatepos(*(__first + __holeIndex), __holeIndex);
00073 __holeIndex = __secondChild - 1;
00074 }
00075 std::__push_heap(__first, __holeIndex, __topIndex, __value, __comp, __updatepos);
00076 }
00077
00078 template<typename _RandomAccessIterator, typename _Tp, typename _Compare, typename _Updatepos>
00079 inline void
00080 __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
00081 _RandomAccessIterator __result, _Tp __value, _Compare __comp, _Updatepos __updatepos)
00082 {
00083 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
00084 _Distance;
00085 *__result = *__first;
00086 std::__adjust_heap(__first, _Distance(0), _Distance(__last - __first),
00087 __value, __comp, __updatepos);
00088 }
00089
00090 template<typename _RandomAccessIterator, typename _Compare, typename _Updatepos>
00091 inline void
00092 pop_heap(_RandomAccessIterator __first,
00093 _RandomAccessIterator __last, _Compare __comp, _Updatepos __updatepos)
00094 {
00095
00096 typedef typename iterator_traits<_RandomAccessIterator>::value_type
00097 _ValueType;
00098 std::__pop_heap(__first, __last - 1, __last - 1,
00099 _ValueType(*(__last - 1)), __comp, __updatepos);
00100 }
00101
00102 template<typename _RandomAccessIterator, typename _Compare, typename _Updatepos>
00103 inline void
00104 make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
00105 _Compare __comp, _Updatepos __updatepos)
00106 {
00107 typedef typename iterator_traits<_RandomAccessIterator>::value_type
00108 _ValueType;
00109 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
00110 _DistanceType;
00111
00112
00113
00114 if (__last - __first < 2)
00115 {
00116 for (_DistanceType __len = 0; __len < __last - __first; __len ++)
00117 {
00118 __updatepos(*(__first + __len), __len);
00119 }
00120
00121 return;
00122 }
00123 const _DistanceType __len = __last - __first;
00124 _DistanceType __parent = (__len - 2) / 2;
00125 while (true)
00126 {
00127 std::__adjust_heap(__first, __parent, __len,
00128 _ValueType(*(__first + __parent)), __comp, __updatepos);
00129 if (__parent == 0)
00130 {
00131 for (_DistanceType __len = 0; __len < __last - __first; __len ++)
00132 {
00133 __updatepos(*(__first + __len), __len);
00134 }
00135
00136 return;
00137 }
00138 __parent--;
00139 }
00140
00141 }
00142
00143
00144 template<typename _RandomAccessIterator, typename _Distance, typename _Tp, typename _Compare, typename _Updatepos>
00145 inline void
00146 __up_heap(_RandomAccessIterator __first, _RandomAccessIterator __end, _RandomAccessIterator __pos,
00147 _Distance, _Tp __value, _Compare __comp, _Updatepos __updatepos)
00148 {
00149 _Distance __parent = (__pos - __first - 1) / 2;
00150 _Distance __index = __pos - __first;
00151 while (__index > 0 && __comp(*(__first + __parent), __value)) {
00152 *(__first + __index) = *(__first + __parent);
00153 __updatepos(*(__first + __index), __index);
00154
00155 __index = __parent;
00156 __parent = (__parent - 1) / 2;
00157 }
00158
00159 if (__pos != (__first + __index)) {
00160 *(__first + __index) = __value;
00161 __updatepos(*(__first + __index), __index);
00162 }
00163 }
00164
00165 template<typename _RandomAccessIterator, typename _Distance, typename _Tp, typename _Compare, typename _Updatepos>
00166 inline void
00167 __down_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _RandomAccessIterator __pos,
00168 _Distance, _Tp __value, _Compare __comp, _Updatepos __updatepos)
00169 {
00170 _Distance __len = __last - __first;
00171 _Distance __index = __pos - __first;
00172 _Distance __left = __index * 2 + 1;
00173 _Distance __right = __index * 2 + 2;
00174 _Distance __largest;
00175 while (__index < __len)
00176 {
00177 if (__right < __len)
00178 {
00179 if (__comp(*(__first + __left), *(__first + __right)))
00180 {
00181 __largest = __right;
00182 }
00183 else
00184 {
00185 __largest = __left;
00186 }
00187 }
00188 else if (__left < __len)
00189 {
00190 __largest = __left;
00191 }
00192 else
00193 {
00194 __largest = __index;
00195 }
00196
00197 if (__largest < __len && __comp(__value, *(__first + __largest)))
00198 {
00199 *(__first + __index) = *(__first + __largest);
00200 __updatepos(*(__first + __index), __index);
00201 __index = __largest;
00202 *(__first + __index) = __value;
00203 __left = __index * 2 + 1;
00204 __right = __index * 2 + 2;
00205 } else
00206 break;
00207 }
00208
00209 if (__pos != (__first + __index)) {
00210 *(__first + __index) = __value;
00211 __updatepos(*(__first + __index), __index);
00212 }
00213 }
00214
00215 template<typename _RandomAccessIterator, typename _Distance, typename _Tp,
00216 typename _Compare, typename _Updatepos>
00217 inline void
00218 __update_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
00219 _RandomAccessIterator __pos, _Distance, _Tp __value, _Compare __comp, _Updatepos __updatepos)
00220 {
00221 *(__pos) = __value;
00222
00223 _Distance __index = (__pos - __first);
00224 _Distance __parent = (__index - 1) / 2;
00225
00226 if (__index > 0 && __comp(*(__first + __parent), __value))
00227 __up_heap(__first, __last, __pos, _Distance(), __value, __comp, __updatepos);
00228 else
00229 __down_heap(__first, __last, __pos, _Distance(), __value, __comp, __updatepos);
00230 }
00231
00232 template<typename _RandomAccessIterator, typename _Distance, typename _Compare, typename _Updatepos>
00233 inline void
00234 __update_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
00235 _RandomAccessIterator __pos, _Distance, _Compare __comp, _Updatepos __updatepos)
00236 {
00237 _Distance __index = (__pos - __first);
00238 _Distance __parent = (__index - 1) / 2;
00239 if (__index > 0 && __comp(*(__first + __parent), *(__pos)))
00240 __up_heap(__first, __last, __pos, _Distance(), *(__pos), __comp, __updatepos);
00241 else
00242 __down_heap(__first, __last, __pos, _Distance(), *(__pos), __comp, __updatepos);
00243 }
00244
00245 template<typename _RandomAccessIterator, typename _Tp, typename _Updatepos>
00246 inline void
00247 update_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
00248 _RandomAccessIterator __pos, _Tp __value, _Updatepos __updatepos)
00249 {
00250 typedef typename iterator_traits<_RandomAccessIterator>::value_type _ValueType;
00251 typedef typename iterator_traits<_RandomAccessIterator>::difference_type _DistanceType;
00252
00253 __update_heap(__first, __last, __pos, _DistanceType(), __value, less<_ValueType>(), __updatepos);
00254 }
00255
00256 template<typename _RandomAccessIterator, typename _Tp, typename _Compare, typename _Updatepos>
00257 inline void
00258 update_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
00259 _RandomAccessIterator __pos, _Tp __value, _Compare __comp, _Updatepos __updatepos)
00260 {
00261 __update_heap(__first, __last, __pos, __value, __comp, __updatepos);
00262 }
00263
00264
00265 template<typename _RandomAccessIterator, typename _Updatepos>
00266 inline void
00267 update_heap_pos(_RandomAccessIterator __first, _RandomAccessIterator __last,
00268 _RandomAccessIterator __pos, _Updatepos __updatepos) {
00269 typedef typename iterator_traits<_RandomAccessIterator>::value_type _ValueType;
00270 typedef typename iterator_traits<_RandomAccessIterator>::difference_type _DistanceType;
00271
00272 __update_heap(__first, __last, __pos, _DistanceType(), less<_ValueType>(), __updatepos);
00273 }
00274
00275
00276 template<typename _RandomAccessIterator, typename _Compare, typename _Updatepos>
00277 inline void
00278 update_heap_pos(_RandomAccessIterator __first, _RandomAccessIterator __last,
00279 _RandomAccessIterator __pos, _Compare __comp, _Updatepos __updatepos) {
00280 typedef typename iterator_traits<_RandomAccessIterator>::value_type _ValueType;
00281 typedef typename iterator_traits<_RandomAccessIterator>::difference_type _DistanceType;
00282
00283 __update_heap(__first, __last, __pos, _DistanceType(), __comp, __updatepos);
00284 }
00285
00286
00287
00288 }
00289
00290 #endif // !HEAPPLUS_H_