sorted-rs 0.1.0

another blazing fast algorithm through SIMDs which used to check the sequnce is sort or not
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

#![allow(dead_code)]

pub use simd::Trend;

use crate::simd::SinglePrecision;

mod simd;

///
/// example:
///     let nums = vec![1, 2, 3, 4, 5, ....];
///     is_sorted(&nums, Trend::Ascending);
///     let nums = vec![9, 8, 7, 6, 5, ....];
///     is_sorted(&nums, Trend:Descending);
///
/// is_sorted check sequence is sorted or not but it doesn't check the length of input.
/// It's better to avoid call the function when the length of input is 1 or 0;

pub fn is_sorted<T: num::Integer + SinglePrecision>(a: &[T], t: Trend) -> bool {
    let a = a.as_ref();
    let n = a.len();
    #[cfg(feature = "use-sse")]
    {
        if n < SSE_WORD {
            return simd::is_sorted(a, t);
        }
    }
    #[cfg(feature = "use-avx2")]
    {
        if n < AVX2_WORD {
            return simd::is_sorted(&a, t);
        }
    }
    #[cfg(feature = "use-sse")]
    {
        if n >= SSE_WORD {
            return simd::is_sorted_unroll4(&a, t);
        }
    }
    #[cfg(feature = "use-avx2")]
    {
        if n >= AVX2_WORD {
            return simd::is_sorted_unroll4(&a, t);
        }
    }
    false
}

const WORD: usize = 8;
const SSE_WORD: usize = 4 * (4 + 1);
const AVX2_WORD: usize = 4 * 7 + 1;

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_works() {
        for i in 1..1024 {
            let mut a = (0..i).into_iter().collect::<Vec<_>>();
            assert!(is_sorted(&a, Trend::Ascending));
            a.reverse();
            assert!(is_sorted(&a, Trend::Descending));
            a.fill(1);
            assert!(is_sorted(&a, Trend::Ascending));
            assert!(is_sorted(&a, Trend::Descending));
        }

        for i in 6..1024 {
            let a = (0..i).into_iter().collect::<Vec<_>>();
            let mut reversed: Vec<i32> = Vec::with_capacity(a.len());
            for cur_data in a.chunks(3) {
                reversed.extend(cur_data.iter().rev());
            }

            assert!(!is_sorted(&reversed, Trend::Ascending), "{:?}", reversed);
            assert!(!is_sorted(&reversed, Trend::Descending), "{:?}", reversed);
        }

        for i in 1u32..1024 {
            let mut a = (0..i).into_iter().collect::<Vec<_>>();
            assert!(is_sorted(&a, Trend::Ascending));
            a.reverse();
            assert!(is_sorted(&a, Trend::Descending));
            a.fill(1);
            assert!(is_sorted(&a, Trend::Ascending));
            assert!(is_sorted(&a, Trend::Descending));
        }
    }
}