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