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