stl_numeric.h

Go to the documentation of this file.
00001 // Numeric functions implementation -*- 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,1997
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 stl_numeric.h
00053  *  This is an internal header file, included by other library headers.
00054  *  You should not attempt to use it directly.
00055  */
00056 
00057 #ifndef _STL_NUMERIC_H
00058 #define _STL_NUMERIC_H 1
00059 
00060 #include <bits/concept_check.h>
00061 #include <debug/debug.h>
00062 
00063 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00064 
00065 _GLIBCXX_BEGIN_NAMESPACE(std)
00066 
00067   /**
00068    *  @brief  Create a range of sequentially increasing values.
00069    *
00070    *  For each element in the range @p [first,last) assigns @p value and
00071    *  increments @p value as if by @p ++value.
00072    *
00073    *  @param  first  Start of range.
00074    *  @param  last  End of range.
00075    *  @param  value  Starting value.
00076    *  @return  Nothing.
00077    */
00078   template<typename _ForwardIterator, typename _Tp>
00079     void
00080     iota(_ForwardIterator __first, _ForwardIterator __last, _Tp __value)
00081     {
00082       // concept requirements
00083       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
00084                   _ForwardIterator>)
00085       __glibcxx_function_requires(_ConvertibleConcept<_Tp,
00086         typename iterator_traits<_ForwardIterator>::value_type>)
00087       __glibcxx_requires_valid_range(__first, __last);
00088 
00089       for (; __first != __last; ++__first)
00090     {
00091       *__first = __value;
00092       ++__value;
00093     }
00094     }
00095 
00096 _GLIBCXX_END_NAMESPACE
00097 
00098 #endif
00099 
00100 _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_P)
00101 
00102   /**
00103    *  @brief  Accumulate values in a range.
00104    *
00105    *  Accumulates the values in the range [first,last) using operator+().  The
00106    *  initial value is @a init.  The values are processed in order.
00107    *
00108    *  @param  first  Start of range.
00109    *  @param  last  End of range.
00110    *  @param  init  Starting value to add other values to.
00111    *  @return  The final sum.
00112    */
00113   template<typename _InputIterator, typename _Tp>
00114     inline _Tp
00115     accumulate(_InputIterator __first, _InputIterator __last, _Tp __init)
00116     {
00117       // concept requirements
00118       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
00119       __glibcxx_requires_valid_range(__first, __last);
00120 
00121       for (; __first != __last; ++__first)
00122     __init = __init + *__first;
00123       return __init;
00124     }
00125 
00126   /**
00127    *  @brief  Accumulate values in a range with operation.
00128    *
00129    *  Accumulates the values in the range [first,last) using the function
00130    *  object @a binary_op.  The initial value is @a init.  The values are
00131    *  processed in order.
00132    *
00133    *  @param  first  Start of range.
00134    *  @param  last  End of range.
00135    *  @param  init  Starting value to add other values to.
00136    *  @param  binary_op  Function object to accumulate with.
00137    *  @return  The final sum.
00138    */
00139   template<typename _InputIterator, typename _Tp, typename _BinaryOperation>
00140     inline _Tp
00141     accumulate(_InputIterator __first, _InputIterator __last, _Tp __init,
00142            _BinaryOperation __binary_op)
00143     {
00144       // concept requirements
00145       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
00146       __glibcxx_requires_valid_range(__first, __last);
00147 
00148       for (; __first != __last; ++__first)
00149     __init = __binary_op(__init, *__first);
00150       return __init;
00151     }
00152 
00153   /**
00154    *  @brief  Compute inner product of two ranges.
00155    *
00156    *  Starting with an initial value of @a init, multiplies successive
00157    *  elements from the two ranges and adds each product into the accumulated
00158    *  value using operator+().  The values in the ranges are processed in
00159    *  order.
00160    *
00161    *  @param  first1  Start of range 1.
00162    *  @param  last1  End of range 1.
00163    *  @param  first2  Start of range 2.
00164    *  @param  init  Starting value to add other values to.
00165    *  @return  The final inner product.
00166    */
00167   template<typename _InputIterator1, typename _InputIterator2, typename _Tp>
00168     inline _Tp
00169     inner_product(_InputIterator1 __first1, _InputIterator1 __last1,
00170           _InputIterator2 __first2, _Tp __init)
00171     {
00172       // concept requirements
00173       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
00174       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
00175       __glibcxx_requires_valid_range(__first1, __last1);
00176 
00177       for (; __first1 != __last1; ++__first1, ++__first2)
00178     __init = __init + (*__first1 * *__first2);
00179       return __init;
00180     }
00181 
00182   /**
00183    *  @brief  Compute inner product of two ranges.
00184    *
00185    *  Starting with an initial value of @a init, applies @a binary_op2 to
00186    *  successive elements from the two ranges and accumulates each result into
00187    *  the accumulated value using @a binary_op1.  The values in the ranges are
00188    *  processed in order.
00189    *
00190    *  @param  first1  Start of range 1.
00191    *  @param  last1  End of range 1.
00192    *  @param  first2  Start of range 2.
00193    *  @param  init  Starting value to add other values to.
00194    *  @param  binary_op1  Function object to accumulate with.
00195    *  @param  binary_op2  Function object to apply to pairs of input values.
00196    *  @return  The final inner product.
00197    */
00198   template<typename _InputIterator1, typename _InputIterator2, typename _Tp,
00199        typename _BinaryOperation1, typename _BinaryOperation2>
00200     inline _Tp
00201     inner_product(_InputIterator1 __first1, _InputIterator1 __last1,
00202           _InputIterator2 __first2, _Tp __init,
00203           _BinaryOperation1 __binary_op1,
00204           _BinaryOperation2 __binary_op2)
00205     {
00206       // concept requirements
00207       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
00208       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
00209       __glibcxx_requires_valid_range(__first1, __last1);
00210 
00211       for (; __first1 != __last1; ++__first1, ++__first2)
00212     __init = __binary_op1(__init, __binary_op2(*__first1, *__first2));
00213       return __init;
00214     }
00215 
00216   /**
00217    *  @brief  Return list of partial sums
00218    *
00219    *  Accumulates the values in the range [first,last) using operator+().
00220    *  As each successive input value is added into the total, that partial sum
00221    *  is written to @a result.  Therefore, the first value in result is the
00222    *  first value of the input, the second value in result is the sum of the
00223    *  first and second input values, and so on.
00224    *
00225    *  @param  first  Start of input range.
00226    *  @param  last  End of input range.
00227    *  @param  result  Output to write sums to.
00228    *  @return  Iterator pointing just beyond the values written to result.
00229    */
00230   template<typename _InputIterator, typename _OutputIterator>
00231     _OutputIterator
00232     partial_sum(_InputIterator __first, _InputIterator __last,
00233         _OutputIterator __result)
00234     {
00235       typedef typename iterator_traits<_InputIterator>::value_type _ValueType;
00236 
00237       // concept requirements
00238       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
00239       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
00240                                          _ValueType>)
00241       __glibcxx_requires_valid_range(__first, __last);
00242 
00243       if (__first == __last)
00244     return __result;
00245       _ValueType __value = *__first;
00246       *__result = __value;
00247       while (++__first != __last)
00248     {
00249       __value = __value + *__first;
00250       *++__result = __value;
00251     }
00252       return ++__result;
00253     }
00254 
00255   /**
00256    *  @brief  Return list of partial sums
00257    *
00258    *  Accumulates the values in the range [first,last) using operator+().
00259    *  As each successive input value is added into the total, that partial sum
00260    *  is written to @a result.  Therefore, the first value in result is the
00261    *  first value of the input, the second value in result is the sum of the
00262    *  first and second input values, and so on.
00263    *
00264    *  @param  first  Start of input range.
00265    *  @param  last  End of input range.
00266    *  @param  result  Output to write sums to.
00267    *  @return  Iterator pointing just beyond the values written to result.
00268    */
00269   template<typename _InputIterator, typename _OutputIterator,
00270        typename _BinaryOperation>
00271     _OutputIterator
00272     partial_sum(_InputIterator __first, _InputIterator __last,
00273         _OutputIterator __result, _BinaryOperation __binary_op)
00274     {
00275       typedef typename iterator_traits<_InputIterator>::value_type _ValueType;
00276 
00277       // concept requirements
00278       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
00279       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
00280                                          _ValueType>)
00281       __glibcxx_requires_valid_range(__first, __last);
00282 
00283       if (__first == __last)
00284     return __result;
00285       _ValueType __value = *__first;
00286       *__result = __value;
00287       while (++__first != __last)
00288     {
00289       __value = __binary_op(__value, *__first);
00290       *++__result = __value;
00291     }
00292       return ++__result;
00293     }
00294 
00295   /**
00296    *  @brief  Return differences between adjacent values.
00297    *
00298    *  Computes the difference between adjacent values in the range
00299    *  [first,last) using operator-() and writes the result to @a result.
00300    *
00301    *  @param  first  Start of input range.
00302    *  @param  last  End of input range.
00303    *  @param  result  Output to write sums to.
00304    *  @return  Iterator pointing just beyond the values written to result.
00305    */
00306   template<typename _InputIterator, typename _OutputIterator>
00307     _OutputIterator
00308     adjacent_difference(_InputIterator __first,
00309             _InputIterator __last, _OutputIterator __result)
00310     {
00311       typedef typename iterator_traits<_InputIterator>::value_type _ValueType;
00312 
00313       // concept requirements
00314       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
00315       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
00316                                          _ValueType>)
00317       __glibcxx_requires_valid_range(__first, __last);
00318 
00319       if (__first == __last)
00320     return __result;
00321       _ValueType __value = *__first;
00322       *__result = __value;
00323       while (++__first != __last)
00324     {
00325       _ValueType __tmp = *__first;
00326       *++__result = __tmp - __value;
00327       __value = __tmp;
00328     }
00329       return ++__result;
00330     }
00331 
00332   /**
00333    *  @brief  Return differences between adjacent values.
00334    *
00335    *  Computes the difference between adjacent values in the range
00336    *  [first,last) using the function object @a binary_op and writes the
00337    *  result to @a result.
00338    *
00339    *  @param  first  Start of input range.
00340    *  @param  last  End of input range.
00341    *  @param  result  Output to write sums to.
00342    *  @return  Iterator pointing just beyond the values written to result.
00343    */
00344   template<typename _InputIterator, typename _OutputIterator,
00345        typename _BinaryOperation>
00346     _OutputIterator
00347     adjacent_difference(_InputIterator __first, _InputIterator __last,
00348             _OutputIterator __result, _BinaryOperation __binary_op)
00349     {
00350       typedef typename iterator_traits<_InputIterator>::value_type _ValueType;
00351 
00352       // concept requirements
00353       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
00354       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
00355                                          _ValueType>)
00356       __glibcxx_requires_valid_range(__first, __last);
00357 
00358       if (__first == __last)
00359     return __result;
00360       _ValueType __value = *__first;
00361       *__result = __value;
00362       while (++__first != __last)
00363     {
00364       _ValueType __tmp = *__first;
00365       *++__result = __binary_op(__tmp, __value);
00366       __value = __tmp;
00367     }
00368       return ++__result;
00369     }
00370 
00371 _GLIBCXX_END_NESTED_NAMESPACE
00372 
00373 #endif /* _STL_NUMERIC_H */

Generated on Thu Jul 23 21:16:22 2009 for libstdc++ by  doxygen 1.5.8