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, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
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,
00207                                          _ValueType>)
00208       __glibcxx_requires_valid_range(__first, __last);
00209 
00210       if (__first == __last)
00211     return __result;
00212       _ValueType __value = *__first;
00213       *__result = __value;
00214       while (++__first != __last)
00215     {
00216       __value = __value + *__first;
00217       *++__result = __value;
00218     }
00219       return ++__result;
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        typename _BinaryOperation>
00238     _OutputIterator
00239     partial_sum(_InputIterator __first, _InputIterator __last,
00240         _OutputIterator __result, _BinaryOperation __binary_op)
00241     {
00242       typedef typename iterator_traits<_InputIterator>::value_type _ValueType;
00243 
00244       // concept requirements
00245       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
00246       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
00247                                          _ValueType>)
00248       __glibcxx_requires_valid_range(__first, __last);
00249 
00250       if (__first == __last)
00251     return __result;
00252       _ValueType __value = *__first;
00253       *__result = __value;
00254       while (++__first != __last)
00255     {
00256       __value = __binary_op(__value, *__first);
00257       *++__result = __value;
00258     }
00259       return ++__result;
00260     }
00261 
00262   /**
00263    *  @brief  Return differences between adjacent values.
00264    *
00265    *  Computes the difference between adjacent values in the range
00266    *  [first,last) using operator-() and writes the result to @a result.
00267    *
00268    *  @param  first  Start of input range.
00269    *  @param  last  End of input range.
00270    *  @param  result  Output to write sums to.
00271    *  @return  Iterator pointing just beyond the values written to result.
00272    */
00273   template<typename _InputIterator, typename _OutputIterator>
00274     _OutputIterator
00275     adjacent_difference(_InputIterator __first,
00276             _InputIterator __last, _OutputIterator __result)
00277     {
00278       typedef typename iterator_traits<_InputIterator>::value_type _ValueType;
00279 
00280       // concept requirements
00281       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
00282       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
00283                                          _ValueType>)
00284       __glibcxx_requires_valid_range(__first, __last);
00285 
00286       if (__first == __last)
00287     return __result;
00288       _ValueType __value = *__first;
00289       *__result = __value;
00290       while (++__first != __last)
00291     {
00292       _ValueType __tmp = *__first;
00293       *++__result = __tmp - __value;
00294       __value = __tmp;
00295     }
00296       return ++__result;
00297     }
00298 
00299   /**
00300    *  @brief  Return differences between adjacent values.
00301    *
00302    *  Computes the difference between adjacent values in the range
00303    *  [first,last) using the function object @a binary_op and writes the
00304    *  result to @a result.
00305    *
00306    *  @param  first  Start of input range.
00307    *  @param  last  End of input range.
00308    *  @param  result  Output to write sums to.
00309    *  @return  Iterator pointing just beyond the values written to result.
00310    */
00311   template<typename _InputIterator, typename _OutputIterator,
00312        typename _BinaryOperation>
00313     _OutputIterator
00314     adjacent_difference(_InputIterator __first, _InputIterator __last,
00315             _OutputIterator __result, _BinaryOperation __binary_op)
00316     {
00317       typedef typename iterator_traits<_InputIterator>::value_type _ValueType;
00318 
00319       // concept requirements
00320       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
00321       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
00322                                          _ValueType>)
00323       __glibcxx_requires_valid_range(__first, __last);
00324 
00325       if (__first == __last)
00326     return __result;
00327       _ValueType __value = *__first;
00328       *__result = __value;
00329       while (++__first != __last)
00330     {
00331       _ValueType __tmp = *__first;
00332       *++__result = __binary_op(__tmp, __value);
00333       __value = __tmp;
00334     }
00335       return ++__result;
00336     }
00337 
00338 } // namespace std
00339 
00340 #endif /* _STL_NUMERIC_H */

Generated on Tue Dec 2 03:59:29 2008 for libstdc++ by  doxygen 1.5.7.1