# stl_numeric.h

Go to the documentation of this file.

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