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