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
00061 #ifndef _STL_HEAP_H
00062 #define _STL_HEAP_H 1
00063
00064 #include <debug/debug.h>
00065 #include <bits/stl_move.h>
00066
00067 _GLIBCXX_BEGIN_NAMESPACE(std)
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 std::__pop_heap(__first, __last - 1, __last - 1);
00289 }
00290
00291 template<typename _RandomAccessIterator, typename _Distance,
00292 typename _Tp, typename _Compare>
00293 void
00294 __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
00295 _Distance __len, _Tp __value, _Compare __comp)
00296 {
00297 const _Distance __topIndex = __holeIndex;
00298 _Distance __secondChild = __holeIndex;
00299 while (__secondChild < (__len - 1) / 2)
00300 {
00301 __secondChild = 2 * (__secondChild + 1);
00302 if (__comp(*(__first + __secondChild),
00303 *(__first + (__secondChild - 1))))
00304 __secondChild--;
00305 *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __secondChild));
00306 __holeIndex = __secondChild;
00307 }
00308 if ((__len & 1) == 0 && __secondChild == (__len - 2) / 2)
00309 {
00310 __secondChild = 2 * (__secondChild + 1);
00311 *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first
00312 + (__secondChild - 1)));
00313 __holeIndex = __secondChild - 1;
00314 }
00315 std::__push_heap(__first, __holeIndex, __topIndex,
00316 _GLIBCXX_MOVE(__value), __comp);
00317 }
00318
00319 template<typename _RandomAccessIterator, typename _Compare>
00320 inline void
00321 __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
00322 _RandomAccessIterator __result, _Compare __comp)
00323 {
00324 typedef typename iterator_traits<_RandomAccessIterator>::value_type
00325 _ValueType;
00326 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
00327 _DistanceType;
00328
00329 _ValueType __value = _GLIBCXX_MOVE(*__result);
00330 *__result = _GLIBCXX_MOVE(*__first);
00331 std::__adjust_heap(__first, _DistanceType(0),
00332 _DistanceType(__last - __first),
00333 _GLIBCXX_MOVE(__value), __comp);
00334 }
00335
00336
00337
00338
00339
00340
00341
00342
00343
00344
00345
00346
00347 template<typename _RandomAccessIterator, typename _Compare>
00348 inline void
00349 pop_heap(_RandomAccessIterator __first,
00350 _RandomAccessIterator __last, _Compare __comp)
00351 {
00352
00353 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
00354 _RandomAccessIterator>)
00355 __glibcxx_requires_valid_range(__first, __last);
00356 __glibcxx_requires_heap_pred(__first, __last, __comp);
00357
00358 std::__pop_heap(__first, __last - 1, __last - 1, __comp);
00359 }
00360
00361
00362
00363
00364
00365
00366
00367
00368
00369 template<typename _RandomAccessIterator>
00370 void
00371 make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
00372 {
00373 typedef typename iterator_traits<_RandomAccessIterator>::value_type
00374 _ValueType;
00375 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
00376 _DistanceType;
00377
00378
00379 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
00380 _RandomAccessIterator>)
00381 __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
00382 __glibcxx_requires_valid_range(__first, __last);
00383
00384 if (__last - __first < 2)
00385 return;
00386
00387 const _DistanceType __len = __last - __first;
00388 _DistanceType __parent = (__len - 2) / 2;
00389 while (true)
00390 {
00391 _ValueType __value = _GLIBCXX_MOVE(*(__first + __parent));
00392 std::__adjust_heap(__first, __parent, __len, _GLIBCXX_MOVE(__value));
00393 if (__parent == 0)
00394 return;
00395 __parent--;
00396 }
00397 }
00398
00399
00400
00401
00402
00403
00404
00405
00406
00407
00408
00409 template<typename _RandomAccessIterator, typename _Compare>
00410 void
00411 make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
00412 _Compare __comp)
00413 {
00414 typedef typename iterator_traits<_RandomAccessIterator>::value_type
00415 _ValueType;
00416 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
00417 _DistanceType;
00418
00419
00420 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
00421 _RandomAccessIterator>)
00422 __glibcxx_requires_valid_range(__first, __last);
00423
00424 if (__last - __first < 2)
00425 return;
00426
00427 const _DistanceType __len = __last - __first;
00428 _DistanceType __parent = (__len - 2) / 2;
00429 while (true)
00430 {
00431 _ValueType __value = _GLIBCXX_MOVE(*(__first + __parent));
00432 std::__adjust_heap(__first, __parent, __len, _GLIBCXX_MOVE(__value),
00433 __comp);
00434 if (__parent == 0)
00435 return;
00436 __parent--;
00437 }
00438 }
00439
00440
00441
00442
00443
00444
00445
00446
00447
00448 template<typename _RandomAccessIterator>
00449 void
00450 sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
00451 {
00452
00453 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
00454 _RandomAccessIterator>)
00455 __glibcxx_function_requires(_LessThanComparableConcept<
00456 typename iterator_traits<_RandomAccessIterator>::value_type>)
00457 __glibcxx_requires_valid_range(__first, __last);
00458 __glibcxx_requires_heap(__first, __last);
00459
00460 while (__last - __first > 1)
00461 std::pop_heap(__first, _RandomAccessIterator(__last--));
00462 }
00463
00464
00465
00466
00467
00468
00469
00470
00471
00472
00473
00474 template<typename _RandomAccessIterator, typename _Compare>
00475 void
00476 sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
00477 _Compare __comp)
00478 {
00479
00480 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
00481 _RandomAccessIterator>)
00482 __glibcxx_requires_valid_range(__first, __last);
00483 __glibcxx_requires_heap_pred(__first, __last, __comp);
00484
00485 while (__last - __first > 1)
00486 std::pop_heap(__first, _RandomAccessIterator(__last--), __comp);
00487 }
00488
00489 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00490
00491
00492
00493
00494
00495
00496
00497
00498
00499
00500 template<typename _RandomAccessIterator>
00501 inline _RandomAccessIterator
00502 is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last)
00503 {
00504
00505 __glibcxx_function_requires(_RandomAccessIteratorConcept<
00506 _RandomAccessIterator>)
00507 __glibcxx_function_requires(_LessThanComparableConcept<
00508 typename iterator_traits<_RandomAccessIterator>::value_type>)
00509 __glibcxx_requires_valid_range(__first, __last);
00510
00511 return __first + std::__is_heap_until(__first, std::distance(__first,
00512 __last));
00513 }
00514
00515
00516
00517
00518
00519
00520
00521
00522
00523
00524
00525
00526 template<typename _RandomAccessIterator, typename _Compare>
00527 inline _RandomAccessIterator
00528 is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last,
00529 _Compare __comp)
00530 {
00531
00532 __glibcxx_function_requires(_RandomAccessIteratorConcept<
00533 _RandomAccessIterator>)
00534 __glibcxx_requires_valid_range(__first, __last);
00535
00536 return __first + std::__is_heap_until(__first, std::distance(__first,
00537 __last),
00538 __comp);
00539 }
00540
00541
00542
00543
00544
00545
00546
00547
00548 template<typename _RandomAccessIterator>
00549 inline bool
00550 is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
00551 { return std::is_heap_until(__first, __last) == __last; }
00552
00553
00554
00555
00556
00557
00558
00559
00560
00561 template<typename _RandomAccessIterator, typename _Compare>
00562 inline bool
00563 is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
00564 _Compare __comp)
00565 { return std::is_heap_until(__first, __last, __comp) == __last; }
00566 #endif
00567
00568 _GLIBCXX_END_NAMESPACE
00569
00570 #endif