tlx
Loading...
Searching...
No Matches
bose_nelson.hpp
Go to the documentation of this file.
1/*******************************************************************************
2 * tlx/sort/networks/bose_nelson.hpp
3 *
4 * Recursively called Bose-Nelson sorting networks.
5 *
6 * Part of tlx - http://panthema.net/tlx
7 *
8 * Copyright (C) 2018-2020 Jasper Marianczuk <jasper.marianczuk@gmail.com>
9 * Copyright (C) 2020 Timo Bingmann <tb@panthema.net>
10 *
11 * All rights reserved. Published under the Boost Software License, Version 1.0
12 ******************************************************************************/
13
14#ifndef TLX_SORT_NETWORKS_BOSE_NELSON_HEADER
15#define TLX_SORT_NETWORKS_BOSE_NELSON_HEADER
16
18
19#include <functional>
20
21namespace tlx {
22
23//! Implementations of sorting networks for up to sixteen elements.
24namespace sort_networks {
25
26//! \addtogroup tlx_sort
27//! \{
28//! \name Implementations of Sorting Networks
29//! \{
30
31//! Implementation of Bose-Nelson sorting networks for up to sixteen elements.
32namespace bose_nelson {
33
34//! default conditional swap implementation
35template <typename Iterator>
37 std::less<typename std::iterator_traits<Iterator>::value_type> >;
38
39/*----------------------------------------------------------------------------*/
40
41//! merge network for element arrays length one and one
42template <typename Iterator, typename CSwap>
43static inline void merge1_1(Iterator a, Iterator b, CSwap cswap) {
44 cswap(a[0], b[0]);
45}
46
47//! merge network for element arrays length one and two
48template <typename Iterator, typename CSwap>
49static inline void merge1_2(Iterator a, Iterator b, CSwap cswap) {
50 cswap(a[0], b[1]);
51 cswap(a[0], b[0]);
52}
53
54//! merge network for element arrays length two and one
55template <typename Iterator, typename CSwap>
56static inline void merge2_1(Iterator a, Iterator b, CSwap cswap) {
57 cswap(a[0], b[0]);
58 cswap(a[1], b[0]);
59}
60
61//! merge network for element arrays length two and two
62template <typename Iterator, typename CSwap>
63static inline void merge2_2(Iterator a, Iterator b, CSwap cswap) {
64 merge1_1(a, b, cswap);
65 merge1_1(a + 1, b + 1, cswap);
66 merge1_1(a + 1, b, cswap);
67}
68
69//! merge network for element arrays length two and three
70template <typename Iterator, typename CSwap>
71static inline void merge2_3(Iterator a, Iterator b, CSwap cswap) {
72 merge1_2(a, b, cswap);
73 merge1_1(a + 1, b + 2, cswap);
74 merge1_2(a + 1, b, cswap);
75}
76
77//! merge network for element arrays length three and two
78template <typename Iterator, typename CSwap>
79static inline void merge3_2(Iterator a, Iterator b, CSwap cswap) {
80 merge1_1(a, b, cswap);
81 merge2_1(a + 1, b + 1, cswap);
82 merge2_1(a + 1, b, cswap);
83}
84
85//! merge network for element arrays length three and three
86template <typename Iterator, typename CSwap>
87static inline void merge3_3(Iterator a, Iterator b, CSwap cswap) {
88 merge1_1(a, b, cswap);
89 merge2_2(a + 1, b + 1, cswap);
90 merge2_1(a + 1, b, cswap);
91}
92
93//! merge network for element arrays length three and four
94template <typename Iterator, typename CSwap>
95static inline void merge3_4(Iterator a, Iterator b, CSwap cswap) {
96 merge1_2(a, b, cswap);
97 merge2_2(a + 1, b + 2, cswap);
98 merge2_2(a + 1, b, cswap);
99}
100
101//! merge network for element arrays length four and three
102template <typename Iterator, typename CSwap>
103static inline void merge4_3(Iterator a, Iterator b, CSwap cswap) {
104 merge2_2(a, b, cswap);
105 merge2_1(a + 2, b + 2, cswap);
106 merge2_2(a + 2, b, cswap);
107}
108
109//! merge network for element arrays length four and four
110template <typename Iterator, typename CSwap>
111static inline void merge4_4(Iterator a, Iterator b, CSwap cswap) {
112 merge2_2(a, b, cswap);
113 merge2_2(a + 2, b + 2, cswap);
114 merge2_2(a + 2, b, cswap);
115}
116
117//! merge network for element arrays length four and five
118template <typename Iterator, typename CSwap>
119static inline void merge4_5(Iterator a, Iterator b, CSwap cswap) {
120 merge2_3(a, b, cswap);
121 merge2_2(a + 2, b + 3, cswap);
122 merge2_3(a + 2, b, cswap);
123}
124
125//! merge network for element arrays length five and five
126template <typename Iterator, typename CSwap>
127static inline void merge5_5(Iterator a, Iterator b, CSwap cswap) {
128 merge2_2(a, b, cswap);
129 merge3_3(a + 2, b + 2, cswap);
130 merge3_2(a + 2, b, cswap);
131}
132
133//! merge network for element arrays length five and six
134template <typename Iterator, typename CSwap>
135static inline void merge5_6(Iterator a, Iterator b, CSwap cswap) {
136 merge2_3(a, b, cswap);
137 merge3_3(a + 2, b + 3, cswap);
138 merge3_3(a + 2, b, cswap);
139}
140
141//! merge network for element arrays length six and six
142template <typename Iterator, typename CSwap>
143static inline void merge6_6(Iterator a, Iterator b, CSwap cswap) {
144 merge3_3(a, b, cswap);
145 merge3_3(a + 3, b + 3, cswap);
146 merge3_3(a + 3, b, cswap);
147}
148
149//! merge network for element arrays length six and seven
150template <typename Iterator, typename CSwap>
151static inline void merge6_7(Iterator a, Iterator b, CSwap cswap) {
152 merge3_4(a, b, cswap);
153 merge3_3(a + 3, b + 4, cswap);
154 merge3_4(a + 3, b, cswap);
155}
156
157//! merge network for element arrays length seven and seven
158template <typename Iterator, typename CSwap>
159static inline void merge7_7(Iterator a, Iterator b, CSwap cswap) {
160 merge3_3(a, b, cswap);
161 merge4_4(a + 3, b + 3, cswap);
162 merge4_3(a + 3, b, cswap);
163}
164
165//! merge network for element arrays length seven and eight
166template <typename Iterator, typename CSwap>
167static inline void merge7_8(Iterator a, Iterator b, CSwap cswap) {
168 merge3_4(a, b, cswap);
169 merge4_4(a + 3, b + 4, cswap);
170 merge4_4(a + 3, b, cswap);
171}
172
173//! merge network for element arrays length eight and eight
174template <typename Iterator, typename CSwap>
175static inline void merge8_8(Iterator a, Iterator b, CSwap cswap) {
176 merge4_4(a, b, cswap);
177 merge4_4(a + 4, b + 4, cswap);
178 merge4_4(a + 4, b, cswap);
179}
180
181/*----------------------------------------------------------------------------*/
182
183//! Bose-Nelson sorting network for two elements
184template <typename Iterator, typename CSwap = DefaultCSwap<Iterator> >
185static inline void sort2(Iterator a, CSwap cswap = CSwap()) {
186 merge1_1(a, a + 1, cswap);
187}
188
189//! Bose-Nelson sorting network for three elements
190template <typename Iterator, typename CSwap = DefaultCSwap<Iterator> >
191static inline void sort3(Iterator a, CSwap cswap = CSwap()) {
192 sort2(a + 1, cswap);
193 merge1_2(a, a + 1, cswap);
194}
195
196//! Bose-Nelson sorting network for four elements
197template <typename Iterator, typename CSwap = DefaultCSwap<Iterator> >
198static void sort4(Iterator a, CSwap cswap = CSwap()) {
199 sort2(a, cswap);
200 sort2(a + 2, cswap);
201 merge2_2(a, a + 2, cswap);
202}
203
204//! Bose-Nelson sorting network for five elements
205template <typename Iterator, typename CSwap = DefaultCSwap<Iterator> >
206static void sort5(Iterator a, CSwap cswap = CSwap()) {
207 sort2(a, cswap);
208 sort3(a + 2, cswap);
209 merge2_3(a, a + 2, cswap);
210}
211
212//! Bose-Nelson sorting network for six elements
213template <typename Iterator, typename CSwap = DefaultCSwap<Iterator> >
214static void sort6(Iterator a, CSwap cswap = CSwap()) {
215 sort3(a, cswap);
216 sort3(a + 3, cswap);
217 merge3_3(a, a + 3, cswap);
218}
219
220//! Bose-Nelson sorting network for seven elements
221template <typename Iterator, typename CSwap = DefaultCSwap<Iterator> >
222static void sort7(Iterator a, CSwap cswap = CSwap()) {
223 sort3(a, cswap);
224 sort4(a + 3, cswap);
225 merge3_4(a, a + 3, cswap);
226}
227
228//! Bose-Nelson sorting network for eight elements
229template <typename Iterator, typename CSwap = DefaultCSwap<Iterator> >
230static void sort8(Iterator a, CSwap cswap = CSwap()) {
231 sort4(a, cswap);
232 sort4(a + 4, cswap);
233 merge4_4(a, a + 4, cswap);
234}
235
236//! Bose-Nelson sorting network for nine elements
237template <typename Iterator, typename CSwap = DefaultCSwap<Iterator> >
238static void sort9(Iterator a, CSwap cswap = CSwap()) {
239 sort4(a, cswap);
240 sort5(a + 4, cswap);
241 merge4_5(a, a + 4, cswap);
242}
243
244//! Bose-Nelson sorting network for ten elements
245template <typename Iterator, typename CSwap = DefaultCSwap<Iterator> >
246static void sort10(Iterator a, CSwap cswap = CSwap()) {
247 sort5(a, cswap);
248 sort5(a + 5, cswap);
249 merge5_5(a, a + 5, cswap);
250}
251
252//! Bose-Nelson sorting network for eleven elements
253template <typename Iterator, typename CSwap = DefaultCSwap<Iterator> >
254static void sort11(Iterator a, CSwap cswap = CSwap()) {
255 sort5(a, cswap);
256 sort6(a + 5, cswap);
257 merge5_6(a, a + 5, cswap);
258}
259
260//! Bose-Nelson sorting network for twelve elements
261template <typename Iterator, typename CSwap = DefaultCSwap<Iterator> >
262static void sort12(Iterator a, CSwap cswap = CSwap()) {
263 sort6(a, cswap);
264 sort6(a + 6, cswap);
265 merge6_6(a, a + 6, cswap);
266}
267
268//! Bose-Nelson sorting network for thirteen elements
269template <typename Iterator, typename CSwap = DefaultCSwap<Iterator> >
270static void sort13(Iterator a, CSwap cswap = CSwap()) {
271 sort6(a, cswap);
272 sort7(a + 6, cswap);
273 merge6_7(a, a + 6, cswap);
274}
275
276//! Bose-Nelson sorting network for fourteen elements
277template <typename Iterator, typename CSwap = DefaultCSwap<Iterator> >
278static void sort14(Iterator a, CSwap cswap = CSwap()) {
279 sort7(a, cswap);
280 sort7(a + 7, cswap);
281 merge7_7(a, a + 7, cswap);
282}
283
284//! Bose-Nelson sorting network for fifteen elements
285template <typename Iterator, typename CSwap = DefaultCSwap<Iterator> >
286static void sort15(Iterator a, CSwap cswap = CSwap()) {
287 sort7(a, cswap);
288 sort8(a + 7, cswap);
289 merge7_8(a, a + 7, cswap);
290}
291
292//! Bose-Nelson sorting network for sixteen elements
293template <typename Iterator, typename CSwap = DefaultCSwap<Iterator> >
294static void sort16(Iterator a, CSwap cswap = CSwap()) {
295 sort8(a, cswap);
296 sort8(a + 8, cswap);
297 merge8_8(a, a + 8, cswap);
298}
299
300/*----------------------------------------------------------------------------*/
301
302//! Call Bose-Network sorting network for up to sixteen elements with given
303//! comparison method
304template <typename Iterator, typename Comparator =
305 std::less<typename std::iterator_traits<Iterator>::value_type> >
306static void sort(Iterator begin, Iterator end, Comparator cmp = Comparator()) {
307 CS_IfSwap<Comparator> cswap(cmp);
308
309 switch (end - begin) {
310 case 0:
311 break;
312 case 1:
313 break;
314 case 2:
315 sort2(begin, cswap);
316 break;
317 case 3:
318 sort3(begin, cswap);
319 break;
320 case 4:
321 sort4(begin, cswap);
322 break;
323 case 5:
324 sort5(begin, cswap);
325 break;
326 case 6:
327 sort6(begin, cswap);
328 break;
329 case 7:
330 sort7(begin, cswap);
331 break;
332 case 8:
333 sort8(begin, cswap);
334 break;
335 case 9:
336 sort9(begin, cswap);
337 break;
338 case 10:
339 sort10(begin, cswap);
340 break;
341 case 11:
342 sort11(begin, cswap);
343 break;
344 case 12:
345 sort12(begin, cswap);
346 break;
347 case 13:
348 sort13(begin, cswap);
349 break;
350 case 14:
351 sort14(begin, cswap);
352 break;
353 case 15:
354 sort15(begin, cswap);
355 break;
356 case 16:
357 sort16(begin, cswap);
358 break;
359 default:
360 abort();
361 break;
362 }
363}
364
365} // namespace bose_nelson
366
367/******************************************************************************/
368
369//! \}
370//! \}
371
372} // namespace sort_networks
373} // namespace tlx
374
375#endif // !TLX_SORT_NETWORKS_BOSE_NELSON_HEADER
376
377/******************************************************************************/
Conditional swap implementation used for sorting networks: trivial portable C++ implementation with c...
Definition cswap.hpp:33
static void sort5(Iterator a, CSwap cswap=CSwap())
Bose-Nelson sorting network for five elements.
static void sort4(Iterator a, CSwap cswap=CSwap())
Bose-Nelson sorting network for four elements.
static void sort7(Iterator a, CSwap cswap=CSwap())
Bose-Nelson sorting network for seven elements.
static void sort2(Iterator a, CSwap cswap=CSwap())
Bose-Nelson sorting network for two elements.
static void merge1_2(Iterator a, Iterator b, CSwap cswap)
merge network for element arrays length one and two
static void merge5_5(Iterator a, Iterator b, CSwap cswap)
merge network for element arrays length five and five
static void sort13(Iterator a, CSwap cswap=CSwap())
Bose-Nelson sorting network for thirteen elements.
static void merge2_2(Iterator a, Iterator b, CSwap cswap)
merge network for element arrays length two and two
static void merge2_1(Iterator a, Iterator b, CSwap cswap)
merge network for element arrays length two and one
static void sort8(Iterator a, CSwap cswap=CSwap())
Bose-Nelson sorting network for eight elements.
static void merge6_6(Iterator a, Iterator b, CSwap cswap)
merge network for element arrays length six and six
static void merge8_8(Iterator a, Iterator b, CSwap cswap)
merge network for element arrays length eight and eight
static void sort15(Iterator a, CSwap cswap=CSwap())
Bose-Nelson sorting network for fifteen elements.
static void sort9(Iterator a, CSwap cswap=CSwap())
Bose-Nelson sorting network for nine elements.
static void merge6_7(Iterator a, Iterator b, CSwap cswap)
merge network for element arrays length six and seven
static void sort16(Iterator a, CSwap cswap=CSwap())
Bose-Nelson sorting network for sixteen elements.
static void merge2_3(Iterator a, Iterator b, CSwap cswap)
merge network for element arrays length two and three
static void merge4_4(Iterator a, Iterator b, CSwap cswap)
merge network for element arrays length four and four
static void sort12(Iterator a, CSwap cswap=CSwap())
Bose-Nelson sorting network for twelve elements.
static void sort10(Iterator a, CSwap cswap=CSwap())
Bose-Nelson sorting network for ten elements.
static void sort3(Iterator a, CSwap cswap=CSwap())
Bose-Nelson sorting network for three elements.
static void merge3_4(Iterator a, Iterator b, CSwap cswap)
merge network for element arrays length three and four
static void sort14(Iterator a, CSwap cswap=CSwap())
Bose-Nelson sorting network for fourteen elements.
static void merge4_5(Iterator a, Iterator b, CSwap cswap)
merge network for element arrays length four and five
static void sort6(Iterator a, CSwap cswap=CSwap())
Bose-Nelson sorting network for six elements.
static void merge1_1(Iterator a, Iterator b, CSwap cswap)
merge network for element arrays length one and one
static void merge3_2(Iterator a, Iterator b, CSwap cswap)
merge network for element arrays length three and two
static void sort(Iterator begin, Iterator end, Comparator cmp=Comparator())
Call Bose-Network sorting network for up to sixteen elements with given comparison method.
static void sort11(Iterator a, CSwap cswap=CSwap())
Bose-Nelson sorting network for eleven elements.
static void merge7_8(Iterator a, Iterator b, CSwap cswap)
merge network for element arrays length seven and eight
static void merge4_3(Iterator a, Iterator b, CSwap cswap)
merge network for element arrays length four and three
static void merge3_3(Iterator a, Iterator b, CSwap cswap)
merge network for element arrays length three and three
static void merge5_6(Iterator a, Iterator b, CSwap cswap)
merge network for element arrays length five and six
static void merge7_7(Iterator a, Iterator b, CSwap cswap)
merge network for element arrays length seven and seven