Initial PSTL commit
[lldb.git] / pstl / test / test_inplace_merge.cpp
1 // -*- C++ -*-
2 //===-- test_inplace_merge.cpp --------------------------------------------===//
3 //
4 //                     The LLVM Compiler Infrastructure
5 //
6 // This file is dual licensed under the MIT and the University of Illinois Open
7 // Source Licenses. See LICENSE.TXT for details.
8 //
9 //===----------------------------------------------------------------------===//
10
11 #include "pstl_test_config.h"
12
13 #include <algorithm>
14 #include "pstl/execution"
15 #include "pstl/algorithm"
16
17 #include "utils.h"
18
19 using namespace TestUtils;
20
21 struct test_one_policy
22 {
23 #if __PSTL_ICC_17_VC141_TEST_SIMD_LAMBDA_DEBUG_32_BROKEN ||                                                            \
24     __PSTL_ICC_16_VC14_TEST_SIMD_LAMBDA_DEBUG_32_BROKEN // dummy specialization by policy type, in case of broken configuration
25     template <typename BiDirIt1, typename Size, typename Generator1, typename Generator2, typename Compare>
26     void
27     operator()(pstl::execution::unsequenced_policy, BiDirIt1 first1, BiDirIt1 last1, BiDirIt1 first2, BiDirIt1 last2,
28                Size n, Size m, Generator1 generator1, Generator2 generator2, Compare comp)
29     {
30     }
31
32     template <typename BiDirIt1, typename Size, typename Generator1, typename Generator2, typename Compare>
33     void
34     operator()(pstl::execution::parallel_unsequenced_policy, BiDirIt1 first1, BiDirIt1 last1, BiDirIt1 first2,
35                BiDirIt1 last2, Size n, Size m, Generator1 generator1, Generator2 generator2, Compare comp)
36     {
37     }
38 #endif
39
40     // inplace_merge works with bidirectional iterators at least
41     template <typename Policy, typename BiDirIt1, typename Size, typename Generator1, typename Generator2,
42               typename Compare>
43     typename std::enable_if<!is_same_iterator_category<BiDirIt1, std::forward_iterator_tag>::value, void>::type
44     operator()(Policy&& exec, BiDirIt1 first1, BiDirIt1 last1, BiDirIt1 first2, BiDirIt1 last2, Size n, Size m,
45                Generator1 generator1, Generator2 generator2, Compare comp)
46     {
47
48         using T = typename std::iterator_traits<BiDirIt1>::value_type;
49         const BiDirIt1 mid1 = std::next(first1, m);
50         fill_data(first1, mid1, generator1);
51         fill_data(mid1, last1, generator2);
52
53         const BiDirIt1 mid2 = std::next(first2, m);
54         fill_data(first2, mid2, generator1);
55         fill_data(mid2, last2, generator2);
56
57         std::inplace_merge(first1, mid1, last1, comp);
58         std::inplace_merge(exec, first2, mid2, last2, comp);
59         EXPECT_EQ_N(first1, first2, n, "wrong effect from inplace_merge with predicate");
60     }
61
62     template <typename Policy, typename BiDirIt1, typename Size, typename Generator1, typename Generator2,
63               typename Compare>
64     typename std::enable_if<is_same_iterator_category<BiDirIt1, std::forward_iterator_tag>::value, void>::type
65     operator()(Policy&& exec, BiDirIt1 first1, BiDirIt1 last1, BiDirIt1 first2, BiDirIt1 last2, Size n, Size m,
66                Generator1 generator1, Generator2 generator2, Compare comp)
67     {
68     }
69 };
70
71 template <typename T, typename Generator1, typename Generator2, typename Compare>
72 void
73 test_by_type(Generator1 generator1, Generator2 generator2, Compare comp)
74 {
75     using namespace std;
76     size_t max_size = 100000;
77     Sequence<T> in1(max_size, [](size_t v) { return T(v); });
78     Sequence<T> exp(max_size, [](size_t v) { return T(v); });
79     size_t m;
80
81     for (size_t n = 0; n <= max_size; n = n <= 16 ? n + 1 : size_t(3.1415 * n))
82     {
83         m = 0;
84         invoke_on_all_policies(test_one_policy(), in1.begin(), in1.begin() + n, exp.begin(), exp.begin() + n, n, m,
85                                generator1, generator2, comp);
86
87         m = n / 3;
88         invoke_on_all_policies(test_one_policy(), in1.begin(), in1.begin() + n, exp.begin(), exp.begin() + n, n, m,
89                                generator1, generator2, comp);
90
91         m = 2 * n / 3;
92         invoke_on_all_policies(test_one_policy(), in1.begin(), in1.begin() + n, exp.begin(), exp.begin() + n, n, m,
93                                generator1, generator2, comp);
94     }
95 }
96
97 template <typename T>
98 struct LocalWrapper
99 {
100     explicit LocalWrapper(int32_t k) : my_val(k) {}
101     LocalWrapper(LocalWrapper&& input) { my_val = std::move(input.my_val); }
102     LocalWrapper&
103     operator=(LocalWrapper&& input)
104     {
105         my_val = std::move(input.my_val);
106         return *this;
107     }
108     bool
109     operator<(const LocalWrapper<T>& w) const
110     {
111         return my_val < w.my_val;
112     }
113     friend bool
114     operator==(const LocalWrapper<T>& x, const LocalWrapper<T>& y)
115     {
116         return x.my_val == y.my_val;
117     }
118     friend std::ostream&
119     operator<<(std::ostream& stream, const LocalWrapper<T>& input)
120     {
121         return stream << input.my_val;
122     }
123
124   private:
125     T my_val;
126 };
127
128 template <typename T>
129 struct test_non_const
130 {
131     template <typename Policy, typename Iterator>
132     void
133     operator()(Policy&& exec, Iterator iter)
134     {
135         invoke_if(exec, [&]() { inplace_merge(exec, iter, iter, iter, non_const(std::less<T>())); });
136     }
137 };
138
139 int32_t
140 main()
141 {
142     test_by_type<float64_t>([](int32_t i) { return -2 * i; }, [](int32_t i) { return -(2 * i + 1); },
143                             [](const float64_t x, const float64_t y) { return x > y; });
144
145     test_by_type<int32_t>([](int32_t i) { return 10 * i; }, [](int32_t i) { return i + 1; }, std::less<int32_t>());
146
147     test_by_type<LocalWrapper<float32_t>>([](int32_t i) { return LocalWrapper<float32_t>(2 * i + 1); },
148                                           [](int32_t i) { return LocalWrapper<float32_t>(2 * i); },
149                                           std::less<LocalWrapper<float32_t>>());
150
151     test_algo_basic_single<int32_t>(run_for_rnd_bi<test_non_const<int32_t>>());
152
153     std::cout << done() << std::endl;
154     return 0;
155 }