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