use std::cmp::{self, Ordering};
use std::mem::swap;
use crate::scope;
#[cfg(feature="experimental_pointer_ranges")]
use crate::pointer::zip;
const QS_INSERTION_SORT_THRESH: usize = 24;
pub fn quicksort_range<T: Ord>(v: &mut [T]) {
scope(v, |mut v| {
let range = v.range();
if let Ok(range) = range.nonempty() {
if range.len() <= QS_INSERTION_SORT_THRESH {
insertion_sort_ranges(&mut v[..], |x, y| x < y);
return;
}
let (l, m, r) = (range.first(), range.upper_middle(), range.last());
let mut pivot = if v[l] <= v[m] && v[m] <= v[r] {
m
} else if v[m] <= v[l] && v[l] <= v[r] {
l
} else {
r
};
let mut scan = range;
v.swap(scan.first(), pivot);
pivot = scan.first();
'main: loop {
if v[scan.first()] >= v[pivot] {
loop {
if v[scan.last()] <= v[pivot] {
v.swap(scan.first(), scan.last());
break;
}
if !scan.advance_back() {
break 'main;
}
}
}
if !scan.advance() {
break;
}
}
let (a, b) = v.split_at(scan.first());
quicksort_range(&mut v[a]);
quicksort_range(&mut v[b]);
}
});
}
#[cfg(feature="experimental_pointer_ranges")]
pub fn quicksort_prange<T: Ord>(v: &mut [T]) {
scope(v, |mut v| {
let range = v.pointer_range();
if let Ok(range) = range.nonempty() {
if range.len() <= QS_INSERTION_SORT_THRESH {
insertion_sort_ranges(&mut v[..], |x, y| x < y);
return;
}
let (l, m, r) = (range.first(), range.upper_middle(), range.last());
let mut pivot = if v[l] <= v[m] && v[m] <= v[r] {
m
} else if v[m] <= v[l] && v[l] <= v[r] {
l
} else {
r
};
let mut scan = range;
v.swap_ptr(scan.first(), pivot);
pivot = scan.first();
'main: loop {
if v[scan.first()] >= v[pivot] {
loop {
if v[scan.last()] <= v[pivot] {
v.swap_ptr(scan.first(), scan.last());
break;
}
if !scan.advance_back() {
break 'main;
}
}
}
if !scan.advance() {
break;
}
}
let (a, b) = v.split_at_pointer(scan.first());
quicksort_prange(&mut v[a]);
quicksort_prange(&mut v[b]);
}
});
}
pub fn quicksort_bounds<T: Ord>(v: &mut [T]) {
if v.len() <= QS_INSERTION_SORT_THRESH {
insertion_sort_ranges(&mut v[..], |x, y| x < y);
return;
}
let (l, m, r) = (0, v.len() / 2, v.len() - 1);
let mut pivot = if v[l] <= v[m] && v[m] <= v[r] {
m
} else if v[m] <= v[l] && v[l] <= v[r] {
l
} else {
r
};
v.swap(0, pivot);
pivot = 0;
let mut i = 0;
let mut j = v.len() - 1;
'main: loop {
if v[i] >= v[pivot] {
loop {
if v[j] <= v[pivot] {
v.swap(i, j);
break;
}
j -= 1;
if i >= j { break 'main; }
}
}
if i >= j {
break;
}
i += 1;
}
let (a, b) = v.split_at_mut(i);
quicksort_bounds(a);
quicksort_bounds(b);
}
#[cfg(feature="experimental_pointer_ranges")]
pub fn zip_dot_i32(xs: &[i32], ys: &[i32]) -> i32 {
xs.iter().zip(ys).map(|(x, y)| x * y).sum()
}
#[cfg(feature="experimental_pointer_ranges")]
pub fn zip_dot_i32_prange(xs: &[i32], ys: &[i32]) -> i32 {
scope(xs, move |v| {
scope(ys, move |u| {
let mut sum = 0;
zip(v.pointer_range(), &v,
u.pointer_range(), &u,
|&x, &y| sum += x * y);
sum
})
})
}
pub fn copy<T: Copy>(xs: &[T], ys: &mut [T]) {
for (&x, y) in xs.iter().zip(ys) {
*y = x;
}
}
#[cfg(feature="experimental_pointer_ranges")]
pub fn copy_prange<T: Copy>(xs: &[T], ys: &mut [T]) {
scope(xs, move |v| {
scope(ys, move |mut u| {
zip(v.pointer_range(), &v,
u.pointer_range(), &mut u,
|&x, y| *y = x);
})
})
}
#[test]
fn test_quicksort() {
let mut data = [1, 0];
quicksort_range(&mut data);
assert_eq!(&data, &[0, 1]);
let mut data = [1, 2, 2, 1, 3, 3, 2, 3];
quicksort_range(&mut data);
assert_eq!(&data, &[1, 1, 2, 2, 2, 3, 3, 3]);
let mut data = [1, 4, 2, 0, 3];
quicksort_range(&mut data);
assert_eq!(&data, &[0, 1, 2, 3, 4]);
let mut data = [4, 3, 2, 1, 0];
quicksort_range(&mut data);
assert_eq!(&data, &[0, 1, 2, 3, 4]);
let mut data = [0, 1, 2, 3, 4];
quicksort_range(&mut data);
assert_eq!(&data, &[0, 1, 2, 3, 4]);
let mut data = [0, 1, 5, 2, 3, 4];
quicksort_range(&mut data);
assert_eq!(&data, &[0, 1, 2, 3, 4, 5]);
let mut data = [0, 1, 1, -1, 0, -1];
quicksort_range(&mut data);
assert_eq!(&data, &[-1, -1, 0, 0, 1, 1]);
}
pub fn insertion_sort_indexes<T, F>(v: &mut [T], mut less_than: F) where F: FnMut(&T, &T) -> bool {
scope(v, move |mut v| {
for i in v.range() {
let jtail = v.scan_from_rev(i, |j_elt| less_than(&v[i], j_elt));
v.rotate1_up(jtail);
}
});
}
pub fn insertion_sort2_indexes<T, U, F>(v: &mut [T], u: &mut [U], mut less_than: F) where F: FnMut(&T, &T) -> bool {
scope(v, move |mut v| {
let mut u = v.make_twin(u).unwrap();
for i in v.range() {
let jtail = v.scan_from_rev(i, |j_elt| less_than(&v[i], j_elt));
v.rotate1_up(jtail);
u.rotate1_up(jtail);
}
});
}
pub fn insertion_sort_ranges<T, F>(v: &mut [T], mut less_than: F) where F: FnMut(&T, &T) -> bool {
scope(v, move |mut v| {
if let Ok(mut i) = v.range().nonempty() {
while i.advance() {
let jtail = v.scan_from_rev(i.first(), |j_elt| less_than(&v[i.first()], j_elt));
v.rotate1_up(jtail);
}
}
});
}
#[cfg(feature="experimental_pointer_ranges")]
pub fn insertion_sort_prange_lower<T, F>(v: &mut [T], mut less_than: F)
where F: FnMut(&T, &T) -> bool,
{
scope(v, |mut v| {
for i in v.pointer_range() {
let up_to = v.pointer_range_of(..i);
let lb = lower_bound_prange_(up_to, &v, |x| less_than(x, &v[i]));
if let Ok(lb_range) = v.nonempty_range(lb, i.after()) {
v.rotate1_prange(lb_range);
}
}
});
}
#[cfg(feature="experimental_pointer_ranges")]
pub fn insertion_sort_pointerindex<T, F>(v: &mut [T], mut less_than: F) where F: FnMut(&T, &T) -> bool {
scope(v, move |mut v| {
for i in v.pointer_range() {
let jtail = v.scan_tail_(i, |j_elt| less_than(&v[i], j_elt));
v.rotate1_prange(jtail);
}
});
}
pub fn insertion_sort_rust<T, F>(v: &mut [T], mut less_than: F) where F: FnMut(&T, &T) -> bool {
use std::mem;
use std::ptr;
let len = v.len() as isize;
let buf_v = v.as_mut_ptr();
for i in 1..len {
let mut j = i;
unsafe {
let read_ptr = buf_v.offset(i) as *const T;
while j > 0 && less_than(&*read_ptr, &*buf_v.offset(j - 1)) {
j -= 1;
}
if i != j {
let tmp = ptr::read(read_ptr);
ptr::copy(&*buf_v.offset(j),
buf_v.offset(j + 1),
(i - j) as usize);
ptr::copy_nonoverlapping(&tmp, buf_v.offset(j), 1);
mem::forget(tmp);
}
}
}
}
fn block_swap2<T>(a: &mut [T], b: &mut [T]) {
let count = cmp::min(a.len(), b.len());
let a = &mut a[..count];
let b = &mut b[..count];
for i in 0..count {
swap(&mut a[i], &mut b[i]);
}
}
#[derive(Clone, Debug)]
pub struct AlgorithmError(pub &'static str);
impl From<&'static str> for AlgorithmError {
fn from(s: &'static str) -> Self { AlgorithmError(s) }
}
pub fn merge_internal_indices<T: Ord>(data: &mut [T], left_end: usize, buffer: &mut [T])
-> Result<(), AlgorithmError>
{
debug_assert!(data.len() >= 1);
if left_end > data.len() || left_end > buffer.len() {
Err("merge_internal: data or buffer too short")?;
}
scope(data, move |mut data| {
let r = data.range();
scope(&mut buffer[..left_end], |mut buffer| {
let rb = buffer.range();
let right_end = data.len();
if right_end - left_end == 0 {
return;
}
block_swap2(&mut data[r], &mut buffer[rb]);
let mut i = match rb.contains(0) {
Some(i) => i,
None => return,
};
let mut out = match r.contains(0) {
Some(i) => i,
None => return,
};
let mut j = match r.contains(left_end) {
Some(i) => i,
None => return,
};
loop {
if buffer[i] <= data[j] {
swap(&mut buffer[i], &mut data[out]);
data.forward(&mut out);
if !buffer.forward(&mut i) { break; }
} else {
data.swap(j, out);
data.forward(&mut out);
if !data.forward(&mut j) {
block_swap2(&mut buffer[i..], &mut data[out..]);
break;
}
}
}
})
});
Ok(())
}
pub fn merge_internal_ranges<T: Ord>(data: &mut [T], left_end: usize, buffer: &mut [T])
-> Result<(), AlgorithmError>
{
debug_assert!(data.len() >= 1);
if left_end > data.len() || left_end > buffer.len() {
Err("merge_internal: data or buffer too short")?;
}
scope(data, |mut data| {
let r = data.range();
scope(&mut buffer[..left_end], |mut buffer| {
let rb = buffer.range();
let mut i = match rb.nonempty() {
Ok(r) => r,
Err(_) => return,
};
let mut out = match r.nonempty() {
Ok(r) => r,
Err(_) => return,
};
let mut j = match r.split_at(left_end).1.nonempty() {
Ok(r) => r,
Err(_) => return,
};
block_swap2(&mut data[r], &mut buffer[rb]);
loop {
if buffer[i.first()] <= data[j.first()] {
swap(&mut buffer[i.first()], &mut data[out.first()]);
if !out.advance() { return; }
if !i.advance() { return; }
} else {
data.swap(j.first(), out.first());
if !out.advance() { return; }
if !j.advance() {
block_swap2(&mut buffer[i], &mut data[out]);
break;
}
}
}
})
});
Ok(())
}
#[cfg(feature="use_std")]
#[test]
fn test_merge_internal() {
let mut buffer = [0; 128];
let a = (0..15).collect::<Vec<_>>();
let b = (1..25).filter(|&x| x % 2 == 0).collect::<Vec<_>>();
let data = [&a[..], &b[..]].concat();
let mut ans = data.clone();
ans.sort();
{
let mut workspace = data.clone();
merge_internal_indices(&mut workspace, a.len(), &mut buffer).ok();
assert_eq!(workspace, ans);
assert!(buffer.iter().all(|x| *x == 0));
}
{
let mut workspace = data.clone();
merge_internal_ranges(&mut workspace, a.len(), &mut buffer).ok();
assert_eq!(workspace, ans);
assert!(buffer.iter().all(|x| *x == 0));
}
}
pub fn heapify<T: Ord>(v: &mut [T]) {
scope(v, |mut v| {
let (left, _right) = v.range().split_in_half();
for i in left.into_iter().rev() {
let mut pos = i;
while let Ok(mut child) = v.vet(pos.integer() * 2 + 1) {
let mut right = child;
if v.forward(&mut right) && v[child] > v[right] {
child = right;
}
if v[pos] <= v[child] {
break;
}
v.swap(pos, child);
pos = child;
}
}
});
}
#[test]
fn test_heapify() {
let mut data = [8, 12, 9, 7, 22, 3, 26, 14, 11, 15, 22];
let heap = [3, 7, 8, 11, 15, 9, 26, 14, 12, 22, 22];
heapify(&mut data);
assert_eq!(&data, &heap);
}
pub fn binary_search<T: Ord>(v: &[T], elt: &T) -> Result<usize, usize> {
binary_search_by(v, |x| x.cmp(elt))
}
pub fn binary_search_by<T, F>(v: &[T], mut f: F) -> Result<usize, usize>
where F: FnMut(&T) -> Ordering,
{
scope(v, move |v| {
let mut range = v.range();
loop {
let (a, b) = range.split_in_half();
if let Ok(b_) = b.nonempty() {
let mid = b_.first();
match f(&v[mid]) {
Ordering::Equal => return Ok(mid.integer()),
Ordering::Greater => range = a,
Ordering::Less => range = b_.tail(),
}
} else {
break;
}
}
Err(range.start())
})
}
#[cfg(feature="experimental_pointer_ranges")]
pub fn binary_search_by_prange<'id, T, F>(v: &[T], compare: F)
-> Result<usize, usize>
where F: FnMut(&T) -> Ordering,
{
scope(v, move |v| {
match binary_search_by_prange_(v.pointer_range(), &v, compare) {
Ok(p) => Ok(v.distance_to(p)),
Err(p) => Err(v.distance_to(p)),
}
})
}
#[cfg(feature="experimental_pointer_ranges")]
pub fn binary_search_by_prange_<'id, T, P, Array, F>(range: PRange<'id, T, P>,
v: &Container<'id, Array>,
mut compare: F)
-> Result<PIndex<'id, T>, PIndex<'id, T, Unknown>>
where F: FnMut(&T) -> Ordering,
Array: Contiguous<Item=T>,
{
let mut range = range.no_proof();
loop {
let (a, b) = range.split_in_half();
if let Ok(b_) = b.nonempty() {
let mid = b_.first();
match compare(&v[mid]) {
Ordering::Equal => return Ok(mid),
Ordering::Greater => range = a,
Ordering::Less => range = b_.tail(),
}
} else {
break;
}
}
Err(range.first())
}
#[inline(never)]
#[cfg(feature="experimental_pointer_ranges")]
pub fn binary_search_by_pslice<'id, T, F>(v: &[T], compare: F)
-> Result<usize, usize>
where F: FnMut(&T) -> Ordering,
{
scope(v, move |v| {
match binary_search_by_pslice_(v.pointer_slice(), &v, compare) {
Ok(p) => Ok(v.distance_to(p)),
Err(p) => Err(v.distance_to(p)),
}
})
}
#[cfg(feature="experimental_pointer_ranges")]
pub fn binary_search_by_pslice_<'id, T, P, Array, F>(range: PSlice<'id, T, P>,
v: &Container<'id, Array>,
mut compare: F)
-> Result<PIndex<'id, T>, PIndex<'id, T, Unknown>>
where F: FnMut(&T) -> Ordering,
Array: Contiguous<Item=T>,
{
let mut range = range.no_proof();
loop {
let (a, b) = range.split_in_half();
if let Ok(b_) = b.nonempty() {
let mid = b_.first();
match compare(&v[mid]) {
Ordering::Equal => return Ok(mid),
Ordering::Greater => range = a,
Ordering::Less => range = b_.tail(),
}
} else {
break;
}
}
Err(range.first())
}
#[test]
fn test_binary_search() {
let data = [3, 7, 8, 11, 15, 22, 26];
assert_eq!(binary_search(&data, &3), Ok(0));
assert_eq!(binary_search(&data, &2), Err(0));
let elts = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 25, 26, 27, 28];
for elt in &elts {
assert_eq!(binary_search(&data, elt), data.binary_search(elt));
}
}
pub fn lower_bound<T: PartialOrd>(v: &[T], elt: &T) -> usize {
scope(v, move |v| {
let mut range = v.range();
while let Ok(range_) = range.nonempty() {
let (a, b) = range_.split_in_half();
if v[b.first()] < *elt {
range = b.tail();
} else {
range = a;
}
}
range.start()
})
}
#[cfg(feature="experimental_pointer_ranges")]
pub fn lower_bound_prange<T: PartialOrd>(v: &[T], elt: &T) -> usize {
scope(v, move |v| {
let mut range = v.pointer_range();
while let Ok(range_) = range.nonempty() {
let (a, b) = range_.split_in_half();
if v[b.first()] < *elt {
range = b.tail();
} else {
range = a;
}
}
v.distance_to(range.first())
})
}
#[cfg(feature="experimental_pointer_ranges")]
use crate::Container;
#[cfg(feature="experimental_pointer_ranges")]
use crate::Unknown;
#[cfg(feature="experimental_pointer_ranges")]
use crate::proof::Provable;
#[cfg(feature="experimental_pointer_ranges")]
use crate::container_traits::Contiguous;
#[cfg(feature="experimental_pointer_ranges")]
use crate::pointer::{PIndex, PRange, PSlice};
#[cfg(feature="experimental_pointer_ranges")]
pub fn lower_bound_prange_<'id, T, P, Array, F>(range: PRange<'id, T, P>,
v: &Container<'id, Array>,
mut less_than: F)
-> PIndex<'id, T, Unknown>
where Array: Contiguous<Item=T>,
F: FnMut(&T) -> bool,
{
let mut range = range.no_proof();
while let Ok(range_) = range.nonempty() {
let (a, b) = range_.split_in_half();
if less_than(&v[b.first()]) {
range = b.tail();
} else {
range = a;
}
}
range.first()
}
#[cfg(feature="experimental_pointer_ranges")]
pub fn lower_bound_pslice_<'id, T, P, Array, F>(range: PSlice<'id, T, P>,
v: &Container<'id, Array>,
mut less_than: F)
-> PIndex<'id, T, Unknown>
where Array: Contiguous<Item=T>,
F: FnMut(&T) -> bool,
{
let mut range = range.no_proof();
while let Ok(range_) = range.nonempty() {
let (a, b) = range_.split_in_half();
if less_than(&v[b.first()]) {
range = b.tail();
} else {
range = a;
}
}
range.first()
}
#[cfg(feature="experimental_pointer_ranges")]
pub fn lower_bound_pslice<T, F>(v: &[T], f: F) -> usize
where F: FnMut(&T) -> bool,
{
scope(v, move |v| {
let range = v.pointer_slice();
v.distance_to(lower_bound_pslice_(range, &v, f))
})
}
pub fn lower_bound_raw_ptr<T: PartialOrd>(v: &[T], elt: &T) -> usize {
unsafe {
let mut start = v.as_ptr();
let end = start.offset(v.len() as isize);
let mut count = ptrdistance(start, end);
while count > 0 {
let step = count / 2;
let it = start.offset(step as isize);
if *it < *elt {
start = it.offset(1);
count -= step + 1;
} else {
count = step;
}
}
ptrdistance(v.as_ptr(), start)
}
}
fn ptrdistance<T>(from: *const T, to: *const T) -> usize {
use std::mem;
(to as usize - from as usize) / mem::size_of::<T>()
}
#[test]
fn test_lower_bound() {
let data = [3, 7, 8, 8, 8, 11, 11, 11, 15, 22, 22, 26];
assert_eq!(lower_bound(&data, &8), 2);
assert_eq!(lower_bound(&data, &7), 1);
let elts = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 25, 26, 27, 28];
for elt in &elts {
assert_eq!(lower_bound(&data, elt),
data.binary_search_by(|x| if x >= elt {
Ordering::Greater
} else {
Ordering::Less
}).unwrap_err());
}
}
#[test]
fn test_lower_bound_ptr() {
let data = [3, 7, 8, 8, 8, 11, 11, 11, 15, 22, 22, 26];
assert_eq!(lower_bound_raw_ptr(&data, &8), 2);
assert_eq!(lower_bound_raw_ptr(&data, &7), 1);
let elts = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 25, 26, 27, 28];
for elt in &elts {
assert_eq!(lower_bound_raw_ptr(&data, elt),
data.binary_search_by(|x| if x >= elt {
Ordering::Greater
} else {
Ordering::Less
}).unwrap_err());
}
}
#[cfg(feature="experimental_pointer_ranges")]
#[test]
fn test_lower_bound_pointer() {
let data = [3, 7, 8, 8, 8, 11, 11, 11, 15, 22, 22, 26];
assert_eq!(lower_bound_prange(&data, &8), 2);
assert_eq!(lower_bound_prange(&data, &7), 1);
let elts = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 25, 26, 27, 28];
for elt in &elts {
assert_eq!(lower_bound_prange(&data, elt),
data.binary_search_by(|x| if x >= elt {
Ordering::Greater
} else {
Ordering::Less
}).unwrap_err());
}
}
#[test]
fn test_twin_insertion_sort() {
let mut data1 = [2, 3, 1, 4];
let mut data2 = data1;
let mut data3 = ["a", "b", "c", "d"];
insertion_sort_indexes(&mut data1, PartialOrd::lt);
insertion_sort2_indexes(&mut data2, &mut data3, PartialOrd::lt);
assert_eq!(data2, [1, 2, 3, 4]);
assert_eq!(data3, ["c", "a", "b", "d"]);
}
#[test]
fn test_make_twin() {
let arr1 = [1, 2, 3, 4, 5];
let mut arr2 = [6, 7, 8, 9, 10];
scope(&arr1[..], |arr| {
let r = arr.range();
let r = r.nonempty().unwrap();
let twin = arr.make_twin(&mut arr2[..]).unwrap();
let mut tested = 0;
for (i, j) in r.into_iter().zip(twin.range()) {
assert_eq!(twin[i], twin[j]);
assert_eq!(arr[i] + 5, twin[j]);
assert_eq!(i, j);
tested += 1;
}
assert_eq!(tested, 5);
});
}