contrib/gcc-5.0/libstdc++-v3/include/bits/stl_numeric.h

   1 // Numeric functions implementation -*- C++ -*-
   2
   3 // Copyright (C) 2001-2015 Free Software Foundation, Inc.
   4 //
   5 // This file is part of the GNU ISO C++ Library.  This library is free
   6 // software; you can redistribute it and/or modify it under the
   7 // terms of the GNU General Public License as published by the
   8 // Free Software Foundation; either version 3, or (at your option)
   9 // any later version.
  10
  11 // This library is distributed in the hope that it will be useful,
  12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 // GNU General Public License for more details.
  15
  16 // Under Section 7 of GPL version 3, you are granted additional
  17 // permissions described in the GCC Runtime Library Exception, version
  18 // 3.1, as published by the Free Software Foundation.
  19
  20 // You should have received a copy of the GNU General Public License and
  21 // a copy of the GCC Runtime Library Exception along with this program;
  22 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
  23 // <http://www.gnu.org/licenses/>.
  24
  25 /*
  26  *
  27  * Copyright (c) 1994
  28  * Hewlett-Packard Company
  29  *
  30  * Permission to use, copy, modify, distribute and sell this software
  31  * and its documentation for any purpose is hereby granted without fee,
  32  * provided that the above copyright notice appear in all copies and
  33  * that both that copyright notice and this permission notice appear
  34  * in supporting documentation.  Hewlett-Packard Company makes no
  35  * representations about the suitability of this software for any
  36  * purpose.  It is provided "as is" without express or implied warranty.
  37  *
  38  *
  39  * Copyright (c) 1996,1997
  40  * Silicon Graphics Computer Systems, Inc.
  41  *
  42  * Permission to use, copy, modify, distribute and sell this software
  43  * and its documentation for any purpose is hereby granted without fee,
  44  * provided that the above copyright notice appear in all copies and
  45  * that both that copyright notice and this permission notice appear
  46  * in supporting documentation.  Silicon Graphics makes no
  47  * representations about the suitability of this software for any
  48  * purpose.  It is provided "as is" without express or implied warranty.
  49  */
  50
  51 /** @file bits/stl_numeric.h
  52  *  This is an internal header file, included by other library headers.
  53  *  Do not attempt to use it directly. @headername{numeric}
  54  */
  55
  56 #ifndef _STL_NUMERIC_H
  57 #define _STL_NUMERIC_H 1
  58
  59 #include <bits/concept_check.h>
  60 #include <debug/debug.h>
  61 #include <bits/move.h> // For _GLIBCXX_MOVE
  62
  63 #if __cplusplus >= 201103L
  64
  65 namespace std _GLIBCXX_VISIBILITY(default)
  66 {
  67 _GLIBCXX_BEGIN_NAMESPACE_VERSION
  68
  69   /**
  70    *  @brief  Create a range of sequentially increasing values.
  71    *
  72    *  For each element in the range @p [first,last) assigns @p value and
  73    *  increments @p value as if by @p ++value.
  74    *
  75    *  @param  __first  Start of range.
  76    *  @param  __last  End of range.
  77    *  @param  __value  Starting value.
  78    *  @return  Nothing.
  79    */
  80   template<typename _ForwardIterator, typename _Tp>
  81     void
  82     iota(_ForwardIterator __first, _ForwardIterator __last, _Tp __value)
  83     {
  84       // concept requirements
  85       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
  86                                   _ForwardIterator>)
  87       __glibcxx_function_requires(_ConvertibleConcept<_Tp,
  88             typename iterator_traits<_ForwardIterator>::value_type>)
  89       __glibcxx_requires_valid_range(__first, __last);
  90
  91       for (; __first != __last; ++__first)
  92         {
  93           *__first = __value;
  94           ++__value;
  95         }
  96     }
  97
  98 _GLIBCXX_END_NAMESPACE_VERSION
  99 } // namespace std
 100
 101 #endif
 102
 103 namespace std _GLIBCXX_VISIBILITY(default)
 104 {
 105 _GLIBCXX_BEGIN_NAMESPACE_ALGO
 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 @p __binary_op.  The initial value is @p __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 @p __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 @p __init, applies @p __binary_op2 to
 191    *  successive elements from the two ranges and accumulates each result into
 192    *  the accumulated value using @p __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 the @c + operator.
 225    *  As each successive input value is added into the total, that partial sum
 226    *  is written to @p __result.  Therefore, the first value in @p __result is
 227    *  the first value of the input, the second value in @p __result is the sum
 228    *  of the 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 sum.
 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 @p __binary_op.
 264    *  As each successive input value is added into the total, that partial sum
 265    *  is written to @p __result.  Therefore, the first value in @p __result is
 266    *  the first value of the input, the second value in @p __result is the sum
 267    *  of the 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 sum.
 272    *  @param  __binary_op  Function object.
 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 */