libstdc++
|
00001 // Algorithm extensions -*- C++ -*- 00002 00003 // Copyright (C) 2001-2015 Free Software Foundation, Inc. 00004 // 00005 // This file is part of the GNU ISO C++ Library. This library is free 00006 // software; you can redistribute it and/or modify it under the 00007 // terms of the GNU General Public License as published by the 00008 // Free Software Foundation; either version 3, or (at your option) 00009 // any later version. 00010 00011 // This library is distributed in the hope that it will be useful, 00012 // but WITHOUT ANY WARRANTY; without even the implied warranty of 00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00014 // GNU General Public License for more details. 00015 00016 // Under Section 7 of GPL version 3, you are granted additional 00017 // permissions described in the GCC Runtime Library Exception, version 00018 // 3.1, as published by the Free Software Foundation. 00019 00020 // You should have received a copy of the GNU General Public License and 00021 // a copy of the GCC Runtime Library Exception along with this program; 00022 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 00023 // <http://www.gnu.org/licenses/>. 00024 00025 /* 00026 * 00027 * Copyright (c) 1994 00028 * Hewlett-Packard Company 00029 * 00030 * Permission to use, copy, modify, distribute and sell this software 00031 * and its documentation for any purpose is hereby granted without fee, 00032 * provided that the above copyright notice appear in all copies and 00033 * that both that copyright notice and this permission notice appear 00034 * in supporting documentation. Hewlett-Packard Company makes no 00035 * representations about the suitability of this software for any 00036 * purpose. It is provided "as is" without express or implied warranty. 00037 * 00038 * 00039 * Copyright (c) 1996 00040 * Silicon Graphics Computer Systems, Inc. 00041 * 00042 * Permission to use, copy, modify, distribute and sell this software 00043 * and its documentation for any purpose is hereby granted without fee, 00044 * provided that the above copyright notice appear in all copies and 00045 * that both that copyright notice and this permission notice appear 00046 * in supporting documentation. Silicon Graphics makes no 00047 * representations about the suitability of this software for any 00048 * purpose. It is provided "as is" without express or implied warranty. 00049 */ 00050 00051 /** @file ext/algorithm 00052 * This file is a GNU extension to the Standard C++ Library (possibly 00053 * containing extensions from the HP/SGI STL subset). 00054 */ 00055 00056 #ifndef _EXT_ALGORITHM 00057 #define _EXT_ALGORITHM 1 00058 00059 #pragma GCC system_header 00060 00061 #include <algorithm> 00062 00063 namespace __gnu_cxx _GLIBCXX_VISIBILITY(default) 00064 { 00065 _GLIBCXX_BEGIN_NAMESPACE_VERSION 00066 00067 using std::ptrdiff_t; 00068 using std::min; 00069 using std::pair; 00070 using std::input_iterator_tag; 00071 using std::random_access_iterator_tag; 00072 using std::iterator_traits; 00073 00074 //-------------------------------------------------- 00075 // copy_n (not part of the C++ standard) 00076 00077 template<typename _InputIterator, typename _Size, typename _OutputIterator> 00078 pair<_InputIterator, _OutputIterator> 00079 __copy_n(_InputIterator __first, _Size __count, 00080 _OutputIterator __result, 00081 input_iterator_tag) 00082 { 00083 for ( ; __count > 0; --__count) 00084 { 00085 *__result = *__first; 00086 ++__first; 00087 ++__result; 00088 } 00089 return pair<_InputIterator, _OutputIterator>(__first, __result); 00090 } 00091 00092 template<typename _RAIterator, typename _Size, typename _OutputIterator> 00093 inline pair<_RAIterator, _OutputIterator> 00094 __copy_n(_RAIterator __first, _Size __count, 00095 _OutputIterator __result, 00096 random_access_iterator_tag) 00097 { 00098 _RAIterator __last = __first + __count; 00099 return pair<_RAIterator, _OutputIterator>(__last, std::copy(__first, 00100 __last, 00101 __result)); 00102 } 00103 00104 /** 00105 * @brief Copies the range [first,first+count) into [result,result+count). 00106 * @param __first An input iterator. 00107 * @param __count The number of elements to copy. 00108 * @param __result An output iterator. 00109 * @return A std::pair composed of first+count and result+count. 00110 * 00111 * This is an SGI extension. 00112 * This inline function will boil down to a call to @c memmove whenever 00113 * possible. Failing that, if random access iterators are passed, then the 00114 * loop count will be known (and therefore a candidate for compiler 00115 * optimizations such as unrolling). 00116 * @ingroup SGIextensions 00117 */ 00118 template<typename _InputIterator, typename _Size, typename _OutputIterator> 00119 inline pair<_InputIterator, _OutputIterator> 00120 copy_n(_InputIterator __first, _Size __count, _OutputIterator __result) 00121 { 00122 // concept requirements 00123 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 00124 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 00125 typename iterator_traits<_InputIterator>::value_type>) 00126 00127 return __gnu_cxx::__copy_n(__first, __count, __result, 00128 std::__iterator_category(__first)); 00129 } 00130 00131 template<typename _InputIterator1, typename _InputIterator2> 00132 int 00133 __lexicographical_compare_3way(_InputIterator1 __first1, 00134 _InputIterator1 __last1, 00135 _InputIterator2 __first2, 00136 _InputIterator2 __last2) 00137 { 00138 while (__first1 != __last1 && __first2 != __last2) 00139 { 00140 if (*__first1 < *__first2) 00141 return -1; 00142 if (*__first2 < *__first1) 00143 return 1; 00144 ++__first1; 00145 ++__first2; 00146 } 00147 if (__first2 == __last2) 00148 return !(__first1 == __last1); 00149 else 00150 return -1; 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 = __builtin_memcmp(__first1, __first2, 00162 min(__len1, __len2)); 00163 return __result != 0 ? __result 00164 : (__len1 == __len2 ? 0 : (__len1 < __len2 ? -1 : 1)); 00165 } 00166 00167 inline int 00168 __lexicographical_compare_3way(const char* __first1, const char* __last1, 00169 const char* __first2, const char* __last2) 00170 { 00171 #if CHAR_MAX == SCHAR_MAX 00172 return __lexicographical_compare_3way((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 * @brief @c memcmp on steroids. 00186 * @param __first1 An input iterator. 00187 * @param __last1 An input iterator. 00188 * @param __first2 An input iterator. 00189 * @param __last2 An input iterator. 00190 * @return An int, as with @c memcmp. 00191 * 00192 * The return value will be less than zero if the first range is 00193 * <em>lexigraphically less than</em> the second, greater than zero 00194 * if the second range is <em>lexigraphically less than</em> the 00195 * first, and zero otherwise. 00196 * This is an SGI extension. 00197 * @ingroup SGIextensions 00198 */ 00199 template<typename _InputIterator1, typename _InputIterator2> 00200 int 00201 lexicographical_compare_3way(_InputIterator1 __first1, 00202 _InputIterator1 __last1, 00203 _InputIterator2 __first2, 00204 _InputIterator2 __last2) 00205 { 00206 // concept requirements 00207 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 00208 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 00209 __glibcxx_function_requires(_LessThanComparableConcept< 00210 typename iterator_traits<_InputIterator1>::value_type>) 00211 __glibcxx_function_requires(_LessThanComparableConcept< 00212 typename iterator_traits<_InputIterator2>::value_type>) 00213 __glibcxx_requires_valid_range(__first1, __last1); 00214 __glibcxx_requires_valid_range(__first2, __last2); 00215 00216 return __lexicographical_compare_3way(__first1, __last1, __first2, 00217 __last2); 00218 } 00219 00220 // count and count_if: this version, whose return type is void, was present 00221 // in the HP STL, and is retained as an extension for backward compatibility. 00222 template<typename _InputIterator, typename _Tp, typename _Size> 00223 void 00224 count(_InputIterator __first, _InputIterator __last, 00225 const _Tp& __value, 00226 _Size& __n) 00227 { 00228 // concept requirements 00229 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 00230 __glibcxx_function_requires(_EqualityComparableConcept< 00231 typename iterator_traits<_InputIterator>::value_type >) 00232 __glibcxx_function_requires(_EqualityComparableConcept<_Tp>) 00233 __glibcxx_requires_valid_range(__first, __last); 00234 00235 for ( ; __first != __last; ++__first) 00236 if (*__first == __value) 00237 ++__n; 00238 } 00239 00240 template<typename _InputIterator, typename _Predicate, typename _Size> 00241 void 00242 count_if(_InputIterator __first, _InputIterator __last, 00243 _Predicate __pred, 00244 _Size& __n) 00245 { 00246 // concept requirements 00247 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 00248 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate, 00249 typename iterator_traits<_InputIterator>::value_type>) 00250 __glibcxx_requires_valid_range(__first, __last); 00251 00252 for ( ; __first != __last; ++__first) 00253 if (__pred(*__first)) 00254 ++__n; 00255 } 00256 00257 // random_sample and random_sample_n (extensions, not part of the standard). 00258 00259 /** 00260 * This is an SGI extension. 00261 * @ingroup SGIextensions 00262 * @doctodo 00263 */ 00264 template<typename _ForwardIterator, typename _OutputIterator, 00265 typename _Distance> 00266 _OutputIterator 00267 random_sample_n(_ForwardIterator __first, _ForwardIterator __last, 00268 _OutputIterator __out, const _Distance __n) 00269 { 00270 // concept requirements 00271 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 00272 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 00273 typename iterator_traits<_ForwardIterator>::value_type>) 00274 __glibcxx_requires_valid_range(__first, __last); 00275 00276 _Distance __remaining = std::distance(__first, __last); 00277 _Distance __m = min(__n, __remaining); 00278 00279 while (__m > 0) 00280 { 00281 if ((std::rand() % __remaining) < __m) 00282 { 00283 *__out = *__first; 00284 ++__out; 00285 --__m; 00286 } 00287 --__remaining; 00288 ++__first; 00289 } 00290 return __out; 00291 } 00292 00293 /** 00294 * This is an SGI extension. 00295 * @ingroup SGIextensions 00296 * @doctodo 00297 */ 00298 template<typename _ForwardIterator, typename _OutputIterator, 00299 typename _Distance, typename _RandomNumberGenerator> 00300 _OutputIterator 00301 random_sample_n(_ForwardIterator __first, _ForwardIterator __last, 00302 _OutputIterator __out, const _Distance __n, 00303 _RandomNumberGenerator& __rand) 00304 { 00305 // concept requirements 00306 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 00307 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 00308 typename iterator_traits<_ForwardIterator>::value_type>) 00309 __glibcxx_function_requires(_UnaryFunctionConcept< 00310 _RandomNumberGenerator, _Distance, _Distance>) 00311 __glibcxx_requires_valid_range(__first, __last); 00312 00313 _Distance __remaining = std::distance(__first, __last); 00314 _Distance __m = min(__n, __remaining); 00315 00316 while (__m > 0) 00317 { 00318 if (__rand(__remaining) < __m) 00319 { 00320 *__out = *__first; 00321 ++__out; 00322 --__m; 00323 } 00324 --__remaining; 00325 ++__first; 00326 } 00327 return __out; 00328 } 00329 00330 template<typename _InputIterator, typename _RandomAccessIterator, 00331 typename _Distance> 00332 _RandomAccessIterator 00333 __random_sample(_InputIterator __first, _InputIterator __last, 00334 _RandomAccessIterator __out, 00335 const _Distance __n) 00336 { 00337 _Distance __m = 0; 00338 _Distance __t = __n; 00339 for ( ; __first != __last && __m < __n; ++__m, ++__first) 00340 __out[__m] = *__first; 00341 00342 while (__first != __last) 00343 { 00344 ++__t; 00345 _Distance __M = std::rand() % (__t); 00346 if (__M < __n) 00347 __out[__M] = *__first; 00348 ++__first; 00349 } 00350 return __out + __m; 00351 } 00352 00353 template<typename _InputIterator, typename _RandomAccessIterator, 00354 typename _RandomNumberGenerator, typename _Distance> 00355 _RandomAccessIterator 00356 __random_sample(_InputIterator __first, _InputIterator __last, 00357 _RandomAccessIterator __out, 00358 _RandomNumberGenerator& __rand, 00359 const _Distance __n) 00360 { 00361 // concept requirements 00362 __glibcxx_function_requires(_UnaryFunctionConcept< 00363 _RandomNumberGenerator, _Distance, _Distance>) 00364 00365 _Distance __m = 0; 00366 _Distance __t = __n; 00367 for ( ; __first != __last && __m < __n; ++__m, ++__first) 00368 __out[__m] = *__first; 00369 00370 while (__first != __last) 00371 { 00372 ++__t; 00373 _Distance __M = __rand(__t); 00374 if (__M < __n) 00375 __out[__M] = *__first; 00376 ++__first; 00377 } 00378 return __out + __m; 00379 } 00380 00381 /** 00382 * This is an SGI extension. 00383 * @ingroup SGIextensions 00384 * @doctodo 00385 */ 00386 template<typename _InputIterator, typename _RandomAccessIterator> 00387 inline _RandomAccessIterator 00388 random_sample(_InputIterator __first, _InputIterator __last, 00389 _RandomAccessIterator __out_first, 00390 _RandomAccessIterator __out_last) 00391 { 00392 // concept requirements 00393 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 00394 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 00395 _RandomAccessIterator>) 00396 __glibcxx_requires_valid_range(__first, __last); 00397 __glibcxx_requires_valid_range(__out_first, __out_last); 00398 00399 return __random_sample(__first, __last, 00400 __out_first, __out_last - __out_first); 00401 } 00402 00403 /** 00404 * This is an SGI extension. 00405 * @ingroup SGIextensions 00406 * @doctodo 00407 */ 00408 template<typename _InputIterator, typename _RandomAccessIterator, 00409 typename _RandomNumberGenerator> 00410 inline _RandomAccessIterator 00411 random_sample(_InputIterator __first, _InputIterator __last, 00412 _RandomAccessIterator __out_first, 00413 _RandomAccessIterator __out_last, 00414 _RandomNumberGenerator& __rand) 00415 { 00416 // concept requirements 00417 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 00418 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 00419 _RandomAccessIterator>) 00420 __glibcxx_requires_valid_range(__first, __last); 00421 __glibcxx_requires_valid_range(__out_first, __out_last); 00422 00423 return __random_sample(__first, __last, 00424 __out_first, __rand, 00425 __out_last - __out_first); 00426 } 00427 00428 #if __cplusplus >= 201103L 00429 using std::is_heap; 00430 #else 00431 /** 00432 * This is an SGI extension. 00433 * @ingroup SGIextensions 00434 * @doctodo 00435 */ 00436 template<typename _RandomAccessIterator> 00437 inline bool 00438 is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) 00439 { 00440 // concept requirements 00441 __glibcxx_function_requires(_RandomAccessIteratorConcept< 00442 _RandomAccessIterator>) 00443 __glibcxx_function_requires(_LessThanComparableConcept< 00444 typename iterator_traits<_RandomAccessIterator>::value_type>) 00445 __glibcxx_requires_valid_range(__first, __last); 00446 00447 return std::__is_heap(__first, __last - __first); 00448 } 00449 00450 /** 00451 * This is an SGI extension. 00452 * @ingroup SGIextensions 00453 * @doctodo 00454 */ 00455 template<typename _RandomAccessIterator, typename _StrictWeakOrdering> 00456 inline bool 00457 is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, 00458 _StrictWeakOrdering __comp) 00459 { 00460 // concept requirements 00461 __glibcxx_function_requires(_RandomAccessIteratorConcept< 00462 _RandomAccessIterator>) 00463 __glibcxx_function_requires(_BinaryPredicateConcept<_StrictWeakOrdering, 00464 typename iterator_traits<_RandomAccessIterator>::value_type, 00465 typename iterator_traits<_RandomAccessIterator>::value_type>) 00466 __glibcxx_requires_valid_range(__first, __last); 00467 00468 return std::__is_heap(__first, __comp, __last - __first); 00469 } 00470 #endif 00471 00472 #if __cplusplus >= 201103L 00473 using std::is_sorted; 00474 #else 00475 // is_sorted, a predicated testing whether a range is sorted in 00476 // nondescending order. This is an extension, not part of the C++ 00477 // standard. 00478 00479 /** 00480 * This is an SGI extension. 00481 * @ingroup SGIextensions 00482 * @doctodo 00483 */ 00484 template<typename _ForwardIterator> 00485 bool 00486 is_sorted(_ForwardIterator __first, _ForwardIterator __last) 00487 { 00488 // concept requirements 00489 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 00490 __glibcxx_function_requires(_LessThanComparableConcept< 00491 typename iterator_traits<_ForwardIterator>::value_type>) 00492 __glibcxx_requires_valid_range(__first, __last); 00493 00494 if (__first == __last) 00495 return true; 00496 00497 _ForwardIterator __next = __first; 00498 for (++__next; __next != __last; __first = __next, ++__next) 00499 if (*__next < *__first) 00500 return false; 00501 return true; 00502 } 00503 00504 /** 00505 * This is an SGI extension. 00506 * @ingroup SGIextensions 00507 * @doctodo 00508 */ 00509 template<typename _ForwardIterator, typename _StrictWeakOrdering> 00510 bool 00511 is_sorted(_ForwardIterator __first, _ForwardIterator __last, 00512 _StrictWeakOrdering __comp) 00513 { 00514 // concept requirements 00515 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 00516 __glibcxx_function_requires(_BinaryPredicateConcept<_StrictWeakOrdering, 00517 typename iterator_traits<_ForwardIterator>::value_type, 00518 typename iterator_traits<_ForwardIterator>::value_type>) 00519 __glibcxx_requires_valid_range(__first, __last); 00520 00521 if (__first == __last) 00522 return true; 00523 00524 _ForwardIterator __next = __first; 00525 for (++__next; __next != __last; __first = __next, ++__next) 00526 if (__comp(*__next, *__first)) 00527 return false; 00528 return true; 00529 } 00530 #endif // C++11 00531 00532 /** 00533 * @brief Find the median of three values. 00534 * @param __a A value. 00535 * @param __b A value. 00536 * @param __c A value. 00537 * @return One of @p a, @p b or @p c. 00538 * 00539 * If @c {l,m,n} is some convolution of @p {a,b,c} such that @c l<=m<=n 00540 * then the value returned will be @c m. 00541 * This is an SGI extension. 00542 * @ingroup SGIextensions 00543 */ 00544 template<typename _Tp> 00545 const _Tp& 00546 __median(const _Tp& __a, const _Tp& __b, const _Tp& __c) 00547 { 00548 // concept requirements 00549 __glibcxx_function_requires(_LessThanComparableConcept<_Tp>) 00550 if (__a < __b) 00551 if (__b < __c) 00552 return __b; 00553 else if (__a < __c) 00554 return __c; 00555 else 00556 return __a; 00557 else if (__a < __c) 00558 return __a; 00559 else if (__b < __c) 00560 return __c; 00561 else 00562 return __b; 00563 } 00564 00565 /** 00566 * @brief Find the median of three values using a predicate for comparison. 00567 * @param __a A value. 00568 * @param __b A value. 00569 * @param __c A value. 00570 * @param __comp A binary predicate. 00571 * @return One of @p a, @p b or @p c. 00572 * 00573 * If @c {l,m,n} is some convolution of @p {a,b,c} such that @p comp(l,m) 00574 * and @p comp(m,n) are both true then the value returned will be @c m. 00575 * This is an SGI extension. 00576 * @ingroup SGIextensions 00577 */ 00578 template<typename _Tp, typename _Compare> 00579 const _Tp& 00580 __median(const _Tp& __a, const _Tp& __b, const _Tp& __c, _Compare __comp) 00581 { 00582 // concept requirements 00583 __glibcxx_function_requires(_BinaryFunctionConcept<_Compare, bool, 00584 _Tp, _Tp>) 00585 if (__comp(__a, __b)) 00586 if (__comp(__b, __c)) 00587 return __b; 00588 else if (__comp(__a, __c)) 00589 return __c; 00590 else 00591 return __a; 00592 else if (__comp(__a, __c)) 00593 return __a; 00594 else if (__comp(__b, __c)) 00595 return __c; 00596 else 00597 return __b; 00598 } 00599 00600 _GLIBCXX_END_NAMESPACE_VERSION 00601 } // namespace 00602 00603 #endif /* _EXT_ALGORITHM */