# algorithm

Go to the documentation of this file.

    00001 // Algorithm extensions -*- C++ -*-
    00002
    00003 // Copyright (C) 2001, 2002 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 2, 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 // You should have received a copy of the GNU General Public License along
    00017 // with this library; see the file COPYING.  If not, write to the Free
    00018 // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
    00019 // USA.
    00020
    00021 // As a special exception, you may use this file as part of a free software
    00022 // library without restriction.  Specifically, if other files instantiate
    00023 // templates or use macros or inline functions from this file, or you compile
    00024 // this file and link it with other files to produce an executable, this
    00025 // file does not by itself cause the resulting executable to be covered by
    00026 // the GNU General Public License.  This exception does not however
    00027 // invalidate any other reasons why the executable file might be covered by
    00028 // the GNU General Public License.
    00029
    00030 /*
    00031  *
    00032  * Copyright (c) 1994
    00033  * Hewlett-Packard Company
    00034  *
    00035  * Permission to use, copy, modify, distribute and sell this software
    00036  * and its documentation for any purpose is hereby granted without fee,
    00037  * provided that the above copyright notice appear in all copies and
    00038  * that both that copyright notice and this permission notice appear
    00039  * in supporting documentation.  Hewlett-Packard Company makes no
    00040  * representations about the suitability of this software for any
    00041  * purpose.  It is provided "as is" without express or implied warranty.
    00042  *
    00043  *
    00044  * Copyright (c) 1996
    00045  * Silicon Graphics Computer Systems, Inc.
    00046  *
    00047  * Permission to use, copy, modify, distribute and sell this software
    00048  * and its documentation for any purpose is hereby granted without fee,
    00049  * provided that the above copyright notice appear in all copies and
    00050  * that both that copyright notice and this permission notice appear
    00051  * in supporting documentation.  Silicon Graphics makes no
    00052  * representations about the suitability of this software for any
    00053  * purpose.  It is provided "as is" without express or implied warranty.
    00054  */
    00055
    00056 /** @file ext/algorithm
    00057  *  This file is a GNU extension to the Standard C++ Library (possibly
    00058  *  containing extensions from the HP/SGI STL subset).  You should only
    00059  *  include this header if you are using GCC 3 or later.
    00060  */
    00061
    00062 #ifndef _EXT_ALGORITHM
    00063 #define _EXT_ALGORITHM 1
    00064
    00065 #pragma GCC system_header
    00066
    00067 #include <algorithm>
    00068
    00069 namespace __gnu_cxx
    00070 {
    00071   using std::ptrdiff_t;
    00072   using std::min;
    00073   using std::pair;
    00074   using std::input_iterator_tag;
    00075   using std::random_access_iterator_tag;
    00076   using std::iterator_traits;
    00077
    00078   //--------------------------------------------------
    00079   // copy_n (not part of the C++ standard)
    00080
    00081   template<typename _InputIterator, typename _Size, typename _OutputIterator>
    00082     pair<_InputIterator, _OutputIterator>
    00083     __copy_n(_InputIterator __first, _Size __count,
    00084          _OutputIterator __result,
    00085          input_iterator_tag)
    00086     {
    00087       for ( ; __count > 0; --__count) {
    00088     *__result = *__first;
    00089     ++__first;
    00090     ++__result;
    00091       }
    00092       return pair<_InputIterator, _OutputIterator>(__first, __result);
    00093     }
    00094
    00095   template<typename _RAIterator, typename _Size, typename _OutputIterator>
    00096     inline pair<_RAIterator, _OutputIterator>
    00097     __copy_n(_RAIterator __first, _Size __count,
    00098          _OutputIterator __result,
    00099          random_access_iterator_tag)
    00100     {
    00101       _RAIterator __last = __first + __count;
    00102       return pair<_RAIterator, _OutputIterator>(__last,
    00103                     std::copy(__first, __last, __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 __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, _InputIterator1 __last1,
    00136                    _InputIterator2 __first2, _InputIterator2 __last2)
    00137     {
    00138       while (__first1 != __last1 && __first2 != __last2) {
    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       }
    00149       else {
    00150     return -1;
    00151       }
    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 = std::memcmp(__first1, __first2, 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(
    00173                   (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    *  "lexigraphically less than" the second, greater than zero if the second
    00195    *  range is "lexigraphically less than" the 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, _InputIterator1 __last1,
    00202                  _InputIterator2 __first2, _InputIterator2 __last2)
    00203     {
    00204       // concept requirements
    00205       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
    00206       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
    00207       __glibcxx_function_requires(_LessThanComparableConcept<
    00208         typename iterator_traits<_InputIterator1>::value_type>)
    00209       __glibcxx_function_requires(_LessThanComparableConcept<
    00210         typename iterator_traits<_InputIterator2>::value_type>)
    00211       __glibcxx_requires_valid_range(__first1, __last1);
    00212       __glibcxx_requires_valid_range(__first2, __last2);
    00213
    00214       return __lexicographical_compare_3way(__first1, __last1, __first2, __last2);
    00215     }
    00216
    00217   // count and count_if: this version, whose return type is void, was present
    00218   // in the HP STL, and is retained as an extension for backward compatibility.
    00219
    00220   template<typename _InputIterator, typename _Tp, typename _Size>
    00221     void
    00222     count(_InputIterator __first, _InputIterator __last,
    00223       const _Tp& __value,
    00224       _Size& __n)
    00225     {
    00226       // concept requirements
    00227       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
    00228       __glibcxx_function_requires(_EqualityComparableConcept<
    00229         typename iterator_traits<_InputIterator>::value_type >)
    00230       __glibcxx_function_requires(_EqualityComparableConcept<_Tp>)
    00231       __glibcxx_requires_valid_range(__first, __last);
    00232
    00233       for ( ; __first != __last; ++__first)
    00234     if (*__first == __value)
    00235       ++__n;
    00236     }
    00237
    00238   template<typename _InputIterator, typename _Predicate, typename _Size>
    00239     void
    00240     count_if(_InputIterator __first, _InputIterator __last,
    00241          _Predicate __pred,
    00242          _Size& __n)
    00243     {
    00244       // concept requirements
    00245       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
    00246       __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
    00247         typename iterator_traits<_InputIterator>::value_type>)
    00248       __glibcxx_requires_valid_range(__first, __last);
    00249
    00250       for ( ; __first != __last; ++__first)
    00251     if (__pred(*__first))
    00252       ++__n;
    00253     }
    00254
    00255   // random_sample and random_sample_n (extensions, not part of the standard).
    00256
    00257   /**
    00258    *  This is an SGI extension.
    00259    *  @ingroup SGIextensions
    00260    *  @doctodo
    00261   */
    00262   template<typename _ForwardIterator, typename _OutputIterator, typename _Distance>
    00263     _OutputIterator
    00264     random_sample_n(_ForwardIterator __first, _ForwardIterator __last,
    00265                     _OutputIterator __out, const _Distance __n)
    00266     {
    00267       // concept requirements
    00268       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
    00269       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
    00270         typename iterator_traits<_ForwardIterator>::value_type>)
    00271       __glibcxx_requires_valid_range(__first, __last);
    00272
    00273       _Distance __remaining = std::distance(__first, __last);
    00274       _Distance __m = min(__n, __remaining);
    00275
    00276       while (__m > 0) {
    00277     if ((std::rand() % __remaining) < __m) {
    00278           *__out = *__first;
    00279           ++__out;
    00280           --__m;
    00281     }
    00282
    00283     --__remaining;
    00284     ++__first;
    00285       }
    00286       return __out;
    00287     }
    00288
    00289   /**
    00290    *  This is an SGI extension.
    00291    *  @ingroup SGIextensions
    00292    *  @doctodo
    00293   */
    00294   template<typename _ForwardIterator, typename _OutputIterator, typename _Distance,
    00295        typename _RandomNumberGenerator>
    00296     _OutputIterator
    00297     random_sample_n(_ForwardIterator __first, _ForwardIterator __last,
    00298                    _OutputIterator __out, const _Distance __n,
    00299            _RandomNumberGenerator& __rand)
    00300     {
    00301       // concept requirements
    00302       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
    00303       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
    00304         typename iterator_traits<_ForwardIterator>::value_type>)
    00305       __glibcxx_function_requires(_UnaryFunctionConcept<
    00306         _RandomNumberGenerator, _Distance, _Distance>)
    00307       __glibcxx_requires_valid_range(__first, __last);
    00308
    00309       _Distance __remaining = std::distance(__first, __last);
    00310       _Distance __m = min(__n, __remaining);
    00311
    00312       while (__m > 0) {
    00313     if (__rand(__remaining) < __m) {
    00314           *__out = *__first;
    00315           ++__out;
    00316           --__m;
    00317     }
    00318
    00319     --__remaining;
    00320     ++__first;
    00321       }
    00322       return __out;
    00323     }
    00324
    00325   template<typename _InputIterator, typename _RandomAccessIterator, typename _Distance>
    00326     _RandomAccessIterator
    00327     __random_sample(_InputIterator __first, _InputIterator __last,
    00328             _RandomAccessIterator __out,
    00329             const _Distance __n)
    00330     {
    00331       _Distance __m = 0;
    00332       _Distance __t = __n;
    00333       for ( ; __first != __last && __m < __n; ++__m, ++__first)
    00334     __out[__m] = *__first;
    00335
    00336       while (__first != __last) {
    00337     ++__t;
    00338     _Distance __M = std::rand() % (__t);
    00339     if (__M < __n)
    00340       __out[__M] = *__first;
    00341     ++__first;
    00342       }
    00343
    00344       return __out + __m;
    00345     }
    00346
    00347   template<typename _InputIterator, typename _RandomAccessIterator,
    00348        typename _RandomNumberGenerator, typename _Distance>
    00349     _RandomAccessIterator
    00350     __random_sample(_InputIterator __first, _InputIterator __last,
    00351             _RandomAccessIterator __out,
    00352             _RandomNumberGenerator& __rand,
    00353             const _Distance __n)
    00354     {
    00355       // concept requirements
    00356       __glibcxx_function_requires(_UnaryFunctionConcept<
    00357         _RandomNumberGenerator, _Distance, _Distance>)
    00358
    00359       _Distance __m = 0;
    00360       _Distance __t = __n;
    00361       for ( ; __first != __last && __m < __n; ++__m, ++__first)
    00362     __out[__m] = *__first;
    00363
    00364       while (__first != __last) {
    00365     ++__t;
    00366     _Distance __M = __rand(__t);
    00367     if (__M < __n)
    00368       __out[__M] = *__first;
    00369     ++__first;
    00370       }
    00371
    00372       return __out + __m;
    00373     }
    00374
    00375   /**
    00376    *  This is an SGI extension.
    00377    *  @ingroup SGIextensions
    00378    *  @doctodo
    00379   */
    00380   template<typename _InputIterator, typename _RandomAccessIterator>
    00381     inline _RandomAccessIterator
    00382     random_sample(_InputIterator __first, _InputIterator __last,
    00383           _RandomAccessIterator __out_first, _RandomAccessIterator __out_last)
    00384     {
    00385       // concept requirements
    00386       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
    00387       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
    00388         _RandomAccessIterator>)
    00389       __glibcxx_requires_valid_range(__first, __last);
    00390       __glibcxx_requires_valid_range(__out_first, __out_last);
    00391
    00392       return __random_sample(__first, __last,
    00393                  __out_first, __out_last - __out_first);
    00394     }
    00395
    00396   /**
    00397    *  This is an SGI extension.
    00398    *  @ingroup SGIextensions
    00399    *  @doctodo
    00400   */
    00401   template<typename _InputIterator, typename _RandomAccessIterator,
    00402        typename _RandomNumberGenerator>
    00403     inline _RandomAccessIterator
    00404     random_sample(_InputIterator __first, _InputIterator __last,
    00405           _RandomAccessIterator __out_first, _RandomAccessIterator __out_last,
    00406           _RandomNumberGenerator& __rand)
    00407     {
    00408       // concept requirements
    00409       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
    00410       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
    00411         _RandomAccessIterator>)
    00412       __glibcxx_requires_valid_range(__first, __last);
    00413       __glibcxx_requires_valid_range(__out_first, __out_last);
    00414
    00415       return __random_sample(__first, __last,
    00416                  __out_first, __rand,
    00417                  __out_last - __out_first);
    00418     }
    00419
    00420   /**
    00421    *  This is an SGI extension.
    00422    *  @ingroup SGIextensions
    00423    *  @doctodo
    00424   */
    00425   template<typename _RandomAccessIterator>
    00426     inline bool
    00427     is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
    00428     {
    00429       // concept requirements
    00430       __glibcxx_function_requires(_RandomAccessIteratorConcept<_RandomAccessIterator>)
    00431       __glibcxx_function_requires(_LessThanComparableConcept<
    00432         typename iterator_traits<_RandomAccessIterator>::value_type>)
    00433       __glibcxx_requires_valid_range(__first, __last);
    00434
    00435       return std::__is_heap(__first, __last - __first);
    00436     }
    00437
    00438   /**
    00439    *  This is an SGI extension.
    00440    *  @ingroup SGIextensions
    00441    *  @doctodo
    00442   */
    00443   template<typename _RandomAccessIterator, typename _StrictWeakOrdering>
    00444     inline bool
    00445     is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
    00446         _StrictWeakOrdering __comp)
    00447     {
    00448       // concept requirements
    00449       __glibcxx_function_requires(_RandomAccessIteratorConcept<_RandomAccessIterator>)
    00450       __glibcxx_function_requires(_BinaryPredicateConcept<_StrictWeakOrdering,
    00451         typename iterator_traits<_RandomAccessIterator>::value_type,
    00452         typename iterator_traits<_RandomAccessIterator>::value_type>)
    00453       __glibcxx_requires_valid_range(__first, __last);
    00454
    00455       return std::__is_heap(__first, __comp, __last - __first);
    00456     }
    00457
    00458   // is_sorted, a predicated testing whether a range is sorted in
    00459   // nondescending order.  This is an extension, not part of the C++
    00460   // standard.
    00461
    00462   /**
    00463    *  This is an SGI extension.
    00464    *  @ingroup SGIextensions
    00465    *  @doctodo
    00466   */
    00467   template<typename _ForwardIterator>
    00468     bool
    00469     is_sorted(_ForwardIterator __first, _ForwardIterator __last)
    00470     {
    00471       // concept requirements
    00472       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
    00473       __glibcxx_function_requires(_LessThanComparableConcept<
    00474         typename iterator_traits<_ForwardIterator>::value_type>)
    00475       __glibcxx_requires_valid_range(__first, __last);
    00476
    00477       if (__first == __last)
    00478     return true;
    00479
    00480       _ForwardIterator __next = __first;
    00481       for (++__next; __next != __last; __first = __next, ++__next) {
    00482     if (*__next < *__first)
    00483       return false;
    00484       }
    00485
    00486       return true;
    00487     }
    00488
    00489   /**
    00490    *  This is an SGI extension.
    00491    *  @ingroup SGIextensions
    00492    *  @doctodo
    00493   */
    00494   template<typename _ForwardIterator, typename _StrictWeakOrdering>
    00495     bool
    00496     is_sorted(_ForwardIterator __first, _ForwardIterator __last, _StrictWeakOrdering __comp)
    00497     {
    00498       // concept requirements
    00499       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
    00500       __glibcxx_function_requires(_BinaryPredicateConcept<_StrictWeakOrdering,
    00501         typename iterator_traits<_ForwardIterator>::value_type,
    00502         typename iterator_traits<_ForwardIterator>::value_type>)
    00503       __glibcxx_requires_valid_range(__first, __last);
    00504
    00505       if (__first == __last)
    00506     return true;
    00507
    00508       _ForwardIterator __next = __first;
    00509       for (++__next; __next != __last; __first = __next, ++__next) {
    00510     if (__comp(*__next, *__first))
    00511       return false;
    00512       }
    00513
    00514       return true;
    00515     }
    00516 } // namespace __gnu_cxx
    00517
    00518 #endif /* _EXT_ALGORITHM */