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); )+)* } }; }