rusty-perm 0.2.0

Rusty permutation with no-std
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

use crate::common::*;

/// The permutation operator on slice-like types.
pub trait PermApply<T>
where
    T: ?Sized,
{
    type Output;

    fn apply(&self, input: &mut T) -> Self::Output;
}

mod without_std {
    use super::*;
    use crate::perm_type::PermS;

    impl<T, const SIZE: usize> PermApply<[T; SIZE]> for PermS<SIZE> {
        type Output = ();

        fn apply(&self, input: &mut [T; SIZE]) -> Self::Output {
            let mut visited = [false; SIZE];
            apply(&self.indices, &mut visited, input);
        }
    }

    impl<T, const SIZE: usize> PermApply<[T]> for PermS<SIZE> {
        type Output = Result<(), &'static str>;

        fn apply(&self, input: &mut [T]) -> Self::Output {
            if input.len() != SIZE {
                return Err("input slice length mismatch");
            }
            let mut visited = [false; SIZE];
            apply(&self.indices, &mut visited, input);
            Ok(())
        }
    }
}

#[cfg(feature = "std")]
mod with_std {
    use super::*;
    use crate::perm_type::{PermD, PermS};

    impl<T, const SIZE: usize> PermApply<[T; SIZE]> for PermD {
        type Output = Result<(), &'static str>;

        fn apply(&self, input: &mut [T; SIZE]) -> Self::Output {
            let len = self.indices.len();
            if len != SIZE {
                return Err("input slice length mismatch");
            }
            let mut visited = vec![false; len];
            apply(&self.indices, &mut visited, input);
            Ok(())
        }
    }

    impl<T> PermApply<[T]> for PermD {
        type Output = Result<(), &'static str>;

        fn apply(&self, input: &mut [T]) -> Self::Output {
            let len = self.indices.len();
            if len != input.len() {
                return Err("input slice length mismatch");
            }
            let mut visited = vec![false; len];
            apply(&self.indices, &mut visited, input);
            Ok(())
        }
    }

    impl<T> PermApply<Vec<T>> for PermD {
        type Output = Result<(), &'static str>;

        fn apply(&self, input: &mut Vec<T>) -> Self::Output {
            let len = self.indices.len();
            if len != input.len() {
                return Err("input slice length mismatch");
            }
            let mut visited = vec![false; len];
            apply(&self.indices, &mut visited, input);
            Ok(())
        }
    }

    impl<T, const SIZE: usize> PermApply<Vec<T>> for PermS<SIZE> {
        type Output = Result<(), &'static str>;

        fn apply(&self, input: &mut Vec<T>) -> Self::Output {
            self.apply(input.as_mut_slice())
        }
    }
}

fn apply<T>(indices: &[usize], visited: &mut [bool], slice: &mut [T]) {
    unsafe { apply_unsafe(indices, visited, slice.as_mut_ptr()) }
}

unsafe fn apply_unsafe<T>(indices: &[usize], visited: &mut [bool], slice: *mut T) {
    let len = indices.len();

    for idx in 0..len {
        let mut dst = idx;

        if visited[dst] {
            continue;
        }

        loop {
            visited[dst] = true;

            let src = indices[dst];
            if visited[src] {
                break;
            }

            mem::swap(
                slice.add(src).as_mut().unwrap(),
                slice.add(dst).as_mut().unwrap(),
            );
            dst = src;
        }
    }
}