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 | |
64 | namespace 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 | |