#![crate_type = "lib"]
#![crate_name = "partial_sort"]
#![cfg_attr(feature = "nightly", feature(test))]
use std::cmp::Ordering;
use std::cmp::Ordering::Less;
use std::{mem, ptr};
pub trait PartialSort {
type Item;
fn partial_sort<F>(&mut self, _: usize, _: F)
where
F: FnMut(&Self::Item, &Self::Item) -> Ordering;
}
impl<T> PartialSort for [T] {
type Item = T;
fn partial_sort<F>(&mut self, last: usize, mut cmp: F)
where
F: FnMut(&Self::Item, &Self::Item) -> Ordering,
{
partial_sort(self, last, |a, b| cmp(a, b) == Less);
}
}
pub fn partial_sort<T, F>(v: &mut [T], last: usize, mut is_less: F)
where
F: FnMut(&T, &T) -> bool,
{
debug_assert!(last <= v.len());
make_heap(v, last, &mut is_less);
unsafe {
for i in last..v.len() {
if is_less(v.get_unchecked(i), v.get_unchecked(0)) {
v.swap(0, i);
adjust_heap(v, 0, last, &mut is_less);
}
}
sort_heap(v, last, &mut is_less);
}
}
#[inline]
fn make_heap<T, F>(v: &mut [T], last: usize, is_less: &mut F)
where
F: FnMut(&T, &T) -> bool,
{
if last < 2 {
return;
}
let len = last;
let mut parent = (len - 2) / 2;
loop {
adjust_heap(v, parent, len, is_less);
if parent == 0 {
return;
}
parent -= 1;
}
}
#[inline]
fn adjust_heap<T, F>(v: &mut [T], hole_index: usize, len: usize, is_less: &mut F)
where
F: FnMut(&T, &T) -> bool,
{
let mut left_child = hole_index * 2 + 1;
unsafe {
let mut tmp = mem::ManuallyDrop::new(ptr::read(&v[hole_index]));
let mut hole = InsertionHole {
src: &mut *tmp,
dest: &mut v[hole_index],
};
while left_child < len {
if left_child + 1 < len
&& is_less(v.get_unchecked(left_child), v.get_unchecked(left_child + 1))
{
left_child += 1;
}
if is_less(&*tmp, v.get_unchecked(left_child)) {
ptr::copy_nonoverlapping(&v[left_child], hole.dest, 1);
hole.dest = &mut v[left_child];
} else {
break;
}
left_child = left_child * 2 + 1;
}
}
struct InsertionHole<T> {
src: *mut T,
dest: *mut T,
}
impl<T> Drop for InsertionHole<T> {
fn drop(&mut self) {
unsafe {
ptr::copy_nonoverlapping(self.src, self.dest, 1);
}
}
}
}
#[inline]
unsafe fn sort_heap<T, F>(v: &mut [T], last: usize, is_less: &mut F)
where
F: FnMut(&T, &T) -> bool,
{
let mut last = last;
while last > 1 {
v.swap(0, last - 1);
adjust_heap(v, 0, last - 1, is_less);
last -= 1;
}
}
#[cfg(test)]
mod tests {
use std::cmp::Ordering;
use std::fmt;
use std::sync::Arc;
use PartialSort;
#[test]
fn empty_test() {
let mut before: Vec<u32> = vec![4, 4, 3, 3, 1, 1, 2, 2];
before.partial_sort(0, |a, b| a.cmp(b));
}
#[test]
fn single_test() {
let mut before: Vec<u32> = vec![4, 4, 3, 3, 1, 1, 2, 2];
let last = 6;
let mut d = before.clone();
d.sort();
before.partial_sort(last, |a, b| a.cmp(b));
assert_eq!(&d[0..last], &before.as_slice()[0..last]);
}
#[test]
fn sorted_strings_test() {
let mut before: Vec<&str> = vec![
"a", "cat", "mat", "on", "sat", "the", "xxx", "xxxx", "fdadfdsf",
];
let last = 6;
let mut d = before.clone();
d.sort();
before.partial_sort(last, |a, b| a.cmp(b));
assert_eq!(&d[0..last], &before.as_slice()[0..last]);
}
#[test]
fn sorted_ref_test() {
trait TModel: fmt::Debug + Send + Sync {
fn size(&self) -> usize;
}
struct ModelFoo {
size: usize,
}
impl TModel for ModelFoo {
fn size(&self) -> usize {
return self.size;
}
}
impl fmt::Debug for ModelFoo {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
write!(f, "ModelFoo[{}]", self.size)?;
Ok(())
}
}
struct ModelBar {
size: usize,
}
impl TModel for ModelBar {
fn size(&self) -> usize {
return self.size;
}
}
impl fmt::Debug for ModelBar {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
write!(f, "ModelBar[{}]", self.size)?;
Ok(())
}
}
type ModelRef = Arc<dyn TModel>;
fn cmp_model(a: &dyn TModel, b: &dyn TModel) -> Ordering {
return a.size().cmp(&b.size());
}
let mut before: Vec<(i32, ModelRef)> = vec![
(1i32, Arc::new(ModelBar { size: 100 })),
(1i32, Arc::new(ModelFoo { size: 99 })),
(1i32, Arc::new(ModelFoo { size: 101 })),
(1i32, Arc::new(ModelBar { size: 104 })),
(1i32, Arc::new(ModelBar { size: 10 })),
(1i32, Arc::new(ModelBar { size: 24 })),
(1i32, Arc::new(ModelBar { size: 34 })),
(1i32, Arc::new(ModelBar { size: 114 })),
];
let last = 6;
let mut d = before.clone();
d.sort_by(|a, b| cmp_model(a.1.as_ref(), b.1.as_ref()));
before.partial_sort(last, |a, b| cmp_model(a.1.as_ref(), b.1.as_ref()));
&d[0..last].iter().zip(&before[0..last]).map(|(a, b)| {
assert_eq!(a.0, b.0);
assert_eq!(a.1.size(), b.1.size());
});
}
}
#[cfg(feature = "nightly")]
#[cfg(test)]
mod benches {
extern crate rand;
extern crate test;
use self::test::{black_box, Bencher};
use self::rand::distributions::{Distribution, Range};
use crate::PartialSort;
use std::collections::BinaryHeap;
static RANGE: u64 = 1000000;
static VEC_SIZE: u64 = 50000;
fn data() -> Vec<u64> {
let mut rng = rand::thread_rng();
let between = Range::new(0u64, RANGE);
(0u64..VEC_SIZE).map(|_| between.sample(&mut rng)).collect()
}
#[bench]
fn c_standard_bench(b: &mut Bencher) {
let input = data();
b.iter(|| {
let mut numbers = black_box(&input).clone();
numbers.sort();
});
}
#[bench]
fn c_partial_10_bench(b: &mut Bencher) {
let input = data();
b.iter(|| {
let mut numbers = black_box(&input).clone();
numbers.partial_sort(10, |a, b| a.cmp(b));
});
}
#[bench]
fn c_partial_100_bench(b: &mut Bencher) {
let input = data();
b.iter(|| {
let mut numbers = black_box(&input).clone();
numbers.partial_sort(100, |a, b| a.cmp(b));
});
}
#[bench]
fn c_partial_1000_bench(b: &mut Bencher) {
let input = data();
b.iter(|| {
let mut numbers = black_box(&input).clone();
numbers.partial_sort(1000, |a, b| a.cmp(b));
});
}
#[bench]
fn c_partial_10000_bench(b: &mut Bencher) {
let input = data();
b.iter(|| {
let mut numbers = black_box(&input).clone();
numbers.partial_sort(10000, |a, b| a.cmp(b));
});
}
#[bench]
fn c_heap_bench(b: &mut Bencher) {
let input = data();
b.iter(|| {
let numbers = black_box(&input).clone();
let h = BinaryHeap::from(numbers);
h.into_sorted_vec();
});
}
}