libstdc++
|
00001 // Numeric functions implementation -*- C++ -*- 00002 00003 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 00004 // 2011 Free Software Foundation, Inc. 00005 // 00006 // This file is part of the GNU ISO C++ Library. This library is free 00007 // software; you can redistribute it and/or modify it under the 00008 // terms of the GNU General Public License as published by the 00009 // Free Software Foundation; either version 3, or (at your option) 00010 // any later version. 00011 00012 // This library is distributed in the hope that it will be useful, 00013 // but WITHOUT ANY WARRANTY; without even the implied warranty of 00014 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00015 // GNU General Public License for more details. 00016 00017 // Under Section 7 of GPL version 3, you are granted additional 00018 // permissions described in the GCC Runtime Library Exception, version 00019 // 3.1, as published by the Free Software Foundation. 00020 00021 // You should have received a copy of the GNU General Public License and 00022 // a copy of the GCC Runtime Library Exception along with this program; 00023 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 00024 // <http://www.gnu.org/licenses/>. 00025 00026 /* 00027 * 00028 * Copyright (c) 1994 00029 * Hewlett-Packard Company 00030 * 00031 * Permission to use, copy, modify, distribute and sell this software 00032 * and its documentation for any purpose is hereby granted without fee, 00033 * provided that the above copyright notice appear in all copies and 00034 * that both that copyright notice and this permission notice appear 00035 * in supporting documentation. Hewlett-Packard Company makes no 00036 * representations about the suitability of this software for any 00037 * purpose. It is provided "as is" without express or implied warranty. 00038 * 00039 * 00040 * Copyright (c) 1996,1997 00041 * Silicon Graphics Computer Systems, Inc. 00042 * 00043 * Permission to use, copy, modify, distribute and sell this software 00044 * and its documentation for any purpose is hereby granted without fee, 00045 * provided that the above copyright notice appear in all copies and 00046 * that both that copyright notice and this permission notice appear 00047 * in supporting documentation. Silicon Graphics makes no 00048 * representations about the suitability of this software for any 00049 * purpose. It is provided "as is" without express or implied warranty. 00050 */ 00051 00052 /** @file bits/stl_numeric.h 00053 * This is an internal header file, included by other library headers. 00054 * Do not attempt to use it directly. @headername{numeric} 00055 */ 00056 00057 #ifndef _STL_NUMERIC_H 00058 #define _STL_NUMERIC_H 1 00059 00060 #include <bits/concept_check.h> 00061 #include <debug/debug.h> 00062 #include <bits/move.h> // For _GLIBCXX_MOVE 00063 00064 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00065 00066 namespace std _GLIBCXX_VISIBILITY(default) 00067 { 00068 _GLIBCXX_BEGIN_NAMESPACE_VERSION 00069 00070 /** 00071 * @brief Create a range of sequentially increasing values. 00072 * 00073 * For each element in the range @p [first,last) assigns @p value and 00074 * increments @p value as if by @p ++value. 00075 * 00076 * @param __first Start of range. 00077 * @param __last End of range. 00078 * @param __value Starting value. 00079 * @return Nothing. 00080 */ 00081 template<typename _ForwardIterator, typename _Tp> 00082 void 00083 iota(_ForwardIterator __first, _ForwardIterator __last, _Tp __value) 00084 { 00085 // concept requirements 00086 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< 00087 _ForwardIterator>) 00088 __glibcxx_function_requires(_ConvertibleConcept<_Tp, 00089 typename iterator_traits<_ForwardIterator>::value_type>) 00090 __glibcxx_requires_valid_range(__first, __last); 00091 00092 for (; __first != __last; ++__first) 00093 { 00094 *__first = __value; 00095 ++__value; 00096 } 00097 } 00098 00099 _GLIBCXX_END_NAMESPACE_VERSION 00100 } // namespace std 00101 00102 #endif 00103 00104 namespace std _GLIBCXX_VISIBILITY(default) 00105 { 00106 _GLIBCXX_BEGIN_NAMESPACE_ALGO 00107 00108 /** 00109 * @brief Accumulate values in a range. 00110 * 00111 * Accumulates the values in the range [first,last) using operator+(). The 00112 * initial value is @a init. The values are processed in order. 00113 * 00114 * @param __first Start of range. 00115 * @param __last End of range. 00116 * @param __init Starting value to add other values to. 00117 * @return The final sum. 00118 */ 00119 template<typename _InputIterator, typename _Tp> 00120 inline _Tp 00121 accumulate(_InputIterator __first, _InputIterator __last, _Tp __init) 00122 { 00123 // concept requirements 00124 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 00125 __glibcxx_requires_valid_range(__first, __last); 00126 00127 for (; __first != __last; ++__first) 00128 __init = __init + *__first; 00129 return __init; 00130 } 00131 00132 /** 00133 * @brief Accumulate values in a range with operation. 00134 * 00135 * Accumulates the values in the range [first,last) using the function 00136 * object @p __binary_op. The initial value is @p __init. The values are 00137 * processed in order. 00138 * 00139 * @param __first Start of range. 00140 * @param __last End of range. 00141 * @param __init Starting value to add other values to. 00142 * @param __binary_op Function object to accumulate with. 00143 * @return The final sum. 00144 */ 00145 template<typename _InputIterator, typename _Tp, typename _BinaryOperation> 00146 inline _Tp 00147 accumulate(_InputIterator __first, _InputIterator __last, _Tp __init, 00148 _BinaryOperation __binary_op) 00149 { 00150 // concept requirements 00151 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 00152 __glibcxx_requires_valid_range(__first, __last); 00153 00154 for (; __first != __last; ++__first) 00155 __init = __binary_op(__init, *__first); 00156 return __init; 00157 } 00158 00159 /** 00160 * @brief Compute inner product of two ranges. 00161 * 00162 * Starting with an initial value of @p __init, multiplies successive 00163 * elements from the two ranges and adds each product into the accumulated 00164 * value using operator+(). The values in the ranges are processed in 00165 * order. 00166 * 00167 * @param __first1 Start of range 1. 00168 * @param __last1 End of range 1. 00169 * @param __first2 Start of range 2. 00170 * @param __init Starting value to add other values to. 00171 * @return The final inner product. 00172 */ 00173 template<typename _InputIterator1, typename _InputIterator2, typename _Tp> 00174 inline _Tp 00175 inner_product(_InputIterator1 __first1, _InputIterator1 __last1, 00176 _InputIterator2 __first2, _Tp __init) 00177 { 00178 // concept requirements 00179 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 00180 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 00181 __glibcxx_requires_valid_range(__first1, __last1); 00182 00183 for (; __first1 != __last1; ++__first1, ++__first2) 00184 __init = __init + (*__first1 * *__first2); 00185 return __init; 00186 } 00187 00188 /** 00189 * @brief Compute inner product of two ranges. 00190 * 00191 * Starting with an initial value of @p __init, applies @p __binary_op2 to 00192 * successive elements from the two ranges and accumulates each result into 00193 * the accumulated value using @p __binary_op1. The values in the ranges are 00194 * processed in order. 00195 * 00196 * @param __first1 Start of range 1. 00197 * @param __last1 End of range 1. 00198 * @param __first2 Start of range 2. 00199 * @param __init Starting value to add other values to. 00200 * @param __binary_op1 Function object to accumulate with. 00201 * @param __binary_op2 Function object to apply to pairs of input values. 00202 * @return The final inner product. 00203 */ 00204 template<typename _InputIterator1, typename _InputIterator2, typename _Tp, 00205 typename _BinaryOperation1, typename _BinaryOperation2> 00206 inline _Tp 00207 inner_product(_InputIterator1 __first1, _InputIterator1 __last1, 00208 _InputIterator2 __first2, _Tp __init, 00209 _BinaryOperation1 __binary_op1, 00210 _BinaryOperation2 __binary_op2) 00211 { 00212 // concept requirements 00213 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 00214 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 00215 __glibcxx_requires_valid_range(__first1, __last1); 00216 00217 for (; __first1 != __last1; ++__first1, ++__first2) 00218 __init = __binary_op1(__init, __binary_op2(*__first1, *__first2)); 00219 return __init; 00220 } 00221 00222 /** 00223 * @brief Return list of partial sums 00224 * 00225 * Accumulates the values in the range [first,last) using the @c + operator. 00226 * As each successive input value is added into the total, that partial sum 00227 * is written to @p __result. Therefore, the first value in @p __result is 00228 * the first value of the input, the second value in @p __result is the sum 00229 * of the first and second input values, and so on. 00230 * 00231 * @param __first Start of input range. 00232 * @param __last End of input range. 00233 * @param __result Output sum. 00234 * @return Iterator pointing just beyond the values written to __result. 00235 */ 00236 template<typename _InputIterator, typename _OutputIterator> 00237 _OutputIterator 00238 partial_sum(_InputIterator __first, _InputIterator __last, 00239 _OutputIterator __result) 00240 { 00241 typedef typename iterator_traits<_InputIterator>::value_type _ValueType; 00242 00243 // concept requirements 00244 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 00245 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 00246 _ValueType>) 00247 __glibcxx_requires_valid_range(__first, __last); 00248 00249 if (__first == __last) 00250 return __result; 00251 _ValueType __value = *__first; 00252 *__result = __value; 00253 while (++__first != __last) 00254 { 00255 __value = __value + *__first; 00256 *++__result = __value; 00257 } 00258 return ++__result; 00259 } 00260 00261 /** 00262 * @brief Return list of partial sums 00263 * 00264 * Accumulates the values in the range [first,last) using @p __binary_op. 00265 * As each successive input value is added into the total, that partial sum 00266 * is written to @p __result. Therefore, the first value in @p __result is 00267 * the first value of the input, the second value in @p __result is the sum 00268 * of the first and second input values, and so on. 00269 * 00270 * @param __first Start of input range. 00271 * @param __last End of input range. 00272 * @param __result Output sum. 00273 * @param __binary_op Function object. 00274 * @return Iterator pointing just beyond the values written to __result. 00275 */ 00276 template<typename _InputIterator, typename _OutputIterator, 00277 typename _BinaryOperation> 00278 _OutputIterator 00279 partial_sum(_InputIterator __first, _InputIterator __last, 00280 _OutputIterator __result, _BinaryOperation __binary_op) 00281 { 00282 typedef typename iterator_traits<_InputIterator>::value_type _ValueType; 00283 00284 // concept requirements 00285 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 00286 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 00287 _ValueType>) 00288 __glibcxx_requires_valid_range(__first, __last); 00289 00290 if (__first == __last) 00291 return __result; 00292 _ValueType __value = *__first; 00293 *__result = __value; 00294 while (++__first != __last) 00295 { 00296 __value = __binary_op(__value, *__first); 00297 *++__result = __value; 00298 } 00299 return ++__result; 00300 } 00301 00302 /** 00303 * @brief Return differences between adjacent values. 00304 * 00305 * Computes the difference between adjacent values in the range 00306 * [first,last) using operator-() and writes the result to @p __result. 00307 * 00308 * @param __first Start of input range. 00309 * @param __last End of input range. 00310 * @param __result Output sums. 00311 * @return Iterator pointing just beyond the values written to result. 00312 * 00313 * _GLIBCXX_RESOLVE_LIB_DEFECTS 00314 * DR 539. partial_sum and adjacent_difference should mention requirements 00315 */ 00316 template<typename _InputIterator, typename _OutputIterator> 00317 _OutputIterator 00318 adjacent_difference(_InputIterator __first, 00319 _InputIterator __last, _OutputIterator __result) 00320 { 00321 typedef typename iterator_traits<_InputIterator>::value_type _ValueType; 00322 00323 // concept requirements 00324 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 00325 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 00326 _ValueType>) 00327 __glibcxx_requires_valid_range(__first, __last); 00328 00329 if (__first == __last) 00330 return __result; 00331 _ValueType __value = *__first; 00332 *__result = __value; 00333 while (++__first != __last) 00334 { 00335 _ValueType __tmp = *__first; 00336 *++__result = __tmp - __value; 00337 __value = _GLIBCXX_MOVE(__tmp); 00338 } 00339 return ++__result; 00340 } 00341 00342 /** 00343 * @brief Return differences between adjacent values. 00344 * 00345 * Computes the difference between adjacent values in the range 00346 * [__first,__last) using the function object @p __binary_op and writes the 00347 * result to @p __result. 00348 * 00349 * @param __first Start of input range. 00350 * @param __last End of input range. 00351 * @param __result Output sum. 00352 * @param __binary_op Function object. 00353 * @return Iterator pointing just beyond the values written to result. 00354 * 00355 * _GLIBCXX_RESOLVE_LIB_DEFECTS 00356 * DR 539. partial_sum and adjacent_difference should mention requirements 00357 */ 00358 template<typename _InputIterator, typename _OutputIterator, 00359 typename _BinaryOperation> 00360 _OutputIterator 00361 adjacent_difference(_InputIterator __first, _InputIterator __last, 00362 _OutputIterator __result, _BinaryOperation __binary_op) 00363 { 00364 typedef typename iterator_traits<_InputIterator>::value_type _ValueType; 00365 00366 // concept requirements 00367 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 00368 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 00369 _ValueType>) 00370 __glibcxx_requires_valid_range(__first, __last); 00371 00372 if (__first == __last) 00373 return __result; 00374 _ValueType __value = *__first; 00375 *__result = __value; 00376 while (++__first != __last) 00377 { 00378 _ValueType __tmp = *__first; 00379 *++__result = __binary_op(__tmp, __value); 00380 __value = _GLIBCXX_MOVE(__tmp); 00381 } 00382 return ++__result; 00383 } 00384 00385 _GLIBCXX_END_NAMESPACE_ALGO 00386 } // namespace std 00387 00388 #endif /* _STL_NUMERIC_H */