permoot 0.2.1

General-purpose no_std permutation library
Documentation 
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

use crate::error::TooLongSliceForPermutation;
use crate::util::AlwaysEq;
use crate::Permutation;

#[derive(Ord, PartialOrd, Eq, PartialEq)]
enum SortHelper<'a, T> {
	ActualValue(AlwaysEq<usize>, &'a T),
	Lengthening(usize),
}

impl<'a, T> SortHelper<'a, T> {
	fn index(&self) -> usize {
		match *self {
			Self::ActualValue(i, _) => i.0,
			Self::Lengthening(i) => i,
		}
	}
}

/// An abstraction that allows implementing custom sorting algorithms
pub trait SortArray<const N: usize> {
	#[allow(missing_docs)] // the function name says it all
	fn sort<T: Ord>(arr: &mut [T; N]);
}

/// An abstraction that allows implementing custom sorting algorithms
pub trait SortSlice {
	#[allow(missing_docs)] // the function name says it all
	fn sort<T: Ord>(sl: &mut [T]);
}

/// Sort an array or slice using [slice::sort_unstable](https://doc.rust-lang.org/std/primitive.slice.html#method.sort_unstable)
pub struct CoreSortUnstable;

impl<const N: usize> SortArray<N> for CoreSortUnstable {
	fn sort<T: Ord>(arr: &mut [T; N]) {
		arr.sort_unstable();
	}
}

impl SortSlice for CoreSortUnstable {
	fn sort<T: Ord>(sl: &mut [T]) {
		sl.sort_unstable();
	}
}

#[cfg(feature = "std")]
/// Sort an array or slice using [slice::sort](https://doc.rust-lang.org/std/primitive.slice.html#method.sort)
pub struct StdSort;

#[cfg(feature = "std")]
impl<const N: usize> SortArray<N> for StdSort {
	fn sort<T: Ord>(arr: &mut [T; N]) {
		arr.sort();
	}
}

#[cfg(feature = "std")]
impl SortSlice for StdSort {
	fn sort<T: Ord>(sl: &mut [T]) {
		sl.sort();
	}
}

/// Construct a permutations that would sort a slice/array when [`apply`](crate::Permutation::apply)ed
impl<const N: usize> Permutation<N> {
	/// Construct a permutation that would sort `arr` according to the sort method given by `S`
	pub fn from_custom_sort<T: Ord, S: SortArray<N>>(arr: &[T; N]) -> Self {
		let mut to_sort: [_; N] =
			core::array::from_fn(|i| SortHelper::ActualValue(AlwaysEq(i), &arr[i]));

		S::sort(&mut to_sort);

		Self {
			arr_repr: to_sort.map(|s| s.index()),
		}
	}

	/// Construct a permutation that would sort `arr` according to the sort method given by [`CoreSortUnstable`]
	#[inline]
	pub fn from_sort_unstable<T: Ord>(arr: &[T; N]) -> Self {
		Self::from_custom_sort::<T, CoreSortUnstable>(arr)
	}

	/// Construct a permutation that would sort `arr` according to the sort method given by [`StdSort`]
	#[cfg(feature = "std")]
	#[inline]
	pub fn from_sort<T: Ord>(arr: &[T; N]) -> Self {
		Self::from_custom_sort::<T, StdSort>(arr)
	}

	/// Construct a permutation that would sort `sl` according to the sort method given by `S`
	pub fn from_custom_sort_slice<T: Ord, S: SortSlice>(
		sl: &[T],
	) -> Result<Self, TooLongSliceForPermutation> {
		if sl.len() > N {
			return Err(TooLongSliceForPermutation {
				length: sl.len(),
				max: N,
			});
		}

		let mut arr: [_; N] = core::array::from_fn(|i| match sl.get(i) {
			Some(x) => SortHelper::ActualValue(AlwaysEq(i), x),
			None => SortHelper::Lengthening(i),
		});

		S::sort(&mut arr[..]);

		Ok(Self {
			arr_repr: arr.map(|s| s.index()),
		})
	}

	/// Construct a permutation that would sort `sl` according to the sort method given by [`CoreSortUnstable`]
	#[inline]
	pub fn from_sort_unstable_slice<T: Ord>(sl: &[T]) -> Result<Self, TooLongSliceForPermutation> {
		Self::from_custom_sort_slice::<T, CoreSortUnstable>(sl)
	}

	/// Construct a permutation that would sort `sl` according to the sort method given by [`StdSort`]
	#[cfg(feature = "std")]
	#[inline]
	pub fn from_sort_slice<T: Ord>(sl: &[T]) -> Result<Self, TooLongSliceForPermutation> {
		Self::from_custom_sort_slice::<T, StdSort>(sl)
	}
}