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

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