tlx
bose_nelson_parameter.hpp
Go to the documentation of this file.
1 /*******************************************************************************
2  * tlx/sort/networks/bose_nelson_parameter.hpp
3  *
4  * Recursively called Bose-Nelson sorting networks processing parameters instead
5  * of an array.
6  *
7  * Part of tlx - http://panthema.net/tlx
8  *
9  * Copyright (C) 2018-2020 Jasper Marianczuk <jasper.marianczuk@gmail.com>
10  * Copyright (C) 2020 Timo Bingmann <tb@panthema.net>
11  *
12  * All rights reserved. Published under the Boost Software License, Version 1.0
13  ******************************************************************************/
14 
15 #ifndef TLX_SORT_NETWORKS_BOSE_NELSON_PARAMETER_HEADER
16 #define TLX_SORT_NETWORKS_BOSE_NELSON_PARAMETER_HEADER
17 
19 
20 #include <functional>
21 
22 namespace tlx {
23 
24 //! Implementations of sorting networks for up to sixteen elements.
25 namespace sort_networks {
26 
27 //! \addtogroup tlx_sort
28 //! \{
29 //! \name Implementations of Sorting Networks
30 //! \{
31 
32 //! Implementation of Bose-Nelson sorting networks for up to sixteen elements
33 //! processing parameters instead of an array.
34 namespace bose_nelson_parameter {
35 
36 //! default conditional swap implementation
37 template <typename ValueType>
39 
40 /*----------------------------------------------------------------------------*/
41 
42 //! merge network for element arrays length one and one
43 template <typename ValueType, typename CSwap>
44 static inline
45 void merge_1_1(ValueType& a0, ValueType& b0, CSwap cswap) {
46  cswap(a0, b0);
47 }
48 
49 //! merge network for element arrays length one and two
50 template <typename ValueType, typename CSwap>
51 static inline
52 void merge_1_2(ValueType& a0, ValueType& b0, ValueType& b1, CSwap cswap) {
53  cswap(a0, b1);
54  cswap(a0, b0);
55 }
56 
57 //! merge network for element arrays length two and one
58 template <typename ValueType, typename CSwap>
59 static inline
60 void merge_2_1(ValueType& a0, ValueType& a1, ValueType& b0, CSwap cswap) {
61  cswap(a0, b0);
62  cswap(a1, b0);
63 }
64 
65 //! merge network for element arrays length two and two
66 template <typename ValueType, typename CSwap>
67 static inline
68 void merge_2_2(ValueType& a0, ValueType& a1, ValueType& b0, ValueType& b1,
69  CSwap cswap) {
70  merge_1_1(a0, b0, cswap);
71  merge_1_1(a1, b1, cswap);
72  merge_1_1(a1, b0, cswap);
73 }
74 
75 //! merge network for element arrays length two and three
76 template <typename ValueType, typename CSwap>
77 static inline
78 void merge_2_3(ValueType& a0, ValueType& a1, ValueType& b0, ValueType& b1,
79  ValueType& b2, CSwap cswap) {
80  merge_1_2(a0, b0, b1, cswap);
81  merge_1_1(a1, b2, cswap);
82  merge_1_2(a1, b0, b1, cswap);
83 }
84 
85 //! merge network for element arrays length three and two
86 template <typename ValueType, typename CSwap>
87 static inline
88 void merge_3_2(ValueType& a0, ValueType& a1, ValueType& a2, ValueType& b0,
89  ValueType& b1, CSwap cswap) {
90  merge_1_1(a0, b0, cswap);
91  merge_2_1(a1, a2, b1, cswap);
92  merge_2_1(a1, a2, b0, cswap);
93 }
94 
95 //! merge network for element arrays length three and three
96 template <typename ValueType, typename CSwap>
97 static inline
98 void merge_3_3(ValueType& a0, ValueType& a1, ValueType& a2, ValueType& b0,
99  ValueType& b1, ValueType& b2, CSwap cswap) {
100  merge_1_1(a0, b0, cswap);
101  merge_2_2(a1, a2, b1, b2, cswap);
102  merge_2_1(a1, a2, b0, cswap);
103 }
104 
105 //! merge network for element arrays length three and four
106 template <typename ValueType, typename CSwap>
107 static inline
108 void merge_3_4(ValueType& a0, ValueType& a1, ValueType& a2, ValueType& b0,
109  ValueType& b1, ValueType& b2, ValueType& b3, CSwap cswap) {
110  merge_1_2(a0, b0, b1, cswap);
111  merge_2_2(a1, a2, b2, b3, cswap);
112  merge_2_2(a1, a2, b0, b1, cswap);
113 }
114 
115 //! merge network for element arrays length four and three
116 template <typename ValueType, typename CSwap>
117 static inline
118 void merge_4_3(ValueType& a0, ValueType& a1, ValueType& a2, ValueType& a3,
119  ValueType& b0, ValueType& b1, ValueType& b2, CSwap cswap) {
120  merge_2_2(a0, a1, b0, b1, cswap);
121  merge_2_1(a2, a3, b2, cswap);
122  merge_2_2(a2, a3, b0, b1, cswap);
123 }
124 
125 //! merge network for element arrays length four and four
126 template <typename ValueType, typename CSwap>
127 static inline
128 void merge_4_4(ValueType& a0, ValueType& a1, ValueType& a2, ValueType& a3,
129  ValueType& b0, ValueType& b1, ValueType& b2, ValueType& b3,
130  CSwap cswap) {
131  merge_2_2(a0, a1, b0, b1, cswap);
132  merge_2_2(a2, a3, b2, b3, cswap);
133  merge_2_2(a2, a3, b0, b1, cswap);
134 }
135 
136 //! merge network for element arrays length four and five
137 template <typename ValueType, typename CSwap>
138 static inline
139 void merge_4_5(ValueType& a0, ValueType& a1, ValueType& a2, ValueType& a3,
140  ValueType& b0, ValueType& b1, ValueType& b2, ValueType& b3,
141  ValueType& b4, CSwap cswap) {
142  merge_2_3(a0, a1, b0, b1, b2, cswap);
143  merge_2_2(a2, a3, b3, b4, cswap);
144  merge_2_3(a2, a3, b0, b1, b2, cswap);
145 }
146 
147 //! merge network for element arrays length five and five
148 template <typename ValueType, typename CSwap>
149 static inline
150 void merge_5_5(ValueType& a0, ValueType& a1, ValueType& a2, ValueType& a3,
151  ValueType& a4, ValueType& b0, ValueType& b1, ValueType& b2,
152  ValueType& b3, ValueType& b4, CSwap cswap) {
153  merge_2_2(a0, a1, b0, b1, cswap);
154  merge_3_3(a2, a3, a4, b2, b3, b4, cswap);
155  merge_3_2(a2, a3, a4, b0, b1, cswap);
156 }
157 
158 //! merge network for element arrays length five and six
159 template <typename ValueType, typename CSwap>
160 static inline
161 void merge_5_6(ValueType& a0, ValueType& a1, ValueType& a2, ValueType& a3,
162  ValueType& a4, ValueType& b0, ValueType& b1, ValueType& b2,
163  ValueType& b3, ValueType& b4, ValueType& b5, CSwap cswap) {
164  merge_2_3(a0, a1, b0, b1, b2, cswap);
165  merge_3_3(a2, a3, a4, b3, b4, b5, cswap);
166  merge_3_3(a2, a3, a4, b0, b1, b2, cswap);
167 }
168 
169 //! merge network for element arrays length six and six
170 template <typename ValueType, typename CSwap>
171 static inline
172 void merge_6_6(ValueType& a0, ValueType& a1, ValueType& a2, ValueType& a3,
173  ValueType& a4, ValueType& a5, ValueType& b0, ValueType& b1,
174  ValueType& b2, ValueType& b3, ValueType& b4, ValueType& b5,
175  CSwap cswap) {
176  merge_3_3(a0, a1, a2, b0, b1, b2, cswap);
177  merge_3_3(a3, a4, a5, b3, b4, b5, cswap);
178  merge_3_3(a3, a4, a5, b0, b1, b2, cswap);
179 }
180 
181 //! merge network for element arrays length six and seven
182 template <typename ValueType, typename CSwap>
183 static inline
184 void merge_6_7(ValueType& a0, ValueType& a1, ValueType& a2, ValueType& a3,
185  ValueType& a4, ValueType& a5, ValueType& b0, ValueType& b1,
186  ValueType& b2, ValueType& b3, ValueType& b4, ValueType& b5,
187  ValueType& b6, CSwap cswap) {
188  merge_3_4(a0, a1, a2, b0, b1, b2, b3, cswap);
189  merge_3_3(a3, a4, a5, b4, b5, b6, cswap);
190  merge_3_4(a3, a4, a5, b0, b1, b2, b3, cswap);
191 }
192 
193 //! merge network for element arrays length seven and seven
194 template <typename ValueType, typename CSwap>
195 static inline
196 void merge_7_7(ValueType& a0, ValueType& a1, ValueType& a2, ValueType& a3,
197  ValueType& a4, ValueType& a5, ValueType& a6, ValueType& b0,
198  ValueType& b1, ValueType& b2, ValueType& b3, ValueType& b4,
199  ValueType& b5, ValueType& b6, CSwap cswap) {
200  merge_3_3(a0, a1, a2, b0, b1, b2, cswap);
201  merge_4_4(a3, a4, a5, a6, b3, b4, b5, b6, cswap);
202  merge_4_3(a3, a4, a5, a6, b0, b1, b2, cswap);
203 }
204 
205 //! merge network for element arrays length seven and eight
206 template <typename ValueType, typename CSwap>
207 static inline
208 void merge_7_8(ValueType& a0, ValueType& a1, ValueType& a2, ValueType& a3,
209  ValueType& a4, ValueType& a5, ValueType& a6, ValueType& b0,
210  ValueType& b1, ValueType& b2, ValueType& b3, ValueType& b4,
211  ValueType& b5, ValueType& b6, ValueType& b7, CSwap cswap) {
212  merge_3_4(a0, a1, a2, b0, b1, b2, b3, cswap);
213  merge_4_4(a3, a4, a5, a6, b4, b5, b6, b7, cswap);
214  merge_4_4(a3, a4, a5, a6, b0, b1, b2, b3, cswap);
215 }
216 
217 //! merge network for element arrays length eight and eight
218 template <typename ValueType, typename CSwap>
219 static inline
220 void merge_8_8(ValueType& a0, ValueType& a1, ValueType& a2, ValueType& a3,
221  ValueType& a4, ValueType& a5, ValueType& a6, ValueType& a7,
222  ValueType& b0, ValueType& b1, ValueType& b2, ValueType& b3,
223  ValueType& b4, ValueType& b5, ValueType& b6, ValueType& b7,
224  CSwap cswap) {
225  merge_4_4(a0, a1, a2, a3, b0, b1, b2, b3, cswap);
226  merge_4_4(a4, a5, a6, a7, b4, b5, b6, b7, cswap);
227  merge_4_4(a4, a5, a6, a7, b0, b1, b2, b3, cswap);
228 }
229 
230 /*----------------------------------------------------------------------------*/
231 
232 //! Bose-Nelson sorting network for two elements
233 template <typename ValueType, typename CSwap = DefaultCSwap<ValueType> >
234 static inline
235 void sort2(ValueType& x0, ValueType& x1, CSwap cswap = CSwap()) {
236  merge_1_1(x0, x1, cswap);
237 }
238 
239 //! Bose-Nelson sorting network for three elements
240 template <typename ValueType, typename CSwap = DefaultCSwap<ValueType> >
241 static inline
242 void sort3(ValueType& x0, ValueType& x1, ValueType& x2, CSwap cswap = CSwap()) {
243  sort2(x1, x2, cswap);
244  merge_1_2(x0, x1, x2, cswap);
245 }
246 
247 //! Bose-Nelson sorting network for four elements
248 template <typename ValueType, typename CSwap = DefaultCSwap<ValueType> >
249 static inline
250 void sort4(ValueType& x0, ValueType& x1, ValueType& x2, ValueType& x3,
251  CSwap cswap = CSwap()) {
252  sort2(x0, x1, cswap);
253  sort2(x2, x3, cswap);
254  merge_2_2(x0, x1, x2, x3, cswap);
255 }
256 
257 //! Bose-Nelson sorting network for five elements
258 template <typename ValueType, typename CSwap = DefaultCSwap<ValueType> >
259 static inline
260 void sort5(ValueType& x0, ValueType& x1, ValueType& x2, ValueType& x3,
261  ValueType& x4, CSwap cswap = CSwap()) {
262  sort2(x0, x1, cswap);
263  sort3(x2, x3, x4, cswap);
264  merge_2_3(x0, x1, x2, x3, x4, cswap);
265 }
266 
267 //! Bose-Nelson sorting network for six elements
268 template <typename ValueType, typename CSwap = DefaultCSwap<ValueType> >
269 static inline
270 void sort6(ValueType& x0, ValueType& x1, ValueType& x2, ValueType& x3,
271  ValueType& x4, ValueType& x5, CSwap cswap = CSwap()) {
272  sort3(x0, x1, x2, cswap);
273  sort3(x3, x4, x5, cswap);
274  merge_3_3(x0, x1, x2, x3, x4, x5, cswap);
275 }
276 
277 //! Bose-Nelson sorting network for seven elements
278 template <typename ValueType, typename CSwap = DefaultCSwap<ValueType> >
279 static inline
280 void sort7(ValueType& x0, ValueType& x1, ValueType& x2, ValueType& x3,
281  ValueType& x4, ValueType& x5, ValueType& x6, CSwap cswap = CSwap()) {
282  sort3(x0, x1, x2, cswap);
283  sort4(x3, x4, x5, x6, cswap);
284  merge_3_4(x0, x1, x2,
285  x3, x4, x5, x6, cswap);
286 }
287 
288 //! Bose-Nelson sorting network for eight elements
289 template <typename ValueType, typename CSwap = DefaultCSwap<ValueType> >
290 static inline
291 void sort8(ValueType& x0, ValueType& x1, ValueType& x2, ValueType& x3,
292  ValueType& x4, ValueType& x5, ValueType& x6, ValueType& x7,
293  CSwap cswap = CSwap()) {
294  sort4(x0, x1, x2, x3, cswap);
295  sort4(x4, x5, x6, x7, cswap);
296  merge_4_4(x0, x1, x2, x3,
297  x4, x5, x6, x7, cswap);
298 }
299 
300 //! Bose-Nelson sorting network for nine elements
301 template <typename ValueType, typename CSwap = DefaultCSwap<ValueType> >
302 static inline
303 void sort9(ValueType& x0, ValueType& x1, ValueType& x2, ValueType& x3,
304  ValueType& x4, ValueType& x5, ValueType& x6, ValueType& x7,
305  ValueType& x8, CSwap cswap = CSwap()) {
306  sort4(x0, x1, x2, x3, cswap);
307  sort5(x4, x5, x6, x7, x8, cswap);
308  merge_4_5(x0, x1, x2, x3,
309  x4, x5, x6, x7, x8, cswap);
310 }
311 
312 //! Bose-Nelson sorting network for ten elements
313 template <typename ValueType, typename CSwap = DefaultCSwap<ValueType> >
314 static inline
315 void sort10(ValueType& x0, ValueType& x1, ValueType& x2, ValueType& x3,
316  ValueType& x4, ValueType& x5, ValueType& x6, ValueType& x7,
317  ValueType& x8, ValueType& x9, CSwap cswap = CSwap()) {
318  sort5(x0, x1, x2, x3, x4, cswap);
319  sort5(x5, x6, x7, x8, x9, cswap);
320  merge_5_5(x0, x1, x2, x3, x4,
321  x5, x6, x7, x8, x9, cswap);
322 }
323 
324 //! Bose-Nelson sorting network for eleven elements
325 template <typename ValueType, typename CSwap = DefaultCSwap<ValueType> >
326 static inline
327 void sort11(ValueType& x0, ValueType& x1, ValueType& x2, ValueType& x3,
328  ValueType& x4, ValueType& x5, ValueType& x6, ValueType& x7,
329  ValueType& x8, ValueType& x9, ValueType& x10,
330  CSwap cswap = CSwap()) {
331  sort5(x0, x1, x2, x3, x4, cswap);
332  sort6(x5, x6, x7, x8, x9, x10, cswap);
333  merge_5_6(x0, x1, x2, x3, x4,
334  x5, x6, x7, x8, x9, x10, cswap);
335 }
336 
337 //! Bose-Nelson sorting network for twelve elements
338 template <typename ValueType, typename CSwap = DefaultCSwap<ValueType> >
339 static inline
340 void sort12(ValueType& x0, ValueType& x1, ValueType& x2, ValueType& x3,
341  ValueType& x4, ValueType& x5, ValueType& x6, ValueType& x7,
342  ValueType& x8, ValueType& x9, ValueType& x10, ValueType& x11,
343  CSwap cswap = CSwap()) {
344  sort6(x0, x1, x2, x3, x4, x5, cswap);
345  sort6(x6, x7, x8, x9, x10, x11, cswap);
346  merge_6_6(x0, x1, x2, x3, x4, x5,
347  x6, x7, x8, x9, x10, x11, cswap);
348 }
349 
350 //! Bose-Nelson sorting network for thirteen elements
351 template <typename ValueType, typename CSwap = DefaultCSwap<ValueType> >
352 static inline
353 void sort13(ValueType& x0, ValueType& x1, ValueType& x2, ValueType& x3,
354  ValueType& x4, ValueType& x5, ValueType& x6, ValueType& x7,
355  ValueType& x8, ValueType& x9, ValueType& x10, ValueType& x11,
356  ValueType& x12, CSwap cswap = CSwap()) {
357  sort6(x0, x1, x2, x3, x4, x5, cswap);
358  sort7(x6, x7, x8, x9, x10, x11, x12, cswap);
359  merge_6_7(x0, x1, x2, x3, x4, x5,
360  x6, x7, x8, x9, x10, x11, x12, cswap);
361 }
362 
363 //! Bose-Nelson sorting network for fourteen elements
364 template <typename ValueType, typename CSwap = DefaultCSwap<ValueType> >
365 static inline
366 void sort14(ValueType& x0, ValueType& x1, ValueType& x2, ValueType& x3,
367  ValueType& x4, ValueType& x5, ValueType& x6, ValueType& x7,
368  ValueType& x8, ValueType& x9, ValueType& x10, ValueType& x11,
369  ValueType& x12, ValueType& x13, CSwap cswap = CSwap()) {
370  sort7(x0, x1, x2, x3, x4, x5, x6, cswap);
371  sort7(x7, x8, x9, x10, x11, x12, x13, cswap);
372  merge_7_7(x0, x1, x2, x3, x4, x5, x6,
373  x7, x8, x9, x10, x11, x12, x13, cswap);
374 }
375 
376 //! Bose-Nelson sorting network for fifteen elements
377 template <typename ValueType, typename CSwap = DefaultCSwap<ValueType> >
378 static inline
379 void sort15(ValueType& x0, ValueType& x1, ValueType& x2, ValueType& x3,
380  ValueType& x4, ValueType& x5, ValueType& x6, ValueType& x7,
381  ValueType& x8, ValueType& x9, ValueType& x10, ValueType& x11,
382  ValueType& x12, ValueType& x13, ValueType& x14,
383  CSwap cswap = CSwap()) {
384  sort7(x0, x1, x2, x3, x4, x5, x6, cswap);
385  sort8(x7, x8, x9, x10, x11, x12, x13, x14, cswap);
386  merge_7_8(x0, x1, x2, x3, x4, x5, x6,
387  x7, x8, x9, x10, x11, x12, x13, x14, cswap);
388 }
389 
390 //! Bose-Nelson sorting network for sixteen elements
391 template <typename ValueType, typename CSwap = DefaultCSwap<ValueType> >
392 static inline
393 void sort16(ValueType& x0, ValueType& x1, ValueType& x2, ValueType& x3,
394  ValueType& x4, ValueType& x5, ValueType& x6, ValueType& x7,
395  ValueType& x8, ValueType& x9, ValueType& x10, ValueType& x11,
396  ValueType& x12, ValueType& x13, ValueType& x14, ValueType& x15,
397  CSwap cswap = CSwap()) {
398  sort8(x0, x1, x2, x3, x4, x5, x6, x7, cswap);
399  sort8(x8, x9, x10, x11, x12, x13, x14, x15, cswap);
400  merge_8_8(x0, x1, x2, x3, x4, x5, x6, x7,
401  x8, x9, x10, x11, x12, x13, x14, x15, cswap);
402 }
403 
404 /*----------------------------------------------------------------------------*/
405 
406 //! Call Bose-Network sorting network for up to sixteen elements with given
407 //! comparison method
408 template <typename Iterator, typename Comparator =
409  std::less<typename std::iterator_traits<Iterator>::value_type> >
410 static void sort(Iterator a, Iterator b, Comparator cmp = Comparator()) {
411  CS_IfSwap<Comparator> cswap(cmp);
412 
413  switch (b - a) {
414  case 0:
415  break;
416  case 1:
417  break;
418  case 2:
419  sort2(a[0], a[1], cswap);
420  break;
421  case 3:
422  sort3(a[0], a[1], a[2], cswap);
423  break;
424  case 4:
425  sort4(a[0], a[1], a[2], a[3], cswap);
426  break;
427  case 5:
428  sort5(a[0], a[1], a[2], a[3], a[4], cswap);
429  break;
430  case 6:
431  sort6(a[0], a[1], a[2], a[3], a[4], a[5], cswap);
432  break;
433  case 7:
434  sort7(a[0], a[1], a[2], a[3], a[4], a[5], a[6], cswap);
435  break;
436  case 8:
437  sort8(a[0], a[1], a[2], a[3], a[4], a[5], a[6], a[7], cswap);
438  break;
439  case 9:
440  sort9(a[0], a[1], a[2], a[3], a[4], a[5], a[6], a[7], a[8], cswap);
441  break;
442  case 10:
443  sort10(a[0], a[1], a[2], a[3], a[4], a[5], a[6], a[7], a[8], a[9],
444  cswap);
445  break;
446  case 11:
447  sort11(a[0], a[1], a[2], a[3], a[4], a[5], a[6], a[7], a[8], a[9],
448  a[10], cswap);
449  break;
450  case 12:
451  sort12(a[0], a[1], a[2], a[3], a[4], a[5], a[6], a[7], a[8], a[9],
452  a[10], a[11], cswap);
453  break;
454  case 13:
455  sort13(a[0], a[1], a[2], a[3], a[4], a[5], a[6], a[7], a[8], a[9],
456  a[10], a[11], a[12], cswap);
457  break;
458  case 14:
459  sort14(a[0], a[1], a[2], a[3], a[4], a[5], a[6], a[7], a[8], a[9],
460  a[10], a[11], a[12], a[13], cswap);
461  break;
462  case 15:
463  sort15(a[0], a[1], a[2], a[3], a[4], a[5], a[6], a[7], a[8], a[9],
464  a[10], a[11], a[12], a[13], a[14], cswap);
465  break;
466  case 16:
467  sort16(a[0], a[1], a[2], a[3], a[4], a[5], a[6], a[7], a[8], a[9],
468  a[10], a[11], a[12], a[13], a[14], a[15], cswap);
469  break;
470  default:
471  abort();
472  break;
473  }
474 }
475 
476 } // namespace bose_nelson_parameter
477 
478 /******************************************************************************/
479 
480 //! \}
481 //! \}
482 
483 } // namespace sort_networks
484 } // namespace tlx
485 
486 #endif // !TLX_SORT_NETWORKS_BOSE_NELSON_PARAMETER_HEADER
487 
488 /******************************************************************************/
static void merge_3_3(ValueType &a0, ValueType &a1, ValueType &a2, ValueType &b0, ValueType &b1, ValueType &b2, CSwap cswap)
merge network for element arrays length three and three
static void merge_3_4(ValueType &a0, ValueType &a1, ValueType &a2, ValueType &b0, ValueType &b1, ValueType &b2, ValueType &b3, CSwap cswap)
merge network for element arrays length three and four
static void sort14(ValueType &x0, ValueType &x1, ValueType &x2, ValueType &x3, ValueType &x4, ValueType &x5, ValueType &x6, ValueType &x7, ValueType &x8, ValueType &x9, ValueType &x10, ValueType &x11, ValueType &x12, ValueType &x13, CSwap cswap=CSwap())
Bose-Nelson sorting network for fourteen elements.
static void merge_4_5(ValueType &a0, ValueType &a1, ValueType &a2, ValueType &a3, ValueType &b0, ValueType &b1, ValueType &b2, ValueType &b3, ValueType &b4, CSwap cswap)
merge network for element arrays length four and five
static void sort16(ValueType &x0, ValueType &x1, ValueType &x2, ValueType &x3, ValueType &x4, ValueType &x5, ValueType &x6, ValueType &x7, ValueType &x8, ValueType &x9, ValueType &x10, ValueType &x11, ValueType &x12, ValueType &x13, ValueType &x14, ValueType &x15, CSwap cswap=CSwap())
Bose-Nelson sorting network for sixteen elements.
static void merge_2_2(ValueType &a0, ValueType &a1, ValueType &b0, ValueType &b1, CSwap cswap)
merge network for element arrays length two and two
static void merge_8_8(ValueType &a0, ValueType &a1, ValueType &a2, ValueType &a3, ValueType &a4, ValueType &a5, ValueType &a6, ValueType &a7, ValueType &b0, ValueType &b1, ValueType &b2, ValueType &b3, ValueType &b4, ValueType &b5, ValueType &b6, ValueType &b7, CSwap cswap)
merge network for element arrays length eight and eight
static void merge_7_7(ValueType &a0, ValueType &a1, ValueType &a2, ValueType &a3, ValueType &a4, ValueType &a5, ValueType &a6, ValueType &b0, ValueType &b1, ValueType &b2, ValueType &b3, ValueType &b4, ValueType &b5, ValueType &b6, CSwap cswap)
merge network for element arrays length seven and seven
static void merge_7_8(ValueType &a0, ValueType &a1, ValueType &a2, ValueType &a3, ValueType &a4, ValueType &a5, ValueType &a6, ValueType &b0, ValueType &b1, ValueType &b2, ValueType &b3, ValueType &b4, ValueType &b5, ValueType &b6, ValueType &b7, CSwap cswap)
merge network for element arrays length seven and eight
static void sort4(ValueType &x0, ValueType &x1, ValueType &x2, ValueType &x3, CSwap cswap=CSwap())
Bose-Nelson sorting network for four elements.
static void merge_6_6(ValueType &a0, ValueType &a1, ValueType &a2, ValueType &a3, ValueType &a4, ValueType &a5, ValueType &b0, ValueType &b1, ValueType &b2, ValueType &b3, ValueType &b4, ValueType &b5, CSwap cswap)
merge network for element arrays length six and six
static void merge_1_2(ValueType &a0, ValueType &b0, ValueType &b1, CSwap cswap)
merge network for element arrays length one and two
static void sort12(ValueType &x0, ValueType &x1, ValueType &x2, ValueType &x3, ValueType &x4, ValueType &x5, ValueType &x6, ValueType &x7, ValueType &x8, ValueType &x9, ValueType &x10, ValueType &x11, CSwap cswap=CSwap())
Bose-Nelson sorting network for twelve elements.
static void sort5(ValueType &x0, ValueType &x1, ValueType &x2, ValueType &x3, ValueType &x4, CSwap cswap=CSwap())
Bose-Nelson sorting network for five elements.
Conditional swap implementation used for sorting networks: trivial portable C++ implementation with c...
Definition: cswap.hpp:32
static void sort10(ValueType &x0, ValueType &x1, ValueType &x2, ValueType &x3, ValueType &x4, ValueType &x5, ValueType &x6, ValueType &x7, ValueType &x8, ValueType &x9, CSwap cswap=CSwap())
Bose-Nelson sorting network for ten elements.
static void merge_2_1(ValueType &a0, ValueType &a1, ValueType &b0, CSwap cswap)
merge network for element arrays length two and one
static void merge_5_6(ValueType &a0, ValueType &a1, ValueType &a2, ValueType &a3, ValueType &a4, ValueType &b0, ValueType &b1, ValueType &b2, ValueType &b3, ValueType &b4, ValueType &b5, CSwap cswap)
merge network for element arrays length five and six
static void merge_2_3(ValueType &a0, ValueType &a1, ValueType &b0, ValueType &b1, ValueType &b2, CSwap cswap)
merge network for element arrays length two and three
static void sort3(ValueType &x0, ValueType &x1, ValueType &x2, CSwap cswap=CSwap())
Bose-Nelson sorting network for three elements.
static void sort9(ValueType &x0, ValueType &x1, ValueType &x2, ValueType &x3, ValueType &x4, ValueType &x5, ValueType &x6, ValueType &x7, ValueType &x8, CSwap cswap=CSwap())
Bose-Nelson sorting network for nine elements.
static void merge_5_5(ValueType &a0, ValueType &a1, ValueType &a2, ValueType &a3, ValueType &a4, ValueType &b0, ValueType &b1, ValueType &b2, ValueType &b3, ValueType &b4, CSwap cswap)
merge network for element arrays length five and five
static void sort7(ValueType &x0, ValueType &x1, ValueType &x2, ValueType &x3, ValueType &x4, ValueType &x5, ValueType &x6, CSwap cswap=CSwap())
Bose-Nelson sorting network for seven elements.
static void merge_4_3(ValueType &a0, ValueType &a1, ValueType &a2, ValueType &a3, ValueType &b0, ValueType &b1, ValueType &b2, CSwap cswap)
merge network for element arrays length four and three
static void sort15(ValueType &x0, ValueType &x1, ValueType &x2, ValueType &x3, ValueType &x4, ValueType &x5, ValueType &x6, ValueType &x7, ValueType &x8, ValueType &x9, ValueType &x10, ValueType &x11, ValueType &x12, ValueType &x13, ValueType &x14, CSwap cswap=CSwap())
Bose-Nelson sorting network for fifteen elements.
static void merge_1_1(ValueType &a0, ValueType &b0, CSwap cswap)
merge network for element arrays length one and one
static void merge_6_7(ValueType &a0, ValueType &a1, ValueType &a2, ValueType &a3, ValueType &a4, ValueType &a5, ValueType &b0, ValueType &b1, ValueType &b2, ValueType &b3, ValueType &b4, ValueType &b5, ValueType &b6, CSwap cswap)
merge network for element arrays length six and seven
static void sort8(ValueType &x0, ValueType &x1, ValueType &x2, ValueType &x3, ValueType &x4, ValueType &x5, ValueType &x6, ValueType &x7, CSwap cswap=CSwap())
Bose-Nelson sorting network for eight elements.
static void merge_4_4(ValueType &a0, ValueType &a1, ValueType &a2, ValueType &a3, ValueType &b0, ValueType &b1, ValueType &b2, ValueType &b3, CSwap cswap)
merge network for element arrays length four and four
static void sort13(ValueType &x0, ValueType &x1, ValueType &x2, ValueType &x3, ValueType &x4, ValueType &x5, ValueType &x6, ValueType &x7, ValueType &x8, ValueType &x9, ValueType &x10, ValueType &x11, ValueType &x12, CSwap cswap=CSwap())
Bose-Nelson sorting network for thirteen elements.
static void sort2(ValueType &x0, ValueType &x1, CSwap cswap=CSwap())
Bose-Nelson sorting network for two elements.
static void sort6(ValueType &x0, ValueType &x1, ValueType &x2, ValueType &x3, ValueType &x4, ValueType &x5, CSwap cswap=CSwap())
Bose-Nelson sorting network for six elements.
static void sort(Iterator a, Iterator b, Comparator cmp=Comparator())
Call Bose-Network sorting network for up to sixteen elements with given comparison method...
static void merge_3_2(ValueType &a0, ValueType &a1, ValueType &a2, ValueType &b0, ValueType &b1, CSwap cswap)
merge network for element arrays length three and two
static void sort11(ValueType &x0, ValueType &x1, ValueType &x2, ValueType &x3, ValueType &x4, ValueType &x5, ValueType &x6, ValueType &x7, ValueType &x8, ValueType &x9, ValueType &x10, CSwap cswap=CSwap())
Bose-Nelson sorting network for eleven elements.