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 @a binary_op.  The initial value is @a 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 @a 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 @a init, applies @a binary_op2 to
00192    *  successive elements from the two ranges and accumulates each result into
00193    *  the accumulated value using @a 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 operator+().
00226    *  As each successive input value is added into the total, that partial sum
00227    *  is written to @a result.  Therefore, the first value in result is the
00228    *  first value of the input, the second value in result is the sum of the
00229    *  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 to write sums to.
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 operator+().
00265    *  As each successive input value is added into the total, that partial sum
00266    *  is written to @a result.  Therefore, the first value in result is the
00267    *  first value of the input, the second value in result is the sum of the
00268    *  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 to write sums to.
00273    *  @return  Iterator pointing just beyond the values written to result.
00274    */
00275   template<typename _InputIterator, typename _OutputIterator,
00276        typename _BinaryOperation>
00277     _OutputIterator
00278     partial_sum(_InputIterator __first, _InputIterator __last,
00279         _OutputIterator __result, _BinaryOperation __binary_op)
00280     {
00281       typedef typename iterator_traits<_InputIterator>::value_type _ValueType;
00282 
00283       // concept requirements
00284       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
00285       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
00286                                          _ValueType>)
00287       __glibcxx_requires_valid_range(__first, __last);
00288 
00289       if (__first == __last)
00290     return __result;
00291       _ValueType __value = *__first;
00292       *__result = __value;
00293       while (++__first != __last)
00294     {
00295       __value = __binary_op(__value, *__first);
00296       *++__result = __value;
00297     }
00298       return ++__result;
00299     }
00300 
00301   /**
00302    *  @brief  Return differences between adjacent values.
00303    *
00304    *  Computes the difference between adjacent values in the range
00305    *  [first,last) using operator-() and writes the result to @a result.
00306    *
00307    *  @param  first  Start of input range.
00308    *  @param  last  End of input range.
00309    *  @param  result  Output to write sums to.
00310    *  @return  Iterator pointing just beyond the values written to result.
00311    *
00312    *  _GLIBCXX_RESOLVE_LIB_DEFECTS
00313    *  DR 539. partial_sum and adjacent_difference should mention requirements
00314    */
00315   template<typename _InputIterator, typename _OutputIterator>
00316     _OutputIterator
00317     adjacent_difference(_InputIterator __first,
00318             _InputIterator __last, _OutputIterator __result)
00319     {
00320       typedef typename iterator_traits<_InputIterator>::value_type _ValueType;
00321 
00322       // concept requirements
00323       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
00324       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
00325                                          _ValueType>)
00326       __glibcxx_requires_valid_range(__first, __last);
00327 
00328       if (__first == __last)
00329     return __result;
00330       _ValueType __value = *__first;
00331       *__result = __value;
00332       while (++__first != __last)
00333     {
00334       _ValueType __tmp = *__first;
00335       *++__result = __tmp - __value;
00336       __value = _GLIBCXX_MOVE(__tmp);
00337     }
00338       return ++__result;
00339     }
00340 
00341   /**
00342    *  @brief  Return differences between adjacent values.
00343    *
00344    *  Computes the difference between adjacent values in the range
00345    *  [first,last) using the function object @a binary_op and writes the
00346    *  result to @a result.
00347    *
00348    *  @param  first  Start of input range.
00349    *  @param  last  End of input range.
00350    *  @param  result  Output to write sums to.
00351    *  @return  Iterator pointing just beyond the values written to result.
00352    *
00353    *  _GLIBCXX_RESOLVE_LIB_DEFECTS
00354    *  DR 539. partial_sum and adjacent_difference should mention requirements
00355    */
00356   template<typename _InputIterator, typename _OutputIterator,
00357        typename _BinaryOperation>
00358     _OutputIterator
00359     adjacent_difference(_InputIterator __first, _InputIterator __last,
00360             _OutputIterator __result, _BinaryOperation __binary_op)
00361     {
00362       typedef typename iterator_traits<_InputIterator>::value_type _ValueType;
00363 
00364       // concept requirements
00365       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
00366       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
00367                                          _ValueType>)
00368       __glibcxx_requires_valid_range(__first, __last);
00369 
00370       if (__first == __last)
00371     return __result;
00372       _ValueType __value = *__first;
00373       *__result = __value;
00374       while (++__first != __last)
00375     {
00376       _ValueType __tmp = *__first;
00377       *++__result = __binary_op(__tmp, __value);
00378       __value = _GLIBCXX_MOVE(__tmp);
00379     }
00380       return ++__result;
00381     }
00382 
00383 _GLIBCXX_END_NAMESPACE_ALGO
00384 } // namespace std
00385 
00386 #endif /* _STL_NUMERIC_H */