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