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
00061 #ifndef _EXT_ALGORITHM
00062 #define _EXT_ALGORITHM 1
00063
00064 #pragma GCC system_header
00065
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 _InputIterator, typename _Size, typename _OutputIterator>
00081 pair<_InputIterator, _OutputIterator>
00082 __copy_n(_InputIterator __first, _Size __count,
00083 _OutputIterator __result,
00084 input_iterator_tag)
00085 {
00086 for ( ; __count > 0; --__count)
00087 {
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, std::copy(__first,
00103 __last,
00104 __result));
00105 }
00106
00121 template<typename _InputIterator, typename _Size, typename _OutputIterator>
00122 inline pair<_InputIterator, _OutputIterator>
00123 copy_n(_InputIterator __first, _Size __count, _OutputIterator __result)
00124 {
00125
00126 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
00127 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
00128 typename iterator_traits<_InputIterator>::value_type>)
00129
00130 return __copy_n(__first, __count, __result,
00131 std::__iterator_category(__first));
00132 }
00133
00134 template<typename _InputIterator1, typename _InputIterator2>
00135 int
00136 __lexicographical_compare_3way(_InputIterator1 __first1,
00137 _InputIterator1 __last1,
00138 _InputIterator2 __first2,
00139 _InputIterator2 __last2)
00140 {
00141 while (__first1 != __last1 && __first2 != __last2)
00142 {
00143 if (*__first1 < *__first2)
00144 return -1;
00145 if (*__first2 < *__first1)
00146 return 1;
00147 ++__first1;
00148 ++__first2;
00149 }
00150 if (__first2 == __last2)
00151 return !(__first1 == __last1);
00152 else
00153 return -1;
00154 }
00155
00156 inline int
00157 __lexicographical_compare_3way(const unsigned char* __first1,
00158 const unsigned char* __last1,
00159 const unsigned char* __first2,
00160 const unsigned char* __last2)
00161 {
00162 const ptrdiff_t __len1 = __last1 - __first1;
00163 const ptrdiff_t __len2 = __last2 - __first2;
00164 const int __result = std::memcmp(__first1, __first2, 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
00200 template<typename _InputIterator1, typename _InputIterator2>
00201 int
00202 lexicographical_compare_3way(_InputIterator1 __first1,
00203 _InputIterator1 __last1,
00204 _InputIterator2 __first2,
00205 _InputIterator2 __last2)
00206 {
00207
00208 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
00209 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
00210 __glibcxx_function_requires(_LessThanComparableConcept<
00211 typename iterator_traits<_InputIterator1>::value_type>)
00212 __glibcxx_function_requires(_LessThanComparableConcept<
00213 typename iterator_traits<_InputIterator2>::value_type>)
00214 __glibcxx_requires_valid_range(__first1, __last1);
00215 __glibcxx_requires_valid_range(__first2, __last2);
00216
00217 return __lexicographical_compare_3way(__first1, __last1, __first2,
00218 __last2);
00219 }
00220
00221
00222
00223 template<typename _InputIterator, typename _Tp, typename _Size>
00224 void
00225 count(_InputIterator __first, _InputIterator __last,
00226 const _Tp& __value,
00227 _Size& __n)
00228 {
00229
00230 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
00231 __glibcxx_function_requires(_EqualityComparableConcept<
00232 typename iterator_traits<_InputIterator>::value_type >)
00233 __glibcxx_function_requires(_EqualityComparableConcept<_Tp>)
00234 __glibcxx_requires_valid_range(__first, __last);
00235
00236 for ( ; __first != __last; ++__first)
00237 if (*__first == __value)
00238 ++__n;
00239 }
00240
00241 template<typename _InputIterator, typename _Predicate, typename _Size>
00242 void
00243 count_if(_InputIterator __first, _InputIterator __last,
00244 _Predicate __pred,
00245 _Size& __n)
00246 {
00247
00248 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
00249 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
00250 typename iterator_traits<_InputIterator>::value_type>)
00251 __glibcxx_requires_valid_range(__first, __last);
00252
00253 for ( ; __first != __last; ++__first)
00254 if (__pred(*__first))
00255 ++__n;
00256 }
00257
00258
00259
00265 template<typename _ForwardIterator, typename _OutputIterator,
00266 typename _Distance>
00267 _OutputIterator
00268 random_sample_n(_ForwardIterator __first, _ForwardIterator __last,
00269 _OutputIterator __out, const _Distance __n)
00270 {
00271
00272 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
00273 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
00274 typename iterator_traits<_ForwardIterator>::value_type>)
00275 __glibcxx_requires_valid_range(__first, __last);
00276
00277 _Distance __remaining = std::distance(__first, __last);
00278 _Distance __m = min(__n, __remaining);
00279
00280 while (__m > 0)
00281 {
00282 if ((std::rand() % __remaining) < __m)
00283 {
00284 *__out = *__first;
00285 ++__out;
00286 --__m;
00287 }
00288 --__remaining;
00289 ++__first;
00290 }
00291 return __out;
00292 }
00293
00299 template<typename _ForwardIterator, typename _OutputIterator,
00300 typename _Distance, typename _RandomNumberGenerator>
00301 _OutputIterator
00302 random_sample_n(_ForwardIterator __first, _ForwardIterator __last,
00303 _OutputIterator __out, const _Distance __n,
00304 _RandomNumberGenerator& __rand)
00305 {
00306
00307 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
00308 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
00309 typename iterator_traits<_ForwardIterator>::value_type>)
00310 __glibcxx_function_requires(_UnaryFunctionConcept<
00311 _RandomNumberGenerator, _Distance, _Distance>)
00312 __glibcxx_requires_valid_range(__first, __last);
00313
00314 _Distance __remaining = std::distance(__first, __last);
00315 _Distance __m = min(__n, __remaining);
00316
00317 while (__m > 0)
00318 {
00319 if (__rand(__remaining) < __m)
00320 {
00321 *__out = *__first;
00322 ++__out;
00323 --__m;
00324 }
00325 --__remaining;
00326 ++__first;
00327 }
00328 return __out;
00329 }
00330
00331 template<typename _InputIterator, typename _RandomAccessIterator,
00332 typename _Distance>
00333 _RandomAccessIterator
00334 __random_sample(_InputIterator __first, _InputIterator __last,
00335 _RandomAccessIterator __out,
00336 const _Distance __n)
00337 {
00338 _Distance __m = 0;
00339 _Distance __t = __n;
00340 for ( ; __first != __last && __m < __n; ++__m, ++__first)
00341 __out[__m] = *__first;
00342
00343 while (__first != __last)
00344 {
00345 ++__t;
00346 _Distance __M = std::rand() % (__t);
00347 if (__M < __n)
00348 __out[__M] = *__first;
00349 ++__first;
00350 }
00351 return __out + __m;
00352 }
00353
00354 template<typename _InputIterator, typename _RandomAccessIterator,
00355 typename _RandomNumberGenerator, typename _Distance>
00356 _RandomAccessIterator
00357 __random_sample(_InputIterator __first, _InputIterator __last,
00358 _RandomAccessIterator __out,
00359 _RandomNumberGenerator& __rand,
00360 const _Distance __n)
00361 {
00362
00363 __glibcxx_function_requires(_UnaryFunctionConcept<
00364 _RandomNumberGenerator, _Distance, _Distance>)
00365
00366 _Distance __m = 0;
00367 _Distance __t = __n;
00368 for ( ; __first != __last && __m < __n; ++__m, ++__first)
00369 __out[__m] = *__first;
00370
00371 while (__first != __last)
00372 {
00373 ++__t;
00374 _Distance __M = __rand(__t);
00375 if (__M < __n)
00376 __out[__M] = *__first;
00377 ++__first;
00378 }
00379 return __out + __m;
00380 }
00381
00387 template<typename _InputIterator, typename _RandomAccessIterator>
00388 inline _RandomAccessIterator
00389 random_sample(_InputIterator __first, _InputIterator __last,
00390 _RandomAccessIterator __out_first,
00391 _RandomAccessIterator __out_last)
00392 {
00393
00394 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
00395 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
00396 _RandomAccessIterator>)
00397 __glibcxx_requires_valid_range(__first, __last);
00398 __glibcxx_requires_valid_range(__out_first, __out_last);
00399
00400 return __random_sample(__first, __last,
00401 __out_first, __out_last - __out_first);
00402 }
00403
00409 template<typename _InputIterator, typename _RandomAccessIterator,
00410 typename _RandomNumberGenerator>
00411 inline _RandomAccessIterator
00412 random_sample(_InputIterator __first, _InputIterator __last,
00413 _RandomAccessIterator __out_first,
00414 _RandomAccessIterator __out_last,
00415 _RandomNumberGenerator& __rand)
00416 {
00417
00418 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
00419 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
00420 _RandomAccessIterator>)
00421 __glibcxx_requires_valid_range(__first, __last);
00422 __glibcxx_requires_valid_range(__out_first, __out_last);
00423
00424 return __random_sample(__first, __last,
00425 __out_first, __rand,
00426 __out_last - __out_first);
00427 }
00428
00434 template<typename _RandomAccessIterator>
00435 inline bool
00436 is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
00437 {
00438
00439 __glibcxx_function_requires(_RandomAccessIteratorConcept<
00440 _RandomAccessIterator>)
00441 __glibcxx_function_requires(_LessThanComparableConcept<
00442 typename iterator_traits<_RandomAccessIterator>::value_type>)
00443 __glibcxx_requires_valid_range(__first, __last);
00444
00445 return std::__is_heap(__first, __last - __first);
00446 }
00447
00453 template<typename _RandomAccessIterator, typename _StrictWeakOrdering>
00454 inline bool
00455 is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
00456 _StrictWeakOrdering __comp)
00457 {
00458
00459 __glibcxx_function_requires(_RandomAccessIteratorConcept<
00460 _RandomAccessIterator>)
00461 __glibcxx_function_requires(_BinaryPredicateConcept<_StrictWeakOrdering,
00462 typename iterator_traits<_RandomAccessIterator>::value_type,
00463 typename iterator_traits<_RandomAccessIterator>::value_type>)
00464 __glibcxx_requires_valid_range(__first, __last);
00465
00466 return std::__is_heap(__first, __comp, __last - __first);
00467 }
00468
00469
00470
00471
00472
00478 template<typename _ForwardIterator>
00479 bool
00480 is_sorted(_ForwardIterator __first, _ForwardIterator __last)
00481 {
00482
00483 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
00484 __glibcxx_function_requires(_LessThanComparableConcept<
00485 typename iterator_traits<_ForwardIterator>::value_type>)
00486 __glibcxx_requires_valid_range(__first, __last);
00487
00488 if (__first == __last)
00489 return true;
00490
00491 _ForwardIterator __next = __first;
00492 for (++__next; __next != __last; __first = __next, ++__next)
00493 if (*__next < *__first)
00494 return false;
00495 return true;
00496 }
00497
00503 template<typename _ForwardIterator, typename _StrictWeakOrdering>
00504 bool
00505 is_sorted(_ForwardIterator __first, _ForwardIterator __last,
00506 _StrictWeakOrdering __comp)
00507 {
00508
00509 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
00510 __glibcxx_function_requires(_BinaryPredicateConcept<_StrictWeakOrdering,
00511 typename iterator_traits<_ForwardIterator>::value_type,
00512 typename iterator_traits<_ForwardIterator>::value_type>)
00513 __glibcxx_requires_valid_range(__first, __last);
00514
00515 if (__first == __last)
00516 return true;
00517
00518 _ForwardIterator __next = __first;
00519 for (++__next; __next != __last; __first = __next, ++__next)
00520 if (__comp(*__next, *__first))
00521 return false;
00522 return true;
00523 }
00524 }
00525
00526 #endif