Implement the non-parallel versions of reduce and transform_reduce for C++17

llvm-svn: 305365

6 files changed, 520 insertions, 0 deletions

diff --git a/libcxx/test/std/numerics/numeric.ops/reduce/reduce_iter_iter.pass.cpp b/libcxx/test/std/numerics/numeric.ops/reduce/reduce_iter_iter.pass.cpp
new file mode 100644
index 00000000000..aa055e70d4f
--- /dev/null
+++ b/libcxx/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.
+//
+//===----------------------------------------------------------------------===//
+
+// <numeric>
+// UNSUPPORTED: c++98, c++03, c++11, c++14
+
+// template<class InputIterator>
+//     typename iterator_traits<InputIterator>::value_type
+//     reduce(InputIterator first, InputIterator last);
+
+#include <numeric>
+#include <cassert>
+
+#include "test_iterators.h"
+
+template <class Iter, class T>
+void
+test(Iter first, Iter last, T x)
+{
+    static_assert( std::is_same_v<typename std::iterator_traits<decltype(first)>::value_type,
+                                decltype(std::reduce(first, last))> );
+    assert(std::reduce(first, last) == x);
+}
+
+template <class Iter>
+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 <typename T>
+void test_return_type()
+{
+    T *p = nullptr;
+    static_assert( std::is_same_v<T, decltype(std::reduce(p, p))> );
+}
+
+int main()
+{
+    test_return_type<char>();
+    test_return_type<int>();
+    test_return_type<unsigned long>();
+    test_return_type<float>();
+    test_return_type<double>();
+
+    test<input_iterator<const int*> >();
+    test<forward_iterator<const int*> >();
+    test<bidirectional_iterator<const int*> >();
+    test<random_access_iterator<const int*> >();
+    test<const int*>();
+}
diff --git a/libcxx/test/std/numerics/numeric.ops/reduce/reduce_iter_iter_T.pass.cpp b/libcxx/test/std/numerics/numeric.ops/reduce/reduce_iter_iter_T.pass.cpp
new file mode 100644
index 00000000000..480ead11c73
--- /dev/null
+++ b/libcxx/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.
+//
+//===----------------------------------------------------------------------===//
+
+// <numeric>
+// UNSUPPORTED: c++98, c++03, c++11, c++14
+
+// template<class InputIterator, class T>
+//   T reduce(InputIterator first, InputIterator last, T init);
+
+#include <numeric>
+#include <cassert>
+
+#include "test_iterators.h"
+
+template <class Iter, class T>
+void
+test(Iter first, Iter last, T init, T x)
+{
+    static_assert( std::is_same_v<T, decltype(std::reduce(first, last, init))> );
+    assert(std::reduce(first, last, init) == x);
+}
+
+template <class Iter>
+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 <typename T, typename Init>
+void test_return_type()
+{
+    T *p = nullptr;
+    static_assert( std::is_same_v<Init, decltype(std::reduce(p, p, Init{}))> );
+}
+
+int main()
+{
+    test_return_type<char, int>();
+    test_return_type<int, int>();
+    test_return_type<int, unsigned long>();
+    test_return_type<float, int>();
+    test_return_type<short, float>();
+    test_return_type<double, char>();
+    test_return_type<char, double>();
+
+    test<input_iterator<const int*> >();
+    test<forward_iterator<const int*> >();
+    test<bidirectional_iterator<const int*> >();
+    test<random_access_iterator<const int*> >();
+    test<const int*>();
+}
diff --git a/libcxx/test/std/numerics/numeric.ops/reduce/reduce_iter_iter_T_op.pass.cpp b/libcxx/test/std/numerics/numeric.ops/reduce/reduce_iter_iter_T_op.pass.cpp
new file mode 100644
index 00000000000..5238a1f2ed5
--- /dev/null
+++ b/libcxx/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.
+//
+//===----------------------------------------------------------------------===//
+
+// <numeric>
+// UNSUPPORTED: c++98, c++03, c++11, c++14
+
+// template<class InputIterator, class T, class BinaryOperation>
+//   T reduce(InputIterator first, InputIterator last, T init, BinaryOperation op);
+  
+#include <numeric>
+#include <cassert>
+
+#include "test_iterators.h"
+
+template <class Iter, class T, class Op>
+void
+test(Iter first, Iter last, T init, Op op, T x)
+{
+    static_assert( std::is_same_v<T, decltype(std::reduce(first, last, init, op))>, "" );
+    assert(std::reduce(first, last, init, op) == x);
+}
+
+template <class Iter>
+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 <typename T, typename Init>
+void test_return_type()
+{
+    T *p = nullptr;
+    static_assert( std::is_same_v<Init, decltype(std::reduce(p, p, Init{}, std::plus<>()))>, "" );
+}
+
+int main()
+{
+    test_return_type<char, int>();
+    test_return_type<int, int>();
+    test_return_type<int, unsigned long>();
+    test_return_type<float, int>();
+    test_return_type<short, float>();
+    test_return_type<double, char>();
+    test_return_type<char, double>();
+
+    test<input_iterator<const int*> >();
+    test<forward_iterator<const int*> >();
+    test<bidirectional_iterator<const int*> >();
+    test<random_access_iterator<const int*> >();
+    test<const int*>();
+
+//	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
+    }
+}
diff --git a/libcxx/test/std/numerics/numeric.ops/transform.reduce/transform_reduce_iter_iter_init_bop_uop.pass.cpp b/libcxx/test/std/numerics/numeric.ops/transform.reduce/transform_reduce_iter_iter_init_bop_uop.pass.cpp
new file mode 100644
index 00000000000..c283f3e2972
--- /dev/null
+++ b/libcxx/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.
+//
+//===----------------------------------------------------------------------===//
+
+// <numeric>
+// UNSUPPORTED: c++98, c++03, c++11, c++14
+
+// template <class InputIterator1, class T,
+//           class BinaryOperation, class UnaryOperation>
+//    T transform_reduce(InputIterator1 first1, InputIterator1 last1,
+//                       T init, BinaryOperation binary_op, UnaryOperation unary_op);
+//                      
+  
+#include <numeric>
+#include <cassert>
+
+#include "test_iterators.h"
+
+template <class _Tp = void>
+struct identity : std::unary_function<_Tp, _Tp>
+{
+    constexpr const _Tp& operator()(const _Tp& __x) const { return __x;}
+};
+
+template <>
+struct identity<void>
+{
+    template <class _Tp>
+    constexpr auto operator()(_Tp&& __x) const
+    _NOEXCEPT_(noexcept(_VSTD::forward<_Tp>(__x)))
+    -> decltype        (_VSTD::forward<_Tp>(__x))
+        { return        _VSTD::forward<_Tp>(__x); }
+};
+
+
+template <class _Tp = void>
+struct twice
+{
+  	constexpr const _Tp operator()(const _Tp& __x) const noexcept { return 2 * __x; }
+};
+
+template <>
+struct twice<void>
+{
+    template <class _Tp>
+    constexpr auto operator()(const _Tp& __x) const
+    _NOEXCEPT_(noexcept(2 * __x))
+    -> decltype        (2 * __x)
+        { return        2 * __x; }
+};
+
+template <class Iter1, class T, class BOp, class UOp>
+void
+test(Iter1 first1, Iter1 last1, T init, BOp bOp, UOp uOp, T x)
+{
+    static_assert( std::is_same_v<T, 
+                    decltype(std::transform_reduce(first1, last1, init, bOp, uOp))> );
+    assert(std::transform_reduce(first1, last1, init, bOp, uOp) == x);
+}
+
+template <class Iter>
+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 <typename T, typename Init>
+void test_return_type()
+{
+    T *p = nullptr;
+    static_assert( std::is_same_v<Init, 
+         decltype(std::transform_reduce(p, p, Init{}, std::plus<>(), identity<>()))> );
+}
+
+int main()
+{
+    test_return_type<char, int>();
+    test_return_type<int, int>();
+    test_return_type<int, unsigned long>();
+    test_return_type<float, int>();
+    test_return_type<short, float>();
+    test_return_type<double, char>();
+    test_return_type<char, double>();
+
+//  All the iterator categories
+    test<input_iterator        <const int*> >();
+    test<forward_iterator      <const int*> >();
+    test<bidirectional_iterator<const int*> >();
+    test<random_access_iterator<const int*> >();
+    test<const int*>();
+    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
+    }
+}
diff --git a/libcxx/test/std/numerics/numeric.ops/transform.reduce/transform_reduce_iter_iter_iter_init.pass.cpp b/libcxx/test/std/numerics/numeric.ops/transform.reduce/transform_reduce_iter_iter_iter_init.pass.cpp
new file mode 100644
index 00000000000..f36b7d49410
--- /dev/null
+++ b/libcxx/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.
+//
+//===----------------------------------------------------------------------===//
+
+// <numeric>
+// UNSUPPORTED: c++98, c++03, c++11, c++14
+
+// template <class InputIterator1, class InputIterator2, class T>
+//   T transform_reduce(InputIterator1 first1, InputIterator1 last1,
+//                      InputIterator2 first2, T init);
+
+
+#include <numeric>
+#include <cassert>
+
+#include "test_iterators.h"
+
+template <class Iter1, class Iter2, class T>
+void
+test(Iter1 first1, Iter1 last1, Iter2 first2, T init, T x)
+{
+    static_assert( std::is_same_v<T, 
+            decltype(std::transform_reduce(first1, last1, first2, init))> );
+    assert(std::transform_reduce(first1, last1, first2, init) == x);
+}
+
+template <class SIter, class UIter>
+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 <typename T, typename Init>
+void test_return_type()
+{
+    T *p = nullptr;
+    static_assert( std::is_same_v<Init, 
+                       decltype(std::transform_reduce(p, p, p, Init{}))> );
+}
+
+int main()
+{
+    test_return_type<char, int>();
+    test_return_type<int, int>();
+    test_return_type<int, unsigned long>();
+    test_return_type<float, int>();
+    test_return_type<short, float>();
+    test_return_type<double, char>();
+    test_return_type<char, double>();
+
+//  All the iterator categories
+    test<input_iterator        <const int*>, input_iterator        <const unsigned int*> >();
+    test<input_iterator        <const int*>, forward_iterator      <const unsigned int*> >();
+    test<input_iterator        <const int*>, bidirectional_iterator<const unsigned int*> >();
+    test<input_iterator        <const int*>, random_access_iterator<const unsigned int*> >();
+
+    test<forward_iterator      <const int*>, input_iterator        <const unsigned int*> >();
+    test<forward_iterator      <const int*>, forward_iterator      <const unsigned int*> >();
+    test<forward_iterator      <const int*>, bidirectional_iterator<const unsigned int*> >();
+    test<forward_iterator      <const int*>, random_access_iterator<const unsigned int*> >();
+
+    test<bidirectional_iterator<const int*>, input_iterator        <const unsigned int*> >();
+    test<bidirectional_iterator<const int*>, forward_iterator      <const unsigned int*> >();
+    test<bidirectional_iterator<const int*>, bidirectional_iterator<const unsigned int*> >();
+    test<bidirectional_iterator<const int*>, random_access_iterator<const unsigned int*> >();
+
+    test<random_access_iterator<const int*>, input_iterator        <const unsigned int*> >();
+    test<random_access_iterator<const int*>, forward_iterator      <const unsigned int*> >();
+    test<random_access_iterator<const int*>, bidirectional_iterator<const unsigned int*> >();
+    test<random_access_iterator<const int*>, random_access_iterator<const unsigned int*> >();
+
+//  just plain pointers (const vs. non-const, too)
+    test<const int*, const unsigned int *>();
+    test<const int*,       unsigned int *>();
+    test<      int*, const unsigned int *>();
+    test<      int*,       unsigned int *>();
+}
diff --git a/libcxx/test/std/numerics/numeric.ops/transform.reduce/transform_reduce_iter_iter_iter_init_op_op.pass.cpp b/libcxx/test/std/numerics/numeric.ops/transform.reduce/transform_reduce_iter_iter_iter_init_op_op.pass.cpp
new file mode 100644
index 00000000000..b1b53293b99
--- /dev/null
+++ b/libcxx/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.
+//
+//===----------------------------------------------------------------------===//
+
+// <numeric>
+// UNSUPPORTED: c++98, c++03, c++11, c++14
+
+// template <class InputIterator1, class InputIterator2, class T,
+//           class BinaryOperation1, class BinaryOperation2>
+//    T transform_reduce(InputIterator1 first1, InputIterator1 last1,
+//                       InputIterator2 first2, T init,
+//                       BinaryOperation1 binary_op1, BinaryOperation2 binary_op2);
+//                      
+  
+#include <numeric>
+#include <cassert>
+
+#include "test_iterators.h"
+
+template <class Iter1, class Iter2, class T, class Op1, class Op2>
+void
+test(Iter1 first1, Iter1 last1, Iter2 first2, T init, Op1 op1, Op2 op2, T x)
+{
+    static_assert( std::is_same_v<T, 
+         decltype(std::transform_reduce(first1, last1, first2, init, op1, op2))> );
+    assert(std::transform_reduce(first1, last1, first2, init, op1, op2) == x);
+}
+
+template <class SIter, class UIter>
+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 <typename T, typename Init>
+void test_return_type()
+{
+    T *p = nullptr;
+    static_assert( std::is_same_v<Init, 
+       decltype(std::transform_reduce(p, p, p, Init{}, std::plus<>(), std::multiplies<>()))> );
+}
+
+int main()
+{
+    test_return_type<char, int>();
+    test_return_type<int, int>();
+    test_return_type<int, unsigned long>();
+    test_return_type<float, int>();
+    test_return_type<short, float>();
+    test_return_type<double, char>();
+    test_return_type<char, double>();
+
+//  All the iterator categories
+    test<input_iterator        <const int*>, input_iterator        <const unsigned int*> >();
+    test<input_iterator        <const int*>, forward_iterator      <const unsigned int*> >();
+    test<input_iterator        <const int*>, bidirectional_iterator<const unsigned int*> >();
+    test<input_iterator        <const int*>, random_access_iterator<const unsigned int*> >();
+
+    test<forward_iterator      <const int*>, input_iterator        <const unsigned int*> >();
+    test<forward_iterator      <const int*>, forward_iterator      <const unsigned int*> >();
+    test<forward_iterator      <const int*>, bidirectional_iterator<const unsigned int*> >();
+    test<forward_iterator      <const int*>, random_access_iterator<const unsigned int*> >();
+
+    test<bidirectional_iterator<const int*>, input_iterator        <const unsigned int*> >();
+    test<bidirectional_iterator<const int*>, forward_iterator      <const unsigned int*> >();
+    test<bidirectional_iterator<const int*>, bidirectional_iterator<const unsigned int*> >();
+    test<bidirectional_iterator<const int*>, random_access_iterator<const unsigned int*> >();
+
+    test<random_access_iterator<const int*>, input_iterator        <const unsigned int*> >();
+    test<random_access_iterator<const int*>, forward_iterator      <const unsigned int*> >();
+    test<random_access_iterator<const int*>, bidirectional_iterator<const unsigned int*> >();
+    test<random_access_iterator<const int*>, random_access_iterator<const unsigned int*> >();
+
+//  just plain pointers (const vs. non-const, too)
+    test<const int*, const unsigned int *>();
+    test<const int*,       unsigned int *>();
+    test<      int*, const unsigned int *>();
+    test<      int*,       unsigned int *>();
+}