feanor_math/seq/
permute.rs

1use std::alloc::{Allocator, Global};
2
3use super::SwappableVectorViewMut;
4
5/// Computes `values_new[i] = values[perm(i)]`.
6#[stability::unstable(feature = "enable")]
7pub fn permute<V, T, F>(values: V, perm: F)
8where
9    V: SwappableVectorViewMut<T>,
10    F: Fn(usize) -> usize,
11{
12    permute_using_allocator(values, perm, Global)
13}
14
15/// Computes `values_new[i] = values[perm(i)]`.
16#[stability::unstable(feature = "enable")]
17pub fn permute_using_allocator<V, T, F, A: Allocator>(mut values: V, perm: F, allocator: A)
18where
19    V: SwappableVectorViewMut<T>,
20    F: Fn(usize) -> usize,
21{
22    let mut swapped_indices = Vec::with_capacity_in(values.len(), allocator);
23    swapped_indices.extend((0..values.len()).map(|_| false));
24    let mut start = 0;
25    while start < values.len() {
26        let mut current = start;
27        let mut next = perm(current);
28        while !swapped_indices[next] {
29            swapped_indices[current] = true;
30            values.swap(current, next);
31            current = next;
32            next = perm(current);
33        }
34        swapped_indices[current] = true;
35        start += 1;
36    }
37}
38
39/// Computes `values_new[perm(i)] = values[i]`.
40/// This is the inverse operation to [`permute()`].
41#[stability::unstable(feature = "enable")]
42pub fn permute_inv<V, T, F>(values: V, perm: F)
43where
44    V: SwappableVectorViewMut<T>,
45    F: Fn(usize) -> usize,
46{
47    permute_inv_using_allocator(values, perm, Global)
48}
49
50/// Computes `values_new[perm(i)] = values[i]`.
51/// This is the inverse operation to [`permute()`].
52#[stability::unstable(feature = "enable")]
53pub fn permute_inv_using_allocator<V, T, F, A: Allocator>(mut values: V, perm: F, allocator: A)
54where
55    V: SwappableVectorViewMut<T>,
56    F: Fn(usize) -> usize,
57{
58    let mut swapped_indices = Vec::with_capacity_in(values.len(), allocator);
59    swapped_indices.extend((0..values.len()).map(|_| false));
60    let mut start = 0;
61    while start < values.len() {
62        let mut current = perm(start);
63        swapped_indices[start] = true;
64        while !swapped_indices[current] {
65            swapped_indices[current] = true;
66            values.swap(current, start);
67            current = perm(current);
68        }
69        start += 1;
70    }
71}
72
73#[test]
74fn test_permute() {
75    let mut values = [0, 1, 2, 3, 4, 5, 6, 7];
76    let permutation = [2, 1, 7, 5, 6, 3, 4, 0];
77    permute(&mut values, |i| permutation[i]);
78    assert_eq!(values, permutation);
79}
80
81#[test]
82fn test_permute_inv() {
83    let mut values = [2, 1, 7, 5, 6, 3, 4, 0];
84    let permutation = [2, 1, 7, 5, 6, 3, 4, 0];
85    permute_inv(&mut values, |i| permutation[i]);
86    assert_eq!(values, [0, 1, 2, 3, 4, 5, 6, 7]);
87}
feanor_math/seq/permute.rs

feanor_math/seq/
permute.rs
