xref: /llvm-project/pstl/test/std/algorithms/alg.modifying.operations/alg.partitions/partition.pass.cpp (revision 3b9a1bb1af90db9472340ef2122d3855eb9ba3fc)
13b62047bSLouis Dionne // -*- C++ -*-
23b62047bSLouis Dionne //===-- partition.pass.cpp ------------------------------------------------===//
33b62047bSLouis Dionne //
43b62047bSLouis Dionne // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
53b62047bSLouis Dionne // See https://llvm.org/LICENSE.txt for license information.
63b62047bSLouis Dionne // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
73b62047bSLouis Dionne //
83b62047bSLouis Dionne //===----------------------------------------------------------------------===//
93b62047bSLouis Dionne 
10b5e896c0SLouis Dionne // UNSUPPORTED: c++03, c++11, c++14
116ab35c9dSLouis Dionne 
123b62047bSLouis Dionne // Tests for stable_partition and partition
133b62047bSLouis Dionne #include "support/pstl_test_config.h"
143b62047bSLouis Dionne 
153b62047bSLouis Dionne #include <execution>
163b62047bSLouis Dionne #include <algorithm>
173b62047bSLouis Dionne #include <iterator>
183b62047bSLouis Dionne #include <type_traits>
193b62047bSLouis Dionne 
204d88b17bSLouis Dionne #include "support/utils.h"
214d88b17bSLouis Dionne 
223b62047bSLouis Dionne using namespace TestUtils;
233b62047bSLouis Dionne 
243b62047bSLouis Dionne template <typename T>
253b62047bSLouis Dionne struct DataType
263b62047bSLouis Dionne {
DataTypeDataType273b62047bSLouis Dionne     explicit DataType(int32_t k) : my_val(k) {}
DataTypeDataType283b62047bSLouis Dionne     DataType(DataType&& input) { my_val = std::move(input.my_val); }
293b62047bSLouis Dionne     DataType&
operator =DataType303b62047bSLouis Dionne     operator=(DataType&& input)
313b62047bSLouis Dionne     {
323b62047bSLouis Dionne         my_val = std::move(input.my_val);
333b62047bSLouis Dionne         return *this;
343b62047bSLouis Dionne     }
353b62047bSLouis Dionne     T
get_valDataType363b62047bSLouis Dionne     get_val() const
373b62047bSLouis Dionne     {
383b62047bSLouis Dionne         return my_val;
393b62047bSLouis Dionne     }
403b62047bSLouis Dionne 
413b62047bSLouis Dionne     friend std::ostream&
operator <<(std::ostream & stream,const DataType<T> & input)423b62047bSLouis Dionne     operator<<(std::ostream& stream, const DataType<T>& input)
433b62047bSLouis Dionne     {
443b62047bSLouis Dionne         return stream << input.my_val;
453b62047bSLouis Dionne     }
463b62047bSLouis Dionne 
473b62047bSLouis Dionne   private:
483b62047bSLouis Dionne     T my_val;
493b62047bSLouis Dionne };
503b62047bSLouis Dionne 
513b62047bSLouis Dionne template <typename Iterator>
523b62047bSLouis Dionne typename std::enable_if<std::is_trivial<typename std::iterator_traits<Iterator>::value_type>::value, bool>::type
is_equal(Iterator first,Iterator last,Iterator d_first)533b62047bSLouis Dionne is_equal(Iterator first, Iterator last, Iterator d_first)
543b62047bSLouis Dionne {
553b62047bSLouis Dionne     return std::equal(first, last, d_first);
563b62047bSLouis Dionne }
573b62047bSLouis Dionne 
583b62047bSLouis Dionne template <typename Iterator>
593b62047bSLouis Dionne typename std::enable_if<!std::is_trivial<typename std::iterator_traits<Iterator>::value_type>::value, bool>::type
is_equal(Iterator,Iterator,Iterator)603491119fSLouis Dionne     is_equal(Iterator, Iterator, Iterator)
613b62047bSLouis Dionne {
623b62047bSLouis Dionne     return true;
633b62047bSLouis Dionne }
643b62047bSLouis Dionne 
653b62047bSLouis Dionne struct test_one_policy
663b62047bSLouis Dionne {
67*3b9a1bb1SLouis Dionne #if defined(_PSTL_ICC_17_VC141_TEST_SIMD_LAMBDA_DEBUG_32_BROKEN) ||                                                             \
68*3b9a1bb1SLouis Dionne     defined(_PSTL_ICC_16_VC14_TEST_SIMD_LAMBDA_DEBUG_32_BROKEN) //dummy specializations to skip testing in case of broken configuration
693b62047bSLouis Dionne     template <typename BiDirIt, typename Size, typename UnaryOp, typename Generator>
703b62047bSLouis Dionne     void
operator ()test_one_policy713b62047bSLouis Dionne     operator()(pstl::execution::unsequenced_policy, BiDirIt first, BiDirIt last, BiDirIt exp_first, BiDirIt exp_last,
723b62047bSLouis Dionne                Size n, UnaryOp unary_op, Generator generator)
733b62047bSLouis Dionne     {
743b62047bSLouis Dionne     }
753b62047bSLouis Dionne 
763b62047bSLouis Dionne     template <typename BiDirIt, typename Size, typename UnaryOp, typename Generator>
773b62047bSLouis Dionne     void
operator ()test_one_policy783b62047bSLouis Dionne     operator()(pstl::execution::parallel_unsequenced_policy, BiDirIt first, BiDirIt last, BiDirIt exp_first,
793b62047bSLouis Dionne                BiDirIt exp_last, Size n, UnaryOp unary_op, Generator generator)
803b62047bSLouis Dionne     {
813b62047bSLouis Dionne     }
82*3b9a1bb1SLouis Dionne #elif defined(_PSTL_ICC_16_VC14_TEST_PAR_TBB_RT_RELEASE_64_BROKEN) //dummy specializations to skip testing in case of broken configuration
833b62047bSLouis Dionne     template <typename BiDirIt, typename Size, typename UnaryOp, typename Generator>
843b62047bSLouis Dionne     void
853b62047bSLouis Dionne     operator()(pstl::execution::parallel_policy, BiDirIt first, BiDirIt last, BiDirIt exp_first, BiDirIt exp_last,
863b62047bSLouis Dionne                Size n, UnaryOp unary_op, Generator generator)
873b62047bSLouis Dionne     {
883b62047bSLouis Dionne     }
893b62047bSLouis Dionne 
903b62047bSLouis Dionne     template <typename BiDirIt, typename Size, typename UnaryOp, typename Generator>
913b62047bSLouis Dionne     void
923b62047bSLouis Dionne     operator()(pstl::execution::parallel_unsequenced_policy, BiDirIt first, BiDirIt last, BiDirIt exp_first,
933b62047bSLouis Dionne                BiDirIt exp_last, Size n, UnaryOp unary_op, Generator generator)
943b62047bSLouis Dionne     {
953b62047bSLouis Dionne     }
963b62047bSLouis Dionne #endif
973b62047bSLouis Dionne 
983b62047bSLouis Dionne     template <typename Policy, typename BiDirIt, typename Size, typename UnaryOp, typename Generator>
993b62047bSLouis Dionne     typename std::enable_if<!is_same_iterator_category<BiDirIt, std::forward_iterator_tag>::value, void>::type
operator ()test_one_policy10001963cecSLouis Dionne     operator()(Policy&& exec, BiDirIt first, BiDirIt last, BiDirIt exp_first, BiDirIt exp_last, Size, UnaryOp unary_op,
10101963cecSLouis Dionne                Generator generator)
1023b62047bSLouis Dionne     {
1033b62047bSLouis Dionne         // partition
1043b62047bSLouis Dionne         {
1053b62047bSLouis Dionne             fill_data(first, last, generator);
1063b62047bSLouis Dionne             BiDirIt actual_ret = std::partition(exec, first, last, unary_op);
1073b62047bSLouis Dionne             EXPECT_TRUE(std::all_of(first, actual_ret, unary_op) && !std::any_of(actual_ret, last, unary_op),
1083b62047bSLouis Dionne                         "wrong effect from partition");
1093b62047bSLouis Dionne         }
1103b62047bSLouis Dionne         // stable_partition
1113b62047bSLouis Dionne         {
1123b62047bSLouis Dionne             fill_data(exp_first, exp_last, generator);
1133b62047bSLouis Dionne             BiDirIt exp_ret = std::stable_partition(exp_first, exp_last, unary_op);
1143b62047bSLouis Dionne             fill_data(first, last, generator);
1153b62047bSLouis Dionne             BiDirIt actual_ret = std::stable_partition(exec, first, last, unary_op);
1163b62047bSLouis Dionne 
1173b62047bSLouis Dionne             EXPECT_TRUE(std::distance(first, actual_ret) == std::distance(exp_first, exp_ret),
1183b62047bSLouis Dionne                         "wrong result from stable_partition");
1193b62047bSLouis Dionne             EXPECT_TRUE((is_equal<BiDirIt>(exp_first, exp_last, first)), "wrong effect from stable_partition");
1203b62047bSLouis Dionne         }
1213b62047bSLouis Dionne     }
1223b62047bSLouis Dionne     template <typename Policy, typename BiDirIt, typename Size, typename UnaryOp, typename Generator>
1233b62047bSLouis Dionne     typename std::enable_if<is_same_iterator_category<BiDirIt, std::forward_iterator_tag>::value, void>::type
operator ()test_one_policy12401963cecSLouis Dionne     operator()(Policy&&, BiDirIt, BiDirIt, BiDirIt, BiDirIt, Size, UnaryOp, Generator)
1253b62047bSLouis Dionne     {
1263b62047bSLouis Dionne     }
1273b62047bSLouis Dionne };
1283b62047bSLouis Dionne 
1293b62047bSLouis Dionne template <typename T, typename Generator, typename UnaryPred>
1303b62047bSLouis Dionne void
test_by_type(Generator generator,UnaryPred pred)1313b62047bSLouis Dionne test_by_type(Generator generator, UnaryPred pred)
1323b62047bSLouis Dionne {
1333b62047bSLouis Dionne 
1343b62047bSLouis Dionne     using namespace std;
1353b62047bSLouis Dionne     size_t max_size = 100000;
1363b62047bSLouis Dionne     Sequence<T> in(max_size, [](size_t v) { return T(v); });
1373b62047bSLouis Dionne     Sequence<T> exp(max_size, [](size_t v) { return T(v); });
1383b62047bSLouis Dionne 
1393b62047bSLouis Dionne     for (size_t n = 0; n <= max_size; n = n <= 16 ? n + 1 : size_t(3.1415 * n))
1403b62047bSLouis Dionne     {
1413b62047bSLouis Dionne         invoke_on_all_policies(test_one_policy(), in.begin(), in.begin() + n, exp.begin(), exp.begin() + n, n, pred,
1423b62047bSLouis Dionne                                generator);
1433b62047bSLouis Dionne     }
1443b62047bSLouis Dionne }
1453b62047bSLouis Dionne 
1463b62047bSLouis Dionne struct test_non_const
1473b62047bSLouis Dionne {
1483b62047bSLouis Dionne     template <typename Policy, typename Iterator>
1493b62047bSLouis Dionne     void
operator ()test_non_const1503b62047bSLouis Dionne     operator()(Policy&& exec, Iterator iter)
1513b62047bSLouis Dionne     {
1523b62047bSLouis Dionne         auto is_even = [&](float64_t v) {
1533b62047bSLouis Dionne             uint32_t i = (uint32_t)v;
1543b62047bSLouis Dionne             return i % 2 == 0;
1553b62047bSLouis Dionne         };
1563b62047bSLouis Dionne         invoke_if(exec, [&]() {
1573b62047bSLouis Dionne             partition(exec, iter, iter, non_const(is_even));
1583b62047bSLouis Dionne             stable_partition(exec, iter, iter, non_const(is_even));
1593b62047bSLouis Dionne         });
1603b62047bSLouis Dionne     }
1613b62047bSLouis Dionne };
1623b62047bSLouis Dionne 
163249c1c74SLouis Dionne int
main()1643b62047bSLouis Dionne main()
1653b62047bSLouis Dionne {
166*3b9a1bb1SLouis Dionne #if !defined(_PSTL_ICC_16_17_TEST_REDUCTION_RELEASE_BROKEN)
1673b62047bSLouis Dionne     test_by_type<int32_t>([](int32_t i) { return i; }, [](int32_t) { return true; });
1683b62047bSLouis Dionne #endif
1693b62047bSLouis Dionne     test_by_type<float64_t>([](int32_t i) { return -i; }, [](const float64_t x) { return x < 0; });
1703b62047bSLouis Dionne     test_by_type<int64_t>([](int32_t i) { return i + 1; }, [](int64_t x) { return x % 3 == 0; });
1713b62047bSLouis Dionne     test_by_type<DataType<float32_t>>([](int32_t i) { return DataType<float32_t>(2 * i + 1); },
1723b62047bSLouis Dionne                                       [](const DataType<float32_t>& x) { return x.get_val() < 0; });
1733b62047bSLouis Dionne 
1743b62047bSLouis Dionne     test_algo_basic_single<int32_t>(run_for_rnd_bi<test_non_const>());
1753b62047bSLouis Dionne 
1763b62047bSLouis Dionne     std::cout << done() << std::endl;
1773b62047bSLouis Dionne     return 0;
1783b62047bSLouis Dionne }
179