try_partialord/sort/
mod.rs

1use crate::{ord_as_cmp, InvalidOrderError, OrderResult};
2use core::cmp::Ordering;
3#[cfg(feature = "std")]
4mod std_mergesort;
5mod std_quicksort;
6
7/// Sort methods for [`PartialOrd`].
8pub trait TrySort<T> {
9    #[cfg(feature = "std")]
10    #[inline]
11    /// [`PartialOrd`] version for [`slice::sort`]
12    fn try_sort(&mut self) -> OrderResult<()>
13    where
14        T: PartialOrd<T>,
15    {
16        self.try_sort_by(ord_as_cmp)
17    }
18    #[cfg(feature = "std")]
19    /// [`PartialOrd`] version for [`slice::sort_by`]
20    fn try_sort_by<F>(&mut self, compare: F) -> OrderResult<()>
21    where
22        F: FnMut(&T, &T) -> Option<bool>;
23    #[cfg(feature = "std")]
24    #[inline]
25    /// [`PartialOrd`] version for [`slice::sort_by_key`]
26    fn try_sort_by_key<K, F>(&mut self, f: F) -> OrderResult<()>
27    where
28        F: FnMut(&T) -> Option<K>,
29        K: PartialOrd<K>,
30    {
31        let mut f2 = f;
32        self.try_sort_by(|a, b| f2(a).partial_cmp(&f2(b)).map(|a| a == Ordering::Less))
33    }
34    #[cfg(feature = "std")]
35    /// [`PartialOrd`] version for [`slice::sort_by_cached_key`]
36    fn try_sort_by_cached_key<K, F>(&mut self, f: F) -> OrderResult<()>
37    where
38        F: FnMut(&T) -> Option<K>,
39        K: PartialOrd<K>;
40
41    #[inline]
42    /// [`PartialOrd`] version for [`slice::sort_unstable`]
43    fn try_sort_unstable(&mut self) -> OrderResult<()>
44    where
45        T: PartialOrd<T>,
46    {
47        self.try_sort_unstable_by(ord_as_cmp)
48    }
49    /// [`PartialOrd`] version for [`slice::sort_unstable_by`]
50    fn try_sort_unstable_by<F>(&mut self, compare: F) -> OrderResult<()>
51    where
52        F: FnMut(&T, &T) -> Option<bool>;
53    #[inline]
54    /// [`PartialOrd`] version for [`slice::sort_unstable_by_key`]
55    fn try_sort_unstable_by_key<K, F>(&mut self, f: F) -> OrderResult<()>
56    where
57        F: FnMut(&T) -> Option<K>,
58        K: PartialOrd<K>,
59    {
60        let mut f2 = f;
61        self.try_sort_unstable_by(|a, b| f2(a).partial_cmp(&f2(b)).map(|a| a == Ordering::Less))
62    }
63
64    #[inline]
65    /// [`PartialOrd`] version for [`slice::is_sorted`]
66    fn try_is_sorted(&self) -> OrderResult<bool>
67    where
68        T: PartialOrd<T>,
69    {
70        self.try_is_sorted_by(ord_as_cmp)
71    }
72    /// [`PartialOrd`] version for [`slice::is_sorted_by`]
73    fn try_is_sorted_by<F>(&self, compare: F) -> OrderResult<bool>
74    where
75        F: FnMut(&T, &T) -> Option<bool>;
76    #[inline]
77    /// [`PartialOrd`] version for [`slice::is_sorted_by_key`]
78    fn try_is_sorted_by_key<K, F>(&mut self, f: F) -> OrderResult<bool>
79    where
80        F: FnMut(&T) -> Option<K>,
81        K: PartialOrd<K>,
82    {
83        let mut f2 = f;
84        self.try_is_sorted_by(|a, b| f2(a).partial_cmp(&f2(b)).map(|a| a == Ordering::Less))
85    }
86}
87
88impl<T> TrySort<T> for [T] {
89    #[inline]
90    #[cfg(feature = "std")]
91    fn try_sort_by<F>(&mut self, compare: F) -> OrderResult<()>
92    where
93        F: FnMut(&T, &T) -> Option<bool>,
94    {
95        std_mergesort::merge_sort(self, compare).ok_or(InvalidOrderError)
96    }
97
98    #[inline]
99    fn try_sort_unstable_by<F>(&mut self, compare: F) -> OrderResult<()>
100    where
101        F: FnMut(&T, &T) -> Option<bool>,
102    {
103        std_quicksort::quicksort(self, compare).ok_or(InvalidOrderError)
104    }
105
106    #[inline]
107    fn try_is_sorted_by<F>(&self, compare: F) -> OrderResult<bool>
108    where
109        F: FnMut(&T, &T) -> Option<bool>,
110    {
111        try_is_sorted_by_slice(self, compare)
112    }
113
114    #[cfg(feature = "std")]
115    #[inline]
116    fn try_sort_by_cached_key<K, F>(&mut self, f: F) -> OrderResult<()>
117    where
118        F: FnMut(&T) -> Option<K>,
119        K: PartialOrd<K>,
120    {
121        // Helper macro for indexing our vector by the smallest possible type, to reduce allocation.
122        macro_rules! sort_by_key {
123            ($t:ty, $slice:ident, $f:ident) => {{
124                let mut indices: Vec<_> = $slice
125                    .iter()
126                    .map($f)
127                    .enumerate()
128                    .map(|(i, k)| (k, i as $t))
129                    .collect();
130                // The elements of `indices` are unique, as they are indexed, so any sort will be
131                // stable with respect to the original slice. We use `sort_unstable` here because
132                // it requires less memory allocation.
133                indices.try_sort_unstable()?;
134                for i in 0..$slice.len() {
135                    let mut index = indices[i].1;
136                    while (index as usize) < i {
137                        index = indices[index as usize].1;
138                    }
139                    indices[i].1 = index;
140                    $slice.swap(i, index as usize);
141                }
142                Ok(())
143            }};
144        }
145
146        let sz_u8 = core::mem::size_of::<(K, u8)>();
147        let sz_u16 = core::mem::size_of::<(K, u16)>();
148        let sz_u32 = core::mem::size_of::<(K, u32)>();
149        let sz_usize = core::mem::size_of::<(K, usize)>();
150
151        let len = self.len();
152        if len < 2 {
153            return Ok(());
154        }
155        if sz_u8 < sz_u16 && len <= (u8::MAX as usize) {
156            return sort_by_key!(u8, self, f);
157        }
158        if sz_u16 < sz_u32 && len <= (u16::MAX as usize) {
159            return sort_by_key!(u16, self, f);
160        }
161        if sz_u32 < sz_usize && len <= (u32::MAX as usize) {
162            return sort_by_key!(u32, self, f);
163        }
164        sort_by_key!(usize, self, f)
165    }
166}
167
168/// Function to check whether slice is sorted.
169pub fn try_is_sorted_by_slice<T, F>(slice: &[T], compare: F) -> OrderResult<bool>
170where
171    F: FnMut(&T, &T) -> Option<bool>,
172{
173    let mut cmp = compare;
174    if slice.len() > 1 {
175        unsafe {
176            let mut prev = slice.get_unchecked(0);
177            for i in 1..slice.len() {
178                let next = slice.get_unchecked(i);
179                if let Some(x) = cmp(&prev, &next) {
180                    if !x {
181                        return Ok(false);
182                    }
183                    prev = next;
184                } else {
185                    return Err(InvalidOrderError);
186                }
187            }
188        }
189    }
190    Ok(true)
191}
192
193/// Function to check whether iter is sorted.
194pub fn try_is_sorted_by<T, I, F>(mut iter: I, compare: F) -> OrderResult<bool>
195where
196    F: FnMut(&T, &T) -> Option<bool>,
197    I: Iterator<Item = T>,
198{
199    let mut cmp = compare;
200    if let Some(mut prev) = iter.next() {
201        for next in iter {
202            if let Some(x) = cmp(&prev, &next) {
203                if !x {
204                    return Ok(false);
205                }
206                prev = next;
207            } else {
208                return Err(InvalidOrderError);
209            }
210        }
211    }
212    Ok(true)
213}
214
215#[cfg(test)]
216#[cfg(feature = "std")]
217mod tests {
218    use crate::sort::*;
219    use rand::distributions::Standard;
220    use rand::prelude::*;
221    use std::vec::Vec;
222
223    #[test]
224    fn try_sort_ok() {
225        let rng = thread_rng();
226        let mut v: Vec<f32> = Standard.sample_iter(rng).take(100).collect();
227        let res = v.try_sort();
228        assert!(res.is_ok());
229        assert!(v.try_is_sorted().unwrap_or(false))
230    }
231
232    #[test]
233    fn try_sort_error() {
234        let rng = thread_rng();
235        let mut v: Vec<f32> = Standard.sample_iter(rng).take(100).collect();
236        v.push(f32::NAN);
237        let res = v.try_sort();
238        assert!(res.is_err());
239        assert!(!v.try_is_sorted().is_err())
240    }
241}
try_partialord/sort/mod.rs

try_partialord/sort/
mod.rs
