ext/algorithm

Go to the documentation of this file.
00001 // Algorithm extensions -*- C++ -*-
00002 
00003 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007
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 2, 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 // You should have received a copy of the GNU General Public License along
00018 // with this library; see the file COPYING.  If not, write to the Free
00019 // Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
00020 // USA.
00021 
00022 // As a special exception, you may use this file as part of a free software
00023 // library without restriction.  Specifically, if other files instantiate
00024 // templates or use macros or inline functions from this file, or you compile
00025 // this file and link it with other files to produce an executable, this
00026 // file does not by itself cause the resulting executable to be covered by
00027 // the GNU General Public License.  This exception does not however
00028 // invalidate any other reasons why the executable file might be covered by
00029 // the GNU General Public License.
00030 
00031 /*
00032  *
00033  * Copyright (c) 1994
00034  * Hewlett-Packard Company
00035  *
00036  * Permission to use, copy, modify, distribute and sell this software
00037  * and its documentation for any purpose is hereby granted without fee,
00038  * provided that the above copyright notice appear in all copies and
00039  * that both that copyright notice and this permission notice appear
00040  * in supporting documentation.  Hewlett-Packard Company makes no
00041  * representations about the suitability of this software for any
00042  * purpose.  It is provided "as is" without express or implied warranty.
00043  *
00044  *
00045  * Copyright (c) 1996
00046  * Silicon Graphics Computer Systems, Inc.
00047  *
00048  * Permission to use, copy, modify, distribute and sell this software
00049  * and its documentation for any purpose is hereby granted without fee,
00050  * provided that the above copyright notice appear in all copies and
00051  * that both that copyright notice and this permission notice appear
00052  * in supporting documentation.  Silicon Graphics makes no
00053  * representations about the suitability of this software for any
00054  * purpose.  It is provided "as is" without express or implied warranty.
00055  */
00056 
00057 /** @file ext/algorithm
00058  *  This file is a GNU extension to the Standard C++ Library (possibly
00059  *  containing extensions from the HP/SGI STL subset).
00060  */
00061 
00062 #ifndef _EXT_ALGORITHM
00063 #define _EXT_ALGORITHM 1
00064 
00065 #pragma GCC system_header
00066 
00067 #include <algorithm>
00068 
00069 _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx)
00070 
00071   using std::ptrdiff_t;
00072   using std::min;
00073   using std::pair;
00074   using std::input_iterator_tag;
00075   using std::random_access_iterator_tag;
00076   using std::iterator_traits;
00077 
00078   //--------------------------------------------------
00079   // copy_n (not part of the C++ standard)
00080 
00081   template<typename _InputIterator, typename _Size, typename _OutputIterator>
00082     pair<_InputIterator, _OutputIterator>
00083     __copy_n(_InputIterator __first, _Size __count,
00084          _OutputIterator __result,
00085          input_iterator_tag)
00086     {
00087       for ( ; __count > 0; --__count)
00088     {
00089       *__result = *__first;
00090       ++__first;
00091       ++__result;
00092     }
00093       return pair<_InputIterator, _OutputIterator>(__first, __result);
00094     }
00095 
00096   template<typename _RAIterator, typename _Size, typename _OutputIterator>
00097     inline pair<_RAIterator, _OutputIterator>
00098     __copy_n(_RAIterator __first, _Size __count,
00099          _OutputIterator __result,
00100          random_access_iterator_tag)
00101     {
00102       _RAIterator __last = __first + __count;
00103       return pair<_RAIterator, _OutputIterator>(__last, std::copy(__first,
00104                                   __last,
00105                                   __result));
00106     }
00107 
00108   /**
00109    *  @brief Copies the range [first,first+count) into [result,result+count).
00110    *  @param  first  An input iterator.
00111    *  @param  count  The number of elements to copy.
00112    *  @param  result An output iterator.
00113    *  @return   A std::pair composed of first+count and result+count.
00114    *
00115    *  This is an SGI extension.
00116    *  This inline function will boil down to a call to @c memmove whenever
00117    *  possible.  Failing that, if random access iterators are passed, then the
00118    *  loop count will be known (and therefore a candidate for compiler
00119    *  optimizations such as unrolling).
00120    *  @ingroup SGIextensions
00121   */
00122   template<typename _InputIterator, typename _Size, typename _OutputIterator>
00123     inline pair<_InputIterator, _OutputIterator>
00124     copy_n(_InputIterator __first, _Size __count, _OutputIterator __result)
00125     {
00126       // concept requirements
00127       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
00128       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
00129         typename iterator_traits<_InputIterator>::value_type>)
00130 
00131       return __copy_n(__first, __count, __result,
00132               std::__iterator_category(__first));
00133     }
00134 
00135   template<typename _InputIterator1, typename _InputIterator2>
00136     int
00137     __lexicographical_compare_3way(_InputIterator1 __first1,
00138                    _InputIterator1 __last1,
00139                    _InputIterator2 __first2,
00140                    _InputIterator2 __last2)
00141     {
00142       while (__first1 != __last1 && __first2 != __last2)
00143     {
00144       if (*__first1 < *__first2)
00145         return -1;
00146       if (*__first2 < *__first1)
00147         return 1;
00148       ++__first1;
00149       ++__first2;
00150     }
00151       if (__first2 == __last2)
00152     return !(__first1 == __last1);
00153       else
00154     return -1;
00155     }
00156 
00157   inline int
00158   __lexicographical_compare_3way(const unsigned char* __first1,
00159                  const unsigned char* __last1,
00160                  const unsigned char* __first2,
00161                  const unsigned char* __last2)
00162   {
00163     const ptrdiff_t __len1 = __last1 - __first1;
00164     const ptrdiff_t __len2 = __last2 - __first2;
00165     const int __result = __builtin_memcmp(__first1, __first2,
00166                       min(__len1, __len2));
00167     return __result != 0 ? __result
00168              : (__len1 == __len2 ? 0 : (__len1 < __len2 ? -1 : 1));
00169   }
00170 
00171   inline int
00172   __lexicographical_compare_3way(const char* __first1, const char* __last1,
00173                  const char* __first2, const char* __last2)
00174   {
00175 #if CHAR_MAX == SCHAR_MAX
00176     return __lexicographical_compare_3way((const signed char*) __first1,
00177                       (const signed char*) __last1,
00178                       (const signed char*) __first2,
00179                       (const signed char*) __last2);
00180 #else
00181     return __lexicographical_compare_3way((const unsigned char*) __first1,
00182                       (const unsigned char*) __last1,
00183                       (const unsigned char*) __first2,
00184                       (const unsigned char*) __last2);
00185 #endif
00186   }
00187 
00188   /**
00189    *  @brief @c memcmp on steroids.
00190    *  @param  first1  An input iterator.
00191    *  @param  last1   An input iterator.
00192    *  @param  first2  An input iterator.
00193    *  @param  last2   An input iterator.
00194    *  @return   An int, as with @c memcmp.
00195    *
00196    *  The return value will be less than zero if the first range is
00197    *  "lexigraphically less than" the second, greater than zero if the second
00198    *  range is "lexigraphically less than" the first, and zero otherwise.
00199    *  This is an SGI extension.
00200    *  @ingroup SGIextensions
00201   */
00202   template<typename _InputIterator1, typename _InputIterator2>
00203     int
00204     lexicographical_compare_3way(_InputIterator1 __first1,
00205                  _InputIterator1 __last1,
00206                  _InputIterator2 __first2,
00207                  _InputIterator2 __last2)
00208     {
00209       // concept requirements
00210       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
00211       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
00212       __glibcxx_function_requires(_LessThanComparableConcept<
00213         typename iterator_traits<_InputIterator1>::value_type>)
00214       __glibcxx_function_requires(_LessThanComparableConcept<
00215         typename iterator_traits<_InputIterator2>::value_type>)
00216       __glibcxx_requires_valid_range(__first1, __last1);
00217       __glibcxx_requires_valid_range(__first2, __last2);
00218 
00219       return __lexicographical_compare_3way(__first1, __last1, __first2,
00220                         __last2);
00221     }
00222 
00223   // count and count_if: this version, whose return type is void, was present
00224   // in the HP STL, and is retained as an extension for backward compatibility.
00225   template<typename _InputIterator, typename _Tp, typename _Size>
00226     void
00227     count(_InputIterator __first, _InputIterator __last,
00228       const _Tp& __value,
00229       _Size& __n)
00230     {
00231       // concept requirements
00232       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
00233       __glibcxx_function_requires(_EqualityComparableConcept<
00234         typename iterator_traits<_InputIterator>::value_type >)
00235       __glibcxx_function_requires(_EqualityComparableConcept<_Tp>)
00236       __glibcxx_requires_valid_range(__first, __last);
00237 
00238       for ( ; __first != __last; ++__first)
00239     if (*__first == __value)
00240       ++__n;
00241     }
00242 
00243   template<typename _InputIterator, typename _Predicate, typename _Size>
00244     void
00245     count_if(_InputIterator __first, _InputIterator __last,
00246          _Predicate __pred,
00247          _Size& __n)
00248     {
00249       // concept requirements
00250       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
00251       __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
00252         typename iterator_traits<_InputIterator>::value_type>)
00253       __glibcxx_requires_valid_range(__first, __last);
00254 
00255       for ( ; __first != __last; ++__first)
00256     if (__pred(*__first))
00257       ++__n;
00258     }
00259 
00260   // random_sample and random_sample_n (extensions, not part of the standard).
00261 
00262   /**
00263    *  This is an SGI extension.
00264    *  @ingroup SGIextensions
00265    *  @doctodo
00266   */
00267   template<typename _ForwardIterator, typename _OutputIterator,
00268        typename _Distance>
00269     _OutputIterator
00270     random_sample_n(_ForwardIterator __first, _ForwardIterator __last,
00271                     _OutputIterator __out, const _Distance __n)
00272     {
00273       // concept requirements
00274       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
00275       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
00276         typename iterator_traits<_ForwardIterator>::value_type>)
00277       __glibcxx_requires_valid_range(__first, __last);
00278 
00279       _Distance __remaining = std::distance(__first, __last);
00280       _Distance __m = min(__n, __remaining);
00281 
00282       while (__m > 0)
00283     {
00284       if ((std::rand() % __remaining) < __m)
00285         {
00286           *__out = *__first;
00287           ++__out;
00288           --__m;
00289         }
00290       --__remaining;
00291       ++__first;
00292     }
00293       return __out;
00294     }
00295 
00296   /**
00297    *  This is an SGI extension.
00298    *  @ingroup SGIextensions
00299    *  @doctodo
00300   */
00301   template<typename _ForwardIterator, typename _OutputIterator,
00302        typename _Distance, typename _RandomNumberGenerator>
00303     _OutputIterator
00304     random_sample_n(_ForwardIterator __first, _ForwardIterator __last,
00305                    _OutputIterator __out, const _Distance __n,
00306            _RandomNumberGenerator& __rand)
00307     {
00308       // concept requirements
00309       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
00310       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
00311         typename iterator_traits<_ForwardIterator>::value_type>)
00312       __glibcxx_function_requires(_UnaryFunctionConcept<
00313         _RandomNumberGenerator, _Distance, _Distance>)
00314       __glibcxx_requires_valid_range(__first, __last);
00315 
00316       _Distance __remaining = std::distance(__first, __last);
00317       _Distance __m = min(__n, __remaining);
00318 
00319       while (__m > 0)
00320     {
00321       if (__rand(__remaining) < __m)
00322         {
00323           *__out = *__first;
00324           ++__out;
00325           --__m;
00326         }
00327       --__remaining;
00328       ++__first;
00329     }
00330       return __out;
00331     }
00332 
00333   template<typename _InputIterator, typename _RandomAccessIterator,
00334        typename _Distance>
00335     _RandomAccessIterator
00336     __random_sample(_InputIterator __first, _InputIterator __last,
00337             _RandomAccessIterator __out,
00338             const _Distance __n)
00339     {
00340       _Distance __m = 0;
00341       _Distance __t = __n;
00342       for ( ; __first != __last && __m < __n; ++__m, ++__first)
00343     __out[__m] = *__first;
00344 
00345       while (__first != __last)
00346     {
00347       ++__t;
00348       _Distance __M = std::rand() % (__t);
00349       if (__M < __n)
00350         __out[__M] = *__first;
00351       ++__first;
00352     }
00353       return __out + __m;
00354     }
00355 
00356   template<typename _InputIterator, typename _RandomAccessIterator,
00357        typename _RandomNumberGenerator, typename _Distance>
00358     _RandomAccessIterator
00359     __random_sample(_InputIterator __first, _InputIterator __last,
00360             _RandomAccessIterator __out,
00361             _RandomNumberGenerator& __rand,
00362             const _Distance __n)
00363     {
00364       // concept requirements
00365       __glibcxx_function_requires(_UnaryFunctionConcept<
00366         _RandomNumberGenerator, _Distance, _Distance>)
00367 
00368       _Distance __m = 0;
00369       _Distance __t = __n;
00370       for ( ; __first != __last && __m < __n; ++__m, ++__first)
00371     __out[__m] = *__first;
00372 
00373       while (__first != __last)
00374     {
00375       ++__t;
00376       _Distance __M = __rand(__t);
00377       if (__M < __n)
00378         __out[__M] = *__first;
00379       ++__first;
00380     }
00381       return __out + __m;
00382     }
00383 
00384   /**
00385    *  This is an SGI extension.
00386    *  @ingroup SGIextensions
00387    *  @doctodo
00388   */
00389   template<typename _InputIterator, typename _RandomAccessIterator>
00390     inline _RandomAccessIterator
00391     random_sample(_InputIterator __first, _InputIterator __last,
00392           _RandomAccessIterator __out_first,
00393           _RandomAccessIterator __out_last)
00394     {
00395       // concept requirements
00396       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
00397       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
00398         _RandomAccessIterator>)
00399       __glibcxx_requires_valid_range(__first, __last);
00400       __glibcxx_requires_valid_range(__out_first, __out_last);
00401 
00402       return __random_sample(__first, __last,
00403                  __out_first, __out_last - __out_first);
00404     }
00405 
00406   /**
00407    *  This is an SGI extension.
00408    *  @ingroup SGIextensions
00409    *  @doctodo
00410   */
00411   template<typename _InputIterator, typename _RandomAccessIterator,
00412        typename _RandomNumberGenerator>
00413     inline _RandomAccessIterator
00414     random_sample(_InputIterator __first, _InputIterator __last,
00415           _RandomAccessIterator __out_first,
00416           _RandomAccessIterator __out_last,
00417           _RandomNumberGenerator& __rand)
00418     {
00419       // concept requirements
00420       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
00421       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
00422         _RandomAccessIterator>)
00423       __glibcxx_requires_valid_range(__first, __last);
00424       __glibcxx_requires_valid_range(__out_first, __out_last);
00425 
00426       return __random_sample(__first, __last,
00427                  __out_first, __rand,
00428                  __out_last - __out_first);
00429     }
00430 
00431 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00432   using std::is_heap;
00433   using std::is_sorted;
00434 #else
00435   /**
00436    *  This is an SGI extension.
00437    *  @ingroup SGIextensions
00438    *  @doctodo
00439   */
00440   template<typename _RandomAccessIterator>
00441     inline bool
00442     is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
00443     {
00444       // concept requirements
00445       __glibcxx_function_requires(_RandomAccessIteratorConcept<
00446                   _RandomAccessIterator>)
00447       __glibcxx_function_requires(_LessThanComparableConcept<
00448         typename iterator_traits<_RandomAccessIterator>::value_type>)
00449       __glibcxx_requires_valid_range(__first, __last);
00450 
00451       return std::__is_heap(__first, __last - __first);
00452     }
00453 
00454   /**
00455    *  This is an SGI extension.
00456    *  @ingroup SGIextensions
00457    *  @doctodo
00458   */
00459   template<typename _RandomAccessIterator, typename _StrictWeakOrdering>
00460     inline bool
00461     is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
00462         _StrictWeakOrdering __comp)
00463     {
00464       // concept requirements
00465       __glibcxx_function_requires(_RandomAccessIteratorConcept<
00466                   _RandomAccessIterator>)
00467       __glibcxx_function_requires(_BinaryPredicateConcept<_StrictWeakOrdering,
00468         typename iterator_traits<_RandomAccessIterator>::value_type,
00469         typename iterator_traits<_RandomAccessIterator>::value_type>)
00470       __glibcxx_requires_valid_range(__first, __last);
00471 
00472       return std::__is_heap(__first, __comp, __last - __first);
00473     }
00474 
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
00531 
00532 _GLIBCXX_END_NAMESPACE
00533 
00534 #endif /* _EXT_ALGORITHM */

Generated on Wed Mar 26 00:42:53 2008 for libstdc++ by  doxygen 1.5.1