rusty_perm/
apply.rs

1use crate::common::*;
2
3/// The permutation operator on slice-like types.
4pub trait PermApply<T>
5where
6    T: ?Sized,
7{
8    type Output;
9
10    fn apply(&self, input: &mut T) -> Self::Output;
11}
12
13mod without_std {
14    use super::*;
15    use crate::perm_type::PermS;
16
17    impl<T, const SIZE: usize> PermApply<[T; SIZE]> for PermS<SIZE> {
18        type Output = ();
19
20        fn apply(&self, input: &mut [T; SIZE]) -> Self::Output {
21            let mut visited = [false; SIZE];
22            apply(&self.indices, &mut visited, input);
23        }
24    }
25
26    impl<T, const SIZE: usize> PermApply<[T]> for PermS<SIZE> {
27        type Output = Result<(), &'static str>;
28
29        fn apply(&self, input: &mut [T]) -> Self::Output {
30            if input.len() != SIZE {
31                return Err("input slice length mismatch");
32            }
33            let mut visited = [false; SIZE];
34            apply(&self.indices, &mut visited, input);
35            Ok(())
36        }
37    }
38}
39
40#[cfg(feature = "std")]
41mod with_std {
42    use super::*;
43    use crate::perm_type::{PermD, PermS};
44
45    impl<T, const SIZE: usize> PermApply<[T; SIZE]> for PermD {
46        type Output = Result<(), &'static str>;
47
48        fn apply(&self, input: &mut [T; SIZE]) -> Self::Output {
49            let len = self.indices.len();
50            if len != SIZE {
51                return Err("input slice length mismatch");
52            }
53            let mut visited = vec![false; len];
54            apply(&self.indices, &mut visited, input);
55            Ok(())
56        }
57    }
58
59    impl<T> PermApply<[T]> for PermD {
60        type Output = Result<(), &'static str>;
61
62        fn apply(&self, input: &mut [T]) -> Self::Output {
63            let len = self.indices.len();
64            if len != input.len() {
65                return Err("input slice length mismatch");
66            }
67            let mut visited = vec![false; len];
68            apply(&self.indices, &mut visited, input);
69            Ok(())
70        }
71    }
72
73    impl<T> PermApply<Vec<T>> for PermD {
74        type Output = Result<(), &'static str>;
75
76        fn apply(&self, input: &mut Vec<T>) -> Self::Output {
77            let len = self.indices.len();
78            if len != input.len() {
79                return Err("input slice length mismatch");
80            }
81            let mut visited = vec![false; len];
82            apply(&self.indices, &mut visited, input);
83            Ok(())
84        }
85    }
86
87    impl<T, const SIZE: usize> PermApply<Vec<T>> for PermS<SIZE> {
88        type Output = Result<(), &'static str>;
89
90        fn apply(&self, input: &mut Vec<T>) -> Self::Output {
91            self.apply(input.as_mut_slice())
92        }
93    }
94}
95
96fn apply<T>(indices: &[usize], visited: &mut [bool], slice: &mut [T]) {
97    unsafe { apply_unsafe(indices, visited, slice.as_mut_ptr()) }
98}
99
100unsafe fn apply_unsafe<T>(indices: &[usize], visited: &mut [bool], slice: *mut T) {
101    let len = indices.len();
102
103    for idx in 0..len {
104        let mut dst = idx;
105
106        if visited[dst] {
107            continue;
108        }
109
110        loop {
111            visited[dst] = true;
112
113            let src = indices[dst];
114            if visited[src] {
115                break;
116            }
117
118            mem::swap(
119                slice.add(src).as_mut().unwrap(),
120                slice.add(dst).as_mut().unwrap(),
121            );
122            dst = src;
123        }
124    }
125}
rusty_perm/apply.rs

rusty_perm/
apply.rs
