#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>
#include <stdbool.h>
#include "vptree.h"
#define INT_MAX 2147483647

#ifndef VPTREE_H_INCLUDED
#define VPTREE_H_INCLUDED



struct vptree{

    double *points;
    int n; // number of points
    int d; //dimensions
    struct vptree *innerTree;
    struct vptree *outerTree;
    double median;
    double * cooVP; //coordinates of vantage point
    int indx;

    int *indexArray;//THELEI DOULEIA


};
//DATASET STRUCT
struct helpStruct{
double *dataSet;
int dataLength;
};



int isFather=5;
struct helpStruct index;




//DATASET

typedef struct vptree vptree;
//PRWTOTUPA SUNARTHSEWN
 vptree * buildvp(double * X,int n,int d);
 vptree * getInner( vptree * T);
 vptree * getOuter( vptree * T);

double getMD( vptree *T);
double * getVP( vptree *T);

int getIDX( vptree *T);

int partition(double arr[], int l, int r);
double kthSmallest(double arr[], int l, int r, int k);
//PRWTOTUPA SUNARTHSEWN
#endif // VPTREE_H_INCLUDED









int main()
{
    int n=5;//data
    int d=3;//dimensions
    int i,j;

    double  * dataArr=(double*)malloc(n*d*sizeof(double));

    for (i=0;i<n;i++){

            for(j=0;j<d;j++){
                *(dataArr+i*d+j)=rand()%100; //na to ftiaksw na epistrefei random double numbers
                printf("%f ---",*(dataArr+i*d+j));
            }printf("\n");
    }
 vptree *one =( vptree*)malloc(100*sizeof( vptree));
one=buildvp(dataArr,n,d);

//printf(" --%d root index %f ",one->innerTree->index,one->innerTree->cooVP[2] );


}



 vptree * buildvp(double *X,int n,int d){
     if(isFather==5){
        index.dataSet=X;
        index.dataLength=n;
        isFather=0;
        printf("\nGIA TON ISFATHER");
     }
    vptree * node=( vptree*)malloc(sizeof( vptree));

    node->d=d;
    node->n=n;

    node->points=X;

    node->cooVP=getVP(node);

    node->median=getMD(node);

    node->innerTree=(vptree*)malloc(sizeof(vptree));
    node->innerTree=getInner(node);
    if(node->innerTree!=NULL)node->innerTree=buildvp(node->innerTree->points,node->innerTree->n,node->innerTree->d);

    node->outerTree=(vptree*)malloc(sizeof(vptree));
    node->outerTree=getOuter(node);
    if(node->outerTree!=NULL)node->outerTree=buildvp(node->outerTree->points,node->outerTree->n,node->outerTree->d);

    node->indx=getIDX(node);//den to exw valei akoma sth swsth seira

    return node;

};

 vptree * getInner( vptree * T){

   if(T->n>1){
    vptree* inNode=( vptree*)malloc(sizeof( vptree));

   double coo[T->n][T->d];
   int l;
   int k;
   for(l=0;l<(T->n);l++){
        for(k=0;k<T->d;k++){
            coo[l][k]=T->points[(T->d)*l+k];//einai swsto??? EINAI
    }}
    double* distance=(double*)malloc(((T->n)-1)*sizeof(double));
    int i;
    int j;
    double sqrtValue;
    for(i=0;i<(T->n)-1;i++){
        sqrtValue=0;
            for(j=0;j<(T->d);j++){
                sqrtValue+=(coo[i][j]-coo[(T->n)-1][j])*(coo[i][j]-coo[(T->n)-1][j]);

            }
        distance[i]=sqrt(sqrtValue);}

        //------------------------------PANW GINETAI O UPOLOGISMOS DISTANCE


        int w,h;
        int z=0;
        int indexCounter=0;
        for(w=0;w<(T->n)-1;w++){
                if(distance[w]<T->median)indexCounter++;
          }


        inNode->points=(double*)malloc((indexCounter*T->d)*sizeof(double));
        for(w=0;w<(T->n)-1;w++){
                if(distance[w]<T->median){

                    for(h=0;h<T->d;h++){
                  inNode->points[(T->d)*z+h]=coo[w][h];}//vazei tis katallhles suntetagmenes ston points tou inner
                  z++;
               }
          }
        inNode->n=z;
        inNode->d=T->d;

return inNode;
   }
   else //printf("\n  ---->  ",T->index, T->cooVP[0]);
return NULL;
};
 vptree * getOuter( vptree * T){
    if(T->n>1){
    vptree* outNode=( vptree*)malloc(sizeof( vptree));

   double coo[T->n][T->d];
   int l;
   int k;
   for(l=0;l<(T->n);l++){
        for(k=0;k<T->d;k++){
            coo[l][k]=T->points[(T->d)*l+k];//einai swsto??? EINAI
    }}
    double* distance=(double*)malloc(((T->n)-1)*sizeof(double));
    int i;
    int j;
    double sqrtValue;
    for(i=0;i<(T->n)-1;i++){
        sqrtValue=0;
            for(j=0;j<(T->d);j++){
                sqrtValue+=(coo[i][j]-coo[(T->n)-1][j])*(coo[i][j]-coo[(T->n)-1][j]);

            }
        distance[i]=sqrt(sqrtValue);}

        //------------------------------PANW GINETAI O UPOLOGISMOS DISTANCE


        int w,h;
        int z=0;
        int indexCounter=0;
        for(w=0;w<(T->n)-1;w++){
                if(distance[w]>=T->median)indexCounter++;
          }


        outNode->points=(double*)malloc((indexCounter*T->d)*sizeof(double));
        for(w=0;w<(T->n)-1;w++){
                if(distance[w]>=T->median){

                    for(h=0;h<T->d;h++){
                  outNode->points[(T->d)*z+h]=coo[w][h];}//vazei tis katallhles suntetagmenes ston points tou inner
                  z++;
               }
          }
        outNode->n=z;
        outNode->d=T->d;

return outNode;
   }
   else //printf("\n  ---->  ",T->index, T->cooVP[0]);
return NULL;

};

double getMD( vptree *T){
    double* distance=(double*)malloc(((T->n)-1)*sizeof(double));

    double coo[T->n][T->d]; //periexei oles tis suntetagmenes olwn twn stoixeiwn
    double sqrtValue=0;

    int i;
    int k;
    int j;
    int l;

    for(l=0;l<(T->n);l++){
        for(k=0;k<T->d;k++){
            coo[l][k]=T->points[(T->d)*l+k];//einai swsto????
    }}

    for(i=0;i<(T->n)-1;i++){
        sqrtValue=0;
            for(j=0;j<(T->d);j++){
                sqrtValue+=(coo[i][j]-coo[(T->n)-1][j])*(coo[i][j]-coo[(T->n)-1][j]);

            }
        distance[i]=sqrt(sqrtValue);}

return kthSmallest(distance,0,(T->n)-2,((T->n)-1)/2);
};

double * getVP( vptree *T){//epistrefei gia to vptree T to vantage point pou tha xrhsimopoihthei
    int j; // metavlhtes gia na prospelasw thn for

    int n=T->n;//krataw diastaseis tou pinaka twn point tou T gia na paiksw sth for apo katv
    int d=T->d;//ta dia me panw

    double* arrayVP=(double*)malloc(d*sizeof(double));// o vector poy tha epistrafei kai periexei coordinates tou VP

        for(j=0;j<d;j++){
            arrayVP[j]=(*(T->points+(n-1)*d+j));
        }

return arrayVP;
};

int getIDX( vptree *T){//nomizw me afton ton tropo epistrefw amesws ton deikth tou teleftaiou stoixeiou
    int k;
    int l;

    vptree* outNode=( vptree*)malloc(sizeof( vptree));

   double coo[index.dataLength][T->d];

   for(l=0;l<index.dataLength;l++){
        for(k=0;k<T->d;k++){
            coo[l][k]=index.dataSet[(T->d)*l+k];//einai swsto??? EINAI
    }}
    double* distance=(double*)malloc((index.dataLength)*sizeof(double));
    int i;
    int j,m;
    double sqrtValue;
    for(i=0;i<index.dataLength;i++){
        sqrtValue=0;
            for(j=0;j<(T->d);j++){
                sqrtValue+=(coo[i][j]-T->cooVP[j])*(coo[i][j]-T->cooVP[j]);

            }
        distance[i]=sqrt(sqrtValue);

        }


    for(m=0;m<index.dataLength;m++){if(distance[m]==0)return m;}

    printf("h index exei themaaaaaaa");
    return 0;

};

int partition(double arr[], int l, int r)
{   double temp;
    double x = arr[r];
    int i = l;
    int j;
    for (j = l; j <= r - 1; j++) {
        if (arr[j] <= x) {
            temp=arr[i];
            arr[i]=arr[j];
            arr[j]=temp;

            i++;
        }
    }
    temp=arr[i];
    arr[i]=arr[r];
    arr[r]=temp;

    return i;
};

double kthSmallest(double arr[], int l, int r, int k)
{
    if (k > 0 && k <= r - l + 1) {
        int index = partition(arr, l, r);
        if (index - l == k - 1)
            return arr[index];
        if (index - l > k - 1)
            return kthSmallest(arr, l, index - 1, k);

        return kthSmallest(arr, index + 1, r,
                            k - index + l - 1);
    }
    return INT_MAX;
};

//Ara kathe vptree stoixeio tha periexei mesa to VP tou (dhladh tha mas leei poio VP einai sa node) to index tou node aftou ston megalo pinaka kai to aristero kai deksi tree