stl_numeric.h

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

Generated on Thu Nov 1 13:12:33 2007 for libstdc++ by  doxygen 1.5.1