00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040
00041
00042
00043
00044
00045
00046
00047
00048
00049
00050
00051
00052
00053
00054
00055
00056
00057
00058
00059
00060
00061 #ifndef __GLIBCPP_INTERNAL_ALGOBASE_H
00062 #define __GLIBCPP_INTERNAL_ALGOBASE_H
00063
00064 #include <bits/c++config.h>
00065 #include <cstring>
00066 #include <climits>
00067 #include <cstdlib>
00068 #include <cstddef>
00069 #include <new>
00070 #include <iosfwd>
00071 #include <bits/stl_pair.h>
00072 #include <bits/type_traits.h>
00073 #include <bits/stl_iterator_base_types.h>
00074 #include <bits/stl_iterator_base_funcs.h>
00075 #include <bits/stl_iterator.h>
00076 #include <bits/concept_check.h>
00077
00078 namespace std
00079 {
00080
00081
00082
00083
00084
00085
00086
00087
00088
00089
00090
00091 template<typename _ForwardIter1, typename _ForwardIter2>
00092 inline void
00093 iter_swap(_ForwardIter1 __a, _ForwardIter2 __b)
00094 {
00095 typedef typename iterator_traits<_ForwardIter1>::value_type _ValueType1;
00096 typedef typename iterator_traits<_ForwardIter2>::value_type _ValueType2;
00097
00098
00099 __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter1>)
00100 __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter2>)
00101 __glibcpp_function_requires(_ConvertibleConcept<_ValueType1, _ValueType2>)
00102 __glibcpp_function_requires(_ConvertibleConcept<_ValueType2, _ValueType1>)
00103
00104 _ValueType1 __tmp = *__a;
00105 *__a = *__b;
00106 *__b = __tmp;
00107 }
00108
00109
00110
00111
00112
00113
00114
00115
00116
00117
00118 template<typename _Tp>
00119 inline void
00120 swap(_Tp& __a, _Tp& __b)
00121 {
00122
00123 __glibcpp_function_requires(_SGIAssignableConcept<_Tp>)
00124
00125 _Tp __tmp = __a;
00126 __a = __b;
00127 __b = __tmp;
00128 }
00129
00130
00131
00132
00133 #undef min
00134 #undef max
00135
00136
00137
00138
00139
00140
00141
00142
00143
00144
00145
00146 template<typename _Tp>
00147 inline const _Tp&
00148 min(const _Tp& __a, const _Tp& __b)
00149 {
00150
00151 __glibcpp_function_requires(_LessThanComparableConcept<_Tp>)
00152
00153 if (__b < __a) return __b; return __a;
00154 }
00155
00156
00157
00158
00159
00160
00161
00162
00163
00164
00165
00166 template<typename _Tp>
00167 inline const _Tp&
00168 max(const _Tp& __a, const _Tp& __b)
00169 {
00170
00171 __glibcpp_function_requires(_LessThanComparableConcept<_Tp>)
00172
00173 if (__a < __b) return __b; return __a;
00174 }
00175
00176
00177
00178
00179
00180
00181
00182
00183
00184
00185
00186 template<typename _Tp, typename _Compare>
00187 inline const _Tp&
00188 min(const _Tp& __a, const _Tp& __b, _Compare __comp)
00189 {
00190
00191 if (__comp(__b, __a)) return __b; return __a;
00192 }
00193
00194
00195
00196
00197
00198
00199
00200
00201
00202
00203
00204 template<typename _Tp, typename _Compare>
00205 inline const _Tp&
00206 max(const _Tp& __a, const _Tp& __b, _Compare __comp)
00207 {
00208
00209 if (__comp(__a, __b)) return __b; return __a;
00210 }
00211
00212
00213
00214
00215
00216
00217
00218
00219
00220
00221 template<typename _InputIter, typename _OutputIter>
00222 inline _OutputIter
00223 __copy(_InputIter __first, _InputIter __last,
00224 _OutputIter __result,
00225 input_iterator_tag)
00226 {
00227 for ( ; __first != __last; ++__result, ++__first)
00228 *__result = *__first;
00229 return __result;
00230 }
00231
00232 template<typename _RandomAccessIter, typename _OutputIter>
00233 inline _OutputIter
00234 __copy(_RandomAccessIter __first, _RandomAccessIter __last,
00235 _OutputIter __result,
00236 random_access_iterator_tag)
00237 {
00238 typedef typename iterator_traits<_RandomAccessIter>::difference_type
00239 _Distance;
00240 for (_Distance __n = __last - __first; __n > 0; --__n) {
00241 *__result = *__first;
00242 ++__first;
00243 ++__result;
00244 }
00245 return __result;
00246 }
00247
00248 template<typename _Tp>
00249 inline _Tp*
00250 __copy_trivial(const _Tp* __first, const _Tp* __last, _Tp* __result)
00251 {
00252 memmove(__result, __first, sizeof(_Tp) * (__last - __first));
00253 return __result + (__last - __first);
00254 }
00255
00256 template<typename _InputIter, typename _OutputIter>
00257 inline _OutputIter
00258 __copy_aux2(_InputIter __first, _InputIter __last,
00259 _OutputIter __result, __false_type)
00260 { return __copy(__first, __last, __result, __iterator_category(__first)); }
00261
00262 template<typename _InputIter, typename _OutputIter>
00263 inline _OutputIter
00264 __copy_aux2(_InputIter __first, _InputIter __last,
00265 _OutputIter __result, __true_type)
00266 { return __copy(__first, __last, __result, __iterator_category(__first)); }
00267
00268 template<typename _Tp>
00269 inline _Tp*
00270 __copy_aux2(_Tp* __first, _Tp* __last,
00271 _Tp* __result, __true_type)
00272 { return __copy_trivial(__first, __last, __result); }
00273
00274 template<typename _Tp>
00275 inline _Tp*
00276 __copy_aux2(const _Tp* __first, const _Tp* __last,
00277 _Tp* __result, __true_type)
00278 { return __copy_trivial(__first, __last, __result); }
00279
00280 template<typename _InputIter, typename _OutputIter>
00281 inline _OutputIter
00282 __copy_ni2(_InputIter __first, _InputIter __last,
00283 _OutputIter __result, __true_type)
00284 {
00285 typedef typename iterator_traits<_InputIter>::value_type
00286 _ValueType;
00287 typedef typename __type_traits<_ValueType>::has_trivial_assignment_operator
00288 _Trivial;
00289 return _OutputIter(__copy_aux2(__first, __last,
00290 __result.base(),
00291 _Trivial()));
00292 }
00293
00294 template<typename _InputIter, typename _OutputIter>
00295 inline _OutputIter
00296 __copy_ni2(_InputIter __first, _InputIter __last,
00297 _OutputIter __result, __false_type)
00298 {
00299 typedef typename iterator_traits<_InputIter>::value_type
00300 _ValueType;
00301 typedef typename __type_traits<_ValueType>::has_trivial_assignment_operator
00302 _Trivial;
00303 return __copy_aux2(__first, __last,
00304 __result,
00305 _Trivial());
00306 }
00307
00308 template<typename _InputIter, typename _OutputIter>
00309 inline _OutputIter
00310 __copy_ni1(_InputIter __first, _InputIter __last,
00311 _OutputIter __result, __true_type)
00312 {
00313 typedef typename _Is_normal_iterator<_OutputIter>::_Normal __Normal;
00314 return __copy_ni2(__first.base(), __last.base(), __result, __Normal());
00315 }
00316
00317 template<typename _InputIter, typename _OutputIter>
00318 inline _OutputIter
00319 __copy_ni1(_InputIter __first, _InputIter __last,
00320 _OutputIter __result, __false_type)
00321 {
00322 typedef typename _Is_normal_iterator<_OutputIter>::_Normal __Normal;
00323 return __copy_ni2(__first, __last, __result, __Normal());
00324 }
00325
00326
00327
00328
00329
00330
00331
00332
00333
00334
00335
00336
00337
00338
00339 template<typename _InputIter, typename _OutputIter>
00340 inline _OutputIter
00341 copy(_InputIter __first, _InputIter __last, _OutputIter __result)
00342 {
00343
00344 __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
00345 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
00346 typename iterator_traits<_InputIter>::value_type>)
00347
00348 typedef typename _Is_normal_iterator<_InputIter>::_Normal __Normal;
00349 return __copy_ni1(__first, __last, __result, __Normal());
00350 }
00351
00352
00353
00354
00355 template<typename _BidirectionalIter1, typename _BidirectionalIter2>
00356 inline _BidirectionalIter2
00357 __copy_backward(_BidirectionalIter1 __first, _BidirectionalIter1 __last,
00358 _BidirectionalIter2 __result,
00359 bidirectional_iterator_tag)
00360 {
00361 while (__first != __last)
00362 *--__result = *--__last;
00363 return __result;
00364 }
00365
00366 template<typename _RandomAccessIter, typename _BidirectionalIter>
00367 inline _BidirectionalIter
00368 __copy_backward(_RandomAccessIter __first, _RandomAccessIter __last,
00369 _BidirectionalIter __result,
00370 random_access_iterator_tag)
00371 {
00372 typename iterator_traits<_RandomAccessIter>::difference_type __n;
00373 for (__n = __last - __first; __n > 0; --__n)
00374 *--__result = *--__last;
00375 return __result;
00376 }
00377
00378
00379
00380
00381
00382
00383
00384 template<typename _BidirectionalIter1, typename _BidirectionalIter2,
00385 typename _BoolType>
00386 struct __copy_backward_dispatch
00387 {
00388 static _BidirectionalIter2
00389 copy(_BidirectionalIter1 __first, _BidirectionalIter1 __last,
00390 _BidirectionalIter2 __result)
00391 {
00392 return __copy_backward(__first, __last,
00393 __result,
00394 __iterator_category(__first));
00395 }
00396 };
00397
00398 template<typename _Tp>
00399 struct __copy_backward_dispatch<_Tp*, _Tp*, __true_type>
00400 {
00401 static _Tp*
00402 copy(const _Tp* __first, const _Tp* __last, _Tp* __result)
00403 {
00404 const ptrdiff_t _Num = __last - __first;
00405 memmove(__result - _Num, __first, sizeof(_Tp) * _Num);
00406 return __result - _Num;
00407 }
00408 };
00409
00410 template<typename _Tp>
00411 struct __copy_backward_dispatch<const _Tp*, _Tp*, __true_type>
00412 {
00413 static _Tp*
00414 copy(const _Tp* __first, const _Tp* __last, _Tp* __result)
00415 {
00416 return __copy_backward_dispatch<_Tp*, _Tp*, __true_type>
00417 ::copy(__first, __last, __result);
00418 }
00419 };
00420
00421 template<typename _BI1, typename _BI2>
00422 inline _BI2
00423 __copy_backward_aux(_BI1 __first, _BI1 __last, _BI2 __result)
00424 {
00425 typedef typename __type_traits<typename iterator_traits<_BI2>::value_type>
00426 ::has_trivial_assignment_operator _Trivial;
00427 return __copy_backward_dispatch<_BI1, _BI2, _Trivial>
00428 ::copy(__first, __last, __result);
00429 }
00430
00431 template <typename _BI1, typename _BI2>
00432 inline _BI2
00433 __copy_backward_output_normal_iterator(_BI1 __first, _BI1 __last,
00434 _BI2 __result, __true_type)
00435 { return _BI2(__copy_backward_aux(__first, __last, __result.base())); }
00436
00437 template <typename _BI1, typename _BI2>
00438 inline _BI2
00439 __copy_backward_output_normal_iterator(_BI1 __first, _BI1 __last,
00440 _BI2 __result, __false_type)
00441 { return __copy_backward_aux(__first, __last, __result); }
00442
00443 template <typename _BI1, typename _BI2>
00444 inline _BI2
00445 __copy_backward_input_normal_iterator(_BI1 __first, _BI1 __last,
00446 _BI2 __result, __true_type)
00447 {
00448 typedef typename _Is_normal_iterator<_BI2>::_Normal __Normal;
00449 return __copy_backward_output_normal_iterator(__first.base(), __last.base(),
00450 __result, __Normal());
00451 }
00452
00453 template <typename _BI1, typename _BI2>
00454 inline _BI2
00455 __copy_backward_input_normal_iterator(_BI1 __first, _BI1 __last,
00456 _BI2 __result, __false_type)
00457 {
00458 typedef typename _Is_normal_iterator<_BI2>::_Normal __Normal;
00459 return __copy_backward_output_normal_iterator(__first, __last, __result,
00460 __Normal());
00461 }
00462
00463
00464
00465
00466
00467
00468
00469
00470
00471
00472
00473
00474
00475
00476
00477 template <typename _BI1, typename _BI2>
00478 inline _BI2
00479 copy_backward(_BI1 __first, _BI1 __last, _BI2 __result)
00480 {
00481
00482 __glibcpp_function_requires(_BidirectionalIteratorConcept<_BI1>)
00483 __glibcpp_function_requires(_Mutable_BidirectionalIteratorConcept<_BI2>)
00484 __glibcpp_function_requires(_ConvertibleConcept<
00485 typename iterator_traits<_BI1>::value_type,
00486 typename iterator_traits<_BI2>::value_type>)
00487
00488 typedef typename _Is_normal_iterator<_BI1>::_Normal __Normal;
00489 return __copy_backward_input_normal_iterator(__first, __last, __result,
00490 __Normal());
00491 }
00492
00493
00494
00495
00496
00497
00498
00499
00500
00501
00502
00503
00504
00505
00506
00507
00508
00509 template<typename _ForwardIter, typename _Tp>
00510 void
00511 fill(_ForwardIter __first, _ForwardIter __last, const _Tp& __value)
00512 {
00513
00514 __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter>)
00515
00516 for ( ; __first != __last; ++__first)
00517 *__first = __value;
00518 }
00519
00520
00521
00522
00523
00524
00525
00526
00527
00528
00529
00530
00531 template<typename _OutputIter, typename _Size, typename _Tp>
00532 _OutputIter
00533 fill_n(_OutputIter __first, _Size __n, const _Tp& __value)
00534 {
00535
00536 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,_Tp>)
00537
00538 for ( ; __n > 0; --__n, ++__first)
00539 *__first = __value;
00540 return __first;
00541 }
00542
00543
00544
00545 inline void
00546 fill(unsigned char* __first, unsigned char* __last, const unsigned char& __c)
00547 {
00548 unsigned char __tmp = __c;
00549 memset(__first, __tmp, __last - __first);
00550 }
00551
00552 inline void
00553 fill(signed char* __first, signed char* __last, const signed char& __c)
00554 {
00555 signed char __tmp = __c;
00556 memset(__first, static_cast<unsigned char>(__tmp), __last - __first);
00557 }
00558
00559 inline void
00560 fill(char* __first, char* __last, const char& __c)
00561 {
00562 char __tmp = __c;
00563 memset(__first, static_cast<unsigned char>(__tmp), __last - __first);
00564 }
00565
00566 template<typename _Size>
00567 inline unsigned char*
00568 fill_n(unsigned char* __first, _Size __n, const unsigned char& __c)
00569 {
00570 fill(__first, __first + __n, __c);
00571 return __first + __n;
00572 }
00573
00574 template<typename _Size>
00575 inline signed char*
00576 fill_n(char* __first, _Size __n, const signed char& __c)
00577 {
00578 fill(__first, __first + __n, __c);
00579 return __first + __n;
00580 }
00581
00582 template<typename _Size>
00583 inline char*
00584 fill_n(char* __first, _Size __n, const char& __c)
00585 {
00586 fill(__first, __first + __n, __c);
00587 return __first + __n;
00588 }
00589
00590
00591
00592
00593
00594
00595
00596
00597
00598
00599
00600
00601
00602
00603
00604
00605
00606 template<typename _InputIter1, typename _InputIter2>
00607 pair<_InputIter1, _InputIter2>
00608 mismatch(_InputIter1 __first1, _InputIter1 __last1,
00609 _InputIter2 __first2)
00610 {
00611
00612 __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>)
00613 __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>)
00614 __glibcpp_function_requires(_EqualityComparableConcept<
00615 typename iterator_traits<_InputIter1>::value_type>)
00616 __glibcpp_function_requires(_EqualityComparableConcept<
00617 typename iterator_traits<_InputIter2>::value_type>)
00618
00619 while (__first1 != __last1 && *__first1 == *__first2) {
00620 ++__first1;
00621 ++__first2;
00622 }
00623 return pair<_InputIter1, _InputIter2>(__first1, __first2);
00624 }
00625
00626
00627
00628
00629
00630
00631
00632
00633
00634
00635
00636
00637
00638
00639
00640 template<typename _InputIter1, typename _InputIter2, typename _BinaryPredicate>
00641 pair<_InputIter1, _InputIter2>
00642 mismatch(_InputIter1 __first1, _InputIter1 __last1,
00643 _InputIter2 __first2,
00644 _BinaryPredicate __binary_pred)
00645 {
00646
00647 __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>)
00648 __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>)
00649
00650 while (__first1 != __last1 && __binary_pred(*__first1, *__first2)) {
00651 ++__first1;
00652 ++__first2;
00653 }
00654 return pair<_InputIter1, _InputIter2>(__first1, __first2);
00655 }
00656
00657
00658
00659
00660
00661
00662
00663
00664
00665
00666
00667
00668 template<typename _InputIter1, typename _InputIter2>
00669 inline bool
00670 equal(_InputIter1 __first1, _InputIter1 __last1,
00671 _InputIter2 __first2)
00672 {
00673
00674 __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>)
00675 __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>)
00676 __glibcpp_function_requires(_EqualOpConcept<
00677 typename iterator_traits<_InputIter1>::value_type,
00678 typename iterator_traits<_InputIter2>::value_type>)
00679
00680 for ( ; __first1 != __last1; ++__first1, ++__first2)
00681 if (!(*__first1 == *__first2))
00682 return false;
00683 return true;
00684 }
00685
00686
00687
00688
00689
00690
00691
00692
00693
00694
00695
00696
00697
00698
00699 template<typename _InputIter1, typename _InputIter2, typename _BinaryPredicate>
00700 inline bool
00701 equal(_InputIter1 __first1, _InputIter1 __last1,
00702 _InputIter2 __first2,
00703 _BinaryPredicate __binary_pred)
00704 {
00705
00706 __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>)
00707 __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>)
00708
00709 for ( ; __first1 != __last1; ++__first1, ++__first2)
00710 if (!__binary_pred(*__first1, *__first2))
00711 return false;
00712 return true;
00713 }
00714
00715
00716
00717
00718
00719
00720
00721
00722
00723
00724
00725
00726
00727
00728
00729
00730
00731
00732 template<typename _InputIter1, typename _InputIter2>
00733 bool
00734 lexicographical_compare(_InputIter1 __first1, _InputIter1 __last1,
00735 _InputIter2 __first2, _InputIter2 __last2)
00736 {
00737
00738 __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>)
00739 __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>)
00740 __glibcpp_function_requires(_LessThanComparableConcept<
00741 typename iterator_traits<_InputIter1>::value_type>)
00742 __glibcpp_function_requires(_LessThanComparableConcept<
00743 typename iterator_traits<_InputIter2>::value_type>)
00744
00745 for ( ; __first1 != __last1 && __first2 != __last2
00746 ; ++__first1, ++__first2) {
00747 if (*__first1 < *__first2)
00748 return true;
00749 if (*__first2 < *__first1)
00750 return false;
00751 }
00752 return __first1 == __last1 && __first2 != __last2;
00753 }
00754
00755
00756
00757
00758
00759
00760
00761
00762
00763
00764
00765
00766
00767 template<typename _InputIter1, typename _InputIter2, typename _Compare>
00768 bool
00769 lexicographical_compare(_InputIter1 __first1, _InputIter1 __last1,
00770 _InputIter2 __first2, _InputIter2 __last2,
00771 _Compare __comp)
00772 {
00773
00774 __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>)
00775 __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>)
00776
00777 for ( ; __first1 != __last1 && __first2 != __last2
00778 ; ++__first1, ++__first2) {
00779 if (__comp(*__first1, *__first2))
00780 return true;
00781 if (__comp(*__first2, *__first1))
00782 return false;
00783 }
00784 return __first1 == __last1 && __first2 != __last2;
00785 }
00786
00787 inline bool
00788 lexicographical_compare(const unsigned char* __first1, const unsigned char* __last1,
00789 const unsigned char* __first2, const unsigned char* __last2)
00790 {
00791 const size_t __len1 = __last1 - __first1;
00792 const size_t __len2 = __last2 - __first2;
00793 const int __result = memcmp(__first1, __first2, min(__len1, __len2));
00794 return __result != 0 ? __result < 0 : __len1 < __len2;
00795 }
00796
00797 inline bool
00798 lexicographical_compare(const char* __first1, const char* __last1,
00799 const char* __first2, const char* __last2)
00800 {
00801 #if CHAR_MAX == SCHAR_MAX
00802 return lexicographical_compare((const signed char*) __first1,
00803 (const signed char*) __last1,
00804 (const signed char*) __first2,
00805 (const signed char*) __last2);
00806 #else
00807 return lexicographical_compare((const unsigned char*) __first1,
00808 (const unsigned char*) __last1,
00809 (const unsigned char*) __first2,
00810 (const unsigned char*) __last2);
00811 #endif
00812 }
00813
00814 }
00815
00816 #endif
00817
00818
00819
00820