Index: include/numeric =================================================================== --- include/numeric +++ include/numeric @@ -81,6 +81,20 @@ exclusive_scan(InputIterator first, InputIterator last, OutputIterator result, T init, BinaryOperation binary_op); // C++17 +template + OutputIterator + inclusive_scan(InputIterator first, InputIterator last, OutputIterator result); // C++17 + +template + OutputIterator + inclusive_scan(InputIterator first, InputIterator last, + OutputIterator result, BinaryOperation binary_op); // C++17 + +template + OutputIterator + inclusive_scan(InputIterator first, InputIterator last, + OutputIterator result, BinaryOperation binary_op, T init); // C++17 + template OutputIterator @@ -88,6 +102,21 @@ OutputIterator result, T init, BinaryOperation binary_op, UnaryOperation unary_op); // C++17 +template + OutputIterator + transform_inclusive_scan(InputIterator first, InputIterator last, + OutputIterator result, + BinaryOperation binary_op, UnaryOperation unary_op); // C++17 + +template + OutputIterator + transform_inclusive_scan(InputIterator first, InputIterator last, + OutputIterator result, + BinaryOperation binary_op, UnaryOperation unary_op, + T init); // C++17 + template OutputIterator adjacent_difference(InputIterator first, InputIterator last, OutputIterator result); @@ -295,6 +324,38 @@ return _VSTD::exclusive_scan(__first, __last, __result, __init, _VSTD::plus<>()); } +template +_OutputIterator inclusive_scan(_InputIterator __first, _InputIterator __last, + _OutputIterator __result, _BinaryOp __b, _Tp __init) +{ + for (; __first != __last; ++__first, (void) ++__result) { + __init = __b(__init, *__first); + *__result = __init; + } + return __result; +} + +template +_OutputIterator inclusive_scan(_InputIterator __first, _InputIterator __last, + _OutputIterator __result, _BinaryOp __b) +{ + if (__first != __last) { + typename std::iterator_traits<_InputIterator>::value_type __init = *__first; + *__result++ = __init; + if (++__first != __last) + return _VSTD::inclusive_scan(__first, __last, __result, __b, __init); + } + + return __result; +} + +template +_OutputIterator inclusive_scan(_InputIterator __first, _InputIterator __last, + _OutputIterator __result) +{ + return _VSTD::inclusive_scan(__first, __last, __result, std::plus<>()); +} + template inline _LIBCPP_INLINE_VISIBILITY @@ -316,6 +377,32 @@ } return __result; } + +template +_OutputIterator transform_inclusive_scan(_InputIterator __first, _InputIterator __last, + _OutputIterator __result, _BinaryOp __b, _UnaryOp __u, _Tp __init) +{ + for (; __first != __last; ++__first, (void) ++__result) { + __init = __b(__init, __u(*__first)); + *__result = __init; + } + + return __result; +} + +template +_OutputIterator transform_inclusive_scan(_InputIterator __first, _InputIterator __last, + _OutputIterator __result, _BinaryOp __b, _UnaryOp __u) +{ + if (__first != __last) { + typename std::iterator_traits<_InputIterator>::value_type __init = __u(*__first); + *__result++ = __init; + if (++__first != __last) + return _VSTD::transform_inclusive_scan(__first, __last, __result, __b, __u, __init); + } + + return __result; +} #endif template Index: test/std/numerics/numeric.ops/inclusive.scan/inclusive_scan.pass.cpp =================================================================== --- test/std/numerics/numeric.ops/inclusive.scan/inclusive_scan.pass.cpp +++ test/std/numerics/numeric.ops/inclusive.scan/inclusive_scan.pass.cpp @@ -0,0 +1,102 @@ +//===----------------------------------------------------------------------===// +// +// 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 inclusive_scan(InputIterator first, InputIterator last, +// OutputIterator result, T init); +// + +#include +#include +#include + +#include "test_iterators.h" + +template +void +test(Iter1 first, Iter1 last, Iter2 rFirst, Iter2 rLast) +{ + std::vector::value_type> v; + +// Not in place + std::inclusive_scan(first, last, std::back_inserter(v)); + assert(std::equal(v.begin(), v.end(), rFirst, rLast)); + +// In place + v.clear(); + v.assign(first, last); + std::inclusive_scan(v.begin(), v.end(), v.begin()); + assert(std::equal(v.begin(), v.end(), rFirst, rLast)); +} + + +template +void +test() +{ + int ia[] = {1, 3, 5, 7, 9}; + const int pRes[] = {1, 4, 9, 16, 25}; + 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), 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::inclusive_scan(v.begin(), v.end(), v.begin()); + for (size_t i = 0; i < v.size(); ++i) + assert(v[i] == (int)(i+1) * 3); + } + + { + std::vector v(10); + std::iota(v.begin(), v.end(), 0); + std::inclusive_scan(v.begin(), v.end(), v.begin()); + for (size_t i = 0; i < v.size(); ++i) + assert(v[i] == triangle(i)); + } + + { + std::vector v(10); + std::iota(v.begin(), v.end(), 1); + std::inclusive_scan(v.begin(), v.end(), v.begin()); + for (size_t i = 0; i < v.size(); ++i) + assert(v[i] == triangle(i + 1)); + } + + { + std::vector v, res; + std::inclusive_scan(v.begin(), v.end(), std::back_inserter(res)); + assert(res.empty()); + } +} + +int main() +{ + basic_tests(); + +// All the iterator categories + test >(); + test >(); + test >(); + test >(); + test(); + test< int*>(); +} Index: test/std/numerics/numeric.ops/inclusive.scan/inclusive_scan_op.pass.cpp =================================================================== --- test/std/numerics/numeric.ops/inclusive.scan/inclusive_scan_op.pass.cpp +++ test/std/numerics/numeric.ops/inclusive.scan/inclusive_scan_op.pass.cpp @@ -0,0 +1,112 @@ +//===----------------------------------------------------------------------===// +// +// 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 +// inclusive_scan(InputIterator first, InputIterator last, +// OutputIterator result, +// BinaryOperation binary_op); // C++17 + +#include +#include +#include +#include + +#include "test_iterators.h" + +template +void +test(Iter1 first, Iter1 last, Op op, Iter2 rFirst, Iter2 rLast) +{ + std::vector::value_type> v; + +// Not in place + std::inclusive_scan(first, last, std::back_inserter(v), op); + assert(std::equal(v.begin(), v.end(), rFirst, rLast)); + +// In place + v.clear(); + v.assign(first, last); + std::inclusive_scan(v.begin(), v.end(), v.begin(), op); + assert(std::equal(v.begin(), v.end(), rFirst, rLast)); +} + + +template +void +test() +{ + int ia[] = {1, 3, 5, 7, 9}; + const int pRes[] = {1, 4, 9, 16, 25}; + const int mRes[] = {1, 3, 15, 105, 945}; + 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), std::plus<>(), pRes, pRes + i); + test(Iter(ia), Iter(ia + i), std::multiplies<>(), mRes, mRes + 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::inclusive_scan(v.begin(), v.end(), v.begin(), std::plus<>()); + for (size_t i = 0; i < v.size(); ++i) + assert(v[i] == (int)(i+1) * 3); + } + + { + std::vector v(10); + std::iota(v.begin(), v.end(), 0); + std::inclusive_scan(v.begin(), v.end(), v.begin(), std::plus<>()); + for (size_t i = 0; i < v.size(); ++i) + assert(v[i] == triangle(i)); + } + + { + std::vector v(10); + std::iota(v.begin(), v.end(), 1); + std::inclusive_scan(v.begin(), v.end(), v.begin(), std::plus<>()); + for (size_t i = 0; i < v.size(); ++i) + assert(v[i] == triangle(i + 1)); + } + + { + std::vector v, res; + std::inclusive_scan(v.begin(), v.end(), std::back_inserter(res), std::plus<>()); + assert(res.empty()); + } +} + + +int main() +{ + + basic_tests(); + +// All the iterator categories +// test >(); +// test >(); +// test >(); +// test >(); +// test(); +// test< int*>(); + +} + \ No newline at end of file Index: test/std/numerics/numeric.ops/inclusive.scan/inclusive_scan_op_init.pass.cpp =================================================================== --- test/std/numerics/numeric.ops/inclusive.scan/inclusive_scan_op_init.pass.cpp +++ test/std/numerics/numeric.ops/inclusive.scan/inclusive_scan_op_init.pass.cpp @@ -0,0 +1,128 @@ +//===----------------------------------------------------------------------===// +// +// 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 +// inclusive_scan(InputIterator first, InputIterator last, +// OutputIterator result, +// BinaryOperation binary_op, T init); // C++17 + +#include +#include +#include + +#include "test_iterators.h" + +template +void +test(Iter1 first, Iter1 last, Op op, T init, Iter2 rFirst, Iter2 rLast) +{ + std::vector::value_type> v; + +// Not in place + std::inclusive_scan(first, last, std::back_inserter(v), op, init); + assert(std::equal(v.begin(), v.end(), rFirst, rLast)); + +// In place + v.clear(); + v.assign(first, last); + std::inclusive_scan(v.begin(), v.end(), v.begin(), op, init); + assert(std::equal(v.begin(), v.end(), rFirst, rLast)); +} + + +template +void +test() +{ + int ia[] = {1, 3, 5, 7, 9}; + const int pRes[] = {1, 4, 9, 16, 25}; + const int mRes[] = {1, 3, 15, 105, 945}; + 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), std::plus<>(), 0, pRes, pRes + i); + test(Iter(ia), Iter(ia + i), std::multiplies<>(), 1, mRes, mRes + 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::inclusive_scan(v.begin(), v.end(), v.begin(), std::plus<>(), 50); + for (size_t i = 0; i < v.size(); ++i) + assert(v[i] == 50 + (int)(i+1) * 3); + } + + { + std::vector v(10); + std::iota(v.begin(), v.end(), 0); + std::inclusive_scan(v.begin(), v.end(), v.begin(), std::plus<>(), 40); + for (size_t i = 0; i < v.size(); ++i) + assert(v[i] == 40 + triangle(i)); + } + + { + std::vector v(10); + std::iota(v.begin(), v.end(), 1); + std::inclusive_scan(v.begin(), v.end(), v.begin(), std::plus<>(), 30); + for (size_t i = 0; i < v.size(); ++i) + assert(v[i] == 30 + triangle(i + 1)); + } + + { + std::vector v, res; + std::inclusive_scan(v.begin(), v.end(), std::back_inserter(res), std::plus<>(), 40); + assert(res.empty()); + } + +// 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::inclusive_scan(v.begin(), v.end(), std::back_inserter(res), std::multiplies<>(), 1); + + assert(res.size() == 10); + int j = 1; + assert(res[0] == 1); + for (size_t i = 1; i < v.size(); ++i) + { + j *= i + 1; + assert(res[i] == j); + } + } +} + + +int main() +{ + + basic_tests(); + +// All the iterator categories + test >(); + test >(); + test >(); + test >(); + test(); + test< int*>(); + +} + \ No newline at end of file Index: test/std/numerics/numeric.ops/transform.inclusive.scan/transform_inclusive_scan_bop_uop.pass.cpp =================================================================== --- test/std/numerics/numeric.ops/transform.inclusive.scan/transform_inclusive_scan_bop_uop.pass.cpp +++ test/std/numerics/numeric.ops/transform.inclusive.scan/transform_inclusive_scan_bop_uop.pass.cpp @@ -0,0 +1,133 @@ +//===----------------------------------------------------------------------===// +// +// 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_inclusive_scan(InputIterator first, InputIterator last, +// OutputIterator result, +// 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, Iter2 rFirst, Iter2 rLast) +{ + std::vector::value_type> v; +// Test not in-place + std::transform_inclusive_scan(first, last, std::back_inserter(v), bop, uop); + assert(std::equal(v.begin(), v.end(), rFirst, rLast)); + +// Test in-place + v.clear(); + v.assign(first, last); + std::transform_inclusive_scan(v.begin(), v.end(), v.begin(), bop, uop); + assert(std::equal(v.begin(), v.end(), rFirst, rLast)); +} + + +template +void +test() +{ + int ia[] = { 1, 3, 5, 7, 9}; + const int pResI0[] = { 1, 4, 9, 16, 25}; // with identity + const int mResI0[] = { 1, 3, 15, 105, 945}; + const int pResN0[] = { -1, -4, -9, -16, -25}; // with negate + const int mResN0[] = { -1, 3, -15, 105, -945}; + 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 + + for (unsigned int i = 0; i < sa; ++i ) { + test(Iter(ia), Iter(ia + i), std::plus<>(), identity<>(), pResI0, pResI0 + i); + test(Iter(ia), Iter(ia + i), std::multiplies<>(), identity<>(), mResI0, mResI0 + i); + test(Iter(ia), Iter(ia + i), std::plus<>(), std::negate<>(), pResN0, pResN0 + i); + test(Iter(ia), Iter(ia + i), std::multiplies<>(), std::negate<>(), mResN0, mResN0 + 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_inclusive_scan(v.begin(), v.end(), v.begin(), std::plus<>(), identity<>()); + std::copy(v.begin(), v.end(), std::ostream_iterator(std::cout, " ")); + std::cout << std::endl; + for (size_t i = 0; i < v.size(); ++i) + assert(v[i] == (int)(i+1) * 3); + } + + { + std::vector v(10); + std::iota(v.begin(), v.end(), 0); + std::transform_inclusive_scan(v.begin(), v.end(), v.begin(), std::plus<>(), identity<>()); + for (size_t i = 0; i < v.size(); ++i) + assert(v[i] == triangle(i)); + } + + { + std::vector v(10); + std::iota(v.begin(), v.end(), 1); + std::transform_inclusive_scan(v.begin(), v.end(), v.begin(), std::plus<>(), identity<>()); + for (size_t i = 0; i < v.size(); ++i) + assert(v[i] == triangle(i + 1)); + } + + { + std::vector v, res; + std::transform_inclusive_scan(v.begin(), v.end(), std::back_inserter(res), std::plus<>(), identity<>()); + assert(res.empty()); + } +} + +int main() +{ + basic_tests(); + +// All the iterator categories + test >(); + test >(); + test >(); + test >(); + test(); + test< int*>(); +} Index: test/std/numerics/numeric.ops/transform.inclusive.scan/transform_inclusive_scan_bop_uop_init.pass.cpp =================================================================== --- test/std/numerics/numeric.ops/transform.inclusive.scan/transform_inclusive_scan_bop_uop_init.pass.cpp +++ test/std/numerics/numeric.ops/transform.inclusive.scan/transform_inclusive_scan_bop_uop_init.pass.cpp @@ -0,0 +1,160 @@ +//===----------------------------------------------------------------------===// +// +// 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_inclusive_scan(InputIterator first, InputIterator last, +// OutputIterator result, +// BinaryOperation binary_op, +// UnaryOperation unary_op, +// T init); + + +#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_inclusive_scan(first, last, std::back_inserter(v), bop, uop, init); + assert(std::equal(v.begin(), v.end(), rFirst, rLast)); + +// Test in-place + v.clear(); + v.assign(first, last); + std::transform_inclusive_scan(v.begin(), v.end(), v.begin(), bop, uop, init); + assert(std::equal(v.begin(), v.end(), rFirst, rLast)); +} + + +template +void +test() +{ + int ia[] = { 1, 3, 5, 7, 9}; + const int pResI0[] = { 1, 4, 9, 16, 25}; // with identity + const int mResI0[] = { 0, 0, 0, 0, 0}; + const int pResN0[] = { -1, -4, -9, -16, -25}; // with negate + const int mResN0[] = { 0, 0, 0, 0, 0}; + const int pResI2[] = { 3, 6, 11, 18, 27}; // with identity + const int mResI2[] = { 2, 6, 30, 210, 1890}; + const int pResN2[] = { 1, -2, -7, -14, -23}; // with negate + const int mResN2[] = { -2, 6, -30, 210, -1890}; + 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_inclusive_scan(v.begin(), v.end(), v.begin(), std::plus<>(), identity<>(), 50); + for (size_t i = 0; i < v.size(); ++i) + assert(v[i] == 50 + (int) (i + 1) * 3); + } + + { + std::vector v(10); + std::iota(v.begin(), v.end(), 0); + std::transform_inclusive_scan(v.begin(), v.end(), v.begin(), std::plus<>(), identity<>(), 30); + for (size_t i = 0; i < v.size(); ++i) + assert(v[i] == 30 + triangle(i)); + } + + { + std::vector v(10); + std::iota(v.begin(), v.end(), 1); + std::transform_inclusive_scan(v.begin(), v.end(), v.begin(), std::plus<>(), identity<>(), 40); + for (size_t i = 0; i < v.size(); ++i) + assert(v[i] == 40 + triangle(i + 1)); + } + + { + std::vector v, res; + std::transform_inclusive_scan(v.begin(), v.end(), std::back_inserter(res), std::plus<>(), identity<>(), 1); + assert(res.empty()); + } + +// 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_inclusive_scan(v.begin(), v.end(), std::back_inserter(res), std::multiplies<>(), identity<>(), 1); + + assert(res.size() == 10); + int j = 1; + assert(res[0] == 1); + for (size_t i = 1; i < res.size(); ++i) + { + j *= i + 1; + assert(res[i] == j); + } + } +} + +int main() +{ + basic_tests(); + +// All the iterator categories + test >(); + test >(); + test >(); + test >(); + test(); + test< int*>(); +}