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 */ 374
