libstdc++
|
00001 // Numeric functions implementation -*- C++ -*- 00002 00003 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009 00004 // 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 stl_numeric.h 00053 * This is an internal header file, included by other library headers. 00054 * You should not attempt to use it directly. 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 00063 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00064 00065 _GLIBCXX_BEGIN_NAMESPACE(std) 00066 00067 /** 00068 * @brief Create a range of sequentially increasing values. 00069 * 00070 * For each element in the range @p [first,last) assigns @p value and 00071 * increments @p value as if by @p ++value. 00072 * 00073 * @param first Start of range. 00074 * @param last End of range. 00075 * @param value Starting value. 00076 * @return Nothing. 00077 */ 00078 template<typename _ForwardIterator, typename _Tp> 00079 void 00080 iota(_ForwardIterator __first, _ForwardIterator __last, _Tp __value) 00081 { 00082 // concept requirements 00083 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< 00084 _ForwardIterator>) 00085 __glibcxx_function_requires(_ConvertibleConcept<_Tp, 00086 typename iterator_traits<_ForwardIterator>::value_type>) 00087 __glibcxx_requires_valid_range(__first, __last); 00088 00089 for (; __first != __last; ++__first) 00090 { 00091 *__first = __value; 00092 ++__value; 00093 } 00094 } 00095 00096 _GLIBCXX_END_NAMESPACE 00097 00098 #endif 00099 00100 _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_P) 00101 00102 /** 00103 * @brief Accumulate values in a range. 00104 * 00105 * Accumulates the values in the range [first,last) using operator+(). The 00106 * initial value is @a init. The values are processed in order. 00107 * 00108 * @param first Start of range. 00109 * @param last End of range. 00110 * @param init Starting value to add other values to. 00111 * @return The final sum. 00112 */ 00113 template<typename _InputIterator, typename _Tp> 00114 inline _Tp 00115 accumulate(_InputIterator __first, _InputIterator __last, _Tp __init) 00116 { 00117 // concept requirements 00118 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 00119 __glibcxx_requires_valid_range(__first, __last); 00120 00121 for (; __first != __last; ++__first) 00122 __init = __init + *__first; 00123 return __init; 00124 } 00125 00126 /** 00127 * @brief Accumulate values in a range with operation. 00128 * 00129 * Accumulates the values in the range [first,last) using the function 00130 * object @a binary_op. The initial value is @a init. The values are 00131 * processed in order. 00132 * 00133 * @param first Start of range. 00134 * @param last End of range. 00135 * @param init Starting value to add other values to. 00136 * @param binary_op Function object to accumulate with. 00137 * @return The final sum. 00138 */ 00139 template<typename _InputIterator, typename _Tp, typename _BinaryOperation> 00140 inline _Tp 00141 accumulate(_InputIterator __first, _InputIterator __last, _Tp __init, 00142 _BinaryOperation __binary_op) 00143 { 00144 // concept requirements 00145 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 00146 __glibcxx_requires_valid_range(__first, __last); 00147 00148 for (; __first != __last; ++__first) 00149 __init = __binary_op(__init, *__first); 00150 return __init; 00151 } 00152 00153 /** 00154 * @brief Compute inner product of two ranges. 00155 * 00156 * Starting with an initial value of @a init, multiplies successive 00157 * elements from the two ranges and adds each product into the accumulated 00158 * value using operator+(). The values in the ranges are processed in 00159 * order. 00160 * 00161 * @param first1 Start of range 1. 00162 * @param last1 End of range 1. 00163 * @param first2 Start of range 2. 00164 * @param init Starting value to add other values to. 00165 * @return The final inner product. 00166 */ 00167 template<typename _InputIterator1, typename _InputIterator2, typename _Tp> 00168 inline _Tp 00169 inner_product(_InputIterator1 __first1, _InputIterator1 __last1, 00170 _InputIterator2 __first2, _Tp __init) 00171 { 00172 // concept requirements 00173 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 00174 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 00175 __glibcxx_requires_valid_range(__first1, __last1); 00176 00177 for (; __first1 != __last1; ++__first1, ++__first2) 00178 __init = __init + (*__first1 * *__first2); 00179 return __init; 00180 } 00181 00182 /** 00183 * @brief Compute inner product of two ranges. 00184 * 00185 * Starting with an initial value of @a init, applies @a binary_op2 to 00186 * successive elements from the two ranges and accumulates each result into 00187 * the accumulated value using @a binary_op1. The values in the ranges are 00188 * processed in order. 00189 * 00190 * @param first1 Start of range 1. 00191 * @param last1 End of range 1. 00192 * @param first2 Start of range 2. 00193 * @param init Starting value to add other values to. 00194 * @param binary_op1 Function object to accumulate with. 00195 * @param binary_op2 Function object to apply to pairs of input values. 00196 * @return The final inner product. 00197 */ 00198 template<typename _InputIterator1, typename _InputIterator2, typename _Tp, 00199 typename _BinaryOperation1, typename _BinaryOperation2> 00200 inline _Tp 00201 inner_product(_InputIterator1 __first1, _InputIterator1 __last1, 00202 _InputIterator2 __first2, _Tp __init, 00203 _BinaryOperation1 __binary_op1, 00204 _BinaryOperation2 __binary_op2) 00205 { 00206 // concept requirements 00207 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 00208 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 00209 __glibcxx_requires_valid_range(__first1, __last1); 00210 00211 for (; __first1 != __last1; ++__first1, ++__first2) 00212 __init = __binary_op1(__init, __binary_op2(*__first1, *__first2)); 00213 return __init; 00214 } 00215 00216 /** 00217 * @brief Return list of partial sums 00218 * 00219 * Accumulates the values in the range [first,last) using operator+(). 00220 * As each successive input value is added into the total, that partial sum 00221 * is written to @a result. Therefore, the first value in result is the 00222 * first value of the input, the second value in result is the sum of the 00223 * first and second input values, and so on. 00224 * 00225 * @param first Start of input range. 00226 * @param last End of input range. 00227 * @param result Output to write sums to. 00228 * @return Iterator pointing just beyond the values written to result. 00229 */ 00230 template<typename _InputIterator, typename _OutputIterator> 00231 _OutputIterator 00232 partial_sum(_InputIterator __first, _InputIterator __last, 00233 _OutputIterator __result) 00234 { 00235 typedef typename iterator_traits<_InputIterator>::value_type _ValueType; 00236 00237 // concept requirements 00238 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 00239 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 00240 _ValueType>) 00241 __glibcxx_requires_valid_range(__first, __last); 00242 00243 if (__first == __last) 00244 return __result; 00245 _ValueType __value = *__first; 00246 *__result = __value; 00247 while (++__first != __last) 00248 { 00249 __value = __value + *__first; 00250 *++__result = __value; 00251 } 00252 return ++__result; 00253 } 00254 00255 /** 00256 * @brief Return list of partial sums 00257 * 00258 * Accumulates the values in the range [first,last) using operator+(). 00259 * As each successive input value is added into the total, that partial sum 00260 * is written to @a result. Therefore, the first value in result is the 00261 * first value of the input, the second value in result is the sum of the 00262 * first and second input values, and so on. 00263 * 00264 * @param first Start of input range. 00265 * @param last End of input range. 00266 * @param result Output to write sums to. 00267 * @return Iterator pointing just beyond the values written to result. 00268 */ 00269 template<typename _InputIterator, typename _OutputIterator, 00270 typename _BinaryOperation> 00271 _OutputIterator 00272 partial_sum(_InputIterator __first, _InputIterator __last, 00273 _OutputIterator __result, _BinaryOperation __binary_op) 00274 { 00275 typedef typename iterator_traits<_InputIterator>::value_type _ValueType; 00276 00277 // concept requirements 00278 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 00279 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 00280 _ValueType>) 00281 __glibcxx_requires_valid_range(__first, __last); 00282 00283 if (__first == __last) 00284 return __result; 00285 _ValueType __value = *__first; 00286 *__result = __value; 00287 while (++__first != __last) 00288 { 00289 __value = __binary_op(__value, *__first); 00290 *++__result = __value; 00291 } 00292 return ++__result; 00293 } 00294 00295 /** 00296 * @brief Return differences between adjacent values. 00297 * 00298 * Computes the difference between adjacent values in the range 00299 * [first,last) using operator-() and writes the result to @a result. 00300 * 00301 * @param first Start of input range. 00302 * @param last End of input range. 00303 * @param result Output to write sums to. 00304 * @return Iterator pointing just beyond the values written to result. 00305 */ 00306 template<typename _InputIterator, typename _OutputIterator> 00307 _OutputIterator 00308 adjacent_difference(_InputIterator __first, 00309 _InputIterator __last, _OutputIterator __result) 00310 { 00311 typedef typename iterator_traits<_InputIterator>::value_type _ValueType; 00312 00313 // concept requirements 00314 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 00315 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 00316 _ValueType>) 00317 __glibcxx_requires_valid_range(__first, __last); 00318 00319 if (__first == __last) 00320 return __result; 00321 _ValueType __value = *__first; 00322 *__result = __value; 00323 while (++__first != __last) 00324 { 00325 _ValueType __tmp = *__first; 00326 *++__result = __tmp - __value; 00327 __value = __tmp; 00328 } 00329 return ++__result; 00330 } 00331 00332 /** 00333 * @brief Return differences between adjacent values. 00334 * 00335 * Computes the difference between adjacent values in the range 00336 * [first,last) using the function object @a binary_op and writes the 00337 * result to @a result. 00338 * 00339 * @param first Start of input range. 00340 * @param last End of input range. 00341 * @param result Output to write sums to. 00342 * @return Iterator pointing just beyond the values written to result. 00343 */ 00344 template<typename _InputIterator, typename _OutputIterator, 00345 typename _BinaryOperation> 00346 _OutputIterator 00347 adjacent_difference(_InputIterator __first, _InputIterator __last, 00348 _OutputIterator __result, _BinaryOperation __binary_op) 00349 { 00350 typedef typename iterator_traits<_InputIterator>::value_type _ValueType; 00351 00352 // concept requirements 00353 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 00354 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 00355 _ValueType>) 00356 __glibcxx_requires_valid_range(__first, __last); 00357 00358 if (__first == __last) 00359 return __result; 00360 _ValueType __value = *__first; 00361 *__result = __value; 00362 while (++__first != __last) 00363 { 00364 _ValueType __tmp = *__first; 00365 *++__result = __binary_op(__tmp, __value); 00366 __value = __tmp; 00367 } 00368 return ++__result; 00369 } 00370 00371 _GLIBCXX_END_NESTED_NAMESPACE 00372 00373 #endif /* _STL_NUMERIC_H */