1// -*- C++ -*- 2//===---------------------------- numeric ---------------------------------===// 3// 4// The LLVM Compiler Infrastructure 5// 6// This file is dual licensed under the MIT and the University of Illinois Open 7// Source Licenses. See LICENSE.TXT for details. 8// 9//===----------------------------------------------------------------------===// 10 11#ifndef _LIBCPP_NUMERIC 12#define _LIBCPP_NUMERIC 13 14/* 15 numeric synopsis 16 17namespace std 18{ 19 20template <class InputIterator, class T> 21 T 22 accumulate(InputIterator first, InputIterator last, T init); 23 24template <class InputIterator, class T, class BinaryOperation> 25 T 26 accumulate(InputIterator first, InputIterator last, T init, BinaryOperation binary_op); 27 28template <class InputIterator1, class InputIterator2, class T> 29 T 30 inner_product(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, T init); 31 32template <class InputIterator1, class InputIterator2, class T, class BinaryOperation1, class BinaryOperation2> 33 T 34 inner_product(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, 35 T init, BinaryOperation1 binary_op1, BinaryOperation2 binary_op2); 36 37template <class InputIterator, class OutputIterator> 38 OutputIterator 39 partial_sum(InputIterator first, InputIterator last, OutputIterator result); 40 41template <class InputIterator, class OutputIterator, class BinaryOperation> 42 OutputIterator 43 partial_sum(InputIterator first, InputIterator last, OutputIterator result, BinaryOperation binary_op); 44 45template <class InputIterator, class OutputIterator> 46 OutputIterator 47 adjacent_difference(InputIterator first, InputIterator last, OutputIterator result); 48 49template <class InputIterator, class OutputIterator, class BinaryOperation> 50 OutputIterator 51 adjacent_difference(InputIterator first, InputIterator last, OutputIterator result, BinaryOperation binary_op); 52 53template <class ForwardIterator, class T> 54 void iota(ForwardIterator first, ForwardIterator last, T value); 55 56template <class M, class N> 57 constexpr common_type_t<M,N> gcd(M m, N n); // C++17 58 59template <class M, class N> 60 constexpr common_type_t<M,N> lcm(M m, N n); // C++17 61 62} // std 63 64*/ 65 66#include <__config> 67#include <iterator> 68#include <limits> // for numeric_limits 69 70#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 71#pragma GCC system_header 72#endif 73 74_LIBCPP_PUSH_MACROS 75#include <__undef_macros> 76 77_LIBCPP_BEGIN_NAMESPACE_STD 78 79template <class _InputIterator, class _Tp> 80inline _LIBCPP_INLINE_VISIBILITY 81_Tp 82accumulate(_InputIterator __first, _InputIterator __last, _Tp __init) 83{ 84 for (; __first != __last; ++__first) 85 __init = __init + *__first; 86 return __init; 87} 88 89template <class _InputIterator, class _Tp, class _BinaryOperation> 90inline _LIBCPP_INLINE_VISIBILITY 91_Tp 92accumulate(_InputIterator __first, _InputIterator __last, _Tp __init, _BinaryOperation __binary_op) 93{ 94 for (; __first != __last; ++__first) 95 __init = __binary_op(__init, *__first); 96 return __init; 97} 98 99template <class _InputIterator1, class _InputIterator2, class _Tp> 100inline _LIBCPP_INLINE_VISIBILITY 101_Tp 102inner_product(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _Tp __init) 103{ 104 for (; __first1 != __last1; ++__first1, (void) ++__first2) 105 __init = __init + *__first1 * *__first2; 106 return __init; 107} 108 109template <class _InputIterator1, class _InputIterator2, class _Tp, class _BinaryOperation1, class _BinaryOperation2> 110inline _LIBCPP_INLINE_VISIBILITY 111_Tp 112inner_product(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, 113 _Tp __init, _BinaryOperation1 __binary_op1, _BinaryOperation2 __binary_op2) 114{ 115 for (; __first1 != __last1; ++__first1, (void) ++__first2) 116 __init = __binary_op1(__init, __binary_op2(*__first1, *__first2)); 117 return __init; 118} 119 120template <class _InputIterator, class _OutputIterator> 121inline _LIBCPP_INLINE_VISIBILITY 122_OutputIterator 123partial_sum(_InputIterator __first, _InputIterator __last, _OutputIterator __result) 124{ 125 if (__first != __last) 126 { 127 typename iterator_traits<_InputIterator>::value_type __t(*__first); 128 *__result = __t; 129 for (++__first, (void) ++__result; __first != __last; ++__first, (void) ++__result) 130 { 131 __t = __t + *__first; 132 *__result = __t; 133 } 134 } 135 return __result; 136} 137 138template <class _InputIterator, class _OutputIterator, class _BinaryOperation> 139inline _LIBCPP_INLINE_VISIBILITY 140_OutputIterator 141partial_sum(_InputIterator __first, _InputIterator __last, _OutputIterator __result, 142 _BinaryOperation __binary_op) 143{ 144 if (__first != __last) 145 { 146 typename iterator_traits<_InputIterator>::value_type __t(*__first); 147 *__result = __t; 148 for (++__first, (void) ++__result; __first != __last; ++__first, (void) ++__result) 149 { 150 __t = __binary_op(__t, *__first); 151 *__result = __t; 152 } 153 } 154 return __result; 155} 156 157template <class _InputIterator, class _OutputIterator> 158inline _LIBCPP_INLINE_VISIBILITY 159_OutputIterator 160adjacent_difference(_InputIterator __first, _InputIterator __last, _OutputIterator __result) 161{ 162 if (__first != __last) 163 { 164 typename iterator_traits<_InputIterator>::value_type __t1(*__first); 165 *__result = __t1; 166 for (++__first, (void) ++__result; __first != __last; ++__first, (void) ++__result) 167 { 168 typename iterator_traits<_InputIterator>::value_type __t2(*__first); 169 *__result = __t2 - __t1; 170 __t1 = _VSTD::move(__t2); 171 } 172 } 173 return __result; 174} 175 176template <class _InputIterator, class _OutputIterator, class _BinaryOperation> 177inline _LIBCPP_INLINE_VISIBILITY 178_OutputIterator 179adjacent_difference(_InputIterator __first, _InputIterator __last, _OutputIterator __result, 180 _BinaryOperation __binary_op) 181{ 182 if (__first != __last) 183 { 184 typename iterator_traits<_InputIterator>::value_type __t1(*__first); 185 *__result = __t1; 186 for (++__first, (void) ++__result; __first != __last; ++__first, (void) ++__result) 187 { 188 typename iterator_traits<_InputIterator>::value_type __t2(*__first); 189 *__result = __binary_op(__t2, __t1); 190 __t1 = _VSTD::move(__t2); 191 } 192 } 193 return __result; 194} 195 196template <class _ForwardIterator, class _Tp> 197inline _LIBCPP_INLINE_VISIBILITY 198void 199iota(_ForwardIterator __first, _ForwardIterator __last, _Tp __value_) 200{ 201 for (; __first != __last; ++__first, (void) ++__value_) 202 *__first = __value_; 203} 204 205 206#if _LIBCPP_STD_VER > 14 207template <typename _Result, typename _Source, bool _IsSigned = is_signed<_Source>::value> struct __abs; 208 209template <typename _Result, typename _Source> 210struct __abs<_Result, _Source, true> { 211 _LIBCPP_CONSTEXPR _LIBCPP_INLINE_VISIBILITY 212 _Result operator()(_Source __t) const noexcept 213 { 214 if (__t >= 0) return __t; 215 if (__t == numeric_limits<_Source>::min()) return -static_cast<_Result>(__t); 216 return -__t; 217 } 218}; 219 220template <typename _Result, typename _Source> 221struct __abs<_Result, _Source, false> { 222 _LIBCPP_CONSTEXPR _LIBCPP_INLINE_VISIBILITY 223 _Result operator()(_Source __t) const noexcept { return __t; } 224}; 225 226 227template<class _Tp> 228_LIBCPP_CONSTEXPR _LIBCPP_HIDDEN 229_Tp __gcd(_Tp __m, _Tp __n) 230{ 231 static_assert((!is_signed<_Tp>::value), ""); 232 return __n == 0 ? __m : _VSTD::__gcd<_Tp>(__n, __m % __n); 233} 234 235 236template<class _Tp, class _Up> 237_LIBCPP_CONSTEXPR _LIBCPP_INLINE_VISIBILITY 238common_type_t<_Tp,_Up> 239gcd(_Tp __m, _Up __n) 240{ 241 static_assert((is_integral<_Tp>::value && is_integral<_Up>::value), "Arguments to gcd must be integer types"); 242 static_assert((!is_same<typename remove_cv<_Tp>::type, bool>::value), "First argument to gcd cannot be bool" ); 243 static_assert((!is_same<typename remove_cv<_Up>::type, bool>::value), "Second argument to gcd cannot be bool" ); 244 using _Rp = common_type_t<_Tp,_Up>; 245 using _Wp = make_unsigned_t<_Rp>; 246 return static_cast<_Rp>(_VSTD::__gcd( 247 static_cast<_Wp>(__abs<_Rp, _Tp>()(__m)), 248 static_cast<_Wp>(__abs<_Rp, _Up>()(__n)))); 249} 250 251template<class _Tp, class _Up> 252_LIBCPP_CONSTEXPR _LIBCPP_INLINE_VISIBILITY 253common_type_t<_Tp,_Up> 254lcm(_Tp __m, _Up __n) 255{ 256 static_assert((is_integral<_Tp>::value && is_integral<_Up>::value), "Arguments to lcm must be integer types"); 257 static_assert((!is_same<typename remove_cv<_Tp>::type, bool>::value), "First argument to lcm cannot be bool" ); 258 static_assert((!is_same<typename remove_cv<_Up>::type, bool>::value), "Second argument to lcm cannot be bool" ); 259 if (__m == 0 || __n == 0) 260 return 0; 261 262 using _Rp = common_type_t<_Tp,_Up>; 263 _Rp __val1 = __abs<_Rp, _Tp>()(__m) / _VSTD::gcd(__m, __n); 264 _Rp __val2 = __abs<_Rp, _Up>()(__n); 265 _LIBCPP_ASSERT((numeric_limits<_Rp>::max() / __val1 > __val2), "Overflow in lcm"); 266 return __val1 * __val2; 267} 268 269#endif /* _LIBCPP_STD_VER > 14 */ 270 271_LIBCPP_END_NAMESPACE_STD 272 273_LIBCPP_POP_MACROS 274 275#endif // _LIBCPP_NUMERIC 276