libstdc++
stl_numeric.h
Go to the documentation of this file.
00001 // Numeric functions implementation -*- C++ -*-
00002 
00003 // Copyright (C) 2001-2013 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 3, 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 // Under Section 7 of GPL version 3, you are granted additional
00017 // permissions described in the GCC Runtime Library Exception, version
00018 // 3.1, as published by the Free Software Foundation.
00019 
00020 // You should have received a copy of the GNU General Public License and
00021 // a copy of the GCC Runtime Library Exception along with this program;
00022 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
00023 // <http://www.gnu.org/licenses/>.
00024 
00025 /*
00026  *
00027  * Copyright (c) 1994
00028  * Hewlett-Packard Company
00029  *
00030  * Permission to use, copy, modify, distribute and sell this software
00031  * and its documentation for any purpose is hereby granted without fee,
00032  * provided that the above copyright notice appear in all copies and
00033  * that both that copyright notice and this permission notice appear
00034  * in supporting documentation.  Hewlett-Packard Company makes no
00035  * representations about the suitability of this software for any
00036  * purpose.  It is provided "as is" without express or implied warranty.
00037  *
00038  *
00039  * Copyright (c) 1996,1997
00040  * Silicon Graphics Computer Systems, Inc.
00041  *
00042  * Permission to use, copy, modify, distribute and sell this software
00043  * and its documentation for any purpose is hereby granted without fee,
00044  * provided that the above copyright notice appear in all copies and
00045  * that both that copyright notice and this permission notice appear
00046  * in supporting documentation.  Silicon Graphics makes no
00047  * representations about the suitability of this software for any
00048  * purpose.  It is provided "as is" without express or implied warranty.
00049  */
00050 
00051 /** @file bits/stl_numeric.h
00052  *  This is an internal header file, included by other library headers.
00053  *  Do not attempt to use it directly. @headername{numeric}
00054  */
00055 
00056 #ifndef _STL_NUMERIC_H
00057 #define _STL_NUMERIC_H 1
00058 
00059 #include <bits/concept_check.h>
00060 #include <debug/debug.h>
00061 #include <bits/move.h> // For _GLIBCXX_MOVE
00062 
00063 #if __cplusplus >= 201103L
00064 
00065 namespace std _GLIBCXX_VISIBILITY(default)
00066 {
00067 _GLIBCXX_BEGIN_NAMESPACE_VERSION
00068 
00069   /**
00070    *  @brief  Create a range of sequentially increasing values.
00071    *
00072    *  For each element in the range @p [first,last) assigns @p value and
00073    *  increments @p value as if by @p ++value.
00074    *
00075    *  @param  __first  Start of range.
00076    *  @param  __last  End of range.
00077    *  @param  __value  Starting value.
00078    *  @return  Nothing.
00079    */
00080   template<typename _ForwardIterator, typename _Tp>
00081     void
00082     iota(_ForwardIterator __first, _ForwardIterator __last, _Tp __value)
00083     {
00084       // concept requirements
00085       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
00086                   _ForwardIterator>)
00087       __glibcxx_function_requires(_ConvertibleConcept<_Tp,
00088         typename iterator_traits<_ForwardIterator>::value_type>)
00089       __glibcxx_requires_valid_range(__first, __last);
00090 
00091       for (; __first != __last; ++__first)
00092     {
00093       *__first = __value;
00094       ++__value;
00095     }
00096     }
00097 
00098 _GLIBCXX_END_NAMESPACE_VERSION
00099 } // namespace std
00100 
00101 #endif
00102 
00103 namespace std _GLIBCXX_VISIBILITY(default)
00104 {
00105 _GLIBCXX_BEGIN_NAMESPACE_ALGO
00106 
00107   /**
00108    *  @brief  Accumulate values in a range.
00109    *
00110    *  Accumulates the values in the range [first,last) using operator+().  The
00111    *  initial value is @a init.  The values are processed in order.
00112    *
00113    *  @param  __first  Start of range.
00114    *  @param  __last  End of range.
00115    *  @param  __init  Starting value to add other values to.
00116    *  @return  The final sum.
00117    */
00118   template<typename _InputIterator, typename _Tp>
00119     inline _Tp
00120     accumulate(_InputIterator __first, _InputIterator __last, _Tp __init)
00121     {
00122       // concept requirements
00123       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
00124       __glibcxx_requires_valid_range(__first, __last);
00125 
00126       for (; __first != __last; ++__first)
00127     __init = __init + *__first;
00128       return __init;
00129     }
00130 
00131   /**
00132    *  @brief  Accumulate values in a range with operation.
00133    *
00134    *  Accumulates the values in the range [first,last) using the function
00135    *  object @p __binary_op.  The initial value is @p __init.  The values are
00136    *  processed in order.
00137    *
00138    *  @param  __first  Start of range.
00139    *  @param  __last  End of range.
00140    *  @param  __init  Starting value to add other values to.
00141    *  @param  __binary_op  Function object to accumulate with.
00142    *  @return  The final sum.
00143    */
00144   template<typename _InputIterator, typename _Tp, typename _BinaryOperation>
00145     inline _Tp
00146     accumulate(_InputIterator __first, _InputIterator __last, _Tp __init,
00147            _BinaryOperation __binary_op)
00148     {
00149       // concept requirements
00150       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
00151       __glibcxx_requires_valid_range(__first, __last);
00152 
00153       for (; __first != __last; ++__first)
00154     __init = __binary_op(__init, *__first);
00155       return __init;
00156     }
00157 
00158   /**
00159    *  @brief  Compute inner product of two ranges.
00160    *
00161    *  Starting with an initial value of @p __init, multiplies successive
00162    *  elements from the two ranges and adds each product into the accumulated
00163    *  value using operator+().  The values in the ranges are processed in
00164    *  order.
00165    *
00166    *  @param  __first1  Start of range 1.
00167    *  @param  __last1  End of range 1.
00168    *  @param  __first2  Start of range 2.
00169    *  @param  __init  Starting value to add other values to.
00170    *  @return  The final inner product.
00171    */
00172   template<typename _InputIterator1, typename _InputIterator2, typename _Tp>
00173     inline _Tp
00174     inner_product(_InputIterator1 __first1, _InputIterator1 __last1,
00175           _InputIterator2 __first2, _Tp __init)
00176     {
00177       // concept requirements
00178       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
00179       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
00180       __glibcxx_requires_valid_range(__first1, __last1);
00181 
00182       for (; __first1 != __last1; ++__first1, ++__first2)
00183     __init = __init + (*__first1 * *__first2);
00184       return __init;
00185     }
00186 
00187   /**
00188    *  @brief  Compute inner product of two ranges.
00189    *
00190    *  Starting with an initial value of @p __init, applies @p __binary_op2 to
00191    *  successive elements from the two ranges and accumulates each result into
00192    *  the accumulated value using @p __binary_op1.  The values in the ranges are
00193    *  processed in order.
00194    *
00195    *  @param  __first1  Start of range 1.
00196    *  @param  __last1  End of range 1.
00197    *  @param  __first2  Start of range 2.
00198    *  @param  __init  Starting value to add other values to.
00199    *  @param  __binary_op1  Function object to accumulate with.
00200    *  @param  __binary_op2  Function object to apply to pairs of input values.
00201    *  @return  The final inner product.
00202    */
00203   template<typename _InputIterator1, typename _InputIterator2, typename _Tp,
00204        typename _BinaryOperation1, typename _BinaryOperation2>
00205     inline _Tp
00206     inner_product(_InputIterator1 __first1, _InputIterator1 __last1,
00207           _InputIterator2 __first2, _Tp __init,
00208           _BinaryOperation1 __binary_op1,
00209           _BinaryOperation2 __binary_op2)
00210     {
00211       // concept requirements
00212       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
00213       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
00214       __glibcxx_requires_valid_range(__first1, __last1);
00215 
00216       for (; __first1 != __last1; ++__first1, ++__first2)
00217     __init = __binary_op1(__init, __binary_op2(*__first1, *__first2));
00218       return __init;
00219     }
00220 
00221   /**
00222    *  @brief  Return list of partial sums
00223    *
00224    *  Accumulates the values in the range [first,last) using the @c + operator.
00225    *  As each successive input value is added into the total, that partial sum
00226    *  is written to @p __result.  Therefore, the first value in @p __result is
00227    *  the first value of the input, the second value in @p __result is the sum
00228    *  of the first and second input values, and so on.
00229    *
00230    *  @param  __first  Start of input range.
00231    *  @param  __last  End of input range.
00232    *  @param  __result  Output sum.
00233    *  @return  Iterator pointing just beyond the values written to __result.
00234    */
00235   template<typename _InputIterator, typename _OutputIterator>
00236     _OutputIterator
00237     partial_sum(_InputIterator __first, _InputIterator __last,
00238         _OutputIterator __result)
00239     {
00240       typedef typename iterator_traits<_InputIterator>::value_type _ValueType;
00241 
00242       // concept requirements
00243       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
00244       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
00245                                          _ValueType>)
00246       __glibcxx_requires_valid_range(__first, __last);
00247 
00248       if (__first == __last)
00249     return __result;
00250       _ValueType __value = *__first;
00251       *__result = __value;
00252       while (++__first != __last)
00253     {
00254       __value = __value + *__first;
00255       *++__result = __value;
00256     }
00257       return ++__result;
00258     }
00259 
00260   /**
00261    *  @brief  Return list of partial sums
00262    *
00263    *  Accumulates the values in the range [first,last) using @p __binary_op.
00264    *  As each successive input value is added into the total, that partial sum
00265    *  is written to @p __result.  Therefore, the first value in @p __result is
00266    *  the first value of the input, the second value in @p __result is the sum
00267    *  of the first and second input values, and so on.
00268    *
00269    *  @param  __first  Start of input range.
00270    *  @param  __last  End of input range.
00271    *  @param  __result  Output sum.
00272    *  @param  __binary_op  Function object.
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 @p __result.
00306    *
00307    *  @param  __first  Start of input range.
00308    *  @param  __last  End of input range.
00309    *  @param  __result  Output sums.
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 @p __binary_op and writes the
00346    *  result to @p __result.
00347    *
00348    *  @param  __first  Start of input range.
00349    *  @param  __last  End of input range.
00350    *  @param  __result  Output sum.
00351    *  @param  __binary_op Function object.
00352    *  @return  Iterator pointing just beyond the values written to result.
00353    *
00354    *  _GLIBCXX_RESOLVE_LIB_DEFECTS
00355    *  DR 539. partial_sum and adjacent_difference should mention requirements
00356    */
00357   template<typename _InputIterator, typename _OutputIterator,
00358        typename _BinaryOperation>
00359     _OutputIterator
00360     adjacent_difference(_InputIterator __first, _InputIterator __last,
00361             _OutputIterator __result, _BinaryOperation __binary_op)
00362     {
00363       typedef typename iterator_traits<_InputIterator>::value_type _ValueType;
00364 
00365       // concept requirements
00366       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
00367       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
00368                                          _ValueType>)
00369       __glibcxx_requires_valid_range(__first, __last);
00370 
00371       if (__first == __last)
00372     return __result;
00373       _ValueType __value = *__first;
00374       *__result = __value;
00375       while (++__first != __last)
00376     {
00377       _ValueType __tmp = *__first;
00378       *++__result = __binary_op(__tmp, __value);
00379       __value = _GLIBCXX_MOVE(__tmp);
00380     }
00381       return ++__result;
00382     }
00383 
00384 _GLIBCXX_END_NAMESPACE_ALGO
00385 } // namespace std
00386 
00387 #endif /* _STL_NUMERIC_H */