1 //////////////////////////////////////////////////////////////////////////////
2 //
3 // (C) Copyright Ion Gaztanaga 2016-2016.
4 // Distributed under the Boost Software License, Version 1.0.
5 // (See accompanying file LICENSE_1_0.txt or copy at
6 // http://www.boost.org/LICENSE_1_0.txt)
7 //
8 // See http://www.boost.org/libs/move for documentation.
9 //
10 //////////////////////////////////////////////////////////////////////////////
11
12 //#define BOOST_MOVE_ADAPTIVE_SORT_INVARIANTS
13 #define BOOST_MOVE_ADAPTIVE_SORT_STATS
14
15 #include "order_type.hpp"
16
17 #include <iostream> //std::cout
18 #include <boost/config.hpp>
19
20 #include <boost/move/algo/detail/adaptive_sort_merge.hpp>
21 #include <boost/move/core.hpp>
22 #include <boost/move/unique_ptr.hpp>
23 #include <boost/move/make_unique.hpp>
24
25 #include <boost/move/detail/type_traits.hpp>
26 #include <boost/core/lightweight_test.hpp>
27
28 #include <cstddef>
29
30 const std::size_t BlockSize = 7u;
31
32 #if defined(BOOST_MSVC)
33 #pragma warning (disable : 4267)
34 #endif
35
36
37 const std::size_t left_merge = 0;
38 const std::size_t buf_merge = 1;
39 const std::size_t unbuf_merge= 2;
40 const std::size_t max_merge = 3;
41
42 template<class Op>
alternating_test(const std::size_t NumBlocksA,const std::size_t NumBlocksB,const std::size_t ExtraA,const std::size_t ExtraB,Op op)43 void alternating_test(
44 const std::size_t NumBlocksA,
45 const std::size_t NumBlocksB,
46 const std::size_t ExtraA,
47 const std::size_t ExtraB,
48 Op op)
49 {
50 using namespace boost::movelib::detail_adaptive;
51
52
53 const std::size_t DataSize = ExtraA + NumBlocksA*BlockSize + NumBlocksB*BlockSize + ExtraB;
54 const std::size_t KeySize = NumBlocksA + NumBlocksB + 1;
55 const std::size_t HdrSize = BlockSize + KeySize;
56 const std::size_t ArraySize = HdrSize + DataSize;
57
58 boost::movelib::unique_ptr<order_move_type[]> testarray(boost::movelib::make_unique<order_move_type[]>(ArraySize));
59
60
61 for(std::size_t szt_merge = 0; szt_merge != max_merge; ++szt_merge){
62 //Order keys
63 for (std::size_t szt_i = 0u; szt_i != KeySize; ++szt_i) {
64 testarray[szt_i].key = szt_i;
65 testarray[szt_i].val = std::size_t(-1);
66 }
67
68 //Order buffer
69 for (std::size_t szt_i = 0u; szt_i != BlockSize; ++szt_i) {
70 testarray[KeySize+szt_i].key = std::size_t(-1);
71 testarray[KeySize+szt_i].val = szt_i;
72 }
73
74 //Block A
75 std::size_t szt_k = 0;
76 for (std::size_t szt_i = 0u; szt_i != ExtraA; ++szt_i) {
77 testarray[HdrSize+szt_k].key = (szt_k/2)*2;
78 testarray[HdrSize+szt_k].val = szt_k & 1;
79 ++szt_k;
80 }
81
82 for (std::size_t szt_b = 0u; szt_b != NumBlocksA; ++szt_b)
83 for (std::size_t szt_i = 0u; szt_i != BlockSize; ++szt_i) {
84 testarray[HdrSize+szt_k].key = (szt_k/2)*2;
85 testarray[HdrSize+szt_k].val = szt_k & 1;
86 ++szt_k;
87 }
88
89 //Block B
90 std::size_t szt_l = 0;
91 for (std::size_t szt_b = 0u, szt_t = 0; szt_b != NumBlocksB; ++szt_b)
92 for (std::size_t szt_i = 0u; szt_i != BlockSize; ++szt_i, ++szt_t) {
93 testarray[HdrSize+szt_k].key = (szt_l/2)*2+1;
94 testarray[HdrSize+szt_k].val = szt_l & 1;
95 ++szt_k;
96 ++szt_l;
97 }
98
99 for (std::size_t szt_i = 0u; szt_i != ExtraB; ++szt_i) {
100 testarray[HdrSize+szt_k].key = (szt_l/2)*2+1;
101 testarray[HdrSize+szt_k].val = szt_l & 1;
102 ++szt_k;
103 ++szt_l;
104 }
105
106 if(szt_merge == left_merge){
107 //Merge Left
108 op_merge_blocks_left
109 ( testarray.get(), order_type_less()
110 , testarray.get()+HdrSize, BlockSize, ExtraA, NumBlocksA, NumBlocksB, ExtraB
111 , order_type_less(), op );
112 BOOST_TEST( is_order_type_ordered(testarray.get()+KeySize, DataSize) );
113 BOOST_TEST( is_key(testarray.get(), KeySize) );
114 BOOST_TEST(( !boost::move_detail::is_same<Op, boost::movelib::swap_op>::value
115 || is_buffer(testarray.get()+ KeySize+DataSize, BlockSize) ));
116 }
117 else if(szt_merge == buf_merge){
118 //Merge with buf
119 op_merge_blocks_with_buf
120 ( testarray.get(), order_type_less()
121 , testarray.get()+HdrSize, BlockSize, ExtraA, NumBlocksA, NumBlocksB, ExtraB
122 , order_type_less(), op, testarray.get()+KeySize );
123 BOOST_TEST( is_order_type_ordered(testarray.get()+HdrSize, DataSize) );
124 BOOST_TEST( is_key(testarray.get(), KeySize) );
125 BOOST_TEST(( !boost::move_detail::is_same<Op, boost::movelib::swap_op>::value
126 || is_buffer(testarray.get()+ KeySize, BlockSize) ));
127 }
128 else if(szt_merge == unbuf_merge){
129 //Merge Left
130 merge_blocks_bufferless
131 ( testarray.get(), order_type_less()
132 , testarray.get()+HdrSize, BlockSize, ExtraA, NumBlocksA, NumBlocksB, ExtraB
133 , order_type_less());
134 BOOST_TEST( is_order_type_ordered(testarray.get()+HdrSize, DataSize) );
135 BOOST_TEST( is_key(testarray.get(), KeySize) );
136 BOOST_TEST(( !boost::move_detail::is_same<Op, boost::movelib::swap_op>::value
137 || is_buffer(testarray.get()+ KeySize, BlockSize) ));
138 }
139 }
140 }
141
main()142 int main()
143 {
144 {
145 const std::size_t NumBlocksA = 3u;
146 const std::size_t NumBlocksB = 3u;
147 const std::size_t ExtraA = BlockSize/2;
148 const std::size_t ExtraB = ExtraA;
149 alternating_test(NumBlocksA, NumBlocksB, ExtraA, ExtraB, boost::movelib::move_op());
150 alternating_test(NumBlocksA, NumBlocksB, ExtraA, ExtraB, boost::movelib::swap_op());
151 }
152 {
153 const std::size_t NumBlocksA = 3u;
154 const std::size_t NumBlocksB = 3u;
155 const std::size_t ExtraA = 0u;
156 const std::size_t ExtraB = BlockSize/2;
157 alternating_test(NumBlocksA, NumBlocksB, ExtraA, ExtraB, boost::movelib::move_op());
158 alternating_test(NumBlocksA, NumBlocksB, ExtraA, ExtraB, boost::movelib::swap_op());
159 }
160 {
161 const std::size_t NumBlocksA = 3u;
162 const std::size_t NumBlocksB = 3u;
163 const std::size_t ExtraA = BlockSize/2;
164 const std::size_t ExtraB = 0;
165 alternating_test(NumBlocksA, NumBlocksB, ExtraA, ExtraB, boost::movelib::move_op());
166 alternating_test(NumBlocksA, NumBlocksB, ExtraA, ExtraB, boost::movelib::swap_op());
167 }
168 {
169 const std::size_t NumBlocksA = 3u;
170 const std::size_t NumBlocksB = 3u;
171 const std::size_t ExtraA = 0;
172 const std::size_t ExtraB = 0;
173 alternating_test(NumBlocksA, NumBlocksB, ExtraA, ExtraB, boost::movelib::move_op());
174 alternating_test(NumBlocksA, NumBlocksB, ExtraA, ExtraB, boost::movelib::swap_op());
175 }
176 {
177 const std::size_t NumBlocksA = 6u;
178 const std::size_t NumBlocksB = 3u;
179 const std::size_t ExtraA = BlockSize/2;
180 const std::size_t ExtraB = ExtraA;
181 alternating_test(NumBlocksA, NumBlocksB, ExtraA, ExtraB, boost::movelib::move_op());
182 alternating_test(NumBlocksA, NumBlocksB, ExtraA, ExtraB, boost::movelib::swap_op());
183 }
184 {
185 const std::size_t NumBlocksA = 6u;
186 const std::size_t NumBlocksB = 3u;
187 const std::size_t ExtraA = BlockSize/2;
188 const std::size_t ExtraB = 0;
189 alternating_test(NumBlocksA, NumBlocksB, ExtraA, ExtraB, boost::movelib::move_op());
190 alternating_test(NumBlocksA, NumBlocksB, ExtraA, ExtraB, boost::movelib::swap_op());
191 }
192 {
193 const std::size_t NumBlocksA = 3u;
194 const std::size_t NumBlocksB = 5u;
195 const std::size_t ExtraA = BlockSize/2;
196 const std::size_t ExtraB = ExtraA;
197 alternating_test(NumBlocksA, NumBlocksB, ExtraA, ExtraB, boost::movelib::move_op());
198 alternating_test(NumBlocksA, NumBlocksB, ExtraA, ExtraB, boost::movelib::swap_op());
199 }
200 {
201 const std::size_t NumBlocksA = 3u;
202 const std::size_t NumBlocksB = 5u;
203 const std::size_t ExtraA = BlockSize/2;
204 const std::size_t ExtraB = 0;
205 alternating_test(NumBlocksA, NumBlocksB, ExtraA, ExtraB, boost::movelib::move_op());
206 alternating_test(NumBlocksA, NumBlocksB, ExtraA, ExtraB, boost::movelib::swap_op());
207 }
208 {
209 const std::size_t NumBlocksA = 0u;
210 const std::size_t NumBlocksB = 0u;
211 const std::size_t ExtraA = 0;
212 const std::size_t ExtraB = 0;
213 alternating_test(NumBlocksA, NumBlocksB, ExtraA, ExtraB, boost::movelib::move_op());
214 alternating_test(NumBlocksA, NumBlocksB, ExtraA, ExtraB, boost::movelib::swap_op());
215 }
216 {
217 const std::size_t NumBlocksA = 0u;
218 const std::size_t NumBlocksB = 0u;
219 const std::size_t ExtraA = BlockSize/2;
220 const std::size_t ExtraB = 0;
221 alternating_test(NumBlocksA, NumBlocksB, ExtraA, ExtraB, boost::movelib::move_op());
222 alternating_test(NumBlocksA, NumBlocksB, ExtraA, ExtraB, boost::movelib::swap_op());
223 }
224 {
225 const std::size_t NumBlocksA = 0u;
226 const std::size_t NumBlocksB = 0u;
227 const std::size_t ExtraA = 0;
228 const std::size_t ExtraB = BlockSize/2;
229 alternating_test(NumBlocksA, NumBlocksB, ExtraA, ExtraB, boost::movelib::move_op());
230 alternating_test(NumBlocksA, NumBlocksB, ExtraA, ExtraB, boost::movelib::swap_op());
231 }
232 //
233 {
234 const std::size_t NumBlocksA = 0u;
235 const std::size_t NumBlocksB = 1u;
236 const std::size_t ExtraA = 0;
237 const std::size_t ExtraB = 0;
238 alternating_test(NumBlocksA, NumBlocksB, ExtraA, ExtraB, boost::movelib::move_op());
239 alternating_test(NumBlocksA, NumBlocksB, ExtraA, ExtraB, boost::movelib::swap_op());
240 }
241 {
242 const std::size_t NumBlocksA = 1u;
243 const std::size_t NumBlocksB = 0u;
244 const std::size_t ExtraA = 0;
245 const std::size_t ExtraB = 0;
246 alternating_test(NumBlocksA, NumBlocksB, ExtraA, ExtraB, boost::movelib::move_op());
247 alternating_test(NumBlocksA, NumBlocksB, ExtraA, ExtraB, boost::movelib::swap_op());
248 }
249 {
250 const std::size_t NumBlocksA = 1u;
251 const std::size_t NumBlocksB = 0u;
252 const std::size_t ExtraA = BlockSize/2;
253 const std::size_t ExtraB = 0;
254 alternating_test(NumBlocksA, NumBlocksB, ExtraA, ExtraB, boost::movelib::move_op());
255 alternating_test(NumBlocksA, NumBlocksB, ExtraA, ExtraB, boost::movelib::swap_op());
256 }
257 {
258 const std::size_t NumBlocksA = 0u;
259 const std::size_t NumBlocksB = 1u;
260 const std::size_t ExtraA = BlockSize/2;
261 const std::size_t ExtraB = 0;
262 alternating_test(NumBlocksA, NumBlocksB, ExtraA, ExtraB, boost::movelib::move_op());
263 alternating_test(NumBlocksA, NumBlocksB, ExtraA, ExtraB, boost::movelib::swap_op());
264 }
265 {
266 const std::size_t NumBlocksA = 1u;
267 const std::size_t NumBlocksB = 0u;
268 const std::size_t ExtraA = 0;
269 const std::size_t ExtraB = BlockSize/2;
270 alternating_test(NumBlocksA, NumBlocksB, ExtraA, ExtraB, boost::movelib::move_op());
271 alternating_test(NumBlocksA, NumBlocksB, ExtraA, ExtraB, boost::movelib::swap_op());
272 }
273 {
274 const std::size_t NumBlocksA = 0u;
275 const std::size_t NumBlocksB = 1u;
276 const std::size_t ExtraA = 0;
277 const std::size_t ExtraB = BlockSize/2;
278 alternating_test(NumBlocksA, NumBlocksB, ExtraA, ExtraB, boost::movelib::move_op());
279 alternating_test(NumBlocksA, NumBlocksB, ExtraA, ExtraB, boost::movelib::swap_op());
280 }
281
282 return ::boost::report_errors();
283 }
284