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

   1 // Numeric functions implementation -*- C++ -*-
   2
   3 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010,
   4 // 2011 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 3, 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 // Under Section 7 of GPL version 3, you are granted additional
  18 // permissions described in the GCC Runtime Library Exception, version
  19 // 3.1, as published by the Free Software Foundation.
  20
  21 // You should have received a copy of the GNU General Public License and
  22 // a copy of the GCC Runtime Library Exception along with this program;
  23 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
  24 // <http://www.gnu.org/licenses/>.
  25
  26 /*
  27  *
  28  * Copyright (c) 1994
  29  * Hewlett-Packard Company
  30  *
  31  * Permission to use, copy, modify, distribute and sell this software
  32  * and its documentation for any purpose is hereby granted without fee,
  33  * provided that the above copyright notice appear in all copies and
  34  * that both that copyright notice and this permission notice appear
  35  * in supporting documentation.  Hewlett-Packard Company makes no
  36  * representations about the suitability of this software for any
  37  * purpose.  It is provided "as is" without express or implied warranty.
  38  *
  39  *
  40  * Copyright (c) 1996,1997
  41  * Silicon Graphics Computer Systems, Inc.
  42  *
  43  * Permission to use, copy, modify, distribute and sell this software
  44  * and its documentation for any purpose is hereby granted without fee,
  45  * provided that the above copyright notice appear in all copies and
  46  * that both that copyright notice and this permission notice appear
  47  * in supporting documentation.  Silicon Graphics makes no
  48  * representations about the suitability of this software for any
  49  * purpose.  It is provided "as is" without express or implied warranty.
  50  */
  51
  52 /** @file bits/stl_numeric.h
  53  *  This is an internal header file, included by other library headers.
  54  *  Do not attempt to use it directly. @headername{numeric}
  55  */
  56
  57 #ifndef _STL_NUMERIC_H
  58 #define _STL_NUMERIC_H 1
  59
  60 #include <bits/concept_check.h>
  61 #include <debug/debug.h>
  62 #include <bits/move.h> // For _GLIBCXX_MOVE
  63
  64 #ifdef __GXX_EXPERIMENTAL_CXX0X__
  65
  66 namespace std _GLIBCXX_VISIBILITY(default)
  67 {
  68 _GLIBCXX_BEGIN_NAMESPACE_VERSION
  69
  70   /**
  71    *  @brief  Create a range of sequentially increasing values.
  72    *
  73    *  For each element in the range @p [first,last) assigns @p value and
  74    *  increments @p value as if by @p ++value.
  75    *
  76    *  @param  __first  Start of range.
  77    *  @param  __last  End of range.
  78    *  @param  __value  Starting value.
  79    *  @return  Nothing.
  80    */
  81   template<typename _ForwardIterator, typename _Tp>
  82     void
  83     iota(_ForwardIterator __first, _ForwardIterator __last, _Tp __value)
  84     {
  85       // concept requirements
  86       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
  87                                   _ForwardIterator>)
  88       __glibcxx_function_requires(_ConvertibleConcept<_Tp,
  89             typename iterator_traits<_ForwardIterator>::value_type>)
  90       __glibcxx_requires_valid_range(__first, __last);
  91
  92       for (; __first != __last; ++__first)
  93         {
  94           *__first = __value;
  95           ++__value;
  96         }
  97     }
  98
  99 _GLIBCXX_END_NAMESPACE_VERSION
 100 } // namespace std
 101
 102 #endif
 103
 104 namespace std _GLIBCXX_VISIBILITY(default)
 105 {
 106 _GLIBCXX_BEGIN_NAMESPACE_ALGO
 107
 108   /**
 109    *  @brief  Accumulate values in a range.
 110    *
 111    *  Accumulates the values in the range [first,last) using operator+().  The
 112    *  initial value is @a init.  The values are processed in order.
 113    *
 114    *  @param  __first  Start of range.
 115    *  @param  __last  End of range.
 116    *  @param  __init  Starting value to add other values to.
 117    *  @return  The final sum.
 118    */
 119   template<typename _InputIterator, typename _Tp>
 120     inline _Tp
 121     accumulate(_InputIterator __first, _InputIterator __last, _Tp __init)
 122     {
 123       // concept requirements
 124       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
 125       __glibcxx_requires_valid_range(__first, __last);
 126
 127       for (; __first != __last; ++__first)
 128         __init = __init + *__first;
 129       return __init;
 130     }
 131
 132   /**
 133    *  @brief  Accumulate values in a range with operation.
 134    *
 135    *  Accumulates the values in the range [first,last) using the function
 136    *  object @p __binary_op.  The initial value is @p __init.  The values are
 137    *  processed in order.
 138    *
 139    *  @param  __first  Start of range.
 140    *  @param  __last  End of range.
 141    *  @param  __init  Starting value to add other values to.
 142    *  @param  __binary_op  Function object to accumulate with.
 143    *  @return  The final sum.
 144    */
 145   template<typename _InputIterator, typename _Tp, typename _BinaryOperation>
 146     inline _Tp
 147     accumulate(_InputIterator __first, _InputIterator __last, _Tp __init,
 148                _BinaryOperation __binary_op)
 149     {
 150       // concept requirements
 151       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
 152       __glibcxx_requires_valid_range(__first, __last);
 153
 154       for (; __first != __last; ++__first)
 155         __init = __binary_op(__init, *__first);
 156       return __init;
 157     }
 158
 159   /**
 160    *  @brief  Compute inner product of two ranges.
 161    *
 162    *  Starting with an initial value of @p __init, multiplies successive
 163    *  elements from the two ranges and adds each product into the accumulated
 164    *  value using operator+().  The values in the ranges are processed in
 165    *  order.
 166    *
 167    *  @param  __first1  Start of range 1.
 168    *  @param  __last1  End of range 1.
 169    *  @param  __first2  Start of range 2.
 170    *  @param  __init  Starting value to add other values to.
 171    *  @return  The final inner product.
 172    */
 173   template<typename _InputIterator1, typename _InputIterator2, typename _Tp>
 174     inline _Tp
 175     inner_product(_InputIterator1 __first1, _InputIterator1 __last1,
 176                   _InputIterator2 __first2, _Tp __init)
 177     {
 178       // concept requirements
 179       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
 180       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
 181       __glibcxx_requires_valid_range(__first1, __last1);
 182
 183       for (; __first1 != __last1; ++__first1, ++__first2)
 184         __init = __init + (*__first1 * *__first2);
 185       return __init;
 186     }
 187
 188   /**
 189    *  @brief  Compute inner product of two ranges.
 190    *
 191    *  Starting with an initial value of @p __init, applies @p __binary_op2 to
 192    *  successive elements from the two ranges and accumulates each result into
 193    *  the accumulated value using @p __binary_op1.  The values in the ranges are
 194    *  processed in order.
 195    *
 196    *  @param  __first1  Start of range 1.
 197    *  @param  __last1  End of range 1.
 198    *  @param  __first2  Start of range 2.
 199    *  @param  __init  Starting value to add other values to.
 200    *  @param  __binary_op1  Function object to accumulate with.
 201    *  @param  __binary_op2  Function object to apply to pairs of input values.
 202    *  @return  The final inner product.
 203    */
 204   template<typename _InputIterator1, typename _InputIterator2, typename _Tp,
 205            typename _BinaryOperation1, typename _BinaryOperation2>
 206     inline _Tp
 207     inner_product(_InputIterator1 __first1, _InputIterator1 __last1,
 208                   _InputIterator2 __first2, _Tp __init,
 209                   _BinaryOperation1 __binary_op1,
 210                   _BinaryOperation2 __binary_op2)
 211     {
 212       // concept requirements
 213       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
 214       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
 215       __glibcxx_requires_valid_range(__first1, __last1);
 216
 217       for (; __first1 != __last1; ++__first1, ++__first2)
 218         __init = __binary_op1(__init, __binary_op2(*__first1, *__first2));
 219       return __init;
 220     }
 221
 222   /**
 223    *  @brief  Return list of partial sums
 224    *
 225    *  Accumulates the values in the range [first,last) using operator+().
 226    *  As each successive input value is added into the total, that partial sum
 227    *  is written to @p __result.  Therefore, the first value in result is the
 228    *  first value of the input, the second value in result is the sum of the
 229    *  first and second input values, and so on.
 230    *
 231    *  @param  __first  Start of input range.
 232    *  @param  __last  End of input range.
 233    *  @param  __result  Output sum.
 234    *  @return  Iterator pointing just beyond the values written to __result.
 235    */
 236   template<typename _InputIterator, typename _OutputIterator>
 237     _OutputIterator
 238     partial_sum(_InputIterator __first, _InputIterator __last,
 239                 _OutputIterator __result)
 240     {
 241       typedef typename iterator_traits<_InputIterator>::value_type _ValueType;
 242
 243       // concept requirements
 244       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
 245       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
 246                                                          _ValueType>)
 247       __glibcxx_requires_valid_range(__first, __last);
 248
 249       if (__first == __last)
 250         return __result;
 251       _ValueType __value = *__first;
 252       *__result = __value;
 253       while (++__first != __last)
 254         {
 255           __value = __value + *__first;
 256           *++__result = __value;
 257         }
 258       return ++__result;
 259     }
 260
 261   /**
 262    *  @brief  Return list of partial sums
 263    *
 264    *  Accumulates the values in the range [first,last) using operator+().
 265    *  As each successive input value is added into the total, that partial sum
 266    *  is written to @p __result.  Therefore, the first value in result is the
 267    *  first value of the input, the second value in result is the sum of the
 268    *  first and second input values, and so on.
 269    *
 270    *  @param  __first  Start of input range.
 271    *  @param  __last  End of input range.
 272    *  @param  __result  Output sum.
 273    *  @return  Iterator pointing just beyond the values written to __result.
 274    */
 275   template<typename _InputIterator, typename _OutputIterator,
 276            typename _BinaryOperation>
 277     _OutputIterator
 278     partial_sum(_InputIterator __first, _InputIterator __last,
 279                 _OutputIterator __result, _BinaryOperation __binary_op)
 280     {
 281       typedef typename iterator_traits<_InputIterator>::value_type _ValueType;
 282
 283       // concept requirements
 284       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
 285       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
 286                                                          _ValueType>)
 287       __glibcxx_requires_valid_range(__first, __last);
 288
 289       if (__first == __last)
 290         return __result;
 291       _ValueType __value = *__first;
 292       *__result = __value;
 293       while (++__first != __last)
 294         {
 295           __value = __binary_op(__value, *__first);
 296           *++__result = __value;
 297         }
 298       return ++__result;
 299     }
 300
 301   /**
 302    *  @brief  Return differences between adjacent values.
 303    *
 304    *  Computes the difference between adjacent values in the range
 305    *  [first,last) using operator-() and writes the result to @p __result.
 306    *
 307    *  @param  __first  Start of input range.
 308    *  @param  __last  End of input range.
 309    *  @param  __result  Output sums.
 310    *  @return  Iterator pointing just beyond the values written to result.
 311    *
 312    *  _GLIBCXX_RESOLVE_LIB_DEFECTS
 313    *  DR 539. partial_sum and adjacent_difference should mention requirements
 314    */
 315   template<typename _InputIterator, typename _OutputIterator>
 316     _OutputIterator
 317     adjacent_difference(_InputIterator __first,
 318                         _InputIterator __last, _OutputIterator __result)
 319     {
 320       typedef typename iterator_traits<_InputIterator>::value_type _ValueType;
 321
 322       // concept requirements
 323       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
 324       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
 325                                                          _ValueType>)
 326       __glibcxx_requires_valid_range(__first, __last);
 327
 328       if (__first == __last)
 329         return __result;
 330       _ValueType __value = *__first;
 331       *__result = __value;
 332       while (++__first != __last)
 333         {
 334           _ValueType __tmp = *__first;
 335           *++__result = __tmp - __value;
 336           __value = _GLIBCXX_MOVE(__tmp);
 337         }
 338       return ++__result;
 339     }
 340
 341   /**
 342    *  @brief  Return differences between adjacent values.
 343    *
 344    *  Computes the difference between adjacent values in the range
 345    *  [__first,__last) using the function object @p __binary_op and writes the
 346    *  result to @p __result.
 347    *
 348    *  @param  __first  Start of input range.
 349    *  @param  __last  End of input range.
 350    *  @param  __result  Output sum.
 351    *  @param  __binary_op Function object.
 352    *  @return  Iterator pointing just beyond the values written to result.
 353    *
 354    *  _GLIBCXX_RESOLVE_LIB_DEFECTS
 355    *  DR 539. partial_sum and adjacent_difference should mention requirements
 356    */
 357   template<typename _InputIterator, typename _OutputIterator,
 358            typename _BinaryOperation>
 359     _OutputIterator
 360     adjacent_difference(_InputIterator __first, _InputIterator __last,
 361                         _OutputIterator __result, _BinaryOperation __binary_op)
 362     {
 363       typedef typename iterator_traits<_InputIterator>::value_type _ValueType;
 364
 365       // concept requirements
 366       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
 367       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
 368                                                          _ValueType>)
 369       __glibcxx_requires_valid_range(__first, __last);
 370
 371       if (__first == __last)
 372         return __result;
 373       _ValueType __value = *__first;
 374       *__result = __value;
 375       while (++__first != __last)
 376         {
 377           _ValueType __tmp = *__first;
 378           *++__result = __binary_op(__tmp, __value);
 379           __value = _GLIBCXX_MOVE(__tmp);
 380         }
 381       return ++__result;
 382     }
 383
 384 _GLIBCXX_END_NAMESPACE_ALGO
 385 } // namespace std
 386
 387 #endif /* _STL_NUMERIC_H */