algorithm

Go to the documentation of this file.
00001 // Algorithm extensions -*- C++ -*- 00002 00003 // Copyright (C) 2001, 2002 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 2, 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 // You should have received a copy of the GNU General Public License along 00017 // with this library; see the file COPYING. If not, write to the Free 00018 // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, 00019 // USA. 00020 00021 // As a special exception, you may use this file as part of a free software 00022 // library without restriction. Specifically, if other files instantiate 00023 // templates or use macros or inline functions from this file, or you compile 00024 // this file and link it with other files to produce an executable, this 00025 // file does not by itself cause the resulting executable to be covered by 00026 // the GNU General Public License. This exception does not however 00027 // invalidate any other reasons why the executable file might be covered by 00028 // the GNU General Public License. 00029 00030 /* 00031 * 00032 * Copyright (c) 1994 00033 * Hewlett-Packard Company 00034 * 00035 * Permission to use, copy, modify, distribute and sell this software 00036 * and its documentation for any purpose is hereby granted without fee, 00037 * provided that the above copyright notice appear in all copies and 00038 * that both that copyright notice and this permission notice appear 00039 * in supporting documentation. Hewlett-Packard Company makes no 00040 * representations about the suitability of this software for any 00041 * purpose. It is provided "as is" without express or implied warranty. 00042 * 00043 * 00044 * Copyright (c) 1996 00045 * Silicon Graphics Computer Systems, Inc. 00046 * 00047 * Permission to use, copy, modify, distribute and sell this software 00048 * and its documentation for any purpose is hereby granted without fee, 00049 * provided that the above copyright notice appear in all copies and 00050 * that both that copyright notice and this permission notice appear 00051 * in supporting documentation. Silicon Graphics makes no 00052 * representations about the suitability of this software for any 00053 * purpose. It is provided "as is" without express or implied warranty. 00054 */ 00055 00056 /** @file ext/algorithm 00057 * This file is a GNU extension to the Standard C++ Library (possibly 00058 * containing extensions from the HP/SGI STL subset). You should only 00059 * include this header if you are using GCC 3 or later. 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 // copy_n (not part of the C++ standard) 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 * @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 _InputIter, typename _Size, typename _OutputIter> 00120 inline pair<_InputIter, _OutputIter> 00121 copy_n(_InputIter __first, _Size __count, _OutputIter __result) 00122 { 00123 // concept requirements 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 * @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 * "lexigraphically less than" the second, greater than zero if the second 00194 * range is "lexigraphically less than" the first, and zero otherwise. 00195 * This is an SGI extension. 00196 * @ingroup SGIextensions 00197 */ 00198 template<typename _InputIter1, typename _InputIter2> 00199 int 00200 lexicographical_compare_3way(_InputIter1 __first1, _InputIter1 __last1, 00201 _InputIter2 __first2, _InputIter2 __last2) 00202 { 00203 // concept requirements 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 // count and count_if: this version, whose return type is void, was present 00215 // in the HP STL, and is retained as an extension for backward compatibility. 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 // concept requirements 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 // concept requirements 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 // random_sample and random_sample_n (extensions, not part of the standard). 00249 00250 /** 00251 * This is an SGI extension. 00252 * @ingroup SGIextensions 00253 * @doctodo 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 // concept requirements 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 * This is an SGI extension. 00283 * @ingroup SGIextensions 00284 * @doctodo 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 // concept requirements 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 // concept requirements 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 * This is an SGI extension. 00368 * @ingroup SGIextensions 00369 * @doctodo 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 // concept requirements 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 * This is an SGI extension. 00387 * @ingroup SGIextensions 00388 * @doctodo 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 // concept requirements 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 // is_heap, a predicate testing whether or not a range is 00408 // a heap. This function is an extension, not part of the C++ 00409 // standard. 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 * This is an SGI extension. 00443 * @ingroup SGIextensions 00444 * @doctodo 00445 */ 00446 template<typename _RandomAccessIter> 00447 inline bool 00448 is_heap(_RandomAccessIter __first, _RandomAccessIter __last) 00449 { 00450 // concept requirements 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 * This is an SGI extension. 00460 * @ingroup SGIextensions 00461 * @doctodo 00462 */ 00463 template<typename _RandomAccessIter, typename _StrictWeakOrdering> 00464 inline bool 00465 is_heap(_RandomAccessIter __first, _RandomAccessIter __last, 00466 _StrictWeakOrdering __comp) 00467 { 00468 // concept requirements 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 // 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 _ForwardIter> 00487 bool 00488 is_sorted(_ForwardIter __first, _ForwardIter __last) 00489 { 00490 // concept requirements 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 * This is an SGI extension. 00509 * @ingroup SGIextensions 00510 * @doctodo 00511 */ 00512 template<typename _ForwardIter, typename _StrictWeakOrdering> 00513 bool 00514 is_sorted(_ForwardIter __first, _ForwardIter __last, _StrictWeakOrdering __comp) 00515 { 00516 // concept requirements 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 } // namespace __gnu_cxx 00535 00536 #endif /* _EXT_ALGORITHM */

Generated on Wed Aug 4 21:43:08 2004 for libstdc++-v3 Source by doxygen 1.3.8