]>
Commit | Line | Data |
---|---|---|
42526146 PE |
1 | // Numeric functions implementation -*- C++ -*- |
2 | ||
a5544970 | 3 | // Copyright (C) 2001-2019 Free Software Foundation, Inc. |
42526146 PE |
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 | |
748086b7 | 8 | // Free Software Foundation; either version 3, or (at your option) |
42526146 PE |
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 | ||
748086b7 JJ |
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. | |
42526146 | 19 | |
748086b7 JJ |
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/>. | |
42526146 | 24 | |
725dc051 BK |
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 | ||
f910786b | 51 | /** @file bits/stl_numeric.h |
729e3d3f | 52 | * This is an internal header file, included by other library headers. |
f910786b | 53 | * Do not attempt to use it directly. @headername{numeric} |
725dc051 BK |
54 | */ |
55 | ||
3d7c150e BK |
56 | #ifndef _STL_NUMERIC_H |
57 | #define _STL_NUMERIC_H 1 | |
725dc051 | 58 | |
681a6919 | 59 | #include <bits/concept_check.h> |
285b36d6 | 60 | #include <debug/debug.h> |
8246b314 | 61 | #include <bits/move.h> // For _GLIBCXX_MOVE |
285b36d6 | 62 | |
fa52081d | 63 | |
12ffa228 BK |
64 | namespace std _GLIBCXX_VISIBILITY(default) |
65 | { | |
66 | _GLIBCXX_BEGIN_NAMESPACE_VERSION | |
fa52081d | 67 | |
ed920373 JW |
68 | /** @defgroup numeric_ops Generalized Numeric operations |
69 | * @ingroup algorithms | |
70 | */ | |
71 | ||
72 | #if __cplusplus >= 201103L | |
fa52081d PC |
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 | * | |
93c66bc6 BK |
79 | * @param __first Start of range. |
80 | * @param __last End of range. | |
81 | * @param __value Starting value. | |
fa52081d | 82 | * @return Nothing. |
ed920373 | 83 | * @ingroup numeric_ops |
fa52081d PC |
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 | } | |
ed920373 | 102 | #endif |
fa52081d | 103 | |
12ffa228 | 104 | _GLIBCXX_END_NAMESPACE_VERSION |
fa52081d | 105 | |
12ffa228 | 106 | _GLIBCXX_BEGIN_NAMESPACE_ALGO |
725dc051 | 107 | |
5840e3b8 JW |
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 | ||
ed920373 JW |
116 | /// @addtogroup numeric_ops |
117 | /// @{ | |
118 | ||
7fb397a4 JQ |
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 | * | |
93c66bc6 BK |
125 | * @param __first Start of range. |
126 | * @param __last End of range. | |
127 | * @param __init Starting value to add other values to. | |
7fb397a4 JQ |
128 | * @return The final sum. |
129 | */ | |
02d92e3b | 130 | template<typename _InputIterator, typename _Tp> |
d46c958b | 131 | inline _Tp |
02d92e3b SW |
132 | accumulate(_InputIterator __first, _InputIterator __last, _Tp __init) |
133 | { | |
134 | // concept requirements | |
3d7c150e | 135 | __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) |
285b36d6 | 136 | __glibcxx_requires_valid_range(__first, __last); |
02d92e3b | 137 | |
dae62ba8 | 138 | for (; __first != __last; ++__first) |
5840e3b8 | 139 | __init = _GLIBCXX_MOVE_IF_20(__init) + *__first; |
02d92e3b SW |
140 | return __init; |
141 | } | |
30a20a1e | 142 | |
7fb397a4 JQ |
143 | /** |
144 | * @brief Accumulate values in a range with operation. | |
145 | * | |
ed920373 JW |
146 | * Accumulates the values in the range `[first,last)` using the function |
147 | * object `__binary_op`. The initial value is `__init`. The values are | |
7fb397a4 JQ |
148 | * processed in order. |
149 | * | |
93c66bc6 BK |
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. | |
7fb397a4 JQ |
154 | * @return The final sum. |
155 | */ | |
02d92e3b | 156 | template<typename _InputIterator, typename _Tp, typename _BinaryOperation> |
d46c958b | 157 | inline _Tp |
02d92e3b SW |
158 | accumulate(_InputIterator __first, _InputIterator __last, _Tp __init, |
159 | _BinaryOperation __binary_op) | |
160 | { | |
161 | // concept requirements | |
3d7c150e | 162 | __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) |
285b36d6 | 163 | __glibcxx_requires_valid_range(__first, __last); |
02d92e3b | 164 | |
dae62ba8 | 165 | for (; __first != __last; ++__first) |
5840e3b8 | 166 | __init = __binary_op(_GLIBCXX_MOVE_IF_20(__init), *__first); |
02d92e3b SW |
167 | return __init; |
168 | } | |
725dc051 | 169 | |
7fb397a4 JQ |
170 | /** |
171 | * @brief Compute inner product of two ranges. | |
172 | * | |
7897a1c0 | 173 | * Starting with an initial value of @p __init, multiplies successive |
7fb397a4 JQ |
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 | * | |
93c66bc6 BK |
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. | |
7fb397a4 JQ |
182 | * @return The final inner product. |
183 | */ | |
02d92e3b | 184 | template<typename _InputIterator1, typename _InputIterator2, typename _Tp> |
d46c958b | 185 | inline _Tp |
02d92e3b SW |
186 | inner_product(_InputIterator1 __first1, _InputIterator1 __last1, |
187 | _InputIterator2 __first2, _Tp __init) | |
188 | { | |
189 | // concept requirements | |
3d7c150e BK |
190 | __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) |
191 | __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) | |
285b36d6 | 192 | __glibcxx_requires_valid_range(__first1, __last1); |
02d92e3b | 193 | |
f970a17d | 194 | for (; __first1 != __last1; ++__first1, (void)++__first2) |
5840e3b8 | 195 | __init = _GLIBCXX_MOVE_IF_20(__init) + (*__first1 * *__first2); |
02d92e3b | 196 | return __init; |
725dc051 BK |
197 | } |
198 | ||
7fb397a4 JQ |
199 | /** |
200 | * @brief Compute inner product of two ranges. | |
201 | * | |
7897a1c0 | 202 | * Starting with an initial value of @p __init, applies @p __binary_op2 to |
7fb397a4 | 203 | * successive elements from the two ranges and accumulates each result into |
7897a1c0 | 204 | * the accumulated value using @p __binary_op1. The values in the ranges are |
7fb397a4 JQ |
205 | * processed in order. |
206 | * | |
93c66bc6 BK |
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. | |
7fb397a4 JQ |
213 | * @return The final inner product. |
214 | */ | |
02d92e3b | 215 | template<typename _InputIterator1, typename _InputIterator2, typename _Tp, |
fa52081d | 216 | typename _BinaryOperation1, typename _BinaryOperation2> |
d46c958b | 217 | inline _Tp |
02d92e3b | 218 | inner_product(_InputIterator1 __first1, _InputIterator1 __last1, |
ed6814f7 | 219 | _InputIterator2 __first2, _Tp __init, |
02d92e3b SW |
220 | _BinaryOperation1 __binary_op1, |
221 | _BinaryOperation2 __binary_op2) | |
222 | { | |
223 | // concept requirements | |
3d7c150e BK |
224 | __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) |
225 | __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) | |
285b36d6 | 226 | __glibcxx_requires_valid_range(__first1, __last1); |
02d92e3b | 227 | |
f970a17d | 228 | for (; __first1 != __last1; ++__first1, (void)++__first2) |
5840e3b8 JW |
229 | __init = __binary_op1(_GLIBCXX_MOVE_IF_20(__init), |
230 | __binary_op2(*__first1, *__first2)); | |
02d92e3b | 231 | return __init; |
725dc051 | 232 | } |
725dc051 | 233 | |
7fb397a4 JQ |
234 | /** |
235 | * @brief Return list of partial sums | |
236 | * | |
d36971dd | 237 | * Accumulates the values in the range [first,last) using the @c + operator. |
7fb397a4 | 238 | * As each successive input value is added into the total, that partial sum |
d36971dd JW |
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. | |
7fb397a4 | 242 | * |
93c66bc6 BK |
243 | * @param __first Start of input range. |
244 | * @param __last End of input range. | |
7897a1c0 BK |
245 | * @param __result Output sum. |
246 | * @return Iterator pointing just beyond the values written to __result. | |
7fb397a4 | 247 | */ |
02d92e3b | 248 | template<typename _InputIterator, typename _OutputIterator> |
ed6814f7 | 249 | _OutputIterator |
02d92e3b SW |
250 | partial_sum(_InputIterator __first, _InputIterator __last, |
251 | _OutputIterator __result) | |
252 | { | |
253 | typedef typename iterator_traits<_InputIterator>::value_type _ValueType; | |
254 | ||
255 | // concept requirements | |
3d7c150e | 256 | __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) |
dae62ba8 PC |
257 | __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, |
258 | _ValueType>) | |
285b36d6 | 259 | __glibcxx_requires_valid_range(__first, __last); |
02d92e3b | 260 | |
dae62ba8 PC |
261 | if (__first == __last) |
262 | return __result; | |
02d92e3b | 263 | _ValueType __value = *__first; |
cb1d5dba | 264 | *__result = __value; |
dae62ba8 PC |
265 | while (++__first != __last) |
266 | { | |
5840e3b8 | 267 | __value = _GLIBCXX_MOVE_IF_20(__value) + *__first; |
dae62ba8 PC |
268 | *++__result = __value; |
269 | } | |
02d92e3b SW |
270 | return ++__result; |
271 | } | |
725dc051 | 272 | |
7fb397a4 JQ |
273 | /** |
274 | * @brief Return list of partial sums | |
275 | * | |
d36971dd | 276 | * Accumulates the values in the range [first,last) using @p __binary_op. |
7fb397a4 | 277 | * As each successive input value is added into the total, that partial sum |
d36971dd JW |
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. | |
7fb397a4 | 281 | * |
93c66bc6 BK |
282 | * @param __first Start of input range. |
283 | * @param __last End of input range. | |
7897a1c0 | 284 | * @param __result Output sum. |
d36971dd | 285 | * @param __binary_op Function object. |
7897a1c0 | 286 | * @return Iterator pointing just beyond the values written to __result. |
7fb397a4 | 287 | */ |
dae62ba8 PC |
288 | template<typename _InputIterator, typename _OutputIterator, |
289 | typename _BinaryOperation> | |
ed6814f7 | 290 | _OutputIterator |
02d92e3b SW |
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 | |
3d7c150e | 297 | __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) |
dae62ba8 PC |
298 | __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, |
299 | _ValueType>) | |
285b36d6 | 300 | __glibcxx_requires_valid_range(__first, __last); |
02d92e3b | 301 | |
dae62ba8 PC |
302 | if (__first == __last) |
303 | return __result; | |
02d92e3b | 304 | _ValueType __value = *__first; |
cb1d5dba | 305 | *__result = __value; |
dae62ba8 PC |
306 | while (++__first != __last) |
307 | { | |
5840e3b8 | 308 | __value = __binary_op(_GLIBCXX_MOVE_IF_20(__value), *__first); |
dae62ba8 PC |
309 | *++__result = __value; |
310 | } | |
02d92e3b SW |
311 | return ++__result; |
312 | } | |
725dc051 | 313 | |
7fb397a4 JQ |
314 | /** |
315 | * @brief Return differences between adjacent values. | |
316 | * | |
317 | * Computes the difference between adjacent values in the range | |
7897a1c0 | 318 | * [first,last) using operator-() and writes the result to @p __result. |
7fb397a4 | 319 | * |
93c66bc6 BK |
320 | * @param __first Start of input range. |
321 | * @param __last End of input range. | |
7897a1c0 | 322 | * @param __result Output sums. |
7fb397a4 | 323 | * @return Iterator pointing just beyond the values written to result. |
8246b314 PC |
324 | * |
325 | * _GLIBCXX_RESOLVE_LIB_DEFECTS | |
326 | * DR 539. partial_sum and adjacent_difference should mention requirements | |
7fb397a4 | 327 | */ |
02d92e3b SW |
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 | |
3d7c150e | 336 | __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) |
dae62ba8 PC |
337 | __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, |
338 | _ValueType>) | |
285b36d6 | 339 | __glibcxx_requires_valid_range(__first, __last); |
02d92e3b | 340 | |
dae62ba8 PC |
341 | if (__first == __last) |
342 | return __result; | |
02d92e3b | 343 | _ValueType __value = *__first; |
cb1d5dba | 344 | *__result = __value; |
dae62ba8 PC |
345 | while (++__first != __last) |
346 | { | |
347 | _ValueType __tmp = *__first; | |
5840e3b8 | 348 | *++__result = __tmp - _GLIBCXX_MOVE_IF_20(__value); |
8246b314 | 349 | __value = _GLIBCXX_MOVE(__tmp); |
dae62ba8 | 350 | } |
02d92e3b SW |
351 | return ++__result; |
352 | } | |
725dc051 | 353 | |
7fb397a4 JQ |
354 | /** |
355 | * @brief Return differences between adjacent values. | |
356 | * | |
357 | * Computes the difference between adjacent values in the range | |
7897a1c0 BK |
358 | * [__first,__last) using the function object @p __binary_op and writes the |
359 | * result to @p __result. | |
7fb397a4 | 360 | * |
93c66bc6 BK |
361 | * @param __first Start of input range. |
362 | * @param __last End of input range. | |
7897a1c0 BK |
363 | * @param __result Output sum. |
364 | * @param __binary_op Function object. | |
7fb397a4 | 365 | * @return Iterator pointing just beyond the values written to result. |
8246b314 PC |
366 | * |
367 | * _GLIBCXX_RESOLVE_LIB_DEFECTS | |
368 | * DR 539. partial_sum and adjacent_difference should mention requirements | |
7fb397a4 | 369 | */ |
dae62ba8 PC |
370 | template<typename _InputIterator, typename _OutputIterator, |
371 | typename _BinaryOperation> | |
ed6814f7 | 372 | _OutputIterator |
02d92e3b SW |
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 | |
3d7c150e | 379 | __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) |
dae62ba8 PC |
380 | __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, |
381 | _ValueType>) | |
285b36d6 | 382 | __glibcxx_requires_valid_range(__first, __last); |
02d92e3b | 383 | |
dae62ba8 PC |
384 | if (__first == __last) |
385 | return __result; | |
02d92e3b | 386 | _ValueType __value = *__first; |
cb1d5dba | 387 | *__result = __value; |
dae62ba8 PC |
388 | while (++__first != __last) |
389 | { | |
390 | _ValueType __tmp = *__first; | |
5840e3b8 | 391 | *++__result = __binary_op(__tmp, _GLIBCXX_MOVE_IF_20(__value)); |
8246b314 | 392 | __value = _GLIBCXX_MOVE(__tmp); |
dae62ba8 | 393 | } |
02d92e3b SW |
394 | return ++__result; |
395 | } | |
725dc051 | 396 | |
ed920373 JW |
397 | // @} group numeric_ops |
398 | ||
5840e3b8 JW |
399 | #undef _GLIBCXX_MOVE_IF_20 |
400 | ||
12ffa228 BK |
401 | _GLIBCXX_END_NAMESPACE_ALGO |
402 | } // namespace std | |
725dc051 | 403 | |
3d7c150e | 404 | #endif /* _STL_NUMERIC_H */ |