[thirdparty/gcc.git] / libstdc++-v3 / include / bits / stl_numeric.h

// Numeric functions implementation -*- C++ -*-

// Copyright (C) 2001-2016 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library.  This library is free
// software; you can redistribute it and/or modify it under the
// terms of the GNU General Public License as published by the
// Free Software Foundation; either version 3, or (at your option)
// any later version.

// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.

// Under Section 7 of GPL version 3, you are granted additional
// permissions described in the GCC Runtime Library Exception, version
// 3.1, as published by the Free Software Foundation.

// You should have received a copy of the GNU General Public License and
// a copy of the GCC Runtime Library Exception along with this program;
// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
// <http://www.gnu.org/licenses/>.

/*
 *
 * Copyright (c) 1994
 * Hewlett-Packard Company
 *
 * Permission to use, copy, modify, distribute and sell this software
 * and its documentation for any purpose is hereby granted without fee,
 * provided that the above copyright notice appear in all copies and
 * that both that copyright notice and this permission notice appear
 * in supporting documentation.  Hewlett-Packard Company makes no
 * representations about the suitability of this software for any
 * purpose.  It is provided "as is" without express or implied warranty.
 *
 *
 * Copyright (c) 1996,1997
 * Silicon Graphics Computer Systems, Inc.
 *
 * Permission to use, copy, modify, distribute and sell this software
 * and its documentation for any purpose is hereby granted without fee,
 * provided that the above copyright notice appear in all copies and
 * that both that copyright notice and this permission notice appear
 * in supporting documentation.  Silicon Graphics makes no
 * representations about the suitability of this software for any
 * purpose.  It is provided "as is" without express or implied warranty.
 */

/** @file bits/stl_numeric.h
 *  This is an internal header file, included by other library headers.
 *  Do not attempt to use it directly. @headername{numeric}
 */

#ifndef _STL_NUMERIC_H
#define _STL_NUMERIC_H 1

#include <bits/concept_check.h>
#include <debug/debug.h>
#include <bits/move.h> // For _GLIBCXX_MOVE

#if __cplusplus >= 201103L

namespace std _GLIBCXX_VISIBILITY(default)
{
_GLIBCXX_BEGIN_NAMESPACE_VERSION

  /**
   *  @brief  Create a range of sequentially increasing values.
   *
   *  For each element in the range @p [first,last) assigns @p value and
   *  increments @p value as if by @p ++value.
   *
   *  @param  __first  Start of range.
   *  @param  __last  End of range.
   *  @param  __value  Starting value.
   *  @return  Nothing.
   */
  template<typename _ForwardIterator, typename _Tp>
    void
    iota(_ForwardIterator __first, _ForwardIterator __last, _Tp __value)
    {
      // concept requirements
      __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
				  _ForwardIterator>)
      __glibcxx_function_requires(_ConvertibleConcept<_Tp,
	    typename iterator_traits<_ForwardIterator>::value_type>)
      __glibcxx_requires_valid_range(__first, __last);

      for (; __first != __last; ++__first)
	{
	  *__first = __value;
	  ++__value;
	}
    }

_GLIBCXX_END_NAMESPACE_VERSION
} // namespace std

#endif

namespace std _GLIBCXX_VISIBILITY(default)
{
_GLIBCXX_BEGIN_NAMESPACE_ALGO

  /**
   *  @brief  Accumulate values in a range.
   *
   *  Accumulates the values in the range [first,last) using operator+().  The
   *  initial value is @a init.  The values are processed in order.
   *
   *  @param  __first  Start of range.
   *  @param  __last  End of range.
   *  @param  __init  Starting value to add other values to.
   *  @return  The final sum.
   */
  template<typename _InputIterator, typename _Tp>
    inline _Tp
    accumulate(_InputIterator __first, _InputIterator __last, _Tp __init)
    {
      // concept requirements
      __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
      __glibcxx_requires_valid_range(__first, __last);

      for (; __first != __last; ++__first)
	__init = __init + *__first;
      return __init;
    }

  /**
   *  @brief  Accumulate values in a range with operation.
   *
   *  Accumulates the values in the range [first,last) using the function
   *  object @p __binary_op.  The initial value is @p __init.  The values are
   *  processed in order.
   *
   *  @param  __first  Start of range.
   *  @param  __last  End of range.
   *  @param  __init  Starting value to add other values to.
   *  @param  __binary_op  Function object to accumulate with.
   *  @return  The final sum.
   */
  template<typename _InputIterator, typename _Tp, typename _BinaryOperation>
    inline _Tp
    accumulate(_InputIterator __first, _InputIterator __last, _Tp __init,
	       _BinaryOperation __binary_op)
    {
      // concept requirements
      __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
      __glibcxx_requires_valid_range(__first, __last);

      for (; __first != __last; ++__first)
	__init = __binary_op(__init, *__first);
      return __init;
    }

  /**
   *  @brief  Compute inner product of two ranges.
   *
   *  Starting with an initial value of @p __init, multiplies successive
   *  elements from the two ranges and adds each product into the accumulated
   *  value using operator+().  The values in the ranges are processed in
   *  order.
   *
   *  @param  __first1  Start of range 1.
   *  @param  __last1  End of range 1.
   *  @param  __first2  Start of range 2.
   *  @param  __init  Starting value to add other values to.
   *  @return  The final inner product.
   */
  template<typename _InputIterator1, typename _InputIterator2, typename _Tp>
    inline _Tp
    inner_product(_InputIterator1 __first1, _InputIterator1 __last1,
		  _InputIterator2 __first2, _Tp __init)
    {
      // concept requirements
      __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
      __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
      __glibcxx_requires_valid_range(__first1, __last1);

      for (; __first1 != __last1; ++__first1, (void)++__first2)
	__init = __init + (*__first1 * *__first2);
      return __init;
    }

  /**
   *  @brief  Compute inner product of two ranges.
   *
   *  Starting with an initial value of @p __init, applies @p __binary_op2 to
   *  successive elements from the two ranges and accumulates each result into
   *  the accumulated value using @p __binary_op1.  The values in the ranges are
   *  processed in order.
   *
   *  @param  __first1  Start of range 1.
   *  @param  __last1  End of range 1.
   *  @param  __first2  Start of range 2.
   *  @param  __init  Starting value to add other values to.
   *  @param  __binary_op1  Function object to accumulate with.
   *  @param  __binary_op2  Function object to apply to pairs of input values.
   *  @return  The final inner product.
   */
  template<typename _InputIterator1, typename _InputIterator2, typename _Tp,
	   typename _BinaryOperation1, typename _BinaryOperation2>
    inline _Tp
    inner_product(_InputIterator1 __first1, _InputIterator1 __last1,
		  _InputIterator2 __first2, _Tp __init,
		  _BinaryOperation1 __binary_op1,
		  _BinaryOperation2 __binary_op2)
    {
      // concept requirements
      __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
      __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
      __glibcxx_requires_valid_range(__first1, __last1);

      for (; __first1 != __last1; ++__first1, (void)++__first2)
	__init = __binary_op1(__init, __binary_op2(*__first1, *__first2));
      return __init;
    }

  /**
   *  @brief  Return list of partial sums
   *
   *  Accumulates the values in the range [first,last) using the @c + operator.
   *  As each successive input value is added into the total, that partial sum
   *  is written to @p __result.  Therefore, the first value in @p __result is
   *  the first value of the input, the second value in @p __result is the sum
   *  of the first and second input values, and so on.
   *
   *  @param  __first  Start of input range.
   *  @param  __last  End of input range.
   *  @param  __result  Output sum.
   *  @return  Iterator pointing just beyond the values written to __result.
   */
  template<typename _InputIterator, typename _OutputIterator>
    _OutputIterator
    partial_sum(_InputIterator __first, _InputIterator __last,
		_OutputIterator __result)
    {
      typedef typename iterator_traits<_InputIterator>::value_type _ValueType;

      // concept requirements
      __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
      __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
				                         _ValueType>)
      __glibcxx_requires_valid_range(__first, __last);

      if (__first == __last)
	return __result;
      _ValueType __value = *__first;
      *__result = __value;
      while (++__first != __last)
	{
	  __value = __value + *__first;
	  *++__result = __value;
	}
      return ++__result;
    }

  /**
   *  @brief  Return list of partial sums
   *
   *  Accumulates the values in the range [first,last) using @p __binary_op.
   *  As each successive input value is added into the total, that partial sum
   *  is written to @p __result.  Therefore, the first value in @p __result is
   *  the first value of the input, the second value in @p __result is the sum
   *  of the first and second input values, and so on.
   *
   *  @param  __first  Start of input range.
   *  @param  __last  End of input range.
   *  @param  __result  Output sum.
   *  @param  __binary_op  Function object.
   *  @return  Iterator pointing just beyond the values written to __result.
   */
  template<typename _InputIterator, typename _OutputIterator,
	   typename _BinaryOperation>
    _OutputIterator
    partial_sum(_InputIterator __first, _InputIterator __last,
		_OutputIterator __result, _BinaryOperation __binary_op)
    {
      typedef typename iterator_traits<_InputIterator>::value_type _ValueType;

      // concept requirements
      __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
      __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
				                         _ValueType>)
      __glibcxx_requires_valid_range(__first, __last);

      if (__first == __last)
	return __result;
      _ValueType __value = *__first;
      *__result = __value;
      while (++__first != __last)
	{
	  __value = __binary_op(__value, *__first);
	  *++__result = __value;
	}
      return ++__result;
    }

  /**
   *  @brief  Return differences between adjacent values.
   *
   *  Computes the difference between adjacent values in the range
   *  [first,last) using operator-() and writes the result to @p __result.
   *
   *  @param  __first  Start of input range.
   *  @param  __last  End of input range.
   *  @param  __result  Output sums.
   *  @return  Iterator pointing just beyond the values written to result.
   *
   *  _GLIBCXX_RESOLVE_LIB_DEFECTS
   *  DR 539. partial_sum and adjacent_difference should mention requirements
   */
  template<typename _InputIterator, typename _OutputIterator>
    _OutputIterator
    adjacent_difference(_InputIterator __first,
			_InputIterator __last, _OutputIterator __result)
    {
      typedef typename iterator_traits<_InputIterator>::value_type _ValueType;

      // concept requirements
      __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
      __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
				                         _ValueType>)
      __glibcxx_requires_valid_range(__first, __last);

      if (__first == __last)
	return __result;
      _ValueType __value = *__first;
      *__result = __value;
      while (++__first != __last)
	{
	  _ValueType __tmp = *__first;
	  *++__result = __tmp - __value;
	  __value = _GLIBCXX_MOVE(__tmp);
	}
      return ++__result;
    }

  /**
   *  @brief  Return differences between adjacent values.
   *
   *  Computes the difference between adjacent values in the range
   *  [__first,__last) using the function object @p __binary_op and writes the
   *  result to @p __result.
   *
   *  @param  __first  Start of input range.
   *  @param  __last  End of input range.
   *  @param  __result  Output sum.
   *  @param  __binary_op Function object.
   *  @return  Iterator pointing just beyond the values written to result.
   *
   *  _GLIBCXX_RESOLVE_LIB_DEFECTS
   *  DR 539. partial_sum and adjacent_difference should mention requirements
   */
  template<typename _InputIterator, typename _OutputIterator,
	   typename _BinaryOperation>
    _OutputIterator
    adjacent_difference(_InputIterator __first, _InputIterator __last,
			_OutputIterator __result, _BinaryOperation __binary_op)
    {
      typedef typename iterator_traits<_InputIterator>::value_type _ValueType;

      // concept requirements
      __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
      __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
				                         _ValueType>)
      __glibcxx_requires_valid_range(__first, __last);

      if (__first == __last)
	return __result;
      _ValueType __value = *__first;
      *__result = __value;
      while (++__first != __last)
	{
	  _ValueType __tmp = *__first;
	  *++__result = __binary_op(__tmp, __value);
	  __value = _GLIBCXX_MOVE(__tmp);
	}
      return ++__result;
    }

_GLIBCXX_END_NAMESPACE_ALGO
} // namespace std

#endif /* _STL_NUMERIC_H */
Commit	Line	Data
1d61409b	1	// Numeric functions implementation -- C++ --
1d61409b	2
f1717362	3	// Copyright (C) 2001-2016 Free Software Foundation, Inc.
1d61409b	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
6bc9506f	8	// Free Software Foundation; either version 3, or (at your option)
1d61409b	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
6bc9506f	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.
1d61409b	19
6bc9506f	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/>.
1d61409b	24
1d487aca	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
5846aeac	51	/** @file bits/stl_numeric.h
7a472ef1	52	* This is an internal header file, included by other library headers.
5846aeac	53	* Do not attempt to use it directly. @headername{numeric}
1d487aca	54	*/
1d487aca	55
5a64d8cf	56	#ifndef _STL_NUMERIC_H
5a64d8cf	57	#define _STL_NUMERIC_H 1
1d487aca	58
40180232	59	#include <bits/concept_check.h>
d570f2e9	60	#include <debug/debug.h>
a34688d4	61	#include <bits/move.h> // For _GLIBCXX_MOVE
d570f2e9	62
0c8766b1	63	#if __cplusplus >= 201103L
6e48a8d0	64
2948dd21	65	namespace std _GLIBCXX_VISIBILITY(default)
	66	{
	67	_GLIBCXX_BEGIN_NAMESPACE_VERSION
6e48a8d0	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	*
e12e4f3b	75	* @param __first Start of range.
	76	* @param __last End of range.
	77	* @param __value Starting value.
6e48a8d0	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
2948dd21	98	_GLIBCXX_END_NAMESPACE_VERSION
2948dd21	99	} // namespace std
6e48a8d0	100
	101	#endif
	102
2948dd21	103	namespace std _GLIBCXX_VISIBILITY(default)
	104	{
	105	_GLIBCXX_BEGIN_NAMESPACE_ALGO
1d487aca	106
21d4b1cc	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	*
e12e4f3b	113	* @param __first Start of range.
	114	* @param __last End of range.
	115	* @param __init Starting value to add other values to.
21d4b1cc	116	* @return The final sum.
21d4b1cc	117	*/
66b2d994	118	template<typename _InputIterator, typename _Tp>
a854189d	119	inline _Tp
66b2d994	120	accumulate(_InputIterator __first, _InputIterator __last, _Tp __init)
	121	{
	122	// concept requirements
5a64d8cf	123	__glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
d570f2e9	124	__glibcxx_requires_valid_range(__first, __last);
66b2d994	125
7fddaaca	126	for (; __first != __last; ++__first)
66b2d994	127	__init = __init + *__first;
	128	return __init;
	129	}
40b55285	130
21d4b1cc	131	/**
	132	* @brief Accumulate values in a range with operation.
	133	*
	134	* Accumulates the values in the range [first,last) using the function
db3b35cb	135	* object @p __binary_op. The initial value is @p __init. The values are
21d4b1cc	136	* processed in order.
21d4b1cc	137	*
e12e4f3b	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.
21d4b1cc	142	* @return The final sum.
21d4b1cc	143	*/
66b2d994	144	template<typename _InputIterator, typename _Tp, typename _BinaryOperation>
a854189d	145	inline _Tp
66b2d994	146	accumulate(_InputIterator __first, _InputIterator __last, _Tp __init,
	147	_BinaryOperation __binary_op)
	148	{
	149	// concept requirements
5a64d8cf	150	__glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
d570f2e9	151	__glibcxx_requires_valid_range(__first, __last);
66b2d994	152
7fddaaca	153	for (; __first != __last; ++__first)
66b2d994	154	__init = __binary_op(__init, *__first);
	155	return __init;
	156	}
1d487aca	157
21d4b1cc	158	/**
	159	* @brief Compute inner product of two ranges.
	160	*
db3b35cb	161	* Starting with an initial value of @p __init, multiplies successive
21d4b1cc	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	*
e12e4f3b	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.
21d4b1cc	170	* @return The final inner product.
21d4b1cc	171	*/
66b2d994	172	template<typename _InputIterator1, typename _InputIterator2, typename _Tp>
a854189d	173	inline _Tp
66b2d994	174	inner_product(_InputIterator1 __first1, _InputIterator1 __last1,
	175	_InputIterator2 __first2, _Tp __init)
	176	{
	177	// concept requirements
5a64d8cf	178	__glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5a64d8cf	179	__glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
d570f2e9	180	__glibcxx_requires_valid_range(__first1, __last1);
66b2d994	181
0ba86e4e	182	for (; __first1 != __last1; ++__first1, (void)++__first2)
66b2d994	183	__init = __init + (__first1 *__first2);
66b2d994	184	return __init;
1d487aca	185	}
1d487aca	186
21d4b1cc	187	/**
	188	* @brief Compute inner product of two ranges.
	189	*
db3b35cb	190	* Starting with an initial value of @p __init, applies @p __binary_op2 to
21d4b1cc	191	* successive elements from the two ranges and accumulates each result into
db3b35cb	192	* the accumulated value using @p __binary_op1. The values in the ranges are
21d4b1cc	193	* processed in order.
21d4b1cc	194	*
e12e4f3b	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.
21d4b1cc	201	* @return The final inner product.
21d4b1cc	202	*/
66b2d994	203	template<typename _InputIterator1, typename _InputIterator2, typename _Tp,
6e48a8d0	204	typename _BinaryOperation1, typename _BinaryOperation2>
a854189d	205	inline _Tp
66b2d994	206	inner_product(_InputIterator1 __first1, _InputIterator1 __last1,
bae9b8af	207	_InputIterator2 __first2, _Tp __init,
66b2d994	208	_BinaryOperation1 __binary_op1,
	209	_BinaryOperation2 __binary_op2)
	210	{
	211	// concept requirements
5a64d8cf	212	__glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5a64d8cf	213	__glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
d570f2e9	214	__glibcxx_requires_valid_range(__first1, __last1);
66b2d994	215
0ba86e4e	216	for (; __first1 != __last1; ++__first1, (void)++__first2)
66b2d994	217	__init = __binary_op1(__init, __binary_op2(__first1, __first2));
66b2d994	218	return __init;
1d487aca	219	}
1d487aca	220
21d4b1cc	221	/**
	222	* @brief Return list of partial sums
	223	*
e437596b	224	* Accumulates the values in the range [first,last) using the @c + operator.
21d4b1cc	225	* As each successive input value is added into the total, that partial sum
e437596b	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.
21d4b1cc	229	*
e12e4f3b	230	* @param __first Start of input range.
e12e4f3b	231	* @param __last End of input range.
db3b35cb	232	* @param __result Output sum.
db3b35cb	233	* @return Iterator pointing just beyond the values written to __result.
21d4b1cc	234	*/
66b2d994	235	template<typename _InputIterator, typename _OutputIterator>
bae9b8af	236	_OutputIterator
66b2d994	237	partial_sum(_InputIterator __first, _InputIterator __last,
	238	_OutputIterator __result)
	239	{
	240	typedef typename iterator_traits<_InputIterator>::value_type _ValueType;
	241
	242	// concept requirements
5a64d8cf	243	__glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
7fddaaca	244	__glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
7fddaaca	245	_ValueType>)
d570f2e9	246	__glibcxx_requires_valid_range(__first, __last);
66b2d994	247
7fddaaca	248	if (__first == __last)
7fddaaca	249	return __result;
66b2d994	250	_ValueType __value = *__first;
9c5ccb1d	251	*__result = __value;
7fddaaca	252	while (++__first != __last)
	253	{
	254	__value = __value + *__first;
	255	*++__result = __value;
	256	}
66b2d994	257	return ++__result;
66b2d994	258	}
1d487aca	259
21d4b1cc	260	/**
	261	* @brief Return list of partial sums
	262	*
e437596b	263	* Accumulates the values in the range [first,last) using @p __binary_op.
21d4b1cc	264	* As each successive input value is added into the total, that partial sum
e437596b	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.
21d4b1cc	268	*
e12e4f3b	269	* @param __first Start of input range.
e12e4f3b	270	* @param __last End of input range.
db3b35cb	271	* @param __result Output sum.
e437596b	272	* @param __binary_op Function object.
db3b35cb	273	* @return Iterator pointing just beyond the values written to __result.
21d4b1cc	274	*/
7fddaaca	275	template<typename _InputIterator, typename _OutputIterator,
7fddaaca	276	typename _BinaryOperation>
bae9b8af	277	_OutputIterator
66b2d994	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
5a64d8cf	284	__glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
7fddaaca	285	__glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
7fddaaca	286	_ValueType>)
d570f2e9	287	__glibcxx_requires_valid_range(__first, __last);
66b2d994	288
7fddaaca	289	if (__first == __last)
7fddaaca	290	return __result;
66b2d994	291	_ValueType __value = *__first;
9c5ccb1d	292	*__result = __value;
7fddaaca	293	while (++__first != __last)
	294	{
	295	__value = __binary_op(__value, *__first);
	296	*++__result = __value;
	297	}
66b2d994	298	return ++__result;
66b2d994	299	}
1d487aca	300
21d4b1cc	301	/**
	302	* @brief Return differences between adjacent values.
	303	*
	304	* Computes the difference between adjacent values in the range
db3b35cb	305	* [first,last) using operator-() and writes the result to @p __result.
21d4b1cc	306	*
e12e4f3b	307	* @param __first Start of input range.
e12e4f3b	308	* @param __last End of input range.
db3b35cb	309	* @param __result Output sums.
21d4b1cc	310	* @return Iterator pointing just beyond the values written to result.
a34688d4	311	*
	312	* _GLIBCXX_RESOLVE_LIB_DEFECTS
	313	* DR 539. partial_sum and adjacent_difference should mention requirements
21d4b1cc	314	*/
66b2d994	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
5a64d8cf	323	__glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
7fddaaca	324	__glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
7fddaaca	325	_ValueType>)
d570f2e9	326	__glibcxx_requires_valid_range(__first, __last);
66b2d994	327
7fddaaca	328	if (__first == __last)
7fddaaca	329	return __result;
66b2d994	330	_ValueType __value = *__first;
9c5ccb1d	331	*__result = __value;
7fddaaca	332	while (++__first != __last)
	333	{
	334	_ValueType __tmp = *__first;
	335	*++__result = __tmp - __value;
a34688d4	336	__value = _GLIBCXX_MOVE(__tmp);
7fddaaca	337	}
66b2d994	338	return ++__result;
66b2d994	339	}
1d487aca	340
21d4b1cc	341	/**
	342	* @brief Return differences between adjacent values.
	343	*
	344	* Computes the difference between adjacent values in the range
db3b35cb	345	* [__first,__last) using the function object @p __binary_op and writes the
db3b35cb	346	* result to @p __result.
21d4b1cc	347	*
e12e4f3b	348	* @param __first Start of input range.
e12e4f3b	349	* @param __last End of input range.
db3b35cb	350	* @param __result Output sum.
db3b35cb	351	* @param __binary_op Function object.
21d4b1cc	352	* @return Iterator pointing just beyond the values written to result.
a34688d4	353	*
	354	* _GLIBCXX_RESOLVE_LIB_DEFECTS
	355	* DR 539. partial_sum and adjacent_difference should mention requirements
21d4b1cc	356	*/
7fddaaca	357	template<typename _InputIterator, typename _OutputIterator,
7fddaaca	358	typename _BinaryOperation>
bae9b8af	359	_OutputIterator
66b2d994	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
5a64d8cf	366	__glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
7fddaaca	367	__glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
7fddaaca	368	_ValueType>)
d570f2e9	369	__glibcxx_requires_valid_range(__first, __last);
66b2d994	370
7fddaaca	371	if (__first == __last)
7fddaaca	372	return __result;
66b2d994	373	_ValueType __value = *__first;
9c5ccb1d	374	*__result = __value;
7fddaaca	375	while (++__first != __last)
	376	{
	377	_ValueType __tmp = *__first;
	378	*++__result = __binary_op(__tmp, __value);
a34688d4	379	__value = _GLIBCXX_MOVE(__tmp);
7fddaaca	380	}
66b2d994	381	return ++__result;
66b2d994	382	}
1d487aca	383
2948dd21	384	_GLIBCXX_END_NAMESPACE_ALGO
2948dd21	385	} // namespace std
1d487aca	386
5a64d8cf	387	#endif /* _STL_NUMERIC_H */