From ed920373a5faece7ea0bfdfebbd615294165c01c Mon Sep 17 00:00:00 2001 From: Jonathan Wakely Date: Wed, 19 Jun 2019 00:01:16 +0100 Subject: [PATCH] Implement new serial algorithms from Parallelism TS (P0024R2) These new (non-parallel) algorithms were added to C++17 along with the parallel algorithms, but were missing from libstdc++. * include/bits/algorithmfwd.h: Change title of doc group. * include/bits/stl_algo.h (for_each_n): Add new C++17 algorithm from P0024R2. * include/bits/stl_numeric.h: Define doc group and add algos to it. * include/std/numeric (__is_random_access_iter): New internal trait. (reduce, transform_reduce, exclusive_scan, inclusive_scan) (transform_exclusive_scan, transform_inclusive_scan): Likewise. * testsuite/25_algorithms/for_each/for_each_n.cc: New test. * testsuite/26_numerics/exclusive_scan/1.cc: New test. * testsuite/26_numerics/inclusive_scan/1.cc: New test. * testsuite/26_numerics/reduce/1.cc: New test. * testsuite/26_numerics/transform_exclusive_scan/1.cc: New test. * testsuite/26_numerics/transform_inclusive_scan/1.cc: New test. * testsuite/26_numerics/transform_reduce/1.cc: New test. * testsuite/util/testsuite_iterators.h (test_container::size()): New member function. From-SVN: r272459 --- libstdc++-v3/ChangeLog | 17 + libstdc++-v3/include/bits/algorithmfwd.h | 2 +- libstdc++-v3/include/bits/stl_algo.h | 33 ++ libstdc++-v3/include/bits/stl_numeric.h | 22 +- libstdc++-v3/include/std/numeric | 466 ++++++++++++++++++ .../25_algorithms/for_each/for_each_n.cc | 57 +++ .../testsuite/26_numerics/exclusive_scan/1.cc | 94 ++++ .../testsuite/26_numerics/inclusive_scan/1.cc | 123 +++++ .../testsuite/26_numerics/reduce/1.cc | 82 +++ .../26_numerics/transform_exclusive_scan/1.cc | 65 +++ .../26_numerics/transform_inclusive_scan/1.cc | 94 ++++ .../26_numerics/transform_reduce/1.cc | 109 ++++ .../testsuite/util/testsuite_iterators.h | 4 + 13 files changed, 1159 insertions(+), 9 deletions(-) create mode 100644 libstdc++-v3/testsuite/25_algorithms/for_each/for_each_n.cc create mode 100644 libstdc++-v3/testsuite/26_numerics/exclusive_scan/1.cc create mode 100644 libstdc++-v3/testsuite/26_numerics/inclusive_scan/1.cc create mode 100644 libstdc++-v3/testsuite/26_numerics/reduce/1.cc create mode 100644 libstdc++-v3/testsuite/26_numerics/transform_exclusive_scan/1.cc create mode 100644 libstdc++-v3/testsuite/26_numerics/transform_inclusive_scan/1.cc create mode 100644 libstdc++-v3/testsuite/26_numerics/transform_reduce/1.cc diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog index 4570ab147d5..5702523ed1c 100644 --- a/libstdc++-v3/ChangeLog +++ b/libstdc++-v3/ChangeLog @@ -1,5 +1,22 @@ 2019-06-18 Jonathan Wakely + * include/bits/algorithmfwd.h: Change title of doc group. + * include/bits/stl_algo.h (for_each_n): Add new C++17 algorithm from + P0024R2. + * include/bits/stl_numeric.h: Define doc group and add algos to it. + * include/std/numeric (__is_random_access_iter): New internal trait. + (reduce, transform_reduce, exclusive_scan, inclusive_scan) + (transform_exclusive_scan, transform_inclusive_scan): Likewise. + * testsuite/25_algorithms/for_each/for_each_n.cc: New test. + * testsuite/26_numerics/exclusive_scan/1.cc: New test. + * testsuite/26_numerics/inclusive_scan/1.cc: New test. + * testsuite/26_numerics/reduce/1.cc: New test. + * testsuite/26_numerics/transform_exclusive_scan/1.cc: New test. + * testsuite/26_numerics/transform_inclusive_scan/1.cc: New test. + * testsuite/26_numerics/transform_reduce/1.cc: New test. + * testsuite/util/testsuite_iterators.h (test_container::size()): New + member function. + * include/c_global/cstddef (std::byte): Perform arithmetic operations in unsigned int to avoid promotion (LWG 2950). diff --git a/libstdc++-v3/include/bits/algorithmfwd.h b/libstdc++-v3/include/bits/algorithmfwd.h index 40e051aa9e3..5e47fffe86e 100644 --- a/libstdc++-v3/include/bits/algorithmfwd.h +++ b/libstdc++-v3/include/bits/algorithmfwd.h @@ -154,7 +154,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION */ /** - * @defgroup set_algorithms Set Operation + * @defgroup set_algorithms Set Operations * @ingroup sorting_algorithms * * These algorithms are common set operations performed on sequences diff --git a/libstdc++-v3/include/bits/stl_algo.h b/libstdc++-v3/include/bits/stl_algo.h index b50c642f0e6..ca957e0b9a7 100644 --- a/libstdc++-v3/include/bits/stl_algo.h +++ b/libstdc++-v3/include/bits/stl_algo.h @@ -3867,6 +3867,39 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO return __f; // N.B. [alg.foreach] says std::move(f) but it's redundant. } +#if __cplusplus >= 201703L + /** + * @brief Apply a function to every element of a sequence. + * @ingroup non_mutating_algorithms + * @param __first An input iterator. + * @param __n A value convertible to an integer. + * @param __f A unary function object. + * @return `__first+__n` + * + * Applies the function object `__f` to each element in the range + * `[first, first+n)`. `__f` must not modify the order of the sequence. + * If `__f` has a return value it is ignored. + */ + template + _InputIterator + for_each_n(_InputIterator __first, _Size __n, _Function __f) + { + auto __n2 = std::__size_to_integer(__n); + using _Cat = typename iterator_traits<_InputIterator>::iterator_category; + if constexpr (is_base_of_v) + return std::for_each(__first, __first + __n2, __f); + else + { + while (__n2-->0) + { + __f(*__first); + ++__first; + } + return __first; + } + } +#endif // C++17 + /** * @brief Find the first occurrence of a value in a sequence. * @ingroup non_mutating_algorithms diff --git a/libstdc++-v3/include/bits/stl_numeric.h b/libstdc++-v3/include/bits/stl_numeric.h index e859c76bc44..387bed91174 100644 --- a/libstdc++-v3/include/bits/stl_numeric.h +++ b/libstdc++-v3/include/bits/stl_numeric.h @@ -60,12 +60,16 @@ #include #include // For _GLIBCXX_MOVE -#if __cplusplus >= 201103L namespace std _GLIBCXX_VISIBILITY(default) { _GLIBCXX_BEGIN_NAMESPACE_VERSION + /** @defgroup numeric_ops Generalized Numeric operations + * @ingroup algorithms + */ + +#if __cplusplus >= 201103L /** * @brief Create a range of sequentially increasing values. * @@ -76,6 +80,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION * @param __last End of range. * @param __value Starting value. * @return Nothing. + * @ingroup numeric_ops */ template void @@ -94,14 +99,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION ++__value; } } +#endif _GLIBCXX_END_NAMESPACE_VERSION -} // namespace std -#endif - -namespace std _GLIBCXX_VISIBILITY(default) -{ _GLIBCXX_BEGIN_NAMESPACE_ALGO #if __cplusplus > 201703L @@ -112,6 +113,9 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO # define _GLIBCXX_MOVE_IF_20(_E) _E #endif + /// @addtogroup numeric_ops + /// @{ + /** * @brief Accumulate values in a range. * @@ -139,8 +143,8 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO /** * @brief Accumulate values in a range with operation. * - * Accumulates the values in the range [first,last) using the function - * object @p __binary_op. The initial value is @p __init. The values are + * Accumulates the values in the range `[first,last)` using the function + * object `__binary_op`. The initial value is `__init`. The values are * processed in order. * * @param __first Start of range. @@ -390,6 +394,8 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO return ++__result; } + // @} group numeric_ops + #undef _GLIBCXX_MOVE_IF_20 _GLIBCXX_END_NAMESPACE_ALGO diff --git a/libstdc++-v3/include/std/numeric b/libstdc++-v3/include/std/numeric index 01e3ae8e35d..66792506d10 100644 --- a/libstdc++-v3/include/std/numeric +++ b/libstdc++-v3/include/std/numeric @@ -205,6 +205,472 @@ _GLIBCXX_END_NAMESPACE_VERSION #endif // C++14 #if __cplusplus > 201402L +#include + +namespace std _GLIBCXX_VISIBILITY(default) +{ +_GLIBCXX_BEGIN_NAMESPACE_VERSION + + /// @addtogroup numeric_ops + /// @{ + + /// @cond undocumented + template, + typename _Cat = typename _Traits::iterator_category> + using __is_random_access_iter + = is_base_of; + /// @endcond + + /** + * @brief Calculate reduction of values in a range. + * + * @param __first Start of range. + * @param __last End of range. + * @param __init Starting value to add other values to. + * @param __binary_op A binary function object. + * @return The final sum. + * + * Reduce the values in the range `[first,last)` using a binary operation. + * The initial value is `init`. The values are not necessarily processed + * in order. + * + * This algorithm is similar to `std::accumulate` but is not required to + * perform the operations in order from first to last. For operations + * that are commutative and associative the result will be the same as + * for `std::accumulate`, but for other operations (such as floating point + * arithmetic) the result can be different. + */ + template + _Tp + reduce(_InputIterator __first, _InputIterator __last, _Tp __init, + _BinaryOperation __binary_op) + { + using value_type = typename iterator_traits<_InputIterator>::value_type; + static_assert(is_invocable_r_v<_Tp, _BinaryOperation, _Tp&, _Tp&>); + static_assert(is_convertible_v); + if constexpr (__is_random_access_iter<_InputIterator>::value) + { + while ((__last - __first) >= 4) + { + _Tp __v1 = __binary_op(__first[0], __first[1]); + _Tp __v2 = __binary_op(__first[2], __first[3]); + _Tp __v3 = __binary_op(__v1, __v2); + __init = __binary_op(__init, __v3); + __first += 4; + } + } + for (; __first != __last; ++__first) + __init = __binary_op(__init, *__first); + return __init; + } + + /** + * @brief Calculate reduction of values in a range. + * + * @param __first Start of range. + * @param __last End of range. + * @param __init Starting value to add other values to. + * @return The final sum. + * + * Reduce the values in the range `[first,last)` using addition. + * Equivalent to calling std::reduce(first, last, init, std::plus<>())`. + */ + template + inline _Tp + reduce(_InputIterator __first, _InputIterator __last, _Tp __init) + { return std::reduce(__first, __last, __init, plus<>()); } + + /** + * @brief Calculate reduction of values in a range. + * + * @param __first Start of range. + * @param __last End of range. + * @return The final sum. + * + * Reduce the values in the range `[first,last)` using addition, with + * an initial value of `T{}`, where `T` is the iterator's value type. + * Equivalent to calling std::reduce(first, last, T{}, std::plus<>())`. + */ + template + inline typename iterator_traits<_InputIterator>::value_type + reduce(_InputIterator __first, _InputIterator __last) + { + using value_type = typename iterator_traits<_InputIterator>::value_type; + return std::reduce(__first, __last, value_type{}, plus<>()); + } + + /** + * @brief Combine elements from two ranges and reduce + * + * @param __first1 Start of first range. + * @param __last1 End of first range. + * @param __first2 Start of second range. + * @param __init Starting value to add other values to. + * @param __binary_op1 The function used to perform reduction. + * @param __binary_op2 The function used to combine values from the ranges. + * @return The final sum. + * + * Call `binary_op2(first1[n],first2[n])` for each `n` in `[0,last1-first1)` + * and then use `binary_op1` to reduce the values returned by `binary_op2` + * to a single value of type `T`. + * + * The range beginning at `first2` must contain at least `last1-first1` + * elements. + */ + template + _Tp + transform_reduce(_InputIterator1 __first1, _InputIterator1 __last1, + _InputIterator2 __first2, _Tp __init, + _BinaryOperation1 __binary_op1, + _BinaryOperation2 __binary_op2) + { + if constexpr (__and_v<__is_random_access_iter<_InputIterator1>, + __is_random_access_iter<_InputIterator2>>) + { + while ((__last1 - __first1) >= 4) + { + _Tp __v1 = __binary_op1(__binary_op2(__first1[0], __first2[0]), + __binary_op2(__first1[1], __first2[1])); + _Tp __v2 = __binary_op1(__binary_op2(__first1[2], __first2[2]), + __binary_op2(__first1[3], __first2[3])); + _Tp __v3 = __binary_op1(__v1, __v2); + __init = __binary_op1(__init, __v3); + __first1 += 4; + __first2 += 4; + } + } + for (; __first1 != __last1; ++__first1, (void) ++__first2) + __init = __binary_op1(__init, __binary_op2(*__first1, *__first2)); + return __init; + } + + /** + * @brief Combine elements from two ranges and reduce + * + * @param __first1 Start of first range. + * @param __last1 End of first range. + * @param __first2 Start of second range. + * @param __init Starting value to add other values to. + * @return The final sum. + * + * Call `first1[n]*first2[n]` for each `n` in `[0,last1-first1)` and then + * use addition to sum those products to a single value of type `T`. + * + * The range beginning at `first2` must contain at least `last1-first1` + * elements. + */ + template + inline _Tp + transform_reduce(_InputIterator1 __first1, _InputIterator1 __last1, + _InputIterator2 __first2, _Tp __init) + { + return std::transform_reduce(__first1, __last1, __first2, + std::move(__init), + plus<>(), multiplies<>()); + } + + /** + * @brief Transform the elements of a range and reduce + * + * @param __first Start of range. + * @param __last End of range. + * @param __init Starting value to add other values to. + * @param __binary_op The function used to perform reduction. + * @param __unary_op The function used to transform values from the range. + * @return The final sum. + * + * Call `unary_op(first[n])` for each `n` in `[0,last-first)` and then + * use `binary_op` to reduce the values returned by `unary_op` + * to a single value of type `T`. + */ + template + _Tp + transform_reduce(_InputIterator __first, _InputIterator __last, _Tp __init, + _BinaryOperation __binary_op, _UnaryOperation __unary_op) + { + if constexpr (__is_random_access_iter<_InputIterator>::value) + { + while ((__last - __first) >= 4) + { + _Tp __v1 = __binary_op(__unary_op(__first[0]), + __unary_op(__first[1])); + _Tp __v2 = __binary_op(__unary_op(__first[2]), + __unary_op(__first[3])); + _Tp __v3 = __binary_op(__v1, __v2); + __init = __binary_op(__init, __v3); + __first += 4; + } + } + for (; __first != __last; ++__first) + __init = __binary_op(__init, __unary_op(*__first)); + return __init; + } + + /** @brief Output the cumulative sum of one range to a second range + * + * @param __first Start of input range. + * @param __last End of input range. + * @param __result Start of output range. + * @param __init Initial value. + * @param __binary_op Function to perform summation. + * @return The end of the output range. + * + * Write the cumulative sum (aka prefix sum, aka scan) of the input range + * to the output range. Each element of the output range contains the + * running total of all earlier elements (and the initial value), + * using `binary_op` for summation. + * + * This function generates an "exclusive" scan, meaning the Nth element + * of the output range is the sum of the first N-1 input elements, + * so the Nth input element is not included. + */ + template + _OutputIterator + exclusive_scan(_InputIterator __first, _InputIterator __last, + _OutputIterator __result, _Tp __init, + _BinaryOperation __binary_op) + { + while (__first != __last) + { + auto __v = __init; + __init = __binary_op(__init, *__first); + ++__first; + *__result++ = std::move(__v); + } + return __result; + } + + /** @brief Output the cumulative sum of one range to a second range + * + * @param __first Start of input range. + * @param __last End of input range. + * @param __result Start of output range. + * @param __init Initial value. + * @return The end of the output range. + * + * Write the cumulative sum (aka prefix sum, aka scan) of the input range + * to the output range. Each element of the output range contains the + * running total of all earlier elements (and the initial value), + * using `std::plus<>` for summation. + * + * This function generates an "exclusive" scan, meaning the Nth element + * of the output range is the sum of the first N-1 input elements, + * so the Nth input element is not included. + */ + template + inline _OutputIterator + exclusive_scan(_InputIterator __first, _InputIterator __last, + _OutputIterator __result, _Tp __init) + { + return std::exclusive_scan(__first, __last, __result, std::move(__init), + plus<>()); + } + + /** @brief Output the cumulative sum of one range to a second range + * + * @param __first Start of input range. + * @param __last End of input range. + * @param __result Start of output range. + * @param __binary_op Function to perform summation. + * @param __init Initial value. + * @return The end of the output range. + * + * Write the cumulative sum (aka prefix sum, aka scan) of the input range + * to the output range. Each element of the output range contains the + * running total of all earlier elements (and the initial value), + * using `binary_op` for summation. + * + * This function generates an "inclusive" scan, meaning the Nth element + * of the output range is the sum of the first N input elements, + * so the Nth input element is included. + */ + template + _OutputIterator + inclusive_scan(_InputIterator __first, _InputIterator __last, + _OutputIterator __result, _BinaryOperation __binary_op, + _Tp __init) + { + for (; __first != __last; ++__first) + *__result++ = __init = __binary_op(__init, *__first); + return __result; + } + + /** @brief Output the cumulative sum of one range to a second range + * + * @param __first Start of input range. + * @param __last End of input range. + * @param __result Start of output range. + * @param __binary_op Function to perform summation. + * @return The end of the output range. + * + * Write the cumulative sum (aka prefix sum, aka scan) of the input range + * to the output range. Each element of the output range contains the + * running total of all earlier elements, using `binary_op` for summation. + * + * This function generates an "inclusive" scan, meaning the Nth element + * of the output range is the sum of the first N input elements, + * so the Nth input element is included. + */ + template + _OutputIterator + inclusive_scan(_InputIterator __first, _InputIterator __last, + _OutputIterator __result, _BinaryOperation __binary_op) + { + if (__first != __last) + { + auto __init = *__first; + *__result++ = __init; + ++__first; + if (__first != __last) + __result = std::inclusive_scan(__first, __last, __result, + __binary_op, std::move(__init)); + } + return __result; + } + + /** @brief Output the cumulative sum of one range to a second range + * + * @param __first Start of input range. + * @param __last End of input range. + * @param __result Start of output range. + * @return The end of the output range. + * + * Write the cumulative sum (aka prefix sum, aka scan) of the input range + * to the output range. Each element of the output range contains the + * running total of all earlier elements, using `std::plus<>` for summation. + * + * This function generates an "inclusive" scan, meaning the Nth element + * of the output range is the sum of the first N input elements, + * so the Nth input element is included. + */ + template + inline _OutputIterator + inclusive_scan(_InputIterator __first, _InputIterator __last, + _OutputIterator __result) + { return std::inclusive_scan(__first, __last, __result, plus<>()); } + + /** @brief Output the cumulative sum of one range to a second range + * + * @param __first Start of input range. + * @param __last End of input range. + * @param __result Start of output range. + * @param __init Initial value. + * @param __binary_op Function to perform summation. + * @param __unary_op Function to transform elements of the input range. + * @return The end of the output range. + * + * Write the cumulative sum (aka prefix sum, aka scan) of the input range + * to the output range. Each element of the output range contains the + * running total of all earlier elements (and the initial value), + * using `__unary_op` to transform the input elements + * and using `__binary_op` for summation. + * + * This function generates an "exclusive" scan, meaning the Nth element + * of the output range is the sum of the first N-1 input elements, + * so the Nth input element is not included. + */ + template + _OutputIterator + transform_exclusive_scan(_InputIterator __first, _InputIterator __last, + _OutputIterator __result, _Tp __init, + _BinaryOperation __binary_op, + _UnaryOperation __unary_op) + { + while (__first != __last) + { + auto __v = __init; + __init = __binary_op(__init, __unary_op(*__first)); + ++__first; + *__result++ = std::move(__v); + } + return __result; + } + + /** @brief Output the cumulative sum of one range to a second range + * + * @param __first Start of input range. + * @param __last End of input range. + * @param __result Start of output range. + * @param __binary_op Function to perform summation. + * @param __unary_op Function to transform elements of the input range. + * @param __init Initial value. + * @return The end of the output range. + * + * Write the cumulative sum (aka prefix sum, aka scan) of the input range + * to the output range. Each element of the output range contains the + * running total of all earlier elements (and the initial value), + * using `__unary_op` to transform the input elements + * and using `__binary_op` for summation. + * + * This function generates an "inclusive" scan, meaning the Nth element + * of the output range is the sum of the first N input elements, + * so the Nth input element is included. + */ + template + _OutputIterator + transform_inclusive_scan(_InputIterator __first, _InputIterator __last, + _OutputIterator __result, + _BinaryOperation __binary_op, + _UnaryOperation __unary_op, + _Tp __init) + { + for (; __first != __last; ++__first) + *__result++ = __init = __binary_op(__init, __unary_op(*__first)); + return __result; + } + + /** @brief Output the cumulative sum of one range to a second range + * + * @param __first Start of input range. + * @param __last End of input range. + * @param __result Start of output range. + * @param __binary_op Function to perform summation. + * @param __unary_op Function to transform elements of the input range. + * @return The end of the output range. + * + * Write the cumulative sum (aka prefix sum, aka scan) of the input range + * to the output range. Each element of the output range contains the + * running total of all earlier elements, + * using `__unary_op` to transform the input elements + * and using `__binary_op` for summation. + * + * This function generates an "inclusive" scan, meaning the Nth element + * of the output range is the sum of the first N input elements, + * so the Nth input element is included. + */ + template + _OutputIterator + transform_inclusive_scan(_InputIterator __first, _InputIterator __last, + _OutputIterator __result, + _BinaryOperation __binary_op, + _UnaryOperation __unary_op) + { + if (__first != __last) + { + auto __init = __unary_op(*__first); + *__result++ = __init; + ++__first; + if (__first != __last) + __result = std::transform_inclusive_scan(__first, __last, __result, + __binary_op, __unary_op, + std::move(__init)); + } + return __result; + } + + // @} group numeric_ops + +_GLIBCXX_END_NAMESPACE_VERSION +} // namespace std + // Parallel STL algorithms # if _PSTL_EXECUTION_POLICIES_DEFINED // If has already been included, pull in implementations diff --git a/libstdc++-v3/testsuite/25_algorithms/for_each/for_each_n.cc b/libstdc++-v3/testsuite/25_algorithms/for_each/for_each_n.cc new file mode 100644 index 00000000000..57c2bbe6d36 --- /dev/null +++ b/libstdc++-v3/testsuite/25_algorithms/for_each/for_each_n.cc @@ -0,0 +1,57 @@ +// { dg-options "-std=gnu++17" } +// { dg-do run { target c++17 } } + +// Copyright (C) 2019 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// . + +#include +#include +#include + +void test01() +{ + using __gnu_test::test_container; + using __gnu_test::input_iterator_wrapper; + int array[5] = { 1, 2, 3, 4, 5 }; + test_container con(array); + + int sum = 0; + struct Func + { + Func(int& i) : i(i) { } + Func(Func&&) = default; + Func& operator=(Func&&) = delete; + void operator()(int n) const { i += n; } + int& i; + }; + + struct Size + { + Size(short v) : val(v) { } + operator short() const { return val; } + short val; + }; + auto res = std::for_each_n(con.begin(), Size(con.size()), Func(sum)); + + VERIFY( res.ptr == con.end().ptr ); + VERIFY( sum == 15 ); +} + +int main() +{ + test01(); +} diff --git a/libstdc++-v3/testsuite/26_numerics/exclusive_scan/1.cc b/libstdc++-v3/testsuite/26_numerics/exclusive_scan/1.cc new file mode 100644 index 00000000000..05a0135d7ab --- /dev/null +++ b/libstdc++-v3/testsuite/26_numerics/exclusive_scan/1.cc @@ -0,0 +1,94 @@ +// { dg-options "-std=gnu++17" } +// { dg-do run { target c++17 } } + +// Copyright (C) 2019 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// . + +// C++17 29.8.7 [exclusive.scan] + +#include +#include +#include +#include + +int a[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; + +using __gnu_test::test_container; +using __gnu_test::input_iterator_wrapper; +using __gnu_test::output_iterator_wrapper; + +/* +template + OutputIterator + exclusive_scan(InputIterator, InputIterator, OutputIterator, T); +*/ +void +test01() +{ + int out[10]; + test_container co(out); + test_container ca(a); + auto end = std::exclusive_scan(ca.begin(), ca.end(), co.begin(), 5); + static_assert(std::is_same_v); + VERIFY( end.ptr == out+10 ); + VERIFY( out[0] == 5 ); + VERIFY( out[1] == 6 ); + VERIFY( out[2] == 8 ); + VERIFY( out[3] == 11 ); + VERIFY( out[4] == 15 ); + VERIFY( out[5] == 20 ); + VERIFY( out[6] == 26 ); + VERIFY( out[7] == 33 ); + VERIFY( out[8] == 41 ); + VERIFY( out[9] == 50 ); +} + +/* +template + OutputIterator + exclusive_scan(InputIterator, InputIterator, OutputIterator, T, + BinaryOperation); +*/ +void +test02() +{ + int out[10]; + test_container co(out); + test_container ca(a); + auto end = std::exclusive_scan(ca.begin(), ca.end(), co.begin(), 2, + [](int i, int j) { return 2*i + 2*j; }); + static_assert(std::is_same_v); + VERIFY( end.ptr == out+10 ); + VERIFY( out[0] == 2 ); + VERIFY( out[1] == 6 ); + VERIFY( out[2] == 16 ); + VERIFY( out[3] == 38 ); + VERIFY( out[4] == 84 ); + VERIFY( out[5] == 178 ); + VERIFY( out[6] == 368 ); + VERIFY( out[7] == 750 ); + VERIFY( out[8] == 1516 ); + VERIFY( out[9] == 3050 ); +} + +int +main() +{ + test01(); + test02(); +} diff --git a/libstdc++-v3/testsuite/26_numerics/inclusive_scan/1.cc b/libstdc++-v3/testsuite/26_numerics/inclusive_scan/1.cc new file mode 100644 index 00000000000..68f1578928c --- /dev/null +++ b/libstdc++-v3/testsuite/26_numerics/inclusive_scan/1.cc @@ -0,0 +1,123 @@ +// { dg-options "-std=gnu++17" } +// { dg-do run { target c++17 } } + +// Copyright (C) 2019 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// . + +// C++17 29.8.8 [inclusive.scan] + +#include +#include +#include +#include + +int a[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; + +using __gnu_test::test_container; +using __gnu_test::input_iterator_wrapper; +using __gnu_test::output_iterator_wrapper; + +/* +template + OutputIterator + inclusive_scan(InputIterator, InputIterator, OutputIterator); +*/ +void +test01() +{ + int out[10]; + test_container co(out); + test_container ca(a); + auto end = std::inclusive_scan(ca.begin(), ca.end(), co.begin()); + static_assert(std::is_same_v); + VERIFY( end.ptr == out+10 ); + VERIFY( out[0] == 1 ); + VERIFY( out[1] == (1+2) ); + VERIFY( out[2] == (1+2+3) ); + VERIFY( out[3] == (1+2+3+4) ); + VERIFY( out[4] == (1+2+3+4+5) ); + VERIFY( out[5] == (1+2+3+4+5+6) ); + VERIFY( out[6] == (1+2+3+4+5+6+7) ); + VERIFY( out[7] == (1+2+3+4+5+6+7+8) ); + VERIFY( out[8] == (1+2+3+4+5+6+7+8+9) ); + VERIFY( out[9] == (1+2+3+4+5+6+7+8+9+10) ); +} + +/* +template + OutputIterator + inclusive_scan(InputIterator, InputIterator, OutputIterator, + BinaryOperation); +*/ +void +test02() +{ + int out[10]; + test_container co(out); + test_container ca(a); + auto end = std::inclusive_scan(ca.begin(), ca.end(), co.begin(), + [](int i, int j) { return 2*i + 2*j; }); + static_assert(std::is_same_v); + VERIFY( end.ptr == out+10 ); + VERIFY( out[0] == 1 ); + VERIFY( out[1] == (2*1+2*2) ); + VERIFY( out[2] == (2*6+2*3) ); + VERIFY( out[3] == (2*18+2*4) ); + VERIFY( out[4] == (2*44+2*5) ); + VERIFY( out[5] == (2*98+2*6)); + VERIFY( out[6] == (2*208+2*7) ); + VERIFY( out[7] == (2*430+2*8) ); + VERIFY( out[8] == (2*876+2*9) ); + VERIFY( out[9] == (2*1770+2*10) ); +} + +/* +template + OutputIterator + inclusive_scan(InputIterator, InputIterator, OutputIterator, + BinaryOperation, T); +*/ +void +test03() +{ + int out[10]; + test_container co(out); + test_container ca(a); + auto end = std::inclusive_scan(ca.begin(), ca.end(), co.begin(), + [](int i, int j) { return 2*i + 2*j; }, + 1); + static_assert(std::is_same_v); + VERIFY( end.ptr == out+10 ); + VERIFY( out[0] == 4 ); + VERIFY( out[1] == (2*4+2*2) ); + VERIFY( out[2] == (2*12+2*3) ); + VERIFY( out[3] == (2*30+2*4) ); + VERIFY( out[4] == (2*68+2*5) ); + VERIFY( out[5] == (2*146+2*6) ); + VERIFY( out[6] == (2*304+2*7)); + VERIFY( out[7] == (2*622+2*8) ); + VERIFY( out[8] == (2*1260+2*9) ); + VERIFY( out[9] == (2*2538+2*10) ); +} + +int +main() +{ + test01(); + test02(); + test03(); +} diff --git a/libstdc++-v3/testsuite/26_numerics/reduce/1.cc b/libstdc++-v3/testsuite/26_numerics/reduce/1.cc new file mode 100644 index 00000000000..0434d2ecf49 --- /dev/null +++ b/libstdc++-v3/testsuite/26_numerics/reduce/1.cc @@ -0,0 +1,82 @@ +// { dg-options "-std=gnu++17" } +// { dg-do run { target c++17 } } + +// Copyright (C) 2019 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// . + +// C++17 29.8.3 [reduce] + +#include +#include +#include +#include + +/* +template + iterator_traits::value_type + reduce(InputIterator, InputIterator); +*/ +void +test01() +{ + using __gnu_test::test_container; + using __gnu_test::input_iterator_wrapper; + int array[5] = { 1, 2, 3, 4, 5 }; + test_container con(array); + int res = std::reduce(con.begin(), con.end()); + VERIFY( res == 15 ); +} + +/* +template + T reduce(InputIterator, InputIterator, T); +*/ +void +test02() +{ + bool b[] = {true, false, true, true, false, true, false, true, true, false}; + int res = std::reduce(std::begin(b), std::end(b), 100); + VERIFY( res == 106 ); +} + +/* +template + T reduce(InputIterator, InputIterator, T); +template + T reduce(InputIterator, InputIterator, T, BinaryOperation); +*/ +void +test03() +{ + int a[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; + + auto res = std::reduce(std::begin(a), std::end(a), (short)11); + static_assert(std::is_same_v); + VERIFY( res == 66 ); + + auto res2 = std::reduce(std::begin(a), std::end(a), -1l, std::multiplies<>()); + static_assert(std::is_same_v); + VERIFY( res2 == -3628800 ); +} + +int +main() +{ + test01(); + test02(); + test03(); +} diff --git a/libstdc++-v3/testsuite/26_numerics/transform_exclusive_scan/1.cc b/libstdc++-v3/testsuite/26_numerics/transform_exclusive_scan/1.cc new file mode 100644 index 00000000000..61dca6af6ac --- /dev/null +++ b/libstdc++-v3/testsuite/26_numerics/transform_exclusive_scan/1.cc @@ -0,0 +1,65 @@ +// { dg-options "-std=gnu++17" } +// { dg-do run { target c++17 } } + +// Copyright (C) 2019 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// . + +// C++17 29.8.9 [transform.exclusive.scan] + +#include +#include +#include +#include + +int a[] = {1, 2, 3, 4, 5, 6, 7}; + +using __gnu_test::test_container; +using __gnu_test::input_iterator_wrapper; +using __gnu_test::output_iterator_wrapper; + +/* +template + OutputIterator + transform_exclusive_scan(InputIterator, InputIterator, OutputIterator, T, + BinaryOperation, UnaryOperation); +*/ +void +test01() +{ + int out[7]; + test_container co(out); + test_container ca(a); + auto end = std::transform_exclusive_scan(ca.begin(), ca.end(), co.begin(), 5, + std::multiplies<>(), + std::negate<>()); + static_assert(std::is_same_v); + VERIFY( end.ptr == out+7 ); + VERIFY( out[0] == 5 ); + VERIFY( out[1] == -5 ); + VERIFY( out[2] == 10 ); + VERIFY( out[3] == -30 ); + VERIFY( out[4] == 120 ); + VERIFY( out[5] == -600 ); + VERIFY( out[6] == 3600 ); +} + +int +main() +{ + test01(); +} diff --git a/libstdc++-v3/testsuite/26_numerics/transform_inclusive_scan/1.cc b/libstdc++-v3/testsuite/26_numerics/transform_inclusive_scan/1.cc new file mode 100644 index 00000000000..16eeedb58ee --- /dev/null +++ b/libstdc++-v3/testsuite/26_numerics/transform_inclusive_scan/1.cc @@ -0,0 +1,94 @@ +// { dg-options "-std=gnu++17" } +// { dg-do run { target c++17 } } + +// Copyright (C) 2019 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// . + +// C++17 29.8.10 [transform.inclusive.scan] + +#include +#include +#include +#include + +int a[] = {1, 2, 3, 4, 5, 6, 7}; + +using __gnu_test::test_container; +using __gnu_test::input_iterator_wrapper; +using __gnu_test::output_iterator_wrapper; + +/* +template + OutputIterator + transform_inclusive_scan(InputIterator, InputIterator, OutputIterator, + BinaryOperation, UnaryOperation); +*/ +void +test01() +{ + int out[7]; + test_container co(out); + test_container ca(a); + auto end = std::transform_inclusive_scan(ca.begin(), ca.end(), co.begin(), + std::multiplies<>(), + [](int i) { return i+1; }); + static_assert(std::is_same_v); + VERIFY( end.ptr == out+7 ); + VERIFY( out[0] == 2 ); + VERIFY( out[1] == (2*3) ); + VERIFY( out[2] == (2*3*4) ); + VERIFY( out[3] == (2*3*4*5) ); + VERIFY( out[4] == (2*3*4*5*6) ); + VERIFY( out[5] == (2*3*4*5*6*7) ); + VERIFY( out[6] == (2*3*4*5*6*7*8) ); +} + +/* +template + OutputIterator + transform_inclusive_scan(InputIterator, InputIterator, OutputIterator, + BinaryOperation, UnaryOperation, T); +*/ +void +test02() +{ + int out[7]; + test_container co(out); + test_container ca(a); + auto end = std::transform_inclusive_scan(ca.begin(), ca.end(), co.begin(), + std::multiplies<>(), + [](int i) { return i+1; }, + 3); + static_assert(std::is_same_v); + VERIFY( end.ptr == out+7 ); + VERIFY( out[0] == 3*2 ); + VERIFY( out[1] == (3*2*3) ); + VERIFY( out[2] == (3*2*3*4) ); + VERIFY( out[3] == (3*2*3*4*5) ); + VERIFY( out[4] == (3*2*3*4*5*6) ); + VERIFY( out[5] == (3*2*3*4*5*6*7) ); + VERIFY( out[6] == (3*2*3*4*5*6*7*8) ); +} + +int +main() +{ + test01(); + test02(); +} diff --git a/libstdc++-v3/testsuite/26_numerics/transform_reduce/1.cc b/libstdc++-v3/testsuite/26_numerics/transform_reduce/1.cc new file mode 100644 index 00000000000..bb9a5bbce7e --- /dev/null +++ b/libstdc++-v3/testsuite/26_numerics/transform_reduce/1.cc @@ -0,0 +1,109 @@ +// { dg-options "-std=gnu++17" } +// { dg-do run { target c++17 } } + +// Copyright (C) 2019 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// . + +// C++17 29.8.5 [transform.reduce] + +#include +#include +#include +#include + +int a[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; +double b[] = {0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5}; + +using __gnu_test::test_container; +using __gnu_test::input_iterator_wrapper; + +/* +template + T transform_reduce(InputIterator1, InputIterator1, InputIterator2, T); +*/ +void +test01() +{ + auto res = std::transform_reduce(std::begin(a), std::end(a), std::begin(b), + 1.0f); + static_assert(std::is_same_v); + VERIFY( res == (float)(1 + 0.5 + 1 + 1.5 + 2 + 2.5 + 3 + 3.5 + 4 + 4.5 + 5) ); + + test_container ca(a); + test_container cb(b); + + auto res2 = std::transform_reduce(ca.begin(), ca.end(), cb.begin(), + 1.0f); + static_assert(std::is_same_v); + VERIFY( res2 == res ); +} + +/* +template + T transform_reduce(InputIterator1, InputIterator1, InputIterator2, T, + BinaryOperation1, BinaryOperation2); +*/ +void +test02() +{ + auto res = std::transform_reduce(std::begin(a), std::end(a), std::begin(b), + 1L, std::multiplies<>(), std::plus()); + static_assert(std::is_same_v); + VERIFY( res == (1L * 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10) ); + + test_container ca(a); + test_container cb(b); + + auto res2 = std::transform_reduce(ca.begin(), ca.end(), cb.begin(), + 1L, std::multiplies<>(), std::plus()); + static_assert(std::is_same_v); + VERIFY( res2 == res ); +} + +/* +template + T transform_reduce(InputIterator, InputIterator, T, + BinaryOperation, UnaryOperation); +*/ +void +test03() +{ + auto res = std::transform_reduce(std::begin(a), std::end(a), 10.0, + std::plus<>(), + [](int i) { return i * i; }); + static_assert(std::is_same_v); + VERIFY( res == (10.0 + 1 + 4 + 9 + 16 + 25 + 36 + 49 + 64 + 81 + 100) ); + + test_container ca(a); + test_container cb(b); + + auto res2 = std::transform_reduce(ca.begin(), ca.end(), 10.0, + std::plus<>(), + [](int i) { return i * i; }); + static_assert(std::is_same_v); + VERIFY( res2 == (10.0 + 1 + 4 + 9 + 16 + 25 + 36 + 49 + 64 + 81 + 100) ); +} + +int +main() +{ + test01(); + test02(); + test03(); +} diff --git a/libstdc++-v3/testsuite/util/testsuite_iterators.h b/libstdc++-v3/testsuite/util/testsuite_iterators.h index 4636d9995c1..ac646a59cb8 100644 --- a/libstdc++-v3/testsuite/util/testsuite_iterators.h +++ b/libstdc++-v3/testsuite/util/testsuite_iterators.h @@ -589,6 +589,10 @@ namespace __gnu_test ItType end() { return it(bounds.last); } + + std::size_t + size() const + { return bounds.last - bounds.first; } }; } #endif -- 2.30.2