#include <iostream>
#include<string.h>
#include<math.h>
#include <iomanip>

using namespace std;

const double pi = 3.14159265;

struct imaginary
{
    float real;
    float img;
} ;


void  get_magnitude(imaginary arr[],int N,double mag[])
{
    for(int i=0;i<N;i++)
    {
        mag[i]=pow(arr[i].real,2);
        mag[i]+=pow(arr[i].img,2);
        mag[i]=sqrt(mag[i]);
    }

}


void get_phase(imaginary arr[],int N,double phs[])
{
    for(int i=0;i<N;i++)
    {
        if (arr[i].real==0)
        {
            phs[i]=90;
        }
        else
        {
        phs[i]= (((atan((arr[i].img)/(arr[i].real)))*180)/pi);
        }
    }

}



imaginary* fft(imaginary arr[],int n)
{

    imaginary F1[n/2];
    imaginary F2[n/2];
    imaginary Wn[n/2];
    imaginary *p1;
    imaginary *p2;
    if(n==1)
    {
        return arr;
    }
    if(n>1)
    {
    for(int i=0;i<n/2;i++)
    {
        F1[i]=arr[2*i];
        F2[i]=arr[2*i+1];
    }

    n=n/2;
    p1=fft(F1,n);
    p2=fft(F2,n);
    for(int i=0;i<n;i++)
    {
        F1[i]=p1[i];
        F2[i]=p2[i];
    }
    for(int i=0;i<n;i++)
    {

        Wn[i].real=cos(((2*pi)*i)/(n*2));
        Wn[i].img=-1*(sin(((2*pi)*i)/(n*2)));
        arr[i].real=F1[i].real+((Wn[i].real)*(F2[i].real)-(Wn[i].img)*(F2[i].img));
        arr[i].img=F1[i].img+((Wn[i].real)*(F2[i].img)+(Wn[i].img)*(F2[i].real));

        arr[i+n].real=F1[i].real-((Wn[i].real)*(F2[i].real)-(Wn[i].img)*(F2[i].img));
        arr[i+n].img=F1[i].img-((Wn[i].real)*(F2[i].img)+(Wn[i].img)*(F2[i].real));

    }
      return arr;
    }
}



int main()
{


    int N = 0 ;

    cout<<endl;
    cout << "Enter the number of points 'N' : ";
    cin >> N ;
    int T=N;
    imaginary X[N];
    imaginary out[N]={0};
    imaginary *o;
    cout<<endl;
    cout << "Enter the size of X(N) = ";


    int s;
    cin >> s;
    cout<<endl;
    cout << "Enter the discrete signal ( separated by spaces ) X(N) = ";
    if (s < N && s > 0 && N > 0)
    {
        for ( int i = s; i < N; i++ )
        {
             X[i].real = 0;
             X[i].img = 0;
        }
        for (int i = 0; i < s; i ++)
        {
            cin >> X[i].real;
            X[i].img = 0;
        }
    }
    if ( s == N  && s > 0 && N > 0 )
    {
      for (int i = 0; i < N; i ++)
        {
            cin >> X[i].real;
            X[i].img = 0;
        }
    }


    cout<<endl;

    for(int i=0 ; i< N; i++)
    {
        cout << fixed << setprecision(2) <<X[i].real<<" + J ";
       if(i+1!=N)
       {
           cout << fixed << setprecision(2) <<X[i].img<<" , ";
       }
       else
        {
        cout << fixed << setprecision(2) <<X[i].img;
        }
    }
    cout<<" } \n";


        cout <<  endl << "   ******** SOLUTION ********   " << endl;


o=fft(X,N);

    for(int i=0;i<N;i++)
    {
        out[i].real=o[i].real;
        out[i].img=o[i].img;
    }
    cout<<" X[K] = { ";
    for(int i=0 ; i< N; i++)
    {
        cout << fixed << setprecision(2) <<out[i].real<<" + J ";
       if(i+1!=N)
       {
           cout << fixed << setprecision(2) <<out[i].img<<" , ";
       }
       else
        {
        cout << fixed << setprecision(2) <<out[i].img;
        }
    }
    cout<<" } \n";

    double mag[N];
    get_magnitude(out,N,mag);
    cout<<endl;
    cout<<" magnitude = { ";

        for(int i=0 ; i< N; i++)
    {
        if(i+1!=N)
            {
            cout <<mag[i]<<" , ";
            }
        else
        {
             cout <<mag[i] ;
        }
    }
    cout<<" } \n";

    cout<<endl;
    cout<<" phase = {";
    double phs[N];
    get_phase(out,N,phs);
    for(int i=0 ; i< N; i++)
    {
        if(i+1!=N)
            {
            cout <<phs[i]<<" , ";
            }
        else
        {
             cout <<phs[i] ;
        }
    }
       cout<<" } \n";

}