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 _B
idirectionalIter1,
typename _B
idirectionalIter2>
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 _B
idirectionalIter>
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