libstdc++
|
00001 // Algorithm extensions -*- C++ -*- 00002 00003 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010 00004 // Free Software Foundation, Inc. 00005 // 00006 // This file is part of the GNU ISO C++ Library. This library is free 00007 // software; you can redistribute it and/or modify it under the 00008 // terms of the GNU General Public License as published by the 00009 // Free Software Foundation; either version 3, or (at your option) 00010 // any later version. 00011 00012 // This library is distributed in the hope that it will be useful, 00013 // but WITHOUT ANY WARRANTY; without even the implied warranty of 00014 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00015 // GNU General Public License for more details. 00016 00017 // Under Section 7 of GPL version 3, you are granted additional 00018 // permissions described in the GCC Runtime Library Exception, version 00019 // 3.1, as published by the Free Software Foundation. 00020 00021 // You should have received a copy of the GNU General Public License and 00022 // a copy of the GCC Runtime Library Exception along with this program; 00023 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 00024 // <http://www.gnu.org/licenses/>. 00025 00026 /* 00027 * 00028 * Copyright (c) 1994 00029 * Hewlett-Packard Company 00030 * 00031 * Permission to use, copy, modify, distribute and sell this software 00032 * and its documentation for any purpose is hereby granted without fee, 00033 * provided that the above copyright notice appear in all copies and 00034 * that both that copyright notice and this permission notice appear 00035 * in supporting documentation. Hewlett-Packard Company makes no 00036 * representations about the suitability of this software for any 00037 * purpose. It is provided "as is" without express or implied warranty. 00038 * 00039 * 00040 * Copyright (c) 1996 00041 * Silicon Graphics Computer Systems, Inc. 00042 * 00043 * Permission to use, copy, modify, distribute and sell this software 00044 * and its documentation for any purpose is hereby granted without fee, 00045 * provided that the above copyright notice appear in all copies and 00046 * that both that copyright notice and this permission notice appear 00047 * in supporting documentation. Silicon Graphics makes no 00048 * representations about the suitability of this software for any 00049 * purpose. It is provided "as is" without express or implied warranty. 00050 */ 00051 00052 /** @file ext/algorithm 00053 * This file is a GNU extension to the Standard C++ Library (possibly 00054 * containing extensions from the HP/SGI STL subset). 00055 */ 00056 00057 #ifndef _EXT_ALGORITHM 00058 #define _EXT_ALGORITHM 1 00059 00060 #pragma GCC system_header 00061 00062 #include <algorithm> 00063 00064 namespace __gnu_cxx _GLIBCXX_VISIBILITY(default) 00065 { 00066 _GLIBCXX_BEGIN_NAMESPACE_VERSION 00067 00068 using std::ptrdiff_t; 00069 using std::min; 00070 using std::pair; 00071 using std::input_iterator_tag; 00072 using std::random_access_iterator_tag; 00073 using std::iterator_traits; 00074 00075 //-------------------------------------------------- 00076 // copy_n (not part of the C++ standard) 00077 00078 template<typename _InputIterator, typename _Size, typename _OutputIterator> 00079 pair<_InputIterator, _OutputIterator> 00080 __copy_n(_InputIterator __first, _Size __count, 00081 _OutputIterator __result, 00082 input_iterator_tag) 00083 { 00084 for ( ; __count > 0; --__count) 00085 { 00086 *__result = *__first; 00087 ++__first; 00088 ++__result; 00089 } 00090 return pair<_InputIterator, _OutputIterator>(__first, __result); 00091 } 00092 00093 template<typename _RAIterator, typename _Size, typename _OutputIterator> 00094 inline pair<_RAIterator, _OutputIterator> 00095 __copy_n(_RAIterator __first, _Size __count, 00096 _OutputIterator __result, 00097 random_access_iterator_tag) 00098 { 00099 _RAIterator __last = __first + __count; 00100 return pair<_RAIterator, _OutputIterator>(__last, std::copy(__first, 00101 __last, 00102 __result)); 00103 } 00104 00105 /** 00106 * @brief Copies the range [first,first+count) into [result,result+count). 00107 * @param first An input iterator. 00108 * @param count The number of elements to copy. 00109 * @param result An output iterator. 00110 * @return A std::pair composed of first+count and result+count. 00111 * 00112 * This is an SGI extension. 00113 * This inline function will boil down to a call to @c memmove whenever 00114 * possible. Failing that, if random access iterators are passed, then the 00115 * loop count will be known (and therefore a candidate for compiler 00116 * optimizations such as unrolling). 00117 * @ingroup SGIextensions 00118 */ 00119 template<typename _InputIterator, typename _Size, typename _OutputIterator> 00120 inline pair<_InputIterator, _OutputIterator> 00121 copy_n(_InputIterator __first, _Size __count, _OutputIterator __result) 00122 { 00123 // concept requirements 00124 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 00125 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 00126 typename iterator_traits<_InputIterator>::value_type>) 00127 00128 return __gnu_cxx::__copy_n(__first, __count, __result, 00129 std::__iterator_category(__first)); 00130 } 00131 00132 template<typename _InputIterator1, typename _InputIterator2> 00133 int 00134 __lexicographical_compare_3way(_InputIterator1 __first1, 00135 _InputIterator1 __last1, 00136 _InputIterator2 __first2, 00137 _InputIterator2 __last2) 00138 { 00139 while (__first1 != __last1 && __first2 != __last2) 00140 { 00141 if (*__first1 < *__first2) 00142 return -1; 00143 if (*__first2 < *__first1) 00144 return 1; 00145 ++__first1; 00146 ++__first2; 00147 } 00148 if (__first2 == __last2) 00149 return !(__first1 == __last1); 00150 else 00151 return -1; 00152 } 00153 00154 inline int 00155 __lexicographical_compare_3way(const unsigned char* __first1, 00156 const unsigned char* __last1, 00157 const unsigned char* __first2, 00158 const unsigned char* __last2) 00159 { 00160 const ptrdiff_t __len1 = __last1 - __first1; 00161 const ptrdiff_t __len2 = __last2 - __first2; 00162 const int __result = __builtin_memcmp(__first1, __first2, 00163 min(__len1, __len2)); 00164 return __result != 0 ? __result 00165 : (__len1 == __len2 ? 0 : (__len1 < __len2 ? -1 : 1)); 00166 } 00167 00168 inline int 00169 __lexicographical_compare_3way(const char* __first1, const char* __last1, 00170 const char* __first2, const char* __last2) 00171 { 00172 #if CHAR_MAX == SCHAR_MAX 00173 return __lexicographical_compare_3way((const signed char*) __first1, 00174 (const signed char*) __last1, 00175 (const signed char*) __first2, 00176 (const signed char*) __last2); 00177 #else 00178 return __lexicographical_compare_3way((const unsigned char*) __first1, 00179 (const unsigned char*) __last1, 00180 (const unsigned char*) __first2, 00181 (const unsigned char*) __last2); 00182 #endif 00183 } 00184 00185 /** 00186 * @brief @c memcmp on steroids. 00187 * @param first1 An input iterator. 00188 * @param last1 An input iterator. 00189 * @param first2 An input iterator. 00190 * @param last2 An input iterator. 00191 * @return An int, as with @c memcmp. 00192 * 00193 * The return value will be less than zero if the first range is 00194 * <em>lexigraphically less than</em> the second, greater than zero 00195 * if the second range is <em>lexigraphically less than</em> the 00196 * first, and zero otherwise. 00197 * This is an SGI extension. 00198 * @ingroup SGIextensions 00199 */ 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 // concept requirements 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 // count and count_if: this version, whose return type is void, was present 00222 // in the HP STL, and is retained as an extension for backward compatibility. 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 // concept requirements 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 // concept requirements 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 // random_sample and random_sample_n (extensions, not part of the standard). 00259 00260 /** 00261 * This is an SGI extension. 00262 * @ingroup SGIextensions 00263 * @doctodo 00264 */ 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 // concept requirements 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 00294 /** 00295 * This is an SGI extension. 00296 * @ingroup SGIextensions 00297 * @doctodo 00298 */ 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 // concept requirements 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 // concept requirements 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 00382 /** 00383 * This is an SGI extension. 00384 * @ingroup SGIextensions 00385 * @doctodo 00386 */ 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 // concept requirements 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 00404 /** 00405 * This is an SGI extension. 00406 * @ingroup SGIextensions 00407 * @doctodo 00408 */ 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 // concept requirements 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 00429 /** 00430 * This is an SGI extension. 00431 * @ingroup SGIextensions 00432 * @doctodo 00433 */ 00434 template<typename _RandomAccessIterator> 00435 inline bool 00436 is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) 00437 { 00438 // concept requirements 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 00448 /** 00449 * This is an SGI extension. 00450 * @ingroup SGIextensions 00451 * @doctodo 00452 */ 00453 template<typename _RandomAccessIterator, typename _StrictWeakOrdering> 00454 inline bool 00455 is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, 00456 _StrictWeakOrdering __comp) 00457 { 00458 // concept requirements 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 // is_sorted, a predicated testing whether a range is sorted in 00470 // nondescending order. This is an extension, not part of the C++ 00471 // standard. 00472 00473 /** 00474 * This is an SGI extension. 00475 * @ingroup SGIextensions 00476 * @doctodo 00477 */ 00478 template<typename _ForwardIterator> 00479 bool 00480 is_sorted(_ForwardIterator __first, _ForwardIterator __last) 00481 { 00482 // concept requirements 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 00498 /** 00499 * This is an SGI extension. 00500 * @ingroup SGIextensions 00501 * @doctodo 00502 */ 00503 template<typename _ForwardIterator, typename _StrictWeakOrdering> 00504 bool 00505 is_sorted(_ForwardIterator __first, _ForwardIterator __last, 00506 _StrictWeakOrdering __comp) 00507 { 00508 // concept requirements 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 * @brief Find the median of three values. 00527 * @param a A value. 00528 * @param b A value. 00529 * @param c A value. 00530 * @return One of @p a, @p b or @p c. 00531 * 00532 * If @c {l,m,n} is some convolution of @p {a,b,c} such that @c l<=m<=n 00533 * then the value returned will be @c m. 00534 * This is an SGI extension. 00535 * @ingroup SGIextensions 00536 */ 00537 template<typename _Tp> 00538 const _Tp& 00539 __median(const _Tp& __a, const _Tp& __b, const _Tp& __c) 00540 { 00541 // concept requirements 00542 __glibcxx_function_requires(_LessThanComparableConcept<_Tp>) 00543 if (__a < __b) 00544 if (__b < __c) 00545 return __b; 00546 else if (__a < __c) 00547 return __c; 00548 else 00549 return __a; 00550 else if (__a < __c) 00551 return __a; 00552 else if (__b < __c) 00553 return __c; 00554 else 00555 return __b; 00556 } 00557 00558 /** 00559 * @brief Find the median of three values using a predicate for comparison. 00560 * @param a A value. 00561 * @param b A value. 00562 * @param c A value. 00563 * @param comp A binary predicate. 00564 * @return One of @p a, @p b or @p c. 00565 * 00566 * If @c {l,m,n} is some convolution of @p {a,b,c} such that @p comp(l,m) 00567 * and @p comp(m,n) are both true then the value returned will be @c m. 00568 * This is an SGI extension. 00569 * @ingroup SGIextensions 00570 */ 00571 template<typename _Tp, typename _Compare> 00572 const _Tp& 00573 __median(const _Tp& __a, const _Tp& __b, const _Tp& __c, _Compare __comp) 00574 { 00575 // concept requirements 00576 __glibcxx_function_requires(_BinaryFunctionConcept<_Compare, bool, 00577 _Tp, _Tp>) 00578 if (__comp(__a, __b)) 00579 if (__comp(__b, __c)) 00580 return __b; 00581 else if (__comp(__a, __c)) 00582 return __c; 00583 else 00584 return __a; 00585 else if (__comp(__a, __c)) 00586 return __a; 00587 else if (__comp(__b, __c)) 00588 return __c; 00589 else 00590 return __b; 00591 } 00592 00593 _GLIBCXX_END_NAMESPACE_VERSION 00594 } // namespace 00595 00596 #endif /* _EXT_ALGORITHM */