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
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160

#![cfg_attr(not(feature = "std"), no_std)]
#![cfg_attr(not(test), feature(lang_items))]

#[cfg(not(any(feature = "std", test)))]
extern crate core as std;

#[cfg(not(any(feature = "std", test)))]
#[macro_use]
extern crate std;

/// Iterators for enumerating a sorting network's structure.
pub mod generate {
    include!(concat!(env!("CARGO_MANIFEST_DIR"), "/generate.rs"));
}

#[cfg(any(feature = "std", test))]
mod debug;

// Branchless max(x, y)/min(x, y) for unsigned integers:
//
// let x: usize = 4;
// let y: usize = 10;
//
// let min = y ^ ((x ^ y) & (!(x < y) as usize - 1));
// println!("min({}, {}) = {}", x, y, min);
//
// let max = y ^ ((x ^ y) & (!(y < x) as usize - 1));
// println!("max({}, {}) = {}", x, y, max);

#[inline]
unsafe fn swap_unchecked<T, F>(slice: &mut [T], lhs: usize, rhs: usize, compare: F)
where
    F: Fn(&T, &T) -> Ordering,
{
    use std::ptr;

    let ptr = slice.as_mut_ptr();

    let lhs_ptr = ptr.offset(lhs as isize);
    let rhs_ptr = ptr.offset(rhs as isize);

    let lhs_ref = &*lhs_ptr;
    let rhs_ref = &*rhs_ptr;

    let is_ordered = compare(&lhs_ref, &rhs_ref) == Ordering::Less;

    let min_ptr = (if is_ordered { lhs_ref } else { rhs_ref }) as *const T;
    let max_ptr = (if is_ordered { rhs_ref } else { lhs_ref }) as *const T;

    let min_val = ptr::read(min_ptr);
    let max_val = ptr::read(max_ptr);

    ptr::write(lhs_ptr, min_val);
    ptr::write(rhs_ptr, max_val);
}

/// Trait for sorting networks
pub trait SortingNetworkTrait {
    /// Sorts the passed slice
    fn sort<T>(&self, slice: &mut [T])
    where
        T: Ord,
    {
        self.sort_by(slice, |lhs, rhs| lhs.cmp(rhs))
    }

    fn sort_by<T, F>(&self, slice: &mut [T], compare: F)
    where
        F: Fn(&T, &T) -> Ordering;
}

pub trait FixedSizeSortingNetwork {
    fn order() -> usize;

    fn width() -> usize {
        1 << Self::order()
    }
}

// http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/networks/oemen.htm
pub struct SortingNetwork;

impl SortingNetwork {
    pub fn new() -> Self {
        SortingNetwork
    }

    pub fn sort<T>(&self, slice: &mut [T])
    where
        T: Ord,
    {
        let len = slice.len();
        let is_power_of_two = (len & (len - 1)) == 0;
        assert!(is_power_of_two);
        self.sort_internal(slice, 0, len);
    }

    fn sort_internal<T>(&self, slice: &mut [T], i: usize, n: usize)
    where
        T: Ord,
    {
        if n <= 1 {
            return;
        }
        let m = n / 2;
        self.sort_internal(slice, i, m);
        self.sort_internal(slice, i + m, m);
        self.merge(slice, i, n, 1);
    }

    fn merge<T>(&self, slice: &mut [T], i: usize, n: usize, interval: usize)
    where
        T: Ord,
    {
        let m = interval * 2;
        if m >= n {
            let i = i;
            let j = i + interval;
            if slice[i] > slice[j] {
                slice.swap(i, j);
                // println!("{:?}, {:?}", i, j);
            }
            return;
        }
        self.merge(slice, i, n, m);
        self.merge(slice, i + interval, n, m);
        let mut i = i + interval;
        while i + interval < n {
            let j = i + interval;
            if slice[i] > slice[j] {
                slice.swap(i, j);
                // println!("{:?}, {:?}", i, j);
            }
            i += m;
        }
    }
}

#[derive(Clone, Copy)]
struct SortingNetwork1;

impl SortingNetwork1 {
    #[inline]
    pub fn new() -> Self {
        SortingNetwork1
    }
    // pub fn width() -> usize { 1 }
}

impl SortingNetworkTrait for SortingNetwork1 {
    #[inline]
    fn sort_by<T, F>(&self, _slice: &mut [T], _compare: F)
    where
        F: Fn(&T, &T) -> Ordering,
    {
        // intentionally left blank
    }
}

include!(concat!(env!("OUT_DIR"), "/generated.rs"));