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 __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 template<typename _InputIterator1, typename _InputIterator2>
00198 int
00199 lexicographical_compare_3way(_InputIterator1 __first1,
00200 _InputIterator1 __last1,
00201 _InputIterator2 __first2,
00202 _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,
00215 __last2);
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,
00263 typename _Distance>
00264 _OutputIterator
00265 random_sample_n(_ForwardIterator __first, _ForwardIterator __last,
00266 _OutputIterator __out, const _Distance __n)
00267 {
00268
00269 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
00270 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
00271 typename iterator_traits<_ForwardIterator>::value_type>)
00272 __glibcxx_requires_valid_range(__first, __last);
00273
00274 _Distance __remaining = std::distance(__first, __last);
00275 _Distance __m = min(__n, __remaining);
00276
00277 while (__m > 0)
00278 {
00279 if ((std::rand() % __remaining) < __m)
00280 {
00281 *__out = *__first;
00282 ++__out;
00283 --__m;
00284 }
00285 --__remaining;
00286 ++__first;
00287 }
00288 return __out;
00289 }
00290
00291
00292
00293
00294
00295
00296 template<typename _ForwardIterator, typename _OutputIterator,
00297 typename _Distance, typename _RandomNumberGenerator>
00298 _OutputIterator
00299 random_sample_n(_ForwardIterator __first, _ForwardIterator __last,
00300 _OutputIterator __out, const _Distance __n,
00301 _RandomNumberGenerator& __rand)
00302 {
00303
00304 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
00305 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
00306 typename iterator_traits<_ForwardIterator>::value_type>)
00307 __glibcxx_function_requires(_UnaryFunctionConcept<
00308 _RandomNumberGenerator, _Distance, _Distance>)
00309 __glibcxx_requires_valid_range(__first, __last);
00310
00311 _Distance __remaining = std::distance(__first, __last);
00312 _Distance __m = min(__n, __remaining);
00313
00314 while (__m > 0)
00315 {
00316 if (__rand(__remaining) < __m)
00317 {
00318 *__out = *__first;
00319 ++__out;
00320 --__m;
00321 }
00322 --__remaining;
00323 ++__first;
00324 }
00325 return __out;
00326 }
00327
00328 template<typename _InputIterator, typename _RandomAccessIterator,
00329 typename _Distance>
00330 _RandomAccessIterator
00331 __random_sample(_InputIterator __first, _InputIterator __last,
00332 _RandomAccessIterator __out,
00333 const _Distance __n)
00334 {
00335 _Distance __m = 0;
00336 _Distance __t = __n;
00337 for ( ; __first != __last && __m < __n; ++__m, ++__first)
00338 __out[__m] = *__first;
00339
00340 while (__first != __last)
00341 {
00342 ++__t;
00343 _Distance __M = std::rand() % (__t);
00344 if (__M < __n)
00345 __out[__M] = *__first;
00346 ++__first;
00347 }
00348 return __out + __m;
00349 }
00350
00351 template<typename _InputIterator, typename _RandomAccessIterator,
00352 typename _RandomNumberGenerator, typename _Distance>
00353 _RandomAccessIterator
00354 __random_sample(_InputIterator __first, _InputIterator __last,
00355 _RandomAccessIterator __out,
00356 _RandomNumberGenerator& __rand,
00357 const _Distance __n)
00358 {
00359
00360 __glibcxx_function_requires(_UnaryFunctionConcept<
00361 _RandomNumberGenerator, _Distance, _Distance>)
00362
00363 _Distance __m = 0;
00364 _Distance __t = __n;
00365 for ( ; __first != __last && __m < __n; ++__m, ++__first)
00366 __out[__m] = *__first;
00367
00368 while (__first != __last)
00369 {
00370 ++__t;
00371 _Distance __M = __rand(__t);
00372 if (__M < __n)
00373 __out[__M] = *__first;
00374 ++__first;
00375 }
00376 return __out + __m;
00377 }
00378
00379
00380
00381
00382
00383
00384 template<typename _InputIterator, typename _RandomAccessIterator>
00385 inline _RandomAccessIterator
00386 random_sample(_InputIterator __first, _InputIterator __last,
00387 _RandomAccessIterator __out_first,
00388 _RandomAccessIterator __out_last)
00389 {
00390
00391 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
00392 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
00393 _RandomAccessIterator>)
00394 __glibcxx_requires_valid_range(__first, __last);
00395 __glibcxx_requires_valid_range(__out_first, __out_last);
00396
00397 return __random_sample(__first, __last,
00398 __out_first, __out_last - __out_first);
00399 }
00400
00401
00402
00403
00404
00405
00406 template<typename _InputIterator, typename _RandomAccessIterator,
00407 typename _RandomNumberGenerator>
00408 inline _RandomAccessIterator
00409 random_sample(_InputIterator __first, _InputIterator __last,
00410 _RandomAccessIterator __out_first,
00411 _RandomAccessIterator __out_last,
00412 _RandomNumberGenerator& __rand)
00413 {
00414
00415 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
00416 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
00417 _RandomAccessIterator>)
00418 __glibcxx_requires_valid_range(__first, __last);
00419 __glibcxx_requires_valid_range(__out_first, __out_last);
00420
00421 return __random_sample(__first, __last,
00422 __out_first, __rand,
00423 __out_last - __out_first);
00424 }
00425
00426
00427
00428
00429
00430
00431 template<typename _RandomAccessIterator>
00432 inline bool
00433 is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
00434 {
00435
00436 __glibcxx_function_requires(_RandomAccessIteratorConcept<
00437 _RandomAccessIterator>)
00438 __glibcxx_function_requires(_LessThanComparableConcept<
00439 typename iterator_traits<_RandomAccessIterator>::value_type>)
00440 __glibcxx_requires_valid_range(__first, __last);
00441
00442 return std::__is_heap(__first, __last - __first);
00443 }
00444
00445
00446
00447
00448
00449
00450 template<typename _RandomAccessIterator, typename _StrictWeakOrdering>
00451 inline bool
00452 is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
00453 _StrictWeakOrdering __comp)
00454 {
00455
00456 __glibcxx_function_requires(_RandomAccessIteratorConcept<
00457 _RandomAccessIterator>)
00458 __glibcxx_function_requires(_BinaryPredicateConcept<_StrictWeakOrdering,
00459 typename iterator_traits<_RandomAccessIterator>::value_type,
00460 typename iterator_traits<_RandomAccessIterator>::value_type>)
00461 __glibcxx_requires_valid_range(__first, __last);
00462
00463 return std::__is_heap(__first, __comp, __last - __first);
00464 }
00465
00466
00467
00468
00469
00470
00471
00472
00473
00474
00475 template<typename _ForwardIterator>
00476 bool
00477 is_sorted(_ForwardIterator __first, _ForwardIterator __last)
00478 {
00479
00480 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
00481 __glibcxx_function_requires(_LessThanComparableConcept<
00482 typename iterator_traits<_ForwardIterator>::value_type>)
00483 __glibcxx_requires_valid_range(__first, __last);
00484
00485 if (__first == __last)
00486 return true;
00487
00488 _ForwardIterator __next = __first;
00489 for (++__next; __next != __last; __first = __next, ++__next)
00490 if (*__next < *__first)
00491 return false;
00492 return true;
00493 }
00494
00495
00496
00497
00498
00499
00500 template<typename _ForwardIterator, typename _StrictWeakOrdering>
00501 bool
00502 is_sorted(_ForwardIterator __first, _ForwardIterator __last,
00503 _StrictWeakOrdering __comp)
00504 {
00505
00506 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
00507 __glibcxx_function_requires(_BinaryPredicateConcept<_StrictWeakOrdering,
00508 typename iterator_traits<_ForwardIterator>::value_type,
00509 typename iterator_traits<_ForwardIterator>::value_type>)
00510 __glibcxx_requires_valid_range(__first, __last);
00511
00512 if (__first == __last)
00513 return true;
00514
00515 _ForwardIterator __next = __first;
00516 for (++__next; __next != __last; __first = __next, ++__next)
00517 if (__comp(*__next, *__first))
00518 return false;
00519 return true;
00520 }
00521
00522 _GLIBCXX_END_NAMESPACE
00523
00524 #endif