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