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