1 | // Numeric functions implementation -*- C++ -*- |
---|---|

2 | |

3 | // Copyright (C) 2001-2018 Free Software Foundation, Inc. |

4 | // |

5 | // This file is part of the GNU ISO C++ Library. This library is free |

6 | // software; you can redistribute it and/or modify it under the |

7 | // terms of the GNU General Public License as published by the |

8 | // Free Software Foundation; either version 3, or (at your option) |

9 | // any later version. |

10 | |

11 | // This library is distributed in the hope that it will be useful, |

12 | // but WITHOUT ANY WARRANTY; without even the implied warranty of |

13 | // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |

14 | // GNU General Public License for more details. |

15 | |

16 | // Under Section 7 of GPL version 3, you are granted additional |

17 | // permissions described in the GCC Runtime Library Exception, version |

18 | // 3.1, as published by the Free Software Foundation. |

19 | |

20 | // You should have received a copy of the GNU General Public License and |

21 | // a copy of the GCC Runtime Library Exception along with this program; |

22 | // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see |

23 | // <http://www.gnu.org/licenses/>. |

24 | |

25 | /* |

26 | * |

27 | * Copyright (c) 1994 |

28 | * Hewlett-Packard Company |

29 | * |

30 | * Permission to use, copy, modify, distribute and sell this software |

31 | * and its documentation for any purpose is hereby granted without fee, |

32 | * provided that the above copyright notice appear in all copies and |

33 | * that both that copyright notice and this permission notice appear |

34 | * in supporting documentation. Hewlett-Packard Company makes no |

35 | * representations about the suitability of this software for any |

36 | * purpose. It is provided "as is" without express or implied warranty. |

37 | * |

38 | * |

39 | * Copyright (c) 1996,1997 |

40 | * Silicon Graphics Computer Systems, Inc. |

41 | * |

42 | * Permission to use, copy, modify, distribute and sell this software |

43 | * and its documentation for any purpose is hereby granted without fee, |

44 | * provided that the above copyright notice appear in all copies and |

45 | * that both that copyright notice and this permission notice appear |

46 | * in supporting documentation. Silicon Graphics makes no |

47 | * representations about the suitability of this software for any |

48 | * purpose. It is provided "as is" without express or implied warranty. |

49 | */ |

50 | |

51 | /** @file bits/stl_numeric.h |

52 | * This is an internal header file, included by other library headers. |

53 | * Do not attempt to use it directly. @headername{numeric} |

54 | */ |

55 | |

56 | #ifndef _STL_NUMERIC_H |

57 | #define _STL_NUMERIC_H 1 |

58 | |

59 | #include <bits/concept_check.h> |

60 | #include <debug/debug.h> |

61 | #include <bits/move.h> // For _GLIBCXX_MOVE |

62 | |

63 | #if __cplusplus >= 201103L |

64 | |

65 | namespace std _GLIBCXX_VISIBILITY(default) |

66 | { |

67 | _GLIBCXX_BEGIN_NAMESPACE_VERSION |

68 | |

69 | /** |

70 | * @brief Create a range of sequentially increasing values. |

71 | * |

72 | * For each element in the range @p [first,last) assigns @p value and |

73 | * increments @p value as if by @p ++value. |

74 | * |

75 | * @param __first Start of range. |

76 | * @param __last End of range. |

77 | * @param __value Starting value. |

78 | * @return Nothing. |

79 | */ |

80 | template<typename _ForwardIterator, typename _Tp> |

81 | void |

82 | iota(_ForwardIterator __first, _ForwardIterator __last, _Tp __value) |

83 | { |

84 | // concept requirements |

85 | __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< |

86 | _ForwardIterator>) |

87 | __glibcxx_function_requires(_ConvertibleConcept<_Tp, |

88 | typename iterator_traits<_ForwardIterator>::value_type>) |

89 | __glibcxx_requires_valid_range(__first, __last); |

90 | |

91 | for (; __first != __last; ++__first) |

92 | { |

93 | *__first = __value; |

94 | ++__value; |

95 | } |

96 | } |

97 | |

98 | _GLIBCXX_END_NAMESPACE_VERSION |

99 | } // namespace std |

100 | |

101 | #endif |

102 | |

103 | namespace std _GLIBCXX_VISIBILITY(default) |

104 | { |

105 | _GLIBCXX_BEGIN_NAMESPACE_ALGO |

106 | |

107 | /** |

108 | * @brief Accumulate values in a range. |

109 | * |

110 | * Accumulates the values in the range [first,last) using operator+(). The |

111 | * initial value is @a init. The values are processed in order. |

112 | * |

113 | * @param __first Start of range. |

114 | * @param __last End of range. |

115 | * @param __init Starting value to add other values to. |

116 | * @return The final sum. |

117 | */ |

118 | template<typename _InputIterator, typename _Tp> |

119 | inline _Tp |

120 | accumulate(_InputIterator __first, _InputIterator __last, _Tp __init) |

121 | { |

122 | // concept requirements |

123 | __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) |

124 | __glibcxx_requires_valid_range(__first, __last); |

125 | |

126 | for (; __first != __last; ++__first) |

127 | __init = __init + *__first; |

128 | return __init; |

129 | } |

130 | |

131 | /** |

132 | * @brief Accumulate values in a range with operation. |

133 | * |

134 | * Accumulates the values in the range [first,last) using the function |

135 | * object @p __binary_op. The initial value is @p __init. The values are |

136 | * processed in order. |

137 | * |

138 | * @param __first Start of range. |

139 | * @param __last End of range. |

140 | * @param __init Starting value to add other values to. |

141 | * @param __binary_op Function object to accumulate with. |

142 | * @return The final sum. |

143 | */ |

144 | template<typename _InputIterator, typename _Tp, typename _BinaryOperation> |

145 | inline _Tp |

146 | accumulate(_InputIterator __first, _InputIterator __last, _Tp __init, |

147 | _BinaryOperation __binary_op) |

148 | { |

149 | // concept requirements |

150 | __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) |

151 | __glibcxx_requires_valid_range(__first, __last); |

152 | |

153 | for (; __first != __last; ++__first) |

154 | __init = __binary_op(__init, *__first); |

155 | return __init; |

156 | } |

157 | |

158 | /** |

159 | * @brief Compute inner product of two ranges. |

160 | * |

161 | * Starting with an initial value of @p __init, multiplies successive |

162 | * elements from the two ranges and adds each product into the accumulated |

163 | * value using operator+(). The values in the ranges are processed in |

164 | * order. |

165 | * |

166 | * @param __first1 Start of range 1. |

167 | * @param __last1 End of range 1. |

168 | * @param __first2 Start of range 2. |

169 | * @param __init Starting value to add other values to. |

170 | * @return The final inner product. |

171 | */ |

172 | template<typename _InputIterator1, typename _InputIterator2, typename _Tp> |

173 | inline _Tp |

174 | inner_product(_InputIterator1 __first1, _InputIterator1 __last1, |

175 | _InputIterator2 __first2, _Tp __init) |

176 | { |

177 | // concept requirements |

178 | __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) |

179 | __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) |

180 | __glibcxx_requires_valid_range(__first1, __last1); |

181 | |

182 | for (; __first1 != __last1; ++__first1, (void)++__first2) |

183 | __init = __init + (*__first1 * *__first2); |

184 | return __init; |

185 | } |

186 | |

187 | /** |

188 | * @brief Compute inner product of two ranges. |

189 | * |

190 | * Starting with an initial value of @p __init, applies @p __binary_op2 to |

191 | * successive elements from the two ranges and accumulates each result into |

192 | * the accumulated value using @p __binary_op1. The values in the ranges are |

193 | * processed in order. |

194 | * |

195 | * @param __first1 Start of range 1. |

196 | * @param __last1 End of range 1. |

197 | * @param __first2 Start of range 2. |

198 | * @param __init Starting value to add other values to. |

199 | * @param __binary_op1 Function object to accumulate with. |

200 | * @param __binary_op2 Function object to apply to pairs of input values. |

201 | * @return The final inner product. |

202 | */ |

203 | template<typename _InputIterator1, typename _InputIterator2, typename _Tp, |

204 | typename _BinaryOperation1, typename _BinaryOperation2> |

205 | inline _Tp |

206 | inner_product(_InputIterator1 __first1, _InputIterator1 __last1, |

207 | _InputIterator2 __first2, _Tp __init, |

208 | _BinaryOperation1 __binary_op1, |

209 | _BinaryOperation2 __binary_op2) |

210 | { |

211 | // concept requirements |

212 | __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) |

213 | __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) |

214 | __glibcxx_requires_valid_range(__first1, __last1); |

215 | |

216 | for (; __first1 != __last1; ++__first1, (void)++__first2) |

217 | __init = __binary_op1(__init, __binary_op2(*__first1, *__first2)); |

218 | return __init; |

219 | } |

220 | |

221 | /** |

222 | * @brief Return list of partial sums |

223 | * |

224 | * Accumulates the values in the range [first,last) using the @c + operator. |

225 | * As each successive input value is added into the total, that partial sum |

226 | * is written to @p __result. Therefore, the first value in @p __result is |

227 | * the first value of the input, the second value in @p __result is the sum |

228 | * of the first and second input values, and so on. |

229 | * |

230 | * @param __first Start of input range. |

231 | * @param __last End of input range. |

232 | * @param __result Output sum. |

233 | * @return Iterator pointing just beyond the values written to __result. |

234 | */ |

235 | template<typename _InputIterator, typename _OutputIterator> |

236 | _OutputIterator |

237 | partial_sum(_InputIterator __first, _InputIterator __last, |

238 | _OutputIterator __result) |

239 | { |

240 | typedef typename iterator_traits<_InputIterator>::value_type _ValueType; |

241 | |

242 | // concept requirements |

243 | __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) |

244 | __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, |

245 | _ValueType>) |

246 | __glibcxx_requires_valid_range(__first, __last); |

247 | |

248 | if (__first == __last) |

249 | return __result; |

250 | _ValueType __value = *__first; |

251 | *__result = __value; |

252 | while (++__first != __last) |

253 | { |

254 | __value = __value + *__first; |

255 | *++__result = __value; |

256 | } |

257 | return ++__result; |

258 | } |

259 | |

260 | /** |

261 | * @brief Return list of partial sums |

262 | * |

263 | * Accumulates the values in the range [first,last) using @p __binary_op. |

264 | * As each successive input value is added into the total, that partial sum |

265 | * is written to @p __result. Therefore, the first value in @p __result is |

266 | * the first value of the input, the second value in @p __result is the sum |

267 | * of the first and second input values, and so on. |

268 | * |

269 | * @param __first Start of input range. |

270 | * @param __last End of input range. |

271 | * @param __result Output sum. |

272 | * @param __binary_op Function object. |

273 | * @return Iterator pointing just beyond the values written to __result. |

274 | */ |

275 | template<typename _InputIterator, typename _OutputIterator, |

276 | typename _BinaryOperation> |

277 | _OutputIterator |

278 | partial_sum(_InputIterator __first, _InputIterator __last, |

279 | _OutputIterator __result, _BinaryOperation __binary_op) |

280 | { |

281 | typedef typename iterator_traits<_InputIterator>::value_type _ValueType; |

282 | |

283 | // concept requirements |

284 | __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) |

285 | __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, |

286 | _ValueType>) |

287 | __glibcxx_requires_valid_range(__first, __last); |

288 | |

289 | if (__first == __last) |

290 | return __result; |

291 | _ValueType __value = *__first; |

292 | *__result = __value; |

293 | while (++__first != __last) |

294 | { |

295 | __value = __binary_op(__value, *__first); |

296 | *++__result = __value; |

297 | } |

298 | return ++__result; |

299 | } |

300 | |

301 | /** |

302 | * @brief Return differences between adjacent values. |

303 | * |

304 | * Computes the difference between adjacent values in the range |

305 | * [first,last) using operator-() and writes the result to @p __result. |

306 | * |

307 | * @param __first Start of input range. |

308 | * @param __last End of input range. |

309 | * @param __result Output sums. |

310 | * @return Iterator pointing just beyond the values written to result. |

311 | * |

312 | * _GLIBCXX_RESOLVE_LIB_DEFECTS |

313 | * DR 539. partial_sum and adjacent_difference should mention requirements |

314 | */ |

315 | template<typename _InputIterator, typename _OutputIterator> |

316 | _OutputIterator |

317 | adjacent_difference(_InputIterator __first, |

318 | _InputIterator __last, _OutputIterator __result) |

319 | { |

320 | typedef typename iterator_traits<_InputIterator>::value_type _ValueType; |

321 | |

322 | // concept requirements |

323 | __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) |

324 | __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, |

325 | _ValueType>) |

326 | __glibcxx_requires_valid_range(__first, __last); |

327 | |

328 | if (__first == __last) |

329 | return __result; |

330 | _ValueType __value = *__first; |

331 | *__result = __value; |

332 | while (++__first != __last) |

333 | { |

334 | _ValueType __tmp = *__first; |

335 | *++__result = __tmp - __value; |

336 | __value = _GLIBCXX_MOVE(__tmp); |

337 | } |

338 | return ++__result; |

339 | } |

340 | |

341 | /** |

342 | * @brief Return differences between adjacent values. |

343 | * |

344 | * Computes the difference between adjacent values in the range |

345 | * [__first,__last) using the function object @p __binary_op and writes the |

346 | * result to @p __result. |

347 | * |

348 | * @param __first Start of input range. |

349 | * @param __last End of input range. |

350 | * @param __result Output sum. |

351 | * @param __binary_op Function object. |

352 | * @return Iterator pointing just beyond the values written to result. |

353 | * |

354 | * _GLIBCXX_RESOLVE_LIB_DEFECTS |

355 | * DR 539. partial_sum and adjacent_difference should mention requirements |

356 | */ |

357 | template<typename _InputIterator, typename _OutputIterator, |

358 | typename _BinaryOperation> |

359 | _OutputIterator |

360 | adjacent_difference(_InputIterator __first, _InputIterator __last, |

361 | _OutputIterator __result, _BinaryOperation __binary_op) |

362 | { |

363 | typedef typename iterator_traits<_InputIterator>::value_type _ValueType; |

364 | |

365 | // concept requirements |

366 | __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) |

367 | __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, |

368 | _ValueType>) |

369 | __glibcxx_requires_valid_range(__first, __last); |

370 | |

371 | if (__first == __last) |

372 | return __result; |

373 | _ValueType __value = *__first; |

374 | *__result = __value; |

375 | while (++__first != __last) |

376 | { |

377 | _ValueType __tmp = *__first; |

378 | *++__result = __binary_op(__tmp, __value); |

379 | __value = _GLIBCXX_MOVE(__tmp); |

380 | } |

381 | return ++__result; |

382 | } |

383 | |

384 | _GLIBCXX_END_NAMESPACE_ALGO |

385 | } // namespace std |

386 | |

387 | #endif /* _STL_NUMERIC_H */ |

388 |