ext/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
00064 
00065 #pragma GCC system_header
00066 #include <algorithm>
00067 
00068 namespace __gnu_cxx
00069 {
00070   using std::ptrdiff_t;
00071   using std::min;
00072   using std::pair;
00073   using std::input_iterator_tag;
00074   using std::random_access_iterator_tag;
00075   using std::iterator_traits;
00076 
00077   //--------------------------------------------------
00078   // copy_n (not part of the C++ standard)
00079 
00080   template<typename _InputIter, typename _Size, typename _OutputIter>
00081     pair<_InputIter, _OutputIter>
00082     __copy_n(_InputIter __first, _Size __count,
00083          _OutputIter __result,
00084          input_iterator_tag)
00085     {
00086       for ( ; __count > 0; --__count) {
00087     *__result = *__first;
00088     ++__first;
00089     ++__result;
00090       }
00091       return pair<_InputIter, _OutputIter>(__first, __result);
00092     }
00093 
00094   template<typename _RAIter, typename _Size, typename _OutputIter>
00095     inline pair<_RAIter, _OutputIter>
00096     __copy_n(_RAIter __first, _Size __count,
00097          _OutputIter __result,
00098          random_access_iterator_tag)
00099     {
00100       _RAIter __last = __first + __count;
00101       return pair<_RAIter, _OutputIter>(__last,
00102                     std::copy(__first, __last, __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 _InputIter, typename _Size, typename _OutputIter>
00120     inline pair<_InputIter, _OutputIter>
00121     copy_n(_InputIter __first, _Size __count, _OutputIter __result)
00122     {
00123       // concept requirements
00124       __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
00125       __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
00126         typename iterator_traits<_InputIter>::value_type>)
00127 
00128       return __copy_n(__first, __count, __result,
00129               std::__iterator_category(__first));
00130     }
00131 
00132   template<typename _InputIter1, typename _InputIter2>
00133     int
00134     __lexicographical_compare_3way(_InputIter1 __first1, _InputIter1 __last1,
00135                    _InputIter2 __first2, _InputIter2 __last2)
00136     {
00137       while (__first1 != __last1 && __first2 != __last2) {
00138     if (*__first1 < *__first2)
00139       return -1;
00140     if (*__first2 < *__first1)
00141       return 1;
00142     ++__first1;
00143     ++__first2;
00144       }
00145       if (__first2 == __last2) {
00146     return !(__first1 == __last1);
00147       }
00148       else {
00149     return -1;
00150       }
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 = std::memcmp(__first1, __first2, 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(
00172                   (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    *  "lexigraphically less than" the second, greater than zero if the second
00194    *  range is "lexigraphically less than" the first, and zero otherwise.
00195    *  This is an SGI extension.
00196    *  @ingroup SGIextensions
00197   */
00198   template<typename _InputIter1, typename _InputIter2>
00199     int
00200     lexicographical_compare_3way(_InputIter1 __first1, _InputIter1 __last1,
00201                  _InputIter2 __first2, _InputIter2 __last2)
00202     {
00203       // concept requirements
00204       __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>)
00205       __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>)
00206       __glibcpp_function_requires(_LessThanComparableConcept<
00207         typename iterator_traits<_InputIter1>::value_type>)
00208       __glibcpp_function_requires(_LessThanComparableConcept<
00209         typename iterator_traits<_InputIter2>::value_type>)
00210 
00211       return __lexicographical_compare_3way(__first1, __last1, __first2, __last2);
00212     }
00213 
00214   // count and count_if: this version, whose return type is void, was present
00215   // in the HP STL, and is retained as an extension for backward compatibility.
00216 
00217   template<typename _InputIter, typename _Tp, typename _Size>
00218     void
00219     count(_InputIter __first, _InputIter __last,
00220       const _Tp& __value,
00221       _Size& __n)
00222     {
00223       // concept requirements
00224       __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
00225       __glibcpp_function_requires(_EqualityComparableConcept<
00226         typename iterator_traits<_InputIter>::value_type >)
00227       __glibcpp_function_requires(_EqualityComparableConcept<_Tp>)
00228       for ( ; __first != __last; ++__first)
00229     if (*__first == __value)
00230       ++__n;
00231     }
00232 
00233   template<typename _InputIter, typename _Predicate, typename _Size>
00234     void
00235     count_if(_InputIter __first, _InputIter __last,
00236          _Predicate __pred,
00237          _Size& __n)
00238     {
00239       // concept requirements
00240       __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
00241       __glibcpp_function_requires(_UnaryPredicateConcept<_Predicate,
00242         typename iterator_traits<_InputIter>::value_type>)
00243       for ( ; __first != __last; ++__first)
00244     if (__pred(*__first))
00245       ++__n;
00246     }
00247 
00248   // random_sample and random_sample_n (extensions, not part of the standard).
00249 
00250   /**
00251    *  This is an SGI extension.
00252    *  @ingroup SGIextensions
00253    *  @doctodo
00254   */
00255   template<typename _ForwardIter, typename _OutputIter, typename _Distance>
00256     _OutputIter
00257     random_sample_n(_ForwardIter __first, _ForwardIter __last,
00258                     _OutputIter __out, const _Distance __n)
00259     {
00260       // concept requirements
00261       __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
00262       __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
00263         typename iterator_traits<_ForwardIter>::value_type>)
00264 
00265       _Distance __remaining = std::distance(__first, __last);
00266       _Distance __m = min(__n, __remaining);
00267 
00268       while (__m > 0) {
00269     if (std::__random_number(__remaining) < __m) {
00270           *__out = *__first;
00271           ++__out;
00272           --__m;
00273     }
00274 
00275     --__remaining;
00276     ++__first;
00277       }
00278       return __out;
00279     }
00280 
00281   /**
00282    *  This is an SGI extension.
00283    *  @ingroup SGIextensions
00284    *  @doctodo
00285   */
00286   template<typename _ForwardIter, typename _OutputIter, typename _Distance,
00287        typename _RandomNumberGenerator>
00288     _OutputIter
00289     random_sample_n(_ForwardIter __first, _ForwardIter __last,
00290                    _OutputIter __out, const _Distance __n, 
00291            _RandomNumberGenerator& __rand)
00292     {
00293       // concept requirements
00294       __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
00295       __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
00296         typename iterator_traits<_ForwardIter>::value_type>)
00297       __glibcpp_function_requires(_UnaryFunctionConcept<
00298         _RandomNumberGenerator, _Distance, _Distance>)
00299 
00300       _Distance __remaining = std::distance(__first, __last);
00301       _Distance __m = min(__n, __remaining);
00302 
00303       while (__m > 0) {
00304     if (__rand(__remaining) < __m) {
00305           *__out = *__first;
00306           ++__out;
00307           --__m;
00308     }
00309 
00310     --__remaining;
00311     ++__first;
00312       }
00313       return __out;
00314     }
00315 
00316   template<typename _InputIter, typename _RandomAccessIter, typename _Distance>
00317     _RandomAccessIter
00318     __random_sample(_InputIter __first, _InputIter __last,
00319             _RandomAccessIter __out,
00320             const _Distance __n)
00321     {
00322       _Distance __m = 0;
00323       _Distance __t = __n;
00324       for ( ; __first != __last && __m < __n; ++__m, ++__first) 
00325     __out[__m] = *__first;
00326 
00327       while (__first != __last) {
00328     ++__t;
00329     _Distance __M = std::__random_number(__t);
00330     if (__M < __n)
00331       __out[__M] = *__first;
00332     ++__first;
00333       }
00334 
00335       return __out + __m;
00336     }
00337 
00338   template<typename _InputIter, typename _RandomAccessIter,
00339        typename _RandomNumberGenerator, typename _Distance>
00340     _RandomAccessIter
00341     __random_sample(_InputIter __first, _InputIter __last,
00342             _RandomAccessIter __out,
00343             _RandomNumberGenerator& __rand,
00344             const _Distance __n)
00345     {
00346       // concept requirements
00347       __glibcpp_function_requires(_UnaryFunctionConcept<
00348         _RandomNumberGenerator, _Distance, _Distance>)
00349 
00350       _Distance __m = 0;
00351       _Distance __t = __n;
00352       for ( ; __first != __last && __m < __n; ++__m, ++__first)
00353     __out[__m] = *__first;
00354 
00355       while (__first != __last) {
00356     ++__t;
00357     _Distance __M = __rand(__t);
00358     if (__M < __n)
00359       __out[__M] = *__first;
00360     ++__first;
00361       }
00362 
00363       return __out + __m;
00364     }
00365 
00366   /**
00367    *  This is an SGI extension.
00368    *  @ingroup SGIextensions
00369    *  @doctodo
00370   */
00371   template<typename _InputIter, typename _RandomAccessIter>
00372     inline _RandomAccessIter
00373     random_sample(_InputIter __first, _InputIter __last,
00374           _RandomAccessIter __out_first, _RandomAccessIter __out_last) 
00375     {
00376       // concept requirements
00377       __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
00378       __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
00379         _RandomAccessIter>)
00380 
00381       return __random_sample(__first, __last,
00382                  __out_first, __out_last - __out_first);
00383     }
00384 
00385   /**
00386    *  This is an SGI extension.
00387    *  @ingroup SGIextensions
00388    *  @doctodo
00389   */
00390   template<typename _InputIter, typename _RandomAccessIter, 
00391        typename _RandomNumberGenerator>
00392     inline _RandomAccessIter
00393     random_sample(_InputIter __first, _InputIter __last,
00394           _RandomAccessIter __out_first, _RandomAccessIter __out_last,
00395           _RandomNumberGenerator& __rand) 
00396     {
00397       // concept requirements
00398       __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
00399       __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
00400         _RandomAccessIter>)
00401 
00402       return __random_sample(__first, __last,
00403                  __out_first, __rand,
00404                  __out_last - __out_first);
00405     }
00406   
00407   // is_heap, a predicate testing whether or not a range is
00408   // a heap.  This function is an extension, not part of the C++
00409   // standard.
00410 
00411   template<typename _RandomAccessIter, typename _Distance>
00412     bool
00413     __is_heap(_RandomAccessIter __first, _Distance __n)
00414     {
00415       _Distance __parent = 0;
00416       for (_Distance __child = 1; __child < __n; ++__child) {
00417     if (__first[__parent] < __first[__child]) 
00418       return false;
00419     if ((__child & 1) == 0)
00420       ++__parent;
00421       }
00422       return true;
00423     }
00424 
00425   template<typename _RandomAccessIter, typename _Distance,
00426            typename _StrictWeakOrdering>
00427     bool
00428     __is_heap(_RandomAccessIter __first, _StrictWeakOrdering __comp,
00429           _Distance __n)
00430     {
00431       _Distance __parent = 0;
00432       for (_Distance __child = 1; __child < __n; ++__child) {
00433     if (__comp(__first[__parent], __first[__child]))
00434       return false;
00435     if ((__child & 1) == 0)
00436       ++__parent;
00437       }
00438       return true;
00439     }
00440 
00441   /**
00442    *  This is an SGI extension.
00443    *  @ingroup SGIextensions
00444    *  @doctodo
00445   */
00446   template<typename _RandomAccessIter>
00447     inline bool
00448     is_heap(_RandomAccessIter __first, _RandomAccessIter __last)
00449     {
00450       // concept requirements
00451       __glibcpp_function_requires(_RandomAccessIteratorConcept<_RandomAccessIter>)
00452       __glibcpp_function_requires(_LessThanComparableConcept<
00453         typename iterator_traits<_RandomAccessIter>::value_type>)
00454 
00455       return __is_heap(__first, __last - __first);
00456     }
00457 
00458   /**
00459    *  This is an SGI extension.
00460    *  @ingroup SGIextensions
00461    *  @doctodo
00462   */
00463   template<typename _RandomAccessIter, typename _StrictWeakOrdering>
00464     inline bool
00465     is_heap(_RandomAccessIter __first, _RandomAccessIter __last,
00466         _StrictWeakOrdering __comp)
00467     {
00468       // concept requirements
00469       __glibcpp_function_requires(_RandomAccessIteratorConcept<_RandomAccessIter>)
00470       __glibcpp_function_requires(_BinaryPredicateConcept<_StrictWeakOrdering,
00471         typename iterator_traits<_RandomAccessIter>::value_type, 
00472         typename iterator_traits<_RandomAccessIter>::value_type>)
00473 
00474       return __is_heap(__first, __comp, __last - __first);
00475     }
00476 
00477   // is_sorted, a predicated testing whether a range is sorted in
00478   // nondescending order.  This is an extension, not part of the C++
00479   // standard.
00480 
00481   /**
00482    *  This is an SGI extension.
00483    *  @ingroup SGIextensions
00484    *  @doctodo
00485   */
00486   template<typename _ForwardIter>
00487     bool
00488     is_sorted(_ForwardIter __first, _ForwardIter __last)
00489     {
00490       // concept requirements
00491       __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
00492       __glibcpp_function_requires(_LessThanComparableConcept<
00493         typename iterator_traits<_ForwardIter>::value_type>)
00494 
00495       if (__first == __last)
00496     return true;
00497 
00498       _ForwardIter __next = __first;
00499       for (++__next; __next != __last; __first = __next, ++__next) {
00500     if (*__next < *__first)
00501       return false;
00502       }
00503 
00504       return true;
00505     }
00506 
00507   /**
00508    *  This is an SGI extension.
00509    *  @ingroup SGIextensions
00510    *  @doctodo
00511   */
00512   template<typename _ForwardIter, typename _StrictWeakOrdering>
00513     bool
00514     is_sorted(_ForwardIter __first, _ForwardIter __last, _StrictWeakOrdering __comp)
00515     {
00516       // concept requirements
00517       __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
00518       __glibcpp_function_requires(_BinaryPredicateConcept<_StrictWeakOrdering,
00519         typename iterator_traits<_ForwardIter>::value_type, 
00520         typename iterator_traits<_ForwardIter>::value_type>)
00521 
00522       if (__first == __last)
00523     return true;
00524 
00525       _ForwardIter __next = __first;
00526       for (++__next; __next != __last; __first = __next, ++__next) {
00527     if (__comp(*__next, *__first))
00528       return false;
00529       }
00530 
00531       return true;
00532     }
00533 
00534 } // namespace __gnu_cxx
00535 
00536 #endif /* _EXT_ALGORITHM */

Generated on Thu Feb 10 23:22:53 2005 for libstdc++-v3 Source by  doxygen 1.4.0