#pragma once

#define KDtreeSize 200000

#define UL unsigned long


struct coordinate
{
	double x = 0;
	double y = 0;
	double z = 0;
	UL index = 0;
};

struct TreeNode
{
	struct coordinate dom_elt;
	UL split = 0;
	struct TreeNode* left = nullptr;
	struct TreeNode* right = nullptr;
};

struct TreeElement
{
	struct coordinate dom_elt;
	int split = 0;
	bool isEmpty = true;
};

void ChooseSplit(coordinate exm_set[], int size, UL &split, coordinate &SplitChoice);

TreeNode* build_kdtree(coordinate exm_set[], int size, TreeNode* T);

double Distance(coordinate a, coordinate b);

void searchNearest(TreeNode * Kd, coordinate target, coordinate &nearestpoint, double & distance);

void searchNearest(TreeElement* treeArray, int size, coordinate target, coordinate &nearestpoint, double & distance);

int getHeight(TreeNode* T);

void TreeToArray(TreeNode* T, TreeElement* treeArray, int index = 0);