libjmmcg  release_579_6_g8cffd
A C++ library containing an eclectic mix of useful, advanced components.
dataflow_full_sorting_algos_infinite_crew.cpp
Go to the documentation of this file.
1 /******************************************************************************
2 ** Copyright © 2002 by J.M.McGuiness, coder@hussar.me.uk
3 **
4 ** This library is free software; you can redistribute it and/or
5 ** modify it under the terms of the GNU Lesser General Public
6 ** License as published by the Free Software Foundation; either
7 ** version 2.1 of the License, or (at your option) any later version.
8 **
9 ** This library is distributed in the hope that it will be useful,
10 ** but WITHOUT ANY WARRANTY; without even the implied warranty of
11 ** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 ** Lesser General Public License for more details.
13 **
14 ** You should have received a copy of the GNU Lesser General Public
15 ** License along with this library; if not, write to the Free Software
16 ** Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
17 */
18 
19 #include "stdafx.h"
20 
21 #define BOOST_TEST_MODULE libjmmcg_tests
22 #include <boost/test/included/unit_test.hpp>
23 
24 #include <boost/mpl/list.hpp>
25 
26 #include "core/thread_pool_sequential.hpp"
27 #include "core/thread_pool_master.hpp"
28 #include "core/thread_pool_workers.hpp"
29 
30 using namespace libjmmcg;
31 using namespace ppd;
32 
33 template<class Db, pool_traits::size_mode_t Sz, generic_traits::return_data Jn, class Mdl, unsigned int PoolSize=0, unsigned int GSSk=1>
34 struct crew_normal_fifo_t {
35  typedef api_lock_traits<platform_api, Mdl> lock_traits;
36  typedef safe_colln<
37  std::vector<long>,
38  typename lock::rw::locker<lock_traits>,
39  typename lock::rw::locker<lock_traits>::decaying_write_lock_type
40  > vtr_colln_t;
41 
42  typedef pool_aspects<
43  Jn,
44  platform_api,
45  Mdl,
46  pool_traits::normal_fifo,
47  std::less,
48  GSSk
49  > thread_pool_traits;
50 
51  typedef thread_pool<Db, Sz, thread_pool_traits> pool_type;
52 
53  static const typename pool_type::pool_type::size_type pool_size=PoolSize;
54 };
55 
56 template<class Db, pool_traits::size_mode_t Sz, generic_traits::return_data Jn, class Mdl, unsigned int PoolSize, unsigned int GSSk>
57 const typename crew_normal_fifo_t<Db, Sz, Jn, Mdl, PoolSize, GSSk>::pool_type::pool_type::size_type crew_normal_fifo_t<Db, Sz, Jn, Mdl, PoolSize, GSSk>::pool_size;
58 
59 template<class Db, pool_traits::size_mode_t Sz, generic_traits::return_data Jn, class Mdl, unsigned int PoolSize=0, unsigned int GSSk=1>
60 struct crew_priority_queue_t {
61  typedef api_lock_traits<platform_api, Mdl> lock_traits;
62  typedef safe_colln<
63  std::vector<long>,
64  typename lock::rw::locker<lock_traits>,
65  typename lock::rw::locker<lock_traits>::decaying_write_lock_type
66  > vtr_colln_t;
67 
68  typedef pool_aspects<
69  Jn,
70  platform_api,
71  Mdl,
72  pool_traits::prioritised_queue,
73  std::less,
74  GSSk
75  > thread_pool_traits;
76 
77  typedef thread_pool<Db, Sz, thread_pool_traits> pool_type;
78 
79  static const typename pool_type::pool_type::size_type pool_size=PoolSize;
80 };
81 
82 template<class Db, pool_traits::size_mode_t Sz, generic_traits::return_data Jn, class Mdl, unsigned int PoolSize, unsigned int GSSk>
83 const typename crew_priority_queue_t<Db, Sz, Jn, Mdl, PoolSize, GSSk>::pool_type::pool_type::size_type crew_priority_queue_t<Db, Sz, Jn, Mdl, PoolSize, GSSk>::pool_size;
84 
85 typedef boost::mpl::list<
86  crew_normal_fifo_t<pool_traits::work_distribution_mode_t::worker_threads_get_work<pool_traits::work_distribution_mode_t::queue_model_t::pool_owns_queue>, pool_traits::size_mode_t::sequential, generic_traits::return_data::joinable, sequential_mode>,
87  crew_priority_queue_t<pool_traits::work_distribution_mode_t::worker_threads_get_work<pool_traits::work_distribution_mode_t::queue_model_t::pool_owns_queue>, pool_traits::size_mode_t::sequential, generic_traits::return_data::joinable, sequential_mode>,
88  crew_normal_fifo_t<pool_traits::work_distribution_mode_t::one_thread_distributes<>, pool_traits::size_mode_t::sequential, generic_traits::return_data::joinable, sequential_mode>,
89  crew_priority_queue_t<pool_traits::work_distribution_mode_t::one_thread_distributes<>, pool_traits::size_mode_t::sequential, generic_traits::return_data::joinable, sequential_mode>,
90 
91 // TODO crew_normal_fifo_t<pool_traits::work_distribution_mode_t::worker_threads_get_work<pool_traits::work_distribution_mode_t::queue_model_t::pool_owns_queue>, pool_traits::size_mode_t::infinite, generic_traits::return_data::joinable, heavyweight_threading>,
92 // TODO crew_priority_queue_t<pool_traits::work_distribution_mode_t::worker_threads_get_work<pool_traits::work_distribution_mode_t::queue_model_t::pool_owns_queue>, pool_traits::size_mode_t::infinite, generic_traits::return_data::joinable, heavyweight_threading>,
93  crew_normal_fifo_t<pool_traits::work_distribution_mode_t::one_thread_distributes<>, pool_traits::size_mode_t::infinite, generic_traits::return_data::joinable, heavyweight_threading>,
94  crew_normal_fifo_t<pool_traits::work_distribution_mode_t::one_thread_distributes<>, pool_traits::size_mode_t::infinite, generic_traits::return_data::joinable, heavyweight_threading, 0, 2>,
95  crew_priority_queue_t<pool_traits::work_distribution_mode_t::one_thread_distributes<>, pool_traits::size_mode_t::infinite, generic_traits::return_data::joinable, heavyweight_threading>,
96  crew_priority_queue_t<pool_traits::work_distribution_mode_t::one_thread_distributes<>, pool_traits::size_mode_t::infinite, generic_traits::return_data::joinable, heavyweight_threading, 0, 2>
97 > infinite_test_types;
98 
99 // TODO Need to test: pool_traits::size_mode_t::tracks_to_max
100 
101 template<typename T>
102 struct square : std::unary_function<T, void> {
103  static T last;
104 
105  void operator()(T t) {
106  last+=t;
107  };
108 };
109 
110 template<typename T>
111 T square<T>::last;
112 
113 inline int sqr() {
114  static int last=0;
115  return last++<<1;
116 }
117 
118 BOOST_AUTO_TEST_SUITE(thread_pool_tests)
119 
120 BOOST_AUTO_TEST_SUITE(joinable_dataflow)
121 
122 BOOST_AUTO_TEST_SUITE(infinite)
123 
124 BOOST_AUTO_TEST_SUITE(empty_colln)
125 
126 BOOST_AUTO_TEST_CASE_TEMPLATE(max_element_op, T, infinite_test_types) {
127  typedef typename T::vtr_colln_t vtr_colln_t;
128  typedef typename T::pool_type pool_type;
129  typedef typename pool_type::joinable joinable;
130 
131  pool_type pool;
132  vtr_colln_t v;
133  auto const &context=pool<<joinable()<<pool.max_element(v, std::greater<typename vtr_colln_t::value_type>());
134  BOOST_CHECK_EQUAL(*context, std::numeric_limits<typename vtr_colln_t::value_type>::min());
135  BOOST_CHECK_EQUAL(pool.min_time(context), 0U);
136  BOOST_CHECK_EQUAL(pool.min_processors(context), 0U);
137 }
138 
139 BOOST_AUTO_TEST_CASE_TEMPLATE(max_element, T, infinite_test_types) {
140  typedef typename T::vtr_colln_t vtr_colln_t;
141  typedef typename T::pool_type pool_type;
142  typedef typename pool_type::joinable joinable;
143 
144  pool_type pool;
145  vtr_colln_t v;
146  auto const &context=pool<<joinable()<<pool.max_element(v);
147  BOOST_CHECK_EQUAL(*context, std::numeric_limits<typename vtr_colln_t::value_type>::min());
148  BOOST_CHECK_EQUAL(pool.min_time(context), 0U);
149  BOOST_CHECK_EQUAL(pool.min_processors(context), 0U);
150 }
151 
152 BOOST_AUTO_TEST_CASE_TEMPLATE(min_element_op, T, infinite_test_types) {
153  typedef typename T::vtr_colln_t vtr_colln_t;
154  typedef typename T::pool_type pool_type;
155  typedef typename pool_type::joinable joinable;
156 
157  pool_type pool;
158  vtr_colln_t v;
159  auto const &context=pool<<joinable()<<pool.min_element(v, std::greater<typename vtr_colln_t::value_type>());
160  BOOST_CHECK_EQUAL(*context, std::numeric_limits<typename vtr_colln_t::value_type>::max());
161  BOOST_CHECK_EQUAL(pool.min_time(context), 0U);
162  BOOST_CHECK_EQUAL(pool.min_processors(context), 0U);
163 }
164 
165 BOOST_AUTO_TEST_CASE_TEMPLATE(min_element, T, infinite_test_types) {
166  typedef typename T::vtr_colln_t vtr_colln_t;
167  typedef typename T::pool_type pool_type;
168  typedef typename pool_type::joinable joinable;
169 
170  pool_type pool;
171  vtr_colln_t v;
172  auto const &context=pool<<joinable()<<pool.min_element(v);
173  BOOST_CHECK_EQUAL(*context, std::numeric_limits<typename vtr_colln_t::value_type>::max());
174  BOOST_CHECK_EQUAL(pool.min_time(context), 0U);
175  BOOST_CHECK_EQUAL(pool.min_processors(context), 0U);
176 }
177 
178 BOOST_AUTO_TEST_CASE_TEMPLATE(merge_op, T, infinite_test_types) {
179  typedef typename T::vtr_colln_t vtr_colln_t;
180  typedef typename T::pool_type pool_type;
181  typedef typename pool_type::joinable joinable;
182 
183  pool_type pool;
184  vtr_colln_t v, v1, v_out;
185  auto const &context=pool<<joinable()<<pool.merge(v, v1, v_out, std::less<typename vtr_colln_t::value_type>());
186  pool.min_time(vtr_colln_t::memory_access_mode);
187  pool.min_processors(vtr_colln_t::memory_access_mode);
188  *context;
189  BOOST_CHECK_EQUAL(v.empty(), true);
190  BOOST_CHECK_EQUAL(v1.empty(), true);
191  BOOST_CHECK_EQUAL(v_out.size(), v.size()+v1.size());
192  BOOST_CHECK(v==v_out);
193  BOOST_CHECK_EQUAL(pool.min_time(context), 0U);
194  BOOST_CHECK_EQUAL(pool.min_processors(context), 0U);
195  vtr_colln_t v_chk;
196  std::merge(v.colln().begin(), v.colln().end(), v1.colln().begin(), v1.colln().end(), std::back_inserter(v_chk.colln()), std::less<typename vtr_colln_t::value_type>());
197  BOOST_CHECK(v_out==v_chk);
198 }
199 
200 BOOST_AUTO_TEST_CASE_TEMPLATE(merge, T, infinite_test_types) {
201  typedef typename T::vtr_colln_t vtr_colln_t;
202  typedef typename T::pool_type pool_type;
203  typedef typename pool_type::joinable joinable;
204 
205  pool_type pool;
206  vtr_colln_t v, v1, v_out;
207  auto const &context=pool<<joinable()<<pool.merge(v, v1, v_out);
208  pool.min_time(vtr_colln_t::memory_access_mode);
209  pool.min_processors(vtr_colln_t::memory_access_mode);
210  *context;
211  BOOST_CHECK_EQUAL(v.empty(), true);
212  BOOST_CHECK_EQUAL(v1.empty(), true);
213  BOOST_CHECK_EQUAL(v_out.size(), v.size()+v1.size());
214  BOOST_CHECK(v==v_out);
215  BOOST_CHECK_EQUAL(pool.min_time(context), 0U);
216  BOOST_CHECK_EQUAL(pool.min_processors(context), 0U);
217  vtr_colln_t v_chk;
218  std::merge(v.colln().begin(), v.colln().end(), v1.colln().begin(), v1.colln().end(), std::back_inserter(v_chk.colln()));
219  BOOST_CHECK(v_out==v_chk);
220 }
221 
222 BOOST_AUTO_TEST_CASE_TEMPLATE(sort_op, T, infinite_test_types) {
223  typedef typename T::vtr_colln_t vtr_colln_t;
224  typedef typename T::pool_type pool_type;
225  typedef typename pool_type::joinable joinable;
226 
227  pool_type pool;
228  vtr_colln_t v;
229  vtr_colln_t v_chk(v);
230  auto const &context=pool<<joinable()<<pool.sort(v, std::greater<typename vtr_colln_t::value_type>());
231  pool.min_time(vtr_colln_t::memory_access_mode);
232  pool.min_processors(vtr_colln_t::memory_access_mode);
233  *context;
234  BOOST_CHECK_EQUAL(v.empty(), true);
235  BOOST_CHECK_EQUAL(pool.min_time(context), 0U);
236  BOOST_CHECK_EQUAL(pool.min_processors(context), 0U);
237  std::sort(v_chk.colln().begin(), v_chk.colln().end(), std::greater<typename vtr_colln_t::value_type>());
238  BOOST_CHECK(v==v_chk);
239 }
240 
241 BOOST_AUTO_TEST_CASE_TEMPLATE(sort, T, infinite_test_types) {
242  typedef typename T::vtr_colln_t vtr_colln_t;
243  typedef typename T::pool_type pool_type;
244  typedef typename pool_type::joinable joinable;
245 
246  pool_type pool;
247  vtr_colln_t v;
248  vtr_colln_t v_chk(v);
249  auto const &context=pool<<joinable()<<pool.sort(v);
250  pool.min_time(vtr_colln_t::memory_access_mode);
251  pool.min_processors(vtr_colln_t::memory_access_mode);
252  *context;
253  BOOST_CHECK_EQUAL(v.empty(), true);
254  BOOST_CHECK_EQUAL(pool.min_time(context), 0U);
255  BOOST_CHECK_EQUAL(pool.min_processors(context), 0U);
256  std::sort(v_chk.colln().begin(), v_chk.colln().end());
257  BOOST_CHECK(v==v_chk);
258 }
259 
260 BOOST_AUTO_TEST_SUITE_END()
261 
262 BOOST_AUTO_TEST_SUITE(nonempty_colln)
263 
264 BOOST_AUTO_TEST_SUITE(one_element)
265 
266 BOOST_AUTO_TEST_CASE_TEMPLATE(max_element_op, T, infinite_test_types) {
267  typedef typename T::vtr_colln_t vtr_colln_t;
268  typedef typename T::pool_type pool_type;
269  typedef typename pool_type::joinable joinable;
270 
271  pool_type pool;
272  vtr_colln_t v;
273  v.push_back(1);
274  auto const &context=pool<<joinable()<<pool.max_element(v, std::greater<typename vtr_colln_t::value_type>());
275  BOOST_CHECK_EQUAL(*context, 1);
276 }
277 
278 BOOST_AUTO_TEST_CASE_TEMPLATE(max_element, T, infinite_test_types) {
279  typedef typename T::vtr_colln_t vtr_colln_t;
280  typedef typename T::pool_type pool_type;
281  typedef typename pool_type::joinable joinable;
282 
283  pool_type pool;
284  vtr_colln_t v;
285  v.push_back(1);
286  auto const &context=pool<<joinable()<<pool.max_element(v);
287  BOOST_CHECK_EQUAL(*context, 1);
288 }
289 
290 BOOST_AUTO_TEST_CASE_TEMPLATE(min_element_op, T, infinite_test_types) {
291  typedef typename T::vtr_colln_t vtr_colln_t;
292  typedef typename T::pool_type pool_type;
293  typedef typename pool_type::joinable joinable;
294 
295  pool_type pool;
296  vtr_colln_t v;
297  v.push_back(1);
298  auto const &context=pool<<joinable()<<pool.min_element(v, std::greater<typename vtr_colln_t::value_type>());
299  BOOST_CHECK_EQUAL(*context, 1);
300 }
301 
302 BOOST_AUTO_TEST_CASE_TEMPLATE(min_element, T, infinite_test_types) {
303  typedef typename T::vtr_colln_t vtr_colln_t;
304  typedef typename T::pool_type pool_type;
305  typedef typename pool_type::joinable joinable;
306 
307  pool_type pool;
308  vtr_colln_t v;
309  v.push_back(1);
310  auto const &context=pool<<joinable()<<pool.min_element(v);
311  BOOST_CHECK_EQUAL(*context, 1);
312 }
313 
314 BOOST_AUTO_TEST_CASE_TEMPLATE(merge_op, T, infinite_test_types) {
315  typedef typename T::vtr_colln_t vtr_colln_t;
316  typedef typename T::pool_type pool_type;
317  typedef typename pool_type::joinable joinable;
318 
319  pool_type pool;
320  vtr_colln_t v, v1, v_out;
321  v.push_back(1);
322  v1.push_back(1);
323  auto const &context=pool<<joinable()<<pool.merge(v, v1, v_out, std::less<typename vtr_colln_t::value_type>());
324  pool.min_time(vtr_colln_t::memory_access_mode);
325  pool.min_processors(vtr_colln_t::memory_access_mode);
326  *context;
327  BOOST_CHECK_EQUAL(v.size(), 1U);
328  BOOST_CHECK_EQUAL(v1.size(), 1U);
329  BOOST_CHECK_EQUAL(v_out.size(), v.size()+v1.size());
330  BOOST_CHECK_EQUAL(v_out[0], v[0]);
331  BOOST_CHECK_EQUAL(v_out[1], v1[0]);
332  vtr_colln_t v_chk;
333  std::merge(v.colln().begin(), v.colln().end(), v1.colln().begin(), v1.colln().end(), std::back_inserter(v_chk.colln()), std::less<typename vtr_colln_t::value_type>());
334  BOOST_CHECK(v_out==v_chk);
335 }
336 
337 BOOST_AUTO_TEST_CASE_TEMPLATE(merge, T, infinite_test_types) {
338  typedef typename T::vtr_colln_t vtr_colln_t;
339  typedef typename T::pool_type pool_type;
340  typedef typename pool_type::joinable joinable;
341 
342  pool_type pool;
343  vtr_colln_t v, v1, v_out;
344  v.push_back(1);
345  v1.push_back(1);
346  auto const &context=pool<<joinable()<<pool.merge(v, v1, v_out);
347  pool.min_time(vtr_colln_t::memory_access_mode);
348  pool.min_processors(vtr_colln_t::memory_access_mode);
349  *context;
350  BOOST_CHECK_EQUAL(v.size(), 1U);
351  BOOST_CHECK_EQUAL(v1.size(), 1U);
352  BOOST_CHECK_EQUAL(v_out.size(), v.size()+v1.size());
353  BOOST_CHECK_EQUAL(v_out[0], v[0]);
354  BOOST_CHECK_EQUAL(v_out[1], v1[0]);
355  vtr_colln_t v_chk;
356  std::merge(v.colln().begin(), v.colln().end(), v1.colln().begin(), v1.colln().end(), std::back_inserter(v_chk.colln()));
357  BOOST_CHECK(v_out==v_chk);
358 }
359 
360 BOOST_AUTO_TEST_CASE_TEMPLATE(sort_op, T, infinite_test_types) {
361  typedef typename T::vtr_colln_t vtr_colln_t;
362  typedef typename T::pool_type pool_type;
363  typedef typename pool_type::joinable joinable;
364 
365  pool_type pool;
366  vtr_colln_t v;
367  v.push_back(1);
368  vtr_colln_t v_chk(v);
369  auto const &context=pool<<joinable()<<pool.sort(v, std::greater<typename vtr_colln_t::value_type>());
370  pool.min_time(vtr_colln_t::memory_access_mode);
371  pool.min_processors(vtr_colln_t::memory_access_mode);
372  *context;
373  BOOST_CHECK_EQUAL(v.size(), 1U);
374  BOOST_CHECK_EQUAL(v[0], 1);
375  std::sort(v_chk.colln().begin(), v_chk.colln().end(), std::greater<typename vtr_colln_t::value_type>());
376  BOOST_CHECK(v==v_chk);
377 }
378 
379 BOOST_AUTO_TEST_CASE_TEMPLATE(sort, T, infinite_test_types) {
380  typedef typename T::vtr_colln_t vtr_colln_t;
381  typedef typename T::pool_type pool_type;
382  typedef typename pool_type::joinable joinable;
383 
384  pool_type pool;
385  vtr_colln_t v;
386  v.push_back(1);
387  vtr_colln_t v_chk(v);
388  auto const &context=pool<<joinable()<<pool.sort(v);
389  pool.min_time(vtr_colln_t::memory_access_mode);
390  pool.min_processors(vtr_colln_t::memory_access_mode);
391  *context;
392  BOOST_CHECK_EQUAL(v.size(), 1U);
393  BOOST_CHECK_EQUAL(v[0], 1);
394  std::sort(v_chk.colln().begin(), v_chk.colln().end());
395  BOOST_CHECK(v==v_chk);
396 }
397 
398 BOOST_AUTO_TEST_SUITE_END()
399 
400 BOOST_AUTO_TEST_SUITE(two_elements)
401 
402 BOOST_AUTO_TEST_CASE_TEMPLATE(max_element_op, T, infinite_test_types) {
403  typedef typename T::vtr_colln_t vtr_colln_t;
404  typedef typename T::pool_type pool_type;
405  typedef typename pool_type::joinable joinable;
406 
407  pool_type pool;
408  vtr_colln_t v;
409  v.push_back(1);
410  v.push_back(2);
411  auto const &context=pool<<joinable()<<pool.max_element(v, std::greater<typename vtr_colln_t::value_type>());
412  BOOST_CHECK_EQUAL(*context, 1);
413 }
414 
415 BOOST_AUTO_TEST_CASE_TEMPLATE(max_element, T, infinite_test_types) {
416  typedef typename T::vtr_colln_t vtr_colln_t;
417  typedef typename T::pool_type pool_type;
418  typedef typename pool_type::joinable joinable;
419 
420  pool_type pool;
421  vtr_colln_t v;
422  v.push_back(1);
423  v.push_back(2);
424  auto const &context=pool<<joinable()<<pool.max_element(v);
425  BOOST_CHECK_EQUAL(*context, 2);
426 }
427 
428 BOOST_AUTO_TEST_CASE_TEMPLATE(min_element_op, T, infinite_test_types) {
429  typedef typename T::vtr_colln_t vtr_colln_t;
430  typedef typename T::pool_type pool_type;
431  typedef typename pool_type::joinable joinable;
432 
433  pool_type pool;
434  vtr_colln_t v;
435  v.push_back(1);
436  v.push_back(2);
437  auto const &context=pool<<joinable()<<pool.min_element(v, std::greater<typename vtr_colln_t::value_type>());
438  BOOST_CHECK_EQUAL(*context, 2);
439 }
440 
441 BOOST_AUTO_TEST_CASE_TEMPLATE(min_element, T, infinite_test_types) {
442  typedef typename T::vtr_colln_t vtr_colln_t;
443  typedef typename T::pool_type pool_type;
444  typedef typename pool_type::joinable joinable;
445 
446  pool_type pool;
447  vtr_colln_t v;
448  v.push_back(1);
449  v.push_back(2);
450  auto const &context=pool<<joinable()<<pool.min_element(v);
451  BOOST_CHECK_EQUAL(*context, 1);
452 }
453 
454 BOOST_AUTO_TEST_CASE_TEMPLATE(merge_op, T, infinite_test_types) {
455  typedef typename T::vtr_colln_t vtr_colln_t;
456  typedef typename T::pool_type pool_type;
457  typedef typename pool_type::joinable joinable;
458 
459  pool_type pool;
460  vtr_colln_t v, v1, v_out;
461  v.push_back(1);
462  v.push_back(2);
463  v1.push_back(1);
464  v1.push_back(2);
465  auto const &context=pool<<joinable()<<pool.merge(v, v1, v_out, std::less<typename vtr_colln_t::value_type>());
466  pool.min_time(vtr_colln_t::memory_access_mode);
467  pool.min_processors(vtr_colln_t::memory_access_mode);
468  *context;
469  BOOST_CHECK_EQUAL(v.size(), 2U);
470  BOOST_CHECK_EQUAL(v1.size(), 2U);
471  BOOST_CHECK_EQUAL(v_out.size(), v.size()+v1.size());
472  BOOST_CHECK_EQUAL(v_out[0], v[0]);
473  BOOST_CHECK_EQUAL(v_out[1], v1[0]);
474  BOOST_CHECK_EQUAL(v_out[2], v[1]);
475  BOOST_CHECK_EQUAL(v_out[3], v1[1]);
476  vtr_colln_t v_chk;
477  std::merge(v.colln().begin(), v.colln().end(), v1.colln().begin(), v1.colln().end(), std::back_inserter(v_chk.colln()), std::less<typename vtr_colln_t::value_type>());
478  BOOST_CHECK(v_out==v_chk);
479 }
480 
481 BOOST_AUTO_TEST_CASE_TEMPLATE(merge, T, infinite_test_types) {
482  typedef typename T::vtr_colln_t vtr_colln_t;
483  typedef typename T::pool_type pool_type;
484  typedef typename pool_type::joinable joinable;
485 
486  pool_type pool;
487  vtr_colln_t v, v1, v_out;
488  v.push_back(1);
489  v.push_back(2);
490  v1.push_back(1);
491  v1.push_back(2);
492  auto const &context=pool<<joinable()<<pool.merge(v, v1, v_out);
493  pool.min_time(vtr_colln_t::memory_access_mode);
494  pool.min_processors(vtr_colln_t::memory_access_mode);
495  *context;
496  BOOST_CHECK_EQUAL(v.size(), 2U);
497  BOOST_CHECK_EQUAL(v1.size(), 2U);
498  BOOST_CHECK_EQUAL(v_out.size(), v.size()+v1.size());
499  BOOST_CHECK_EQUAL(v_out[0], v[0]);
500  BOOST_CHECK_EQUAL(v_out[1], v1[0]);
501  BOOST_CHECK_EQUAL(v_out[2], v[1]);
502  BOOST_CHECK_EQUAL(v_out[3], v1[1]);
503  vtr_colln_t v_chk;
504  std::merge(v.colln().begin(), v.colln().end(), v1.colln().begin(), v1.colln().end(), std::back_inserter(v_chk.colln()));
505  BOOST_CHECK(v_out==v_chk);
506 }
507 
508 BOOST_AUTO_TEST_CASE_TEMPLATE(sort_op_sorted, T, infinite_test_types) {
509  typedef typename T::vtr_colln_t vtr_colln_t;
510  typedef typename T::pool_type pool_type;
511  typedef typename pool_type::joinable joinable;
512 
513  pool_type pool;
514  vtr_colln_t v;
515  v.push_back(1);
516  v.push_back(2);
517  vtr_colln_t v_chk(v);
518  auto const &context=pool<<joinable()<<pool.sort(v, std::greater<typename vtr_colln_t::value_type>());
519  pool.min_time(vtr_colln_t::memory_access_mode);
520  pool.min_processors(vtr_colln_t::memory_access_mode);
521  *context;
522  BOOST_CHECK_EQUAL(v.size(), 2U);
523  BOOST_CHECK_EQUAL(v[0], 2);
524  BOOST_CHECK_EQUAL(v[1], 1);
525  std::sort(v_chk.colln().begin(), v_chk.colln().end(), std::greater<typename vtr_colln_t::value_type>());
526  BOOST_CHECK(v==v_chk);
527 }
528 
529 BOOST_AUTO_TEST_CASE_TEMPLATE(sort_op_unsorted, T, infinite_test_types) {
530  typedef typename T::vtr_colln_t vtr_colln_t;
531  typedef typename T::pool_type pool_type;
532  typedef typename pool_type::joinable joinable;
533 
534  pool_type pool;
535  vtr_colln_t v;
536  v.push_back(2);
537  v.push_back(1);
538  vtr_colln_t v_chk(v);
539  auto const &context=pool<<joinable()<<pool.sort(v, std::greater<typename vtr_colln_t::value_type>());
540  pool.min_time(vtr_colln_t::memory_access_mode);
541  pool.min_processors(vtr_colln_t::memory_access_mode);
542  *context;
543  BOOST_CHECK_EQUAL(v.size(), 2U);
544  BOOST_CHECK_EQUAL(v[0], 2);
545  BOOST_CHECK_EQUAL(v[1], 1);
546  std::sort(v_chk.colln().begin(), v_chk.colln().end(), std::greater<typename vtr_colln_t::value_type>());
547  BOOST_CHECK(v==v_chk);
548 }
549 
550 BOOST_AUTO_TEST_CASE_TEMPLATE(sort_sorted, T, infinite_test_types) {
551  typedef typename T::vtr_colln_t vtr_colln_t;
552  typedef typename T::pool_type pool_type;
553  typedef typename pool_type::joinable joinable;
554 
555  pool_type pool;
556  vtr_colln_t v;
557  v.push_back(1);
558  v.push_back(2);
559  vtr_colln_t v_chk(v);
560  auto const &context=pool<<joinable()<<pool.sort(v);
561  pool.min_time(vtr_colln_t::memory_access_mode);
562  pool.min_processors(vtr_colln_t::memory_access_mode);
563  *context;
564  BOOST_CHECK_EQUAL(v.size(), 2U);
565  BOOST_CHECK_EQUAL(v[0], 1);
566  BOOST_CHECK_EQUAL(v[1], 2);
567  std::sort(v_chk.colln().begin(), v_chk.colln().end());
568  BOOST_CHECK(v==v_chk);
569 }
570 
571 BOOST_AUTO_TEST_CASE_TEMPLATE(sort_unsorted, T, infinite_test_types) {
572  typedef typename T::vtr_colln_t vtr_colln_t;
573  typedef typename T::pool_type pool_type;
574  typedef typename pool_type::joinable joinable;
575 
576  pool_type pool;
577  vtr_colln_t v;
578  v.push_back(2);
579  v.push_back(1);
580  vtr_colln_t v_chk(v);
581  auto const &context=pool<<joinable()<<pool.sort(v);
582  pool.min_time(vtr_colln_t::memory_access_mode);
583  pool.min_processors(vtr_colln_t::memory_access_mode);
584  *context;
585  BOOST_CHECK_EQUAL(v.size(), 2U);
586  BOOST_CHECK_EQUAL(v[0], 1);
587  BOOST_CHECK_EQUAL(v[1], 2);
588  std::sort(v_chk.colln().begin(), v_chk.colln().end());
589  BOOST_CHECK(v==v_chk);
590 }
591 
592 BOOST_AUTO_TEST_SUITE_END()
593 
594 BOOST_AUTO_TEST_SUITE(n_elements)
595 
596 BOOST_AUTO_TEST_CASE_TEMPLATE(max_element_op, T, infinite_test_types) {
597  typedef typename T::vtr_colln_t vtr_colln_t;
598  typedef typename T::pool_type pool_type;
599  typedef typename pool_type::joinable joinable;
600 
601  pool_type pool;
602  vtr_colln_t v;
603  v.push_back(1);
604  v.push_back(2);
605  v.push_back(3);
606  v.push_back(4);
607  v.push_back(5);
608  v.push_back(6);
609  v.push_back(7);
610  v.push_back(8);
611  auto const &context=pool<<joinable()<<pool.max_element(v, std::greater<typename vtr_colln_t::value_type>());
612  BOOST_CHECK_EQUAL(*context, 1);
613 }
614 
615 BOOST_AUTO_TEST_CASE_TEMPLATE(max_element, T, infinite_test_types) {
616  typedef typename T::vtr_colln_t vtr_colln_t;
617  typedef typename T::pool_type pool_type;
618  typedef typename pool_type::joinable joinable;
619 
620  pool_type pool;
621  vtr_colln_t v;
622  v.push_back(1);
623  v.push_back(2);
624  v.push_back(3);
625  v.push_back(4);
626  v.push_back(5);
627  v.push_back(6);
628  v.push_back(7);
629  v.push_back(8);
630  auto const &context=pool<<joinable()<<pool.max_element(v);
631  BOOST_CHECK_EQUAL(*context, 8);
632 }
633 
634 BOOST_AUTO_TEST_CASE_TEMPLATE(min_element_op, T, infinite_test_types) {
635  typedef typename T::vtr_colln_t vtr_colln_t;
636  typedef typename T::pool_type pool_type;
637  typedef typename pool_type::joinable joinable;
638 
639  pool_type pool;
640  vtr_colln_t v;
641  v.push_back(1);
642  v.push_back(2);
643  v.push_back(3);
644  v.push_back(4);
645  v.push_back(5);
646  v.push_back(6);
647  v.push_back(7);
648  v.push_back(8);
649  auto const &context=pool<<joinable()<<pool.min_element(v, std::greater<typename vtr_colln_t::value_type>());
650  BOOST_CHECK_EQUAL(*context, 8);
651 }
652 
653 BOOST_AUTO_TEST_CASE_TEMPLATE(min_element, T, infinite_test_types) {
654  typedef typename T::vtr_colln_t vtr_colln_t;
655  typedef typename T::pool_type pool_type;
656  typedef typename pool_type::joinable joinable;
657 
658  pool_type pool;
659  vtr_colln_t v;
660  v.push_back(1);
661  v.push_back(2);
662  v.push_back(3);
663  v.push_back(4);
664  v.push_back(5);
665  v.push_back(6);
666  v.push_back(7);
667  v.push_back(8);
668  auto const &context=pool<<joinable()<<pool.min_element(v);
669  BOOST_CHECK_EQUAL(*context, 1);
670 }
671 
672 BOOST_AUTO_TEST_CASE_TEMPLATE(merge_op, T, infinite_test_types) {
673  typedef typename T::vtr_colln_t vtr_colln_t;
674  typedef typename T::pool_type pool_type;
675  typedef typename pool_type::joinable joinable;
676 
677  pool_type pool;
678  vtr_colln_t v, v1, v_out;
679  v.push_back(1);
680  v.push_back(3);
681  v.push_back(5);
682  v.push_back(7);
683  v.push_back(9);
684  v.push_back(11);
685  v.push_back(13);
686  v.push_back(15);
687  v1.push_back(2);
688  v1.push_back(4);
689  v1.push_back(6);
690  v1.push_back(8);
691  v1.push_back(10);
692  v1.push_back(12);
693  v1.push_back(14);
694  v1.push_back(16);
695  auto const &context=pool<<joinable()<<pool.merge(v, v1, v_out, std::less<typename vtr_colln_t::value_type>());
696  pool.min_time(vtr_colln_t::memory_access_mode);
697  pool.min_processors(vtr_colln_t::memory_access_mode);
698  *context;
699  BOOST_CHECK_EQUAL(v.size(), 8U);
700  BOOST_CHECK_EQUAL(v1.size(), 8U);
701  BOOST_CHECK_EQUAL(v_out.size(), v.size()+v1.size());
702  BOOST_CHECK_EQUAL(v_out[0], v[0]);
703  BOOST_CHECK_EQUAL(v_out[1], v1[0]);
704  BOOST_CHECK_EQUAL(v_out[2], v[1]);
705  BOOST_CHECK_EQUAL(v_out[3], v1[1]);
706  BOOST_CHECK_EQUAL(v_out[4], v[2]);
707  BOOST_CHECK_EQUAL(v_out[5], v1[2]);
708  BOOST_CHECK_EQUAL(v_out[6], v[3]);
709  BOOST_CHECK_EQUAL(v_out[7], v1[3]);
710  BOOST_CHECK_EQUAL(v_out[8], v[4]);
711  BOOST_CHECK_EQUAL(v_out[9], v1[4]);
712  BOOST_CHECK_EQUAL(v_out[10], v[5]);
713  BOOST_CHECK_EQUAL(v_out[11], v1[5]);
714  BOOST_CHECK_EQUAL(v_out[12], v[6]);
715  BOOST_CHECK_EQUAL(v_out[13], v1[6]);
716  BOOST_CHECK_EQUAL(v_out[14], v[7]);
717  BOOST_CHECK_EQUAL(v_out[15], v1[7]);
718  vtr_colln_t v_chk;
719  std::merge(v.colln().begin(), v.colln().end(), v1.colln().begin(), v1.colln().end(), std::back_inserter(v_chk.colln()), std::less<typename vtr_colln_t::value_type>());
720  BOOST_CHECK(v_out==v_chk);
721 }
722 
723 BOOST_AUTO_TEST_CASE_TEMPLATE(merge, T, infinite_test_types) {
724  typedef typename T::vtr_colln_t vtr_colln_t;
725  typedef typename T::pool_type pool_type;
726  typedef typename pool_type::joinable joinable;
727 
728  pool_type pool;
729  vtr_colln_t v, v1, v_out;
730  v.push_back(1);
731  v.push_back(3);
732  v.push_back(5);
733  v.push_back(7);
734  v.push_back(9);
735  v.push_back(11);
736  v.push_back(13);
737  v.push_back(15);
738  v1.push_back(2);
739  v1.push_back(4);
740  v1.push_back(6);
741  v1.push_back(8);
742  v1.push_back(10);
743  v1.push_back(12);
744  v1.push_back(14);
745  v1.push_back(16);
746  auto const &context=pool<<joinable()<<pool.merge(v, v1, v_out);
747  pool.min_time(vtr_colln_t::memory_access_mode);
748  pool.min_processors(vtr_colln_t::memory_access_mode);
749  *context;
750  BOOST_CHECK_EQUAL(v.size(), 8U);
751  BOOST_CHECK_EQUAL(v1.size(), 8U);
752  BOOST_CHECK_EQUAL(v_out.size(), v.size()+v1.size());
753  BOOST_CHECK_EQUAL(v_out[0], v[0]);
754  BOOST_CHECK_EQUAL(v_out[1], v1[0]);
755  BOOST_CHECK_EQUAL(v_out[2], v[1]);
756  BOOST_CHECK_EQUAL(v_out[3], v1[1]);
757  BOOST_CHECK_EQUAL(v_out[4], v[2]);
758  BOOST_CHECK_EQUAL(v_out[5], v1[2]);
759  BOOST_CHECK_EQUAL(v_out[6], v[3]);
760  BOOST_CHECK_EQUAL(v_out[7], v1[3]);
761  BOOST_CHECK_EQUAL(v_out[8], v[4]);
762  BOOST_CHECK_EQUAL(v_out[9], v1[4]);
763  BOOST_CHECK_EQUAL(v_out[10], v[5]);
764  BOOST_CHECK_EQUAL(v_out[11], v1[5]);
765  BOOST_CHECK_EQUAL(v_out[12], v[6]);
766  BOOST_CHECK_EQUAL(v_out[13], v1[6]);
767  BOOST_CHECK_EQUAL(v_out[14], v[7]);
768  BOOST_CHECK_EQUAL(v_out[15], v1[7]);
769  vtr_colln_t v_chk;
770  std::merge(v.colln().begin(), v.colln().end(), v1.colln().begin(), v1.colln().end(), std::back_inserter(v_chk.colln()));
771  BOOST_CHECK(v_out==v_chk);
772 }
773 
774 BOOST_AUTO_TEST_CASE_TEMPLATE(sort_op_sorted, T, infinite_test_types) {
775  typedef typename T::vtr_colln_t vtr_colln_t;
776  typedef typename T::pool_type pool_type;
777  typedef typename pool_type::joinable joinable;
778 
779  pool_type pool;
780  vtr_colln_t v;
781  v.push_back(1);
782  v.push_back(2);
783  v.push_back(3);
784  v.push_back(4);
785  v.push_back(5);
786  v.push_back(6);
787  v.push_back(7);
788  v.push_back(8);
789  vtr_colln_t v_chk(v);
790  auto const &context=pool<<joinable()<<pool.sort(v, std::greater<typename vtr_colln_t::value_type>());
791  pool.min_time(vtr_colln_t::memory_access_mode);
792  pool.min_processors(vtr_colln_t::memory_access_mode);
793  *context;
794  BOOST_CHECK_EQUAL(v.size(), 8U);
795  BOOST_CHECK_EQUAL(v[0], 8);
796  BOOST_CHECK_EQUAL(v[1], 7);
797  BOOST_CHECK_EQUAL(v[2], 6);
798  BOOST_CHECK_EQUAL(v[3], 5);
799  BOOST_CHECK_EQUAL(v[4], 4);
800  BOOST_CHECK_EQUAL(v[5], 3);
801  BOOST_CHECK_EQUAL(v[6], 2);
802  BOOST_CHECK_EQUAL(v[7], 1);
803  std::sort(v_chk.colln().begin(), v_chk.colln().end(), std::greater<typename vtr_colln_t::value_type>());
804  BOOST_CHECK(v==v_chk);
805 }
806 
807 BOOST_AUTO_TEST_CASE_TEMPLATE(sort_op_unsorted, T, infinite_test_types) {
808  typedef typename T::vtr_colln_t vtr_colln_t;
809  typedef typename T::pool_type pool_type;
810  typedef typename pool_type::joinable joinable;
811 
812  pool_type pool;
813  vtr_colln_t v;
814  v.push_back(8);
815  v.push_back(7);
816  v.push_back(6);
817  v.push_back(5);
818  v.push_back(4);
819  v.push_back(3);
820  v.push_back(2);
821  v.push_back(1);
822  vtr_colln_t v_chk(v);
823  auto const &context=pool<<joinable()<<pool.sort(v, std::greater<typename vtr_colln_t::value_type>());
824  pool.min_time(vtr_colln_t::memory_access_mode);
825  pool.min_processors(vtr_colln_t::memory_access_mode);
826  *context;
827  BOOST_CHECK_EQUAL(v.size(), 8U);
828  BOOST_CHECK_EQUAL(v[0], 8);
829  BOOST_CHECK_EQUAL(v[1], 7);
830  BOOST_CHECK_EQUAL(v[2], 6);
831  BOOST_CHECK_EQUAL(v[3], 5);
832  BOOST_CHECK_EQUAL(v[4], 4);
833  BOOST_CHECK_EQUAL(v[5], 3);
834  BOOST_CHECK_EQUAL(v[6], 2);
835  BOOST_CHECK_EQUAL(v[7], 1);
836  std::sort(v_chk.colln().begin(), v_chk.colln().end(), std::greater<typename vtr_colln_t::value_type>());
837  BOOST_CHECK(v==v_chk);
838 }
839 
840 BOOST_AUTO_TEST_CASE_TEMPLATE(sort_sorted, T, infinite_test_types) {
841  typedef typename T::vtr_colln_t vtr_colln_t;
842  typedef typename T::pool_type pool_type;
843  typedef typename pool_type::joinable joinable;
844 
845  pool_type pool;
846  vtr_colln_t v;
847  v.push_back(1);
848  v.push_back(2);
849  v.push_back(3);
850  v.push_back(4);
851  v.push_back(5);
852  v.push_back(6);
853  v.push_back(7);
854  v.push_back(8);
855  vtr_colln_t v_chk(v);
856  auto const &context=pool<<joinable()<<pool.sort(v);
857  pool.min_time(vtr_colln_t::memory_access_mode);
858  pool.min_processors(vtr_colln_t::memory_access_mode);
859  *context;
860  BOOST_CHECK_EQUAL(v.size(), 8U);
861  BOOST_CHECK_EQUAL(v[0], 1);
862  BOOST_CHECK_EQUAL(v[1], 2);
863  BOOST_CHECK_EQUAL(v[2], 3);
864  BOOST_CHECK_EQUAL(v[3], 4);
865  BOOST_CHECK_EQUAL(v[4], 5);
866  BOOST_CHECK_EQUAL(v[5], 6);
867  BOOST_CHECK_EQUAL(v[6], 7);
868  BOOST_CHECK_EQUAL(v[7], 8);
869  std::sort(v_chk.colln().begin(), v_chk.colln().end());
870  BOOST_CHECK(v==v_chk);
871 }
872 
873 BOOST_AUTO_TEST_CASE_TEMPLATE(sort_unsorted, T, infinite_test_types) {
874  typedef typename T::vtr_colln_t vtr_colln_t;
875  typedef typename T::pool_type pool_type;
876  typedef typename pool_type::joinable joinable;
877 
878  pool_type pool;
879  vtr_colln_t v;
880  v.push_back(8);
881  v.push_back(7);
882  v.push_back(6);
883  v.push_back(5);
884  v.push_back(4);
885  v.push_back(3);
886  v.push_back(2);
887  v.push_back(1);
888  vtr_colln_t v_chk(v);
889  auto const &context=pool<<joinable()<<pool.sort(v);
890  pool.min_time(vtr_colln_t::memory_access_mode);
891  pool.min_processors(vtr_colln_t::memory_access_mode);
892  *context;
893  BOOST_CHECK_EQUAL(v.size(), 8U);
894  BOOST_CHECK_EQUAL(v[0], 1);
895  BOOST_CHECK_EQUAL(v[1], 2);
896  BOOST_CHECK_EQUAL(v[2], 3);
897  BOOST_CHECK_EQUAL(v[3], 4);
898  BOOST_CHECK_EQUAL(v[4], 5);
899  BOOST_CHECK_EQUAL(v[5], 6);
900  BOOST_CHECK_EQUAL(v[6], 7);
901  BOOST_CHECK_EQUAL(v[7], 8);
902  std::sort(v_chk.colln().begin(), v_chk.colln().end());
903  BOOST_CHECK(v==v_chk);
904 }
905 
906 BOOST_AUTO_TEST_SUITE_END()
907 
908 BOOST_AUTO_TEST_SUITE_END()
909 
910 BOOST_AUTO_TEST_SUITE_END()
911 
912 BOOST_AUTO_TEST_SUITE_END()
913 
914 BOOST_AUTO_TEST_SUITE_END()