from butterfly_processor import ButterflyProcessor
from twiddle_factors import TwiddleFactors
from math import cos, sin, pi, log
from index_transform_decimation_in_frequency import IndexTransformDecimationInFrequency

class FFT8DecimationInFrequency(object):
	"""docstring for FFT8DecimationInFrequency"""
	def __init__(self, N, scale):
		super(FFT8DecimationInFrequency, self).__init__()
		self.N = N
		self.butterflyProcessor = ButterflyProcessor(scale)
		twiddleFactors = TwiddleFactors(N)
		self.w = twiddleFactors.build_twiddle_factors()
		self.indexTransformDecimationInFrequency = IndexTransformDecimationInFrequency(N)

	def fft(self, x):
		# all stages
		fft_output = x[:]
		nb_stages = int( log(len(x), 2) )
		print 'size of input sequence = ', len(x), ', nb stages = ', nb_stages
		for k in range(nb_stages):
			stage = k + 1
			step = 2**(nb_stages - stage)
			nb_groups = 2**(stage-1)
			for twiddle in range(step):
				for group in range(nb_groups):
					res = self.butterflyProcessor.butterfly(
						fft_output[twiddle+group*step*2].real, 
						fft_output[twiddle+group*step*2].imag, 
						fft_output[twiddle+group*step*2+step].real, 
						fft_output[twiddle+group*step*2+step].imag,
						self.w[twiddle*nb_groups].real,
						self.w[twiddle*nb_groups].real + self.w[twiddle*nb_groups].imag,
						self.w[twiddle*nb_groups].real - self.w[twiddle*nb_groups].imag
						)
					fft_output[twiddle+group*step*2] = res[0]
					fft_output[twiddle+group*step*2+step] = res[1]
		# arrange sequence
		self.indexTransformDecimationInFrequency.reverse_order(fft_output)
		return fft_output

	def dft(self, x):
		N = len(x)
		fft_output = x[:]
		for k in range(N):
			val = 0
			for n in range(N):
				teta = - 2 * pi * n * k / self.N
				val = val + x[n] * ( cos(teta) + 1j * sin(teta) )
			fft_output[k] = val
		return fft_output