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