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 #ifndef _STL_HEAP_H
00057 #define _STL_HEAP_H 1
00058
00059 #include <debug/debug.h>
00060 #include <bits/move.h>
00061
00062 _GLIBCXX_BEGIN_NAMESPACE(std)
00063
00064
00065
00066
00067
00068
00069 template<typename _RandomAccessIterator, typename _Distance>
00070 _Distance
00071 __is_heap_until(_RandomAccessIterator __first, _Distance __n)
00072 {
00073 _Distance __parent = 0;
00074 for (_Distance __child = 1; __child < __n; ++__child)
00075 {
00076 if (__first[__parent] < __first[__child])
00077 return __child;
00078 if ((__child & 1) == 0)
00079 ++__parent;
00080 }
00081 return __n;
00082 }
00083
00084 template<typename _RandomAccessIterator, typename _Distance,
00085 typename _Compare>
00086 _Distance
00087 __is_heap_until(_RandomAccessIterator __first, _Distance __n,
00088 _Compare __comp)
00089 {
00090 _Distance __parent = 0;
00091 for (_Distance __child = 1; __child < __n; ++__child)
00092 {
00093 if (__comp(__first[__parent], __first[__child]))
00094 return __child;
00095 if ((__child & 1) == 0)
00096 ++__parent;
00097 }
00098 return __n;
00099 }
00100
00101
00102
00103 template<typename _RandomAccessIterator, typename _Distance>
00104 inline bool
00105 __is_heap(_RandomAccessIterator __first, _Distance __n)
00106 { return std::__is_heap_until(__first, __n) == __n; }
00107
00108 template<typename _RandomAccessIterator, typename _Compare,
00109 typename _Distance>
00110 inline bool
00111 __is_heap(_RandomAccessIterator __first, _Compare __comp, _Distance __n)
00112 { return std::__is_heap_until(__first, __n, __comp) == __n; }
00113
00114 template<typename _RandomAccessIterator>
00115 inline bool
00116 __is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
00117 { return std::__is_heap(__first, std::distance(__first, __last)); }
00118
00119 template<typename _RandomAccessIterator, typename _Compare>
00120 inline bool
00121 __is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
00122 _Compare __comp)
00123 { return std::__is_heap(__first, __comp, std::distance(__first, __last)); }
00124
00125
00126
00127
00128 template<typename _RandomAccessIterator, typename _Distance, typename _Tp>
00129 void
00130 __push_heap(_RandomAccessIterator __first,
00131 _Distance __holeIndex, _Distance __topIndex, _Tp __value)
00132 {
00133 _Distance __parent = (__holeIndex - 1) / 2;
00134 while (__holeIndex > __topIndex && *(__first + __parent) < __value)
00135 {
00136 *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __parent));
00137 __holeIndex = __parent;
00138 __parent = (__holeIndex - 1) / 2;
00139 }
00140 *(__first + __holeIndex) = _GLIBCXX_MOVE(__value);
00141 }
00142
00143
00144
00145
00146
00147
00148
00149
00150
00151
00152 template<typename _RandomAccessIterator>
00153 inline void
00154 push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
00155 {
00156 typedef typename iterator_traits<_RandomAccessIterator>::value_type
00157 _ValueType;
00158 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
00159 _DistanceType;
00160
00161
00162 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
00163 _RandomAccessIterator>)
00164 __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
00165 __glibcxx_requires_valid_range(__first, __last);
00166 __glibcxx_requires_heap(__first, __last - 1);
00167
00168 _ValueType __value = _GLIBCXX_MOVE(*(__last - 1));
00169 std::__push_heap(__first, _DistanceType((__last - __first) - 1),
00170 _DistanceType(0), _GLIBCXX_MOVE(__value));
00171 }
00172
00173 template<typename _RandomAccessIterator, typename _Distance, typename _Tp,
00174 typename _Compare>
00175 void
00176 __push_heap(_RandomAccessIterator __first, _Distance __holeIndex,
00177 _Distance __topIndex, _Tp __value, _Compare __comp)
00178 {
00179 _Distance __parent = (__holeIndex - 1) / 2;
00180 while (__holeIndex > __topIndex
00181 && __comp(*(__first + __parent), __value))
00182 {
00183 *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __parent));
00184 __holeIndex = __parent;
00185 __parent = (__holeIndex - 1) / 2;
00186 }
00187 *(__first + __holeIndex) = _GLIBCXX_MOVE(__value);
00188 }
00189
00190
00191
00192
00193
00194
00195
00196
00197
00198
00199
00200
00201 template<typename _RandomAccessIterator, typename _Compare>
00202 inline void
00203 push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
00204 _Compare __comp)
00205 {
00206 typedef typename iterator_traits<_RandomAccessIterator>::value_type
00207 _ValueType;
00208 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
00209 _DistanceType;
00210
00211
00212 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
00213 _RandomAccessIterator>)
00214 __glibcxx_requires_valid_range(__first, __last);
00215 __glibcxx_requires_heap_pred(__first, __last - 1, __comp);
00216
00217 _ValueType __value = _GLIBCXX_MOVE(*(__last - 1));
00218 std::__push_heap(__first, _DistanceType((__last - __first) - 1),
00219 _DistanceType(0), _GLIBCXX_MOVE(__value), __comp);
00220 }
00221
00222 template<typename _RandomAccessIterator, typename _Distance, typename _Tp>
00223 void
00224 __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
00225 _Distance __len, _Tp __value)
00226 {
00227 const _Distance __topIndex = __holeIndex;
00228 _Distance __secondChild = __holeIndex;
00229 while (__secondChild < (__len - 1) / 2)
00230 {
00231 __secondChild = 2 * (__secondChild + 1);
00232 if (*(__first + __secondChild) < *(__first + (__secondChild - 1)))
00233 __secondChild--;
00234 *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __secondChild));
00235 __holeIndex = __secondChild;
00236 }
00237 if ((__len & 1) == 0 && __secondChild == (__len - 2) / 2)
00238 {
00239 __secondChild = 2 * (__secondChild + 1);
00240 *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first
00241 + (__secondChild - 1)));
00242 __holeIndex = __secondChild - 1;
00243 }
00244 std::__push_heap(__first, __holeIndex, __topIndex,
00245 _GLIBCXX_MOVE(__value));
00246 }
00247
00248 template<typename _RandomAccessIterator>
00249 inline void
00250 __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
00251 _RandomAccessIterator __result)
00252 {
00253 typedef typename iterator_traits<_RandomAccessIterator>::value_type
00254 _ValueType;
00255 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
00256 _DistanceType;
00257
00258 _ValueType __value = _GLIBCXX_MOVE(*__result);
00259 *__result = _GLIBCXX_MOVE(*__first);
00260 std::__adjust_heap(__first, _DistanceType(0),
00261 _DistanceType(__last - __first),
00262 _GLIBCXX_MOVE(__value));
00263 }
00264
00265
00266
00267
00268
00269
00270
00271
00272
00273
00274 template<typename _RandomAccessIterator>
00275 inline void
00276 pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
00277 {
00278 typedef typename iterator_traits<_RandomAccessIterator>::value_type
00279 _ValueType;
00280
00281
00282 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
00283 _RandomAccessIterator>)
00284 __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
00285 __glibcxx_requires_valid_range(__first, __last);
00286 __glibcxx_requires_heap(__first, __last);
00287
00288 --__last;
00289 std::__pop_heap(__first, __last, __last);
00290 }
00291
00292 template<typename _RandomAccessIterator, typename _Distance,
00293 typename _Tp, typename _Compare>
00294 void
00295 __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
00296 _Distance __len, _Tp __value, _Compare __comp)
00297 {
00298 const _Distance __topIndex = __holeIndex;
00299 _Distance __secondChild = __holeIndex;
00300 while (__secondChild < (__len - 1) / 2)
00301 {
00302 __secondChild = 2 * (__secondChild + 1);
00303 if (__comp(*(__first + __secondChild),
00304 *(__first + (__secondChild - 1))))
00305 __secondChild--;
00306 *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __secondChild));
00307 __holeIndex = __secondChild;
00308 }
00309 if ((__len & 1) == 0 && __secondChild == (__len - 2) / 2)
00310 {
00311 __secondChild = 2 * (__secondChild + 1);
00312 *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first
00313 + (__secondChild - 1)));
00314 __holeIndex = __secondChild - 1;
00315 }
00316 std::__push_heap(__first, __holeIndex, __topIndex,
00317 _GLIBCXX_MOVE(__value), __comp);
00318 }
00319
00320 template<typename _RandomAccessIterator, typename _Compare>
00321 inline void
00322 __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
00323 _RandomAccessIterator __result, _Compare __comp)
00324 {
00325 typedef typename iterator_traits<_RandomAccessIterator>::value_type
00326 _ValueType;
00327 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
00328 _DistanceType;
00329
00330 _ValueType __value = _GLIBCXX_MOVE(*__result);
00331 *__result = _GLIBCXX_MOVE(*__first);
00332 std::__adjust_heap(__first, _DistanceType(0),
00333 _DistanceType(__last - __first),
00334 _GLIBCXX_MOVE(__value), __comp);
00335 }
00336
00337
00338
00339
00340
00341
00342
00343
00344
00345
00346
00347
00348 template<typename _RandomAccessIterator, typename _Compare>
00349 inline void
00350 pop_heap(_RandomAccessIterator __first,
00351 _RandomAccessIterator __last, _Compare __comp)
00352 {
00353
00354 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
00355 _RandomAccessIterator>)
00356 __glibcxx_requires_valid_range(__first, __last);
00357 __glibcxx_requires_heap_pred(__first, __last, __comp);
00358
00359 --__last;
00360 std::__pop_heap(__first, __last, __last, __comp);
00361 }
00362
00363
00364
00365
00366
00367
00368
00369
00370
00371 template<typename _RandomAccessIterator>
00372 void
00373 make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
00374 {
00375 typedef typename iterator_traits<_RandomAccessIterator>::value_type
00376 _ValueType;
00377 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
00378 _DistanceType;
00379
00380
00381 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
00382 _RandomAccessIterator>)
00383 __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
00384 __glibcxx_requires_valid_range(__first, __last);
00385
00386 if (__last - __first < 2)
00387 return;
00388
00389 const _DistanceType __len = __last - __first;
00390 _DistanceType __parent = (__len - 2) / 2;
00391 while (true)
00392 {
00393 _ValueType __value = _GLIBCXX_MOVE(*(__first + __parent));
00394 std::__adjust_heap(__first, __parent, __len, _GLIBCXX_MOVE(__value));
00395 if (__parent == 0)
00396 return;
00397 __parent--;
00398 }
00399 }
00400
00401
00402
00403
00404
00405
00406
00407
00408
00409
00410
00411 template<typename _RandomAccessIterator, typename _Compare>
00412 void
00413 make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
00414 _Compare __comp)
00415 {
00416 typedef typename iterator_traits<_RandomAccessIterator>::value_type
00417 _ValueType;
00418 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
00419 _DistanceType;
00420
00421
00422 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
00423 _RandomAccessIterator>)
00424 __glibcxx_requires_valid_range(__first, __last);
00425
00426 if (__last - __first < 2)
00427 return;
00428
00429 const _DistanceType __len = __last - __first;
00430 _DistanceType __parent = (__len - 2) / 2;
00431 while (true)
00432 {
00433 _ValueType __value = _GLIBCXX_MOVE(*(__first + __parent));
00434 std::__adjust_heap(__first, __parent, __len, _GLIBCXX_MOVE(__value),
00435 __comp);
00436 if (__parent == 0)
00437 return;
00438 __parent--;
00439 }
00440 }
00441
00442
00443
00444
00445
00446
00447
00448
00449
00450 template<typename _RandomAccessIterator>
00451 void
00452 sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
00453 {
00454
00455 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
00456 _RandomAccessIterator>)
00457 __glibcxx_function_requires(_LessThanComparableConcept<
00458 typename iterator_traits<_RandomAccessIterator>::value_type>)
00459 __glibcxx_requires_valid_range(__first, __last);
00460 __glibcxx_requires_heap(__first, __last);
00461
00462 while (__last - __first > 1)
00463 {
00464 --__last;
00465 std::__pop_heap(__first, __last, __last);
00466 }
00467 }
00468
00469
00470
00471
00472
00473
00474
00475
00476
00477
00478
00479 template<typename _RandomAccessIterator, typename _Compare>
00480 void
00481 sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
00482 _Compare __comp)
00483 {
00484
00485 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
00486 _RandomAccessIterator>)
00487 __glibcxx_requires_valid_range(__first, __last);
00488 __glibcxx_requires_heap_pred(__first, __last, __comp);
00489
00490 while (__last - __first > 1)
00491 {
00492 --__last;
00493 std::__pop_heap(__first, __last, __last, __comp);
00494 }
00495 }
00496
00497 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00498
00499
00500
00501
00502
00503
00504
00505
00506
00507
00508 template<typename _RandomAccessIterator>
00509 inline _RandomAccessIterator
00510 is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last)
00511 {
00512
00513 __glibcxx_function_requires(_RandomAccessIteratorConcept<
00514 _RandomAccessIterator>)
00515 __glibcxx_function_requires(_LessThanComparableConcept<
00516 typename iterator_traits<_RandomAccessIterator>::value_type>)
00517 __glibcxx_requires_valid_range(__first, __last);
00518
00519 return __first + std::__is_heap_until(__first, std::distance(__first,
00520 __last));
00521 }
00522
00523
00524
00525
00526
00527
00528
00529
00530
00531
00532
00533
00534 template<typename _RandomAccessIterator, typename _Compare>
00535 inline _RandomAccessIterator
00536 is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last,
00537 _Compare __comp)
00538 {
00539
00540 __glibcxx_function_requires(_RandomAccessIteratorConcept<
00541 _RandomAccessIterator>)
00542 __glibcxx_requires_valid_range(__first, __last);
00543
00544 return __first + std::__is_heap_until(__first, std::distance(__first,
00545 __last),
00546 __comp);
00547 }
00548
00549
00550
00551
00552
00553
00554
00555
00556 template<typename _RandomAccessIterator>
00557 inline bool
00558 is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
00559 { return std::is_heap_until(__first, __last) == __last; }
00560
00561
00562
00563
00564
00565
00566
00567
00568
00569 template<typename _RandomAccessIterator, typename _Compare>
00570 inline bool
00571 is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
00572 _Compare __comp)
00573 { return std::is_heap_until(__first, __last, __comp) == __last; }
00574 #endif
00575
00576 _GLIBCXX_END_NAMESPACE
00577
00578 #endif