use std::cmp::Ordering;
#[inline]
fn ordering(less: bool) -> Ordering {
if less {
Ordering::Less
} else {
Ordering::Greater
}
}
#[inline(never)]
fn stable_order(len: usize, less: &mut dyn FnMut(usize, usize) -> bool) -> Vec<usize> {
let mut order: Vec<usize> = (0..len).collect();
order.sort_by(|&a, &b| ordering(less(a, b)));
order
}
#[inline(never)]
unsafe fn permute(base: *mut u8, size: usize, order: &[usize]) {
let bytes = order.len() * size;
let mut moved = Vec::<u8>::with_capacity(bytes);
let out = moved.as_mut_ptr();
for (slot, &from) in order.iter().enumerate() {
debug_assert!(from < order.len());
unsafe { std::ptr::copy_nonoverlapping(base.add(from * size), out.add(slot * size), size) };
}
unsafe { std::ptr::copy_nonoverlapping(out, base, bytes) };
}
#[inline(never)]
fn unstable_by_dyn<T>(items: &mut [T], less: &mut dyn FnMut(&T, &T) -> bool) {
items.sort_unstable_by(|a, b| ordering(less(a, b)));
}
fn stable_by_less<T>(items: &mut [T], mut less: impl FnMut(&T, &T) -> bool) {
if items.len() < 2 || size_of::<T>() == 0 {
return;
}
let order = {
let view = &*items;
stable_order(view.len(), &mut |a, b| unsafe {
less(view.get_unchecked(a), view.get_unchecked(b))
})
};
unsafe { permute(items.as_mut_ptr().cast(), size_of::<T>(), &order) };
}
pub(crate) trait SharedSort<T> {
fn shared_sort_by(&mut self, compare: impl FnMut(&T, &T) -> Ordering);
fn shared_sort_by_key<K: Ord>(&mut self, key: impl FnMut(&T) -> K);
fn shared_sort(&mut self)
where
T: Ord;
fn shared_sort_unstable_by(&mut self, compare: impl FnMut(&T, &T) -> Ordering);
fn shared_sort_unstable_by_key<K: Ord>(&mut self, key: impl FnMut(&T) -> K);
}
impl<T> SharedSort<T> for [T] {
#[inline]
fn shared_sort_by(&mut self, mut compare: impl FnMut(&T, &T) -> Ordering) {
stable_by_less(self, |a, b| compare(a, b) == Ordering::Less);
}
#[inline]
fn shared_sort_by_key<K: Ord>(&mut self, mut key: impl FnMut(&T) -> K) {
stable_by_less(self, |a, b| key(a).lt(&key(b)));
}
#[inline]
fn shared_sort(&mut self)
where
T: Ord,
{
stable_by_less(self, |a, b| a.lt(b));
}
#[inline]
fn shared_sort_unstable_by(&mut self, mut compare: impl FnMut(&T, &T) -> Ordering) {
unstable_by_dyn(self, &mut |a, b| compare(a, b) == Ordering::Less);
}
#[inline]
fn shared_sort_unstable_by_key<K: Ord>(&mut self, mut key: impl FnMut(&T) -> K) {
unstable_by_dyn(self, &mut |a, b| key(a).lt(&key(b)));
}
}
#[cfg(test)]
mod tests {
use super::SharedSort;
fn noise(seed: &mut u64) -> u64 {
*seed ^= *seed << 13;
*seed ^= *seed >> 7;
*seed ^= *seed << 17;
*seed
}
#[test]
fn shared_sorts_match_the_standard_sorts() {
let mut seed = 0x9E37_79B9_7F4A_7C15u64;
for len in [0usize, 1, 2, 3, 7, 20, 21, 33, 64, 257, 1000, 5000] {
for keys in [2u64, 16, 1 << 40] {
let items: Vec<(u64, String, usize)> = (0..len)
.map(|i| (noise(&mut seed) % keys, format!("item{i}"), i))
.collect();
let (mut expected, mut actual) = (items.clone(), items.clone());
expected.sort_by(|a, b| b.0.cmp(&a.0));
actual.shared_sort_by(|a, b| b.0.cmp(&a.0));
assert_eq!(actual, expected, "sort_by len {len}");
let (mut expected, mut actual) = (items.clone(), items.clone());
expected.sort_by_key(|item| item.0);
actual.shared_sort_by_key(|item| item.0);
assert_eq!(actual, expected, "sort_by_key len {len}");
let (mut expected, mut actual) = (items.clone(), items.clone());
expected.sort();
actual.shared_sort();
assert_eq!(actual, expected, "sort len {len}");
let raw: Vec<[u16; 3]> = items.iter().map(|item| [item.0 as u16, 7, 1]).collect();
let (mut expected, mut actual) = (raw.clone(), raw);
expected.sort_unstable();
actual.shared_sort();
assert_eq!(actual, expected, "sort_unstable len {len}");
let order: Vec<usize> = (0..len).collect();
let (mut expected, mut actual) = (order.clone(), order.clone());
expected.sort_unstable_by(|&a, &b| items[a].0.cmp(&items[b].0));
actual.shared_sort_unstable_by(|&a, &b| items[a].0.cmp(&items[b].0));
assert_eq!(actual, expected, "sort_unstable_by len {len}");
let (mut expected, mut actual) = (order.clone(), order);
expected.sort_unstable_by_key(|&i| items[i].0);
actual.shared_sort_unstable_by_key(|&i| items[i].0);
assert_eq!(actual, expected, "sort_unstable_by_key len {len}");
}
}
}
}