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