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

//! Derivative work of [`alloc::slice`] licensed under `MIT OR Apache-2.0`.
//!
//! [`alloc::slice`]: https://doc.rust-lang.org/src/alloc/slice.rs.html

#![cfg(feature = "alloc")]

use crate::merge_sort::{merge_sort, TimSortRun};
use core::{alloc::Layout, mem};
use ndarray::ArrayViewMut1;

#[cfg(not(feature = "std"))]
extern crate alloc as no_std_alloc;
#[cfg(not(feature = "std"))]
use no_std_alloc::alloc::{alloc, dealloc};
#[cfg(feature = "std")]
use std::alloc::{alloc, dealloc};

#[inline]
pub fn stable_sort<T, F>(v: ArrayViewMut1<'_, T>, mut is_less: F)
where
	F: FnMut(&T, &T) -> bool,
{
	if mem::size_of::<T>() == 0 {
		// Sorting has no meaningful behavior on zero-sized types. Do nothing.
		return;
	}

	let elem_alloc_fn = |len: usize| -> *mut T {
		// SAFETY: Creating the layout is safe as long as merge_sort never calls this with len >
		// v.len(). Alloc in general will only be used as 'shadow-region' to store temporary swap
		// elements.
		unsafe { alloc(Layout::array::<T>(len).unwrap_unchecked()) as *mut T }
	};

	let elem_dealloc_fn = |buf_ptr: *mut T, len: usize| {
		// SAFETY: Creating the layout is safe as long as merge_sort never calls this with len >
		// v.len(). The caller must ensure that buf_ptr was created by elem_alloc_fn with the same
		// len.
		unsafe {
			dealloc(
				buf_ptr as *mut u8,
				Layout::array::<T>(len).unwrap_unchecked(),
			);
		}
	};

	let run_alloc_fn = |len: usize| -> *mut TimSortRun {
		// SAFETY: Creating the layout is safe as long as merge_sort never calls this with an
		// obscene length or 0.
		unsafe { alloc(Layout::array::<TimSortRun>(len).unwrap_unchecked()) as *mut TimSortRun }
	};

	let run_dealloc_fn = |buf_ptr: *mut TimSortRun, len: usize| {
		// SAFETY: The caller must ensure that buf_ptr was created by elem_alloc_fn with the same
		// len.
		unsafe {
			dealloc(
				buf_ptr as *mut u8,
				Layout::array::<TimSortRun>(len).unwrap_unchecked(),
			);
		}
	};

	merge_sort(
		v,
		&mut is_less,
		elem_alloc_fn,
		elem_dealloc_fn,
		run_alloc_fn,
		run_dealloc_fn,
	);
}

#[cfg(feature = "std")]
#[cfg(test)]
mod test {
	use super::stable_sort;
	use core::cmp::Ordering;
	use ndarray::Array1;
	use quickcheck_macros::quickcheck;

	struct Item {
		index: usize,
		value: u32,
	}

	impl Eq for Item {}

	impl PartialEq for Item {
		fn eq(&self, other: &Self) -> bool {
			self.value == other.value
		}
	}

	impl Ord for Item {
		fn cmp(&self, other: &Self) -> Ordering {
			self.value.cmp(&other.value)
		}
	}

	impl PartialOrd for Item {
		fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
			Some(self.cmp(other))
		}
	}

	impl From<(usize, u32)> for Item {
		fn from((index, value): (usize, u32)) -> Self {
			Self { index, value }
		}
	}

	#[quickcheck]
	fn stably_sorted(xs: Vec<u32>) {
		let xs = xs
			.into_iter()
			.enumerate()
			.map(Item::from)
			.collect::<Vec<Item>>();
		let mut array = Array1::from_vec(xs);
		stable_sort(array.view_mut(), &mut Item::lt);
		for i in 1..array.len() {
			let [a, b] = [&array[i - 1], &array[i]];
			if a.value == b.value {
				assert!(a.index < b.index);
			} else {
				assert!(a.value < b.value);
			}
		}
	}
}