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