libstdc++
ext/algorithm
Go to the documentation of this file.
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 */