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