1 // -*- C++ -*-
2 //===-- partition.pass.cpp ------------------------------------------------===//
3 //
4 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
5 // See https://llvm.org/LICENSE.txt for license information.
6 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //
8 //===----------------------------------------------------------------------===//
9 
10 // UNSUPPORTED: c++03, c++11, c++14
11 
12 // Tests for stable_partition and partition
13 #include "support/pstl_test_config.h"
14 
15 #include <execution>
16 #include <algorithm>
17 #include <iterator>
18 #include <type_traits>
19 
20 #include "support/utils.h"
21 
22 using namespace TestUtils;
23 
24 template <typename T>
25 struct DataType
26 {
27     explicit DataType(int32_t k) : my_val(k) {}
28     DataType(DataType&& input) { my_val = std::move(input.my_val); }
29     DataType&
30     operator=(DataType&& input)
31     {
32         my_val = std::move(input.my_val);
33         return *this;
34     }
35     T
36     get_val() const
37     {
38         return my_val;
39     }
40 
41     friend std::ostream&
42     operator<<(std::ostream& stream, const DataType<T>& input)
43     {
44         return stream << input.my_val;
45     }
46 
47   private:
48     T my_val;
49 };
50 
51 template <typename Iterator>
52 typename std::enable_if<std::is_trivial<typename std::iterator_traits<Iterator>::value_type>::value, bool>::type
53 is_equal(Iterator first, Iterator last, Iterator d_first)
54 {
55     return std::equal(first, last, d_first);
56 }
57 
58 template <typename Iterator>
59 typename std::enable_if<!std::is_trivial<typename std::iterator_traits<Iterator>::value_type>::value, bool>::type
60     is_equal(Iterator, Iterator, Iterator)
61 {
62     return true;
63 }
64 
65 struct test_one_policy
66 {
67 #if defined(_PSTL_ICC_17_VC141_TEST_SIMD_LAMBDA_DEBUG_32_BROKEN) ||                                                             \
68     defined(_PSTL_ICC_16_VC14_TEST_SIMD_LAMBDA_DEBUG_32_BROKEN) //dummy specializations to skip testing in case of broken configuration
69     template <typename BiDirIt, typename Size, typename UnaryOp, typename Generator>
70     void
71     operator()(pstl::execution::unsequenced_policy, BiDirIt first, BiDirIt last, BiDirIt exp_first, BiDirIt exp_last,
72                Size n, UnaryOp unary_op, Generator generator)
73     {
74     }
75 
76     template <typename BiDirIt, typename Size, typename UnaryOp, typename Generator>
77     void
78     operator()(pstl::execution::parallel_unsequenced_policy, BiDirIt first, BiDirIt last, BiDirIt exp_first,
79                BiDirIt exp_last, Size n, UnaryOp unary_op, Generator generator)
80     {
81     }
82 #elif defined(_PSTL_ICC_16_VC14_TEST_PAR_TBB_RT_RELEASE_64_BROKEN) //dummy specializations to skip testing in case of broken configuration
83     template <typename BiDirIt, typename Size, typename UnaryOp, typename Generator>
84     void
85     operator()(pstl::execution::parallel_policy, BiDirIt first, BiDirIt last, BiDirIt exp_first, BiDirIt exp_last,
86                Size n, UnaryOp unary_op, Generator generator)
87     {
88     }
89 
90     template <typename BiDirIt, typename Size, typename UnaryOp, typename Generator>
91     void
92     operator()(pstl::execution::parallel_unsequenced_policy, BiDirIt first, BiDirIt last, BiDirIt exp_first,
93                BiDirIt exp_last, Size n, UnaryOp unary_op, Generator generator)
94     {
95     }
96 #endif
97 
98     template <typename Policy, typename BiDirIt, typename Size, typename UnaryOp, typename Generator>
99     typename std::enable_if<!is_same_iterator_category<BiDirIt, std::forward_iterator_tag>::value, void>::type
100     operator()(Policy&& exec, BiDirIt first, BiDirIt last, BiDirIt exp_first, BiDirIt exp_last, Size, UnaryOp unary_op,
101                Generator generator)
102     {
103         // partition
104         {
105             fill_data(first, last, generator);
106             BiDirIt actual_ret = std::partition(exec, first, last, unary_op);
107             EXPECT_TRUE(std::all_of(first, actual_ret, unary_op) && !std::any_of(actual_ret, last, unary_op),
108                         "wrong effect from partition");
109         }
110         // stable_partition
111         {
112             fill_data(exp_first, exp_last, generator);
113             BiDirIt exp_ret = std::stable_partition(exp_first, exp_last, unary_op);
114             fill_data(first, last, generator);
115             BiDirIt actual_ret = std::stable_partition(exec, first, last, unary_op);
116 
117             EXPECT_TRUE(std::distance(first, actual_ret) == std::distance(exp_first, exp_ret),
118                         "wrong result from stable_partition");
119             EXPECT_TRUE((is_equal<BiDirIt>(exp_first, exp_last, first)), "wrong effect from stable_partition");
120         }
121     }
122     template <typename Policy, typename BiDirIt, typename Size, typename UnaryOp, typename Generator>
123     typename std::enable_if<is_same_iterator_category<BiDirIt, std::forward_iterator_tag>::value, void>::type
124     operator()(Policy&&, BiDirIt, BiDirIt, BiDirIt, BiDirIt, Size, UnaryOp, Generator)
125     {
126     }
127 };
128 
129 template <typename T, typename Generator, typename UnaryPred>
130 void
131 test_by_type(Generator generator, UnaryPred pred)
132 {
133 
134     using namespace std;
135     size_t max_size = 100000;
136     Sequence<T> in(max_size, [](size_t v) { return T(v); });
137     Sequence<T> exp(max_size, [](size_t v) { return T(v); });
138 
139     for (size_t n = 0; n <= max_size; n = n <= 16 ? n + 1 : size_t(3.1415 * n))
140     {
141         invoke_on_all_policies(test_one_policy(), in.begin(), in.begin() + n, exp.begin(), exp.begin() + n, n, pred,
142                                generator);
143     }
144 }
145 
146 struct test_non_const
147 {
148     template <typename Policy, typename Iterator>
149     void
150     operator()(Policy&& exec, Iterator iter)
151     {
152         auto is_even = [&](float64_t v) {
153             uint32_t i = (uint32_t)v;
154             return i % 2 == 0;
155         };
156         invoke_if(exec, [&]() {
157             partition(exec, iter, iter, non_const(is_even));
158             stable_partition(exec, iter, iter, non_const(is_even));
159         });
160     }
161 };
162 
163 int
164 main()
165 {
166 #if !defined(_PSTL_ICC_16_17_TEST_REDUCTION_RELEASE_BROKEN)
167     test_by_type<int32_t>([](int32_t i) { return i; }, [](int32_t) { return true; });
168 #endif
169     test_by_type<float64_t>([](int32_t i) { return -i; }, [](const float64_t x) { return x < 0; });
170     test_by_type<int64_t>([](int32_t i) { return i + 1; }, [](int64_t x) { return x % 3 == 0; });
171     test_by_type<DataType<float32_t>>([](int32_t i) { return DataType<float32_t>(2 * i + 1); },
172                                       [](const DataType<float32_t>& x) { return x.get_val() < 0; });
173 
174     test_algo_basic_single<int32_t>(run_for_rnd_bi<test_non_const>());
175 
176     std::cout << done() << std::endl;
177     return 0;
178 }
179