Index: include/numeric =================================================================== --- include/numeric +++ include/numeric @@ -42,6 +42,23 @@ OutputIterator partial_sum(InputIterator first, InputIterator last, OutputIterator result, BinaryOperation binary_op); +template + OutputIterator + exclusive_scan(InputIterator first, InputIterator last, + OutputIterator result, T init); // C++17 + +template + OutputIterator + exclusive_scan(InputIterator first, InputIterator last, + OutputIterator result, T init, BinaryOperation binary_op); // C++17 + +template + OutputIterator + transform_exclusive_scan(InputIterator first, InputIterator last, + OutputIterator result, T init, + BinaryOperation binary_op, UnaryOperation unary_op); // C++17 + template OutputIterator adjacent_difference(InputIterator first, InputIterator last, OutputIterator result); @@ -66,6 +83,7 @@ #include <__config> #include #include // for numeric_limits +#include #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) #pragma GCC system_header @@ -154,6 +172,59 @@ return __result; } +#if _LIBCPP_STD_VER > 14 +template +inline _LIBCPP_INLINE_VISIBILITY +_OutputIterator +exclusive_scan(_InputIterator __first, _InputIterator __last, + _OutputIterator __result, _Tp __init, _BinaryOp __b) +{ + if (__first != __last) + { + _Tp __saved = __init; + do + { + __init = __b(__init, *__first); + *__result = __saved; + __saved = __init; + ++__result; + } while (++__first != __last); + } + return __result; +} + +template +inline _LIBCPP_INLINE_VISIBILITY +_OutputIterator +exclusive_scan(_InputIterator __first, _InputIterator __last, + _OutputIterator __result, _Tp __init) +{ + return _VSTD::exclusive_scan(__first, __last, __result, __init, _VSTD::plus<>()); +} + +template +inline _LIBCPP_INLINE_VISIBILITY +_OutputIterator +transform_exclusive_scan(_InputIterator __first, _InputIterator __last, + _OutputIterator __result, _Tp __init, + _BinaryOp __b, _UnaryOp __u) +{ + if (__first != __last) + { + _Tp __saved = __init; + do + { + __init = __b(__init, __u(*__first)); + *__result = __saved; + __saved = __init; + ++__result; + } while (++__first != __last); + } + return __result; +} +#endif + template inline _LIBCPP_INLINE_VISIBILITY _OutputIterator Index: test/std/numerics/numeric.ops/exclusive.scan/exclusive_scan_iter_iter_iter.pass.cpp =================================================================== --- test/std/numerics/numeric.ops/exclusive.scan/exclusive_scan_iter_iter_iter.pass.cpp +++ test/std/numerics/numeric.ops/exclusive.scan/exclusive_scan_iter_iter_iter.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 +// OutputIterator exclusive_scan(InputIterator first, InputIterator last, +// OutputIterator result, T init); +// + +#include +#include +#include + +#include "test_iterators.h" + +template +void +test(Iter1 first, Iter1 last, T init, Iter2 rFirst, Iter2 rLast) +{ + std::vector::value_type> v; + +// Not in place + std::exclusive_scan(first, last, std::back_inserter(v), init); + assert(std::equal(v.begin(), v.end(), rFirst, rLast)); + +// In place + v.clear(); + v.assign(first, last); + std::exclusive_scan(v.begin(), v.end(), v.begin(), init); + assert(std::equal(v.begin(), v.end(), rFirst, rLast)); +} + + +template +void +test() +{ + int ia[] = {1, 3, 5, 7, 9}; + const int pRes[] = {0, 1, 4, 9, 16}; + const unsigned sa = sizeof(ia) / sizeof(ia[0]); + static_assert(sa == sizeof(pRes) / sizeof(pRes[0])); // just to be sure + + for (unsigned int i = 0; i < sa; ++i ) + test(Iter(ia), Iter(ia + i), 0, pRes, pRes + i); +} + +int triangle(int n) { return n*(n+1)/2; } + +// Basic sanity +void basic_tests() +{ + { + std::vector v(10); + std::fill(v.begin(), v.end(), 3); + std::exclusive_scan(v.begin(), v.end(), v.begin(), 50); + for (size_t i = 0; i < v.size(); ++i) + assert(v[i] == 50 + (int) i * 3); + } + + { + std::vector v(10); + std::iota(v.begin(), v.end(), 0); + std::exclusive_scan(v.begin(), v.end(), v.begin(), 30); + for (size_t i = 0; i < v.size(); ++i) + assert(v[i] == 30 + triangle(i-1)); + } + + { + std::vector v(10); + std::iota(v.begin(), v.end(), 1); + std::exclusive_scan(v.begin(), v.end(), v.begin(), 40); + for (size_t i = 0; i < v.size(); ++i) + assert(v[i] == 40 + triangle(i)); + } + +} + +int main() +{ + basic_tests(); + +// All the iterator categories + test >(); + test >(); + test >(); + test >(); + test(); + test< int*>(); +} Index: test/std/numerics/numeric.ops/exclusive.scan/exclusive_scan_iter_iter_iter_init_op.pass.cpp =================================================================== --- test/std/numerics/numeric.ops/exclusive.scan/exclusive_scan_iter_iter_iter_init_op.pass.cpp +++ test/std/numerics/numeric.ops/exclusive.scan/exclusive_scan_iter_iter_iter_init_op.pass.cpp @@ -0,0 +1,87 @@ +//===----------------------------------------------------------------------===// +// +// 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 +// OutputIterator +// exclusive_scan(InputIterator first, InputIterator last, +// OutputIterator result, +// T init, BinaryOperation binary_op); // C++17 + +#include +#include +#include + +#include "test_iterators.h" + +template +void +test(Iter1 first, Iter1 last, T init, Op op, Iter2 rFirst, Iter2 rLast) +{ + std::vector::value_type> v; + +// Not in place + std::exclusive_scan(first, last, std::back_inserter(v), init, op); + assert(std::equal(v.begin(), v.end(), rFirst, rLast)); + +// In place + v.clear(); + v.assign(first, last); + std::exclusive_scan(v.begin(), v.end(), v.begin(), init, op); + assert(std::equal(v.begin(), v.end(), rFirst, rLast)); +} + + +template +void +test() +{ + int ia[] = {1, 3, 5, 7, 9}; + const int pRes[] = {0, 1, 4, 9, 16}; + const int mRes[] = {1, 1, 3, 15, 105}; + const unsigned sa = sizeof(ia) / sizeof(ia[0]); + static_assert(sa == sizeof(pRes) / sizeof(pRes[0])); // just to be sure + static_assert(sa == sizeof(mRes) / sizeof(mRes[0])); // just to be sure + + for (unsigned int i = 0; i < sa; ++i ) { + test(Iter(ia), Iter(ia + i), 0, std::plus<>(), pRes, pRes + i); + test(Iter(ia), Iter(ia + i), 1, std::multiplies<>(), mRes, mRes + i); + } +} + +int main() +{ +// All the iterator categories + test >(); + test >(); + test >(); + test >(); + test(); + test< int*>(); + +// Make sure that the calculations are done using the init typedef + { + std::vector v(10); + std::iota(v.begin(), v.end(), 1); + std::vector res; + std::exclusive_scan(v.begin(), v.end(), std::back_inserter(res), 1, std::multiplies<>()); + + assert(res.size() == 10); + int j = 1; + assert(res[0] == 1); + for (size_t i = 1; i < v.size(); ++i) + { + j *= i; + assert(res[i] == j); + } + } +} + \ No newline at end of file Index: test/std/numerics/numeric.ops/transform.exclusive.scan/transform_exclusive_scan_iter_iter_iter_init_bop_uop.pass.cpp =================================================================== --- test/std/numerics/numeric.ops/transform.exclusive.scan/transform_exclusive_scan_iter_iter_iter_init_bop_uop.pass.cpp +++ test/std/numerics/numeric.ops/transform.exclusive.scan/transform_exclusive_scan_iter_iter_iter_init_bop_uop.pass.cpp @@ -0,0 +1,155 @@ +//===----------------------------------------------------------------------===// +// +// 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 +// OutputIterator transform_exclusive_scan(InputIterator first, InputIterator last, +// OutputIterator result, T init, +// BinaryOperation binary_op, +// UnaryOperation unary_op); + + +#include +#include +#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 +void +test(Iter1 first, Iter1 last, BOp bop, UOp uop, T init, Iter2 rFirst, Iter2 rLast) +{ + std::vector::value_type> v; +// Test not in-place + std::transform_exclusive_scan(first, last, std::back_inserter(v), init, bop, uop); + assert(std::equal(v.begin(), v.end(), rFirst, rLast)); + +// Test in-place + v.clear(); + v.assign(first, last); + std::transform_exclusive_scan(v.begin(), v.end(), v.begin(), init, bop, uop); + assert(std::equal(v.begin(), v.end(), rFirst, rLast)); +} + + +template +void +test() +{ + int ia[] = { 1, 3, 5, 7, 9}; + const int pResI0[] = { 0, 1, 4, 9, 16}; // with identity + const int mResI0[] = { 0, 0, 0, 0, 0}; + const int pResN0[] = { 0, -1, -4, -9, -16}; // with negate + const int mResN0[] = { 0, 0, 0, 0, 0}; + const int pResI2[] = { 2, 3, 6, 11, 18}; // with identity + const int mResI2[] = { 2, 2, 6, 30, 210}; + const int pResN2[] = { 2, 1, -2, -7, -14}; // with negate + const int mResN2[] = { 2, -2, 6, -30, 210}; + const unsigned sa = sizeof(ia) / sizeof(ia[0]); + static_assert(sa == sizeof(pResI0) / sizeof(pResI0[0])); // just to be sure + static_assert(sa == sizeof(mResI0) / sizeof(mResI0[0])); // just to be sure + static_assert(sa == sizeof(pResN0) / sizeof(pResN0[0])); // just to be sure + static_assert(sa == sizeof(mResN0) / sizeof(mResN0[0])); // just to be sure + static_assert(sa == sizeof(pResI2) / sizeof(pResI2[0])); // just to be sure + static_assert(sa == sizeof(mResI2) / sizeof(mResI2[0])); // just to be sure + static_assert(sa == sizeof(pResN2) / sizeof(pResN2[0])); // just to be sure + static_assert(sa == sizeof(mResN2) / sizeof(mResN2[0])); // just to be sure + + for (unsigned int i = 0; i < sa; ++i ) { + test(Iter(ia), Iter(ia + i), std::plus<>(), identity<>(), 0, pResI0, pResI0 + i); + test(Iter(ia), Iter(ia + i), std::multiplies<>(), identity<>(), 0, mResI0, mResI0 + i); + test(Iter(ia), Iter(ia + i), std::plus<>(), std::negate<>(), 0, pResN0, pResN0 + i); + test(Iter(ia), Iter(ia + i), std::multiplies<>(), std::negate<>(), 0, mResN0, mResN0 + i); + test(Iter(ia), Iter(ia + i), std::plus<>(), identity<>(), 2, pResI2, pResI2 + i); + test(Iter(ia), Iter(ia + i), std::multiplies<>(), identity<>(), 2, mResI2, mResI2 + i); + test(Iter(ia), Iter(ia + i), std::plus<>(), std::negate<>(), 2, pResN2, pResN2 + i); + test(Iter(ia), Iter(ia + i), std::multiplies<>(), std::negate<>(), 2, mResN2, mResN2 + i); + } +} + +int triangle(int n) { return n*(n+1)/2; } + +// Basic sanity +void basic_tests() +{ + { + std::vector v(10); + std::fill(v.begin(), v.end(), 3); + std::transform_exclusive_scan(v.begin(), v.end(), v.begin(), 50, std::plus<>(), identity<>()); + for (size_t i = 0; i < v.size(); ++i) + assert(v[i] == 50 + (int) i * 3); + } + + { + std::vector v(10); + std::iota(v.begin(), v.end(), 0); + std::transform_exclusive_scan(v.begin(), v.end(), v.begin(), 30, std::plus<>(), identity<>()); + for (size_t i = 0; i < v.size(); ++i) + assert(v[i] == 30 + triangle(i-1)); + } + + { + std::vector v(10); + std::iota(v.begin(), v.end(), 1); + std::transform_exclusive_scan(v.begin(), v.end(), v.begin(), 40, std::plus<>(), identity<>()); + for (size_t i = 0; i < v.size(); ++i) + assert(v[i] == 40 + triangle(i)); + } + +// Make sure that the calculations are done using the init typedef + { + std::vector v(10); + std::iota(v.begin(), v.end(), 1); + std::vector res; + std::transform_exclusive_scan(v.begin(), v.end(), std::back_inserter(res), 1, std::multiplies<>(), identity<>()); + + assert(res.size() == 10); + int j = 1; + assert(res[0] == 1); + for (size_t i = 1; i < res.size(); ++i) + { + j *= i; + assert(res[i] == j); + + } + } +} + +int main() +{ + basic_tests(); + +// All the iterator categories + test >(); + test >(); + test >(); + test >(); + test(); + test< int*>(); +}