sortnet 0.1.0

Sorting Networks for Rust
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137

/// Create new sortnet implementation.
///
/// Takes the following arguments:
///
/// - `fsort`: name of the public function that gets created
/// - `n`: number of elements in the array
/// - `swaps`: elements to be compared in order. Must be grouped by operations that can be executed
///    in parallel.
///
/// # Example
/// We want to create a new sortnet for 4 elements that looks like this:
///
/// ```text
/// o o o o
/// | | | |
/// +-+ +-+
/// | | | |
/// +---+ |
/// | | | |
/// | +---+
/// | | | |
/// | +-+ |
/// | | | |
/// V V V V
/// ```
///
/// There are 5 compare-and-swap operations:
///
/// - 0 and 1
/// - 2 and 3
/// - 0 and 2
/// - 1 and 3
/// - 1 and 2
///
/// These can be grouped in the following way so that they that elements within a group can be executed in parallel:
///
/// - (0 and 1), (2 and 3)
/// - (0 and 2), (1 and 3)
/// - (1 and 2)
///
/// In code, this looks like this:
/// ```
/// use sortnet::gen_sortnet;
///
/// gen_sortnet!(my_sortnet, 4, [[(0, 1), (2, 3)], [(0, 2), (1, 3)], [(1, 2)]]);
///
/// let mut data = [0, 13, -1, 2];
/// my_sortnet(&mut data);
/// assert_eq!(data, [-1, 0, 2, 13]);
/// ```
///
/// # Requirements
/// Ther are a few compile-time requirements to use the `gen_sortnet` macrol
///
/// ## Non-empty Groups
/// Groups must not be empty:
///
/// ```compile_fail
/// use sortnet::gen_sortnet;
///
/// gen_sortnet!(my_sortnet, 3, [[], [(1, 2)], [(0, 2)], [(0, 1)]]);
/// ```
///
/// ## Non-negative Size
/// The array size must not be negative:
///
/// ```compile_fail
/// use sortnet::gen_sortnet;
///
/// gen_sortnet!(my_sortnet, -1, []);
/// ```
///
/// ## Non-negative Indices
/// Sortnet indices must not be negative:
///
/// ```compile_fail
/// use sortnet::gen_sortnet;
///
/// gen_sortnet!(my_sortnet, 3, [[(1, 2)], [(0, 2)], [(0, -1)]]);
/// ```
///
/// ## In-bounds Indices
/// Sortnet indices must not be out-of bounds:
///
/// ```compile_fail
/// use sortnet::gen_sortnet;
///
/// gen_sortnet!(my_sortnet, 3, [[(1, 2)], [(0, 2)], [(0, 3)]]);
/// ```
///
/// ```compile_fail
/// use sortnet::gen_sortnet;
///
/// gen_sortnet!(my_sortnet, 3, [[(1, 2)], [(0, 2)], [(3, 1)]]);
/// ```
#[macro_export]
macro_rules! gen_sortnet {
    ($fsort:ident, $n:expr, [$([$(($swap_a:expr, $swap_b:expr)),+]),*]) => {
        $crate::__gen_sortnet_inner!($fsort, $n, stringify!($n), [$([$(($swap_a, $swap_b)),+]),*]);
    };
}

#[doc(hidden)]
#[macro_export]
macro_rules! __gen_sortnet_inner {
    ($fsort:ident, $n:expr, $n_str:expr, [$([$(($swap_a:expr, $swap_b:expr)),+]),*]) => {
        #[doc="Sortnet-based sorting for arrays with "]
        #[doc=$n_str]
        #[doc=" elements."]
        pub fn $fsort<T>(arr: &mut [T; $n])
        where
            T: PartialOrd,
        {
            #[allow(unused_imports)]
            use static_assertions::const_assert;

            #[allow(dead_code)]
            #[inline(always)]
            pub fn maybe_swap<T>(arr: &mut [T; $n], a: usize, b: usize)
            where
                T: PartialOrd,
            {
                if arr[a] > arr[b] {
                    arr.swap(a, b)
                }
            }

            #[allow(unused_mut, unused_variables)] let mut arr = arr;

            $($(
            const_assert!($swap_a < $n);
            const_assert!($swap_b < $n);
            maybe_swap(&mut arr, $swap_a, $swap_b);
            )+)*
        }
    };
}