feanor-math 3.5.18

A library for number theory, providing implementations for arithmetic in various rings and algorithms working on them.
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

use std::alloc::{Allocator, Global};

use super::SwappableVectorViewMut;

/// Computes `values_new[i] = values[perm(i)]`.
#[stability::unstable(feature = "enable")]
pub fn permute<V, T, F>(values: V, perm: F)
where
    V: SwappableVectorViewMut<T>,
    F: Fn(usize) -> usize,
{
    permute_using_allocator(values, perm, Global)
}

/// Computes `values_new[i] = values[perm(i)]`.
#[stability::unstable(feature = "enable")]
pub fn permute_using_allocator<V, T, F, A: Allocator>(mut values: V, perm: F, allocator: A)
where
    V: SwappableVectorViewMut<T>,
    F: Fn(usize) -> usize,
{
    let mut swapped_indices = Vec::with_capacity_in(values.len(), allocator);
    swapped_indices.extend((0..values.len()).map(|_| false));
    let mut start = 0;
    while start < values.len() {
        let mut current = start;
        let mut next = perm(current);
        while !swapped_indices[next] {
            swapped_indices[current] = true;
            values.swap(current, next);
            current = next;
            next = perm(current);
        }
        swapped_indices[current] = true;
        start += 1;
    }
}

/// Computes `values_new[perm(i)] = values[i]`.
/// This is the inverse operation to [`permute()`].
#[stability::unstable(feature = "enable")]
pub fn permute_inv<V, T, F>(values: V, perm: F)
where
    V: SwappableVectorViewMut<T>,
    F: Fn(usize) -> usize,
{
    permute_inv_using_allocator(values, perm, Global)
}

/// Computes `values_new[perm(i)] = values[i]`.
/// This is the inverse operation to [`permute()`].
#[stability::unstable(feature = "enable")]
pub fn permute_inv_using_allocator<V, T, F, A: Allocator>(mut values: V, perm: F, allocator: A)
where
    V: SwappableVectorViewMut<T>,
    F: Fn(usize) -> usize,
{
    let mut swapped_indices = Vec::with_capacity_in(values.len(), allocator);
    swapped_indices.extend((0..values.len()).map(|_| false));
    let mut start = 0;
    while start < values.len() {
        let mut current = perm(start);
        swapped_indices[start] = true;
        while !swapped_indices[current] {
            swapped_indices[current] = true;
            values.swap(current, start);
            current = perm(current);
        }
        start += 1;
    }
}

#[test]
fn test_permute() {
    let mut values = [0, 1, 2, 3, 4, 5, 6, 7];
    let permutation = [2, 1, 7, 5, 6, 3, 4, 0];
    permute(&mut values, |i| permutation[i]);
    assert_eq!(values, permutation);
}

#[test]
fn test_permute_inv() {
    let mut values = [2, 1, 7, 5, 6, 3, 4, 0];
    let permutation = [2, 1, 7, 5, 6, 3, 4, 0];
    permute_inv(&mut values, |i| permutation[i]);
    assert_eq!(values, [0, 1, 2, 3, 4, 5, 6, 7]);
}