Algorithms, KDTree implement, Plz help me implement the following code, Also the code need to read a CSV file. For example, there are 7 columns of items in csv file, create a struct to store.

1)Construct a fairly balanced kdtree using the cities file. You need to modify construct() such that for every level it first sorts the cities vector in the x and y coordinate such that the next point your add to the tree is almost in the middle of existing vector of cities points for the coordinate. Probably a good way is to make 2 copies of the cities locations and then sort once in x and the other in y. Then each time pick the middle point corresponding to the cutting coordinates. Make sure to delete that point from both vectors after each entering it in the tree. 2) Implement Range Query. It should take Lower left and upper right max point of a rectangle and returns a vector of all cities falling inside the rectangle. 3) Implement Nearest Neighbor search and was explained in class.It takes a point as an input and reports the nearest city to that point the map.

#include #include #include #include #include #include #include

using namespace std;

namespace KDTree { using CuttimgDim = char; struct Point { int p[2]; Point(int x=0, int y=0) :p{x,y} {} bool operator==(const Point &rp) const { return (p[0] == rp[0] && p[1] == rp[1]); } int operator[](CuttimgDim c) const { assert(c < 2 && c >= 0); return p[c]; } static const Point* min(const Point* p1, const Point* p2, CuttimgDim c) { if (p1 && p2) { if ((*p1)[c] < (*p2)[c]) return p1; return p2; } if (!p1) return p2; return p1; } static const Point* max(const Point* p1, const Point* p2, CuttimgDim c) { if (p1 && p2) { if ((*p1)[c] < (*p2)[c]) return p2; return p1; } if (!p1) return p2; return p1; } };

struct kdNode { kdNode(Point p=Point()) :data(p), left(nullptr), right(nullptr) {} Point data; kdNode *left, *right; };

class kd_tree { public: vector mNodesuffer; kdNode * root; size_t bufferIndex = 0; //index to currently available kdNode for use in the tree. void construt(vector const& pnts) { mNodesuffer.reserve(pnts.size()); mNodesuffer.emplace_back(pnts[0]); root = &mNodesuffer[bufferIndex++]; for (int i = 1; i < pnts.size(); ++i) { insert(pnts[i], root, 0); } }

kdNode *insert(Point const& p, kdNode *node, CuttimgDim c) { CuttimgDim nextCD = 1 - c; if (node == nullptr) { mNodesuffer.emplace_back(p); return &mNodesuffer[bufferIndex++]; }

if (p == node->data) { cerr << "ERROR!! Cannot insert duplicate point!! "; return nullptr; }

if (p[c] < node->data[c]) node->left = insert(p, node->left, nextCD); else node->right = insert(p, node->right, nextCD); return node; }

const Point *findMin(kdNode *node, CuttimgDim minCD, CuttimgDim cdNode) const { if (node == nullptr) return nullptr; if (minCD == cdNode) { if(node->left == nullptr) return &node->data; else return findMin(node->left, minCD, 1 - cdNode); }

const Point* minl = findMin(node->left, minCD, 1 - cdNode); const Point* minr = findMin(node->right, minCD, 1 - cdNode);

// return min of minl, minr, and data on minCD coordinate: const Point* minm = Point::min(minl, minr, minCD); return Point::min(minm, &node->data, minCD); }

const Point *findMax(kdNode *node, CuttimgDim maxCD, CuttimgDim cdNode) const { if (node == nullptr) return nullptr; if (maxCD == cdNode) { if (node->right == nullptr) return &node->data; else return findMax(node->right, maxCD, 1 - cdNode); }

const Point* maxl = findMax(node->left, maxCD, 1 - cdNode); const Point* maxr = findMax(node->right, maxCD, 1 - cdNode);

// return max of maxl, maxr, and data on maxCD coordinate: const Point* maxm = Point::max(maxl, maxr, maxCD); return Point::max(maxm, &node->data, maxCD); }

void PrintRange(kdNode *node, CuttimgDim c, Point min, Point max) { return; }

void PrettyPrintKDTree() {}

};

}

using namespace KDTree;

int main() { vector pnts = { {2,3}, {5, 9}, {2,-3 }, { -5, 9 }, {2,33 }, { 51, -9 }, {12,13}, {65, 9}, {22,53}, {5, 19} };

kd_tree theTree; theTree.construt(pnts); const KDTree::Point *minx = theTree.findMin(theTree.root, 0, 0); if (minx == nullptr) cout << "ERROR!! Your findMin is wrong!! "; else cout << "Min point in x is (" << minx->p[0] << ", " << minx->p[1] << ") ";

const KDTree::Point *miny = theTree.findMin(theTree.root, 1, 0); if (miny == nullptr) cout << "ERROR!! Your findMin is wrong!! "; else cout << "Min point in y is (" << miny->p[0] << ", " << miny->p[1] << ") ";

const KDTree::Point *maxx = theTree.findMax(theTree.root, 0, 0); if (maxx == nullptr) cout << "ERROR!! Your findMax is wrong!! "; else cout << "Max point in x is (" << maxx->p[0] << ", " << maxx->p[1] << ") ";

const KDTree::Point *maxy = theTree.findMax(theTree.root, 1, 0); if (maxy == nullptr) cout << "ERROR!! Your findMax is wrong!! "; else cout << "Max point in y is (" << maxy->p[0] << ", " << maxy->p[1] << ") ";

return 0; }