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;
        }
    }
}