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

   1 // Numeric functions implementation -*- C++ -*-
   2
   3 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008
   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 #ifdef __GXX_EXPERIMENTAL_CXX0X__
  69
  70 _GLIBCXX_BEGIN_NAMESPACE(std)
  71
  72   /**
  73    *  @brief  Create a range of sequentially increasing values.
  74    *
  75    *  For each element in the range @p [first,last) assigns @p value and
  76    *  increments @p value as if by @p ++value.
  77    *
  78    *  @param  first  Start of range.
  79    *  @param  last  End of range.
  80    *  @param  value  Starting value.
  81    *  @return  Nothing.
  82    */
  83   template<typename _ForwardIterator, typename _Tp>
  84     void
  85     iota(_ForwardIterator __first, _ForwardIterator __last, _Tp __value)
  86     {
  87       // concept requirements
  88       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
  89                                   _ForwardIterator>)
  90       __glibcxx_function_requires(_ConvertibleConcept<_Tp,
  91             typename iterator_traits<_ForwardIterator>::value_type>)
  92       __glibcxx_requires_valid_range(__first, __last);
  93
  94       for (; __first != __last; ++__first)
  95         {
  96           *__first = __value;
  97           ++__value;
  98         }
  99     }
 100
 101 _GLIBCXX_END_NAMESPACE
 102
 103 #endif
 104
 105 _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_P)
 106
 107   /**
 108    *  @brief  Accumulate values in a range.
 109    *
 110    *  Accumulates the values in the range [first,last) using operator+().  The
 111    *  initial value is @a init.  The values are processed in order.
 112    *
 113    *  @param  first  Start of range.
 114    *  @param  last  End of range.
 115    *  @param  init  Starting value to add other values to.
 116    *  @return  The final sum.
 117    */
 118   template<typename _InputIterator, typename _Tp>
 119     inline _Tp
 120     accumulate(_InputIterator __first, _InputIterator __last, _Tp __init)
 121     {
 122       // concept requirements
 123       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
 124       __glibcxx_requires_valid_range(__first, __last);
 125
 126       for (; __first != __last; ++__first)
 127         __init = __init + *__first;
 128       return __init;
 129     }
 130
 131   /**
 132    *  @brief  Accumulate values in a range with operation.
 133    *
 134    *  Accumulates the values in the range [first,last) using the function
 135    *  object @a binary_op.  The initial value is @a init.  The values are
 136    *  processed in order.
 137    *
 138    *  @param  first  Start of range.
 139    *  @param  last  End of range.
 140    *  @param  init  Starting value to add other values to.
 141    *  @param  binary_op  Function object to accumulate with.
 142    *  @return  The final sum.
 143    */
 144   template<typename _InputIterator, typename _Tp, typename _BinaryOperation>
 145     inline _Tp
 146     accumulate(_InputIterator __first, _InputIterator __last, _Tp __init,
 147                _BinaryOperation __binary_op)
 148     {
 149       // concept requirements
 150       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
 151       __glibcxx_requires_valid_range(__first, __last);
 152
 153       for (; __first != __last; ++__first)
 154         __init = __binary_op(__init, *__first);
 155       return __init;
 156     }
 157
 158   /**
 159    *  @brief  Compute inner product of two ranges.
 160    *
 161    *  Starting with an initial value of @a init, multiplies successive
 162    *  elements from the two ranges and adds each product into the accumulated
 163    *  value using operator+().  The values in the ranges are processed in
 164    *  order.
 165    *
 166    *  @param  first1  Start of range 1.
 167    *  @param  last1  End of range 1.
 168    *  @param  first2  Start of range 2.
 169    *  @param  init  Starting value to add other values to.
 170    *  @return  The final inner product.
 171    */
 172   template<typename _InputIterator1, typename _InputIterator2, typename _Tp>
 173     inline _Tp
 174     inner_product(_InputIterator1 __first1, _InputIterator1 __last1,
 175                   _InputIterator2 __first2, _Tp __init)
 176     {
 177       // concept requirements
 178       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
 179       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
 180       __glibcxx_requires_valid_range(__first1, __last1);
 181
 182       for (; __first1 != __last1; ++__first1, ++__first2)
 183         __init = __init + (*__first1 * *__first2);
 184       return __init;
 185     }
 186
 187   /**
 188    *  @brief  Compute inner product of two ranges.
 189    *
 190    *  Starting with an initial value of @a init, applies @a binary_op2 to
 191    *  successive elements from the two ranges and accumulates each result into
 192    *  the accumulated value using @a binary_op1.  The values in the ranges are
 193    *  processed in order.
 194    *
 195    *  @param  first1  Start of range 1.
 196    *  @param  last1  End of range 1.
 197    *  @param  first2  Start of range 2.
 198    *  @param  init  Starting value to add other values to.
 199    *  @param  binary_op1  Function object to accumulate with.
 200    *  @param  binary_op2  Function object to apply to pairs of input values.
 201    *  @return  The final inner product.
 202    */
 203   template<typename _InputIterator1, typename _InputIterator2, typename _Tp,
 204            typename _BinaryOperation1, typename _BinaryOperation2>
 205     inline _Tp
 206     inner_product(_InputIterator1 __first1, _InputIterator1 __last1,
 207                   _InputIterator2 __first2, _Tp __init,
 208                   _BinaryOperation1 __binary_op1,
 209                   _BinaryOperation2 __binary_op2)
 210     {
 211       // concept requirements
 212       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
 213       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
 214       __glibcxx_requires_valid_range(__first1, __last1);
 215
 216       for (; __first1 != __last1; ++__first1, ++__first2)
 217         __init = __binary_op1(__init, __binary_op2(*__first1, *__first2));
 218       return __init;
 219     }
 220
 221   /**
 222    *  @brief  Return list of partial sums
 223    *
 224    *  Accumulates the values in the range [first,last) using operator+().
 225    *  As each successive input value is added into the total, that partial sum
 226    *  is written to @a result.  Therefore, the first value in result is the
 227    *  first value of the input, the second value in result is the sum of the
 228    *  first and second input values, and so on.
 229    *
 230    *  @param  first  Start of input range.
 231    *  @param  last  End of input range.
 232    *  @param  result  Output to write sums to.
 233    *  @return  Iterator pointing just beyond the values written to result.
 234    */
 235   template<typename _InputIterator, typename _OutputIterator>
 236     _OutputIterator
 237     partial_sum(_InputIterator __first, _InputIterator __last,
 238                 _OutputIterator __result)
 239     {
 240       typedef typename iterator_traits<_InputIterator>::value_type _ValueType;
 241
 242       // concept requirements
 243       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
 244       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
 245                                                          _ValueType>)
 246       __glibcxx_requires_valid_range(__first, __last);
 247
 248       if (__first == __last)
 249         return __result;
 250       _ValueType __value = *__first;
 251       *__result = __value;
 252       while (++__first != __last)
 253         {
 254           __value = __value + *__first;
 255           *++__result = __value;
 256         }
 257       return ++__result;
 258     }
 259
 260   /**
 261    *  @brief  Return list of partial sums
 262    *
 263    *  Accumulates the values in the range [first,last) using operator+().
 264    *  As each successive input value is added into the total, that partial sum
 265    *  is written to @a result.  Therefore, the first value in result is the
 266    *  first value of the input, the second value in result is the sum of the
 267    *  first and second input values, and so on.
 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            typename _BinaryOperation>
 276     _OutputIterator
 277     partial_sum(_InputIterator __first, _InputIterator __last,
 278                 _OutputIterator __result, _BinaryOperation __binary_op)
 279     {
 280       typedef typename iterator_traits<_InputIterator>::value_type _ValueType;
 281
 282       // concept requirements
 283       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
 284       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
 285                                                          _ValueType>)
 286       __glibcxx_requires_valid_range(__first, __last);
 287
 288       if (__first == __last)
 289         return __result;
 290       _ValueType __value = *__first;
 291       *__result = __value;
 292       while (++__first != __last)
 293         {
 294           __value = __binary_op(__value, *__first);
 295           *++__result = __value;
 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 operator-() and writes the result to @a result.
 305    *
 306    *  @param  first  Start of input range.
 307    *  @param  last  End of input range.
 308    *  @param  result  Output to write sums to.
 309    *  @return  Iterator pointing just beyond the values written to result.
 310    */
 311   template<typename _InputIterator, typename _OutputIterator>
 312     _OutputIterator
 313     adjacent_difference(_InputIterator __first,
 314                         _InputIterator __last, _OutputIterator __result)
 315     {
 316       typedef typename iterator_traits<_InputIterator>::value_type _ValueType;
 317
 318       // concept requirements
 319       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
 320       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
 321                                                          _ValueType>)
 322       __glibcxx_requires_valid_range(__first, __last);
 323
 324       if (__first == __last)
 325         return __result;
 326       _ValueType __value = *__first;
 327       *__result = __value;
 328       while (++__first != __last)
 329         {
 330           _ValueType __tmp = *__first;
 331           *++__result = __tmp - __value;
 332           __value = __tmp;
 333         }
 334       return ++__result;
 335     }
 336
 337   /**
 338    *  @brief  Return differences between adjacent values.
 339    *
 340    *  Computes the difference between adjacent values in the range
 341    *  [first,last) using the function object @a binary_op and writes the
 342    *  result to @a result.
 343    *
 344    *  @param  first  Start of input range.
 345    *  @param  last  End of input range.
 346    *  @param  result  Output to write sums to.
 347    *  @return  Iterator pointing just beyond the values written to result.
 348    */
 349   template<typename _InputIterator, typename _OutputIterator,
 350            typename _BinaryOperation>
 351     _OutputIterator
 352     adjacent_difference(_InputIterator __first, _InputIterator __last,
 353                         _OutputIterator __result, _BinaryOperation __binary_op)
 354     {
 355       typedef typename iterator_traits<_InputIterator>::value_type _ValueType;
 356
 357       // concept requirements
 358       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
 359       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
 360                                                          _ValueType>)
 361       __glibcxx_requires_valid_range(__first, __last);
 362
 363       if (__first == __last)
 364         return __result;
 365       _ValueType __value = *__first;
 366       *__result = __value;
 367       while (++__first != __last)
 368         {
 369           _ValueType __tmp = *__first;
 370           *++__result = __binary_op(__tmp, __value);
 371           __value = __tmp;
 372         }
 373       return ++__result;
 374     }
 375
 376 _GLIBCXX_END_NESTED_NAMESPACE
 377
 378 #endif /* _STL_NUMERIC_H */