libstdc++
|
00001 // Algorithm extensions -*- C++ -*- 00002 00003 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009 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 _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx) 00065 00066 using std::ptrdiff_t; 00067 using std::min; 00068 using std::pair; 00069 using std::input_iterator_tag; 00070 using std::random_access_iterator_tag; 00071 using std::iterator_traits; 00072 00073 //-------------------------------------------------- 00074 // copy_n (not part of the C++ standard) 00075 00076 template<typename _InputIterator, typename _Size, typename _OutputIterator> 00077 pair<_InputIterator, _OutputIterator> 00078 __copy_n(_InputIterator __first, _Size __count, 00079 _OutputIterator __result, 00080 input_iterator_tag) 00081 { 00082 for ( ; __count > 0; --__count) 00083 { 00084 *__result = *__first; 00085 ++__first; 00086 ++__result; 00087 } 00088 return pair<_InputIterator, _OutputIterator>(__first, __result); 00089 } 00090 00091 template<typename _RAIterator, typename _Size, typename _OutputIterator> 00092 inline pair<_RAIterator, _OutputIterator> 00093 __copy_n(_RAIterator __first, _Size __count, 00094 _OutputIterator __result, 00095 random_access_iterator_tag) 00096 { 00097 _RAIterator __last = __first + __count; 00098 return pair<_RAIterator, _OutputIterator>(__last, std::copy(__first, 00099 __last, 00100 __result)); 00101 } 00102 00103 /** 00104 * @brief Copies the range [first,first+count) into [result,result+count). 00105 * @param first An input iterator. 00106 * @param count The number of elements to copy. 00107 * @param result An output iterator. 00108 * @return A std::pair composed of first+count and result+count. 00109 * 00110 * This is an SGI extension. 00111 * This inline function will boil down to a call to @c memmove whenever 00112 * possible. Failing that, if random access iterators are passed, then the 00113 * loop count will be known (and therefore a candidate for compiler 00114 * optimizations such as unrolling). 00115 * @ingroup SGIextensions 00116 */ 00117 template<typename _InputIterator, typename _Size, typename _OutputIterator> 00118 inline pair<_InputIterator, _OutputIterator> 00119 copy_n(_InputIterator __first, _Size __count, _OutputIterator __result) 00120 { 00121 // concept requirements 00122 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 00123 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 00124 typename iterator_traits<_InputIterator>::value_type>) 00125 00126 return __copy_n(__first, __count, __result, 00127 std::__iterator_category(__first)); 00128 } 00129 00130 template<typename _InputIterator1, typename _InputIterator2> 00131 int 00132 __lexicographical_compare_3way(_InputIterator1 __first1, 00133 _InputIterator1 __last1, 00134 _InputIterator2 __first2, 00135 _InputIterator2 __last2) 00136 { 00137 while (__first1 != __last1 && __first2 != __last2) 00138 { 00139 if (*__first1 < *__first2) 00140 return -1; 00141 if (*__first2 < *__first1) 00142 return 1; 00143 ++__first1; 00144 ++__first2; 00145 } 00146 if (__first2 == __last2) 00147 return !(__first1 == __last1); 00148 else 00149 return -1; 00150 } 00151 00152 inline int 00153 __lexicographical_compare_3way(const unsigned char* __first1, 00154 const unsigned char* __last1, 00155 const unsigned char* __first2, 00156 const unsigned char* __last2) 00157 { 00158 const ptrdiff_t __len1 = __last1 - __first1; 00159 const ptrdiff_t __len2 = __last2 - __first2; 00160 const int __result = __builtin_memcmp(__first1, __first2, 00161 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((const signed char*) __first1, 00172 (const signed char*) __last1, 00173 (const signed char*) __first2, 00174 (const signed char*) __last2); 00175 #else 00176 return __lexicographical_compare_3way((const unsigned char*) __first1, 00177 (const unsigned char*) __last1, 00178 (const unsigned char*) __first2, 00179 (const unsigned char*) __last2); 00180 #endif 00181 } 00182 00183 /** 00184 * @brief @c memcmp on steroids. 00185 * @param first1 An input iterator. 00186 * @param last1 An input iterator. 00187 * @param first2 An input iterator. 00188 * @param last2 An input iterator. 00189 * @return An int, as with @c memcmp. 00190 * 00191 * The return value will be less than zero if the first range is 00192 * "lexigraphically less than" the second, greater than zero if the second 00193 * range is "lexigraphically less than" the first, and zero otherwise. 00194 * This is an SGI extension. 00195 * @ingroup SGIextensions 00196 */ 00197 template<typename _InputIterator1, typename _InputIterator2> 00198 int 00199 lexicographical_compare_3way(_InputIterator1 __first1, 00200 _InputIterator1 __last1, 00201 _InputIterator2 __first2, 00202 _InputIterator2 __last2) 00203 { 00204 // concept requirements 00205 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 00206 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 00207 __glibcxx_function_requires(_LessThanComparableConcept< 00208 typename iterator_traits<_InputIterator1>::value_type>) 00209 __glibcxx_function_requires(_LessThanComparableConcept< 00210 typename iterator_traits<_InputIterator2>::value_type>) 00211 __glibcxx_requires_valid_range(__first1, __last1); 00212 __glibcxx_requires_valid_range(__first2, __last2); 00213 00214 return __lexicographical_compare_3way(__first1, __last1, __first2, 00215 __last2); 00216 } 00217 00218 // count and count_if: this version, whose return type is void, was present 00219 // in the HP STL, and is retained as an extension for backward compatibility. 00220 template<typename _InputIterator, typename _Tp, typename _Size> 00221 void 00222 count(_InputIterator __first, _InputIterator __last, 00223 const _Tp& __value, 00224 _Size& __n) 00225 { 00226 // concept requirements 00227 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 00228 __glibcxx_function_requires(_EqualityComparableConcept< 00229 typename iterator_traits<_InputIterator>::value_type >) 00230 __glibcxx_function_requires(_EqualityComparableConcept<_Tp>) 00231 __glibcxx_requires_valid_range(__first, __last); 00232 00233 for ( ; __first != __last; ++__first) 00234 if (*__first == __value) 00235 ++__n; 00236 } 00237 00238 template<typename _InputIterator, typename _Predicate, typename _Size> 00239 void 00240 count_if(_InputIterator __first, _InputIterator __last, 00241 _Predicate __pred, 00242 _Size& __n) 00243 { 00244 // concept requirements 00245 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 00246 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate, 00247 typename iterator_traits<_InputIterator>::value_type>) 00248 __glibcxx_requires_valid_range(__first, __last); 00249 00250 for ( ; __first != __last; ++__first) 00251 if (__pred(*__first)) 00252 ++__n; 00253 } 00254 00255 // random_sample and random_sample_n (extensions, not part of the standard). 00256 00257 /** 00258 * This is an SGI extension. 00259 * @ingroup SGIextensions 00260 * @doctodo 00261 */ 00262 template<typename _ForwardIterator, typename _OutputIterator, 00263 typename _Distance> 00264 _OutputIterator 00265 random_sample_n(_ForwardIterator __first, _ForwardIterator __last, 00266 _OutputIterator __out, const _Distance __n) 00267 { 00268 // concept requirements 00269 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 00270 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 00271 typename iterator_traits<_ForwardIterator>::value_type>) 00272 __glibcxx_requires_valid_range(__first, __last); 00273 00274 _Distance __remaining = std::distance(__first, __last); 00275 _Distance __m = min(__n, __remaining); 00276 00277 while (__m > 0) 00278 { 00279 if ((std::rand() % __remaining) < __m) 00280 { 00281 *__out = *__first; 00282 ++__out; 00283 --__m; 00284 } 00285 --__remaining; 00286 ++__first; 00287 } 00288 return __out; 00289 } 00290 00291 /** 00292 * This is an SGI extension. 00293 * @ingroup SGIextensions 00294 * @doctodo 00295 */ 00296 template<typename _ForwardIterator, typename _OutputIterator, 00297 typename _Distance, typename _RandomNumberGenerator> 00298 _OutputIterator 00299 random_sample_n(_ForwardIterator __first, _ForwardIterator __last, 00300 _OutputIterator __out, const _Distance __n, 00301 _RandomNumberGenerator& __rand) 00302 { 00303 // concept requirements 00304 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 00305 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 00306 typename iterator_traits<_ForwardIterator>::value_type>) 00307 __glibcxx_function_requires(_UnaryFunctionConcept< 00308 _RandomNumberGenerator, _Distance, _Distance>) 00309 __glibcxx_requires_valid_range(__first, __last); 00310 00311 _Distance __remaining = std::distance(__first, __last); 00312 _Distance __m = min(__n, __remaining); 00313 00314 while (__m > 0) 00315 { 00316 if (__rand(__remaining) < __m) 00317 { 00318 *__out = *__first; 00319 ++__out; 00320 --__m; 00321 } 00322 --__remaining; 00323 ++__first; 00324 } 00325 return __out; 00326 } 00327 00328 template<typename _InputIterator, typename _RandomAccessIterator, 00329 typename _Distance> 00330 _RandomAccessIterator 00331 __random_sample(_InputIterator __first, _InputIterator __last, 00332 _RandomAccessIterator __out, 00333 const _Distance __n) 00334 { 00335 _Distance __m = 0; 00336 _Distance __t = __n; 00337 for ( ; __first != __last && __m < __n; ++__m, ++__first) 00338 __out[__m] = *__first; 00339 00340 while (__first != __last) 00341 { 00342 ++__t; 00343 _Distance __M = std::rand() % (__t); 00344 if (__M < __n) 00345 __out[__M] = *__first; 00346 ++__first; 00347 } 00348 return __out + __m; 00349 } 00350 00351 template<typename _InputIterator, typename _RandomAccessIterator, 00352 typename _RandomNumberGenerator, typename _Distance> 00353 _RandomAccessIterator 00354 __random_sample(_InputIterator __first, _InputIterator __last, 00355 _RandomAccessIterator __out, 00356 _RandomNumberGenerator& __rand, 00357 const _Distance __n) 00358 { 00359 // concept requirements 00360 __glibcxx_function_requires(_UnaryFunctionConcept< 00361 _RandomNumberGenerator, _Distance, _Distance>) 00362 00363 _Distance __m = 0; 00364 _Distance __t = __n; 00365 for ( ; __first != __last && __m < __n; ++__m, ++__first) 00366 __out[__m] = *__first; 00367 00368 while (__first != __last) 00369 { 00370 ++__t; 00371 _Distance __M = __rand(__t); 00372 if (__M < __n) 00373 __out[__M] = *__first; 00374 ++__first; 00375 } 00376 return __out + __m; 00377 } 00378 00379 /** 00380 * This is an SGI extension. 00381 * @ingroup SGIextensions 00382 * @doctodo 00383 */ 00384 template<typename _InputIterator, typename _RandomAccessIterator> 00385 inline _RandomAccessIterator 00386 random_sample(_InputIterator __first, _InputIterator __last, 00387 _RandomAccessIterator __out_first, 00388 _RandomAccessIterator __out_last) 00389 { 00390 // concept requirements 00391 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 00392 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 00393 _RandomAccessIterator>) 00394 __glibcxx_requires_valid_range(__first, __last); 00395 __glibcxx_requires_valid_range(__out_first, __out_last); 00396 00397 return __random_sample(__first, __last, 00398 __out_first, __out_last - __out_first); 00399 } 00400 00401 /** 00402 * This is an SGI extension. 00403 * @ingroup SGIextensions 00404 * @doctodo 00405 */ 00406 template<typename _InputIterator, typename _RandomAccessIterator, 00407 typename _RandomNumberGenerator> 00408 inline _RandomAccessIterator 00409 random_sample(_InputIterator __first, _InputIterator __last, 00410 _RandomAccessIterator __out_first, 00411 _RandomAccessIterator __out_last, 00412 _RandomNumberGenerator& __rand) 00413 { 00414 // concept requirements 00415 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 00416 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 00417 _RandomAccessIterator>) 00418 __glibcxx_requires_valid_range(__first, __last); 00419 __glibcxx_requires_valid_range(__out_first, __out_last); 00420 00421 return __random_sample(__first, __last, 00422 __out_first, __rand, 00423 __out_last - __out_first); 00424 } 00425 00426 /** 00427 * This is an SGI extension. 00428 * @ingroup SGIextensions 00429 * @doctodo 00430 */ 00431 template<typename _RandomAccessIterator> 00432 inline bool 00433 is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) 00434 { 00435 // concept requirements 00436 __glibcxx_function_requires(_RandomAccessIteratorConcept< 00437 _RandomAccessIterator>) 00438 __glibcxx_function_requires(_LessThanComparableConcept< 00439 typename iterator_traits<_RandomAccessIterator>::value_type>) 00440 __glibcxx_requires_valid_range(__first, __last); 00441 00442 return std::__is_heap(__first, __last - __first); 00443 } 00444 00445 /** 00446 * This is an SGI extension. 00447 * @ingroup SGIextensions 00448 * @doctodo 00449 */ 00450 template<typename _RandomAccessIterator, typename _StrictWeakOrdering> 00451 inline bool 00452 is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, 00453 _StrictWeakOrdering __comp) 00454 { 00455 // concept requirements 00456 __glibcxx_function_requires(_RandomAccessIteratorConcept< 00457 _RandomAccessIterator>) 00458 __glibcxx_function_requires(_BinaryPredicateConcept<_StrictWeakOrdering, 00459 typename iterator_traits<_RandomAccessIterator>::value_type, 00460 typename iterator_traits<_RandomAccessIterator>::value_type>) 00461 __glibcxx_requires_valid_range(__first, __last); 00462 00463 return std::__is_heap(__first, __comp, __last - __first); 00464 } 00465 00466 // is_sorted, a predicated testing whether a range is sorted in 00467 // nondescending order. This is an extension, not part of the C++ 00468 // standard. 00469 00470 /** 00471 * This is an SGI extension. 00472 * @ingroup SGIextensions 00473 * @doctodo 00474 */ 00475 template<typename _ForwardIterator> 00476 bool 00477 is_sorted(_ForwardIterator __first, _ForwardIterator __last) 00478 { 00479 // concept requirements 00480 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 00481 __glibcxx_function_requires(_LessThanComparableConcept< 00482 typename iterator_traits<_ForwardIterator>::value_type>) 00483 __glibcxx_requires_valid_range(__first, __last); 00484 00485 if (__first == __last) 00486 return true; 00487 00488 _ForwardIterator __next = __first; 00489 for (++__next; __next != __last; __first = __next, ++__next) 00490 if (*__next < *__first) 00491 return false; 00492 return true; 00493 } 00494 00495 /** 00496 * This is an SGI extension. 00497 * @ingroup SGIextensions 00498 * @doctodo 00499 */ 00500 template<typename _ForwardIterator, typename _StrictWeakOrdering> 00501 bool 00502 is_sorted(_ForwardIterator __first, _ForwardIterator __last, 00503 _StrictWeakOrdering __comp) 00504 { 00505 // concept requirements 00506 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 00507 __glibcxx_function_requires(_BinaryPredicateConcept<_StrictWeakOrdering, 00508 typename iterator_traits<_ForwardIterator>::value_type, 00509 typename iterator_traits<_ForwardIterator>::value_type>) 00510 __glibcxx_requires_valid_range(__first, __last); 00511 00512 if (__first == __last) 00513 return true; 00514 00515 _ForwardIterator __next = __first; 00516 for (++__next; __next != __last; __first = __next, ++__next) 00517 if (__comp(*__next, *__first)) 00518 return false; 00519 return true; 00520 } 00521 00522 _GLIBCXX_END_NAMESPACE 00523 00524 #endif /* _EXT_ALGORITHM */