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, 2009, 2010
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 namespace __gnu_cxx _GLIBCXX_VISIBILITY(default)
00065 {
00066 _GLIBCXX_BEGIN_NAMESPACE_VERSION
00067 
00068   using std::ptrdiff_t;
00069   using std::min;
00070   using std::pair;
00071   using std::input_iterator_tag;
00072   using std::random_access_iterator_tag;
00073   using std::iterator_traits;
00074 
00075   //--------------------------------------------------
00076   // copy_n (not part of the C++ standard)
00077 
00078   template<typename _InputIterator, typename _Size, typename _OutputIterator>
00079     pair<_InputIterator, _OutputIterator>
00080     __copy_n(_InputIterator __first, _Size __count,
00081          _OutputIterator __result,
00082          input_iterator_tag)
00083     {
00084       for ( ; __count > 0; --__count)
00085     {
00086       *__result = *__first;
00087       ++__first;
00088       ++__result;
00089     }
00090       return pair<_InputIterator, _OutputIterator>(__first, __result);
00091     }
00092 
00093   template<typename _RAIterator, typename _Size, typename _OutputIterator>
00094     inline pair<_RAIterator, _OutputIterator>
00095     __copy_n(_RAIterator __first, _Size __count,
00096          _OutputIterator __result,
00097          random_access_iterator_tag)
00098     {
00099       _RAIterator __last = __first + __count;
00100       return pair<_RAIterator, _OutputIterator>(__last, std::copy(__first,
00101                                   __last,
00102                                   __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 _InputIterator, typename _Size, typename _OutputIterator>
00120     inline pair<_InputIterator, _OutputIterator>
00121     copy_n(_InputIterator __first, _Size __count, _OutputIterator __result)
00122     {
00123       // concept requirements
00124       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
00125       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
00126         typename iterator_traits<_InputIterator>::value_type>)
00127 
00128       return __gnu_cxx::__copy_n(__first, __count, __result,
00129                  std::__iterator_category(__first));
00130     }
00131 
00132   template<typename _InputIterator1, typename _InputIterator2>
00133     int
00134     __lexicographical_compare_3way(_InputIterator1 __first1,
00135                    _InputIterator1 __last1,
00136                    _InputIterator2 __first2,
00137                    _InputIterator2 __last2)
00138     {
00139       while (__first1 != __last1 && __first2 != __last2)
00140     {
00141       if (*__first1 < *__first2)
00142         return -1;
00143       if (*__first2 < *__first1)
00144         return 1;
00145       ++__first1;
00146       ++__first2;
00147     }
00148       if (__first2 == __last2)
00149     return !(__first1 == __last1);
00150       else
00151     return -1;
00152     }
00153 
00154   inline int
00155   __lexicographical_compare_3way(const unsigned char* __first1,
00156                  const unsigned char* __last1,
00157                  const unsigned char* __first2,
00158                  const unsigned char* __last2)
00159   {
00160     const ptrdiff_t __len1 = __last1 - __first1;
00161     const ptrdiff_t __len2 = __last2 - __first2;
00162     const int __result = __builtin_memcmp(__first1, __first2,
00163                       min(__len1, __len2));
00164     return __result != 0 ? __result
00165              : (__len1 == __len2 ? 0 : (__len1 < __len2 ? -1 : 1));
00166   }
00167 
00168   inline int
00169   __lexicographical_compare_3way(const char* __first1, const char* __last1,
00170                  const char* __first2, const char* __last2)
00171   {
00172 #if CHAR_MAX == SCHAR_MAX
00173     return __lexicographical_compare_3way((const signed char*) __first1,
00174                       (const signed char*) __last1,
00175                       (const signed char*) __first2,
00176                       (const signed char*) __last2);
00177 #else
00178     return __lexicographical_compare_3way((const unsigned char*) __first1,
00179                       (const unsigned char*) __last1,
00180                       (const unsigned char*) __first2,
00181                       (const unsigned char*) __last2);
00182 #endif
00183   }
00184 
00185   /**
00186    *  @brief @c memcmp on steroids.
00187    *  @param  first1  An input iterator.
00188    *  @param  last1   An input iterator.
00189    *  @param  first2  An input iterator.
00190    *  @param  last2   An input iterator.
00191    *  @return   An int, as with @c memcmp.
00192    *
00193    *  The return value will be less than zero if the first range is
00194    *  <em>lexigraphically less than</em> the second, greater than zero
00195    *  if the second range is <em>lexigraphically less than</em> the
00196    *  first, and zero otherwise.
00197    *  This is an SGI extension.
00198    *  @ingroup SGIextensions
00199   */
00200   template<typename _InputIterator1, typename _InputIterator2>
00201     int
00202     lexicographical_compare_3way(_InputIterator1 __first1,
00203                  _InputIterator1 __last1,
00204                  _InputIterator2 __first2,
00205                  _InputIterator2 __last2)
00206     {
00207       // concept requirements
00208       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
00209       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
00210       __glibcxx_function_requires(_LessThanComparableConcept<
00211         typename iterator_traits<_InputIterator1>::value_type>)
00212       __glibcxx_function_requires(_LessThanComparableConcept<
00213         typename iterator_traits<_InputIterator2>::value_type>)
00214       __glibcxx_requires_valid_range(__first1, __last1);
00215       __glibcxx_requires_valid_range(__first2, __last2);
00216 
00217       return __lexicographical_compare_3way(__first1, __last1, __first2,
00218                         __last2);
00219     }
00220 
00221   // count and count_if: this version, whose return type is void, was present
00222   // in the HP STL, and is retained as an extension for backward compatibility.
00223   template<typename _InputIterator, typename _Tp, typename _Size>
00224     void
00225     count(_InputIterator __first, _InputIterator __last,
00226       const _Tp& __value,
00227       _Size& __n)
00228     {
00229       // concept requirements
00230       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
00231       __glibcxx_function_requires(_EqualityComparableConcept<
00232         typename iterator_traits<_InputIterator>::value_type >)
00233       __glibcxx_function_requires(_EqualityComparableConcept<_Tp>)
00234       __glibcxx_requires_valid_range(__first, __last);
00235 
00236       for ( ; __first != __last; ++__first)
00237     if (*__first == __value)
00238       ++__n;
00239     }
00240 
00241   template<typename _InputIterator, typename _Predicate, typename _Size>
00242     void
00243     count_if(_InputIterator __first, _InputIterator __last,
00244          _Predicate __pred,
00245          _Size& __n)
00246     {
00247       // concept requirements
00248       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
00249       __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
00250         typename iterator_traits<_InputIterator>::value_type>)
00251       __glibcxx_requires_valid_range(__first, __last);
00252 
00253       for ( ; __first != __last; ++__first)
00254     if (__pred(*__first))
00255       ++__n;
00256     }
00257 
00258   // random_sample and random_sample_n (extensions, not part of the standard).
00259 
00260   /**
00261    *  This is an SGI extension.
00262    *  @ingroup SGIextensions
00263    *  @doctodo
00264   */
00265   template<typename _ForwardIterator, typename _OutputIterator,
00266        typename _Distance>
00267     _OutputIterator
00268     random_sample_n(_ForwardIterator __first, _ForwardIterator __last,
00269                     _OutputIterator __out, const _Distance __n)
00270     {
00271       // concept requirements
00272       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
00273       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
00274         typename iterator_traits<_ForwardIterator>::value_type>)
00275       __glibcxx_requires_valid_range(__first, __last);
00276 
00277       _Distance __remaining = std::distance(__first, __last);
00278       _Distance __m = min(__n, __remaining);
00279 
00280       while (__m > 0)
00281     {
00282       if ((std::rand() % __remaining) < __m)
00283         {
00284           *__out = *__first;
00285           ++__out;
00286           --__m;
00287         }
00288       --__remaining;
00289       ++__first;
00290     }
00291       return __out;
00292     }
00293 
00294   /**
00295    *  This is an SGI extension.
00296    *  @ingroup SGIextensions
00297    *  @doctodo
00298   */
00299   template<typename _ForwardIterator, typename _OutputIterator,
00300        typename _Distance, typename _RandomNumberGenerator>
00301     _OutputIterator
00302     random_sample_n(_ForwardIterator __first, _ForwardIterator __last,
00303                    _OutputIterator __out, const _Distance __n,
00304            _RandomNumberGenerator& __rand)
00305     {
00306       // concept requirements
00307       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
00308       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
00309         typename iterator_traits<_ForwardIterator>::value_type>)
00310       __glibcxx_function_requires(_UnaryFunctionConcept<
00311         _RandomNumberGenerator, _Distance, _Distance>)
00312       __glibcxx_requires_valid_range(__first, __last);
00313 
00314       _Distance __remaining = std::distance(__first, __last);
00315       _Distance __m = min(__n, __remaining);
00316 
00317       while (__m > 0)
00318     {
00319       if (__rand(__remaining) < __m)
00320         {
00321           *__out = *__first;
00322           ++__out;
00323           --__m;
00324         }
00325       --__remaining;
00326       ++__first;
00327     }
00328       return __out;
00329     }
00330 
00331   template<typename _InputIterator, typename _RandomAccessIterator,
00332        typename _Distance>
00333     _RandomAccessIterator
00334     __random_sample(_InputIterator __first, _InputIterator __last,
00335             _RandomAccessIterator __out,
00336             const _Distance __n)
00337     {
00338       _Distance __m = 0;
00339       _Distance __t = __n;
00340       for ( ; __first != __last && __m < __n; ++__m, ++__first)
00341     __out[__m] = *__first;
00342 
00343       while (__first != __last)
00344     {
00345       ++__t;
00346       _Distance __M = std::rand() % (__t);
00347       if (__M < __n)
00348         __out[__M] = *__first;
00349       ++__first;
00350     }
00351       return __out + __m;
00352     }
00353 
00354   template<typename _InputIterator, typename _RandomAccessIterator,
00355        typename _RandomNumberGenerator, typename _Distance>
00356     _RandomAccessIterator
00357     __random_sample(_InputIterator __first, _InputIterator __last,
00358             _RandomAccessIterator __out,
00359             _RandomNumberGenerator& __rand,
00360             const _Distance __n)
00361     {
00362       // concept requirements
00363       __glibcxx_function_requires(_UnaryFunctionConcept<
00364         _RandomNumberGenerator, _Distance, _Distance>)
00365 
00366       _Distance __m = 0;
00367       _Distance __t = __n;
00368       for ( ; __first != __last && __m < __n; ++__m, ++__first)
00369     __out[__m] = *__first;
00370 
00371       while (__first != __last)
00372     {
00373       ++__t;
00374       _Distance __M = __rand(__t);
00375       if (__M < __n)
00376         __out[__M] = *__first;
00377       ++__first;
00378     }
00379       return __out + __m;
00380     }
00381 
00382   /**
00383    *  This is an SGI extension.
00384    *  @ingroup SGIextensions
00385    *  @doctodo
00386   */
00387   template<typename _InputIterator, typename _RandomAccessIterator>
00388     inline _RandomAccessIterator
00389     random_sample(_InputIterator __first, _InputIterator __last,
00390           _RandomAccessIterator __out_first,
00391           _RandomAccessIterator __out_last)
00392     {
00393       // concept requirements
00394       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
00395       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
00396         _RandomAccessIterator>)
00397       __glibcxx_requires_valid_range(__first, __last);
00398       __glibcxx_requires_valid_range(__out_first, __out_last);
00399 
00400       return __random_sample(__first, __last,
00401                  __out_first, __out_last - __out_first);
00402     }
00403 
00404   /**
00405    *  This is an SGI extension.
00406    *  @ingroup SGIextensions
00407    *  @doctodo
00408   */
00409   template<typename _InputIterator, typename _RandomAccessIterator,
00410        typename _RandomNumberGenerator>
00411     inline _RandomAccessIterator
00412     random_sample(_InputIterator __first, _InputIterator __last,
00413           _RandomAccessIterator __out_first,
00414           _RandomAccessIterator __out_last,
00415           _RandomNumberGenerator& __rand)
00416     {
00417       // concept requirements
00418       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
00419       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
00420         _RandomAccessIterator>)
00421       __glibcxx_requires_valid_range(__first, __last);
00422       __glibcxx_requires_valid_range(__out_first, __out_last);
00423 
00424       return __random_sample(__first, __last,
00425                  __out_first, __rand,
00426                  __out_last - __out_first);
00427     }
00428 
00429   /**
00430    *  This is an SGI extension.
00431    *  @ingroup SGIextensions
00432    *  @doctodo
00433   */
00434   template<typename _RandomAccessIterator>
00435     inline bool
00436     is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
00437     {
00438       // concept requirements
00439       __glibcxx_function_requires(_RandomAccessIteratorConcept<
00440                   _RandomAccessIterator>)
00441       __glibcxx_function_requires(_LessThanComparableConcept<
00442         typename iterator_traits<_RandomAccessIterator>::value_type>)
00443       __glibcxx_requires_valid_range(__first, __last);
00444 
00445       return std::__is_heap(__first, __last - __first);
00446     }
00447 
00448   /**
00449    *  This is an SGI extension.
00450    *  @ingroup SGIextensions
00451    *  @doctodo
00452   */
00453   template<typename _RandomAccessIterator, typename _StrictWeakOrdering>
00454     inline bool
00455     is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
00456         _StrictWeakOrdering __comp)
00457     {
00458       // concept requirements
00459       __glibcxx_function_requires(_RandomAccessIteratorConcept<
00460                   _RandomAccessIterator>)
00461       __glibcxx_function_requires(_BinaryPredicateConcept<_StrictWeakOrdering,
00462         typename iterator_traits<_RandomAccessIterator>::value_type,
00463         typename iterator_traits<_RandomAccessIterator>::value_type>)
00464       __glibcxx_requires_valid_range(__first, __last);
00465 
00466       return std::__is_heap(__first, __comp, __last - __first);
00467     }
00468 
00469   // is_sorted, a predicated testing whether a range is sorted in
00470   // nondescending order.  This is an extension, not part of the C++
00471   // standard.
00472 
00473   /**
00474    *  This is an SGI extension.
00475    *  @ingroup SGIextensions
00476    *  @doctodo
00477   */
00478   template<typename _ForwardIterator>
00479     bool
00480     is_sorted(_ForwardIterator __first, _ForwardIterator __last)
00481     {
00482       // concept requirements
00483       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
00484       __glibcxx_function_requires(_LessThanComparableConcept<
00485         typename iterator_traits<_ForwardIterator>::value_type>)
00486       __glibcxx_requires_valid_range(__first, __last);
00487 
00488       if (__first == __last)
00489     return true;
00490 
00491       _ForwardIterator __next = __first;
00492       for (++__next; __next != __last; __first = __next, ++__next)
00493     if (*__next < *__first)
00494       return false;
00495       return true;
00496     }
00497 
00498   /**
00499    *  This is an SGI extension.
00500    *  @ingroup SGIextensions
00501    *  @doctodo
00502   */
00503   template<typename _ForwardIterator, typename _StrictWeakOrdering>
00504     bool
00505     is_sorted(_ForwardIterator __first, _ForwardIterator __last,
00506           _StrictWeakOrdering __comp)
00507     {
00508       // concept requirements
00509       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
00510       __glibcxx_function_requires(_BinaryPredicateConcept<_StrictWeakOrdering,
00511         typename iterator_traits<_ForwardIterator>::value_type,
00512         typename iterator_traits<_ForwardIterator>::value_type>)
00513       __glibcxx_requires_valid_range(__first, __last);
00514 
00515       if (__first == __last)
00516     return true;
00517 
00518       _ForwardIterator __next = __first;
00519       for (++__next; __next != __last; __first = __next, ++__next)
00520     if (__comp(*__next, *__first))
00521       return false;
00522       return true;
00523     }
00524 
00525   /**
00526    *  @brief Find the median of three values.
00527    *  @param  a  A value.
00528    *  @param  b  A value.
00529    *  @param  c  A value.
00530    *  @return One of @p a, @p b or @p c.
00531    *
00532    *  If @c {l,m,n} is some convolution of @p {a,b,c} such that @c l<=m<=n
00533    *  then the value returned will be @c m.
00534    *  This is an SGI extension.
00535    *  @ingroup SGIextensions
00536   */
00537   template<typename _Tp>
00538     const _Tp&
00539     __median(const _Tp& __a, const _Tp& __b, const _Tp& __c)
00540     {
00541       // concept requirements
00542       __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
00543       if (__a < __b)
00544     if (__b < __c)
00545       return __b;
00546     else if (__a < __c)
00547       return __c;
00548     else
00549       return __a;
00550       else if (__a < __c)
00551     return __a;
00552       else if (__b < __c)
00553     return __c;
00554       else
00555     return __b;
00556     }
00557 
00558   /**
00559    *  @brief Find the median of three values using a predicate for comparison.
00560    *  @param  a     A value.
00561    *  @param  b     A value.
00562    *  @param  c     A value.
00563    *  @param  comp  A binary predicate.
00564    *  @return One of @p a, @p b or @p c.
00565    *
00566    *  If @c {l,m,n} is some convolution of @p {a,b,c} such that @p comp(l,m)
00567    *  and @p comp(m,n) are both true then the value returned will be @c m.
00568    *  This is an SGI extension.
00569    *  @ingroup SGIextensions
00570   */
00571   template<typename _Tp, typename _Compare>
00572     const _Tp&
00573     __median(const _Tp& __a, const _Tp& __b, const _Tp& __c, _Compare __comp)
00574     {
00575       // concept requirements
00576       __glibcxx_function_requires(_BinaryFunctionConcept<_Compare, bool,
00577                                          _Tp, _Tp>)
00578       if (__comp(__a, __b))
00579     if (__comp(__b, __c))
00580       return __b;
00581     else if (__comp(__a, __c))
00582       return __c;
00583     else
00584       return __a;
00585       else if (__comp(__a, __c))
00586     return __a;
00587       else if (__comp(__b, __c))
00588     return __c;
00589       else
00590     return __b;
00591     }
00592 
00593 _GLIBCXX_END_NAMESPACE_VERSION
00594 } // namespace
00595 
00596 #endif /* _EXT_ALGORITHM */