"""Helpers for pft.dc: Cooley-Tukey FFT as a PDC.

   Loaded via:  ./pydc dcsrc/pft.dc dcsrc/pft_lib.py

   vector(e):      wrap e in a vector
   rotor(b,N):     the twiddle factor of FFT
   shuffled(N):    a random permutation of [0..2**N - 1] - the test input.
   expected_fft(V) N^3 time non-parallel implementation"""

import cmath, random

pi = cmath.pi

def vector(e):
    return [e]

def rotor(b,angle):
    return cmath.exp(-1j * b * angle)

def shuffled(N, seed=None):
    if seed is not None:
        random.seed(seed)
    arr = list(range(2 ** N))
    random.shuffle(arr)
    return arr

# Discrete (unoptimized) Fourier Transform
#
# Time complexity: O(N^2)
def expected_fft(arr):
    N = len(arr)
    return [sum(arr[n] * cmath.exp(-2j*cmath.pi*k*n/N)
              for n in range(N))
                for k in range(N)]