C++ 테스트 사례 생성

// 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}));
  }
}

#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}));
  }
}