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