Index: include/numeric =================================================================== --- include/numeric +++ include/numeric @@ -25,6 +25,18 @@ T accumulate(InputIterator first, InputIterator last, T init, BinaryOperation binary_op); +template + typename iterator_traits::value_type + reduce(InputIterator first, InputIterator last); // C++17 + +template + T + reduce(InputIterator first, InputIterator last, T init); // C++17 + +template + T + reduce(InputIterator first, InputIterator last, T init, BinaryOperation binary_op); // C++17 + template T inner_product(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, T init); @@ -34,6 +46,23 @@ inner_product(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, T init, BinaryOperation1 binary_op1, BinaryOperation2 binary_op2); + +template + T + transform_reduce(InputIterator1 first1, InputIterator1 last1, + InputIterator2 first2, T init); // C++17 + +template + T + transform_reduce(InputIterator1 first1, InputIterator1 last1, + InputIterator2 first2, T init, + BinaryOperation1 binary_op1, BinaryOperation2 binary_op2); // C++17 + +template + T + transform_reduce(InputIterator first, InputIterator last, T init, + BinaryOperation binary_op, UnaryOperation unary_op); // C++17 + template OutputIterator partial_sum(InputIterator first, InputIterator last, OutputIterator result); @@ -114,6 +143,35 @@ return __init; } +#if _LIBCPP_STD_VER > 14 +template +inline _LIBCPP_INLINE_VISIBILITY +_Tp +reduce(_InputIterator __first, _InputIterator __last, _Tp __init, _BinaryOp __b) +{ + for (; __first != __last; ++__first) + __init = __b(__init, *__first); + return __init; +} + +template +inline _LIBCPP_INLINE_VISIBILITY +_Tp +reduce(_InputIterator __first, _InputIterator __last, _Tp __init) +{ + return _VSTD::reduce(__first, __last, __init, _VSTD::plus<>()); +} + +template +inline _LIBCPP_INLINE_VISIBILITY +typename iterator_traits<_InputIterator>::value_type +reduce(_InputIterator __first, _InputIterator __last) +{ + return _VSTD::reduce(__first, __last, + typename iterator_traits<_InputIterator>::value_type{}); +} +#endif + template inline _LIBCPP_INLINE_VISIBILITY _Tp @@ -135,6 +193,41 @@ return __init; } +#if _LIBCPP_STD_VER > 14 +template +inline _LIBCPP_INLINE_VISIBILITY +_Tp +transform_reduce(_InputIterator __first, _InputIterator __last, + _Tp __init, _BinaryOp __b, _UnaryOp __u) +{ + for (; __first != __last; ++__first) + __init = __b(__init, __u(*__first)); + return __init; +} + +template +inline _LIBCPP_INLINE_VISIBILITY +_Tp +transform_reduce(_InputIterator1 __first1, _InputIterator1 __last1, + _InputIterator2 __first2, _Tp __init, _BinaryOp1 __b1, _BinaryOp2 __b2) +{ + for (; __first1 != __last1; ++__first1, (void) ++__first2) + __init = __b1(__init, __b2(*__first1, *__first2)); + return __init; +} + +template +inline _LIBCPP_INLINE_VISIBILITY +_Tp +transform_reduce(_InputIterator1 __first1, _InputIterator1 __last1, + _InputIterator2 __first2, _Tp __init) +{ + return _VSTD::transform_reduce(__first1, __last1, __first2, __init, + _VSTD::plus<>(), _VSTD::multiplies<>()); +} +#endif + template inline _LIBCPP_INLINE_VISIBILITY _OutputIterator Index: test/std/numerics/numeric.ops/reduce/reduce_iter_iter.pass.cpp =================================================================== --- test/std/numerics/numeric.ops/reduce/reduce_iter_iter.pass.cpp +++ test/std/numerics/numeric.ops/reduce/reduce_iter_iter.pass.cpp @@ -0,0 +1,63 @@ +//===----------------------------------------------------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is dual licensed under the MIT and the University of Illinois Open +// Source Licenses. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +// +// UNSUPPORTED: c++98, c++03, c++11, c++14 + +// template +// typename iterator_traits::value_type +// reduce(InputIterator first, InputIterator last); + +#include +#include + +#include "test_iterators.h" + +template +void +test(Iter first, Iter last, T x) +{ + static_assert( std::is_same_v::value_type, + decltype(std::reduce(first, last))> ); + assert(std::reduce(first, last) == x); +} + +template +void +test() +{ + int ia[] = {1, 2, 3, 4, 5, 6}; + unsigned sa = sizeof(ia) / sizeof(ia[0]); + test(Iter(ia), Iter(ia), 0); + test(Iter(ia), Iter(ia+1), 1); + test(Iter(ia), Iter(ia+2), 3); + test(Iter(ia), Iter(ia+sa), 21); +} + +template +void test_return_type() +{ + T *p = nullptr; + static_assert( std::is_same_v ); +} + +int main() +{ + test_return_type(); + test_return_type(); + test_return_type(); + test_return_type(); + test_return_type(); + + test >(); + test >(); + test >(); + test >(); + test(); +} Index: test/std/numerics/numeric.ops/reduce/reduce_iter_iter_T.pass.cpp =================================================================== --- test/std/numerics/numeric.ops/reduce/reduce_iter_iter_T.pass.cpp +++ test/std/numerics/numeric.ops/reduce/reduce_iter_iter_T.pass.cpp @@ -0,0 +1,67 @@ +//===----------------------------------------------------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is dual licensed under the MIT and the University of Illinois Open +// Source Licenses. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +// +// UNSUPPORTED: c++98, c++03, c++11, c++14 + +// template +// T reduce(InputIterator first, InputIterator last, T init); + +#include +#include + +#include "test_iterators.h" + +template +void +test(Iter first, Iter last, T init, T x) +{ + static_assert( std::is_same_v ); + assert(std::reduce(first, last, init) == x); +} + +template +void +test() +{ + int ia[] = {1, 2, 3, 4, 5, 6}; + unsigned sa = sizeof(ia) / sizeof(ia[0]); + test(Iter(ia), Iter(ia), 0, 0); + test(Iter(ia), Iter(ia), 1, 1); + test(Iter(ia), Iter(ia+1), 0, 1); + test(Iter(ia), Iter(ia+1), 2, 3); + test(Iter(ia), Iter(ia+2), 0, 3); + test(Iter(ia), Iter(ia+2), 3, 6); + test(Iter(ia), Iter(ia+sa), 0, 21); + test(Iter(ia), Iter(ia+sa), 4, 25); +} + +template +void test_return_type() +{ + T *p = nullptr; + static_assert( std::is_same_v ); +} + +int main() +{ + test_return_type(); + test_return_type(); + test_return_type(); + test_return_type(); + test_return_type(); + test_return_type(); + test_return_type(); + + test >(); + test >(); + test >(); + test >(); + test(); +} Index: test/std/numerics/numeric.ops/reduce/reduce_iter_iter_T_op.pass.cpp =================================================================== --- test/std/numerics/numeric.ops/reduce/reduce_iter_iter_T_op.pass.cpp +++ test/std/numerics/numeric.ops/reduce/reduce_iter_iter_T_op.pass.cpp @@ -0,0 +1,74 @@ +//===----------------------------------------------------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is dual licensed under the MIT and the University of Illinois Open +// Source Licenses. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +// +// UNSUPPORTED: c++98, c++03, c++11, c++14 + +// template +// T reduce(InputIterator first, InputIterator last, T init, BinaryOperation op); + +#include +#include + +#include "test_iterators.h" + +template +void +test(Iter first, Iter last, T init, Op op, T x) +{ + static_assert( std::is_same_v, "" ); + assert(std::reduce(first, last, init, op) == x); +} + +template +void +test() +{ + int ia[] = {1, 2, 3, 4, 5, 6}; + unsigned sa = sizeof(ia) / sizeof(ia[0]); + test(Iter(ia), Iter(ia), 0, std::plus<>(), 0); + test(Iter(ia), Iter(ia), 1, std::multiplies<>(), 1); + test(Iter(ia), Iter(ia+1), 0, std::plus<>(), 1); + test(Iter(ia), Iter(ia+1), 2, std::multiplies<>(), 2); + test(Iter(ia), Iter(ia+2), 0, std::plus<>(), 3); + test(Iter(ia), Iter(ia+2), 3, std::multiplies<>(), 6); + test(Iter(ia), Iter(ia+sa), 0, std::plus<>(), 21); + test(Iter(ia), Iter(ia+sa), 4, std::multiplies<>(), 2880); +} + +template +void test_return_type() +{ + T *p = nullptr; + static_assert( std::is_same_v()))>, "" ); +} + +int main() +{ + test_return_type(); + test_return_type(); + test_return_type(); + test_return_type(); + test_return_type(); + test_return_type(); + test_return_type(); + + test >(); + test >(); + test >(); + test >(); + test(); + +// Make sure the math is done using the correct type + { + auto v = {1, 2, 3, 4, 5, 6, 7, 8}; + unsigned res = std::reduce(v.begin(), v.end(), 1U, std::multiplies<>()); + assert(res == 40320); // 8! will not fit into a char + } +} Index: test/std/numerics/numeric.ops/transform.reduce/transform_reduce_iter_iter_init_bop_uop.pass.cpp =================================================================== --- test/std/numerics/numeric.ops/transform.reduce/transform_reduce_iter_iter_init_bop_uop.pass.cpp +++ test/std/numerics/numeric.ops/transform.reduce/transform_reduce_iter_iter_init_bop_uop.pass.cpp @@ -0,0 +1,124 @@ +//===----------------------------------------------------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is dual licensed under the MIT and the University of Illinois Open +// Source Licenses. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +// +// UNSUPPORTED: c++98, c++03, c++11, c++14 + +// template +// T transform_reduce(InputIterator1 first1, InputIterator1 last1, +// T init, BinaryOperation binary_op, UnaryOperation unary_op); +// + +#include +#include + +#include "test_iterators.h" + +template +struct identity : std::unary_function<_Tp, _Tp> +{ + constexpr const _Tp& operator()(const _Tp& __x) const { return __x;} +}; + +template <> +struct identity +{ + template + constexpr auto operator()(_Tp&& __x) const + _NOEXCEPT_(noexcept(_VSTD::forward<_Tp>(__x))) + -> decltype (_VSTD::forward<_Tp>(__x)) + { return _VSTD::forward<_Tp>(__x); } +}; + + +template +struct twice +{ + constexpr const _Tp operator()(const _Tp& __x) const noexcept { return 2 * __x; } +}; + +template <> +struct twice +{ + template + constexpr auto operator()(const _Tp& __x) const + _NOEXCEPT_(noexcept(2 * __x)) + -> decltype (2 * __x) + { return 2 * __x; } +}; + +template +void +test(Iter1 first1, Iter1 last1, T init, BOp bOp, UOp uOp, T x) +{ + static_assert( std::is_same_v ); + assert(std::transform_reduce(first1, last1, init, bOp, uOp) == x); +} + +template +void +test() +{ + int ia[] = {1, 2, 3, 4, 5, 6}; + unsigned sa = sizeof(ia) / sizeof(ia[0]); + + test(Iter(ia), Iter(ia), 0, std::plus<>(), identity<>(), 0); + test(Iter(ia), Iter(ia), 1, std::multiplies<>(), identity<>(), 1); + test(Iter(ia), Iter(ia+1), 0, std::multiplies<>(), identity<>(), 0); + test(Iter(ia), Iter(ia+1), 2, std::plus<>(), identity<>(), 3); + test(Iter(ia), Iter(ia+2), 0, std::plus<>(), identity<>(), 3); + test(Iter(ia), Iter(ia+2), 3, std::multiplies<>(), identity<>(), 6); + test(Iter(ia), Iter(ia+sa), 4, std::multiplies<>(), identity<>(), 2880); + test(Iter(ia), Iter(ia+sa), 4, std::plus<>(), identity<>(), 25); + + test(Iter(ia), Iter(ia), 0, std::plus<>(), twice<>(), 0); + test(Iter(ia), Iter(ia), 1, std::multiplies<>(), twice<>(), 1); + test(Iter(ia), Iter(ia+1), 0, std::multiplies<>(), twice<>(), 0); + test(Iter(ia), Iter(ia+1), 2, std::plus<>(), twice<>(), 4); + test(Iter(ia), Iter(ia+2), 0, std::plus<>(), twice<>(), 6); + test(Iter(ia), Iter(ia+2), 3, std::multiplies<>(), twice<>(), 24); + test(Iter(ia), Iter(ia+sa), 4, std::multiplies<>(), twice<>(), 184320); // 64 * 2880 + test(Iter(ia), Iter(ia+sa), 4, std::plus<>(), twice<>(), 46); +} + +template +void test_return_type() +{ + T *p = nullptr; + static_assert( std::is_same_v(), identity<>()))> ); +} + +int main() +{ + test_return_type(); + test_return_type(); + test_return_type(); + test_return_type(); + test_return_type(); + test_return_type(); + test_return_type(); + +// All the iterator categories + test >(); + test >(); + test >(); + test >(); + test(); + test< int*>(); + +// Make sure the math is done using the correct type + { + auto v = {1, 2, 3, 4, 5, 6}; + unsigned res = std::transform_reduce(v.begin(), v.end(), 1U, std::multiplies<>(), twice<>()); + assert(res == 46080); // 6! * 64 will not fit into a char + } +} Index: test/std/numerics/numeric.ops/transform.reduce/transform_reduce_iter_iter_iter_init.pass.cpp =================================================================== --- test/std/numerics/numeric.ops/transform.reduce/transform_reduce_iter_iter_iter_init.pass.cpp +++ test/std/numerics/numeric.ops/transform.reduce/transform_reduce_iter_iter_iter_init.pass.cpp @@ -0,0 +1,95 @@ +//===----------------------------------------------------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is dual licensed under the MIT and the University of Illinois Open +// Source Licenses. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +// +// UNSUPPORTED: c++98, c++03, c++11, c++14 + +// template +// T transform_reduce(InputIterator1 first1, InputIterator1 last1, +// InputIterator2 first2, T init); + + +#include +#include + +#include "test_iterators.h" + +template +void +test(Iter1 first1, Iter1 last1, Iter2 first2, T init, T x) +{ + static_assert( std::is_same_v ); + assert(std::transform_reduce(first1, last1, first2, init) == x); +} + +template +void +test() +{ + int ia[] = {1, 2, 3, 4, 5, 6}; + unsigned int ua[] = {2, 4, 6, 8, 10,12}; + unsigned sa = sizeof(ia) / sizeof(ia[0]); + assert(sa == sizeof(ua) / sizeof(ua[0])); // just to be sure + + test(SIter(ia), SIter(ia), UIter(ua), 0, 0); + test(UIter(ua), UIter(ua), SIter(ia), 1, 1); + test(SIter(ia), SIter(ia+1), UIter(ua), 0, 2); + test(UIter(ua), UIter(ua+1), SIter(ia), 2, 4); + test(SIter(ia), SIter(ia+2), UIter(ua), 0, 10); + test(UIter(ua), UIter(ua+2), SIter(ia), 3, 13); + test(SIter(ia), SIter(ia+sa), UIter(ua), 0, 182); + test(UIter(ua), UIter(ua+sa), SIter(ia), 4, 186); +} + +template +void test_return_type() +{ + T *p = nullptr; + static_assert( std::is_same_v ); +} + +int main() +{ + test_return_type(); + test_return_type(); + test_return_type(); + test_return_type(); + test_return_type(); + test_return_type(); + test_return_type(); + +// All the iterator categories + test, input_iterator >(); + test, forward_iterator >(); + test, bidirectional_iterator >(); + test, random_access_iterator >(); + + test, input_iterator >(); + test, forward_iterator >(); + test, bidirectional_iterator >(); + test, random_access_iterator >(); + + test, input_iterator >(); + test, forward_iterator >(); + test, bidirectional_iterator >(); + test, random_access_iterator >(); + + test, input_iterator >(); + test, forward_iterator >(); + test, bidirectional_iterator >(); + test, random_access_iterator >(); + +// just plain pointers (const vs. non-const, too) + test(); + test(); + test< int*, const unsigned int *>(); + test< int*, unsigned int *>(); +} Index: test/std/numerics/numeric.ops/transform.reduce/transform_reduce_iter_iter_iter_init_op_op.pass.cpp =================================================================== --- test/std/numerics/numeric.ops/transform.reduce/transform_reduce_iter_iter_iter_init_op_op.pass.cpp +++ test/std/numerics/numeric.ops/transform.reduce/transform_reduce_iter_iter_iter_init_op_op.pass.cpp @@ -0,0 +1,97 @@ +//===----------------------------------------------------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is dual licensed under the MIT and the University of Illinois Open +// Source Licenses. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +// +// UNSUPPORTED: c++98, c++03, c++11, c++14 + +// template +// T transform_reduce(InputIterator1 first1, InputIterator1 last1, +// InputIterator2 first2, T init, +// BinaryOperation1 binary_op1, BinaryOperation2 binary_op2); +// + +#include +#include + +#include "test_iterators.h" + +template +void +test(Iter1 first1, Iter1 last1, Iter2 first2, T init, Op1 op1, Op2 op2, T x) +{ + static_assert( std::is_same_v ); + assert(std::transform_reduce(first1, last1, first2, init, op1, op2) == x); +} + +template +void +test() +{ + int ia[] = {1, 2, 3, 4, 5, 6}; + unsigned int ua[] = {2, 4, 6, 8, 10,12}; + unsigned sa = sizeof(ia) / sizeof(ia[0]); + assert(sa == sizeof(ua) / sizeof(ua[0])); // just to be sure + + test(SIter(ia), SIter(ia), UIter(ua), 0, std::plus<>(), std::multiplies<>(), 0); + test(UIter(ua), UIter(ua), SIter(ia), 1, std::multiplies<>(), std::plus<>(), 1); + test(SIter(ia), SIter(ia+1), UIter(ua), 0, std::multiplies<>(), std::plus<>(), 0); + test(UIter(ua), UIter(ua+1), SIter(ia), 2, std::plus<>(), std::multiplies<>(), 4); + test(SIter(ia), SIter(ia+2), UIter(ua), 0, std::plus<>(), std::multiplies<>(), 10); + test(UIter(ua), UIter(ua+2), SIter(ia), 3, std::multiplies<>(), std::plus<>(), 54); + test(SIter(ia), SIter(ia+sa), UIter(ua), 4, std::multiplies<>(), std::plus<>(), 2099520); + test(UIter(ua), UIter(ua+sa), SIter(ia), 4, std::plus<>(), std::multiplies<>(), 186); +} + +template +void test_return_type() +{ + T *p = nullptr; + static_assert( std::is_same_v(), std::multiplies<>()))> ); +} + +int main() +{ + test_return_type(); + test_return_type(); + test_return_type(); + test_return_type(); + test_return_type(); + test_return_type(); + test_return_type(); + +// All the iterator categories + test, input_iterator >(); + test, forward_iterator >(); + test, bidirectional_iterator >(); + test, random_access_iterator >(); + + test, input_iterator >(); + test, forward_iterator >(); + test, bidirectional_iterator >(); + test, random_access_iterator >(); + + test, input_iterator >(); + test, forward_iterator >(); + test, bidirectional_iterator >(); + test, random_access_iterator >(); + + test, input_iterator >(); + test, forward_iterator >(); + test, bidirectional_iterator >(); + test, random_access_iterator >(); + +// just plain pointers (const vs. non-const, too) + test(); + test(); + test< int*, const unsigned int *>(); + test< int*, unsigned int *>(); +}