#include<iostream>
#include<iomanip>
#include<cmath>
using namespace std;

#define pi 3.14159265

// class complex
class complex
{
public:
        //This class member function set the values of the class members real and imag
        void setvals(double r, double i)
        {
                real=r;
                imag=i;
        }

        //This function get the values (by reference) of the class members real and imag
        void getvals(double &r, double &i)
        {
                r=real;
                i=imag;
        }

private:
        /* The class members real and imag represents the real and imaginary parts
       of a complex number, respectively.*/
        double real;
        double imag;

}; // end of class complex

//**********************************************************************************************
/* function dft receives two parameters x and N. x is the input sequence containing
the discrete-time samples and N is the number of DFT points.  The complex type paramater
xk receives a sequence of N-points frequency samples (this is the DFT of the input sequence*/

void dft(double x[], int N, complex xk[])
{
        double r,i;
       
        for(int k=0;k<N;k++) //k is the index of the N-point frequency sequence
        {
                xk[k].setvals(0,0); //initialize the values of the counters to zero  
               
                for(int n=0;n<N;n++) //n is the index of the discrete-time sequence
                {
                        xk[k].getvals(r,i); // get the values of real and imag

                        /*This is the computation of the real and imaginary parts of the DFT.
                        The class member function setvals is used to update the value of the accumulators
                        contaning the real and imaginary parts of the DFT samples*/

                        xk[k].setvals(r + x[n]*cos(2*pi*k/N*n),i + x[n]*sin(2*pi*k/N*n));      
                } //end inner for-loop

        } //end outer for-loop

}//end dft function

//************************************************************************************************
//Declaration of the main() function
int main()
{
        int size; // The number of DFT samples
        double r,i; // r = real part of the DFT; i = imaginary part of the DFT

cout<<"Enter the desired number of DFT samples: ";
cin>>size;

double *x = new double[size];  //dynamic array x represent the discrete-time samples
complex *xk = new complex[size]; // dynamic array xk represent the DFT samples

cout<<"\nEnter the sequence x[n]: ";
for(int h=0;h<size;h++)
{
        cin>>x[h];
}

//Computation of the DFT of x
dft(x, size, xk);

system("CLS"); //clear screen

cout<<"Discrete Fourier Transform: "<<endl<<endl;

for(int h=0;h<size;h++)
{
        cout.precision(3); // display three (3) decimal places
        xk[h].getvals(r,i); //get the DFT samples values
        cout<<"xk["<<h<<"] = "<<fixed<< r <<" + "<<fixed<< i <<"j"<<endl;  // print the DFT samples
}

cout<<endl;

return 0;
}// end main function