Index: include/numeric =================================================================== --- include/numeric +++ include/numeric @@ -42,6 +42,35 @@ OutputIterator partial_sum(InputIterator first, InputIterator last, OutputIterator result, BinaryOperation binary_op); +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 + 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); @@ -66,6 +95,7 @@ #include <__config> #include #include // for numeric_limits +#include #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) #pragma GCC system_header @@ -154,9 +184,78 @@ return __result; } +#if _LIBCPP_STD_VER > 14 +template +inline _LIBCPP_INLINE_VISIBILITY +_OutputIterator +inclusive_scan(_InputIterator __first, _InputIterator __last, + _OutputIterator __result, _BinaryOp __b, _Tp __init) +{ + *__result++ = __init; + for (; __first != __last; ++__first) { + __init = __b(__init, *__first); + *__result++ = __init; + } + + return __result; +} + +template +inline _LIBCPP_INLINE_VISIBILITY +_OutputIterator +inclusive_scan(_InputIterator __first, _InputIterator __last, + _OutputIterator __result, _BinaryOp __b) +{ + if (__first != __last) { + typename iterator_traits<_InputIterator>::value_type __init = *__first++; + return inclusive_scan(__first, __last, __result, __b, __init); + } + + return __result; +} + template inline _LIBCPP_INLINE_VISIBILITY _OutputIterator +inclusive_scan(_InputIterator __first, _InputIterator __last, _OutputIterator __result) +{ + return inclusive_scan(__first, __last, __result, _VSTD::plus<>()); +} + +template +inline _LIBCPP_INLINE_VISIBILITY +_OutputIterator +transform_inclusive_scan(_InputIterator __first, _InputIterator __last, + _OutputIterator __result, + _BinaryOp __b, _UnaryOp __u, _Tp __init) +{ + *__result++ = __init; + for (; __first != __last; ++__first) { + __init = __b(__init, __u(*__first)); + *__result++ = __init; + } + + return __result; +} + +template +inline _LIBCPP_INLINE_VISIBILITY +_OutputIterator +transform_inclusive_scan(_InputIterator __first, _InputIterator __last, + _OutputIterator __result, _BinaryOp __b, _UnaryOp __u) +{ + if (__first != __last) { + typename iterator_traits<_InputIterator>::value_type __init = __u(*__first++); + return transform_inclusive_scan(__first, __last, __result, __b, __u, __init); + } + + return __result; +} +#endif + +template +inline _LIBCPP_INLINE_VISIBILITY +_OutputIterator adjacent_difference(_InputIterator __first, _InputIterator __last, _OutputIterator __result) { if (__first != __last) Index: test/std/numerics/numeric.ops/inclusive.scan/inclusive_scan_iter_iter_iter.pass.cpp =================================================================== --- test/std/numerics/numeric.ops/inclusive.scan/inclusive_scan_iter_iter_iter.pass.cpp +++ test/std/numerics/numeric.ops/inclusive.scan/inclusive_scan_iter_iter_iter.pass.cpp @@ -0,0 +1,56 @@ +//===----------------------------------------------------------------------===// +// +// 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); +// + +#include +#include +#include + +#include "test_iterators.h" + +template +void +test(Iter1 first, Iter1 last, Iter2 rFirst, Iter2 rLast) +{ + std::vector::value_type> v; + std::inclusive_scan(first, last, std::back_inserter(v)); + 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}; + unsigned sa = sizeof(ia) / sizeof(ia[0]); + 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 main() +{ +// All the iterator categories + test >(); + test >(); + test >(); + test >(); + test(); + test< int*>(); +} Index: test/std/numerics/numeric.ops/inclusive.scan/inclusive_scan_iter_iter_iter_op.pass.cpp =================================================================== --- test/std/numerics/numeric.ops/inclusive.scan/inclusive_scan_iter_iter_iter_op.pass.cpp +++ test/std/numerics/numeric.ops/inclusive.scan/inclusive_scan_iter_iter_iter_op.pass.cpp @@ -0,0 +1,60 @@ +//===----------------------------------------------------------------------===// +// +// 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 "test_iterators.h" + +template +void +test(Iter1 first, Iter1 last, Op op, Iter2 rFirst, Iter2 rLast) +{ + std::vector::value_type> v; + std::inclusive_scan(first, last, std::back_inserter(v), 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}; + unsigned sa = sizeof(ia) / sizeof(ia[0]); + assert(sa == sizeof(pRes) / sizeof(pRes[0])); // just to be sure + 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 main() +{ +// All the iterator categories + test >(); + test >(); + test >(); + test >(); + test(); + test< int*>(); +} Index: test/std/numerics/numeric.ops/inclusive.scan/inclusive_scan_iter_iter_iter_op_init.pass.cpp =================================================================== --- test/std/numerics/numeric.ops/inclusive.scan/inclusive_scan_iter_iter_iter_op_init.pass.cpp +++ test/std/numerics/numeric.ops/inclusive.scan/inclusive_scan_iter_iter_iter_op_init.pass.cpp @@ -0,0 +1,65 @@ +//===----------------------------------------------------------------------===// +// +// 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); + +#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; + std::inclusive_scan(first, last, std::back_inserter(v), op, init); + assert(std::equal(v.begin(), v.end(), rFirst, rLast)); +} + + +template +void +test() +{ + int ia[] = {1, 3, 5, 7, 9}; + const int pRes0[] = {0, 1, 4, 9, 16, 25}; + const int mRes0[] = {0, 0, 0, 0, 0, 0}; + const int pRes2[] = {2, 3, 6, 11, 18, 27}; + const int mRes2[] = {2, 2, 6, 30, 210, 1890}; + unsigned sa = sizeof(ia) / sizeof(ia[0]); + assert(sa + 1 == sizeof(pRes0) / sizeof(pRes0[0])); // just to be sure + assert(sa + 1 == sizeof(mRes0) / sizeof(mRes0[0])); // just to be sure + assert(sa + 1 == sizeof(pRes2) / sizeof(pRes2[0])); // just to be sure + assert(sa + 1 == sizeof(mRes2) / sizeof(mRes2[0])); // just to be sure + + for (unsigned int i = 0; i < sa; ++i ) { + test(Iter(ia), Iter(ia + i), std::plus<>(), 0, pRes0, pRes0 + i + 1); + test(Iter(ia), Iter(ia + i), std::multiplies<>(), 0, mRes0, mRes0 + i + 1); + test(Iter(ia), Iter(ia + i), std::plus<>(), 2, pRes2, pRes2 + i + 1); + test(Iter(ia), Iter(ia + i), std::multiplies<>(), 2, mRes2, mRes2 + i + 1); + } +} + +int main() +{ +// All the iterator categories + test >(); + test >(); + test >(); + test >(); + test(); + test< int*>(); +} Index: test/std/numerics/numeric.ops/transform.inclusive.scan/transform_inclusive_scan_iter_iter_iter_bop_uop.pass.cpp =================================================================== --- test/std/numerics/numeric.ops/transform.inclusive.scan/transform_inclusive_scan_iter_iter_iter_bop_uop.pass.cpp +++ test/std/numerics/numeric.ops/transform.inclusive.scan/transform_inclusive_scan_iter_iter_iter_bop_uop.pass.cpp @@ -0,0 +1,88 @@ +//===----------------------------------------------------------------------===// +// +// 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; + std::transform_inclusive_scan(first, last, std::back_inserter(v), bop, uop); +// std::cout << v.size() << " vs " << std::distance(rFirst, rLast) << std::endl; +// std::copy(v.begin(), v.end(), std::ostream_iterator(std::cout, " ")); +// std::cout << std::endl; + assert(std::equal(v.begin(), v.end(), rFirst, rLast)); +} + + +template +void +test() +{ + int ia[] = { 1, 3, 5, 7, 9}; + const int pResI[] = { 1, 4, 9, 16, 25}; // with identity + const int mResI[] = { 1, 3, 15, 105, 945}; + const int pResN[] = {-1, -4, -9, -16, -25}; // with negate + const int mResN[] = {-1, 3, -15, 105, -945}; + unsigned sa = sizeof(ia) / sizeof(ia[0]); + assert(sa == sizeof(pResI) / sizeof(pResI[0])); // just to be sure + assert(sa == sizeof(mResI) / sizeof(mResI[0])); // just to be sure + assert(sa == sizeof(pResN) / sizeof(pResN[0])); // just to be sure + assert(sa == sizeof(mResN) / sizeof(mResN[0])); // just to be sure + + for (unsigned int i = 0; i < sa; ++i ) { + test(Iter(ia), Iter(ia + i), std::plus<>(), identity<>(), pResI, pResI + i); + test(Iter(ia), Iter(ia + i), std::multiplies<>(), identity<>(), mResI, mResI + i); + test(Iter(ia), Iter(ia + i), std::plus<>(), std::negate<>(), pResN, pResN + i); + test(Iter(ia), Iter(ia + i), std::multiplies<>(), std::negate<>(), mResN, mResN + i); + } +} + +int main() +{ +// All the iterator categories + test >(); + test >(); + test >(); + test >(); + test(); + test< int*>(); +} Index: test/std/numerics/numeric.ops/transform.inclusive.scan/transform_inclusive_scan_iter_iter_iter_bop_uop_init.pass.cpp =================================================================== --- test/std/numerics/numeric.ops/transform.inclusive.scan/transform_inclusive_scan_iter_iter_iter_bop_uop_init.pass.cpp +++ test/std/numerics/numeric.ops/transform.inclusive.scan/transform_inclusive_scan_iter_iter_iter_bop_uop_init.pass.cpp @@ -0,0 +1,101 @@ +//===----------------------------------------------------------------------===// +// +// 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 + +#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; + std::transform_inclusive_scan(first, last, std::back_inserter(v), bop, uop, init); +// std::cout << v.size() << " vs " << std::distance(rFirst, rLast) << std::endl; +// std::copy(v.begin(), v.end(), std::ostream_iterator(std::cout, " ")); +// std::cout << std::endl; + 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, 25}; // with identity + const int mResI0[] = { 0, 0, 0, 0, 0, 0}; + const int pResN0[] = { 0, -1, -4, -9, -16, -25}; // with negate + const int mResN0[] = { 0, 0, 0, 0, 0, 0}; + const int pResI2[] = { 2, 3, 6, 11, 18, 27}; // with identity + const int mResI2[] = { 2, 2, 6, 30, 210, 1890}; + const int pResN2[] = { 2, 1, -2, -7, -14, -23}; // with negate + const int mResN2[] = { 2, -2, 6, -30, 210, -1890}; + unsigned sa = sizeof(ia) / sizeof(ia[0]); + assert(sa + 1 == sizeof(pResI0) / sizeof(pResI0[0])); // just to be sure + assert(sa + 1 == sizeof(mResI0) / sizeof(mResI0[0])); // just to be sure + assert(sa + 1 == sizeof(pResN0) / sizeof(pResN0[0])); // just to be sure + assert(sa + 1 == sizeof(mResN0) / sizeof(mResN0[0])); // just to be sure + assert(sa + 1 == sizeof(pResI2) / sizeof(pResI2[0])); // just to be sure + assert(sa + 1 == sizeof(mResI2) / sizeof(mResI2[0])); // just to be sure + assert(sa + 1 == sizeof(pResN2) / sizeof(pResN2[0])); // just to be sure + assert(sa + 1 == 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 + 1); + test(Iter(ia), Iter(ia + i), std::multiplies<>(), identity<>(), 0, mResI0, mResI0 + i + 1); + test(Iter(ia), Iter(ia + i), std::plus<>(), std::negate<>(), 0, pResN0, pResN0 + i + 1); + test(Iter(ia), Iter(ia + i), std::multiplies<>(), std::negate<>(), 0, mResN0, mResN0 + i + 1); + test(Iter(ia), Iter(ia + i), std::plus<>(), identity<>(), 2, pResI2, pResI2 + i + 1); + test(Iter(ia), Iter(ia + i), std::multiplies<>(), identity<>(), 2, mResI2, mResI2 + i + 1); + test(Iter(ia), Iter(ia + i), std::plus<>(), std::negate<>(), 2, pResN2, pResN2 + i + 1); + test(Iter(ia), Iter(ia + i), std::multiplies<>(), std::negate<>(), 2, mResN2, mResN2 + i + 1); + } +} + +int main() +{ +// All the iterator categories + test >(); + test >(); + test >(); + test >(); + test(); + test< int*>(); +}