System instructions |
You are a unit testing expert adept at identifying and covering edge cases. You only respond with the requested test code and no additional explanation.
|
Create tests for the RegionTree class in the form of a main function containing assertions. The class should allow bounding boxes to be added if they do not intersect any other box currently in the tree. Label each test with a descriptive comment and the expected behavior.
// RegionTree.hpp
#include <vector>
#include <cassert>
#include <iostream>
class Bounds {
public:
Bounds(int left, int top, int right, int bottom)
: left_{left}
, right_{right}
, top_{top}
, bottom_{bottom} {
assert(right >= left);
assert(bottom >= top);
}
bool operator==(Bounds const& rhs) const {
return left_ == rhs.left_ && right_ == rhs.right_ && top_ == rhs.top_ && bottom_ == rhs.bottom_;
}
int left() const { return left_; }
int right() const { return right_; }
int top() const { return top_; }
int bottom() const { return bottom_; }
int width() const { return right_ - left_; }
int height() const { return bottom_ - top_; }
private:
int left_;
int right_;
int top_;
int bottom_;
};
bool intersects(Bounds const& a, Bounds const& b) {
return !(a.left() > b.right() || a.right() < b.left() || a.top() > b.bottom() || a.bottom() < b.top());
}
bool contains(Bounds const& a, Bounds const& b) {
return a.left() >= b.left() && a.right() <= b.right() && a.top() >= b.top() && a.bottom() <= b.bottom();
}
class RegionTree {
private:
static constexpr int MinSize = 8;
Bounds bounds_;
std::vector<Bounds> items_;
std::vector<RegionTree> subregions_;
bool canInsert(Bounds const& bounds) const {
for (RegionTree const& subregion : subregions_) {
if (intersects(subregion.bounds_, bounds) && !subregion.canInsert(bounds)) {
return false;
}
}
for (Bounds const& item : items_) {
if (intersects(item, bounds)) {
return false;
}
}
return true;
}
bool addImpl(Bounds const& bounds) {
if (!canInsert(bounds)) {
return false;
}
if (subregions_.empty()) {
items_.push_back(bounds);
} else {
for (RegionTree& subregion : subregions_) {
if (intersects(subregion.bounds_, bounds)) {
assert(subregion.addImpl(bounds));
}
}
}
return true;
}
public:
RegionTree(Bounds const& bounds)
: bounds_{bounds}
, items_{}
, subregions_{} {
if (bounds_.width() > MinSize || bounds_.height() > MinSize) {
int westWidth = bounds_.width() - bounds_.width() / 2;
int northHeight = bounds_.height() - bounds_.height() / 2;
subregions_.push_back(Bounds{bounds_.left(), bounds_.top(), bounds_.left() + westWidth, bounds_.top() + northHeight});
subregions_.push_back(Bounds{bounds_.left() + westWidth, bounds_.top(), bounds_.right(), bounds_.top() + northHeight});
subregions_.push_back(Bounds{bounds_.left(), bounds_.top() + northHeight, bounds_.left() + westWidth, bounds_.bottom()});
subregions_.push_back(Bounds{bounds_.left() + westWidth, bounds_.top() + northHeight, bounds_.right(), bounds_.bottom()});
}
}
bool add(Bounds const& bounds) {
if (!contains(bounds, bounds_)) {
return false;
}
return addImpl(bounds);
}
void remove(Bounds const& bounds) {
if (!intersects(bounds_, bounds)) {
return;
}
if (subregions_.empty()) {
auto it = std::find(items_.begin(), items_.end(), bounds);
if (it != items_.end()) {
items_.erase(it);
}
} else {
for (RegionTree& subregion : subregions_) {
subregion.remove(bounds);
}
}
}
};
#include "RegionTree.hpp"
int main() {
// Test 1: Add a box to an empty tree.
// Expected: The box is added successfully.
{
RegionTree tree(Bounds{0, 0, 100, 100});
assert(tree.add(Bounds{10, 10, 20, 20}));
}
// Test 2: Add a box that is fully contained within the tree's bounds.
// Expected: The box is added successfully.
{
RegionTree tree(Bounds{0, 0, 100, 100});
assert(tree.add(Bounds{10, 10, 20, 20}));
}
// Test 3: Add a box that partially intersects the tree's bounds.
// Expected: The box is not added.
{
RegionTree tree(Bounds{0, 0, 100, 100});
assert(!tree.add(Bounds{-10, 10, 20, 20}));
}
// Test 4: Add a box that is fully outside the tree's bounds.
// Expected: The box is not added.
{
RegionTree tree(Bounds{0, 0, 100, 100});
assert(!tree.add(Bounds{-10, -10, -20, -20}));
}
// Test 5: Add two boxes that do not intersect.
// Expected: Both boxes are added successfully.
{
RegionTree tree(Bounds{0, 0, 100, 100});
assert(tree.add(Bounds{10, 10, 20, 20}));
assert(tree.add(Bounds{30, 30, 40, 40}));
}
// Test 6: Add two boxes that intersect.
// Expected: The first box is added, the second is not.
{
RegionTree tree(Bounds{0, 0, 100, 100});
assert(tree.add(Bounds{10, 10, 20, 20}));
assert(!tree.add(Bounds{15, 15, 25, 25}));
}
// Test 7: Remove a box that exists in the tree.
// Expected: The box is removed.
{
RegionTree tree(Bounds{0, 0, 100, 100});
tree.add(Bounds{10, 10, 20, 20});
tree.remove(Bounds{10, 10, 20, 20});
assert(tree.add(Bounds{10, 10, 20, 20}));
}
// Test 8: Remove a box that does not exist in the tree.
// Expected: No change to the tree.
{
RegionTree tree(Bounds{0, 0, 100, 100});
tree.add(Bounds{10, 10, 20, 20});
tree.remove(Bounds{30, 30, 40, 40});
assert(!tree.add(Bounds{30, 30, 40, 40}));
}
}
Response
#include "RegionTree.hpp"
int main() {
// Test 1: Add a box to an empty tree.
// Expected: The box is added successfully.
{
RegionTree tree(Bounds{0, 0, 100, 100});
assert(tree.add(Bounds{10, 10, 20, 20}));
}
// Test 2: Add a box that is fully contained within the tree's bounds.
// Expected: The box is added successfully.
{
RegionTree tree(Bounds{0, 0, 100, 100});
assert(tree.add(Bounds{10, 10, 20, 20}));
}
// Test 3: Add a box that partially intersects the tree's bounds.
// Expected: The box is not added.
{
RegionTree tree(Bounds{0, 0, 100, 100});
assert(!tree.add(Bounds{-10, 10, 20, 20}));
}
// Test 4: Add a box that is fully outside the tree's bounds.
// Expected: The box is not added.
{
RegionTree tree(Bounds{0, 0, 100, 100});
assert(!tree.add(Bounds{-10, -10, -20, -20}));
}
// Test 5: Add two boxes that do not intersect.
// Expected: Both boxes are added successfully.
{
RegionTree tree(Bounds{0, 0, 100, 100});
assert(tree.add(Bounds{10, 10, 20, 20}));
assert(tree.add(Bounds{30, 30, 40, 40}));
}
// Test 6: Add two boxes that intersect.
// Expected: The first box is added, the second is not.
{
RegionTree tree(Bounds{0, 0, 100, 100});
assert(tree.add(Bounds{10, 10, 20, 20}));
assert(!tree.add(Bounds{15, 15, 25, 25}));
}
// Test 7: Remove a box that exists in the tree.
// Expected: The box is removed.
{
RegionTree tree(Bounds{0, 0, 100, 100});
tree.add(Bounds{10, 10, 20, 20});
tree.remove(Bounds{10, 10, 20, 20});
assert(tree.add(Bounds{10, 10, 20, 20}));
}
// Test 8: Remove a box that does not exist in the tree.
// Expected: No change to the tree.
{
RegionTree tree(Bounds{0, 0, 100, 100});
tree.add(Bounds{10, 10, 20, 20});
tree.remove(Bounds{30, 30, 40, 40});
assert(!tree.add(Bounds{30, 30, 40, 40}));
}
//Test 9: Add a box to a tree that is already full.
//Expected: The box is not added.
{
RegionTree tree(Bounds{0,0,8,8});
assert(tree.add(Bounds{0,0,8,8}));
assert(!tree.add(Bounds{0,0,4,4}));
}
//Test 10: Add a box that exactly matches the tree bounds.
//Expected: The box is added.
{
RegionTree tree(Bounds{0,0,100,100});
assert(tree.add(Bounds{0,0,100,100}));
}
//Test 11: Add a box larger than the tree bounds.
//Expected: The box is not added.
{
RegionTree tree(Bounds{0,0,100,100});
assert(!tree.add(Bounds{0,0,200,200}));
}
//Test 12: Add multiple boxes that fill the tree.
//Expected: All boxes are added.
{
RegionTree tree(Bounds{0,0,16,16});
assert(tree.add(Bounds{0,0,8,8}));
assert(tree.add(Bounds{8,0,16,8}));
assert(tree.add(Bounds{0,8,8,16}));
assert(tree.add(Bounds{8,8,16,16}));
}
//Test 13: Remove a box from a tree with subregions.
//Expected: The box is removed.
{
RegionTree tree(Bounds{0,0,16,16});
tree.add(Bounds{0,0,8,8});
tree.remove(Bounds{0,0,8,8});
assert(tree.add(Bounds{0,0,8,8}));
}
}
|
Model: |
gemini-1.5-flash-002 |
Temperature: |
0.2 |
Max output tokens: |
8192 |
TopK: |
40.0 |
TopP: |
0.95 |
|