is_sorted 0.1.1

Is an Iterator sorted?
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

/// Utility macros

/// Checks whether a slice is sorted until the first element aligned with a
/// $boundary (16 for 16-byte boundary). Returns a (i,n,s) tuple where `i` is
/// the index of the next element in the slice aligned to a 16-byte boundary,
/// `n` the slice length, and `s` the slice.
macro_rules! is_sorted_lt_until_alignment_boundary {
    ($s:ident, $ty:ident, $boundary:expr) => {{
        let n = $s.len();
        // If the slice has zero or one elements, it is sorted:
        if n < 2 {
            return n as usize;
        }

        let mut i: usize = 0;

        // The first element of the slice might not be aligned to a
        // 16-byte boundary. Handle the elements until the
        // first 16-byte boundary using the scalar algorithm
        {
            let mut a =
                $s.as_ptr().align_offset($boundary) / ::mem::size_of::<$ty>();
            while a > 0 && i < n - 1 {
                if !($s.get_unchecked(i) <= $s.get_unchecked(i + 1)) {
                    return i;
                }
                i += 1;
                a -= 1;
            }
            debug_assert!(
                i == n - 1
                    || $s.as_ptr().offset(i as isize).align_offset($boundary)
                        == 0
            );
        }

        i
    }};
}

/// Handles the tail of the `slice` `s` of length `n` starting at index `i`
/// using a scalar loop:
macro_rules! is_sorted_lt_tail {
    ($s:ident, $n:ident, $i:ident) => {{
        // Handle the tail of the slice using the scalar algoirithm:
        while $i < $n - 1 {
            if !($s.get_unchecked($i) <= $s.get_unchecked($i + 1)) {
                return $i;
            }
            $i += 1;
        }
        debug_assert!($i == $n - 1);
        $i + 1
    }};
}

macro_rules! is_sorted_gt_until_alignment_boundary {
    ($s:ident, $ty:ident, $boundary:expr) => {{
        let n = $s.len();
        // If the slice has zero or one elements, it is sorted:
        if n < 2 {
            return n;
        }

        let mut i: usize = 0;

        // The first element of the slice might not be aligned to a
        // 16-byte boundary. Handle the elements until the
        // first 16-byte boundary using the scalar algorithm
        {
            let mut a =
                $s.as_ptr().align_offset($boundary) / ::mem::size_of::<$ty>();
            while a > 0 && i < n - 1 {
                if !($s.get_unchecked(i) >= $s.get_unchecked(i + 1)) {
                    return i;
                }
                i += 1;
                a -= 1;
            }
            debug_assert!(
                i == n - 1
                    || $s.as_ptr().offset(i as isize).align_offset($boundary)
                        == 0
            );
        }

        i
    }};
}

macro_rules! is_sorted_gt_tail {
    ($s:ident, $n:ident, $i:ident) => {{
        // Handle the tail of the slice using the scalar algoirithm:
        while $i < $n - 1 {
            if !($s.get_unchecked($i) >= $s.get_unchecked($i + 1)) {
                return $i;
            }
            $i += 1;
        }
        debug_assert!($i == $n - 1);
        $i + 1
    }};
}