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