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 #ifndef _STL_ALGOBASE_H
00058 #define _STL_ALGOBASE_H 1
00059
00060 #include <bits/c++config.h>
00061 #include <bits/functexcept.h>
00062 #include <bits/cpp_type_traits.h>
00063 #include <ext/type_traits.h>
00064 #include <ext/numeric_traits.h>
00065 #include <bits/stl_pair.h>
00066 #include <bits/stl_iterator_base_types.h>
00067 #include <bits/stl_iterator_base_funcs.h>
00068 #include <bits/stl_iterator.h>
00069 #include <bits/concept_check.h>
00070 #include <debug/debug.h>
00071 #include <bits/move.h>
00072
00073 namespace std _GLIBCXX_VISIBILITY(default)
00074 {
00075 _GLIBCXX_BEGIN_NAMESPACE_VERSION
00076
00077
00078
00079
00080 template<bool _BoolType>
00081 struct __iter_swap
00082 {
00083 template<typename _ForwardIterator1, typename _ForwardIterator2>
00084 static void
00085 iter_swap(_ForwardIterator1 __a, _ForwardIterator2 __b)
00086 {
00087 typedef typename iterator_traits<_ForwardIterator1>::value_type
00088 _ValueType1;
00089 _ValueType1 __tmp = _GLIBCXX_MOVE(*__a);
00090 *__a = _GLIBCXX_MOVE(*__b);
00091 *__b = _GLIBCXX_MOVE(__tmp);
00092 }
00093 };
00094
00095 template<>
00096 struct __iter_swap<true>
00097 {
00098 template<typename _ForwardIterator1, typename _ForwardIterator2>
00099 static void
00100 iter_swap(_ForwardIterator1 __a, _ForwardIterator2 __b)
00101 {
00102 swap(*__a, *__b);
00103 }
00104 };
00105
00106
00107
00108
00109
00110
00111
00112
00113
00114
00115
00116 template<typename _ForwardIterator1, typename _ForwardIterator2>
00117 inline void
00118 iter_swap(_ForwardIterator1 __a, _ForwardIterator2 __b)
00119 {
00120 typedef typename iterator_traits<_ForwardIterator1>::value_type
00121 _ValueType1;
00122 typedef typename iterator_traits<_ForwardIterator2>::value_type
00123 _ValueType2;
00124
00125
00126 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
00127 _ForwardIterator1>)
00128 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
00129 _ForwardIterator2>)
00130 __glibcxx_function_requires(_ConvertibleConcept<_ValueType1,
00131 _ValueType2>)
00132 __glibcxx_function_requires(_ConvertibleConcept<_ValueType2,
00133 _ValueType1>)
00134
00135 typedef typename iterator_traits<_ForwardIterator1>::reference
00136 _ReferenceType1;
00137 typedef typename iterator_traits<_ForwardIterator2>::reference
00138 _ReferenceType2;
00139 std::__iter_swap<__are_same<_ValueType1, _ValueType2>::__value
00140 && __are_same<_ValueType1&, _ReferenceType1>::__value
00141 && __are_same<_ValueType2&, _ReferenceType2>::__value>::
00142 iter_swap(__a, __b);
00143 }
00144
00145
00146
00147
00148
00149
00150
00151
00152
00153
00154
00155
00156
00157 template<typename _ForwardIterator1, typename _ForwardIterator2>
00158 _ForwardIterator2
00159 swap_ranges(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
00160 _ForwardIterator2 __first2)
00161 {
00162
00163 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
00164 _ForwardIterator1>)
00165 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
00166 _ForwardIterator2>)
00167 __glibcxx_requires_valid_range(__first1, __last1);
00168
00169 for (; __first1 != __last1; ++__first1, ++__first2)
00170 std::iter_swap(__first1, __first2);
00171 return __first2;
00172 }
00173
00174
00175
00176
00177
00178
00179
00180
00181
00182
00183
00184
00185 template<typename _Tp>
00186 inline const _Tp&
00187 min(const _Tp& __a, const _Tp& __b)
00188 {
00189
00190 __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
00191
00192 if (__b < __a)
00193 return __b;
00194 return __a;
00195 }
00196
00197
00198
00199
00200
00201
00202
00203
00204
00205
00206
00207
00208 template<typename _Tp>
00209 inline const _Tp&
00210 max(const _Tp& __a, const _Tp& __b)
00211 {
00212
00213 __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
00214
00215 if (__a < __b)
00216 return __b;
00217 return __a;
00218 }
00219
00220
00221
00222
00223
00224
00225
00226
00227
00228
00229
00230
00231 template<typename _Tp, typename _Compare>
00232 inline const _Tp&
00233 min(const _Tp& __a, const _Tp& __b, _Compare __comp)
00234 {
00235
00236 if (__comp(__b, __a))
00237 return __b;
00238 return __a;
00239 }
00240
00241
00242
00243
00244
00245
00246
00247
00248
00249
00250
00251
00252 template<typename _Tp, typename _Compare>
00253 inline const _Tp&
00254 max(const _Tp& __a, const _Tp& __b, _Compare __comp)
00255 {
00256
00257 if (__comp(__a, __b))
00258 return __b;
00259 return __a;
00260 }
00261
00262
00263
00264 template<typename _Iterator>
00265 struct _Niter_base
00266 : _Iter_base<_Iterator, __is_normal_iterator<_Iterator>::__value>
00267 { };
00268
00269 template<typename _Iterator>
00270 inline typename _Niter_base<_Iterator>::iterator_type
00271 __niter_base(_Iterator __it)
00272 { return std::_Niter_base<_Iterator>::_S_base(__it); }
00273
00274
00275 template<typename _Iterator>
00276 struct _Miter_base
00277 : _Iter_base<_Iterator, __is_move_iterator<_Iterator>::__value>
00278 { };
00279
00280 template<typename _Iterator>
00281 inline typename _Miter_base<_Iterator>::iterator_type
00282 __miter_base(_Iterator __it)
00283 { return std::_Miter_base<_Iterator>::_S_base(__it); }
00284
00285
00286
00287
00288
00289
00290
00291 template<bool, bool, typename>
00292 struct __copy_move
00293 {
00294 template<typename _II, typename _OI>
00295 static _OI
00296 __copy_m(_II __first, _II __last, _OI __result)
00297 {
00298 for (; __first != __last; ++__result, ++__first)
00299 *__result = *__first;
00300 return __result;
00301 }
00302 };
00303
00304 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00305 template<typename _Category>
00306 struct __copy_move<true, false, _Category>
00307 {
00308 template<typename _II, typename _OI>
00309 static _OI
00310 __copy_m(_II __first, _II __last, _OI __result)
00311 {
00312 for (; __first != __last; ++__result, ++__first)
00313 *__result = std::move(*__first);
00314 return __result;
00315 }
00316 };
00317 #endif
00318
00319 template<>
00320 struct __copy_move<false, false, random_access_iterator_tag>
00321 {
00322 template<typename _II, typename _OI>
00323 static _OI
00324 __copy_m(_II __first, _II __last, _OI __result)
00325 {
00326 typedef typename iterator_traits<_II>::difference_type _Distance;
00327 for(_Distance __n = __last - __first; __n > 0; --__n)
00328 {
00329 *__result = *__first;
00330 ++__first;
00331 ++__result;
00332 }
00333 return __result;
00334 }
00335 };
00336
00337 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00338 template<>
00339 struct __copy_move<true, false, random_access_iterator_tag>
00340 {
00341 template<typename _II, typename _OI>
00342 static _OI
00343 __copy_m(_II __first, _II __last, _OI __result)
00344 {
00345 typedef typename iterator_traits<_II>::difference_type _Distance;
00346 for(_Distance __n = __last - __first; __n > 0; --__n)
00347 {
00348 *__result = std::move(*__first);
00349 ++__first;
00350 ++__result;
00351 }
00352 return __result;
00353 }
00354 };
00355 #endif
00356
00357 template<bool _IsMove>
00358 struct __copy_move<_IsMove, true, random_access_iterator_tag>
00359 {
00360 template<typename _Tp>
00361 static _Tp*
00362 __copy_m(const _Tp* __first, const _Tp* __last, _Tp* __result)
00363 {
00364 const ptrdiff_t _Num = __last - __first;
00365 if (_Num)
00366 __builtin_memmove(__result, __first, sizeof(_Tp) * _Num);
00367 return __result + _Num;
00368 }
00369 };
00370
00371 template<bool _IsMove, typename _II, typename _OI>
00372 inline _OI
00373 __copy_move_a(_II __first, _II __last, _OI __result)
00374 {
00375 typedef typename iterator_traits<_II>::value_type _ValueTypeI;
00376 typedef typename iterator_traits<_OI>::value_type _ValueTypeO;
00377 typedef typename iterator_traits<_II>::iterator_category _Category;
00378 const bool __simple = (__is_trivial(_ValueTypeI)
00379 && __is_pointer<_II>::__value
00380 && __is_pointer<_OI>::__value
00381 && __are_same<_ValueTypeI, _ValueTypeO>::__value);
00382
00383 return std::__copy_move<_IsMove, __simple,
00384 _Category>::__copy_m(__first, __last, __result);
00385 }
00386
00387
00388
00389 template<typename _CharT>
00390 struct char_traits;
00391
00392 template<typename _CharT, typename _Traits>
00393 class istreambuf_iterator;
00394
00395 template<typename _CharT, typename _Traits>
00396 class ostreambuf_iterator;
00397
00398 template<bool _IsMove, typename _CharT>
00399 typename __gnu_cxx::__enable_if<__is_char<_CharT>::__value,
00400 ostreambuf_iterator<_CharT, char_traits<_CharT> > >::__type
00401 __copy_move_a2(_CharT*, _CharT*,
00402 ostreambuf_iterator<_CharT, char_traits<_CharT> >);
00403
00404 template<bool _IsMove, typename _CharT>
00405 typename __gnu_cxx::__enable_if<__is_char<_CharT>::__value,
00406 ostreambuf_iterator<_CharT, char_traits<_CharT> > >::__type
00407 __copy_move_a2(const _CharT*, const _CharT*,
00408 ostreambuf_iterator<_CharT, char_traits<_CharT> >);
00409
00410 template<bool _IsMove, typename _CharT>
00411 typename __gnu_cxx::__enable_if<__is_char<_CharT>::__value,
00412 _CharT*>::__type
00413 __copy_move_a2(istreambuf_iterator<_CharT, char_traits<_CharT> >,
00414 istreambuf_iterator<_CharT, char_traits<_CharT> >, _CharT*);
00415
00416 template<bool _IsMove, typename _II, typename _OI>
00417 inline _OI
00418 __copy_move_a2(_II __first, _II __last, _OI __result)
00419 {
00420 return _OI(std::__copy_move_a<_IsMove>(std::__niter_base(__first),
00421 std::__niter_base(__last),
00422 std::__niter_base(__result)));
00423 }
00424
00425
00426
00427
00428
00429
00430
00431
00432
00433
00434
00435
00436
00437
00438
00439
00440
00441
00442 template<typename _II, typename _OI>
00443 inline _OI
00444 copy(_II __first, _II __last, _OI __result)
00445 {
00446
00447 __glibcxx_function_requires(_InputIteratorConcept<_II>)
00448 __glibcxx_function_requires(_OutputIteratorConcept<_OI,
00449 typename iterator_traits<_II>::value_type>)
00450 __glibcxx_requires_valid_range(__first, __last);
00451
00452 return (std::__copy_move_a2<__is_move_iterator<_II>::__value>
00453 (std::__miter_base(__first), std::__miter_base(__last),
00454 __result));
00455 }
00456
00457 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00458
00459
00460
00461
00462
00463
00464
00465
00466
00467
00468
00469
00470
00471
00472
00473
00474
00475 template<typename _II, typename _OI>
00476 inline _OI
00477 move(_II __first, _II __last, _OI __result)
00478 {
00479
00480 __glibcxx_function_requires(_InputIteratorConcept<_II>)
00481 __glibcxx_function_requires(_OutputIteratorConcept<_OI,
00482 typename iterator_traits<_II>::value_type>)
00483 __glibcxx_requires_valid_range(__first, __last);
00484
00485 return std::__copy_move_a2<true>(std::__miter_base(__first),
00486 std::__miter_base(__last), __result);
00487 }
00488
00489 #define _GLIBCXX_MOVE3(_Tp, _Up, _Vp) std::move(_Tp, _Up, _Vp)
00490 #else
00491 #define _GLIBCXX_MOVE3(_Tp, _Up, _Vp) std::copy(_Tp, _Up, _Vp)
00492 #endif
00493
00494 template<bool, bool, typename>
00495 struct __copy_move_backward
00496 {
00497 template<typename _BI1, typename _BI2>
00498 static _BI2
00499 __copy_move_b(_BI1 __first, _BI1 __last, _BI2 __result)
00500 {
00501 while (__first != __last)
00502 *--__result = *--__last;
00503 return __result;
00504 }
00505 };
00506
00507 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00508 template<typename _Category>
00509 struct __copy_move_backward<true, false, _Category>
00510 {
00511 template<typename _BI1, typename _BI2>
00512 static _BI2
00513 __copy_move_b(_BI1 __first, _BI1 __last, _BI2 __result)
00514 {
00515 while (__first != __last)
00516 *--__result = std::move(*--__last);
00517 return __result;
00518 }
00519 };
00520 #endif
00521
00522 template<>
00523 struct __copy_move_backward<false, false, random_access_iterator_tag>
00524 {
00525 template<typename _BI1, typename _BI2>
00526 static _BI2
00527 __copy_move_b(_BI1 __first, _BI1 __last, _BI2 __result)
00528 {
00529 typename iterator_traits<_BI1>::difference_type __n;
00530 for (__n = __last - __first; __n > 0; --__n)
00531 *--__result = *--__last;
00532 return __result;
00533 }
00534 };
00535
00536 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00537 template<>
00538 struct __copy_move_backward<true, false, random_access_iterator_tag>
00539 {
00540 template<typename _BI1, typename _BI2>
00541 static _BI2
00542 __copy_move_b(_BI1 __first, _BI1 __last, _BI2 __result)
00543 {
00544 typename iterator_traits<_BI1>::difference_type __n;
00545 for (__n = __last - __first; __n > 0; --__n)
00546 *--__result = std::move(*--__last);
00547 return __result;
00548 }
00549 };
00550 #endif
00551
00552 template<bool _IsMove>
00553 struct __copy_move_backward<_IsMove, true, random_access_iterator_tag>
00554 {
00555 template<typename _Tp>
00556 static _Tp*
00557 __copy_move_b(const _Tp* __first, const _Tp* __last, _Tp* __result)
00558 {
00559 const ptrdiff_t _Num = __last - __first;
00560 if (_Num)
00561 __builtin_memmove(__result - _Num, __first, sizeof(_Tp) * _Num);
00562 return __result - _Num;
00563 }
00564 };
00565
00566 template<bool _IsMove, typename _BI1, typename _BI2>
00567 inline _BI2
00568 __copy_move_backward_a(_BI1 __first, _BI1 __last, _BI2 __result)
00569 {
00570 typedef typename iterator_traits<_BI1>::value_type _ValueType1;
00571 typedef typename iterator_traits<_BI2>::value_type _ValueType2;
00572 typedef typename iterator_traits<_BI1>::iterator_category _Category;
00573 const bool __simple = (__is_trivial(_ValueType1)
00574 && __is_pointer<_BI1>::__value
00575 && __is_pointer<_BI2>::__value
00576 && __are_same<_ValueType1, _ValueType2>::__value);
00577
00578 return std::__copy_move_backward<_IsMove, __simple,
00579 _Category>::__copy_move_b(__first,
00580 __last,
00581 __result);
00582 }
00583
00584 template<bool _IsMove, typename _BI1, typename _BI2>
00585 inline _BI2
00586 __copy_move_backward_a2(_BI1 __first, _BI1 __last, _BI2 __result)
00587 {
00588 return _BI2(std::__copy_move_backward_a<_IsMove>
00589 (std::__niter_base(__first), std::__niter_base(__last),
00590 std::__niter_base(__result)));
00591 }
00592
00593
00594
00595
00596
00597
00598
00599
00600
00601
00602
00603
00604
00605
00606
00607
00608
00609
00610
00611 template<typename _BI1, typename _BI2>
00612 inline _BI2
00613 copy_backward(_BI1 __first, _BI1 __last, _BI2 __result)
00614 {
00615
00616 __glibcxx_function_requires(_BidirectionalIteratorConcept<_BI1>)
00617 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<_BI2>)
00618 __glibcxx_function_requires(_ConvertibleConcept<
00619 typename iterator_traits<_BI1>::value_type,
00620 typename iterator_traits<_BI2>::value_type>)
00621 __glibcxx_requires_valid_range(__first, __last);
00622
00623 return (std::__copy_move_backward_a2<__is_move_iterator<_BI1>::__value>
00624 (std::__miter_base(__first), std::__miter_base(__last),
00625 __result));
00626 }
00627
00628 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00629
00630
00631
00632
00633
00634
00635
00636
00637
00638
00639
00640
00641
00642
00643
00644
00645
00646
00647 template<typename _BI1, typename _BI2>
00648 inline _BI2
00649 move_backward(_BI1 __first, _BI1 __last, _BI2 __result)
00650 {
00651
00652 __glibcxx_function_requires(_BidirectionalIteratorConcept<_BI1>)
00653 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<_BI2>)
00654 __glibcxx_function_requires(_ConvertibleConcept<
00655 typename iterator_traits<_BI1>::value_type,
00656 typename iterator_traits<_BI2>::value_type>)
00657 __glibcxx_requires_valid_range(__first, __last);
00658
00659 return std::__copy_move_backward_a2<true>(std::__miter_base(__first),
00660 std::__miter_base(__last),
00661 __result);
00662 }
00663
00664 #define _GLIBCXX_MOVE_BACKWARD3(_Tp, _Up, _Vp) std::move_backward(_Tp, _Up, _Vp)
00665 #else
00666 #define _GLIBCXX_MOVE_BACKWARD3(_Tp, _Up, _Vp) std::copy_backward(_Tp, _Up, _Vp)
00667 #endif
00668
00669 template<typename _ForwardIterator, typename _Tp>
00670 inline typename
00671 __gnu_cxx::__enable_if<!__is_scalar<_Tp>::__value, void>::__type
00672 __fill_a(_ForwardIterator __first, _ForwardIterator __last,
00673 const _Tp& __value)
00674 {
00675 for (; __first != __last; ++__first)
00676 *__first = __value;
00677 }
00678
00679 template<typename _ForwardIterator, typename _Tp>
00680 inline typename
00681 __gnu_cxx::__enable_if<__is_scalar<_Tp>::__value, void>::__type
00682 __fill_a(_ForwardIterator __first, _ForwardIterator __last,
00683 const _Tp& __value)
00684 {
00685 const _Tp __tmp = __value;
00686 for (; __first != __last; ++__first)
00687 *__first = __tmp;
00688 }
00689
00690
00691 template<typename _Tp>
00692 inline typename
00693 __gnu_cxx::__enable_if<__is_byte<_Tp>::__value, void>::__type
00694 __fill_a(_Tp* __first, _Tp* __last, const _Tp& __c)
00695 {
00696 const _Tp __tmp = __c;
00697 __builtin_memset(__first, static_cast<unsigned char>(__tmp),
00698 __last - __first);
00699 }
00700
00701
00702
00703
00704
00705
00706
00707
00708
00709
00710
00711
00712
00713 template<typename _ForwardIterator, typename _Tp>
00714 inline void
00715 fill(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value)
00716 {
00717
00718 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
00719 _ForwardIterator>)
00720 __glibcxx_requires_valid_range(__first, __last);
00721
00722 std::__fill_a(std::__niter_base(__first), std::__niter_base(__last),
00723 __value);
00724 }
00725
00726 template<typename _OutputIterator, typename _Size, typename _Tp>
00727 inline typename
00728 __gnu_cxx::__enable_if<!__is_scalar<_Tp>::__value, _OutputIterator>::__type
00729 __fill_n_a(_OutputIterator __first, _Size __n, const _Tp& __value)
00730 {
00731 for (__decltype(__n + 0) __niter = __n;
00732 __niter > 0; --__niter, ++__first)
00733 *__first = __value;
00734 return __first;
00735 }
00736
00737 template<typename _OutputIterator, typename _Size, typename _Tp>
00738 inline typename
00739 __gnu_cxx::__enable_if<__is_scalar<_Tp>::__value, _OutputIterator>::__type
00740 __fill_n_a(_OutputIterator __first, _Size __n, const _Tp& __value)
00741 {
00742 const _Tp __tmp = __value;
00743 for (__decltype(__n + 0) __niter = __n;
00744 __niter > 0; --__niter, ++__first)
00745 *__first = __tmp;
00746 return __first;
00747 }
00748
00749 template<typename _Size, typename _Tp>
00750 inline typename
00751 __gnu_cxx::__enable_if<__is_byte<_Tp>::__value, _Tp*>::__type
00752 __fill_n_a(_Tp* __first, _Size __n, const _Tp& __c)
00753 {
00754 std::__fill_a(__first, __first + __n, __c);
00755 return __first + __n;
00756 }
00757
00758
00759
00760
00761
00762
00763
00764
00765
00766
00767
00768
00769
00770
00771
00772
00773 template<typename _OI, typename _Size, typename _Tp>
00774 inline _OI
00775 fill_n(_OI __first, _Size __n, const _Tp& __value)
00776 {
00777
00778 __glibcxx_function_requires(_OutputIteratorConcept<_OI, _Tp>)
00779
00780 return _OI(std::__fill_n_a(std::__niter_base(__first), __n, __value));
00781 }
00782
00783 template<bool _BoolType>
00784 struct __equal
00785 {
00786 template<typename _II1, typename _II2>
00787 static bool
00788 equal(_II1 __first1, _II1 __last1, _II2 __first2)
00789 {
00790 for (; __first1 != __last1; ++__first1, ++__first2)
00791 if (!(*__first1 == *__first2))
00792 return false;
00793 return true;
00794 }
00795 };
00796
00797 template<>
00798 struct __equal<true>
00799 {
00800 template<typename _Tp>
00801 static bool
00802 equal(const _Tp* __first1, const _Tp* __last1, const _Tp* __first2)
00803 {
00804 return !__builtin_memcmp(__first1, __first2, sizeof(_Tp)
00805 * (__last1 - __first1));
00806 }
00807 };
00808
00809 template<typename _II1, typename _II2>
00810 inline bool
00811 __equal_aux(_II1 __first1, _II1 __last1, _II2 __first2)
00812 {
00813 typedef typename iterator_traits<_II1>::value_type _ValueType1;
00814 typedef typename iterator_traits<_II2>::value_type _ValueType2;
00815 const bool __simple = (__is_integer<_ValueType1>::__value
00816 && __is_pointer<_II1>::__value
00817 && __is_pointer<_II2>::__value
00818 && __are_same<_ValueType1, _ValueType2>::__value);
00819
00820 return std::__equal<__simple>::equal(__first1, __last1, __first2);
00821 }
00822
00823
00824 template<typename, typename>
00825 struct __lc_rai
00826 {
00827 template<typename _II1, typename _II2>
00828 static _II1
00829 __newlast1(_II1, _II1 __last1, _II2, _II2)
00830 { return __last1; }
00831
00832 template<typename _II>
00833 static bool
00834 __cnd2(_II __first, _II __last)
00835 { return __first != __last; }
00836 };
00837
00838 template<>
00839 struct __lc_rai<random_access_iterator_tag, random_access_iterator_tag>
00840 {
00841 template<typename _RAI1, typename _RAI2>
00842 static _RAI1
00843 __newlast1(_RAI1 __first1, _RAI1 __last1,
00844 _RAI2 __first2, _RAI2 __last2)
00845 {
00846 const typename iterator_traits<_RAI1>::difference_type
00847 __diff1 = __last1 - __first1;
00848 const typename iterator_traits<_RAI2>::difference_type
00849 __diff2 = __last2 - __first2;
00850 return __diff2 < __diff1 ? __first1 + __diff2 : __last1;
00851 }
00852
00853 template<typename _RAI>
00854 static bool
00855 __cnd2(_RAI, _RAI)
00856 { return true; }
00857 };
00858
00859 template<bool _BoolType>
00860 struct __lexicographical_compare
00861 {
00862 template<typename _II1, typename _II2>
00863 static bool __lc(_II1, _II1, _II2, _II2);
00864 };
00865
00866 template<bool _BoolType>
00867 template<typename _II1, typename _II2>
00868 bool
00869 __lexicographical_compare<_BoolType>::
00870 __lc(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2)
00871 {
00872 typedef typename iterator_traits<_II1>::iterator_category _Category1;
00873 typedef typename iterator_traits<_II2>::iterator_category _Category2;
00874 typedef std::__lc_rai<_Category1, _Category2> __rai_type;
00875
00876 __last1 = __rai_type::__newlast1(__first1, __last1,
00877 __first2, __last2);
00878 for (; __first1 != __last1 && __rai_type::__cnd2(__first2, __last2);
00879 ++__first1, ++__first2)
00880 {
00881 if (*__first1 < *__first2)
00882 return true;
00883 if (*__first2 < *__first1)
00884 return false;
00885 }
00886 return __first1 == __last1 && __first2 != __last2;
00887 }
00888
00889 template<>
00890 struct __lexicographical_compare<true>
00891 {
00892 template<typename _Tp, typename _Up>
00893 static bool
00894 __lc(const _Tp* __first1, const _Tp* __last1,
00895 const _Up* __first2, const _Up* __last2)
00896 {
00897 const size_t __len1 = __last1 - __first1;
00898 const size_t __len2 = __last2 - __first2;
00899 const int __result = __builtin_memcmp(__first1, __first2,
00900 std::min(__len1, __len2));
00901 return __result != 0 ? __result < 0 : __len1 < __len2;
00902 }
00903 };
00904
00905 template<typename _II1, typename _II2>
00906 inline bool
00907 __lexicographical_compare_aux(_II1 __first1, _II1 __last1,
00908 _II2 __first2, _II2 __last2)
00909 {
00910 typedef typename iterator_traits<_II1>::value_type _ValueType1;
00911 typedef typename iterator_traits<_II2>::value_type _ValueType2;
00912 const bool __simple =
00913 (__is_byte<_ValueType1>::__value && __is_byte<_ValueType2>::__value
00914 && !__gnu_cxx::__numeric_traits<_ValueType1>::__is_signed
00915 && !__gnu_cxx::__numeric_traits<_ValueType2>::__is_signed
00916 && __is_pointer<_II1>::__value
00917 && __is_pointer<_II2>::__value);
00918
00919 return std::__lexicographical_compare<__simple>::__lc(__first1, __last1,
00920 __first2, __last2);
00921 }
00922
00923
00924
00925
00926
00927
00928
00929
00930
00931
00932
00933
00934 template<typename _ForwardIterator, typename _Tp>
00935 _ForwardIterator
00936 lower_bound(_ForwardIterator __first, _ForwardIterator __last,
00937 const _Tp& __val)
00938 {
00939 typedef typename iterator_traits<_ForwardIterator>::value_type
00940 _ValueType;
00941 typedef typename iterator_traits<_ForwardIterator>::difference_type
00942 _DistanceType;
00943
00944
00945 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
00946 __glibcxx_function_requires(_LessThanOpConcept<_ValueType, _Tp>)
00947 __glibcxx_requires_partitioned_lower(__first, __last, __val);
00948
00949 _DistanceType __len = std::distance(__first, __last);
00950
00951 while (__len > 0)
00952 {
00953 _DistanceType __half = __len >> 1;
00954 _ForwardIterator __middle = __first;
00955 std::advance(__middle, __half);
00956 if (*__middle < __val)
00957 {
00958 __first = __middle;
00959 ++__first;
00960 __len = __len - __half - 1;
00961 }
00962 else
00963 __len = __half;
00964 }
00965 return __first;
00966 }
00967
00968
00969
00970 template<typename _Size>
00971 inline _Size
00972 __lg(_Size __n)
00973 {
00974 _Size __k;
00975 for (__k = 0; __n != 0; __n >>= 1)
00976 ++__k;
00977 return __k - 1;
00978 }
00979
00980 inline int
00981 __lg(int __n)
00982 { return sizeof(int) * __CHAR_BIT__ - 1 - __builtin_clz(__n); }
00983
00984 inline long
00985 __lg(long __n)
00986 { return sizeof(long) * __CHAR_BIT__ - 1 - __builtin_clzl(__n); }
00987
00988 inline long long
00989 __lg(long long __n)
00990 { return sizeof(long long) * __CHAR_BIT__ - 1 - __builtin_clzll(__n); }
00991
00992 _GLIBCXX_END_NAMESPACE_VERSION
00993
00994 _GLIBCXX_BEGIN_NAMESPACE_ALGO
00995
00996
00997
00998
00999
01000
01001
01002
01003
01004
01005
01006
01007
01008 template<typename _II1, typename _II2>
01009 inline bool
01010 equal(_II1 __first1, _II1 __last1, _II2 __first2)
01011 {
01012
01013 __glibcxx_function_requires(_InputIteratorConcept<_II1>)
01014 __glibcxx_function_requires(_InputIteratorConcept<_II2>)
01015 __glibcxx_function_requires(_EqualOpConcept<
01016 typename iterator_traits<_II1>::value_type,
01017 typename iterator_traits<_II2>::value_type>)
01018 __glibcxx_requires_valid_range(__first1, __last1);
01019
01020 return std::__equal_aux(std::__niter_base(__first1),
01021 std::__niter_base(__last1),
01022 std::__niter_base(__first2));
01023 }
01024
01025
01026
01027
01028
01029
01030
01031
01032
01033
01034
01035
01036
01037
01038
01039
01040 template<typename _IIter1, typename _IIter2, typename _BinaryPredicate>
01041 inline bool
01042 equal(_IIter1 __first1, _IIter1 __last1,
01043 _IIter2 __first2, _BinaryPredicate __binary_pred)
01044 {
01045
01046 __glibcxx_function_requires(_InputIteratorConcept<_IIter1>)
01047 __glibcxx_function_requires(_InputIteratorConcept<_IIter2>)
01048 __glibcxx_requires_valid_range(__first1, __last1);
01049
01050 for (; __first1 != __last1; ++__first1, ++__first2)
01051 if (!bool(__binary_pred(*__first1, *__first2)))
01052 return false;
01053 return true;
01054 }
01055
01056
01057
01058
01059
01060
01061
01062
01063
01064
01065
01066
01067
01068
01069
01070
01071 template<typename _II1, typename _II2>
01072 inline bool
01073 lexicographical_compare(_II1 __first1, _II1 __last1,
01074 _II2 __first2, _II2 __last2)
01075 {
01076
01077 typedef typename iterator_traits<_II1>::value_type _ValueType1;
01078 typedef typename iterator_traits<_II2>::value_type _ValueType2;
01079 __glibcxx_function_requires(_InputIteratorConcept<_II1>)
01080 __glibcxx_function_requires(_InputIteratorConcept<_II2>)
01081 __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
01082 __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
01083 __glibcxx_requires_valid_range(__first1, __last1);
01084 __glibcxx_requires_valid_range(__first2, __last2);
01085
01086 return std::__lexicographical_compare_aux(std::__niter_base(__first1),
01087 std::__niter_base(__last1),
01088 std::__niter_base(__first2),
01089 std::__niter_base(__last2));
01090 }
01091
01092
01093
01094
01095
01096
01097
01098
01099
01100
01101
01102
01103
01104
01105 template<typename _II1, typename _II2, typename _Compare>
01106 bool
01107 lexicographical_compare(_II1 __first1, _II1 __last1,
01108 _II2 __first2, _II2 __last2, _Compare __comp)
01109 {
01110 typedef typename iterator_traits<_II1>::iterator_category _Category1;
01111 typedef typename iterator_traits<_II2>::iterator_category _Category2;
01112 typedef std::__lc_rai<_Category1, _Category2> __rai_type;
01113
01114
01115 __glibcxx_function_requires(_InputIteratorConcept<_II1>)
01116 __glibcxx_function_requires(_InputIteratorConcept<_II2>)
01117 __glibcxx_requires_valid_range(__first1, __last1);
01118 __glibcxx_requires_valid_range(__first2, __last2);
01119
01120 __last1 = __rai_type::__newlast1(__first1, __last1, __first2, __last2);
01121 for (; __first1 != __last1 && __rai_type::__cnd2(__first2, __last2);
01122 ++__first1, ++__first2)
01123 {
01124 if (__comp(*__first1, *__first2))
01125 return true;
01126 if (__comp(*__first2, *__first1))
01127 return false;
01128 }
01129 return __first1 == __last1 && __first2 != __last2;
01130 }
01131
01132
01133
01134
01135
01136
01137
01138
01139
01140
01141
01142
01143
01144
01145 template<typename _InputIterator1, typename _InputIterator2>
01146 pair<_InputIterator1, _InputIterator2>
01147 mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
01148 _InputIterator2 __first2)
01149 {
01150
01151 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
01152 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
01153 __glibcxx_function_requires(_EqualOpConcept<
01154 typename iterator_traits<_InputIterator1>::value_type,
01155 typename iterator_traits<_InputIterator2>::value_type>)
01156 __glibcxx_requires_valid_range(__first1, __last1);
01157
01158 while (__first1 != __last1 && *__first1 == *__first2)
01159 {
01160 ++__first1;
01161 ++__first2;
01162 }
01163 return pair<_InputIterator1, _InputIterator2>(__first1, __first2);
01164 }
01165
01166
01167
01168
01169
01170
01171
01172
01173
01174
01175
01176
01177
01178
01179
01180
01181
01182 template<typename _InputIterator1, typename _InputIterator2,
01183 typename _BinaryPredicate>
01184 pair<_InputIterator1, _InputIterator2>
01185 mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
01186 _InputIterator2 __first2, _BinaryPredicate __binary_pred)
01187 {
01188
01189 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
01190 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
01191 __glibcxx_requires_valid_range(__first1, __last1);
01192
01193 while (__first1 != __last1 && bool(__binary_pred(*__first1, *__first2)))
01194 {
01195 ++__first1;
01196 ++__first2;
01197 }
01198 return pair<_InputIterator1, _InputIterator2>(__first1, __first2);
01199 }
01200
01201 _GLIBCXX_END_NAMESPACE_ALGO
01202 }
01203
01204
01205
01206
01207 #ifdef _GLIBCXX_PARALLEL
01208 # include <parallel/algobase.h>
01209 #endif
01210
01211 #endif