Enum RotateCache 

enum RotateCache {}

Implementations

impl RotateCache

fn ensure(n: usize)

Examples found in repository

crates/competitive/src/math/fast_fourier_transform.rs (line 132)

pub fn fft(a: &mut [Complex<f64>]) {
    let n = a.len();
    RotateCache::ensure(n / 2);
    RotateCache::with(|cache| {
        let mut v = n / 2;
        while v > 0 {
            for (a, wj) in a.chunks_exact_mut(v << 1).zip(cache) {
                let (l, r) = a.split_at_mut(v);
                for (x, y) in l.iter_mut().zip(r) {
                    let ajv = wj * *y;
                    *y = *x - ajv;
                    *x += ajv;
                }
            }
            v >>= 1;
        }
    });
}

pub fn ifft(a: &mut [Complex<f64>]) {
    let n = a.len();
    RotateCache::ensure(n / 2);
    RotateCache::with(|cache| {
        let mut v = 1;
        while v < n {
            for (a, wj) in a
                .chunks_exact_mut(v << 1)
                .zip(cache.iter().map(|wj| wj.conjugate()))
            {
                let (l, r) = a.split_at_mut(v);
                for (x, y) in l.iter_mut().zip(r) {
                    let ajv = *x - *y;
                    *x += *y;
                    *y = wj * ajv;
                }
            }
            v <<= 1;
        }
    });
}

Trait Implementations

impl AssociatedValue for RotateCache

type T = Vec<Complex<f64>>

Type of value.

unsafe fn __local_key() -> &'static LocalKey<Cell<Self::T>>

fn get() -> Self::T

fn set(x: Self::T)

fn replace(x: Self::T) -> Self::T

fn with<F, R>(f: F) -> R

where F: FnOnce(&Self::T) -> R,

fn modify<F, R>(f: F) -> R

where F: FnOnce(&mut Self::T) -> R,