| 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);
}
}
}
};
Response
#include <vector>
#include <cassert>
#include <iostream>
#include <algorithm> // For std::find
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);
}
}
}
};
int main() {
// Test: Basic construction with bounds smaller than MinSize
// Expected: No subregions are created, add succeeds.
{
RegionTree tree(Bounds{0, 0, 7, 7});
assert(tree.add(Bounds{1, 1, 2, 2}));
}
// Test: Basic construction with bounds larger than MinSize
// Expected: Subregions are created, add succeeds.
{
RegionTree tree(Bounds{0, 0, 100, 100});
assert(tree.add(Bounds{49, 49, 51, 51}));
}
// Test: Add a single valid box
// Expected: Add returns true.
{
RegionTree tree(Bounds{0, 0, 100, 100});
assert(tree.add(Bounds{10, 10, 20, 20}));
}
// Test: Add a box outside the tree's bounds
// Expected: Add returns false.
{
RegionTree tree(Bounds{0, 0, 100, 100});
assert(!tree.add(Bounds{110, 110, 120, 120}));
}
// Test: Add a box partially overlapping the tree's bounds
// Expected: Add returns false.
{
RegionTree tree(Bounds{0, 0, 100, 100});
assert(!tree.add(Bounds{90, 90, 110, 110}));
}
// Test: Add a box that is flush with the tree's boundary
// Expected: Add returns true.
{
RegionTree tree(Bounds{0, 0, 100, 100});
assert(tree.add(Bounds{0, 0, 10, 10}));
assert(tree.add(Bounds{90, 90, 100, 100}));
}
// Test: Add two non-intersecting boxes
// Expected: Both adds return true.
{
RegionTree tree(Bounds{0, 0, 100, 100});
assert(tree.add(Bounds{10, 10, 20, 20}));
assert(tree.add(Bounds{30, 30, 40, 40}));
}
// Test: Add a box that completely overlaps an existing box
// Expected: Second add returns false.
{
RegionTree tree(Bounds{0, 0, 100, 100});
assert(tree.add(Bounds{10, 10, 20, 20}));
assert(!tree.add(Bounds{5, 5, 25, 25}));
}
// Test: Add a box that is completely contained within an existing box
// Expected: Second add returns false.
{
RegionTree tree(Bounds{0, 0, 100, 100});
assert(tree.add(Bounds{5, 5, 25, 25}));
assert(!tree.add(Bounds{10, 10, 20, 20}));
}
// Test: Add a box that partially intersects an existing box
// Expected: Second add returns false.
{
RegionTree tree(Bounds{0, 0, 100, 100});
assert(tree.add(Bounds{10, 10, 20, 20}));
assert(!tree.add(Bounds{15, 15, 25, 25}));
}
// Test: Add a box that shares an edge with an existing box (touching)
// Expected: Second add returns false because touching is intersecting.
{
RegionTree tree(Bounds{0, 0, 100, 100});
assert(tree.add(Bounds{10, 10, 20, 20}));
assert(!tree.add(Bounds{20, 10, 30, 20}));
}
// Test: Add a box that shares a corner with an existing box (touching)
// Expected: Second add returns false because touching is intersecting.
{
RegionTree tree(Bounds{0, 0, 100, 100});
assert(tree.add(Bounds{10, 10, 20, 20}));
assert(!tree.add(Bounds{20, 20, 30, 30}));
}
// Test: Add identical box twice
// Expected: Second add returns false.
{
RegionTree tree(Bounds{0, 0, 100, 100});
assert(tree.add(Bounds{10, 10, 20, 20}));
assert(!tree.add(Bounds{10, 10, 20, 20}));
}
// Test: Add a box that spans multiple subregions without collision
// Expected: Add returns true.
{
RegionTree tree(Bounds{0, 0, 100, 100});
assert(tree.add(Bounds{40, 40, 60, 60}));
}
// Test: Add a box that spans subregions and collides with an existing box
// Expected: Second add returns false.
{
RegionTree tree(Bounds{0, 0, 100, 100});
assert(tree.add(Bounds{10, 10, 20, 20}));
assert(!tree.add(Bounds{15, 15, 55, 55}));
}
// Test: Add two non-intersecting boxes in different subregions
// Expected: Both adds return true.
{
RegionTree tree(Bounds{0, 0, 100, 100});
assert(tree.add(Bounds{10, 10, 20, 20}));
assert(tree.add(Bounds{60, 60, 70, 70}));
}
// Test: Add zero-width box (a vertical line)
// Expected: Add returns true.
{
RegionTree tree(Bounds{0, 0, 100, 100});
assert(tree.add(Bounds{10, 10, 10, 20}));
}
// Test: Add zero-height box (a horizontal line)
// Expected: Add returns true.
{
RegionTree tree(Bounds{0, 0, 100, 100});
assert(tree.add(Bounds{10, 10, 20, 10}));
}
// Test: Add zero-size box (a point)
// Expected: Add returns true.
{
RegionTree tree(Bounds{0, 0, 100, 100});
assert(tree.add(Bounds{10, 10, 10, 10}));
}
// Test: Add a box that touches a zero-width box
// Expected: Add returns false due to intersection.
{
RegionTree tree(Bounds{0, 0, 100, 100});
assert(tree.add(Bounds{10, 10, 10, 20}));
assert(!tree.add(Bounds{10, 15, 15, 18}));
}
// Test: Basic remove
// Expected: Box can be added again after being removed.
{
RegionTree tree(Bounds{0, 0, 100, 100});
Bounds b{10, 10, 20, 20};
assert(tree.add(b));
assert(!tree.add(b));
tree.remove(b);
assert(tree.add(b));
}
// Test: Remove a non-existent box
// Expected: No change, no crash, existing box remains.
{
RegionTree tree(Bounds{0, 0, 100, 100});
Bounds b1{10, 10, 20, 20};
Bounds b2{30, 30, 40, 40};
assert(tree.add(b1));
tree.remove(b2);
assert(!tree.add(b1));
}
// Test: Remove a box that has already been removed
// Expected: No change, no crash.
{
RegionTree tree(Bounds{0, 0, 100, 100});
Bounds b{10, 10, 20, 20};
assert(tree.add(b));
|
| Model: |
gemini-2.5-pro |
| Temperature: |
0.2 |
| Max output tokens: |
8192 |
| TopK: |
40.0 |
| TopP: |
0.95 |
|
