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