1 // Numeric functions implementation -*- C++ -*-
3 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009
4 // Free Software Foundation, Inc.
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)
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.
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.
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/>.
29 * Hewlett-Packard Company
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.
40 * Copyright (c) 1996,1997
41 * Silicon Graphics Computer Systems, Inc.
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.
52 /** @file stl_numeric.h
53 * This is an internal header file, included by other library headers.
54 * You should not attempt to use it directly.
57 #ifndef _STL_NUMERIC_H
58 #define _STL_NUMERIC_H 1
60 #include <bits/concept_check.h>
61 #include <debug/debug.h>
63 #ifdef __GXX_EXPERIMENTAL_CXX0X__
65 _GLIBCXX_BEGIN_NAMESPACE(std
)
68 * @brief Create a range of sequentially increasing values.
70 * For each element in the range @p [first,last) assigns @p value and
71 * increments @p value as if by @p ++value.
73 * @param first Start of range.
74 * @param last End of range.
75 * @param value Starting value.
78 template<typename _ForwardIterator
, typename _Tp
>
80 iota(_ForwardIterator __first
, _ForwardIterator __last
, _Tp __value
)
82 // concept requirements
83 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept
<
85 __glibcxx_function_requires(_ConvertibleConcept
<_Tp
,
86 typename iterator_traits
<_ForwardIterator
>::value_type
>)
87 __glibcxx_requires_valid_range(__first
, __last
);
89 for (; __first
!= __last
; ++__first
)
96 _GLIBCXX_END_NAMESPACE
100 _GLIBCXX_BEGIN_NESTED_NAMESPACE(std
, _GLIBCXX_STD_P
)
103 * @brief Accumulate values in a range.
105 * Accumulates the values in the range [first,last) using operator+(). The
106 * initial value is @a init. The values are processed in order.
108 * @param first Start of range.
109 * @param last End of range.
110 * @param init Starting value to add other values to.
111 * @return The final sum.
113 template<typename _InputIterator
, typename _Tp
>
115 accumulate(_InputIterator __first
, _InputIterator __last
, _Tp __init
)
117 // concept requirements
118 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator
>)
119 __glibcxx_requires_valid_range(__first
, __last
);
121 for (; __first
!= __last
; ++__first
)
122 __init
= __init
+ *__first
;
127 * @brief Accumulate values in a range with operation.
129 * Accumulates the values in the range [first,last) using the function
130 * object @a binary_op. The initial value is @a init. The values are
131 * processed in order.
133 * @param first Start of range.
134 * @param last End of range.
135 * @param init Starting value to add other values to.
136 * @param binary_op Function object to accumulate with.
137 * @return The final sum.
139 template<typename _InputIterator
, typename _Tp
, typename _BinaryOperation
>
141 accumulate(_InputIterator __first
, _InputIterator __last
, _Tp __init
,
142 _BinaryOperation __binary_op
)
144 // concept requirements
145 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator
>)
146 __glibcxx_requires_valid_range(__first
, __last
);
148 for (; __first
!= __last
; ++__first
)
149 __init
= __binary_op(__init
, *__first
);
154 * @brief Compute inner product of two ranges.
156 * Starting with an initial value of @a init, multiplies successive
157 * elements from the two ranges and adds each product into the accumulated
158 * value using operator+(). The values in the ranges are processed in
161 * @param first1 Start of range 1.
162 * @param last1 End of range 1.
163 * @param first2 Start of range 2.
164 * @param init Starting value to add other values to.
165 * @return The final inner product.
167 template<typename _InputIterator1
, typename _InputIterator2
, typename _Tp
>
169 inner_product(_InputIterator1 __first1
, _InputIterator1 __last1
,
170 _InputIterator2 __first2
, _Tp __init
)
172 // concept requirements
173 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator1
>)
174 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator2
>)
175 __glibcxx_requires_valid_range(__first1
, __last1
);
177 for (; __first1
!= __last1
; ++__first1
, ++__first2
)
178 __init
= __init
+ (*__first1
* *__first2
);
183 * @brief Compute inner product of two ranges.
185 * Starting with an initial value of @a init, applies @a binary_op2 to
186 * successive elements from the two ranges and accumulates each result into
187 * the accumulated value using @a binary_op1. The values in the ranges are
188 * processed in order.
190 * @param first1 Start of range 1.
191 * @param last1 End of range 1.
192 * @param first2 Start of range 2.
193 * @param init Starting value to add other values to.
194 * @param binary_op1 Function object to accumulate with.
195 * @param binary_op2 Function object to apply to pairs of input values.
196 * @return The final inner product.
198 template<typename _InputIterator1
, typename _InputIterator2
, typename _Tp
,
199 typename _BinaryOperation1
, typename _BinaryOperation2
>
201 inner_product(_InputIterator1 __first1
, _InputIterator1 __last1
,
202 _InputIterator2 __first2
, _Tp __init
,
203 _BinaryOperation1 __binary_op1
,
204 _BinaryOperation2 __binary_op2
)
206 // concept requirements
207 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator1
>)
208 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator2
>)
209 __glibcxx_requires_valid_range(__first1
, __last1
);
211 for (; __first1
!= __last1
; ++__first1
, ++__first2
)
212 __init
= __binary_op1(__init
, __binary_op2(*__first1
, *__first2
));
217 * @brief Return list of partial sums
219 * Accumulates the values in the range [first,last) using operator+().
220 * As each successive input value is added into the total, that partial sum
221 * is written to @a result. Therefore, the first value in result is the
222 * first value of the input, the second value in result is the sum of the
223 * first and second input values, and so on.
225 * @param first Start of input range.
226 * @param last End of input range.
227 * @param result Output to write sums to.
228 * @return Iterator pointing just beyond the values written to result.
230 template<typename _InputIterator
, typename _OutputIterator
>
232 partial_sum(_InputIterator __first
, _InputIterator __last
,
233 _OutputIterator __result
)
235 typedef typename iterator_traits
<_InputIterator
>::value_type _ValueType
;
237 // concept requirements
238 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator
>)
239 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
241 __glibcxx_requires_valid_range(__first
, __last
);
243 if (__first
== __last
)
245 _ValueType __value
= *__first
;
247 while (++__first
!= __last
)
249 __value
= __value
+ *__first
;
250 *++__result
= __value
;
256 * @brief Return list of partial sums
258 * Accumulates the values in the range [first,last) using operator+().
259 * As each successive input value is added into the total, that partial sum
260 * is written to @a result. Therefore, the first value in result is the
261 * first value of the input, the second value in result is the sum of the
262 * first and second input values, and so on.
264 * @param first Start of input range.
265 * @param last End of input range.
266 * @param result Output to write sums to.
267 * @return Iterator pointing just beyond the values written to result.
269 template<typename _InputIterator
, typename _OutputIterator
,
270 typename _BinaryOperation
>
272 partial_sum(_InputIterator __first
, _InputIterator __last
,
273 _OutputIterator __result
, _BinaryOperation __binary_op
)
275 typedef typename iterator_traits
<_InputIterator
>::value_type _ValueType
;
277 // concept requirements
278 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator
>)
279 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
281 __glibcxx_requires_valid_range(__first
, __last
);
283 if (__first
== __last
)
285 _ValueType __value
= *__first
;
287 while (++__first
!= __last
)
289 __value
= __binary_op(__value
, *__first
);
290 *++__result
= __value
;
296 * @brief Return differences between adjacent values.
298 * Computes the difference between adjacent values in the range
299 * [first,last) using operator-() and writes the result to @a result.
301 * @param first Start of input range.
302 * @param last End of input range.
303 * @param result Output to write sums to.
304 * @return Iterator pointing just beyond the values written to result.
306 template<typename _InputIterator
, typename _OutputIterator
>
308 adjacent_difference(_InputIterator __first
,
309 _InputIterator __last
, _OutputIterator __result
)
311 typedef typename iterator_traits
<_InputIterator
>::value_type _ValueType
;
313 // concept requirements
314 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator
>)
315 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
317 __glibcxx_requires_valid_range(__first
, __last
);
319 if (__first
== __last
)
321 _ValueType __value
= *__first
;
323 while (++__first
!= __last
)
325 _ValueType __tmp
= *__first
;
326 *++__result
= __tmp
- __value
;
333 * @brief Return differences between adjacent values.
335 * Computes the difference between adjacent values in the range
336 * [first,last) using the function object @a binary_op and writes the
337 * result to @a result.
339 * @param first Start of input range.
340 * @param last End of input range.
341 * @param result Output to write sums to.
342 * @return Iterator pointing just beyond the values written to result.
344 template<typename _InputIterator
, typename _OutputIterator
,
345 typename _BinaryOperation
>
347 adjacent_difference(_InputIterator __first
, _InputIterator __last
,
348 _OutputIterator __result
, _BinaryOperation __binary_op
)
350 typedef typename iterator_traits
<_InputIterator
>::value_type _ValueType
;
352 // concept requirements
353 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator
>)
354 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
356 __glibcxx_requires_valid_range(__first
, __last
);
358 if (__first
== __last
)
360 _ValueType __value
= *__first
;
362 while (++__first
!= __last
)
364 _ValueType __tmp
= *__first
;
365 *++__result
= __binary_op(__tmp
, __value
);
371 _GLIBCXX_END_NESTED_NAMESPACE
373 #endif /* _STL_NUMERIC_H */