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