Line data Source code
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 0 : for (; __first != __last; ++__first)
166 0 : __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 */
|
