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
00062
#ifndef _EXT_ALGORITHM
00063
#define _EXT_ALGORITHM 1
00064
00065
#pragma GCC system_header
00066
00067
#include <algorithm>
00068
00069
namespace __gnu_cxx
00070 {
00071
using std::ptrdiff_t;
00072
using std::min;
00073
using std::pair;
00074
using std::input_iterator_tag;
00075
using std::random_access_iterator_tag;
00076
using std::iterator_traits;
00077
00078
00079
00080
00081
template<
typename _InputIterator,
typename _Size,
typename _OutputIterator>
00082 pair<_InputIterator, _OutputIterator>
00083 __copy_n(_InputIterator __first, _Size __count,
00084 _OutputIterator __result,
00085 input_iterator_tag)
00086 {
00087
for ( ; __count > 0; --__count) {
00088 *__result = *__first;
00089 ++__first;
00090 ++__result;
00091 }
00092
return pair<_InputIterator, _OutputIterator>(__first, __result);
00093 }
00094
00095
template<
typename _RAIterator,
typename _Size,
typename _OutputIterator>
00096
inline pair<_RAIterator, _OutputIterator>
00097 __copy_n(_RAIterator __first, _Size __count,
00098 _OutputIterator __result,
00099 random_access_iterator_tag)
00100 {
00101 _RAIterator __last = __first + __count;
00102
return pair<_RAIterator, _OutputIterator>(__last,
00103
std::copy(__first, __last, __result));
00104 }
00105
00106
00107
00108
00109
00110
00111
00112
00113
00114
00115
00116
00117
00118
00119
00120
template<
typename _InputIterator,
typename _Size,
typename _OutputIterator>
00121
inline pair<_InputIterator, _OutputIterator>
00122 copy_n(_InputIterator __first, _Size __count, _OutputIterator __result)
00123 {
00124
00125 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
00126 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
00127
typename iterator_traits<_InputIterator>::value_type>)
00128
00129
return __copy_n(__first, __count, __result,
00130 std::__iterator_category(__first));
00131 }
00132
00133
template<
typename _InputIterator1,
typename _InputIterator2>
00134
int
00135 __lexicographical_compare_3way(_InputIterator1 __first1, _InputIterator1 __last1,
00136 _InputIterator2 __first2, _InputIterator2 __last2)
00137 {
00138
while (__first1 != __last1 && __first2 != __last2) {
00139
if (*__first1 < *__first2)
00140
return -1;
00141
if (*__first2 < *__first1)
00142
return 1;
00143 ++__first1;
00144 ++__first2;
00145 }
00146
if (__first2 == __last2) {
00147
return !(__first1 == __last1);
00148 }
00149
else {
00150
return -1;
00151 }
00152 }
00153
00154
inline int
00155 __lexicographical_compare_3way(
const unsigned char* __first1,
00156
const unsigned char* __last1,
00157
const unsigned char* __first2,
00158
const unsigned char* __last2)
00159 {
00160
const ptrdiff_t __len1 = __last1 - __first1;
00161
const ptrdiff_t __len2 = __last2 - __first2;
00162
const int __result = std::memcmp(__first1, __first2,
min(__len1, __len2));
00163
return __result != 0 ? __result
00164 : (__len1 == __len2 ? 0 : (__len1 < __len2 ? -1 : 1));
00165 }
00166
00167
inline int
00168 __lexicographical_compare_3way(
const char* __first1,
const char* __last1,
00169
const char* __first2,
const char* __last2)
00170 {
00171
#if CHAR_MAX == SCHAR_MAX
00172
return __lexicographical_compare_3way(
00173 (
const signed char*) __first1,
00174 (
const signed char*) __last1,
00175 (
const signed char*) __first2,
00176 (
const signed char*) __last2);
00177
#else
00178
return __lexicographical_compare_3way((
const unsigned char*) __first1,
00179 (
const unsigned char*) __last1,
00180 (
const unsigned char*) __first2,
00181 (
const unsigned char*) __last2);
00182
#endif
00183
}
00184
00185
00186
00187
00188
00189
00190
00191
00192
00193
00194
00195
00196
00197
00198
00199
template<
typename _InputIterator1,
typename _InputIterator2>
00200
int
00201 lexicographical_compare_3way(_InputIterator1 __first1, _InputIterator1 __last1,
00202 _InputIterator2 __first2, _InputIterator2 __last2)
00203 {
00204
00205 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
00206 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
00207 __glibcxx_function_requires(_LessThanComparableConcept<
00208
typename iterator_traits<_InputIterator1>::value_type>)
00209 __glibcxx_function_requires(_LessThanComparableConcept<
00210
typename iterator_traits<_InputIterator2>::value_type>)
00211 __glibcxx_requires_valid_range(__first1, __last1);
00212 __glibcxx_requires_valid_range(__first2, __last2);
00213
00214
return __lexicographical_compare_3way(__first1, __last1, __first2, __last2);
00215 }
00216
00217
00218
00219
00220
template<
typename _InputIterator,
typename _Tp,
typename _Size>
00221
void
00222 count(_InputIterator __first, _InputIterator __last,
00223
const _Tp& __value,
00224 _Size& __n)
00225 {
00226
00227 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
00228 __glibcxx_function_requires(_EqualityComparableConcept<
00229 typename iterator_traits<_InputIterator>::value_type >)
00230 __glibcxx_function_requires(_EqualityComparableConcept<_Tp>)
00231 __glibcxx_requires_valid_range(__first, __last);
00232
00233 for ( ; __first != __last; ++__first)
00234 if (*__first == __value)
00235 ++__n;
00236 }
00237
00238 template<typename _InputIterator, typename _Predicate, typename _Size>
00239
void
00240 count_if(_InputIterator __first, _InputIterator __last,
00241 _Predicate __pred,
00242 _Size& __n)
00243 {
00244
00245 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
00246 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
00247 typename iterator_traits<_InputIterator>::value_type>)
00248 __glibcxx_requires_valid_range(__first, __last);
00249
00250 for ( ; __first != __last; ++__first)
00251 if (__pred(*__first))
00252 ++__n;
00253 }
00254
00255
00256
00257
00258
00259
00260
00261
00262 template<typename _ForwardIterator, typename _OutputIterator, typename _Distance>
00263 _OutputIterator
00264 random_sample_n(_ForwardIterator __first, _ForwardIterator __last,
00265 _OutputIterator __out, const _Distance __n)
00266 {
00267
00268 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
00269 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
00270
typename iterator_traits<_ForwardIterator>::value_type>)
00271 __glibcxx_requires_valid_range(__first, __last);
00272
00273 _Distance __remaining =
std::distance(__first, __last);
00274 _Distance __m =
min(__n, __remaining);
00275
00276
while (__m > 0) {
00277
if ((std::rand() % __remaining) < __m) {
00278 *__out = *__first;
00279 ++__out;
00280 --__m;
00281 }
00282
00283 --__remaining;
00284 ++__first;
00285 }
00286
return __out;
00287 }
00288
00289
00290
00291
00292
00293
00294
template<
typename _ForwardIterator,
typename _OutputIterator,
typename _Distance,
00295
typename _RandomNumberGenerator>
00296 _OutputIterator
00297
random_sample_n(_ForwardIterator __first, _ForwardIterator __last,
00298 _OutputIterator __out,
const _Distance __n,
00299 _RandomNumberGenerator& __rand)
00300 {
00301
00302 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
00303 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
00304
typename iterator_traits<_ForwardIterator>::value_type>)
00305 __glibcxx_function_requires(_UnaryFunctionConcept<
00306 _RandomNumberGenerator, _Distance, _Distance>)
00307 __glibcxx_requires_valid_range(__first, __last);
00308
00309 _Distance __remaining =
std::distance(__first, __last);
00310 _Distance __m =
min(__n, __remaining);
00311
00312
while (__m > 0) {
00313
if (__rand(__remaining) < __m) {
00314 *__out = *__first;
00315 ++__out;
00316 --__m;
00317 }
00318
00319 --__remaining;
00320 ++__first;
00321 }
00322
return __out;
00323 }
00324
00325
template<
typename _InputIterator,
typename _RandomAccessIterator,
typename _Distance>
00326 _RandomAccessIterator
00327 __random_sample(_InputIterator __first, _InputIterator __last,
00328 _RandomAccessIterator __out,
00329
const _Distance __n)
00330 {
00331 _Distance __m = 0;
00332 _Distance __t = __n;
00333
for ( ; __first != __last && __m < __n; ++__m, ++__first)
00334 __out[__m] = *__first;
00335
00336
while (__first != __last) {
00337 ++__t;
00338 _Distance __M = std::rand() % (__t);
00339
if (__M < __n)
00340 __out[__M] = *__first;
00341 ++__first;
00342 }
00343
00344
return __out + __m;
00345 }
00346
00347
template<
typename _InputIterator,
typename _RandomAccessIterator,
00348
typename _RandomNumberGenerator,
typename _Distance>
00349 _RandomAccessIterator
00350 __random_sample(_InputIterator __first, _InputIterator __last,
00351 _RandomAccessIterator __out,
00352 _RandomNumberGenerator& __rand,
00353
const _Distance __n)
00354 {
00355
00356 __glibcxx_function_requires(_UnaryFunctionConcept<
00357 _RandomNumberGenerator, _Distance, _Distance>)
00358
00359 _Distance __m = 0;
00360 _Distance __t = __n;
00361 for ( ; __first != __last && __m < __n; ++__m, ++__first)
00362 __out[__m] = *__first;
00363
00364 while (__first != __last) {
00365 ++__t;
00366 _Distance __M = __rand(__t);
00367
if (__M < __n)
00368 __out[__M] = *__first;
00369 ++__first;
00370 }
00371
00372
return __out + __m;
00373 }
00374
00375
00376
00377
00378
00379
00380
template<
typename _InputIterator,
typename _RandomAccessIterator>
00381
inline _RandomAccessIterator
00382
random_sample(_InputIterator __first, _InputIterator __last,
00383 _RandomAccessIterator __out_first, _RandomAccessIterator __out_last)
00384 {
00385
00386 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
00387 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
00388 _RandomAccessIterator>)
00389 __glibcxx_requires_valid_range(__first, __last);
00390 __glibcxx_requires_valid_range(__out_first, __out_last);
00391
00392 return __random_sample(__first, __last,
00393 __out_first, __out_last - __out_first);
00394 }
00395
00396
00397
00398
00399
00400
00401 template<typename _InputIterator, typename _RandomAccessIterator,
00402 typename _RandomNumberGenerator>
00403 inline _RandomAccessIterator
00404 random_sample(_InputIterator __first, _InputIterator __last,
00405 _RandomAccessIterator __out_first, _RandomAccessIterator __out_last,
00406 _RandomNumberGenerator& __rand)
00407 {
00408
00409 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
00410 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
00411 _RandomAccessIterator>)
00412 __glibcxx_requires_valid_range(__first, __last);
00413 __glibcxx_requires_valid_range(__out_first, __out_last);
00414
00415 return __random_sample(__first, __last,
00416 __out_first, __rand,
00417 __out_last - __out_first);
00418 }
00419
00420
00421
00422
00423
00424
00425 template<typename _RandomAccessIterator>
00426 inline
bool
00427 is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
00428 {
00429
00430 __glibcxx_function_requires(_RandomAccessIteratorConcept<_RandomAccessIterator>)
00431 __glibcxx_function_requires(_LessThanComparableConcept<
00432 typename iterator_traits<_RandomAccessIterator>::value_type>)
00433 __glibcxx_requires_valid_range(__first, __last);
00434
00435
return std::__is_heap(__first, __last - __first);
00436 }
00437
00438
00439
00440
00441
00442
00443
template<
typename _RandomAccessIterator,
typename _StrictWeakOrdering>
00444
inline bool
00445
is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
00446 _StrictWeakOrdering __comp)
00447 {
00448
00449 __glibcxx_function_requires(_RandomAccessIteratorConcept<_RandomAccessIterator>)
00450 __glibcxx_function_requires(_BinaryPredicateConcept<_StrictWeakOrdering,
00451 typename iterator_traits<_RandomAccessIterator>::value_type,
00452 typename iterator_traits<_RandomAccessIterator>::value_type>)
00453 __glibcxx_requires_valid_range(__first, __last);
00454
00455 return std::__is_heap(__first, __comp, __last - __first);
00456 }
00457
00458
00459
00460
00461
00462
00463
00464
00465
00466
00467 template<typename _ForwardIterator>
00468
bool
00469 is_sorted(_ForwardIterator __first, _ForwardIterator __last)
00470 {
00471
00472 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
00473 __glibcxx_function_requires(_LessThanComparableConcept<
00474
typename iterator_traits<_ForwardIterator>::value_type>)
00475 __glibcxx_requires_valid_range(__first, __last);
00476
00477
if (__first == __last)
00478
return true;
00479
00480 _ForwardIterator __next = __first;
00481
for (++__next; __next != __last; __first = __next, ++__next) {
00482
if (*__next < *__first)
00483
return false;
00484 }
00485
00486
return true;
00487 }
00488
00489
00490
00491
00492
00493
00494
template<
typename _ForwardIterator,
typename _StrictWeakOrdering>
00495
bool
00496
is_sorted(_ForwardIterator __first, _ForwardIterator __last, _StrictWeakOrdering __comp)
00497 {
00498
00499 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
00500 __glibcxx_function_requires(_BinaryPredicateConcept<_StrictWeakOrdering,
00501 typename iterator_traits<_ForwardIterator>::value_type,
00502 typename iterator_traits<_ForwardIterator>::value_type>)
00503 __glibcxx_requires_valid_range(__first, __last);
00504
00505 if (__first == __last)
00506 return true;
00507
00508 _ForwardIterator __next = __first;
00509 for (++__next; __next != __last; __first = __next, ++__next) {
00510
if (__comp(*__next, *__first))
00511
return false;
00512 }
00513
00514
return true;
00515 }
00516 }
00517
00518
#endif