#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()
{
    uint64_t total_paths=0;
    for(int ix=1;ix<32;ix++)
    {
        for(int iy=1;iy<32;iy++)
        {
            std::vector<std::vector<int>> xy_bresenham_vec=bresenham(0,0,ix,iy);
            std::vector<int> path_xy= path_index(xy_bresenham_vec)[0];
            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();
            uint64_t n_paths=pow(2,size_dx_eq_dy);
            total_paths+=n_paths;
        }

    }
    cout<<"total paths "<<total_paths<<endl;
    /* 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; */
    /* for (int num:path_xy) cout<<num<<" "<<endl; */
        /* 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;
}