libstdc++
algorithm
Go to the documentation of this file.
00001 // Algorithm extensions -*- C++ -*-
00002 
00003 // Copyright (C) 2001-2013 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 3, 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 // Under Section 7 of GPL version 3, you are granted additional
00017 // permissions described in the GCC Runtime Library Exception, version
00018 // 3.1, as published by the Free Software Foundation.
00019 
00020 // You should have received a copy of the GNU General Public License and
00021 // a copy of the GCC Runtime Library Exception along with this program;
00022 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
00023 // <http://www.gnu.org/licenses/>.
00024 
00025 /*
00026  *
00027  * Copyright (c) 1994
00028  * Hewlett-Packard Company
00029  *
00030  * Permission to use, copy, modify, distribute and sell this software
00031  * and its documentation for any purpose is hereby granted without fee,
00032  * provided that the above copyright notice appear in all copies and
00033  * that both that copyright notice and this permission notice appear
00034  * in supporting documentation.  Hewlett-Packard Company makes no
00035  * representations about the suitability of this software for any
00036  * purpose.  It is provided "as is" without express or implied warranty.
00037  *
00038  *
00039  * Copyright (c) 1996
00040  * Silicon Graphics Computer Systems, Inc.
00041  *
00042  * Permission to use, copy, modify, distribute and sell this software
00043  * and its documentation for any purpose is hereby granted without fee,
00044  * provided that the above copyright notice appear in all copies and
00045  * that both that copyright notice and this permission notice appear
00046  * in supporting documentation.  Silicon Graphics makes no
00047  * representations about the suitability of this software for any
00048  * purpose.  It is provided "as is" without express or implied warranty.
00049  */
00050 
00051 /** @file ext/algorithm
00052  *  This file is a GNU extension to the Standard C++ Library (possibly
00053  *  containing extensions from the HP/SGI STL subset).
00054  */
00055 
00056 #ifndef _EXT_ALGORITHM
00057 #define _EXT_ALGORITHM 1
00058 
00059 #pragma GCC system_header
00060 
00061 #include <algorithm>
00062 
00063 namespace __gnu_cxx _GLIBCXX_VISIBILITY(default)
00064 {
00065 _GLIBCXX_BEGIN_NAMESPACE_VERSION
00066 
00067   using std::ptrdiff_t;
00068   using std::min;
00069   using std::pair;
00070   using std::input_iterator_tag;
00071   using std::random_access_iterator_tag;
00072   using std::iterator_traits;
00073 
00074   //--------------------------------------------------
00075   // copy_n (not part of the C++ standard)
00076 
00077   template<typename _InputIterator, typename _Size, typename _OutputIterator>
00078     pair<_InputIterator, _OutputIterator>
00079     __copy_n(_InputIterator __first, _Size __count,
00080          _OutputIterator __result,
00081          input_iterator_tag)
00082     {
00083       for ( ; __count > 0; --__count)
00084     {
00085       *__result = *__first;
00086       ++__first;
00087       ++__result;
00088     }
00089       return pair<_InputIterator, _OutputIterator>(__first, __result);
00090     }
00091 
00092   template<typename _RAIterator, typename _Size, typename _OutputIterator>
00093     inline pair<_RAIterator, _OutputIterator>
00094     __copy_n(_RAIterator __first, _Size __count,
00095          _OutputIterator __result,
00096          random_access_iterator_tag)
00097     {
00098       _RAIterator __last = __first + __count;
00099       return pair<_RAIterator, _OutputIterator>(__last, std::copy(__first,
00100                                   __last,
00101                                   __result));
00102     }
00103 
00104   /**
00105    *  @brief Copies the range [first,first+count) into [result,result+count).
00106    *  @param  __first  An input iterator.
00107    *  @param  __count  The number of elements to copy.
00108    *  @param  __result An output iterator.
00109    *  @return   A std::pair composed of first+count and result+count.
00110    *
00111    *  This is an SGI extension.
00112    *  This inline function will boil down to a call to @c memmove whenever
00113    *  possible.  Failing that, if random access iterators are passed, then the
00114    *  loop count will be known (and therefore a candidate for compiler
00115    *  optimizations such as unrolling).
00116    *  @ingroup SGIextensions
00117   */
00118   template<typename _InputIterator, typename _Size, typename _OutputIterator>
00119     inline pair<_InputIterator, _OutputIterator>
00120     copy_n(_InputIterator __first, _Size __count, _OutputIterator __result)
00121     {
00122       // concept requirements
00123       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
00124       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
00125         typename iterator_traits<_InputIterator>::value_type>)
00126 
00127       return __gnu_cxx::__copy_n(__first, __count, __result,
00128                  std::__iterator_category(__first));
00129     }
00130 
00131   template<typename _InputIterator1, typename _InputIterator2>
00132     int
00133     __lexicographical_compare_3way(_InputIterator1 __first1,
00134                    _InputIterator1 __last1,
00135                    _InputIterator2 __first2,
00136                    _InputIterator2 __last2)
00137     {
00138       while (__first1 != __last1 && __first2 != __last2)
00139     {
00140       if (*__first1 < *__first2)
00141         return -1;
00142       if (*__first2 < *__first1)
00143         return 1;
00144       ++__first1;
00145       ++__first2;
00146     }
00147       if (__first2 == __last2)
00148     return !(__first1 == __last1);
00149       else
00150     return -1;
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 = __builtin_memcmp(__first1, __first2,
00162                       min(__len1, __len2));
00163     return __result != 0 ? __result
00164              : (__len1 == __len2 ? 0 : (__len1 < __len2 ? -1 : 1));
00165   }
00166 
00167   inline int
00168   __lexicographical_compare_3way(const char* __first1, const char* __last1,
00169                  const char* __first2, const char* __last2)
00170   {
00171 #if CHAR_MAX == SCHAR_MAX
00172     return __lexicographical_compare_3way((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    *  <em>lexigraphically less than</em> the second, greater than zero
00194    *  if the second range is <em>lexigraphically less than</em> the
00195    *  first, and zero otherwise.
00196    *  This is an SGI extension.
00197    *  @ingroup SGIextensions
00198   */
00199   template<typename _InputIterator1, typename _InputIterator2>
00200     int
00201     lexicographical_compare_3way(_InputIterator1 __first1,
00202                  _InputIterator1 __last1,
00203                  _InputIterator2 __first2,
00204                  _InputIterator2 __last2)
00205     {
00206       // concept requirements
00207       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
00208       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
00209       __glibcxx_function_requires(_LessThanComparableConcept<
00210         typename iterator_traits<_InputIterator1>::value_type>)
00211       __glibcxx_function_requires(_LessThanComparableConcept<
00212         typename iterator_traits<_InputIterator2>::value_type>)
00213       __glibcxx_requires_valid_range(__first1, __last1);
00214       __glibcxx_requires_valid_range(__first2, __last2);
00215 
00216       return __lexicographical_compare_3way(__first1, __last1, __first2,
00217                         __last2);
00218     }
00219 
00220   // count and count_if: this version, whose return type is void, was present
00221   // in the HP STL, and is retained as an extension for backward compatibility.
00222   template<typename _InputIterator, typename _Tp, typename _Size>
00223     void
00224     count(_InputIterator __first, _InputIterator __last,
00225       const _Tp& __value,
00226       _Size& __n)
00227     {
00228       // concept requirements
00229       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
00230       __glibcxx_function_requires(_EqualityComparableConcept<
00231         typename iterator_traits<_InputIterator>::value_type >)
00232       __glibcxx_function_requires(_EqualityComparableConcept<_Tp>)
00233       __glibcxx_requires_valid_range(__first, __last);
00234 
00235       for ( ; __first != __last; ++__first)
00236     if (*__first == __value)
00237       ++__n;
00238     }
00239 
00240   template<typename _InputIterator, typename _Predicate, typename _Size>
00241     void
00242     count_if(_InputIterator __first, _InputIterator __last,
00243          _Predicate __pred,
00244          _Size& __n)
00245     {
00246       // concept requirements
00247       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
00248       __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
00249         typename iterator_traits<_InputIterator>::value_type>)
00250       __glibcxx_requires_valid_range(__first, __last);
00251 
00252       for ( ; __first != __last; ++__first)
00253     if (__pred(*__first))
00254       ++__n;
00255     }
00256 
00257   // random_sample and random_sample_n (extensions, not part of the standard).
00258 
00259   /**
00260    *  This is an SGI extension.
00261    *  @ingroup SGIextensions
00262    *  @doctodo
00263   */
00264   template<typename _ForwardIterator, typename _OutputIterator,
00265        typename _Distance>
00266     _OutputIterator
00267     random_sample_n(_ForwardIterator __first, _ForwardIterator __last,
00268                     _OutputIterator __out, const _Distance __n)
00269     {
00270       // concept requirements
00271       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
00272       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
00273         typename iterator_traits<_ForwardIterator>::value_type>)
00274       __glibcxx_requires_valid_range(__first, __last);
00275 
00276       _Distance __remaining = std::distance(__first, __last);
00277       _Distance __m = min(__n, __remaining);
00278 
00279       while (__m > 0)
00280     {
00281       if ((std::rand() % __remaining) < __m)
00282         {
00283           *__out = *__first;
00284           ++__out;
00285           --__m;
00286         }
00287       --__remaining;
00288       ++__first;
00289     }
00290       return __out;
00291     }
00292 
00293   /**
00294    *  This is an SGI extension.
00295    *  @ingroup SGIextensions
00296    *  @doctodo
00297   */
00298   template<typename _ForwardIterator, typename _OutputIterator,
00299        typename _Distance, typename _RandomNumberGenerator>
00300     _OutputIterator
00301     random_sample_n(_ForwardIterator __first, _ForwardIterator __last,
00302                    _OutputIterator __out, const _Distance __n,
00303            _RandomNumberGenerator& __rand)
00304     {
00305       // concept requirements
00306       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
00307       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
00308         typename iterator_traits<_ForwardIterator>::value_type>)
00309       __glibcxx_function_requires(_UnaryFunctionConcept<
00310         _RandomNumberGenerator, _Distance, _Distance>)
00311       __glibcxx_requires_valid_range(__first, __last);
00312 
00313       _Distance __remaining = std::distance(__first, __last);
00314       _Distance __m = min(__n, __remaining);
00315 
00316       while (__m > 0)
00317     {
00318       if (__rand(__remaining) < __m)
00319         {
00320           *__out = *__first;
00321           ++__out;
00322           --__m;
00323         }
00324       --__remaining;
00325       ++__first;
00326     }
00327       return __out;
00328     }
00329 
00330   template<typename _InputIterator, typename _RandomAccessIterator,
00331        typename _Distance>
00332     _RandomAccessIterator
00333     __random_sample(_InputIterator __first, _InputIterator __last,
00334             _RandomAccessIterator __out,
00335             const _Distance __n)
00336     {
00337       _Distance __m = 0;
00338       _Distance __t = __n;
00339       for ( ; __first != __last && __m < __n; ++__m, ++__first)
00340     __out[__m] = *__first;
00341 
00342       while (__first != __last)
00343     {
00344       ++__t;
00345       _Distance __M = std::rand() % (__t);
00346       if (__M < __n)
00347         __out[__M] = *__first;
00348       ++__first;
00349     }
00350       return __out + __m;
00351     }
00352 
00353   template<typename _InputIterator, typename _RandomAccessIterator,
00354        typename _RandomNumberGenerator, typename _Distance>
00355     _RandomAccessIterator
00356     __random_sample(_InputIterator __first, _InputIterator __last,
00357             _RandomAccessIterator __out,
00358             _RandomNumberGenerator& __rand,
00359             const _Distance __n)
00360     {
00361       // concept requirements
00362       __glibcxx_function_requires(_UnaryFunctionConcept<
00363         _RandomNumberGenerator, _Distance, _Distance>)
00364 
00365       _Distance __m = 0;
00366       _Distance __t = __n;
00367       for ( ; __first != __last && __m < __n; ++__m, ++__first)
00368     __out[__m] = *__first;
00369 
00370       while (__first != __last)
00371     {
00372       ++__t;
00373       _Distance __M = __rand(__t);
00374       if (__M < __n)
00375         __out[__M] = *__first;
00376       ++__first;
00377     }
00378       return __out + __m;
00379     }
00380 
00381   /**
00382    *  This is an SGI extension.
00383    *  @ingroup SGIextensions
00384    *  @doctodo
00385   */
00386   template<typename _InputIterator, typename _RandomAccessIterator>
00387     inline _RandomAccessIterator
00388     random_sample(_InputIterator __first, _InputIterator __last,
00389           _RandomAccessIterator __out_first,
00390           _RandomAccessIterator __out_last)
00391     {
00392       // concept requirements
00393       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
00394       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
00395         _RandomAccessIterator>)
00396       __glibcxx_requires_valid_range(__first, __last);
00397       __glibcxx_requires_valid_range(__out_first, __out_last);
00398 
00399       return __random_sample(__first, __last,
00400                  __out_first, __out_last - __out_first);
00401     }
00402 
00403   /**
00404    *  This is an SGI extension.
00405    *  @ingroup SGIextensions
00406    *  @doctodo
00407   */
00408   template<typename _InputIterator, typename _RandomAccessIterator,
00409        typename _RandomNumberGenerator>
00410     inline _RandomAccessIterator
00411     random_sample(_InputIterator __first, _InputIterator __last,
00412           _RandomAccessIterator __out_first,
00413           _RandomAccessIterator __out_last,
00414           _RandomNumberGenerator& __rand)
00415     {
00416       // concept requirements
00417       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
00418       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
00419         _RandomAccessIterator>)
00420       __glibcxx_requires_valid_range(__first, __last);
00421       __glibcxx_requires_valid_range(__out_first, __out_last);
00422 
00423       return __random_sample(__first, __last,
00424                  __out_first, __rand,
00425                  __out_last - __out_first);
00426     }
00427 
00428 #if __cplusplus >= 201103L
00429   using std::is_heap;
00430 #else
00431   /**
00432    *  This is an SGI extension.
00433    *  @ingroup SGIextensions
00434    *  @doctodo
00435   */
00436   template<typename _RandomAccessIterator>
00437     inline bool
00438     is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
00439     {
00440       // concept requirements
00441       __glibcxx_function_requires(_RandomAccessIteratorConcept<
00442                   _RandomAccessIterator>)
00443       __glibcxx_function_requires(_LessThanComparableConcept<
00444         typename iterator_traits<_RandomAccessIterator>::value_type>)
00445       __glibcxx_requires_valid_range(__first, __last);
00446 
00447       return std::__is_heap(__first, __last - __first);
00448     }
00449 
00450   /**
00451    *  This is an SGI extension.
00452    *  @ingroup SGIextensions
00453    *  @doctodo
00454   */
00455   template<typename _RandomAccessIterator, typename _StrictWeakOrdering>
00456     inline bool
00457     is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
00458         _StrictWeakOrdering __comp)
00459     {
00460       // concept requirements
00461       __glibcxx_function_requires(_RandomAccessIteratorConcept<
00462                   _RandomAccessIterator>)
00463       __glibcxx_function_requires(_BinaryPredicateConcept<_StrictWeakOrdering,
00464         typename iterator_traits<_RandomAccessIterator>::value_type,
00465         typename iterator_traits<_RandomAccessIterator>::value_type>)
00466       __glibcxx_requires_valid_range(__first, __last);
00467 
00468       return std::__is_heap(__first, __comp, __last - __first);
00469     }
00470 #endif
00471 
00472 #if __cplusplus >= 201103L
00473   using std::is_sorted;
00474 #else
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  // C++11
00531 
00532   /**
00533    *  @brief Find the median of three values.
00534    *  @param  __a  A value.
00535    *  @param  __b  A value.
00536    *  @param  __c  A value.
00537    *  @return One of @p a, @p b or @p c.
00538    *
00539    *  If @c {l,m,n} is some convolution of @p {a,b,c} such that @c l<=m<=n
00540    *  then the value returned will be @c m.
00541    *  This is an SGI extension.
00542    *  @ingroup SGIextensions
00543   */
00544   template<typename _Tp>
00545     const _Tp&
00546     __median(const _Tp& __a, const _Tp& __b, const _Tp& __c)
00547     {
00548       // concept requirements
00549       __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
00550       if (__a < __b)
00551     if (__b < __c)
00552       return __b;
00553     else if (__a < __c)
00554       return __c;
00555     else
00556       return __a;
00557       else if (__a < __c)
00558     return __a;
00559       else if (__b < __c)
00560     return __c;
00561       else
00562     return __b;
00563     }
00564 
00565   /**
00566    *  @brief Find the median of three values using a predicate for comparison.
00567    *  @param  __a     A value.
00568    *  @param  __b     A value.
00569    *  @param  __c     A value.
00570    *  @param  __comp  A binary predicate.
00571    *  @return One of @p a, @p b or @p c.
00572    *
00573    *  If @c {l,m,n} is some convolution of @p {a,b,c} such that @p comp(l,m)
00574    *  and @p comp(m,n) are both true then the value returned will be @c m.
00575    *  This is an SGI extension.
00576    *  @ingroup SGIextensions
00577   */
00578   template<typename _Tp, typename _Compare>
00579     const _Tp&
00580     __median(const _Tp& __a, const _Tp& __b, const _Tp& __c, _Compare __comp)
00581     {
00582       // concept requirements
00583       __glibcxx_function_requires(_BinaryFunctionConcept<_Compare, bool,
00584                                          _Tp, _Tp>)
00585       if (__comp(__a, __b))
00586     if (__comp(__b, __c))
00587       return __b;
00588     else if (__comp(__a, __c))
00589       return __c;
00590     else
00591       return __a;
00592       else if (__comp(__a, __c))
00593     return __a;
00594       else if (__comp(__b, __c))
00595     return __c;
00596       else
00597     return __b;
00598     }
00599 
00600 _GLIBCXX_END_NAMESPACE_VERSION
00601 } // namespace
00602 
00603 #endif /* _EXT_ALGORITHM */