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 __SGI_STL_INTERNAL_ALGO_H
00061 #define __SGI_STL_INTERNAL_ALGO_H
00062
00063 #include <bits/stl_heap.h>
00064
00065
00066
00067 namespace std
00068 {
00069
00070
00071
00072 template <class _Tp>
00073 inline const _Tp& __median(const _Tp& __a, const _Tp& __b, const _Tp& __c)
00074 {
00075
00076 __glibcpp_function_requires(_LessThanComparableConcept<_Tp>);
00077 if (__a < __b)
00078 if (__b < __c)
00079 return __b;
00080 else if (__a < __c)
00081 return __c;
00082 else
00083 return __a;
00084 else if (__a < __c)
00085 return __a;
00086 else if (__b < __c)
00087 return __c;
00088 else
00089 return __b;
00090 }
00091
00092 template <class _Tp, class _Compare>
00093 inline const _Tp&
00094 __median(const _Tp& __a, const _Tp& __b, const _Tp& __c, _Compare __comp)
00095 {
00096
00097 __glibcpp_function_requires(_BinaryFunctionConcept<_Compare, bool, _Tp, _Tp>);
00098 if (__comp(__a, __b))
00099 if (__comp(__b, __c))
00100 return __b;
00101 else if (__comp(__a, __c))
00102 return __c;
00103 else
00104 return __a;
00105 else if (__comp(__a, __c))
00106 return __a;
00107 else if (__comp(__b, __c))
00108 return __c;
00109 else
00110 return __b;
00111 }
00112
00113
00114 template <class _InputIter, class _Function>
00115 _Function for_each(_InputIter __first, _InputIter __last, _Function __f)
00116 {
00117
00118 __glibcpp_function_requires(_InputIteratorConcept<_InputIter>);
00119 for ( ; __first != __last; ++__first)
00120 __f(*__first);
00121 return __f;
00122 }
00123
00124
00125
00126 template <class _InputIter, class _Tp>
00127 inline _InputIter find(_InputIter __first, _InputIter __last,
00128 const _Tp& __val,
00129 input_iterator_tag)
00130 {
00131 while (__first != __last && !(*__first == __val))
00132 ++__first;
00133 return __first;
00134 }
00135
00136 template <class _InputIter, class _Predicate>
00137 inline _InputIter find_if(_InputIter __first, _InputIter __last,
00138 _Predicate __pred,
00139 input_iterator_tag)
00140 {
00141 while (__first != __last && !__pred(*__first))
00142 ++__first;
00143 return __first;
00144 }
00145
00146 template <class _RandomAccessIter, class _Tp>
00147 _RandomAccessIter find(_RandomAccessIter __first, _RandomAccessIter __last,
00148 const _Tp& __val,
00149 random_access_iterator_tag)
00150 {
00151 typename iterator_traits<_RandomAccessIter>::difference_type __trip_count
00152 = (__last - __first) >> 2;
00153
00154 for ( ; __trip_count > 0 ; --__trip_count) {
00155 if (*__first == __val) return __first;
00156 ++__first;
00157
00158 if (*__first == __val) return __first;
00159 ++__first;
00160
00161 if (*__first == __val) return __first;
00162 ++__first;
00163
00164 if (*__first == __val) return __first;
00165 ++__first;
00166 }
00167
00168 switch(__last - __first) {
00169 case 3:
00170 if (*__first == __val) return __first;
00171 ++__first;
00172 case 2:
00173 if (*__first == __val) return __first;
00174 ++__first;
00175 case 1:
00176 if (*__first == __val) return __first;
00177 ++__first;
00178 case 0:
00179 default:
00180 return __last;
00181 }
00182 }
00183
00184 template <class _RandomAccessIter, class _Predicate>
00185 _RandomAccessIter find_if(_RandomAccessIter __first, _RandomAccessIter __last,
00186 _Predicate __pred,
00187 random_access_iterator_tag)
00188 {
00189 typename iterator_traits<_RandomAccessIter>::difference_type __trip_count
00190 = (__last - __first) >> 2;
00191
00192 for ( ; __trip_count > 0 ; --__trip_count) {
00193 if (__pred(*__first)) return __first;
00194 ++__first;
00195
00196 if (__pred(*__first)) return __first;
00197 ++__first;
00198
00199 if (__pred(*__first)) return __first;
00200 ++__first;
00201
00202 if (__pred(*__first)) return __first;
00203 ++__first;
00204 }
00205
00206 switch(__last - __first) {
00207 case 3:
00208 if (__pred(*__first)) return __first;
00209 ++__first;
00210 case 2:
00211 if (__pred(*__first)) return __first;
00212 ++__first;
00213 case 1:
00214 if (__pred(*__first)) return __first;
00215 ++__first;
00216 case 0:
00217 default:
00218 return __last;
00219 }
00220 }
00221
00222 template <class _InputIter, class _Tp>
00223 inline _InputIter find(_InputIter __first, _InputIter __last,
00224 const _Tp& __val)
00225 {
00226
00227 __glibcpp_function_requires(_InputIteratorConcept<_InputIter>);
00228 __glibcpp_function_requires(_EqualOpConcept<
00229 typename iterator_traits<_InputIter>::value_type, _Tp>);
00230 return find(__first, __last, __val, __iterator_category(__first));
00231 }
00232
00233 template <class _InputIter, class _Predicate>
00234 inline _InputIter find_if(_InputIter __first, _InputIter __last,
00235 _Predicate __pred)
00236 {
00237
00238 __glibcpp_function_requires(_InputIteratorConcept<_InputIter>);
00239 __glibcpp_function_requires(_UnaryPredicateConcept<_Predicate,
00240 typename iterator_traits<_InputIter>::value_type>);
00241 return find_if(__first, __last, __pred, __iterator_category(__first));
00242 }
00243
00244
00245
00246 template <class _ForwardIter>
00247 _ForwardIter adjacent_find(_ForwardIter __first, _ForwardIter __last)
00248 {
00249
00250 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>);
00251 __glibcpp_function_requires(_EqualityComparableConcept<
00252 typename iterator_traits<_ForwardIter>::value_type>);
00253 if (__first == __last)
00254 return __last;
00255 _ForwardIter __next = __first;
00256 while(++__next != __last) {
00257 if (*__first == *__next)
00258 return __first;
00259 __first = __next;
00260 }
00261 return __last;
00262 }
00263
00264 template <class _ForwardIter, class _BinaryPredicate>
00265 _ForwardIter adjacent_find(_ForwardIter __first, _ForwardIter __last,
00266 _BinaryPredicate __binary_pred)
00267 {
00268
00269 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>);
00270 __glibcpp_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
00271 typename iterator_traits<_ForwardIter>::value_type,
00272 typename iterator_traits<_ForwardIter>::value_type>);
00273 if (__first == __last)
00274 return __last;
00275 _ForwardIter __next = __first;
00276 while(++__next != __last) {
00277 if (__binary_pred(*__first, *__next))
00278 return __first;
00279 __first = __next;
00280 }
00281 return __last;
00282 }
00283
00284
00285
00286
00287
00288
00289
00290 template <class _InputIter, class _Tp, class _Size>
00291 void count(_InputIter __first, _InputIter __last, const _Tp& __value,
00292 _Size& __n)
00293 {
00294
00295 __glibcpp_function_requires(_InputIteratorConcept<_InputIter>);
00296 __glibcpp_function_requires(_EqualityComparableConcept<
00297 typename iterator_traits<_InputIter>::value_type >);
00298 __glibcpp_function_requires(_EqualityComparableConcept<_Tp>);
00299 for ( ; __first != __last; ++__first)
00300 if (*__first == __value)
00301 ++__n;
00302 }
00303
00304 template <class _InputIter, class _Predicate, class _Size>
00305 void count_if(_InputIter __first, _InputIter __last, _Predicate __pred,
00306 _Size& __n)
00307 {
00308
00309 __glibcpp_function_requires(_InputIteratorConcept<_InputIter>);
00310 __glibcpp_function_requires(_UnaryPredicateConcept<_Predicate,
00311 typename iterator_traits<_InputIter>::value_type>);
00312 for ( ; __first != __last; ++__first)
00313 if (__pred(*__first))
00314 ++__n;
00315 }
00316
00317 template <class _InputIter, class _Tp>
00318 typename iterator_traits<_InputIter>::difference_type
00319 count(_InputIter __first, _InputIter __last, const _Tp& __value)
00320 {
00321
00322 __glibcpp_function_requires(_InputIteratorConcept<_InputIter>);
00323 __glibcpp_function_requires(_EqualityComparableConcept<
00324 typename iterator_traits<_InputIter>::value_type >);
00325 __glibcpp_function_requires(_EqualityComparableConcept<_Tp>);
00326 typename iterator_traits<_InputIter>::difference_type __n = 0;
00327 for ( ; __first != __last; ++__first)
00328 if (*__first == __value)
00329 ++__n;
00330 return __n;
00331 }
00332
00333 template <class _InputIter, class _Predicate>
00334 typename iterator_traits<_InputIter>::difference_type
00335 count_if(_InputIter __first, _InputIter __last, _Predicate __pred)
00336 {
00337
00338 __glibcpp_function_requires(_InputIteratorConcept<_InputIter>);
00339 __glibcpp_function_requires(_UnaryPredicateConcept<_Predicate,
00340 typename iterator_traits<_InputIter>::value_type>);
00341 typename iterator_traits<_InputIter>::difference_type __n = 0;
00342 for ( ; __first != __last; ++__first)
00343 if (__pred(*__first))
00344 ++__n;
00345 return __n;
00346 }
00347
00348
00349
00350
00351 template <class _ForwardIter1, class _ForwardIter2>
00352 _ForwardIter1 search(_ForwardIter1 __first1, _ForwardIter1 __last1,
00353 _ForwardIter2 __first2, _ForwardIter2 __last2)
00354 {
00355
00356 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter1>);
00357 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter2>);
00358 __glibcpp_function_requires(_EqualOpConcept<
00359 typename iterator_traits<_ForwardIter1>::value_type,
00360 typename iterator_traits<_ForwardIter2>::value_type>);
00361
00362
00363 if (__first1 == __last1 || __first2 == __last2)
00364 return __first1;
00365
00366
00367 _ForwardIter2 __tmp(__first2);
00368 ++__tmp;
00369 if (__tmp == __last2)
00370 return find(__first1, __last1, *__first2);
00371
00372
00373
00374 _ForwardIter2 __p1, __p;
00375
00376 __p1 = __first2; ++__p1;
00377
00378 _ForwardIter1 __current = __first1;
00379
00380 while (__first1 != __last1) {
00381 __first1 = find(__first1, __last1, *__first2);
00382 if (__first1 == __last1)
00383 return __last1;
00384
00385 __p = __p1;
00386 __current = __first1;
00387 if (++__current == __last1)
00388 return __last1;
00389
00390 while (*__current == *__p) {
00391 if (++__p == __last2)
00392 return __first1;
00393 if (++__current == __last1)
00394 return __last1;
00395 }
00396
00397 ++__first1;
00398 }
00399 return __first1;
00400 }
00401
00402 template <class _ForwardIter1, class _ForwardIter2, class _BinaryPred>
00403 _ForwardIter1 search(_ForwardIter1 __first1, _ForwardIter1 __last1,
00404 _ForwardIter2 __first2, _ForwardIter2 __last2,
00405 _BinaryPred __predicate)
00406 {
00407
00408 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter1>);
00409 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter2>);
00410 __glibcpp_function_requires(_BinaryPredicateConcept<_BinaryPred,
00411 typename iterator_traits<_ForwardIter1>::value_type,
00412 typename iterator_traits<_ForwardIter2>::value_type>);
00413
00414
00415 if (__first1 == __last1 || __first2 == __last2)
00416 return __first1;
00417
00418
00419 _ForwardIter2 __tmp(__first2);
00420 ++__tmp;
00421 if (__tmp == __last2) {
00422 while (__first1 != __last1 && !__predicate(*__first1, *__first2))
00423 ++__first1;
00424 return __first1;
00425 }
00426
00427
00428
00429 _ForwardIter2 __p1, __p;
00430
00431 __p1 = __first2; ++__p1;
00432
00433 _ForwardIter1 __current = __first1;
00434
00435 while (__first1 != __last1) {
00436 while (__first1 != __last1) {
00437 if (__predicate(*__first1, *__first2))
00438 break;
00439 ++__first1;
00440 }
00441 while (__first1 != __last1 && !__predicate(*__first1, *__first2))
00442 ++__first1;
00443 if (__first1 == __last1)
00444 return __last1;
00445
00446 __p = __p1;
00447 __current = __first1;
00448 if (++__current == __last1) return __last1;
00449
00450 while (__predicate(*__current, *__p)) {
00451 if (++__p == __last2)
00452 return __first1;
00453 if (++__current == __last1)
00454 return __last1;
00455 }
00456
00457 ++__first1;
00458 }
00459 return __first1;
00460 }
00461
00462
00463
00464 template <class _ForwardIter, class _Integer, class _Tp>
00465 _ForwardIter search_n(_ForwardIter __first, _ForwardIter __last,
00466 _Integer __count, const _Tp& __val)
00467 {
00468
00469 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>);
00470 __glibcpp_function_requires(_EqualityComparableConcept<
00471 typename iterator_traits<_ForwardIter>::value_type>);
00472 __glibcpp_function_requires(_EqualityComparableConcept<_Tp>);
00473
00474 if (__count <= 0)
00475 return __first;
00476 else {
00477 __first = find(__first, __last, __val);
00478 while (__first != __last) {
00479 _Integer __n = __count - 1;
00480 _ForwardIter __i = __first;
00481 ++__i;
00482 while (__i != __last && __n != 0 && *__i == __val) {
00483 ++__i;
00484 --__n;
00485 }
00486 if (__n == 0)
00487 return __first;
00488 else
00489 __first = find(__i, __last, __val);
00490 }
00491 return __last;
00492 }
00493 }
00494
00495 template <class _ForwardIter, class _Integer, class _Tp, class _BinaryPred>
00496 _ForwardIter search_n(_ForwardIter __first, _ForwardIter __last,
00497 _Integer __count, const _Tp& __val,
00498 _BinaryPred __binary_pred)
00499 {
00500
00501 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>);
00502 __glibcpp_function_requires(_BinaryPredicateConcept<_BinaryPred,
00503 typename iterator_traits<_ForwardIter>::value_type, _Tp>);
00504
00505 if (__count <= 0)
00506 return __first;
00507 else {
00508 while (__first != __last) {
00509 if (__binary_pred(*__first, __val))
00510 break;
00511 ++__first;
00512 }
00513 while (__first != __last) {
00514 _Integer __n = __count - 1;
00515 _ForwardIter __i = __first;
00516 ++__i;
00517 while (__i != __last && __n != 0 && __binary_pred(*__i, __val)) {
00518 ++__i;
00519 --__n;
00520 }
00521 if (__n == 0)
00522 return __first;
00523 else {
00524 while (__i != __last) {
00525 if (__binary_pred(*__i, __val))
00526 break;
00527 ++__i;
00528 }
00529 __first = __i;
00530 }
00531 }
00532 return __last;
00533 }
00534 }
00535
00536
00537
00538 template <class _ForwardIter1, class _ForwardIter2>
00539 _ForwardIter2 swap_ranges(_ForwardIter1 __first1, _ForwardIter1 __last1,
00540 _ForwardIter2 __first2)
00541 {
00542
00543 __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter1>);
00544 __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter2>);
00545 __glibcpp_function_requires(_ConvertibleConcept<
00546 typename iterator_traits<_ForwardIter1>::value_type,
00547 typename iterator_traits<_ForwardIter2>::value_type>);
00548 __glibcpp_function_requires(_ConvertibleConcept<
00549 typename iterator_traits<_ForwardIter2>::value_type,
00550 typename iterator_traits<_ForwardIter1>::value_type>);
00551
00552 for ( ; __first1 != __last1; ++__first1, ++__first2)
00553 iter_swap(__first1, __first2);
00554 return __first2;
00555 }
00556
00557
00558
00559 template <class _InputIter, class _OutputIter, class _UnaryOperation>
00560 _OutputIter transform(_InputIter __first, _InputIter __last,
00561 _OutputIter __result, _UnaryOperation __unary_op)
00562 {
00563
00564 __glibcpp_function_requires(_InputIteratorConcept<_InputIter>);
00565
00566
00567
00568
00569
00570
00571 for ( ; __first != __last; ++__first, ++__result)
00572 *__result = __unary_op(*__first);
00573 return __result;
00574 }
00575
00576 template <class _InputIter1, class _InputIter2, class _OutputIter,
00577 class _BinaryOperation>
00578 _OutputIter transform(_InputIter1 __first1, _InputIter1 __last1,
00579 _InputIter2 __first2, _OutputIter __result,
00580 _BinaryOperation __binary_op)
00581 {
00582
00583 __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>);
00584 __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>);
00585
00586
00587
00588
00589
00590
00591 for ( ; __first1 != __last1; ++__first1, ++__first2, ++__result)
00592 *__result = __binary_op(*__first1, *__first2);
00593 return __result;
00594 }
00595
00596
00597
00598 template <class _ForwardIter, class _Tp>
00599 void replace(_ForwardIter __first, _ForwardIter __last,
00600 const _Tp& __old_value, const _Tp& __new_value)
00601 {
00602
00603 __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter>);
00604 __glibcpp_function_requires(_EqualOpConcept<
00605 typename iterator_traits<_ForwardIter>::value_type, _Tp>);
00606 __glibcpp_function_requires(_ConvertibleConcept<_Tp,
00607 typename iterator_traits<_ForwardIter>::value_type>);
00608
00609 for ( ; __first != __last; ++__first)
00610 if (*__first == __old_value)
00611 *__first = __new_value;
00612 }
00613
00614 template <class _ForwardIter, class _Predicate, class _Tp>
00615 void replace_if(_ForwardIter __first, _ForwardIter __last,
00616 _Predicate __pred, const _Tp& __new_value)
00617 {
00618
00619 __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter>);
00620 __glibcpp_function_requires(_ConvertibleConcept<_Tp,
00621 typename iterator_traits<_ForwardIter>::value_type>);
00622 __glibcpp_function_requires(_UnaryPredicateConcept<_Predicate,
00623 typename iterator_traits<_ForwardIter>::value_type>);
00624
00625 for ( ; __first != __last; ++__first)
00626 if (__pred(*__first))
00627 *__first = __new_value;
00628 }
00629
00630 template <class _InputIter, class _OutputIter, class _Tp>
00631 _OutputIter replace_copy(_InputIter __first, _InputIter __last,
00632 _OutputIter __result,
00633 const _Tp& __old_value, const _Tp& __new_value)
00634 {
00635
00636 __glibcpp_function_requires(_InputIteratorConcept<_InputIter>);
00637 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
00638 typename iterator_traits<_InputIter>::value_type>);
00639 __glibcpp_function_requires(_EqualOpConcept<
00640 typename iterator_traits<_InputIter>::value_type, _Tp>);
00641
00642 for ( ; __first != __last; ++__first, ++__result)
00643 *__result = *__first == __old_value ? __new_value : *__first;
00644 return __result;
00645 }
00646
00647 template <class _InputIter, class _OutputIter, class _Predicate, class _Tp>
00648 _OutputIter replace_copy_if(_InputIter __first, _InputIter __last,
00649 _OutputIter __result,
00650 _Predicate __pred, const _Tp& __new_value)
00651 {
00652
00653 __glibcpp_function_requires(_InputIteratorConcept<_InputIter>);
00654 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
00655 typename iterator_traits<_InputIter>::value_type>);
00656 __glibcpp_function_requires(_UnaryPredicateConcept<_Predicate,
00657 typename iterator_traits<_InputIter>::value_type>);
00658
00659 for ( ; __first != __last; ++__first, ++__result)
00660 *__result = __pred(*__first) ? __new_value : *__first;
00661 return __result;
00662 }
00663
00664
00665
00666 template <class _ForwardIter, class _Generator>
00667 void generate(_ForwardIter __first, _ForwardIter __last, _Generator __gen)
00668 {
00669
00670 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>);
00671 __glibcpp_function_requires(_GeneratorConcept<_Generator,
00672 typename iterator_traits<_ForwardIter>::value_type>);
00673
00674 for ( ; __first != __last; ++__first)
00675 *__first = __gen();
00676 }
00677
00678 template <class _OutputIter, class _Size, class _Generator>
00679 _OutputIter generate_n(_OutputIter __first, _Size __n, _Generator __gen)
00680 {
00681
00682
00683
00684
00685
00686
00687 for ( ; __n > 0; --__n, ++__first)
00688 *__first = __gen();
00689 return __first;
00690 }
00691
00692
00693
00694 template <class _InputIter, class _OutputIter, class _Tp>
00695 _OutputIter remove_copy(_InputIter __first, _InputIter __last,
00696 _OutputIter __result, const _Tp& __value)
00697 {
00698
00699 __glibcpp_function_requires(_InputIteratorConcept<_InputIter>);
00700 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
00701 typename iterator_traits<_InputIter>::value_type>);
00702 __glibcpp_function_requires(_EqualOpConcept<
00703 typename iterator_traits<_InputIter>::value_type, _Tp>);
00704
00705 for ( ; __first != __last; ++__first)
00706 if (!(*__first == __value)) {
00707 *__result = *__first;
00708 ++__result;
00709 }
00710 return __result;
00711 }
00712
00713 template <class _InputIter, class _OutputIter, class _Predicate>
00714 _OutputIter remove_copy_if(_InputIter __first, _InputIter __last,
00715 _OutputIter __result, _Predicate __pred)
00716 {
00717
00718 __glibcpp_function_requires(_InputIteratorConcept<_InputIter>);
00719 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
00720 typename iterator_traits<_InputIter>::value_type>);
00721 __glibcpp_function_requires(_UnaryPredicateConcept<_Predicate,
00722 typename iterator_traits<_InputIter>::value_type>);
00723
00724 for ( ; __first != __last; ++__first)
00725 if (!__pred(*__first)) {
00726 *__result = *__first;
00727 ++__result;
00728 }
00729 return __result;
00730 }
00731
00732 template <class _ForwardIter, class _Tp>
00733 _ForwardIter remove(_ForwardIter __first, _ForwardIter __last,
00734 const _Tp& __value)
00735 {
00736
00737 __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter>);
00738 __glibcpp_function_requires(_ConvertibleConcept<_Tp,
00739 typename iterator_traits<_ForwardIter>::value_type>);
00740 __glibcpp_function_requires(_EqualOpConcept<
00741 typename iterator_traits<_ForwardIter>::value_type, _Tp>);
00742
00743 __first = find(__first, __last, __value);
00744 _ForwardIter __i = __first;
00745 return __first == __last ? __first
00746 : remove_copy(++__i, __last, __first, __value);
00747 }
00748
00749 template <class _ForwardIter, class _Predicate>
00750 _ForwardIter remove_if(_ForwardIter __first, _ForwardIter __last,
00751 _Predicate __pred)
00752 {
00753
00754 __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter>);
00755 __glibcpp_function_requires(_UnaryPredicateConcept<_Predicate,
00756 typename iterator_traits<_ForwardIter>::value_type>);
00757
00758 __first = find_if(__first, __last, __pred);
00759 _ForwardIter __i = __first;
00760 return __first == __last ? __first
00761 : remove_copy_if(++__i, __last, __first, __pred);
00762 }
00763
00764
00765
00766 template <class _InputIter, class _OutputIter, class _Tp>
00767 _OutputIter __unique_copy(_InputIter __first, _InputIter __last,
00768 _OutputIter __result, _Tp*)
00769 {
00770
00771 _Tp __value = *__first;
00772 *__result = __value;
00773 while (++__first != __last)
00774 if (!(__value == *__first)) {
00775 __value = *__first;
00776 *++__result = __value;
00777 }
00778 return ++__result;
00779 }
00780
00781 template <class _InputIter, class _OutputIter>
00782 inline _OutputIter __unique_copy(_InputIter __first, _InputIter __last,
00783 _OutputIter __result,
00784 output_iterator_tag)
00785 {
00786
00787 return __unique_copy(__first, __last, __result, __value_type(__first));
00788 }
00789
00790 template <class _InputIter, class _ForwardIter>
00791 _ForwardIter __unique_copy(_InputIter __first, _InputIter __last,
00792 _ForwardIter __result, forward_iterator_tag)
00793 {
00794
00795 *__result = *__first;
00796 while (++__first != __last)
00797 if (!(*__result == *__first))
00798 *++__result = *__first;
00799 return ++__result;
00800 }
00801
00802 template <class _InputIter, class _OutputIter>
00803 inline _OutputIter unique_copy(_InputIter __first, _InputIter __last,
00804 _OutputIter __result)
00805 {
00806
00807 __glibcpp_function_requires(_InputIteratorConcept<_InputIter>);
00808 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
00809 typename iterator_traits<_InputIter>::value_type>);
00810 __glibcpp_function_requires(_EqualityComparableConcept<
00811 typename iterator_traits<_InputIter>::value_type>);
00812
00813 if (__first == __last) return __result;
00814 return __unique_copy(__first, __last, __result,
00815 __iterator_category(__result));
00816 }
00817
00818 template <class _InputIter, class _OutputIter, class _BinaryPredicate,
00819 class _Tp>
00820 _OutputIter __unique_copy(_InputIter __first, _InputIter __last,
00821 _OutputIter __result,
00822 _BinaryPredicate __binary_pred, _Tp*)
00823 {
00824
00825 __glibcpp_function_requires(_BinaryPredicateConcept<_BinaryPredicate, _Tp, _Tp>);
00826
00827 _Tp __value = *__first;
00828 *__result = __value;
00829 while (++__first != __last)
00830 if (!__binary_pred(__value, *__first)) {
00831 __value = *__first;
00832 *++__result = __value;
00833 }
00834 return ++__result;
00835 }
00836
00837 template <class _InputIter, class _OutputIter, class _BinaryPredicate>
00838 inline _OutputIter __unique_copy(_InputIter __first, _InputIter __last,
00839 _OutputIter __result,
00840 _BinaryPredicate __binary_pred,
00841 output_iterator_tag)
00842 {
00843
00844 return __unique_copy(__first, __last, __result, __binary_pred,
00845 __value_type(__first));
00846 }
00847
00848 template <class _InputIter, class _ForwardIter, class _BinaryPredicate>
00849 _ForwardIter __unique_copy(_InputIter __first, _InputIter __last,
00850 _ForwardIter __result,
00851 _BinaryPredicate __binary_pred,
00852 forward_iterator_tag)
00853 {
00854
00855 __glibcpp_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
00856 typename iterator_traits<_ForwardIter>::value_type,
00857 typename iterator_traits<_InputIter>::value_type>);
00858
00859 *__result = *__first;
00860 while (++__first != __last)
00861 if (!__binary_pred(*__result, *__first)) *++__result = *__first;
00862 return ++__result;
00863 }
00864
00865 template <class _InputIter, class _OutputIter, class _BinaryPredicate>
00866 inline _OutputIter unique_copy(_InputIter __first, _InputIter __last,
00867 _OutputIter __result,
00868 _BinaryPredicate __binary_pred)
00869 {
00870
00871 __glibcpp_function_requires(_InputIteratorConcept<_InputIter>);
00872 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
00873 typename iterator_traits<_InputIter>::value_type>);
00874
00875 if (__first == __last) return __result;
00876 return __unique_copy(__first, __last, __result, __binary_pred,
00877 __iterator_category(__result));
00878 }
00879
00880 template <class _ForwardIter>
00881 _ForwardIter unique(_ForwardIter __first, _ForwardIter __last)
00882 {
00883
00884 __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter>);
00885 __glibcpp_function_requires(_EqualityComparableConcept<
00886 typename iterator_traits<_ForwardIter>::value_type>);
00887
00888 __first = adjacent_find(__first, __last);
00889 return unique_copy(__first, __last, __first);
00890 }
00891
00892 template <class _ForwardIter, class _BinaryPredicate>
00893 _ForwardIter unique(_ForwardIter __first, _ForwardIter __last,
00894 _BinaryPredicate __binary_pred)
00895 {
00896
00897 __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter>);
00898 __glibcpp_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
00899 typename iterator_traits<_ForwardIter>::value_type,
00900 typename iterator_traits<_ForwardIter>::value_type>);
00901
00902 __first = adjacent_find(__first, __last, __binary_pred);
00903 return unique_copy(__first, __last, __first, __binary_pred);
00904 }
00905
00906
00907
00908 template <class _BidirectionalIter>
00909 void __reverse(_BidirectionalIter __first, _BidirectionalIter __last,
00910 bidirectional_iterator_tag) {
00911 while (true)
00912 if (__first == __last || __first == --__last)
00913 return;
00914 else
00915 iter_swap(__first++, __last);
00916 }
00917
00918 template <class _RandomAccessIter>
00919 void __reverse(_RandomAccessIter __first, _RandomAccessIter __last,
00920 random_access_iterator_tag) {
00921 while (__first < __last)
00922 iter_swap(__first++, --__last);
00923 }
00924
00925 template <class _BidirectionalIter>
00926 inline void reverse(_BidirectionalIter __first, _BidirectionalIter __last)
00927 {
00928
00929 __glibcpp_function_requires(_Mutable_BidirectionalIteratorConcept<
00930 _BidirectionalIter>);
00931 __reverse(__first, __last, __iterator_category(__first));
00932 }
00933
00934 template <class _BidirectionalIter, class _OutputIter>
00935 _OutputIter reverse_copy(_BidirectionalIter __first,
00936 _BidirectionalIter __last,
00937 _OutputIter __result)
00938 {
00939
00940 __glibcpp_function_requires(_BidirectionalIteratorConcept<_BidirectionalIter>);
00941 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
00942 typename iterator_traits<_BidirectionalIter>::value_type>);
00943
00944 while (__first != __last) {
00945 --__last;
00946 *__result = *__last;
00947 ++__result;
00948 }
00949 return __result;
00950 }
00951
00952
00953
00954 template <class _EuclideanRingElement>
00955 _EuclideanRingElement __gcd(_EuclideanRingElement __m,
00956 _EuclideanRingElement __n)
00957 {
00958 while (__n != 0) {
00959 _EuclideanRingElement __t = __m % __n;
00960 __m = __n;
00961 __n = __t;
00962 }
00963 return __m;
00964 }
00965
00966 template <class _ForwardIter, class _Distance>
00967 _ForwardIter __rotate(_ForwardIter __first,
00968 _ForwardIter __middle,
00969 _ForwardIter __last,
00970 _Distance*,
00971 forward_iterator_tag)
00972 {
00973 if (__first == __middle)
00974 return __last;
00975 if (__last == __middle)
00976 return __first;
00977
00978 _ForwardIter __first2 = __middle;
00979 do {
00980 swap(*__first++, *__first2++);
00981 if (__first == __middle)
00982 __middle = __first2;
00983 } while (__first2 != __last);
00984
00985 _ForwardIter __new_middle = __first;
00986
00987 __first2 = __middle;
00988
00989 while (__first2 != __last) {
00990 swap (*__first++, *__first2++);
00991 if (__first == __middle)
00992 __middle = __first2;
00993 else if (__first2 == __last)
00994 __first2 = __middle;
00995 }
00996
00997 return __new_middle;
00998 }
00999
01000
01001 template <class _BidirectionalIter, class _Distance>
01002 _BidirectionalIter __rotate(_BidirectionalIter __first,
01003 _BidirectionalIter __middle,
01004 _BidirectionalIter __last,
01005 _Distance*,
01006 bidirectional_iterator_tag)
01007 {
01008
01009 __glibcpp_function_requires(_Mutable_BidirectionalIteratorConcept<
01010 _BidirectionalIter>);
01011
01012 if (__first == __middle)
01013 return __last;
01014 if (__last == __middle)
01015 return __first;
01016
01017 __reverse(__first, __middle, bidirectional_iterator_tag());
01018 __reverse(__middle, __last, bidirectional_iterator_tag());
01019
01020 while (__first != __middle && __middle != __last)
01021 swap (*__first++, *--__last);
01022
01023 if (__first == __middle) {
01024 __reverse(__middle, __last, bidirectional_iterator_tag());
01025 return __last;
01026 }
01027 else {
01028 __reverse(__first, __middle, bidirectional_iterator_tag());
01029 return __first;
01030 }
01031 }
01032
01033 template <class _RandomAccessIter, class _Distance, class _Tp>
01034 _RandomAccessIter __rotate(_RandomAccessIter __first,
01035 _RandomAccessIter __middle,
01036 _RandomAccessIter __last,
01037 _Distance *, _Tp *)
01038 {
01039
01040 __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
01041 _RandomAccessIter>);
01042
01043 _Distance __n = __last - __first;
01044 _Distance __k = __middle - __first;
01045 _Distance __l = __n - __k;
01046 _RandomAccessIter __result = __first + (__last - __middle);
01047
01048 if (__k == 0)
01049 return __last;
01050
01051 else if (__k == __l) {
01052 swap_ranges(__first, __middle, __middle);
01053 return __result;
01054 }
01055
01056 _Distance __d = __gcd(__n, __k);
01057
01058 for (_Distance __i = 0; __i < __d; __i++) {
01059 _Tp __tmp = *__first;
01060 _RandomAccessIter __p = __first;
01061
01062 if (__k < __l) {
01063 for (_Distance __j = 0; __j < __l/__d; __j++) {
01064 if (__p > __first + __l) {
01065 *__p = *(__p - __l);
01066 __p -= __l;
01067 }
01068
01069 *__p = *(__p + __k);
01070 __p += __k;
01071 }
01072 }
01073
01074 else {
01075 for (_Distance __j = 0; __j < __k/__d - 1; __j ++) {
01076 if (__p < __last - __k) {
01077 *__p = *(__p + __k);
01078 __p += __k;
01079 }
01080
01081 *__p = * (__p - __l);
01082 __p -= __l;
01083 }
01084 }
01085
01086 *__p = __tmp;
01087 ++__first;
01088 }
01089
01090 return __result;
01091 }
01092
01093 template <class _ForwardIter>
01094 inline _ForwardIter rotate(_ForwardIter __first, _ForwardIter __middle,
01095 _ForwardIter __last)
01096 {
01097
01098 __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter>);
01099
01100 return __rotate(__first, __middle, __last,
01101 __distance_type(__first),
01102 __iterator_category(__first));
01103 }
01104
01105 template <class _ForwardIter, class _OutputIter>
01106 _OutputIter rotate_copy(_ForwardIter __first, _ForwardIter __middle,
01107 _ForwardIter __last, _OutputIter __result)
01108 {
01109
01110 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>);
01111 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
01112 typename iterator_traits<_ForwardIter>::value_type>);
01113
01114 return copy(__first, __middle, copy(__middle, __last, __result));
01115 }
01116
01117
01118
01119
01120 template <class _Distance>
01121 inline _Distance __random_number(_Distance __n) {
01122 #ifdef _GLIBCPP_HAVE_DRAND48
01123 return lrand48() % __n;
01124 #else
01125 return rand() % __n;
01126 #endif
01127 }
01128
01129
01130
01131 template <class _RandomAccessIter>
01132 inline void random_shuffle(_RandomAccessIter __first,
01133 _RandomAccessIter __last)
01134 {
01135
01136 __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
01137 _RandomAccessIter>);
01138
01139 if (__first == __last) return;
01140 for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i)
01141 iter_swap(__i, __first + __random_number((__i - __first) + 1));
01142 }
01143
01144 template <class _RandomAccessIter, class _RandomNumberGenerator>
01145 void random_shuffle(_RandomAccessIter __first, _RandomAccessIter __last,
01146 _RandomNumberGenerator& __rand)
01147 {
01148
01149 __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
01150 _RandomAccessIter>);
01151
01152 if (__first == __last) return;
01153 for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i)
01154 iter_swap(__i, __first + __rand((__i - __first) + 1));
01155 }
01156
01157
01158
01159 template <class _ForwardIter, class _OutputIter, class _Distance>
01160 _OutputIter random_sample_n(_ForwardIter __first, _ForwardIter __last,
01161 _OutputIter __out, const _Distance __n)
01162 {
01163
01164 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>);
01165 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
01166 typename iterator_traits<_ForwardIter>::value_type>);
01167
01168 _Distance __remaining = 0;
01169 distance(__first, __last, __remaining);
01170 _Distance __m = min(__n, __remaining);
01171
01172 while (__m > 0) {
01173 if (__random_number(__remaining) < __m) {
01174 *__out = *__first;
01175 ++__out;
01176 --__m;
01177 }
01178
01179 --__remaining;
01180 ++__first;
01181 }
01182 return __out;
01183 }
01184
01185 template <class _ForwardIter, class _OutputIter, class _Distance,
01186 class _RandomNumberGenerator>
01187 _OutputIter random_sample_n(_ForwardIter __first, _ForwardIter __last,
01188 _OutputIter __out, const _Distance __n,
01189 _RandomNumberGenerator& __rand)
01190 {
01191
01192 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>);
01193 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
01194 typename iterator_traits<_ForwardIter>::value_type>);
01195 __glibcpp_function_requires(_UnaryFunctionConcept<
01196 _RandomNumberGenerator, _Distance, _Distance>);
01197
01198 _Distance __remaining = 0;
01199 distance(__first, __last, __remaining);
01200 _Distance __m = min(__n, __remaining);
01201
01202 while (__m > 0) {
01203 if (__rand(__remaining) < __m) {
01204 *__out = *__first;
01205 ++__out;
01206 --__m;
01207 }
01208
01209 --__remaining;
01210 ++__first;
01211 }
01212 return __out;
01213 }
01214
01215 template <class _InputIter, class _RandomAccessIter, class _Distance>
01216 _RandomAccessIter __random_sample(_InputIter __first, _InputIter __last,
01217 _RandomAccessIter __out,
01218 const _Distance __n)
01219 {
01220 _Distance __m = 0;
01221 _Distance __t = __n;
01222 for ( ; __first != __last && __m < __n; ++__m, ++__first)
01223 __out[__m] = *__first;
01224
01225 while (__first != __last) {
01226 ++__t;
01227 _Distance __M = __random_number(__t);
01228 if (__M < __n)
01229 __out[__M] = *__first;
01230 ++__first;
01231 }
01232
01233 return __out + __m;
01234 }
01235
01236 template <class _InputIter, class _RandomAccessIter,
01237 class _RandomNumberGenerator, class _Distance>
01238 _RandomAccessIter __random_sample(_InputIter __first, _InputIter __last,
01239 _RandomAccessIter __out,
01240 _RandomNumberGenerator& __rand,
01241 const _Distance __n)
01242 {
01243
01244 __glibcpp_function_requires(_UnaryFunctionConcept<
01245 _RandomNumberGenerator, _Distance, _Distance>);
01246
01247 _Distance __m = 0;
01248 _Distance __t = __n;
01249 for ( ; __first != __last && __m < __n; ++__m, ++__first)
01250 __out[__m] = *__first;
01251
01252 while (__first != __last) {
01253 ++__t;
01254 _Distance __M = __rand(__t);
01255 if (__M < __n)
01256 __out[__M] = *__first;
01257 ++__first;
01258 }
01259
01260 return __out + __m;
01261 }
01262
01263 template <class _InputIter, class _RandomAccessIter>
01264 inline _RandomAccessIter
01265 random_sample(_InputIter __first, _InputIter __last,
01266 _RandomAccessIter __out_first, _RandomAccessIter __out_last)
01267 {
01268
01269 __glibcpp_function_requires(_InputIteratorConcept<_InputIter>);
01270 __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
01271 _RandomAccessIter>);
01272
01273 return __random_sample(__first, __last,
01274 __out_first, __out_last - __out_first);
01275 }
01276
01277
01278 template <class _InputIter, class _RandomAccessIter,
01279 class _RandomNumberGenerator>
01280 inline _RandomAccessIter
01281 random_sample(_InputIter __first, _InputIter __last,
01282 _RandomAccessIter __out_first, _RandomAccessIter __out_last,
01283 _RandomNumberGenerator& __rand)
01284 {
01285
01286 __glibcpp_function_requires(_InputIteratorConcept<_InputIter>);
01287 __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
01288 _RandomAccessIter>);
01289
01290 return __random_sample(__first, __last,
01291 __out_first, __rand,
01292 __out_last - __out_first);
01293 }
01294
01295
01296
01297 template <class _ForwardIter, class _Predicate>
01298 _ForwardIter __partition(_ForwardIter __first,
01299 _ForwardIter __last,
01300 _Predicate __pred,
01301 forward_iterator_tag)
01302 {
01303 if (__first == __last) return __first;
01304
01305 while (__pred(*__first))
01306 if (++__first == __last) return __first;
01307
01308 _ForwardIter __next = __first;
01309
01310 while (++__next != __last)
01311 if (__pred(*__next)) {
01312 swap(*__first, *__next);
01313 ++__first;
01314 }
01315
01316 return __first;
01317 }
01318
01319 template <class _BidirectionalIter, class _Predicate>
01320 _BidirectionalIter __partition(_BidirectionalIter __first,
01321 _BidirectionalIter __last,
01322 _Predicate __pred,
01323 bidirectional_iterator_tag)
01324 {
01325 while (true) {
01326 while (true)
01327 if (__first == __last)
01328 return __first;
01329 else if (__pred(*__first))
01330 ++__first;
01331 else
01332 break;
01333 --__last;
01334 while (true)
01335 if (__first == __last)
01336 return __first;
01337 else if (!__pred(*__last))
01338 --__last;
01339 else
01340 break;
01341 iter_swap(__first, __last);
01342 ++__first;
01343 }
01344 }
01345
01346 template <class _ForwardIter, class _Predicate>
01347 inline _ForwardIter partition(_ForwardIter __first,
01348 _ForwardIter __last,
01349 _Predicate __pred)
01350 {
01351
01352 __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter>);
01353 __glibcpp_function_requires(_UnaryPredicateConcept<_Predicate,
01354 typename iterator_traits<_ForwardIter>::value_type>);
01355
01356 return __partition(__first, __last, __pred, __iterator_category(__first));
01357 }
01358
01359
01360 template <class _ForwardIter, class _Predicate, class _Distance>
01361 _ForwardIter __inplace_stable_partition(_ForwardIter __first,
01362 _ForwardIter __last,
01363 _Predicate __pred, _Distance __len)
01364 {
01365 if (__len == 1)
01366 return __pred(*__first) ? __last : __first;
01367 _ForwardIter __middle = __first;
01368 advance(__middle, __len / 2);
01369 return rotate(__inplace_stable_partition(__first, __middle, __pred,
01370 __len / 2),
01371 __middle,
01372 __inplace_stable_partition(__middle, __last, __pred,
01373 __len - __len / 2));
01374 }
01375
01376 template <class _ForwardIter, class _Pointer, class _Predicate,
01377 class _Distance>
01378 _ForwardIter __stable_partition_adaptive(_ForwardIter __first,
01379 _ForwardIter __last,
01380 _Predicate __pred, _Distance __len,
01381 _Pointer __buffer,
01382 _Distance __buffer_size)
01383 {
01384 if (__len <= __buffer_size) {
01385 _ForwardIter __result1 = __first;
01386 _Pointer __result2 = __buffer;
01387 for ( ; __first != __last ; ++__first)
01388 if (__pred(*__first)) {
01389 *__result1 = *__first;
01390 ++__result1;
01391 }
01392 else {
01393 *__result2 = *__first;
01394 ++__result2;
01395 }
01396 copy(__buffer, __result2, __result1);
01397 return __result1;
01398 }
01399 else {
01400 _ForwardIter __middle = __first;
01401 advance(__middle, __len / 2);
01402 return rotate(__stable_partition_adaptive(
01403 __first, __middle, __pred,
01404 __len / 2, __buffer, __buffer_size),
01405 __middle,
01406 __stable_partition_adaptive(
01407 __middle, __last, __pred,
01408 __len - __len / 2, __buffer, __buffer_size));
01409 }
01410 }
01411
01412 template <class _ForwardIter, class _Predicate, class _Tp, class _Distance>
01413 inline _ForwardIter
01414 __stable_partition_aux(_ForwardIter __first, _ForwardIter __last,
01415 _Predicate __pred, _Tp*, _Distance*)
01416 {
01417 _Temporary_buffer<_ForwardIter, _Tp> __buf(__first, __last);
01418 if (__buf.size() > 0)
01419 return __stable_partition_adaptive(__first, __last, __pred,
01420 _Distance(__buf.requested_size()),
01421 __buf.begin(), __buf.size());
01422 else
01423 return __inplace_stable_partition(__first, __last, __pred,
01424 _Distance(__buf.requested_size()));
01425 }
01426
01427 template <class _ForwardIter, class _Predicate>
01428 inline _ForwardIter stable_partition(_ForwardIter __first,
01429 _ForwardIter __last,
01430 _Predicate __pred)
01431 {
01432
01433 __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter>);
01434 __glibcpp_function_requires(_UnaryPredicateConcept<_Predicate,
01435 typename iterator_traits<_ForwardIter>::value_type>);
01436
01437 if (__first == __last)
01438 return __first;
01439 else
01440 return __stable_partition_aux(__first, __last, __pred,
01441 __value_type(__first),
01442 __distance_type(__first));
01443 }
01444
01445 template <class _RandomAccessIter, class _Tp>
01446 _RandomAccessIter __unguarded_partition(_RandomAccessIter __first,
01447 _RandomAccessIter __last,
01448 _Tp __pivot)
01449 {
01450 while (true) {
01451 while (*__first < __pivot)
01452 ++__first;
01453 --__last;
01454 while (__pivot < *__last)
01455 --__last;
01456 if (!(__first < __last))
01457 return __first;
01458 iter_swap(__first, __last);
01459 ++__first;
01460 }
01461 }
01462
01463 template <class _RandomAccessIter, class _Tp, class _Compare>
01464 _RandomAccessIter __unguarded_partition(_RandomAccessIter __first,
01465 _RandomAccessIter __last,
01466 _Tp __pivot, _Compare __comp)
01467 {
01468 while (true) {
01469 while (__comp(*__first, __pivot))
01470 ++__first;
01471 --__last;
01472 while (__comp(__pivot, *__last))
01473 --__last;
01474 if (!(__first < __last))
01475 return __first;
01476 iter_swap(__first, __last);
01477 ++__first;
01478 }
01479 }
01480
01481 const int __stl_threshold = 16;
01482
01483
01484
01485 template <class _RandomAccessIter, class _Tp>
01486 void __unguarded_linear_insert(_RandomAccessIter __last, _Tp __val)
01487 {
01488 _RandomAccessIter __next = __last;
01489 --__next;
01490 while (__val < *__next) {
01491 *__last = *__next;
01492 __last = __next;
01493 --__next;
01494 }
01495 *__last = __val;
01496 }
01497
01498 template <class _RandomAccessIter, class _Tp, class _Compare>
01499 void __unguarded_linear_insert(_RandomAccessIter __last, _Tp __val,
01500 _Compare __comp)
01501 {
01502 _RandomAccessIter __next = __last;
01503 --__next;
01504 while (__comp(__val, *__next)) {
01505 *__last = *__next;
01506 __last = __next;
01507 --__next;
01508 }
01509 *__last = __val;
01510 }
01511
01512 template <class _RandomAccessIter, class _Tp>
01513 inline void __linear_insert(_RandomAccessIter __first,
01514 _RandomAccessIter __last, _Tp*)
01515 {
01516 _Tp __val = *__last;
01517 if (__val < *__first) {
01518 copy_backward(__first, __last, __last + 1);
01519 *__first = __val;
01520 }
01521 else
01522 __unguarded_linear_insert(__last, __val);
01523 }
01524
01525 template <class _RandomAccessIter, class _Tp, class _Compare>
01526 inline void __linear_insert(_RandomAccessIter __first,
01527 _RandomAccessIter __last, _Tp*, _Compare __comp)
01528 {
01529 _Tp __val = *__last;
01530 if (__comp(__val, *__first)) {
01531 copy_backward(__first, __last, __last + 1);
01532 *__first = __val;
01533 }
01534 else
01535 __unguarded_linear_insert(__last, __val, __comp);
01536 }
01537
01538 template <class _RandomAccessIter>
01539 void __insertion_sort(_RandomAccessIter __first, _RandomAccessIter __last)
01540 {
01541 if (__first == __last) return;
01542 for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i)
01543 __linear_insert(__first, __i, __value_type(__first));
01544 }
01545
01546 template <class _RandomAccessIter, class _Compare>
01547 void __insertion_sort(_RandomAccessIter __first,
01548 _RandomAccessIter __last, _Compare __comp)
01549 {
01550 if (__first == __last) return;
01551 for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i)
01552 __linear_insert(__first, __i, __value_type(__first), __comp);
01553 }
01554
01555 template <class _RandomAccessIter, class _Tp>
01556 void __unguarded_insertion_sort_aux(_RandomAccessIter __first,
01557 _RandomAccessIter __last, _Tp*)
01558 {
01559 for (_RandomAccessIter __i = __first; __i != __last; ++__i)
01560 __unguarded_linear_insert(__i, _Tp(*__i));
01561 }
01562
01563 template <class _RandomAccessIter>
01564 inline void __unguarded_insertion_sort(_RandomAccessIter __first,
01565 _RandomAccessIter __last) {
01566 __unguarded_insertion_sort_aux(__first, __last, __value_type(__first));
01567 }
01568
01569 template <class _RandomAccessIter, class _Tp, class _Compare>
01570 void __unguarded_insertion_sort_aux(_RandomAccessIter __first,
01571 _RandomAccessIter __last,
01572 _Tp*, _Compare __comp)
01573 {
01574 for (_RandomAccessIter __i = __first; __i != __last; ++__i)
01575 __unguarded_linear_insert(__i, _Tp(*__i), __comp);
01576 }
01577
01578 template <class _RandomAccessIter, class _Compare>
01579 inline void __unguarded_insertion_sort(_RandomAccessIter __first,
01580 _RandomAccessIter __last,
01581 _Compare __comp)
01582 {
01583 __unguarded_insertion_sort_aux(__first, __last, __value_type(__first),
01584 __comp);
01585 }
01586
01587 template <class _RandomAccessIter>
01588 void __final_insertion_sort(_RandomAccessIter __first,
01589 _RandomAccessIter __last)
01590 {
01591 if (__last - __first > __stl_threshold) {
01592 __insertion_sort(__first, __first + __stl_threshold);
01593 __unguarded_insertion_sort(__first + __stl_threshold, __last);
01594 }
01595 else
01596 __insertion_sort(__first, __last);
01597 }
01598
01599 template <class _RandomAccessIter, class _Compare>
01600 void __final_insertion_sort(_RandomAccessIter __first,
01601 _RandomAccessIter __last, _Compare __comp)
01602 {
01603 if (__last - __first > __stl_threshold) {
01604 __insertion_sort(__first, __first + __stl_threshold, __comp);
01605 __unguarded_insertion_sort(__first + __stl_threshold, __last, __comp);
01606 }
01607 else
01608 __insertion_sort(__first, __last, __comp);
01609 }
01610
01611 template <class _Size>
01612 inline _Size __lg(_Size __n)
01613 {
01614 _Size __k;
01615 for (__k = 0; __n != 1; __n >>= 1) ++__k;
01616 return __k;
01617 }
01618
01619 template <class _RandomAccessIter, class _Tp, class _Size>
01620 void __introsort_loop(_RandomAccessIter __first,
01621 _RandomAccessIter __last, _Tp*,
01622 _Size __depth_limit)
01623 {
01624 while (__last - __first > __stl_threshold) {
01625 if (__depth_limit == 0) {
01626 partial_sort(__first, __last, __last);
01627 return;
01628 }
01629 --__depth_limit;
01630 _RandomAccessIter __cut =
01631 __unguarded_partition(__first, __last,
01632 _Tp(__median(*__first,
01633 *(__first + (__last - __first)/2),
01634 *(__last - 1))));
01635 __introsort_loop(__cut, __last, (_Tp*) 0, __depth_limit);
01636 __last = __cut;
01637 }
01638 }
01639
01640 template <class _RandomAccessIter, class _Tp, class _Size, class _Compare>
01641 void __introsort_loop(_RandomAccessIter __first,
01642 _RandomAccessIter __last, _Tp*,
01643 _Size __depth_limit, _Compare __comp)
01644 {
01645 while (__last - __first > __stl_threshold) {
01646 if (__depth_limit == 0) {
01647 partial_sort(__first, __last, __last, __comp);
01648 return;
01649 }
01650 --__depth_limit;
01651 _RandomAccessIter __cut =
01652 __unguarded_partition(__first, __last,
01653 _Tp(__median(*__first,
01654 *(__first + (__last - __first)/2),
01655 *(__last - 1), __comp)),
01656 __comp);
01657 __introsort_loop(__cut, __last, (_Tp*) 0, __depth_limit, __comp);
01658 __last = __cut;
01659 }
01660 }
01661
01662 template <class _RandomAccessIter>
01663 inline void sort(_RandomAccessIter __first, _RandomAccessIter __last)
01664 {
01665
01666 __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
01667 _RandomAccessIter>);
01668 __glibcpp_function_requires(_LessThanComparableConcept<
01669 typename iterator_traits<_RandomAccessIter>::value_type>);
01670
01671 if (__first != __last) {
01672 __introsort_loop(__first, __last,
01673 __value_type(__first),
01674 __lg(__last - __first) * 2);
01675 __final_insertion_sort(__first, __last);
01676 }
01677 }
01678
01679 template <class _RandomAccessIter, class _Compare>
01680 inline void sort(_RandomAccessIter __first, _RandomAccessIter __last,
01681 _Compare __comp)
01682 {
01683
01684 __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
01685 _RandomAccessIter>);
01686 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare,
01687 typename iterator_traits<_RandomAccessIter>::value_type,
01688 typename iterator_traits<_RandomAccessIter>::value_type>);
01689
01690 if (__first != __last) {
01691 __introsort_loop(__first, __last,
01692 __value_type(__first),
01693 __lg(__last - __first) * 2,
01694 __comp);
01695 __final_insertion_sort(__first, __last, __comp);
01696 }
01697 }
01698
01699
01700
01701 template <class _RandomAccessIter>
01702 void __inplace_stable_sort(_RandomAccessIter __first,
01703 _RandomAccessIter __last)
01704 {
01705 if (__last - __first < 15) {
01706 __insertion_sort(__first, __last);
01707 return;
01708 }
01709 _RandomAccessIter __middle = __first + (__last - __first) / 2;
01710 __inplace_stable_sort(__first, __middle);
01711 __inplace_stable_sort(__middle, __last);
01712 __merge_without_buffer(__first, __middle, __last,
01713 __middle - __first,
01714 __last - __middle);
01715 }
01716
01717 template <class _RandomAccessIter, class _Compare>
01718 void __inplace_stable_sort(_RandomAccessIter __first,
01719 _RandomAccessIter __last, _Compare __comp)
01720 {
01721 if (__last - __first < 15) {
01722 __insertion_sort(__first, __last, __comp);
01723 return;
01724 }
01725 _RandomAccessIter __middle = __first + (__last - __first) / 2;
01726 __inplace_stable_sort(__first, __middle, __comp);
01727 __inplace_stable_sort(__middle, __last, __comp);
01728 __merge_without_buffer(__first, __middle, __last,
01729 __middle - __first,
01730 __last - __middle,
01731 __comp);
01732 }
01733
01734 template <class _RandomAccessIter1, class _RandomAccessIter2,
01735 class _Distance>
01736 void __merge_sort_loop(_RandomAccessIter1 __first,
01737 _RandomAccessIter1 __last,
01738 _RandomAccessIter2 __result, _Distance __step_size)
01739 {
01740 _Distance __two_step = 2 * __step_size;
01741
01742 while (__last - __first >= __two_step) {
01743 __result = merge(__first, __first + __step_size,
01744 __first + __step_size, __first + __two_step,
01745 __result);
01746 __first += __two_step;
01747 }
01748
01749 __step_size = min(_Distance(__last - __first), __step_size);
01750 merge(__first, __first + __step_size, __first + __step_size, __last,
01751 __result);
01752 }
01753
01754 template <class _RandomAccessIter1, class _RandomAccessIter2,
01755 class _Distance, class _Compare>
01756 void __merge_sort_loop(_RandomAccessIter1 __first,
01757 _RandomAccessIter1 __last,
01758 _RandomAccessIter2 __result, _Distance __step_size,
01759 _Compare __comp)
01760 {
01761 _Distance __two_step = 2 * __step_size;
01762
01763 while (__last - __first >= __two_step) {
01764 __result = merge(__first, __first + __step_size,
01765 __first + __step_size, __first + __two_step,
01766 __result,
01767 __comp);
01768 __first += __two_step;
01769 }
01770 __step_size = min(_Distance(__last - __first), __step_size);
01771
01772 merge(__first, __first + __step_size,
01773 __first + __step_size, __last,
01774 __result,
01775 __comp);
01776 }
01777
01778 const int __stl_chunk_size = 7;
01779
01780 template <class _RandomAccessIter, class _Distance>
01781 void __chunk_insertion_sort(_RandomAccessIter __first,
01782 _RandomAccessIter __last, _Distance __chunk_size)
01783 {
01784 while (__last - __first >= __chunk_size) {
01785 __insertion_sort(__first, __first + __chunk_size);
01786 __first += __chunk_size;
01787 }
01788 __insertion_sort(__first, __last);
01789 }
01790
01791 template <class _RandomAccessIter, class _Distance, class _Compare>
01792 void __chunk_insertion_sort(_RandomAccessIter __first,
01793 _RandomAccessIter __last,
01794 _Distance __chunk_size, _Compare __comp)
01795 {
01796 while (__last - __first >= __chunk_size) {
01797 __insertion_sort(__first, __first + __chunk_size, __comp);
01798 __first += __chunk_size;
01799 }
01800 __insertion_sort(__first, __last, __comp);
01801 }
01802
01803 template <class _RandomAccessIter, class _Pointer, class _Distance>
01804 void __merge_sort_with_buffer(_RandomAccessIter __first,
01805 _RandomAccessIter __last,
01806 _Pointer __buffer, _Distance*)
01807 {
01808 _Distance __len = __last - __first;
01809 _Pointer __buffer_last = __buffer + __len;
01810
01811 _Distance __step_size = __stl_chunk_size;
01812 __chunk_insertion_sort(__first, __last, __step_size);
01813
01814 while (__step_size < __len) {
01815 __merge_sort_loop(__first, __last, __buffer, __step_size);
01816 __step_size *= 2;
01817 __merge_sort_loop(__buffer, __buffer_last, __first, __step_size);
01818 __step_size *= 2;
01819 }
01820 }
01821
01822 template <class _RandomAccessIter, class _Pointer, class _Distance,
01823 class _Compare>
01824 void __merge_sort_with_buffer(_RandomAccessIter __first,
01825 _RandomAccessIter __last, _Pointer __buffer,
01826 _Distance*, _Compare __comp)
01827 {
01828 _Distance __len = __last - __first;
01829 _Pointer __buffer_last = __buffer + __len;
01830
01831 _Distance __step_size = __stl_chunk_size;
01832 __chunk_insertion_sort(__first, __last, __step_size, __comp);
01833
01834 while (__step_size < __len) {
01835 __merge_sort_loop(__first, __last, __buffer, __step_size, __comp);
01836 __step_size *= 2;
01837 __merge_sort_loop(__buffer, __buffer_last, __first, __step_size, __comp);
01838 __step_size *= 2;
01839 }
01840 }
01841
01842 template <class _RandomAccessIter, class _Pointer, class _Distance>
01843 void __stable_sort_adaptive(_RandomAccessIter __first,
01844 _RandomAccessIter __last, _Pointer __buffer,
01845 _Distance __buffer_size)
01846 {
01847 _Distance __len = (__last - __first + 1) / 2;
01848 _RandomAccessIter __middle = __first + __len;
01849 if (__len > __buffer_size) {
01850 __stable_sort_adaptive(__first, __middle, __buffer, __buffer_size);
01851 __stable_sort_adaptive(__middle, __last, __buffer, __buffer_size);
01852 }
01853 else {
01854 __merge_sort_with_buffer(__first, __middle, __buffer, (_Distance*)0);
01855 __merge_sort_with_buffer(__middle, __last, __buffer, (_Distance*)0);
01856 }
01857 __merge_adaptive(__first, __middle, __last, _Distance(__middle - __first),
01858 _Distance(__last - __middle), __buffer, __buffer_size);
01859 }
01860
01861 template <class _RandomAccessIter, class _Pointer, class _Distance,
01862 class _Compare>
01863 void __stable_sort_adaptive(_RandomAccessIter __first,
01864 _RandomAccessIter __last, _Pointer __buffer,
01865 _Distance __buffer_size, _Compare __comp)
01866 {
01867 _Distance __len = (__last - __first + 1) / 2;
01868 _RandomAccessIter __middle = __first + __len;
01869 if (__len > __buffer_size) {
01870 __stable_sort_adaptive(__first, __middle, __buffer, __buffer_size,
01871 __comp);
01872 __stable_sort_adaptive(__middle, __last, __buffer, __buffer_size,
01873 __comp);
01874 }
01875 else {
01876 __merge_sort_with_buffer(__first, __middle, __buffer, (_Distance*)0,
01877 __comp);
01878 __merge_sort_with_buffer(__middle, __last, __buffer, (_Distance*)0,
01879 __comp);
01880 }
01881 __merge_adaptive(__first, __middle, __last, _Distance(__middle - __first),
01882 _Distance(__last - __middle), __buffer, __buffer_size,
01883 __comp);
01884 }
01885
01886 template <class _RandomAccessIter, class _Tp, class _Distance>
01887 inline void __stable_sort_aux(_RandomAccessIter __first,
01888 _RandomAccessIter __last, _Tp*, _Distance*)
01889 {
01890 _Temporary_buffer<_RandomAccessIter, _Tp> buf(__first, __last);
01891 if (buf.begin() == 0)
01892 __inplace_stable_sort(__first, __last);
01893 else
01894 __stable_sort_adaptive(__first, __last, buf.begin(),
01895 _Distance(buf.size()));
01896 }
01897
01898 template <class _RandomAccessIter, class _Tp, class _Distance, class _Compare>
01899 inline void __stable_sort_aux(_RandomAccessIter __first,
01900 _RandomAccessIter __last, _Tp*, _Distance*,
01901 _Compare __comp)
01902 {
01903 _Temporary_buffer<_RandomAccessIter, _Tp> buf(__first, __last);
01904 if (buf.begin() == 0)
01905 __inplace_stable_sort(__first, __last, __comp);
01906 else
01907 __stable_sort_adaptive(__first, __last, buf.begin(),
01908 _Distance(buf.size()),
01909 __comp);
01910 }
01911
01912 template <class _RandomAccessIter>
01913 inline void stable_sort(_RandomAccessIter __first,
01914 _RandomAccessIter __last)
01915 {
01916
01917 __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
01918 _RandomAccessIter>);
01919 __glibcpp_function_requires(_LessThanComparableConcept<
01920 typename iterator_traits<_RandomAccessIter>::value_type>);
01921
01922 __stable_sort_aux(__first, __last,
01923 __value_type(__first),
01924 __distance_type(__first));
01925 }
01926
01927 template <class _RandomAccessIter, class _Compare>
01928 inline void stable_sort(_RandomAccessIter __first,
01929 _RandomAccessIter __last, _Compare __comp)
01930 {
01931
01932 __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
01933 _RandomAccessIter>);
01934 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare,
01935 typename iterator_traits<_RandomAccessIter>::value_type,
01936 typename iterator_traits<_RandomAccessIter>::value_type>);
01937
01938 __stable_sort_aux(__first, __last,
01939 __value_type(__first),
01940 __distance_type(__first),
01941 __comp);
01942 }
01943
01944
01945
01946 template <class _RandomAccessIter, class _Tp>
01947 void __partial_sort(_RandomAccessIter __first, _RandomAccessIter __middle,
01948 _RandomAccessIter __last, _Tp*)
01949 {
01950 make_heap(__first, __middle);
01951 for (_RandomAccessIter __i = __middle; __i < __last; ++__i)
01952 if (*__i < *__first)
01953 __pop_heap(__first, __middle, __i, _Tp(*__i),
01954 __distance_type(__first));
01955 sort_heap(__first, __middle);
01956 }
01957
01958 template <class _RandomAccessIter>
01959 inline void partial_sort(_RandomAccessIter __first,
01960 _RandomAccessIter __middle,
01961 _RandomAccessIter __last)
01962 {
01963
01964 __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
01965 _RandomAccessIter>);
01966 __glibcpp_function_requires(_LessThanComparableConcept<
01967 typename iterator_traits<_RandomAccessIter>::value_type>);
01968
01969 __partial_sort(__first, __middle, __last, __value_type(__first));
01970 }
01971
01972 template <class _RandomAccessIter, class _Tp, class _Compare>
01973 void __partial_sort(_RandomAccessIter __first, _RandomAccessIter __middle,
01974 _RandomAccessIter __last, _Tp*, _Compare __comp)
01975 {
01976 make_heap(__first, __middle, __comp);
01977 for (_RandomAccessIter __i = __middle; __i < __last; ++__i)
01978 if (__comp(*__i, *__first))
01979 __pop_heap(__first, __middle, __i, _Tp(*__i), __comp,
01980 __distance_type(__first));
01981 sort_heap(__first, __middle, __comp);
01982 }
01983
01984 template <class _RandomAccessIter, class _Compare>
01985 inline void partial_sort(_RandomAccessIter __first,
01986 _RandomAccessIter __middle,
01987 _RandomAccessIter __last, _Compare __comp)
01988 {
01989
01990 __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
01991 _RandomAccessIter>);
01992 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare,
01993 typename iterator_traits<_RandomAccessIter>::value_type,
01994 typename iterator_traits<_RandomAccessIter>::value_type>);
01995
01996 __partial_sort(__first, __middle, __last, __value_type(__first), __comp);
01997 }
01998
01999 template <class _InputIter, class _RandomAccessIter, class _Distance,
02000 class _Tp>
02001 _RandomAccessIter __partial_sort_copy(_InputIter __first,
02002 _InputIter __last,
02003 _RandomAccessIter __result_first,
02004 _RandomAccessIter __result_last,
02005 _Distance*, _Tp*)
02006 {
02007 if (__result_first == __result_last) return __result_last;
02008 _RandomAccessIter __result_real_last = __result_first;
02009 while(__first != __last && __result_real_last != __result_last) {
02010 *__result_real_last = *__first;
02011 ++__result_real_last;
02012 ++__first;
02013 }
02014 make_heap(__result_first, __result_real_last);
02015 while (__first != __last) {
02016 if (*__first < *__result_first)
02017 __adjust_heap(__result_first, _Distance(0),
02018 _Distance(__result_real_last - __result_first),
02019 _Tp(*__first));
02020 ++__first;
02021 }
02022 sort_heap(__result_first, __result_real_last);
02023 return __result_real_last;
02024 }
02025
02026 template <class _InputIter, class _RandomAccessIter>
02027 inline _RandomAccessIter
02028 partial_sort_copy(_InputIter __first, _InputIter __last,
02029 _RandomAccessIter __result_first,
02030 _RandomAccessIter __result_last)
02031 {
02032
02033 __glibcpp_function_requires(_InputIteratorConcept<_InputIter>);
02034 __glibcpp_function_requires(_ConvertibleConcept<
02035 typename iterator_traits<_InputIter>::value_type,
02036 typename iterator_traits<_RandomAccessIter>::value_type>);
02037 __glibcpp_function_requires(_LessThanComparableConcept<
02038 typename iterator_traits<_RandomAccessIter>::value_type>);
02039 __glibcpp_function_requires(_LessThanComparableConcept<
02040 typename iterator_traits<_InputIter>::value_type>);
02041
02042 return __partial_sort_copy(__first, __last, __result_first, __result_last,
02043 __distance_type(__result_first),
02044 __value_type(__first));
02045 }
02046
02047 template <class _InputIter, class _RandomAccessIter, class _Compare,
02048 class _Distance, class _Tp>
02049 _RandomAccessIter __partial_sort_copy(_InputIter __first,
02050 _InputIter __last,
02051 _RandomAccessIter __result_first,
02052 _RandomAccessIter __result_last,
02053 _Compare __comp, _Distance*, _Tp*)
02054 {
02055 if (__result_first == __result_last) return __result_last;
02056 _RandomAccessIter __result_real_last = __result_first;
02057 while(__first != __last && __result_real_last != __result_last) {
02058 *__result_real_last = *__first;
02059 ++__result_real_last;
02060 ++__first;
02061 }
02062 make_heap(__result_first, __result_real_last, __comp);
02063 while (__first != __last) {
02064 if (__comp(*__first, *__result_first))
02065 __adjust_heap(__result_first, _Distance(0),
02066 _Distance(__result_real_last - __result_first),
02067 _Tp(*__first),
02068 __comp);
02069 ++__first;
02070 }
02071 sort_heap(__result_first, __result_real_last, __comp);
02072 return __result_real_last;
02073 }
02074
02075 template <class _InputIter, class _RandomAccessIter, class _Compare>
02076 inline _RandomAccessIter
02077 partial_sort_copy(_InputIter __first, _InputIter __last,
02078 _RandomAccessIter __result_first,
02079 _RandomAccessIter __result_last, _Compare __comp)
02080 {
02081
02082 __glibcpp_function_requires(_InputIteratorConcept<_InputIter>);
02083 __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
02084 _RandomAccessIter>);
02085 __glibcpp_function_requires(_ConvertibleConcept<
02086 typename iterator_traits<_InputIter>::value_type,
02087 typename iterator_traits<_RandomAccessIter>::value_type>);
02088 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare,
02089 typename iterator_traits<_RandomAccessIter>::value_type,
02090 typename iterator_traits<_RandomAccessIter>::value_type>);
02091
02092 return __partial_sort_copy(__first, __last, __result_first, __result_last,
02093 __comp,
02094 __distance_type(__result_first),
02095 __value_type(__first));
02096 }
02097
02098
02099
02100 template <class _RandomAccessIter, class _Tp>
02101 void __nth_element(_RandomAccessIter __first, _RandomAccessIter __nth,
02102 _RandomAccessIter __last, _Tp*)
02103 {
02104 while (__last - __first > 3) {
02105 _RandomAccessIter __cut =
02106 __unguarded_partition(__first, __last,
02107 _Tp(__median(*__first,
02108 *(__first + (__last - __first)/2),
02109 *(__last - 1))));
02110 if (__cut <= __nth)
02111 __first = __cut;
02112 else
02113 __last = __cut;
02114 }
02115 __insertion_sort(__first, __last);
02116 }
02117
02118 template <class _RandomAccessIter>
02119 inline void nth_element(_RandomAccessIter __first, _RandomAccessIter __nth,
02120 _RandomAccessIter __last)
02121 {
02122
02123 __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
02124 _RandomAccessIter>);
02125 __glibcpp_function_requires(_LessThanComparableConcept<
02126 typename iterator_traits<_RandomAccessIter>::value_type>);
02127
02128 __nth_element(__first, __nth, __last, __value_type(__first));
02129 }
02130
02131 template <class _RandomAccessIter, class _Tp, class _Compare>
02132 void __nth_element(_RandomAccessIter __first, _RandomAccessIter __nth,
02133 _RandomAccessIter __last, _Tp*, _Compare __comp)
02134 {
02135 while (__last - __first > 3) {
02136 _RandomAccessIter __cut =
02137 __unguarded_partition(__first, __last,
02138 _Tp(__median(*__first,
02139 *(__first + (__last - __first)/2),
02140 *(__last - 1),
02141 __comp)),
02142 __comp);
02143 if (__cut <= __nth)
02144 __first = __cut;
02145 else
02146 __last = __cut;
02147 }
02148 __insertion_sort(__first, __last, __comp);
02149 }
02150
02151 template <class _RandomAccessIter, class _Compare>
02152 inline void nth_element(_RandomAccessIter __first, _RandomAccessIter __nth,
02153 _RandomAccessIter __last, _Compare __comp)
02154 {
02155
02156 __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
02157 _RandomAccessIter>);
02158 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare,
02159 typename iterator_traits<_RandomAccessIter>::value_type,
02160 typename iterator_traits<_RandomAccessIter>::value_type>);
02161
02162 __nth_element(__first, __nth, __last, __value_type(__first), __comp);
02163 }
02164
02165
02166
02167
02168 template <class _ForwardIter, class _Tp, class _Distance>
02169 _ForwardIter __lower_bound(_ForwardIter __first, _ForwardIter __last,
02170 const _Tp& __val, _Distance*)
02171 {
02172 _Distance __len = 0;
02173 distance(__first, __last, __len);
02174 _Distance __half;
02175 _ForwardIter __middle;
02176
02177 while (__len > 0) {
02178 __half = __len >> 1;
02179 __middle = __first;
02180 advance(__middle, __half);
02181 if (*__middle < __val) {
02182 __first = __middle;
02183 ++__first;
02184 __len = __len - __half - 1;
02185 }
02186 else
02187 __len = __half;
02188 }
02189 return __first;
02190 }
02191
02192 template <class _ForwardIter, class _Tp>
02193 inline _ForwardIter lower_bound(_ForwardIter __first, _ForwardIter __last,
02194 const _Tp& __val)
02195 {
02196
02197 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>);
02198 __glibcpp_function_requires(_SameTypeConcept<_Tp,
02199 typename iterator_traits<_ForwardIter>::value_type>);
02200 __glibcpp_function_requires(_LessThanComparableConcept<_Tp>);
02201
02202 return __lower_bound(__first, __last, __val,
02203 __distance_type(__first));
02204 }
02205
02206 template <class _ForwardIter, class _Tp, class _Compare, class _Distance>
02207 _ForwardIter __lower_bound(_ForwardIter __first, _ForwardIter __last,
02208 const _Tp& __val, _Compare __comp, _Distance*)
02209 {
02210 _Distance __len = 0;
02211 distance(__first, __last, __len);
02212 _Distance __half;
02213 _ForwardIter __middle;
02214
02215 while (__len > 0) {
02216 __half = __len >> 1;
02217 __middle = __first;
02218 advance(__middle, __half);
02219 if (__comp(*__middle, __val)) {
02220 __first = __middle;
02221 ++__first;
02222 __len = __len - __half - 1;
02223 }
02224 else
02225 __len = __half;
02226 }
02227 return __first;
02228 }
02229
02230 template <class _ForwardIter, class _Tp, class _Compare>
02231 inline _ForwardIter lower_bound(_ForwardIter __first, _ForwardIter __last,
02232 const _Tp& __val, _Compare __comp)
02233 {
02234
02235 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>);
02236 __glibcpp_function_requires(_SameTypeConcept<_Tp,
02237 typename iterator_traits<_ForwardIter>::value_type>);
02238 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, _Tp, _Tp>);
02239
02240 return __lower_bound(__first, __last, __val, __comp,
02241 __distance_type(__first));
02242 }
02243
02244 template <class _ForwardIter, class _Tp, class _Distance>
02245 _ForwardIter __upper_bound(_ForwardIter __first, _ForwardIter __last,
02246 const _Tp& __val, _Distance*)
02247 {
02248 _Distance __len = 0;
02249 distance(__first, __last, __len);
02250 _Distance __half;
02251 _ForwardIter __middle;
02252
02253 while (__len > 0) {
02254 __half = __len >> 1;
02255 __middle = __first;
02256 advance(__middle, __half);
02257 if (__val < *__middle)
02258 __len = __half;
02259 else {
02260 __first = __middle;
02261 ++__first;
02262 __len = __len - __half - 1;
02263 }
02264 }
02265 return __first;
02266 }
02267
02268 template <class _ForwardIter, class _Tp>
02269 inline _ForwardIter upper_bound(_ForwardIter __first, _ForwardIter __last,
02270 const _Tp& __val)
02271 {
02272
02273 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>);
02274 __glibcpp_function_requires(_SameTypeConcept<_Tp,
02275 typename iterator_traits<_ForwardIter>::value_type>);
02276 __glibcpp_function_requires(_LessThanComparableConcept<_Tp>);
02277
02278 return __upper_bound(__first, __last, __val,
02279 __distance_type(__first));
02280 }
02281
02282 template <class _ForwardIter, class _Tp, class _Compare, class _Distance>
02283 _ForwardIter __upper_bound(_ForwardIter __first, _ForwardIter __last,
02284 const _Tp& __val, _Compare __comp, _Distance*)
02285 {
02286 _Distance __len = 0;
02287 distance(__first, __last, __len);
02288 _Distance __half;
02289 _ForwardIter __middle;
02290
02291 while (__len > 0) {
02292 __half = __len >> 1;
02293 __middle = __first;
02294 advance(__middle, __half);
02295 if (__comp(__val, *__middle))
02296 __len = __half;
02297 else {
02298 __first = __middle;
02299 ++__first;
02300 __len = __len - __half - 1;
02301 }
02302 }
02303 return __first;
02304 }
02305
02306 template <class _ForwardIter, class _Tp, class _Compare>
02307 inline _ForwardIter upper_bound(_ForwardIter __first, _ForwardIter __last,
02308 const _Tp& __val, _Compare __comp)
02309 {
02310
02311 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>);
02312 __glibcpp_function_requires(_SameTypeConcept<_Tp,
02313 typename iterator_traits<_ForwardIter>::value_type>);
02314 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, _Tp, _Tp>);
02315
02316 return __upper_bound(__first, __last, __val, __comp,
02317 __distance_type(__first));
02318 }
02319
02320 template <class _ForwardIter, class _Tp, class _Distance>
02321 pair<_ForwardIter, _ForwardIter>
02322 __equal_range(_ForwardIter __first, _ForwardIter __last, const _Tp& __val,
02323 _Distance*)
02324 {
02325 _Distance __len = 0;
02326 distance(__first, __last, __len);
02327 _Distance __half;
02328 _ForwardIter __middle, __left, __right;
02329
02330 while (__len > 0) {
02331 __half = __len >> 1;
02332 __middle = __first;
02333 advance(__middle, __half);
02334 if (*__middle < __val) {
02335 __first = __middle;
02336 ++__first;
02337 __len = __len - __half - 1;
02338 }
02339 else if (__val < *__middle)
02340 __len = __half;
02341 else {
02342 __left = lower_bound(__first, __middle, __val);
02343 advance(__first, __len);
02344 __right = upper_bound(++__middle, __first, __val);
02345 return pair<_ForwardIter, _ForwardIter>(__left, __right);
02346 }
02347 }
02348 return pair<_ForwardIter, _ForwardIter>(__first, __first);
02349 }
02350
02351 template <class _ForwardIter, class _Tp>
02352 inline pair<_ForwardIter, _ForwardIter>
02353 equal_range(_ForwardIter __first, _ForwardIter __last, const _Tp& __val)
02354 {
02355
02356 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>);
02357 __glibcpp_function_requires(_SameTypeConcept<_Tp,
02358 typename iterator_traits<_ForwardIter>::value_type>);
02359 __glibcpp_function_requires(_LessThanComparableConcept<_Tp>);
02360
02361 return __equal_range(__first, __last, __val,
02362 __distance_type(__first));
02363 }
02364
02365 template <class _ForwardIter, class _Tp, class _Compare, class _Distance>
02366 pair<_ForwardIter, _ForwardIter>
02367 __equal_range(_ForwardIter __first, _ForwardIter __last, const _Tp& __val,
02368 _Compare __comp, _Distance*)
02369 {
02370 _Distance __len = 0;
02371 distance(__first, __last, __len);
02372 _Distance __half;
02373 _ForwardIter __middle, __left, __right;
02374
02375 while (__len > 0) {
02376 __half = __len >> 1;
02377 __middle = __first;
02378 advance(__middle, __half);
02379 if (__comp(*__middle, __val)) {
02380 __first = __middle;
02381 ++__first;
02382 __len = __len - __half - 1;
02383 }
02384 else if (__comp(__val, *__middle))
02385 __len = __half;
02386 else {
02387 __left = lower_bound(__first, __middle, __val, __comp);
02388 advance(__first, __len);
02389 __right = upper_bound(++__middle, __first, __val, __comp);
02390 return pair<_ForwardIter, _ForwardIter>(__left, __right);
02391 }
02392 }
02393 return pair<_ForwardIter, _ForwardIter>(__first, __first);
02394 }
02395
02396 template <class _ForwardIter, class _Tp, class _Compare>
02397 inline pair<_ForwardIter, _ForwardIter>
02398 equal_range(_ForwardIter __first, _ForwardIter __last, const _Tp& __val,
02399 _Compare __comp)
02400 {
02401
02402 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>);
02403 __glibcpp_function_requires(_SameTypeConcept<_Tp,
02404 typename iterator_traits<_ForwardIter>::value_type>);
02405 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, _Tp, _Tp>);
02406
02407 return __equal_range(__first, __last, __val, __comp,
02408 __distance_type(__first));
02409 }
02410
02411 template <class _ForwardIter, class _Tp>
02412 bool binary_search(_ForwardIter __first, _ForwardIter __last,
02413 const _Tp& __val)
02414 {
02415
02416 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>);
02417 __glibcpp_function_requires(_SameTypeConcept<_Tp,
02418 typename iterator_traits<_ForwardIter>::value_type>);
02419 __glibcpp_function_requires(_LessThanComparableConcept<_Tp>);
02420
02421 _ForwardIter __i = lower_bound(__first, __last, __val);
02422 return __i != __last && !(__val < *__i);
02423 }
02424
02425 template <class _ForwardIter, class _Tp, class _Compare>
02426 bool binary_search(_ForwardIter __first, _ForwardIter __last,
02427 const _Tp& __val,
02428 _Compare __comp)
02429 {
02430
02431 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>);
02432 __glibcpp_function_requires(_SameTypeConcept<_Tp,
02433 typename iterator_traits<_ForwardIter>::value_type>);
02434 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, _Tp, _Tp>);
02435
02436 _ForwardIter __i = lower_bound(__first, __last, __val, __comp);
02437 return __i != __last && !__comp(__val, *__i);
02438 }
02439
02440
02441
02442 template <class _InputIter1, class _InputIter2, class _OutputIter>
02443 _OutputIter merge(_InputIter1 __first1, _InputIter1 __last1,
02444 _InputIter2 __first2, _InputIter2 __last2,
02445 _OutputIter __result)
02446 {
02447
02448 __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>);
02449 __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>);
02450 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
02451 typename iterator_traits<_InputIter1>::value_type>);
02452 __glibcpp_function_requires(_SameTypeConcept<
02453 typename iterator_traits<_InputIter1>::value_type,
02454 typename iterator_traits<_InputIter2>::value_type>);
02455 __glibcpp_function_requires(_LessThanComparableConcept<
02456 typename iterator_traits<_InputIter1>::value_type>);
02457
02458 while (__first1 != __last1 && __first2 != __last2) {
02459 if (*__first2 < *__first1) {
02460 *__result = *__first2;
02461 ++__first2;
02462 }
02463 else {
02464 *__result = *__first1;
02465 ++__first1;
02466 }
02467 ++__result;
02468 }
02469 return copy(__first2, __last2, copy(__first1, __last1, __result));
02470 }
02471
02472 template <class _InputIter1, class _InputIter2, class _OutputIter,
02473 class _Compare>
02474 _OutputIter merge(_InputIter1 __first1, _InputIter1 __last1,
02475 _InputIter2 __first2, _InputIter2 __last2,
02476 _OutputIter __result, _Compare __comp)
02477 {
02478
02479 __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>);
02480 __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>);
02481 __glibcpp_function_requires(_SameTypeConcept<
02482 typename iterator_traits<_InputIter1>::value_type,
02483 typename iterator_traits<_InputIter2>::value_type>);
02484 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
02485 typename iterator_traits<_InputIter1>::value_type>);
02486 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare,
02487 typename iterator_traits<_InputIter1>::value_type,
02488 typename iterator_traits<_InputIter2>::value_type>);
02489
02490 while (__first1 != __last1 && __first2 != __last2) {
02491 if (__comp(*__first2, *__first1)) {
02492 *__result = *__first2;
02493 ++__first2;
02494 }
02495 else {
02496 *__result = *__first1;
02497 ++__first1;
02498 }
02499 ++__result;
02500 }
02501 return copy(__first2, __last2, copy(__first1, __last1, __result));
02502 }
02503
02504
02505
02506 template <class _BidirectionalIter, class _Distance>
02507 void __merge_without_buffer(_BidirectionalIter __first,
02508 _BidirectionalIter __middle,
02509 _BidirectionalIter __last,
02510 _Distance __len1, _Distance __len2)
02511 {
02512 if (__len1 == 0 || __len2 == 0)
02513 return;
02514 if (__len1 + __len2 == 2) {
02515 if (*__middle < *__first)
02516 iter_swap(__first, __middle);
02517 return;
02518 }
02519 _BidirectionalIter __first_cut = __first;
02520 _BidirectionalIter __second_cut = __middle;
02521 _Distance __len11 = 0;
02522 _Distance __len22 = 0;
02523 if (__len1 > __len2) {
02524 __len11 = __len1 / 2;
02525 advance(__first_cut, __len11);
02526 __second_cut = lower_bound(__middle, __last, *__first_cut);
02527 distance(__middle, __second_cut, __len22);
02528 }
02529 else {
02530 __len22 = __len2 / 2;
02531 advance(__second_cut, __len22);
02532 __first_cut = upper_bound(__first, __middle, *__second_cut);
02533 distance(__first, __first_cut, __len11);
02534 }
02535 _BidirectionalIter __new_middle
02536 = rotate(__first_cut, __middle, __second_cut);
02537 __merge_without_buffer(__first, __first_cut, __new_middle,
02538 __len11, __len22);
02539 __merge_without_buffer(__new_middle, __second_cut, __last, __len1 - __len11,
02540 __len2 - __len22);
02541 }
02542
02543 template <class _BidirectionalIter, class _Distance, class _Compare>
02544 void __merge_without_buffer(_BidirectionalIter __first,
02545 _BidirectionalIter __middle,
02546 _BidirectionalIter __last,
02547 _Distance __len1, _Distance __len2,
02548 _Compare __comp)
02549 {
02550 if (__len1 == 0 || __len2 == 0)
02551 return;
02552 if (__len1 + __len2 == 2) {
02553 if (__comp(*__middle, *__first))
02554 iter_swap(__first, __middle);
02555 return;
02556 }
02557 _BidirectionalIter __first_cut = __first;
02558 _BidirectionalIter __second_cut = __middle;
02559 _Distance __len11 = 0;
02560 _Distance __len22 = 0;
02561 if (__len1 > __len2) {
02562 __len11 = __len1 / 2;
02563 advance(__first_cut, __len11);
02564 __second_cut = lower_bound(__middle, __last, *__first_cut, __comp);
02565 distance(__middle, __second_cut, __len22);
02566 }
02567 else {
02568 __len22 = __len2 / 2;
02569 advance(__second_cut, __len22);
02570 __first_cut = upper_bound(__first, __middle, *__second_cut, __comp);
02571 distance(__first, __first_cut, __len11);
02572 }
02573 _BidirectionalIter __new_middle
02574 = rotate(__first_cut, __middle, __second_cut);
02575 __merge_without_buffer(__first, __first_cut, __new_middle, __len11, __len22,
02576 __comp);
02577 __merge_without_buffer(__new_middle, __second_cut, __last, __len1 - __len11,
02578 __len2 - __len22, __comp);
02579 }
02580
02581 template <class _BidirectionalIter1, class _BidirectionalIter2,
02582 class _Distance>
02583 _BidirectionalIter1 __rotate_adaptive(_BidirectionalIter1 __first,
02584 _BidirectionalIter1 __middle,
02585 _BidirectionalIter1 __last,
02586 _Distance __len1, _Distance __len2,
02587 _BidirectionalIter2 __buffer,
02588 _Distance __buffer_size)
02589 {
02590 _BidirectionalIter2 __buffer_end;
02591 if (__len1 > __len2 && __len2 <= __buffer_size) {
02592 __buffer_end = copy(__middle, __last, __buffer);
02593 copy_backward(__first, __middle, __last);
02594 return copy(__buffer, __buffer_end, __first);
02595 }
02596 else if (__len1 <= __buffer_size) {
02597 __buffer_end = copy(__first, __middle, __buffer);
02598 copy(__middle, __last, __first);
02599 return copy_backward(__buffer, __buffer_end, __last);
02600 }
02601 else
02602 return rotate(__first, __middle, __last);
02603 }
02604
02605 template <class _BidirectionalIter1, class _BidirectionalIter2,
02606 class _BidirectionalIter3>
02607 _BidirectionalIter3 __merge_backward(_BidirectionalIter1 __first1,
02608 _BidirectionalIter1 __last1,
02609 _BidirectionalIter2 __first2,
02610 _BidirectionalIter2 __last2,
02611 _BidirectionalIter3 __result)
02612 {
02613 if (__first1 == __last1)
02614 return copy_backward(__first2, __last2, __result);
02615 if (__first2 == __last2)
02616 return copy_backward(__first1, __last1, __result);
02617 --__last1;
02618 --__last2;
02619 while (true) {
02620 if (*__last2 < *__last1) {
02621 *--__result = *__last1;
02622 if (__first1 == __last1)
02623 return copy_backward(__first2, ++__last2, __result);
02624 --__last1;
02625 }
02626 else {
02627 *--__result = *__last2;
02628 if (__first2 == __last2)
02629 return copy_backward(__first1, ++__last1, __result);
02630 --__last2;
02631 }
02632 }
02633 }
02634
02635 template <class _BidirectionalIter1, class _BidirectionalIter2,
02636 class _BidirectionalIter3, class _Compare>
02637 _BidirectionalIter3 __merge_backward(_BidirectionalIter1 __first1,
02638 _BidirectionalIter1 __last1,
02639 _BidirectionalIter2 __first2,
02640 _BidirectionalIter2 __last2,
02641 _BidirectionalIter3 __result,
02642 _Compare __comp)
02643 {
02644 if (__first1 == __last1)
02645 return copy_backward(__first2, __last2, __result);
02646 if (__first2 == __last2)
02647 return copy_backward(__first1, __last1, __result);
02648 --__last1;
02649 --__last2;
02650 while (true) {
02651 if (__comp(*__last2, *__last1)) {
02652 *--__result = *__last1;
02653 if (__first1 == __last1)
02654 return copy_backward(__first2, ++__last2, __result);
02655 --__last1;
02656 }
02657 else {
02658 *--__result = *__last2;
02659 if (__first2 == __last2)
02660 return copy_backward(__first1, ++__last1, __result);
02661 --__last2;
02662 }
02663 }
02664 }
02665
02666 template <class _BidirectionalIter, class _Distance, class _Pointer>
02667 void __merge_adaptive(_BidirectionalIter __first,
02668 _BidirectionalIter __middle,
02669 _BidirectionalIter __last,
02670 _Distance __len1, _Distance __len2,
02671 _Pointer __buffer, _Distance __buffer_size)
02672 {
02673 if (__len1 <= __len2 && __len1 <= __buffer_size) {
02674 _Pointer __buffer_end = copy(__first, __middle, __buffer);
02675 merge(__buffer, __buffer_end, __middle, __last, __first);
02676 }
02677 else if (__len2 <= __buffer_size) {
02678 _Pointer __buffer_end = copy(__middle, __last, __buffer);
02679 __merge_backward(__first, __middle, __buffer, __buffer_end, __last);
02680 }
02681 else {
02682 _BidirectionalIter __first_cut = __first;
02683 _BidirectionalIter __second_cut = __middle;
02684 _Distance __len11 = 0;
02685 _Distance __len22 = 0;
02686 if (__len1 > __len2) {
02687 __len11 = __len1 / 2;
02688 advance(__first_cut, __len11);
02689 __second_cut = lower_bound(__middle, __last, *__first_cut);
02690 distance(__middle, __second_cut, __len22);
02691 }
02692 else {
02693 __len22 = __len2 / 2;
02694 advance(__second_cut, __len22);
02695 __first_cut = upper_bound(__first, __middle, *__second_cut);
02696 distance(__first, __first_cut, __len11);
02697 }
02698 _BidirectionalIter __new_middle =
02699 __rotate_adaptive(__first_cut, __middle, __second_cut, __len1 - __len11,
02700 __len22, __buffer, __buffer_size);
02701 __merge_adaptive(__first, __first_cut, __new_middle, __len11,
02702 __len22, __buffer, __buffer_size);
02703 __merge_adaptive(__new_middle, __second_cut, __last, __len1 - __len11,
02704 __len2 - __len22, __buffer, __buffer_size);
02705 }
02706 }
02707
02708 template <class _BidirectionalIter, class _Distance, class _Pointer,
02709 class _Compare>
02710 void __merge_adaptive(_BidirectionalIter __first,
02711 _BidirectionalIter __middle,
02712 _BidirectionalIter __last,
02713 _Distance __len1, _Distance __len2,
02714 _Pointer __buffer, _Distance __buffer_size,
02715 _Compare __comp)
02716 {
02717 if (__len1 <= __len2 && __len1 <= __buffer_size) {
02718 _Pointer __buffer_end = copy(__first, __middle, __buffer);
02719 merge(__buffer, __buffer_end, __middle, __last, __first, __comp);
02720 }
02721 else if (__len2 <= __buffer_size) {
02722 _Pointer __buffer_end = copy(__middle, __last, __buffer);
02723 __merge_backward(__first, __middle, __buffer, __buffer_end, __last,
02724 __comp);
02725 }
02726 else {
02727 _BidirectionalIter __first_cut = __first;
02728 _BidirectionalIter __second_cut = __middle;
02729 _Distance __len11 = 0;
02730 _Distance __len22 = 0;
02731 if (__len1 > __len2) {
02732 __len11 = __len1 / 2;
02733 advance(__first_cut, __len11);
02734 __second_cut = lower_bound(__middle, __last, *__first_cut, __comp);
02735 distance(__middle, __second_cut, __len22);
02736 }
02737 else {
02738 __len22 = __len2 / 2;
02739 advance(__second_cut, __len22);
02740 __first_cut = upper_bound(__first, __middle, *__second_cut, __comp);
02741 distance(__first, __first_cut, __len11);
02742 }
02743 _BidirectionalIter __new_middle =
02744 __rotate_adaptive(__first_cut, __middle, __second_cut, __len1 - __len11,
02745 __len22, __buffer, __buffer_size);
02746 __merge_adaptive(__first, __first_cut, __new_middle, __len11,
02747 __len22, __buffer, __buffer_size, __comp);
02748 __merge_adaptive(__new_middle, __second_cut, __last, __len1 - __len11,
02749 __len2 - __len22, __buffer, __buffer_size, __comp);
02750 }
02751 }
02752
02753 template <class _BidirectionalIter, class _Tp, class _Distance>
02754 inline void __inplace_merge_aux(_BidirectionalIter __first,
02755 _BidirectionalIter __middle,
02756 _BidirectionalIter __last, _Tp*, _Distance*)
02757 {
02758 _Distance __len1 = 0;
02759 distance(__first, __middle, __len1);
02760 _Distance __len2 = 0;
02761 distance(__middle, __last, __len2);
02762
02763 _Temporary_buffer<_BidirectionalIter, _Tp> __buf(__first, __last);
02764 if (__buf.begin() == 0)
02765 __merge_without_buffer(__first, __middle, __last, __len1, __len2);
02766 else
02767 __merge_adaptive(__first, __middle, __last, __len1, __len2,
02768 __buf.begin(), _Distance(__buf.size()));
02769 }
02770
02771 template <class _BidirectionalIter, class _Tp,
02772 class _Distance, class _Compare>
02773 inline void __inplace_merge_aux(_BidirectionalIter __first,
02774 _BidirectionalIter __middle,
02775 _BidirectionalIter __last, _Tp*, _Distance*,
02776 _Compare __comp)
02777 {
02778 _Distance __len1 = 0;
02779 distance(__first, __middle, __len1);
02780 _Distance __len2 = 0;
02781 distance(__middle, __last, __len2);
02782
02783 _Temporary_buffer<_BidirectionalIter, _Tp> __buf(__first, __last);
02784 if (__buf.begin() == 0)
02785 __merge_without_buffer(__first, __middle, __last, __len1, __len2, __comp);
02786 else
02787 __merge_adaptive(__first, __middle, __last, __len1, __len2,
02788 __buf.begin(), _Distance(__buf.size()),
02789 __comp);
02790 }
02791
02792 template <class _BidirectionalIter>
02793 inline void inplace_merge(_BidirectionalIter __first,
02794 _BidirectionalIter __middle,
02795 _BidirectionalIter __last)
02796 {
02797
02798 __glibcpp_function_requires(_Mutable_BidirectionalIteratorConcept<
02799 _BidirectionalIter>);
02800 __glibcpp_function_requires(_LessThanComparableConcept<
02801 typename iterator_traits<_BidirectionalIter>::value_type>);
02802
02803 if (__first == __middle || __middle == __last)
02804 return;
02805 __inplace_merge_aux(__first, __middle, __last,
02806 __value_type(__first), __distance_type(__first));
02807 }
02808
02809 template <class _BidirectionalIter, class _Compare>
02810 inline void inplace_merge(_BidirectionalIter __first,
02811 _BidirectionalIter __middle,
02812 _BidirectionalIter __last, _Compare __comp)
02813 {
02814
02815 __glibcpp_function_requires(_Mutable_BidirectionalIteratorConcept<
02816 _BidirectionalIter>);
02817 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare,
02818 typename iterator_traits<_BidirectionalIter>::value_type,
02819 typename iterator_traits<_BidirectionalIter>::value_type>);
02820
02821 if (__first == __middle || __middle == __last)
02822 return;
02823 __inplace_merge_aux(__first, __middle, __last,
02824 __value_type(__first), __distance_type(__first),
02825 __comp);
02826 }
02827
02828
02829
02830
02831
02832
02833 template <class _InputIter1, class _InputIter2>
02834 bool includes(_InputIter1 __first1, _InputIter1 __last1,
02835 _InputIter2 __first2, _InputIter2 __last2)
02836 {
02837
02838 __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>);
02839 __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>);
02840 __glibcpp_function_requires(_SameTypeConcept<
02841 typename iterator_traits<_InputIter1>::value_type,
02842 typename iterator_traits<_InputIter2>::value_type>);
02843 __glibcpp_function_requires(_LessThanComparableConcept<
02844 typename iterator_traits<_InputIter1>::value_type>);
02845
02846 while (__first1 != __last1 && __first2 != __last2)
02847 if (*__first2 < *__first1)
02848 return false;
02849 else if(*__first1 < *__first2)
02850 ++__first1;
02851 else
02852 ++__first1, ++__first2;
02853
02854 return __first2 == __last2;
02855 }
02856
02857 template <class _InputIter1, class _InputIter2, class _Compare>
02858 bool includes(_InputIter1 __first1, _InputIter1 __last1,
02859 _InputIter2 __first2, _InputIter2 __last2, _Compare __comp)
02860 {
02861
02862 __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>);
02863 __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>);
02864 __glibcpp_function_requires(_SameTypeConcept<
02865 typename iterator_traits<_InputIter1>::value_type,
02866 typename iterator_traits<_InputIter2>::value_type>);
02867 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare,
02868 typename iterator_traits<_InputIter1>::value_type,
02869 typename iterator_traits<_InputIter2>::value_type>);
02870
02871 while (__first1 != __last1 && __first2 != __last2)
02872 if (__comp(*__first2, *__first1))
02873 return false;
02874 else if(__comp(*__first1, *__first2))
02875 ++__first1;
02876 else
02877 ++__first1, ++__first2;
02878
02879 return __first2 == __last2;
02880 }
02881
02882 template <class _InputIter1, class _InputIter2, class _OutputIter>
02883 _OutputIter set_union(_InputIter1 __first1, _InputIter1 __last1,
02884 _InputIter2 __first2, _InputIter2 __last2,
02885 _OutputIter __result)
02886 {
02887
02888 __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>);
02889 __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>);
02890 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
02891 typename iterator_traits<_InputIter1>::value_type>);
02892 __glibcpp_function_requires(_SameTypeConcept<
02893 typename iterator_traits<_InputIter1>::value_type,
02894 typename iterator_traits<_InputIter2>::value_type>);
02895 __glibcpp_function_requires(_LessThanComparableConcept<
02896 typename iterator_traits<_InputIter1>::value_type>);
02897
02898 while (__first1 != __last1 && __first2 != __last2) {
02899 if (*__first1 < *__first2) {
02900 *__result = *__first1;
02901 ++__first1;
02902 }
02903 else if (*__first2 < *__first1) {
02904 *__result = *__first2;
02905 ++__first2;
02906 }
02907 else {
02908 *__result = *__first1;
02909 ++__first1;
02910 ++__first2;
02911 }
02912 ++__result;
02913 }
02914 return copy(__first2, __last2, copy(__first1, __last1, __result));
02915 }
02916
02917 template <class _InputIter1, class _InputIter2, class _OutputIter,
02918 class _Compare>
02919 _OutputIter set_union(_InputIter1 __first1, _InputIter1 __last1,
02920 _InputIter2 __first2, _InputIter2 __last2,
02921 _OutputIter __result, _Compare __comp)
02922 {
02923
02924 __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>);
02925 __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>);
02926 __glibcpp_function_requires(_SameTypeConcept<
02927 typename iterator_traits<_InputIter1>::value_type,
02928 typename iterator_traits<_InputIter2>::value_type>);
02929 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
02930 typename iterator_traits<_InputIter1>::value_type>);
02931 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare,
02932 typename iterator_traits<_InputIter1>::value_type,
02933 typename iterator_traits<_InputIter2>::value_type>);
02934
02935 while (__first1 != __last1 && __first2 != __last2) {
02936 if (__comp(*__first1, *__first2)) {
02937 *__result = *__first1;
02938 ++__first1;
02939 }
02940 else if (__comp(*__first2, *__first1)) {
02941 *__result = *__first2;
02942 ++__first2;
02943 }
02944 else {
02945 *__result = *__first1;
02946 ++__first1;
02947 ++__first2;
02948 }
02949 ++__result;
02950 }
02951 return copy(__first2, __last2, copy(__first1, __last1, __result));
02952 }
02953
02954 template <class _InputIter1, class _InputIter2, class _OutputIter>
02955 _OutputIter set_intersection(_InputIter1 __first1, _InputIter1 __last1,
02956 _InputIter2 __first2, _InputIter2 __last2,
02957 _OutputIter __result)
02958 {
02959
02960 __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>);
02961 __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>);
02962 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
02963 typename iterator_traits<_InputIter1>::value_type>);
02964 __glibcpp_function_requires(_SameTypeConcept<
02965 typename iterator_traits<_InputIter1>::value_type,
02966 typename iterator_traits<_InputIter2>::value_type>);
02967 __glibcpp_function_requires(_LessThanComparableConcept<
02968 typename iterator_traits<_InputIter1>::value_type>);
02969
02970 while (__first1 != __last1 && __first2 != __last2)
02971 if (*__first1 < *__first2)
02972 ++__first1;
02973 else if (*__first2 < *__first1)
02974 ++__first2;
02975 else {
02976 *__result = *__first1;
02977 ++__first1;
02978 ++__first2;
02979 ++__result;
02980 }
02981 return __result;
02982 }
02983
02984 template <class _InputIter1, class _InputIter2, class _OutputIter,
02985 class _Compare>
02986 _OutputIter set_intersection(_InputIter1 __first1, _InputIter1 __last1,
02987 _InputIter2 __first2, _InputIter2 __last2,
02988 _OutputIter __result, _Compare __comp)
02989 {
02990
02991 __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>);
02992 __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>);
02993 __glibcpp_function_requires(_SameTypeConcept<
02994 typename iterator_traits<_InputIter1>::value_type,
02995 typename iterator_traits<_InputIter2>::value_type>);
02996 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
02997 typename iterator_traits<_InputIter1>::value_type>);
02998 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare,
02999 typename iterator_traits<_InputIter1>::value_type,
03000 typename iterator_traits<_InputIter2>::value_type>);
03001
03002 while (__first1 != __last1 && __first2 != __last2)
03003 if (__comp(*__first1, *__first2))
03004 ++__first1;
03005 else if (__comp(*__first2, *__first1))
03006 ++__first2;
03007 else {
03008 *__result = *__first1;
03009 ++__first1;
03010 ++__first2;
03011 ++__result;
03012 }
03013 return __result;
03014 }
03015
03016 template <class _InputIter1, class _InputIter2, class _OutputIter>
03017 _OutputIter set_difference(_InputIter1 __first1, _InputIter1 __last1,
03018 _InputIter2 __first2, _InputIter2 __last2,
03019 _OutputIter __result)
03020 {
03021
03022 __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>);
03023 __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>);
03024 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
03025 typename iterator_traits<_InputIter1>::value_type>);
03026 __glibcpp_function_requires(_SameTypeConcept<
03027 typename iterator_traits<_InputIter1>::value_type,
03028 typename iterator_traits<_InputIter2>::value_type>);
03029 __glibcpp_function_requires(_LessThanComparableConcept<
03030 typename iterator_traits<_InputIter1>::value_type>);
03031
03032 while (__first1 != __last1 && __first2 != __last2)
03033 if (*__first1 < *__first2) {
03034 *__result = *__first1;
03035 ++__first1;
03036 ++__result;
03037 }
03038 else if (*__first2 < *__first1)
03039 ++__first2;
03040 else {
03041 ++__first1;
03042 ++__first2;
03043 }
03044 return copy(__first1, __last1, __result);
03045 }
03046
03047 template <class _InputIter1, class _InputIter2, class _OutputIter,
03048 class _Compare>
03049 _OutputIter set_difference(_InputIter1 __first1, _InputIter1 __last1,
03050 _InputIter2 __first2, _InputIter2 __last2,
03051 _OutputIter __result, _Compare __comp)
03052 {
03053
03054 __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>);
03055 __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>);
03056 __glibcpp_function_requires(_SameTypeConcept<
03057 typename iterator_traits<_InputIter1>::value_type,
03058 typename iterator_traits<_InputIter2>::value_type>);
03059 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
03060 typename iterator_traits<_InputIter1>::value_type>);
03061 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare,
03062 typename iterator_traits<_InputIter1>::value_type,
03063 typename iterator_traits<_InputIter2>::value_type>);
03064
03065 while (__first1 != __last1 && __first2 != __last2)
03066 if (__comp(*__first1, *__first2)) {
03067 *__result = *__first1;
03068 ++__first1;
03069 ++__result;
03070 }
03071 else if (__comp(*__first2, *__first1))
03072 ++__first2;
03073 else {
03074 ++__first1;
03075 ++__first2;
03076 }
03077 return copy(__first1, __last1, __result);
03078 }
03079
03080 template <class _InputIter1, class _InputIter2, class _OutputIter>
03081 _OutputIter
03082 set_symmetric_difference(_InputIter1 __first1, _InputIter1 __last1,
03083 _InputIter2 __first2, _InputIter2 __last2,
03084 _OutputIter __result)
03085 {
03086
03087 __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>);
03088 __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>);
03089 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
03090 typename iterator_traits<_InputIter1>::value_type>);
03091 __glibcpp_function_requires(_SameTypeConcept<
03092 typename iterator_traits<_InputIter1>::value_type,
03093 typename iterator_traits<_InputIter2>::value_type>);
03094 __glibcpp_function_requires(_LessThanComparableConcept<
03095 typename iterator_traits<_InputIter1>::value_type>);
03096
03097 while (__first1 != __last1 && __first2 != __last2)
03098 if (*__first1 < *__first2) {
03099 *__result = *__first1;
03100 ++__first1;
03101 ++__result;
03102 }
03103 else if (*__first2 < *__first1) {
03104 *__result = *__first2;
03105 ++__first2;
03106 ++__result;
03107 }
03108 else {
03109 ++__first1;
03110 ++__first2;
03111 }
03112 return copy(__first2, __last2, copy(__first1, __last1, __result));
03113 }
03114
03115 template <class _InputIter1, class _InputIter2, class _OutputIter,
03116 class _Compare>
03117 _OutputIter
03118 set_symmetric_difference(_InputIter1 __first1, _InputIter1 __last1,
03119 _InputIter2 __first2, _InputIter2 __last2,
03120 _OutputIter __result,
03121 _Compare __comp)
03122 {
03123
03124 __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>);
03125 __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>);
03126 __glibcpp_function_requires(_SameTypeConcept<
03127 typename iterator_traits<_InputIter1>::value_type,
03128 typename iterator_traits<_InputIter2>::value_type>);
03129 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
03130 typename iterator_traits<_InputIter1>::value_type>);
03131 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare,
03132 typename iterator_traits<_InputIter1>::value_type,
03133 typename iterator_traits<_InputIter2>::value_type>);
03134
03135 while (__first1 != __last1 && __first2 != __last2)
03136 if (__comp(*__first1, *__first2)) {
03137 *__result = *__first1;
03138 ++__first1;
03139 ++__result;
03140 }
03141 else if (__comp(*__first2, *__first1)) {
03142 *__result = *__first2;
03143 ++__first2;
03144 ++__result;
03145 }
03146 else {
03147 ++__first1;
03148 ++__first2;
03149 }
03150 return copy(__first2, __last2, copy(__first1, __last1, __result));
03151 }
03152
03153
03154
03155
03156 template <class _ForwardIter>
03157 _ForwardIter max_element(_ForwardIter __first, _ForwardIter __last)
03158 {
03159
03160 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>);
03161 __glibcpp_function_requires(_LessThanComparableConcept<
03162 typename iterator_traits<_ForwardIter>::value_type>);
03163
03164 if (__first == __last) return __first;
03165 _ForwardIter __result = __first;
03166 while (++__first != __last)
03167 if (*__result < *__first)
03168 __result = __first;
03169 return __result;
03170 }
03171
03172 template <class _ForwardIter, class _Compare>
03173 _ForwardIter max_element(_ForwardIter __first, _ForwardIter __last,
03174 _Compare __comp)
03175 {
03176
03177 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>);
03178 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare,
03179 typename iterator_traits<_ForwardIter>::value_type,
03180 typename iterator_traits<_ForwardIter>::value_type>);
03181
03182 if (__first == __last) return __first;
03183 _ForwardIter __result = __first;
03184 while (++__first != __last)
03185 if (__comp(*__result, *__first)) __result = __first;
03186 return __result;
03187 }
03188
03189 template <class _ForwardIter>
03190 _ForwardIter min_element(_ForwardIter __first, _ForwardIter __last)
03191 {
03192
03193 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>);
03194 __glibcpp_function_requires(_LessThanComparableConcept<
03195 typename iterator_traits<_ForwardIter>::value_type>);
03196
03197 if (__first == __last) return __first;
03198 _ForwardIter __result = __first;
03199 while (++__first != __last)
03200 if (*__first < *__result)
03201 __result = __first;
03202 return __result;
03203 }
03204
03205 template <class _ForwardIter, class _Compare>
03206 _ForwardIter min_element(_ForwardIter __first, _ForwardIter __last,
03207 _Compare __comp)
03208 {
03209
03210 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>);
03211 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare,
03212 typename iterator_traits<_ForwardIter>::value_type,
03213 typename iterator_traits<_ForwardIter>::value_type>);
03214
03215 if (__first == __last) return __first;
03216 _ForwardIter __result = __first;
03217 while (++__first != __last)
03218 if (__comp(*__first, *__result))
03219 __result = __first;
03220 return __result;
03221 }
03222
03223
03224
03225
03226 template <class _BidirectionalIter>
03227 bool next_permutation(_BidirectionalIter __first, _BidirectionalIter __last)
03228 {
03229
03230 __glibcpp_function_requires(_BidirectionalIteratorConcept<_BidirectionalIter>);
03231 __glibcpp_function_requires(_LessThanComparableConcept<
03232 typename iterator_traits<_BidirectionalIter>::value_type>);
03233
03234 if (__first == __last)
03235 return false;
03236 _BidirectionalIter __i = __first;
03237 ++__i;
03238 if (__i == __last)
03239 return false;
03240 __i = __last;
03241 --__i;
03242
03243 for(;;) {
03244 _BidirectionalIter __ii = __i;
03245 --__i;
03246 if (*__i < *__ii) {
03247 _BidirectionalIter __j = __last;
03248 while (!(*__i < *--__j))
03249 {}
03250 iter_swap(__i, __j);
03251 reverse(__ii, __last);
03252 return true;
03253 }
03254 if (__i == __first) {
03255 reverse(__first, __last);
03256 return false;
03257 }
03258 }
03259 }
03260
03261 template <class _BidirectionalIter, class _Compare>
03262 bool next_permutation(_BidirectionalIter __first, _BidirectionalIter __last,
03263 _Compare __comp)
03264 {
03265
03266 __glibcpp_function_requires(_BidirectionalIteratorConcept<_BidirectionalIter>);
03267 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare,
03268 typename iterator_traits<_BidirectionalIter>::value_type,
03269 typename iterator_traits<_BidirectionalIter>::value_type>);
03270
03271 if (__first == __last)
03272 return false;
03273 _BidirectionalIter __i = __first;
03274 ++__i;
03275 if (__i == __last)
03276 return false;
03277 __i = __last;
03278 --__i;
03279
03280 for(;;) {
03281 _BidirectionalIter __ii = __i;
03282 --__i;
03283 if (__comp(*__i, *__ii)) {
03284 _BidirectionalIter __j = __last;
03285 while (!__comp(*__i, *--__j))
03286 {}
03287 iter_swap(__i, __j);
03288 reverse(__ii, __last);
03289 return true;
03290 }
03291 if (__i == __first) {
03292 reverse(__first, __last);
03293 return false;
03294 }
03295 }
03296 }
03297
03298 template <class _BidirectionalIter>
03299 bool prev_permutation(_BidirectionalIter __first, _BidirectionalIter __last)
03300 {
03301
03302 __glibcpp_function_requires(_BidirectionalIteratorConcept<_BidirectionalIter>);
03303 __glibcpp_function_requires(_LessThanComparableConcept<
03304 typename iterator_traits<_BidirectionalIter>::value_type>);
03305
03306 if (__first == __last)
03307 return false;
03308 _BidirectionalIter __i = __first;
03309 ++__i;
03310 if (__i == __last)
03311 return false;
03312 __i = __last;
03313 --__i;
03314
03315 for(;;) {
03316 _BidirectionalIter __ii = __i;
03317 --__i;
03318 if (*__ii < *__i) {
03319 _BidirectionalIter __j = __last;
03320 while (!(*--__j < *__i))
03321 {}
03322 iter_swap(__i, __j);
03323 reverse(__ii, __last);
03324 return true;
03325 }
03326 if (__i == __first) {
03327 reverse(__first, __last);
03328 return false;
03329 }
03330 }
03331 }
03332
03333 template <class _BidirectionalIter, class _Compare>
03334 bool prev_permutation(_BidirectionalIter __first, _BidirectionalIter __last,
03335 _Compare __comp)
03336 {
03337
03338 __glibcpp_function_requires(_BidirectionalIteratorConcept<_BidirectionalIter>);
03339 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare,
03340 typename iterator_traits<_BidirectionalIter>::value_type,
03341 typename iterator_traits<_BidirectionalIter>::value_type>);
03342
03343 if (__first == __last)
03344 return false;
03345 _BidirectionalIter __i = __first;
03346 ++__i;
03347 if (__i == __last)
03348 return false;
03349 __i = __last;
03350 --__i;
03351
03352 for(;;) {
03353 _BidirectionalIter __ii = __i;
03354 --__i;
03355 if (__comp(*__ii, *__i)) {
03356 _BidirectionalIter __j = __last;
03357 while (!__comp(*--__j, *__i))
03358 {}
03359 iter_swap(__i, __j);
03360 reverse(__ii, __last);
03361 return true;
03362 }
03363 if (__i == __first) {
03364 reverse(__first, __last);
03365 return false;
03366 }
03367 }
03368 }
03369
03370
03371
03372 template <class _InputIter, class _ForwardIter>
03373 _InputIter find_first_of(_InputIter __first1, _InputIter __last1,
03374 _ForwardIter __first2, _ForwardIter __last2)
03375 {
03376
03377 __glibcpp_function_requires(_InputIteratorConcept<_InputIter>);
03378 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>);
03379 __glibcpp_function_requires(_EqualOpConcept<
03380 typename iterator_traits<_InputIter>::value_type,
03381 typename iterator_traits<_ForwardIter>::value_type>);
03382
03383 for ( ; __first1 != __last1; ++__first1)
03384 for (_ForwardIter __iter = __first2; __iter != __last2; ++__iter)
03385 if (*__first1 == *__iter)
03386 return __first1;
03387 return __last1;
03388 }
03389
03390 template <class _InputIter, class _ForwardIter, class _BinaryPredicate>
03391 _InputIter find_first_of(_InputIter __first1, _InputIter __last1,
03392 _ForwardIter __first2, _ForwardIter __last2,
03393 _BinaryPredicate __comp)
03394 {
03395
03396 __glibcpp_function_requires(_InputIteratorConcept<_InputIter>);
03397 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>);
03398 __glibcpp_function_requires(_EqualOpConcept<
03399 typename iterator_traits<_InputIter>::value_type,
03400 typename iterator_traits<_ForwardIter>::value_type>);
03401 __glibcpp_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
03402 typename iterator_traits<_InputIter>::value_type,
03403 typename iterator_traits<_ForwardIter>::value_type>);
03404
03405 for ( ; __first1 != __last1; ++__first1)
03406 for (_ForwardIter __iter = __first2; __iter != __last2; ++__iter)
03407 if (__comp(*__first1, *__iter))
03408 return __first1;
03409 return __last1;
03410 }
03411
03412
03413
03414
03415
03416
03417
03418
03419 template <class _ForwardIter1, class _ForwardIter2>
03420 _ForwardIter1 __find_end(_ForwardIter1 __first1, _ForwardIter1 __last1,
03421 _ForwardIter2 __first2, _ForwardIter2 __last2,
03422 forward_iterator_tag, forward_iterator_tag)
03423 {
03424 if (__first2 == __last2)
03425 return __last1;
03426 else {
03427 _ForwardIter1 __result = __last1;
03428 while (1) {
03429 _ForwardIter1 __new_result
03430 = search(__first1, __last1, __first2, __last2);
03431 if (__new_result == __last1)
03432 return __result;
03433 else {
03434 __result = __new_result;
03435 __first1 = __new_result;
03436 ++__first1;
03437 }
03438 }
03439 }
03440 }
03441
03442 template <class _ForwardIter1, class _ForwardIter2,
03443 class _BinaryPredicate>
03444 _ForwardIter1 __find_end(_ForwardIter1 __first1, _ForwardIter1 __last1,
03445 _ForwardIter2 __first2, _ForwardIter2 __last2,
03446 forward_iterator_tag, forward_iterator_tag,
03447 _BinaryPredicate __comp)
03448 {
03449 if (__first2 == __last2)
03450 return __last1;
03451 else {
03452 _ForwardIter1 __result = __last1;
03453 while (1) {
03454 _ForwardIter1 __new_result
03455 = search(__first1, __last1, __first2, __last2, __comp);
03456 if (__new_result == __last1)
03457 return __result;
03458 else {
03459 __result = __new_result;
03460 __first1 = __new_result;
03461 ++__first1;
03462 }
03463 }
03464 }
03465 }
03466
03467
03468 template <class _BidirectionalIter1, class _BidirectionalIter2>
03469 _BidirectionalIter1
03470 __find_end(_BidirectionalIter1 __first1, _BidirectionalIter1 __last1,
03471 _BidirectionalIter2 __first2, _BidirectionalIter2 __last2,
03472 bidirectional_iterator_tag, bidirectional_iterator_tag)
03473 {
03474
03475 __glibcpp_function_requires(_BidirectionalIteratorConcept<_BidirectionalIter1>);
03476 __glibcpp_function_requires(_BidirectionalIteratorConcept<_BidirectionalIter2>);
03477
03478 typedef reverse_iterator<_BidirectionalIter1> _RevIter1;
03479 typedef reverse_iterator<_BidirectionalIter2> _RevIter2;
03480
03481 _RevIter1 __rlast1(__first1);
03482 _RevIter2 __rlast2(__first2);
03483 _RevIter1 __rresult = search(_RevIter1(__last1), __rlast1,
03484 _RevIter2(__last2), __rlast2);
03485
03486 if (__rresult == __rlast1)
03487 return __last1;
03488 else {
03489 _BidirectionalIter1 __result = __rresult.base();
03490 advance(__result, -distance(__first2, __last2));
03491 return __result;
03492 }
03493 }
03494
03495 template <class _BidirectionalIter1, class _BidirectionalIter2,
03496 class _BinaryPredicate>
03497 _BidirectionalIter1
03498 __find_end(_BidirectionalIter1 __first1, _BidirectionalIter1 __last1,
03499 _BidirectionalIter2 __first2, _BidirectionalIter2 __last2,
03500 bidirectional_iterator_tag, bidirectional_iterator_tag,
03501 _BinaryPredicate __comp)
03502 {
03503
03504 __glibcpp_function_requires(_BidirectionalIteratorConcept<_BidirectionalIter1>);
03505 __glibcpp_function_requires(_BidirectionalIteratorConcept<_BidirectionalIter2>);
03506
03507 typedef reverse_iterator<_BidirectionalIter1> _RevIter1;
03508 typedef reverse_iterator<_BidirectionalIter2> _RevIter2;
03509
03510 _RevIter1 __rlast1(__first1);
03511 _RevIter2 __rlast2(__first2);
03512 _RevIter1 __rresult = search(_RevIter1(__last1), __rlast1,
03513 _RevIter2(__last2), __rlast2,
03514 __comp);
03515
03516 if (__rresult == __rlast1)
03517 return __last1;
03518 else {
03519 _BidirectionalIter1 __result = __rresult.base();
03520 advance(__result, -distance(__first2, __last2));
03521 return __result;
03522 }
03523 }
03524
03525
03526
03527 template <class _ForwardIter1, class _ForwardIter2>
03528 inline _ForwardIter1
03529 find_end(_ForwardIter1 __first1, _ForwardIter1 __last1,
03530 _ForwardIter2 __first2, _ForwardIter2 __last2)
03531 {
03532
03533 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter1>);
03534 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter2>);
03535 __glibcpp_function_requires(_EqualOpConcept<
03536 typename iterator_traits<_ForwardIter1>::value_type,
03537 typename iterator_traits<_ForwardIter2>::value_type>);
03538
03539 return __find_end(__first1, __last1, __first2, __last2,
03540 __iterator_category(__first1),
03541 __iterator_category(__first2));
03542 }
03543
03544 template <class _ForwardIter1, class _ForwardIter2,
03545 class _BinaryPredicate>
03546 inline _ForwardIter1
03547 find_end(_ForwardIter1 __first1, _ForwardIter1 __last1,
03548 _ForwardIter2 __first2, _ForwardIter2 __last2,
03549 _BinaryPredicate __comp)
03550 {
03551
03552 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter1>);
03553 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter2>);
03554 __glibcpp_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
03555 typename iterator_traits<_ForwardIter1>::value_type,
03556 typename iterator_traits<_ForwardIter2>::value_type>);
03557
03558 return __find_end(__first1, __last1, __first2, __last2,
03559 __iterator_category(__first1),
03560 __iterator_category(__first2),
03561 __comp);
03562 }
03563
03564
03565
03566
03567
03568 template <class _RandomAccessIter, class _Distance>
03569 bool __is_heap(_RandomAccessIter __first, _Distance __n)
03570 {
03571 _Distance __parent = 0;
03572 for (_Distance __child = 1; __child < __n; ++__child) {
03573 if (__first[__parent] < __first[__child])
03574 return false;
03575 if ((__child & 1) == 0)
03576 ++__parent;
03577 }
03578 return true;
03579 }
03580
03581 template <class _RandomAccessIter, class _Distance, class _StrictWeakOrdering>
03582 bool __is_heap(_RandomAccessIter __first, _StrictWeakOrdering __comp,
03583 _Distance __n)
03584 {
03585 _Distance __parent = 0;
03586 for (_Distance __child = 1; __child < __n; ++__child) {
03587 if (__comp(__first[__parent], __first[__child]))
03588 return false;
03589 if ((__child & 1) == 0)
03590 ++__parent;
03591 }
03592 return true;
03593 }
03594
03595 template <class _RandomAccessIter>
03596 inline bool is_heap(_RandomAccessIter __first, _RandomAccessIter __last)
03597 {
03598
03599 __glibcpp_function_requires(_RandomAccessIteratorConcept<_RandomAccessIter>);
03600 __glibcpp_function_requires(_LessThanComparableConcept<
03601 typename iterator_traits<_RandomAccessIter>::value_type>);
03602
03603 return __is_heap(__first, __last - __first);
03604 }
03605
03606
03607 template <class _RandomAccessIter, class _StrictWeakOrdering>
03608 inline bool is_heap(_RandomAccessIter __first, _RandomAccessIter __last,
03609 _StrictWeakOrdering __comp)
03610 {
03611
03612 __glibcpp_function_requires(_RandomAccessIteratorConcept<_RandomAccessIter>);
03613 __glibcpp_function_requires(_BinaryPredicateConcept<_StrictWeakOrdering,
03614 typename iterator_traits<_RandomAccessIter>::value_type,
03615 typename iterator_traits<_RandomAccessIter>::value_type>);
03616
03617 return __is_heap(__first, __comp, __last - __first);
03618 }
03619
03620
03621
03622
03623
03624 template <class _ForwardIter>
03625 bool is_sorted(_ForwardIter __first, _ForwardIter __last)
03626 {
03627
03628 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>);
03629 __glibcpp_function_requires(_LessThanComparableConcept<
03630 typename iterator_traits<_ForwardIter>::value_type>);
03631
03632 if (__first == __last)
03633 return true;
03634
03635 _ForwardIter __next = __first;
03636 for (++__next; __next != __last; __first = __next, ++__next) {
03637 if (*__next < *__first)
03638 return false;
03639 }
03640
03641 return true;
03642 }
03643
03644 template <class _ForwardIter, class _StrictWeakOrdering>
03645 bool is_sorted(_ForwardIter __first, _ForwardIter __last,
03646 _StrictWeakOrdering __comp)
03647 {
03648
03649 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>);
03650 __glibcpp_function_requires(_BinaryPredicateConcept<_StrictWeakOrdering,
03651 typename iterator_traits<_ForwardIter>::value_type,
03652 typename iterator_traits<_ForwardIter>::value_type>);
03653
03654 if (__first == __last)
03655 return true;
03656
03657 _ForwardIter __next = __first;
03658 for (++__next; __next != __last; __first = __next, ++__next) {
03659 if (__comp(*__next, *__first))
03660 return false;
03661 }
03662
03663 return true;
03664 }
03665
03666 }
03667
03668 #endif
03669
03670
03671
03672