libstdc++-v3/include/bits/stl_numeric.h

   1 // Numeric functions implementation -*- C++ -*-
   2
   3 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007
   4 // Free Software Foundation, Inc.
   5 //
   6 // This file is part of the GNU ISO C++ Library.  This library is free
   7 // software; you can redistribute it and/or modify it under the
   8 // terms of the GNU General Public License as published by the
   9 // Free Software Foundation; either version 2, or (at your option)
  10 // any later version.
  11
  12 // This library is distributed in the hope that it will be useful,
  13 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 // GNU General Public License for more details.
  16
  17 // You should have received a copy of the GNU General Public License along
  18 // with this library; see the file COPYING.  If not, write to the Free
  19 // Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
  20 // USA.
  21
  22 // As a special exception, you may use this file as part of a free software
  23 // library without restriction.  Specifically, if other files instantiate
  24 // templates or use macros or inline functions from this file, or you compile
  25 // this file and link it with other files to produce an executable, this
  26 // file does not by itself cause the resulting executable to be covered by
  27 // the GNU General Public License.  This exception does not however
  28 // invalidate any other reasons why the executable file might be covered by
  29 // the GNU General Public License.
  30
  31 /*
  32  *
  33  * Copyright (c) 1994
  34  * Hewlett-Packard Company
  35  *
  36  * Permission to use, copy, modify, distribute and sell this software
  37  * and its documentation for any purpose is hereby granted without fee,
  38  * provided that the above copyright notice appear in all copies and
  39  * that both that copyright notice and this permission notice appear
  40  * in supporting documentation.  Hewlett-Packard Company makes no
  41  * representations about the suitability of this software for any
  42  * purpose.  It is provided "as is" without express or implied warranty.
  43  *
  44  *
  45  * Copyright (c) 1996,1997
  46  * Silicon Graphics Computer Systems, Inc.
  47  *
  48  * Permission to use, copy, modify, distribute and sell this software
  49  * and its documentation for any purpose is hereby granted without fee,
  50  * provided that the above copyright notice appear in all copies and
  51  * that both that copyright notice and this permission notice appear
  52  * in supporting documentation.  Silicon Graphics makes no
  53  * representations about the suitability of this software for any
  54  * purpose.  It is provided "as is" without express or implied warranty.
  55  */
  56
  57 /** @file stl_numeric.h
  58  *  This is an internal header file, included by other library headers.
  59  *  You should not attempt to use it directly.
  60  */
  61
  62 #ifndef _STL_NUMERIC_H
  63 #define _STL_NUMERIC_H 1
  64
  65 #include <bits/concept_check.h>
  66 #include <debug/debug.h>
  67
  68 _GLIBCXX_BEGIN_NAMESPACE(std)
  69
  70   /**
  71    *  @brief  Accumulate values in a range.
  72    *
  73    *  Accumulates the values in the range [first,last) using operator+().  The
  74    *  initial value is @a init.  The values are processed in order.
  75    *
  76    *  @param  first  Start of range.
  77    *  @param  last  End of range.
  78    *  @param  init  Starting value to add other values to.
  79    *  @return  The final sum.
  80    */
  81   template<typename _InputIterator, typename _Tp>
  82     inline _Tp
  83     accumulate(_InputIterator __first, _InputIterator __last, _Tp __init)
  84     {
  85       // concept requirements
  86       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
  87       __glibcxx_requires_valid_range(__first, __last);
  88
  89       for (; __first != __last; ++__first)
  90         __init = __init + *__first;
  91       return __init;
  92     }
  93
  94   /**
  95    *  @brief  Accumulate values in a range with operation.
  96    *
  97    *  Accumulates the values in the range [first,last) using the function
  98    *  object @a binary_op.  The initial value is @a init.  The values are
  99    *  processed in order.
 100    *
 101    *  @param  first  Start of range.
 102    *  @param  last  End of range.
 103    *  @param  init  Starting value to add other values to.
 104    *  @param  binary_op  Function object to accumulate with.
 105    *  @return  The final sum.
 106    */
 107   template<typename _InputIterator, typename _Tp, typename _BinaryOperation>
 108     inline _Tp
 109     accumulate(_InputIterator __first, _InputIterator __last, _Tp __init,
 110                _BinaryOperation __binary_op)
 111     {
 112       // concept requirements
 113       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
 114       __glibcxx_requires_valid_range(__first, __last);
 115
 116       for (; __first != __last; ++__first)
 117         __init = __binary_op(__init, *__first);
 118       return __init;
 119     }
 120
 121   /**
 122    *  @brief  Compute inner product of two ranges.
 123    *
 124    *  Starting with an initial value of @a init, multiplies successive
 125    *  elements from the two ranges and adds each product into the accumulated
 126    *  value using operator+().  The values in the ranges are processed in
 127    *  order.
 128    *
 129    *  @param  first1  Start of range 1.
 130    *  @param  last1  End of range 1.
 131    *  @param  first2  Start of range 2.
 132    *  @param  init  Starting value to add other values to.
 133    *  @return  The final inner product.
 134    */
 135   template<typename _InputIterator1, typename _InputIterator2, typename _Tp>
 136     inline _Tp
 137     inner_product(_InputIterator1 __first1, _InputIterator1 __last1,
 138                   _InputIterator2 __first2, _Tp __init)
 139     {
 140       // concept requirements
 141       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
 142       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
 143       __glibcxx_requires_valid_range(__first1, __last1);
 144
 145       for (; __first1 != __last1; ++__first1, ++__first2)
 146         __init = __init + (*__first1 * *__first2);
 147       return __init;
 148     }
 149
 150   /**
 151    *  @brief  Compute inner product of two ranges.
 152    *
 153    *  Starting with an initial value of @a init, applies @a binary_op2 to
 154    *  successive elements from the two ranges and accumulates each result into
 155    *  the accumulated value using @a binary_op1.  The values in the ranges are
 156    *  processed in order.
 157    *
 158    *  @param  first1  Start of range 1.
 159    *  @param  last1  End of range 1.
 160    *  @param  first2  Start of range 2.
 161    *  @param  init  Starting value to add other values to.
 162    *  @param  binary_op1  Function object to accumulate with.
 163    *  @param  binary_op2  Function object to apply to pairs of input values.
 164    *  @return  The final inner product.
 165    */
 166   template<typename _InputIterator1, typename _InputIterator2, typename _Tp,
 167             typename _BinaryOperation1, typename _BinaryOperation2>
 168     inline _Tp
 169     inner_product(_InputIterator1 __first1, _InputIterator1 __last1,
 170                   _InputIterator2 __first2, _Tp __init,
 171                   _BinaryOperation1 __binary_op1,
 172                   _BinaryOperation2 __binary_op2)
 173     {
 174       // concept requirements
 175       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
 176       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
 177       __glibcxx_requires_valid_range(__first1, __last1);
 178
 179       for (; __first1 != __last1; ++__first1, ++__first2)
 180         __init = __binary_op1(__init, __binary_op2(*__first1, *__first2));
 181       return __init;
 182     }
 183
 184   /**
 185    *  @brief  Return list of partial sums
 186    *
 187    *  Accumulates the values in the range [first,last) using operator+().
 188    *  As each successive input value is added into the total, that partial sum
 189    *  is written to @a result.  Therefore, the first value in result is the
 190    *  first value of the input, the second value in result is the sum of the
 191    *  first and second input values, and so on.
 192    *
 193    *  @param  first  Start of input range.
 194    *  @param  last  End of input range.
 195    *  @param  result  Output to write sums to.
 196    *  @return  Iterator pointing just beyond the values written to result.
 197    */
 198   template<typename _InputIterator, typename _OutputIterator>
 199     _OutputIterator
 200     partial_sum(_InputIterator __first, _InputIterator __last,
 201                 _OutputIterator __result)
 202     {
 203       typedef typename iterator_traits<_InputIterator>::value_type _ValueType;
 204
 205       // concept requirements
 206       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
 207       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
 208                                                          _ValueType>)
 209       __glibcxx_requires_valid_range(__first, __last);
 210
 211       if (__first == __last)
 212         return __result;
 213       _ValueType __value = *__first;
 214       *__result = __value;
 215       while (++__first != __last)
 216         {
 217           __value = __value + *__first;
 218           *++__result = __value;
 219         }
 220       return ++__result;
 221     }
 222
 223   /**
 224    *  @brief  Return list of partial sums
 225    *
 226    *  Accumulates the values in the range [first,last) using operator+().
 227    *  As each successive input value is added into the total, that partial sum
 228    *  is written to @a result.  Therefore, the first value in result is the
 229    *  first value of the input, the second value in result is the sum of the
 230    *  first and second input values, and so on.
 231    *
 232    *  @param  first  Start of input range.
 233    *  @param  last  End of input range.
 234    *  @param  result  Output to write sums to.
 235    *  @return  Iterator pointing just beyond the values written to result.
 236    */
 237   template<typename _InputIterator, typename _OutputIterator,
 238            typename _BinaryOperation>
 239     _OutputIterator
 240     partial_sum(_InputIterator __first, _InputIterator __last,
 241                 _OutputIterator __result, _BinaryOperation __binary_op)
 242     {
 243       typedef typename iterator_traits<_InputIterator>::value_type _ValueType;
 244
 245       // concept requirements
 246       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
 247       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
 248                                                          _ValueType>)
 249       __glibcxx_requires_valid_range(__first, __last);
 250
 251       if (__first == __last)
 252         return __result;
 253       _ValueType __value = *__first;
 254       *__result = __value;
 255       while (++__first != __last)
 256         {
 257           __value = __binary_op(__value, *__first);
 258           *++__result = __value;
 259         }
 260       return ++__result;
 261     }
 262
 263   /**
 264    *  @brief  Return differences between adjacent values.
 265    *
 266    *  Computes the difference between adjacent values in the range
 267    *  [first,last) using operator-() and writes the result to @a result.
 268    *
 269    *  @param  first  Start of input range.
 270    *  @param  last  End of input range.
 271    *  @param  result  Output to write sums to.
 272    *  @return  Iterator pointing just beyond the values written to result.
 273    */
 274   template<typename _InputIterator, typename _OutputIterator>
 275     _OutputIterator
 276     adjacent_difference(_InputIterator __first,
 277                         _InputIterator __last, _OutputIterator __result)
 278     {
 279       typedef typename iterator_traits<_InputIterator>::value_type _ValueType;
 280
 281       // concept requirements
 282       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
 283       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
 284                                                          _ValueType>)
 285       __glibcxx_requires_valid_range(__first, __last);
 286
 287       if (__first == __last)
 288         return __result;
 289       _ValueType __value = *__first;
 290       *__result = __value;
 291       while (++__first != __last)
 292         {
 293           _ValueType __tmp = *__first;
 294           *++__result = __tmp - __value;
 295           __value = __tmp;
 296         }
 297       return ++__result;
 298     }
 299
 300   /**
 301    *  @brief  Return differences between adjacent values.
 302    *
 303    *  Computes the difference between adjacent values in the range
 304    *  [first,last) using the function object @a binary_op and writes the
 305    *  result to @a result.
 306    *
 307    *  @param  first  Start of input range.
 308    *  @param  last  End of input range.
 309    *  @param  result  Output to write sums to.
 310    *  @return  Iterator pointing just beyond the values written to result.
 311    */
 312   template<typename _InputIterator, typename _OutputIterator,
 313            typename _BinaryOperation>
 314     _OutputIterator
 315     adjacent_difference(_InputIterator __first, _InputIterator __last,
 316                         _OutputIterator __result, _BinaryOperation __binary_op)
 317     {
 318       typedef typename iterator_traits<_InputIterator>::value_type _ValueType;
 319
 320       // concept requirements
 321       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
 322       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
 323                                                          _ValueType>)
 324       __glibcxx_requires_valid_range(__first, __last);
 325
 326       if (__first == __last)
 327         return __result;
 328       _ValueType __value = *__first;
 329       *__result = __value;
 330       while (++__first != __last)
 331         {
 332           _ValueType __tmp = *__first;
 333           *++__result = __binary_op(__tmp, __value);
 334           __value = __tmp;
 335         }
 336       return ++__result;
 337     }
 338
 339 _GLIBCXX_END_NAMESPACE
 340
 341 #endif /* _STL_NUMERIC_H */