libstdc++
|
00001 // Algorithm extensions -*- C++ -*- 00002 00003 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 00004 // 2009, 2010, 2011 00005 // Free Software Foundation, Inc. 00006 // 00007 // This file is part of the GNU ISO C++ Library. This library is free 00008 // software; you can redistribute it and/or modify it under the 00009 // terms of the GNU General Public License as published by the 00010 // Free Software Foundation; either version 3, or (at your option) 00011 // any later version. 00012 00013 // This library is distributed in the hope that it will be useful, 00014 // but WITHOUT ANY WARRANTY; without even the implied warranty of 00015 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00016 // GNU General Public License for more details. 00017 00018 // Under Section 7 of GPL version 3, you are granted additional 00019 // permissions described in the GCC Runtime Library Exception, version 00020 // 3.1, as published by the Free Software Foundation. 00021 00022 // You should have received a copy of the GNU General Public License and 00023 // a copy of the GCC Runtime Library Exception along with this program; 00024 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 00025 // <http://www.gnu.org/licenses/>. 00026 00027 /* 00028 * 00029 * Copyright (c) 1994 00030 * Hewlett-Packard Company 00031 * 00032 * Permission to use, copy, modify, distribute and sell this software 00033 * and its documentation for any purpose is hereby granted without fee, 00034 * provided that the above copyright notice appear in all copies and 00035 * that both that copyright notice and this permission notice appear 00036 * in supporting documentation. Hewlett-Packard Company makes no 00037 * representations about the suitability of this software for any 00038 * purpose. It is provided "as is" without express or implied warranty. 00039 * 00040 * 00041 * Copyright (c) 1996 00042 * Silicon Graphics Computer Systems, Inc. 00043 * 00044 * Permission to use, copy, modify, distribute and sell this software 00045 * and its documentation for any purpose is hereby granted without fee, 00046 * provided that the above copyright notice appear in all copies and 00047 * that both that copyright notice and this permission notice appear 00048 * in supporting documentation. Silicon Graphics makes no 00049 * representations about the suitability of this software for any 00050 * purpose. It is provided "as is" without express or implied warranty. 00051 */ 00052 00053 /** @file ext/algorithm 00054 * This file is a GNU extension to the Standard C++ Library (possibly 00055 * containing extensions from the HP/SGI STL subset). 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 // copy_n (not part of the C++ standard) 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 * @brief Copies the range [first,first+count) into [result,result+count). 00108 * @param __first An input iterator. 00109 * @param __count The number of elements to copy. 00110 * @param __result An output iterator. 00111 * @return A std::pair composed of first+count and result+count. 00112 * 00113 * This is an SGI extension. 00114 * This inline function will boil down to a call to @c memmove whenever 00115 * possible. Failing that, if random access iterators are passed, then the 00116 * loop count will be known (and therefore a candidate for compiler 00117 * optimizations such as unrolling). 00118 * @ingroup SGIextensions 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 // concept requirements 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 * @brief @c memcmp on steroids. 00188 * @param __first1 An input iterator. 00189 * @param __last1 An input iterator. 00190 * @param __first2 An input iterator. 00191 * @param __last2 An input iterator. 00192 * @return An int, as with @c memcmp. 00193 * 00194 * The return value will be less than zero if the first range is 00195 * <em>lexigraphically less than</em> the second, greater than zero 00196 * if the second range is <em>lexigraphically less than</em> the 00197 * first, and zero otherwise. 00198 * This is an SGI extension. 00199 * @ingroup SGIextensions 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 // concept requirements 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 // count and count_if: this version, whose return type is void, was present 00223 // in the HP STL, and is retained as an extension for backward compatibility. 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 // concept requirements 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 // concept requirements 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 // random_sample and random_sample_n (extensions, not part of the standard). 00260 00261 /** 00262 * This is an SGI extension. 00263 * @ingroup SGIextensions 00264 * @doctodo 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 // concept requirements 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 * This is an SGI extension. 00297 * @ingroup SGIextensions 00298 * @doctodo 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 // concept requirements 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 // concept requirements 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 * This is an SGI extension. 00385 * @ingroup SGIextensions 00386 * @doctodo 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 // concept requirements 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 * This is an SGI extension. 00407 * @ingroup SGIextensions 00408 * @doctodo 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 // concept requirements 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 * This is an SGI extension. 00435 * @ingroup SGIextensions 00436 * @doctodo 00437 */ 00438 template<typename _RandomAccessIterator> 00439 inline bool 00440 is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) 00441 { 00442 // concept requirements 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 * This is an SGI extension. 00454 * @ingroup SGIextensions 00455 * @doctodo 00456 */ 00457 template<typename _RandomAccessIterator, typename _StrictWeakOrdering> 00458 inline bool 00459 is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, 00460 _StrictWeakOrdering __comp) 00461 { 00462 // concept requirements 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 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00475 using std::is_sorted; 00476 #else 00477 // is_sorted, a predicated testing whether a range is sorted in 00478 // nondescending order. This is an extension, not part of the C++ 00479 // standard. 00480 00481 /** 00482 * This is an SGI extension. 00483 * @ingroup SGIextensions 00484 * @doctodo 00485 */ 00486 template<typename _ForwardIterator> 00487 bool 00488 is_sorted(_ForwardIterator __first, _ForwardIterator __last) 00489 { 00490 // concept requirements 00491 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 00492 __glibcxx_function_requires(_LessThanComparableConcept< 00493 typename iterator_traits<_ForwardIterator>::value_type>) 00494 __glibcxx_requires_valid_range(__first, __last); 00495 00496 if (__first == __last) 00497 return true; 00498 00499 _ForwardIterator __next = __first; 00500 for (++__next; __next != __last; __first = __next, ++__next) 00501 if (*__next < *__first) 00502 return false; 00503 return true; 00504 } 00505 00506 /** 00507 * This is an SGI extension. 00508 * @ingroup SGIextensions 00509 * @doctodo 00510 */ 00511 template<typename _ForwardIterator, typename _StrictWeakOrdering> 00512 bool 00513 is_sorted(_ForwardIterator __first, _ForwardIterator __last, 00514 _StrictWeakOrdering __comp) 00515 { 00516 // concept requirements 00517 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 00518 __glibcxx_function_requires(_BinaryPredicateConcept<_StrictWeakOrdering, 00519 typename iterator_traits<_ForwardIterator>::value_type, 00520 typename iterator_traits<_ForwardIterator>::value_type>) 00521 __glibcxx_requires_valid_range(__first, __last); 00522 00523 if (__first == __last) 00524 return true; 00525 00526 _ForwardIterator __next = __first; 00527 for (++__next; __next != __last; __first = __next, ++__next) 00528 if (__comp(*__next, *__first)) 00529 return false; 00530 return true; 00531 } 00532 #endif // __GXX_EXPERIMENTAL_CXX0X__ 00533 00534 /** 00535 * @brief Find the median of three values. 00536 * @param __a A value. 00537 * @param __b A value. 00538 * @param __c A value. 00539 * @return One of @p a, @p b or @p c. 00540 * 00541 * If @c {l,m,n} is some convolution of @p {a,b,c} such that @c l<=m<=n 00542 * then the value returned will be @c m. 00543 * This is an SGI extension. 00544 * @ingroup SGIextensions 00545 */ 00546 template<typename _Tp> 00547 const _Tp& 00548 __median(const _Tp& __a, const _Tp& __b, const _Tp& __c) 00549 { 00550 // concept requirements 00551 __glibcxx_function_requires(_LessThanComparableConcept<_Tp>) 00552 if (__a < __b) 00553 if (__b < __c) 00554 return __b; 00555 else if (__a < __c) 00556 return __c; 00557 else 00558 return __a; 00559 else if (__a < __c) 00560 return __a; 00561 else if (__b < __c) 00562 return __c; 00563 else 00564 return __b; 00565 } 00566 00567 /** 00568 * @brief Find the median of three values using a predicate for comparison. 00569 * @param __a A value. 00570 * @param __b A value. 00571 * @param __c A value. 00572 * @param __comp A binary predicate. 00573 * @return One of @p a, @p b or @p c. 00574 * 00575 * If @c {l,m,n} is some convolution of @p {a,b,c} such that @p comp(l,m) 00576 * and @p comp(m,n) are both true then the value returned will be @c m. 00577 * This is an SGI extension. 00578 * @ingroup SGIextensions 00579 */ 00580 template<typename _Tp, typename _Compare> 00581 const _Tp& 00582 __median(const _Tp& __a, const _Tp& __b, const _Tp& __c, _Compare __comp) 00583 { 00584 // concept requirements 00585 __glibcxx_function_requires(_BinaryFunctionConcept<_Compare, bool, 00586 _Tp, _Tp>) 00587 if (__comp(__a, __b)) 00588 if (__comp(__b, __c)) 00589 return __b; 00590 else if (__comp(__a, __c)) 00591 return __c; 00592 else 00593 return __a; 00594 else if (__comp(__a, __c)) 00595 return __a; 00596 else if (__comp(__b, __c)) 00597 return __c; 00598 else 00599 return __b; 00600 } 00601 00602 _GLIBCXX_END_NAMESPACE_VERSION 00603 } // namespace 00604 00605 #endif /* _EXT_ALGORITHM */