libstdc++
stl_numeric.h
Go to the documentation of this file.
1 // Numeric functions implementation -*- C++ -*-
2 
3 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010,
4 // 2011 Free Software Foundation, Inc.
5 //
6 // This file is part of the GNU ISO C++ Library. This library is free
7 // software; you can redistribute it and/or modify it under the
8 // terms of the GNU General Public License as published by the
9 // Free Software Foundation; either version 3, or (at your option)
10 // any later version.
11 
12 // This library is distributed in the hope that it will be useful,
13 // but WITHOUT ANY WARRANTY; without even the implied warranty of
14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 // GNU General Public License for more details.
16 
17 // Under Section 7 of GPL version 3, you are granted additional
18 // permissions described in the GCC Runtime Library Exception, version
19 // 3.1, as published by the Free Software Foundation.
20 
21 // You should have received a copy of the GNU General Public License and
22 // a copy of the GCC Runtime Library Exception along with this program;
23 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
24 // <http://www.gnu.org/licenses/>.
25 
26 /*
27  *
28  * Copyright (c) 1994
29  * Hewlett-Packard Company
30  *
31  * Permission to use, copy, modify, distribute and sell this software
32  * and its documentation for any purpose is hereby granted without fee,
33  * provided that the above copyright notice appear in all copies and
34  * that both that copyright notice and this permission notice appear
35  * in supporting documentation. Hewlett-Packard Company makes no
36  * representations about the suitability of this software for any
37  * purpose. It is provided "as is" without express or implied warranty.
38  *
39  *
40  * Copyright (c) 1996,1997
41  * Silicon Graphics Computer Systems, Inc.
42  *
43  * Permission to use, copy, modify, distribute and sell this software
44  * and its documentation for any purpose is hereby granted without fee,
45  * provided that the above copyright notice appear in all copies and
46  * that both that copyright notice and this permission notice appear
47  * in supporting documentation. Silicon Graphics makes no
48  * representations about the suitability of this software for any
49  * purpose. It is provided "as is" without express or implied warranty.
50  */
51 
52 /** @file bits/stl_numeric.h
53  * This is an internal header file, included by other library headers.
54  * Do not attempt to use it directly. @headername{numeric}
55  */
56 
57 #ifndef _STL_NUMERIC_H
58 #define _STL_NUMERIC_H 1
59 
60 #include <bits/concept_check.h>
61 #include <debug/debug.h>
62 #include <bits/move.h> // For _GLIBCXX_MOVE
63 
64 #ifdef __GXX_EXPERIMENTAL_CXX0X__
65 
66 namespace std _GLIBCXX_VISIBILITY(default)
67 {
68 _GLIBCXX_BEGIN_NAMESPACE_VERSION
69 
70  /**
71  * @brief Create a range of sequentially increasing values.
72  *
73  * For each element in the range @p [first,last) assigns @p value and
74  * increments @p value as if by @p ++value.
75  *
76  * @param first Start of range.
77  * @param last End of range.
78  * @param value Starting value.
79  * @return Nothing.
80  */
81  template<typename _ForwardIterator, typename _Tp>
82  void
83  iota(_ForwardIterator __first, _ForwardIterator __last, _Tp __value)
84  {
85  // concept requirements
86  __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
87  _ForwardIterator>)
88  __glibcxx_function_requires(_ConvertibleConcept<_Tp,
89  typename iterator_traits<_ForwardIterator>::value_type>)
90  __glibcxx_requires_valid_range(__first, __last);
91 
92  for (; __first != __last; ++__first)
93  {
94  *__first = __value;
95  ++__value;
96  }
97  }
98 
99 _GLIBCXX_END_NAMESPACE_VERSION
100 } // namespace std
101 
102 #endif
103 
104 namespace std _GLIBCXX_VISIBILITY(default)
105 {
106 _GLIBCXX_BEGIN_NAMESPACE_ALGO
107 
108  /**
109  * @brief Accumulate values in a range.
110  *
111  * Accumulates the values in the range [first,last) using operator+(). The
112  * initial value is @a init. The values are processed in order.
113  *
114  * @param first Start of range.
115  * @param last End of range.
116  * @param init Starting value to add other values to.
117  * @return The final sum.
118  */
119  template<typename _InputIterator, typename _Tp>
120  inline _Tp
121  accumulate(_InputIterator __first, _InputIterator __last, _Tp __init)
122  {
123  // concept requirements
124  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
125  __glibcxx_requires_valid_range(__first, __last);
126 
127  for (; __first != __last; ++__first)
128  __init = __init + *__first;
129  return __init;
130  }
131 
132  /**
133  * @brief Accumulate values in a range with operation.
134  *
135  * Accumulates the values in the range [first,last) using the function
136  * object @a binary_op. The initial value is @a init. The values are
137  * processed in order.
138  *
139  * @param first Start of range.
140  * @param last End of range.
141  * @param init Starting value to add other values to.
142  * @param binary_op Function object to accumulate with.
143  * @return The final sum.
144  */
145  template<typename _InputIterator, typename _Tp, typename _BinaryOperation>
146  inline _Tp
147  accumulate(_InputIterator __first, _InputIterator __last, _Tp __init,
148  _BinaryOperation __binary_op)
149  {
150  // concept requirements
151  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
152  __glibcxx_requires_valid_range(__first, __last);
153 
154  for (; __first != __last; ++__first)
155  __init = __binary_op(__init, *__first);
156  return __init;
157  }
158 
159  /**
160  * @brief Compute inner product of two ranges.
161  *
162  * Starting with an initial value of @a init, multiplies successive
163  * elements from the two ranges and adds each product into the accumulated
164  * value using operator+(). The values in the ranges are processed in
165  * order.
166  *
167  * @param first1 Start of range 1.
168  * @param last1 End of range 1.
169  * @param first2 Start of range 2.
170  * @param init Starting value to add other values to.
171  * @return The final inner product.
172  */
173  template<typename _InputIterator1, typename _InputIterator2, typename _Tp>
174  inline _Tp
175  inner_product(_InputIterator1 __first1, _InputIterator1 __last1,
176  _InputIterator2 __first2, _Tp __init)
177  {
178  // concept requirements
179  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
180  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
181  __glibcxx_requires_valid_range(__first1, __last1);
182 
183  for (; __first1 != __last1; ++__first1, ++__first2)
184  __init = __init + (*__first1 * *__first2);
185  return __init;
186  }
187 
188  /**
189  * @brief Compute inner product of two ranges.
190  *
191  * Starting with an initial value of @a init, applies @a binary_op2 to
192  * successive elements from the two ranges and accumulates each result into
193  * the accumulated value using @a binary_op1. The values in the ranges are
194  * processed in order.
195  *
196  * @param first1 Start of range 1.
197  * @param last1 End of range 1.
198  * @param first2 Start of range 2.
199  * @param init Starting value to add other values to.
200  * @param binary_op1 Function object to accumulate with.
201  * @param binary_op2 Function object to apply to pairs of input values.
202  * @return The final inner product.
203  */
204  template<typename _InputIterator1, typename _InputIterator2, typename _Tp,
205  typename _BinaryOperation1, typename _BinaryOperation2>
206  inline _Tp
207  inner_product(_InputIterator1 __first1, _InputIterator1 __last1,
208  _InputIterator2 __first2, _Tp __init,
209  _BinaryOperation1 __binary_op1,
210  _BinaryOperation2 __binary_op2)
211  {
212  // concept requirements
213  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
214  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
215  __glibcxx_requires_valid_range(__first1, __last1);
216 
217  for (; __first1 != __last1; ++__first1, ++__first2)
218  __init = __binary_op1(__init, __binary_op2(*__first1, *__first2));
219  return __init;
220  }
221 
222  /**
223  * @brief Return list of partial sums
224  *
225  * Accumulates the values in the range [first,last) using the @c + operator.
226  * As each successive input value is added into the total, that partial sum
227  * is written to @p result. Therefore, the first value in @p result is the
228  * first value of the input, the second value in @p result is the sum of the
229  * first and second input values, and so on.
230  *
231  * @param first Start of input range.
232  * @param last End of input range.
233  * @param result Output to write sums to.
234  * @return Iterator pointing just beyond the values written to result.
235  */
236  template<typename _InputIterator, typename _OutputIterator>
237  _OutputIterator
238  partial_sum(_InputIterator __first, _InputIterator __last,
239  _OutputIterator __result)
240  {
241  typedef typename iterator_traits<_InputIterator>::value_type _ValueType;
242 
243  // concept requirements
244  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
245  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
246  _ValueType>)
247  __glibcxx_requires_valid_range(__first, __last);
248 
249  if (__first == __last)
250  return __result;
251  _ValueType __value = *__first;
252  *__result = __value;
253  while (++__first != __last)
254  {
255  __value = __value + *__first;
256  *++__result = __value;
257  }
258  return ++__result;
259  }
260 
261  /**
262  * @brief Return list of partial sums
263  *
264  * Accumulates the values in the range [first,last) using @p binary_op.
265  * As each successive input value is added into the total, that partial sum
266  * is written to @a result. Therefore, the first value in @p result is the
267  * first value of the input, the second value in @p result is the sum of the
268  * first and second input values, and so on.
269  *
270  * @param first Start of input range.
271  * @param last End of input range.
272  * @param result Output to write sums to.
273  * @param binary_op Function object.
274  * @return Iterator pointing just beyond the values written to result.
275  */
276  template<typename _InputIterator, typename _OutputIterator,
277  typename _BinaryOperation>
278  _OutputIterator
279  partial_sum(_InputIterator __first, _InputIterator __last,
280  _OutputIterator __result, _BinaryOperation __binary_op)
281  {
282  typedef typename iterator_traits<_InputIterator>::value_type _ValueType;
283 
284  // concept requirements
285  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
286  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
287  _ValueType>)
288  __glibcxx_requires_valid_range(__first, __last);
289 
290  if (__first == __last)
291  return __result;
292  _ValueType __value = *__first;
293  *__result = __value;
294  while (++__first != __last)
295  {
296  __value = __binary_op(__value, *__first);
297  *++__result = __value;
298  }
299  return ++__result;
300  }
301 
302  /**
303  * @brief Return differences between adjacent values.
304  *
305  * Computes the difference between adjacent values in the range
306  * [first,last) using operator-() and writes the result to @a result.
307  *
308  * @param first Start of input range.
309  * @param last End of input range.
310  * @param result Output to write sums to.
311  * @return Iterator pointing just beyond the values written to result.
312  *
313  * _GLIBCXX_RESOLVE_LIB_DEFECTS
314  * DR 539. partial_sum and adjacent_difference should mention requirements
315  */
316  template<typename _InputIterator, typename _OutputIterator>
317  _OutputIterator
318  adjacent_difference(_InputIterator __first,
319  _InputIterator __last, _OutputIterator __result)
320  {
321  typedef typename iterator_traits<_InputIterator>::value_type _ValueType;
322 
323  // concept requirements
324  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
325  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
326  _ValueType>)
327  __glibcxx_requires_valid_range(__first, __last);
328 
329  if (__first == __last)
330  return __result;
331  _ValueType __value = *__first;
332  *__result = __value;
333  while (++__first != __last)
334  {
335  _ValueType __tmp = *__first;
336  *++__result = __tmp - __value;
337  __value = _GLIBCXX_MOVE(__tmp);
338  }
339  return ++__result;
340  }
341 
342  /**
343  * @brief Return differences between adjacent values.
344  *
345  * Computes the difference between adjacent values in the range
346  * [first,last) using the function object @a binary_op and writes the
347  * result to @a result.
348  *
349  * @param first Start of input range.
350  * @param last End of input range.
351  * @param result Output to write sums to.
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 */