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