Instructions: In this lab implement these basics of a QuadTree.
Implement the following class:
#ifndef QUADTREE_H__
#define QUADTREE_H__
#include <stdlib.h
#include <vector
#include <list
#include <set #include <queue
class QuadTree { private:
/* Class to begin filling out...*/ public:
/* Initialize an empty quadtree. */
QuadTree(float width, float height);
/* add a point to the quadtree. */ bool add(float x, float y);
/* remove a point from the QuadTree.
* Remember to remove empty QuadTree nodes, or your tree will * use up too much memory when doing the add/remove test!
*/ bool remove(float x, float y);
/* returns if the quad tree has a point (x, y) */ bool contains(float x, float y);
/* return the number of points in the box (sx, sy) - (ex, ey) * You may assume that sx < ex and sy < ey!
*/ int countInRange(float sx, float sy, float ex, float ey);
void print();
};
#include "quadtree.cpp"
#endif
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
Write some test cases:
Create some test cases, using cxxtestgen, that you believe would cover all aspects of your code.
Memory Management:
Now that are using new, we must ensure that there is a corresponding delete to free the memory. Ensure there are no memory leaks in your code! Please run Valgrind on your tests to ensure no memory leaks!
How to turn in:
Turn in via GitHub. Ensure the file(s) are in your directory and then:
• $ git add <files
• $ git commit
• $ git push
