feanor_math/seq/
permute.rs

1use std::alloc::{Allocator, Global};
2
3use super::SwappableVectorViewMut;
4
5///
6/// Computes `values_new[i] = values[perm(i)]`.
7/// 
8#[stability::unstable(feature = "enable")]
9pub fn permute<V, T, F>(values: V, perm: F)
10    where V: SwappableVectorViewMut<T>, F: Fn(usize) -> usize
11{
12    permute_using_allocator(values, perm, Global)
13}
14
15///
16/// Computes `values_new[i] = values[perm(i)]`.
17/// 
18#[stability::unstable(feature = "enable")]
19pub fn permute_using_allocator<V, T, F, A: Allocator>(mut values: V, perm: F, allocator: A)
20    where V: SwappableVectorViewMut<T>, 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///
40/// Computes `values_new[perm(i)] = values[i]`.
41/// This is the inverse operation to [`permute()`].
42/// 
43#[stability::unstable(feature = "enable")]
44pub fn permute_inv<V, T, F>(values: V, perm: F)
45    where V: SwappableVectorViewMut<T>, F: Fn(usize) -> usize
46{
47    permute_inv_using_allocator(values, perm, Global)
48}
49
50///
51/// Computes `values_new[perm(i)] = values[i]`.
52/// This is the inverse operation to [`permute()`].
53/// 
54#[stability::unstable(feature = "enable")]
55pub fn permute_inv_using_allocator<V, T, F, A: Allocator>(mut values: V, perm: F, allocator: A)
56    where V: SwappableVectorViewMut<T>, 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
