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