#include <cstdint>
#include <cmath>
#include <iostream>
#include <vector>
#include <stdio.h>
using std::vector;
using std::cout;
using std::endl;

std::vector<std::vector<int>> bresenham(int x0,int y0,int x1,int y1)
{
    std::vector<std::vector<int>> v;
    std::vector<int> x_values;
    std::vector<int> y_values;
    int dx=x1-x0;
    int dy=y1-y0;
    int swap_flag=0;
    if (dy>dx){
        int c=x1;
        x1=y1;
        y1=c;

        int d=x0;
        x0=y0;
        y0=d;
    dx=x1-x0;
    dy=y1-y0;
    swap_flag=1;
    }
    int p=2*dy-dx;
    int x=x0;
    int y=y0;
    x_values.push_back(x);
    y_values.push_back(y);
    int i=0;
    do {
        if (p<0) {
            x+=1;
            p+=2*dy;
        }
        else{
            x+=1;
            y+=1;
            p+=2*(dy-dx);
        }
        x_values.push_back(x);
        y_values.push_back(y);
        /* cout<<x<<" "<<y<<std::endl; */
        i+=1;
    } while (i<dx);
    if(swap_flag==1){
    v.push_back(y_values);
    v.push_back(x_values);
    }
    else{
    v.push_back(x_values);
    v.push_back(y_values);
    }
    return v;
}

std::vector<std::vector<int>> path_index(std::vector<std::vector<int>> xy_bresenham_vec)
{
    std::vector<std::vector<int>> path_vec;
    std::vector<int> path_temp;
    std::vector<int> index; //index where dx=dy
    // 0 means step in x, 1 means step in y, 2 means step in z
    //first we shall find the number of points where delta_x=delta_y, and the number of path shall be 2^number(where delta_x=delta_y) 
    for (int j=0;j<xy_bresenham_vec[0].size()-1;j++)
    {
        int delta_x=xy_bresenham_vec[0][j+1]-xy_bresenham_vec[0][j];
        int delta_y=xy_bresenham_vec[1][j+1]-xy_bresenham_vec[1][j];
        if(delta_x==1 and delta_y==0)
        {
            path_temp.push_back(0);
        }
        else if(delta_x==0 and delta_y==1)
        {
            path_temp.push_back(1);
        }
        else if(delta_x==1 and delta_y==1)
        {
            path_temp.push_back(0);
            path_temp.push_back(1);
            index.push_back(j);
        }
    }
    path_vec.push_back(path_temp);
    path_vec.push_back(index);
return path_vec;
}

int invert(int num)
{
    int result;
    if(num==0)
    {
        result=1;
    }
    else if(num==1)
    {
        result=0;
    }
    return result;
}

std::vector<int> int_to_binary(int num,int size)
{
    //we size=size binary vector
    std::vector<int> binary_vec;
    std::vector<int> binary_vec_rev;
    int result=num;
    while(result!=1 && result!=0)
    {
        binary_vec.push_back(result%2);
        result/=2;
    }
    if(result==1 or result==0) binary_vec.push_back(result);
    int present_size=binary_vec.size();
    if (present_size<size) 
    {
        for(int i=0;i<size-present_size;i++)
        {
            binary_vec.push_back(0);
        }
    }
    int correct_size=binary_vec.size();
    for(int i=0;i<size;i++)
    {
        binary_vec_rev.push_back(binary_vec[size-1-i]);
    }
    return binary_vec_rev;
}

__global__ void print2DVec(int *d_path,int rows,int columns)
{
    for(int i=0;i<rows;i++)
   {
       printf("printing on gpu: path %d: ",i+1);
        for(int j=0;j<columns;j++)
       {
         //printf("%d ",*(d_path+(i*columns)+j));
           printf("%d ",d_path[i*columns+j]);
       }
        printf("\n");

    }
   //    int index=threadIdx.x+blockIdx.x*blockDim.x;
   //    if(index<rows*columns)
   //    {
   //     printf("%d ",d_path[index]);
   //    }


}


int main()
{
    std::vector<std::vector<int>> xy_bresenham_vec=bresenham(0,0,8,8);
    std::vector<int> x_vec=xy_bresenham_vec[0];
    std::vector<int> y_vec=xy_bresenham_vec[1];
    cout<<"number of rows are"<<xy_bresenham_vec.size()<<endl;
    cout<<"numbers of column are"<<xy_bresenham_vec[1].size()<<endl;
    /* for(int i=0;i<xy_bresenham_vec.size();i++) */
    /* { */
    /*     for(int j=0;j<xy_bresenham_vec[i].size();j++) */
    /*     { */
    /*         std::cout<<xy_bresenham_vec[i][j]<<" "; */
    /*     } */
    /*     std::cout<<std::endl; */
    /* } */
    cout<<"trying different way\n";
    cout<<"x values: ";
    for(int i=0;i<x_vec.size();i++)
    {
        cout<<x_vec[i]<<" ";
    }
    cout<<endl;
    cout<<"y values: ";
    for(int i=0;i<y_vec.size();i++)
    {
        cout<<y_vec[i]<<" ";
    }
    cout<<endl;
    std::vector<int> path_xy= path_index(xy_bresenham_vec)[0];
    /* for (int num:path_xy) cout<<num<<" "<<endl; */
    std::vector<std::vector<int>> final_paths_vec;
    std::vector<int> index_xy = path_index(xy_bresenham_vec)[1];
    int size_dx_eq_dy= index_xy.size();
    int n_paths=pow(2,size_dx_eq_dy);
    cout<<"number of paths shall be : "<<n_paths<<endl;
    //we shall find the binary eqvivalent of the 2^size_dx_eq_dy and replace the corresponding value by the binary equivalent value at that index
    //construct a function which returns the binary equivalent array of any integer
    for (int ip=0;ip<n_paths;ip++)
    {
        std::vector<int> binary_rep = int_to_binary(ip,size_dx_eq_dy);
        std::vector<int> path_xy_duplicate=path_xy;
        for(int iindex=0;iindex<size_dx_eq_dy;iindex++)
        {
            int index=iindex+index_xy[iindex];
            path_xy_duplicate[index]=binary_rep[iindex];
            path_xy_duplicate[index+1]=invert(binary_rep[iindex]);
        }
        final_paths_vec.push_back(path_xy_duplicate);
        cout<<"Path "<<ip+1<<" : ";
        for(int i=0;i<path_xy_duplicate.size();i++)
        {
            cout<<" "<<path_xy_duplicate[i]<<" ";
        }
        cout<<endl;
    }

//let us convert this 2d array to 1d, 
    int rows=n_paths;
    int columns=final_paths_vec[0].size();
    int *host_final_paths=new int[rows*columns];
    for(int i=0;i<rows;i++)
    {
        for(int j=0;j<columns;j++)
        {
            host_final_paths[j+i*columns]=final_paths_vec[i][j];
        }
    }
    //allocating memory for paths on gpu
    int* d_path; //declaring pointer to pointer
    cudaMalloc((void**)&d_path,rows*columns*sizeof(int));
    cudaMemcpy(d_path,host_final_paths,columns*rows*sizeof(int),cudaMemcpyHostToDevice);
    print2DVec<<<1,1>>>(d_path, rows, columns);
    cudaDeviceSynchronize();
    cudaFree(d_path);

return 0;
}