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
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 __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    *  "lexigraphically less than" the second, greater than zero if the second
00193    *  range is "lexigraphically less than" the first, and zero otherwise.
00194    *  This is an SGI extension.
00195    *  @ingroup SGIextensions
00196   */
00197   template<typename _InputIterator1, typename _InputIterator2>
00198     int
00199     lexicographical_compare_3way(_InputIterator1 __first1,
00200                  _InputIterator1 __last1,
00201                  _InputIterator2 __first2,
00202                  _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,
00215                         __last2);
00216     }
00217 
00218   // count and count_if: this version, whose return type is void, was present
00219   // in the HP STL, and is retained as an extension for backward compatibility.
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,
00263        typename _Distance>
00264     _OutputIterator
00265     random_sample_n(_ForwardIterator __first, _ForwardIterator __last,
00266                     _OutputIterator __out, const _Distance __n)
00267     {
00268       // concept requirements
00269       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
00270       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
00271         typename iterator_traits<_ForwardIterator>::value_type>)
00272       __glibcxx_requires_valid_range(__first, __last);
00273 
00274       _Distance __remaining = std::distance(__first, __last);
00275       _Distance __m = min(__n, __remaining);
00276 
00277       while (__m > 0)
00278     {
00279       if ((std::rand() % __remaining) < __m)
00280         {
00281           *__out = *__first;
00282           ++__out;
00283           --__m;
00284         }
00285       --__remaining;
00286       ++__first;
00287     }
00288       return __out;
00289     }
00290 
00291   /**
00292    *  This is an SGI extension.
00293    *  @ingroup SGIextensions
00294    *  @doctodo
00295   */
00296   template<typename _ForwardIterator, typename _OutputIterator,
00297        typename _Distance, typename _RandomNumberGenerator>
00298     _OutputIterator
00299     random_sample_n(_ForwardIterator __first, _ForwardIterator __last,
00300                    _OutputIterator __out, const _Distance __n,
00301            _RandomNumberGenerator& __rand)
00302     {
00303       // concept requirements
00304       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
00305       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
00306         typename iterator_traits<_ForwardIterator>::value_type>)
00307       __glibcxx_function_requires(_UnaryFunctionConcept<
00308         _RandomNumberGenerator, _Distance, _Distance>)
00309       __glibcxx_requires_valid_range(__first, __last);
00310 
00311       _Distance __remaining = std::distance(__first, __last);
00312       _Distance __m = min(__n, __remaining);
00313 
00314       while (__m > 0)
00315     {
00316       if (__rand(__remaining) < __m)
00317         {
00318           *__out = *__first;
00319           ++__out;
00320           --__m;
00321         }
00322       --__remaining;
00323       ++__first;
00324     }
00325       return __out;
00326     }
00327 
00328   template<typename _InputIterator, typename _RandomAccessIterator,
00329        typename _Distance>
00330     _RandomAccessIterator
00331     __random_sample(_InputIterator __first, _InputIterator __last,
00332             _RandomAccessIterator __out,
00333             const _Distance __n)
00334     {
00335       _Distance __m = 0;
00336       _Distance __t = __n;
00337       for ( ; __first != __last && __m < __n; ++__m, ++__first)
00338     __out[__m] = *__first;
00339 
00340       while (__first != __last)
00341     {
00342       ++__t;
00343       _Distance __M = std::rand() % (__t);
00344       if (__M < __n)
00345         __out[__M] = *__first;
00346       ++__first;
00347     }
00348       return __out + __m;
00349     }
00350 
00351   template<typename _InputIterator, typename _RandomAccessIterator,
00352        typename _RandomNumberGenerator, typename _Distance>
00353     _RandomAccessIterator
00354     __random_sample(_InputIterator __first, _InputIterator __last,
00355             _RandomAccessIterator __out,
00356             _RandomNumberGenerator& __rand,
00357             const _Distance __n)
00358     {
00359       // concept requirements
00360       __glibcxx_function_requires(_UnaryFunctionConcept<
00361         _RandomNumberGenerator, _Distance, _Distance>)
00362 
00363       _Distance __m = 0;
00364       _Distance __t = __n;
00365       for ( ; __first != __last && __m < __n; ++__m, ++__first)
00366     __out[__m] = *__first;
00367 
00368       while (__first != __last)
00369     {
00370       ++__t;
00371       _Distance __M = __rand(__t);
00372       if (__M < __n)
00373         __out[__M] = *__first;
00374       ++__first;
00375     }
00376       return __out + __m;
00377     }
00378 
00379   /**
00380    *  This is an SGI extension.
00381    *  @ingroup SGIextensions
00382    *  @doctodo
00383   */
00384   template<typename _InputIterator, typename _RandomAccessIterator>
00385     inline _RandomAccessIterator
00386     random_sample(_InputIterator __first, _InputIterator __last,
00387           _RandomAccessIterator __out_first,
00388           _RandomAccessIterator __out_last)
00389     {
00390       // concept requirements
00391       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
00392       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
00393         _RandomAccessIterator>)
00394       __glibcxx_requires_valid_range(__first, __last);
00395       __glibcxx_requires_valid_range(__out_first, __out_last);
00396 
00397       return __random_sample(__first, __last,
00398                  __out_first, __out_last - __out_first);
00399     }
00400 
00401   /**
00402    *  This is an SGI extension.
00403    *  @ingroup SGIextensions
00404    *  @doctodo
00405   */
00406   template<typename _InputIterator, typename _RandomAccessIterator,
00407        typename _RandomNumberGenerator>
00408     inline _RandomAccessIterator
00409     random_sample(_InputIterator __first, _InputIterator __last,
00410           _RandomAccessIterator __out_first,
00411           _RandomAccessIterator __out_last,
00412           _RandomNumberGenerator& __rand)
00413     {
00414       // concept requirements
00415       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
00416       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
00417         _RandomAccessIterator>)
00418       __glibcxx_requires_valid_range(__first, __last);
00419       __glibcxx_requires_valid_range(__out_first, __out_last);
00420 
00421       return __random_sample(__first, __last,
00422                  __out_first, __rand,
00423                  __out_last - __out_first);
00424     }
00425 
00426   /**
00427    *  This is an SGI extension.
00428    *  @ingroup SGIextensions
00429    *  @doctodo
00430   */
00431   template<typename _RandomAccessIterator>
00432     inline bool
00433     is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
00434     {
00435       // concept requirements
00436       __glibcxx_function_requires(_RandomAccessIteratorConcept<
00437                   _RandomAccessIterator>)
00438       __glibcxx_function_requires(_LessThanComparableConcept<
00439         typename iterator_traits<_RandomAccessIterator>::value_type>)
00440       __glibcxx_requires_valid_range(__first, __last);
00441 
00442       return std::__is_heap(__first, __last - __first);
00443     }
00444 
00445   /**
00446    *  This is an SGI extension.
00447    *  @ingroup SGIextensions
00448    *  @doctodo
00449   */
00450   template<typename _RandomAccessIterator, typename _StrictWeakOrdering>
00451     inline bool
00452     is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
00453         _StrictWeakOrdering __comp)
00454     {
00455       // concept requirements
00456       __glibcxx_function_requires(_RandomAccessIteratorConcept<
00457                   _RandomAccessIterator>)
00458       __glibcxx_function_requires(_BinaryPredicateConcept<_StrictWeakOrdering,
00459         typename iterator_traits<_RandomAccessIterator>::value_type,
00460         typename iterator_traits<_RandomAccessIterator>::value_type>)
00461       __glibcxx_requires_valid_range(__first, __last);
00462 
00463       return std::__is_heap(__first, __comp, __last - __first);
00464     }
00465 
00466   // is_sorted, a predicated testing whether a range is sorted in
00467   // nondescending order.  This is an extension, not part of the C++
00468   // standard.
00469 
00470   /**
00471    *  This is an SGI extension.
00472    *  @ingroup SGIextensions
00473    *  @doctodo
00474   */
00475   template<typename _ForwardIterator>
00476     bool
00477     is_sorted(_ForwardIterator __first, _ForwardIterator __last)
00478     {
00479       // concept requirements
00480       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
00481       __glibcxx_function_requires(_LessThanComparableConcept<
00482         typename iterator_traits<_ForwardIterator>::value_type>)
00483       __glibcxx_requires_valid_range(__first, __last);
00484 
00485       if (__first == __last)
00486     return true;
00487 
00488       _ForwardIterator __next = __first;
00489       for (++__next; __next != __last; __first = __next, ++__next)
00490     if (*__next < *__first)
00491       return false;
00492       return true;
00493     }
00494 
00495   /**
00496    *  This is an SGI extension.
00497    *  @ingroup SGIextensions
00498    *  @doctodo
00499   */
00500   template<typename _ForwardIterator, typename _StrictWeakOrdering>
00501     bool
00502     is_sorted(_ForwardIterator __first, _ForwardIterator __last,
00503           _StrictWeakOrdering __comp)
00504     {
00505       // concept requirements
00506       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
00507       __glibcxx_function_requires(_BinaryPredicateConcept<_StrictWeakOrdering,
00508         typename iterator_traits<_ForwardIterator>::value_type,
00509         typename iterator_traits<_ForwardIterator>::value_type>)
00510       __glibcxx_requires_valid_range(__first, __last);
00511 
00512       if (__first == __last)
00513     return true;
00514 
00515       _ForwardIterator __next = __first;
00516       for (++__next; __next != __last; __first = __next, ++__next)
00517     if (__comp(*__next, *__first))
00518       return false;
00519       return true;
00520     }
00521 
00522 _GLIBCXX_END_NAMESPACE
00523 
00524 #endif /* _EXT_ALGORITHM */

Generated on Thu Jul 23 21:15:56 2009 for libstdc++ by  doxygen 1.5.8