Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(166)

Unified Diff: ui/gfx/geometry/r_tree_unittest.cc

Issue 342723002: Repairs crash in RTreeBase::Node::LeastAreaEnlargement (Closed) Base URL: https://chromium.googlesource.com/chromium/src.git@master
Patch Set: crash fix and test added Created 6 years, 6 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View side-by-side diff with in-line comments
Download patch
« no previous file with comments | « ui/gfx/geometry/r_tree_base.cc ('k') | ui/gfx/gfx.gyp » ('j') | no next file with comments »
Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
Index: ui/gfx/geometry/r_tree_unittest.cc
diff --git a/ui/gfx/geometry/r_tree_unittest.cc b/ui/gfx/geometry/r_tree_unittest.cc
index a98c57efade82183e197b67213a40bff57989010..ba45405ee2a3418e81fa5434530d95e50046930b 100644
--- a/ui/gfx/geometry/r_tree_unittest.cc
+++ b/ui/gfx/geometry/r_tree_unittest.cc
@@ -4,459 +4,344 @@
#include "testing/gtest/include/gtest/gtest.h"
#include "ui/gfx/geometry/r_tree.h"
+#include "ui/gfx/geometry/r_tree_base.h"
#include "ui/gfx/geometry/rect.h"
namespace gfx {
class RTreeTest : public ::testing::Test {
protected:
- // Given a pointer to an RTree, traverse it and verify its internal structure
- // is consistent with the RTree semantics.
- void ValidateRTree(RTree* rt) {
+ typedef RTree<int> RT;
+
+ // Given a pointer to an RTree, traverse it and verify that its internal
+ // structure is consistent with RTree semantics.
+ void ValidateRTree(RTreeBase* rt) {
// If RTree is empty it should have an empty rectangle.
- if (!rt->root_->count()) {
- EXPECT_TRUE(rt->root_->rect().IsEmpty());
- EXPECT_EQ(rt->root_->level(), 0);
+ if (!rt->root()->count()) {
+ EXPECT_TRUE(rt->root()->rect().IsEmpty());
+ EXPECT_EQ(0, rt->root()->Level());
return;
}
// Root is allowed to have fewer than min_children_ but never more than
// max_children_.
- EXPECT_LE(rt->root_->count(), rt->max_children_);
+ EXPECT_LE(rt->root()->count(), rt->max_children_);
// The root should never be a record node.
- EXPECT_GT(rt->root_->level(), -1);
- EXPECT_FALSE(rt->root_->key());
+ EXPECT_GT(rt->root()->Level(), -1);
// The root should never have a parent pointer.
- EXPECT_FALSE(rt->root_->parent());
+ EXPECT_TRUE(rt->root()->parent() == NULL);
// Bounds must be consistent on the root.
- CheckBoundsConsistent(rt->root_.get());
- // We traverse root's children ourselves, so we can avoid asserts about
- // root's potential inconsistencies.
- for (size_t i = 0; i < rt->root_->children_.size(); ++i) {
+ CheckBoundsConsistent(rt->root());
+ for (size_t i = 0; i < rt->root()->count(); ++i) {
ValidateNode(
- rt->root_->children_[i], rt->min_children_, rt->max_children_);
+ rt->root()->child(i), rt->min_children_, rt->max_children_);
}
}
// Recursive descent method used by ValidateRTree to check each node within
// the RTree for consistency with RTree semantics.
- void ValidateNode(RTree::Node* node,
+ void ValidateNode(const RTreeBase::NodeBase* node_base,
size_t min_children,
size_t max_children) {
- // Record nodes have different requirements, handle up front.
- if (node->level() == -1) {
- // Record nodes may have no children.
- EXPECT_EQ(node->count(), 0U);
- // They must have an associated non-NULL key.
- EXPECT_TRUE(node->key());
- // They must always have a parent.
- EXPECT_TRUE(node->parent());
- return;
- }
- // Non-record node, normal expectations apply.
- EXPECT_GE(node->count(), min_children);
- EXPECT_LE(node->count(), max_children);
- EXPECT_EQ(node->key(), 0);
- CheckBoundsConsistent(node);
- for (size_t i = 0; i < node->children_.size(); ++i) {
- ValidateNode(node->children_[i], min_children, max_children);
+ if (node_base->Level() >= 0) {
+ const RTreeBase::Node* node =
+ static_cast<const RTreeBase::Node*>(node_base);
+ EXPECT_GE(node->count(), min_children);
+ EXPECT_LE(node->count(), max_children);
+ CheckBoundsConsistent(node);
+ for (size_t i = 0; i < node->count(); ++i)
+ ValidateNode(node->child(i), min_children, max_children);
}
}
// Check bounds are consistent with children bounds, and other checks
// convenient to do while enumerating the children of node.
- void CheckBoundsConsistent(RTree::Node* node) {
- EXPECT_FALSE(node->rect_.IsEmpty());
+ void CheckBoundsConsistent(const RTreeBase::Node* node) {
+ EXPECT_FALSE(node->rect().IsEmpty());
Rect check_bounds;
- for (size_t i = 0; i < node->children_.size(); ++i) {
- RTree::Node* child_node = node->children_[i];
+ for (size_t i = 0; i < node->count(); ++i) {
+ const RTreeBase::NodeBase* child_node = node->child(i);
check_bounds.Union(child_node->rect());
- EXPECT_EQ(node->level() - 1, child_node->level());
+ EXPECT_EQ(node->Level() - 1, child_node->Level());
EXPECT_EQ(node, child_node->parent());
}
- EXPECT_EQ(node->rect_, check_bounds);
+ EXPECT_EQ(check_bounds, node->rect());
}
// Adds count squares stacked around the point (0,0) with key equal to width.
- void AddStackedSquares(RTree* rt, int count) {
+ void AddStackedSquares(RT* rt, int count) {
for (int i = 1; i <= count; ++i) {
rt->Insert(Rect(0, 0, i, i), i);
- ValidateRTree(rt);
+ ValidateRTree(static_cast<RTreeBase*>(rt));
}
}
- // Given an unordered list of matching keys, verify that it contains all
+ // Given an unordered list of matching keys, verifies that it contains all
// values [1..length] for the length of that list.
- void VerifyAllKeys(const base::hash_set<intptr_t>& keys) {
- // Verify that the keys are in values [1,count].
- for (size_t i = 1; i <= keys.size(); ++i) {
- EXPECT_EQ(keys.count(i), 1U);
- }
+ void VerifyAllKeys(const RT::Matches& keys) {
+ for (size_t i = 1; i <= keys.size(); ++i)
+ EXPECT_EQ(1U, keys.count(i));
}
// Given a node and a rectangle, builds an expanded rectangle list where the
- // ith element of the rectangle is union of the recangle of the ith child of
+ // ith element of the vector is the union of the rectangle of the ith child of
// the node and the argument rectangle.
- void BuildExpandedRects(RTree::Node* node,
+ void BuildExpandedRects(RTreeBase::Node* node,
const Rect& rect,
std::vector<Rect>* expanded_rects) {
expanded_rects->clear();
- expanded_rects->reserve(node->children_.size());
- for (size_t i = 0; i < node->children_.size(); ++i) {
+ expanded_rects->reserve(node->count());
+ for (size_t i = 0; i < node->count(); ++i) {
Rect expanded_rect(rect);
- expanded_rect.Union(node->children_[i]->rect_);
+ expanded_rect.Union(node->child(i)->rect());
expanded_rects->push_back(expanded_rect);
}
}
};
-// An empty RTree should never return Query results, and RTrees should be empty
-// upon construction.
-TEST_F(RTreeTest, QueryEmptyTree) {
- RTree rt(2, 10);
- ValidateRTree(&rt);
- base::hash_set<intptr_t> results;
- Rect test_rect(25, 25);
- rt.Query(test_rect, &results);
- EXPECT_EQ(results.size(), 0U);
- ValidateRTree(&rt);
-}
-
-// Clear should empty the tree, meaning that all queries should not return
-// results after.
-TEST_F(RTreeTest, ClearEmptiesTreeOfSingleNode) {
- RTree rt(2, 5);
- rt.Insert(Rect(0, 0, 100, 100), 1);
- rt.Clear();
- base::hash_set<intptr_t> results;
- Rect test_rect(1, 1);
- rt.Query(test_rect, &results);
- EXPECT_EQ(results.size(), 0U);
- ValidateRTree(&rt);
-}
-
-// Even with a complex internal structure, clear should empty the tree, meaning
-// that all queries should not return results after.
-TEST_F(RTreeTest, ClearEmptiesTreeOfManyNodes) {
- RTree rt(2, 5);
- AddStackedSquares(&rt, 100);
- rt.Clear();
- base::hash_set<intptr_t> results;
- Rect test_rect(1, 1);
- rt.Query(test_rect, &results);
- EXPECT_EQ(results.size(), 0U);
- ValidateRTree(&rt);
-}
-
-// Duplicate inserts should overwrite previous inserts.
-TEST_F(RTreeTest, DuplicateInsertsOverwrite) {
- RTree rt(2, 5);
- // Add 100 stacked squares, but always with duplicate key of 1.
- for (int i = 1; i <= 100; ++i) {
- rt.Insert(Rect(0, 0, i, i), 1);
- ValidateRTree(&rt);
+class RTreeNodeTest : public RTreeTest {
+ protected:
+ typedef RTreeBase::NodeBase RTreeNodeBase;
+ typedef RT::Record RTreeRecord;
+ typedef RTreeBase::Node RTreeNode;
+ typedef RTreeBase::Node::Rects RTreeRects;
+ typedef RTreeBase::Nodes RTreeNodes;
+
+ // Accessors to private members of RTree::Node.
+ const RTreeRecord* record(RTreeNode* node, size_t i) {
+ return static_cast<const RTreeRecord*>(node->child(i));
}
- base::hash_set<intptr_t> results;
- Rect test_rect(1, 1);
- rt.Query(test_rect, &results);
- EXPECT_EQ(results.size(), 1U);
- EXPECT_EQ(results.count(1), 1U);
-}
-// Call Remove() once on something that's been inserted repeatedly.
-TEST_F(RTreeTest, DuplicateInsertRemove) {
- RTree rt(3, 9);
- AddStackedSquares(&rt, 25);
- for (int i = 1; i <= 100; ++i) {
- rt.Insert(Rect(0, 0, i, i), 26);
- ValidateRTree(&rt);
+ // Provides access for tests to private methods of RTree::Node.
+ scoped_ptr<RTreeNode> NewNodeAtLevel(size_t level) {
+ return make_scoped_ptr(new RTreeBase::Node(level));
}
- rt.Remove(26);
- base::hash_set<intptr_t> results;
- Rect test_rect(1, 1);
- rt.Query(test_rect, &results);
- EXPECT_EQ(results.size(), 25U);
- VerifyAllKeys(results);
-}
-// Call Remove() repeatedly on something that's been inserted once.
-TEST_F(RTreeTest, InsertDuplicateRemove) {
- RTree rt(7, 15);
- AddStackedSquares(&rt, 101);
- for (int i = 0; i < 100; ++i) {
- rt.Remove(101);
- ValidateRTree(&rt);
+ void NodeRecomputeLocalBounds(RTreeNodeBase* node) {
+ node->RecomputeLocalBounds();
}
- base::hash_set<intptr_t> results;
- Rect test_rect(1, 1);
- rt.Query(test_rect, &results);
- EXPECT_EQ(results.size(), 100U);
- VerifyAllKeys(results);
-}
-
-// Stacked rects should meet all matching queries regardless of nesting.
-TEST_F(RTreeTest, QueryStackedSquaresNestedHit) {
- RTree rt(2, 5);
- AddStackedSquares(&rt, 100);
- base::hash_set<intptr_t> results;
- Rect test_rect(1, 1);
- rt.Query(test_rect, &results);
- EXPECT_EQ(results.size(), 100U);
- VerifyAllKeys(results);
-}
-// Stacked rects should meet all matching queries when contained completely by
-// the query rectangle.
-TEST_F(RTreeTest, QueryStackedSquaresContainedHit) {
- RTree rt(2, 10);
- AddStackedSquares(&rt, 100);
- base::hash_set<intptr_t> results;
- Rect test_rect(0, 0, 100, 100);
- rt.Query(test_rect, &results);
- EXPECT_EQ(results.size(), 100U);
- VerifyAllKeys(results);
-}
+ bool NodeCompareVertical(RTreeNodeBase* a, RTreeNodeBase* b) {
+ return RTreeBase::Node::CompareVertical(a, b);
+ }
-// Stacked rects should miss a missing query when the query has no intersection
-// with the rects.
-TEST_F(RTreeTest, QueryStackedSquaresCompleteMiss) {
- RTree rt(2, 7);
- AddStackedSquares(&rt, 100);
- base::hash_set<intptr_t> results;
- Rect test_rect(150, 150, 100, 100);
- rt.Query(test_rect, &results);
- EXPECT_EQ(results.size(), 0U);
-}
+ bool NodeCompareHorizontal(RTreeNodeBase* a, RTreeNodeBase* b) {
+ return RTreeBase::Node::CompareHorizontal(a, b);
+ }
-// Removing half the nodes after insertion should still result in a valid tree.
-TEST_F(RTreeTest, RemoveHalfStackedRects) {
- RTree rt(2, 11);
- AddStackedSquares(&rt, 200);
- for (int i = 101; i <= 200; ++i) {
- rt.Remove(i);
- ValidateRTree(&rt);
+ bool NodeCompareCenterDistanceFromParent(
+ const RTreeNodeBase* a, const RTreeNodeBase* b) {
+ return RTreeBase::Node::CompareCenterDistanceFromParent(a, b);
}
- base::hash_set<intptr_t> results;
- Rect test_rect(1, 1);
- rt.Query(test_rect, &results);
- EXPECT_EQ(results.size(), 100U);
- VerifyAllKeys(results);
- // Add the nodes back in.
- for (int i = 101; i <= 200; ++i) {
- rt.Insert(Rect(0, 0, i, i), i);
- ValidateRTree(&rt);
+
+ int NodeOverlapIncreaseToAdd(RTreeNode* node,
+ const Rect& rect,
+ const RTreeNodeBase* candidate_node,
+ const Rect& expanded_rect) {
+ return node->OverlapIncreaseToAdd(rect, candidate_node, expanded_rect);
}
- results.clear();
- rt.Query(test_rect, &results);
- EXPECT_EQ(results.size(), 200U);
- VerifyAllKeys(results);
-}
-TEST_F(RTreeTest, InsertDupToRoot) {
- RTree rt(2, 5);
- rt.Insert(Rect(0, 0, 1, 2), 1);
- ValidateRTree(&rt);
- rt.Insert(Rect(0, 0, 2, 1), 1);
- ValidateRTree(&rt);
-}
+ void NodeBuildLowBounds(const std::vector<RTreeNodeBase*>& vertical_sort,
+ const std::vector<RTreeNodeBase*>& horizontal_sort,
+ RTreeRects* vertical_bounds,
+ RTreeRects* horizontal_bounds) {
+ RTreeBase::Node::BuildLowBounds(
+ vertical_sort, horizontal_sort, vertical_bounds, horizontal_bounds);
+ }
-TEST_F(RTreeTest, InsertNegativeCoordsRect) {
- RTree rt(5, 11);
- for (int i = 1; i <= 100; ++i) {
- rt.Insert(Rect(-i, -i, i, i), (i * 2) - 1);
- ValidateRTree(&rt);
- rt.Insert(Rect(0, 0, i, i), i * 2);
- ValidateRTree(&rt);
+ void NodeBuildHighBounds(const std::vector<RTreeNodeBase*>& vertical_sort,
+ const std::vector<RTreeNodeBase*>& horizontal_sort,
+ RTreeRects* vertical_bounds,
+ RTreeRects* horizontal_bounds) {
+ RTreeBase::Node::BuildHighBounds(
+ vertical_sort, horizontal_sort, vertical_bounds, horizontal_bounds);
}
- base::hash_set<intptr_t> results;
- Rect test_rect(-1, -1, 2, 2);
- rt.Query(test_rect, &results);
- EXPECT_EQ(results.size(), 200U);
- VerifyAllKeys(results);
-}
-TEST_F(RTreeTest, RemoveNegativeCoordsRect) {
- RTree rt(7, 21);
- // Add 100 positive stacked squares.
- AddStackedSquares(&rt, 100);
- // Now add 100 negative stacked squares.
- for (int i = 101; i <= 200; ++i) {
- rt.Insert(Rect(100 - i, 100 - i, i - 100, i - 100), 301 - i);
- ValidateRTree(&rt);
+ int NodeSmallestMarginSum(size_t start_index,
+ size_t end_index,
+ const RTreeRects& low_bounds,
+ const RTreeRects& high_bounds) {
+ return RTreeBase::Node::SmallestMarginSum(
+ start_index, end_index, low_bounds, high_bounds);
}
- // Now remove half of the negative squares.
- for (int i = 101; i <= 150; ++i) {
- rt.Remove(301 - i);
- ValidateRTree(&rt);
+
+ size_t NodeChooseSplitIndex(size_t min_children,
+ size_t max_children,
+ const RTreeRects& low_bounds,
+ const RTreeRects& high_bounds) {
+ return RTreeBase::Node::ChooseSplitIndex(
+ min_children, max_children, low_bounds, high_bounds);
}
- // Queries should return 100 positive and 50 negative stacked squares.
- base::hash_set<intptr_t> results;
- Rect test_rect(-1, -1, 2, 2);
- rt.Query(test_rect, &results);
- EXPECT_EQ(results.size(), 150U);
- VerifyAllKeys(results);
-}
-TEST_F(RTreeTest, InsertEmptyRectReplacementRemovesKey) {
- RTree rt(10, 31);
- AddStackedSquares(&rt, 50);
- ValidateRTree(&rt);
+ scoped_ptr<RTreeNodeBase> NodeDivideChildren(
+ RTreeNode* node,
+ const RTreeRects& low_bounds,
+ const RTreeRects& high_bounds,
+ const std::vector<RTreeNodeBase*>& sorted_children,
+ size_t split_index) {
+ return node->DivideChildren(
+ low_bounds, high_bounds, sorted_children, split_index);
+ }
- // Replace last square with empty rect.
- rt.Insert(Rect(), 50);
- ValidateRTree(&rt);
+ RTreeNode* NodeLeastOverlapIncrease(RTreeNode* node,
+ const Rect& node_rect,
+ const RTreeRects& expanded_rects) {
+ return node->LeastOverlapIncrease(node_rect, expanded_rects);
+ }
- // Now query large area to get all rects in tree.
- base::hash_set<intptr_t> results;
- Rect test_rect(0, 0, 100, 100);
- rt.Query(test_rect, &results);
+ RTreeNode* NodeLeastAreaEnlargement(RTreeNode* node,
+ const Rect& node_rect,
+ const RTreeRects& expanded_rects) {
+ return node->LeastAreaEnlargement(node_rect, expanded_rects);
+ }
+};
- // Should only be 49 rects in tree.
- EXPECT_EQ(results.size(), 49U);
- VerifyAllKeys(results);
-}
+// RTreeNodeTest --------------------------------------------------------------
-TEST_F(RTreeTest, NodeRemoveNodesForReinsert) {
+TEST_F(RTreeNodeTest, RemoveNodesForReinsert) {
// Make a leaf node for testing removal from.
- scoped_ptr<RTree::Node> test_node(new RTree::Node(0));
+ scoped_ptr<RTreeNode> test_node(new RTreeNode);
// Build 20 record nodes with rectangle centers going from (1,1) to (20,20)
- for (int i = 1; i <= 20; ++i) {
- test_node->AddChild(new RTree::Node(Rect(i - 1, i - 1, 2, 2), i));
- }
+ for (int i = 1; i <= 20; ++i)
+ test_node->AddChild(scoped_ptr<RTreeNodeBase>(
+ new RTreeRecord(Rect(i - 1, i - 1, 2, 2), i)));
+
// Quick verification of the node before removing children.
ValidateNode(test_node.get(), 1U, 20U);
// Use a scoped vector to delete all children that get removed from the Node.
- ScopedVector<RTree::Node> removals;
+ RTreeNodes removals;
test_node->RemoveNodesForReinsert(1, &removals);
- // Should have gotten back 1 node pointers.
- EXPECT_EQ(removals.size(), 1U);
+ // Should have gotten back 1 node pointer.
+ EXPECT_EQ(1U, removals.size());
// There should be 19 left in the test_node.
- EXPECT_EQ(test_node->count(), 19U);
+ EXPECT_EQ(19U, test_node->count());
// If we fix up the bounds on the test_node, it should verify.
- test_node->RecomputeBoundsNoParents();
+ NodeRecomputeLocalBounds(test_node.get());
ValidateNode(test_node.get(), 2U, 20U);
// The node we removed should be node 10, as it was exactly in the center.
- EXPECT_EQ(removals[0]->key(), 10);
+ EXPECT_EQ(10, static_cast<RTreeRecord*>(removals[0])->key());
// Now remove the next 2.
removals.clear();
test_node->RemoveNodesForReinsert(2, &removals);
- EXPECT_EQ(removals.size(), 2U);
- EXPECT_EQ(test_node->count(), 17U);
- test_node->RecomputeBoundsNoParents();
+ EXPECT_EQ(2U, removals.size());
+ EXPECT_EQ(17U, test_node->count());
+ NodeRecomputeLocalBounds(test_node.get());
ValidateNode(test_node.get(), 2U, 20U);
// Lastly the 2 nodes we should have gotten back are keys 9 and 11, as their
// centers were the closest to the center of the node bounding box.
base::hash_set<intptr_t> results_hash;
- results_hash.insert(removals[0]->key());
- results_hash.insert(removals[1]->key());
- EXPECT_EQ(results_hash.count(9), 1U);
- EXPECT_EQ(results_hash.count(11), 1U);
+ results_hash.insert(static_cast<RTreeRecord*>(removals[0])->key());
+ results_hash.insert(static_cast<RTreeRecord*>(removals[1])->key());
+ EXPECT_EQ(1U, results_hash.count(9));
+ EXPECT_EQ(1U, results_hash.count(11));
}
-TEST_F(RTreeTest, NodeCompareVertical) {
- // One rect with lower y than another should always sort lower than higher y.
- RTree::Node low(Rect(0, 1, 10, 10), 1);
- RTree::Node middle(Rect(0, 5, 10, 10), 5);
- EXPECT_TRUE(RTree::Node::CompareVertical(&low, &middle));
- EXPECT_FALSE(RTree::Node::CompareVertical(&middle, &low));
+TEST_F(RTreeNodeTest, CompareVertical) {
+ // One rect with lower y than another should always sort lower.
+ RTreeRecord low(Rect(0, 1, 10, 10), 1);
+ RTreeRecord middle(Rect(0, 5, 10, 10), 5);
+ EXPECT_TRUE(NodeCompareVertical(&low, &middle));
+ EXPECT_FALSE(NodeCompareVertical(&middle, &low));
// Try a non-overlapping higher-y rectangle.
- RTree::Node high(Rect(-10, 20, 10, 1), 10);
- EXPECT_TRUE(RTree::Node::CompareVertical(&low, &high));
- EXPECT_FALSE(RTree::Node::CompareVertical(&high, &low));
+ RTreeRecord high(Rect(-10, 20, 10, 1), 10);
+ EXPECT_TRUE(NodeCompareVertical(&low, &high));
+ EXPECT_FALSE(NodeCompareVertical(&high, &low));
// Ties are broken by lowest bottom y value.
- RTree::Node shorter_tie(Rect(10, 1, 100, 2), 2);
- EXPECT_TRUE(RTree::Node::CompareVertical(&shorter_tie, &low));
- EXPECT_FALSE(RTree::Node::CompareVertical(&low, &shorter_tie));
+ RTreeRecord shorter_tie(Rect(10, 1, 100, 2), 2);
+ EXPECT_TRUE(NodeCompareVertical(&shorter_tie, &low));
+ EXPECT_FALSE(NodeCompareVertical(&low, &shorter_tie));
}
-TEST_F(RTreeTest, NodeCompareHorizontal) {
+TEST_F(RTreeNodeTest, CompareHorizontal) {
// One rect with lower x than another should always sort lower than higher x.
- RTree::Node low(Rect(1, 0, 10, 10), 1);
- RTree::Node middle(Rect(5, 0, 10, 10), 5);
- EXPECT_TRUE(RTree::Node::CompareHorizontal(&low, &middle));
- EXPECT_FALSE(RTree::Node::CompareHorizontal(&middle, &low));
+ RTreeRecord low(Rect(1, 0, 10, 10), 1);
+ RTreeRecord middle(Rect(5, 0, 10, 10), 5);
+ EXPECT_TRUE(NodeCompareHorizontal(&low, &middle));
+ EXPECT_FALSE(NodeCompareHorizontal(&middle, &low));
// Try a non-overlapping higher-x rectangle.
- RTree::Node high(Rect(20, -10, 1, 10), 10);
- EXPECT_TRUE(RTree::Node::CompareHorizontal(&low, &high));
- EXPECT_FALSE(RTree::Node::CompareHorizontal(&high, &low));
+ RTreeRecord high(Rect(20, -10, 1, 10), 10);
+ EXPECT_TRUE(NodeCompareHorizontal(&low, &high));
+ EXPECT_FALSE(NodeCompareHorizontal(&high, &low));
// Ties are broken by lowest bottom x value.
- RTree::Node shorter_tie(Rect(1, 10, 2, 100), 2);
- EXPECT_TRUE(RTree::Node::CompareHorizontal(&shorter_tie, &low));
- EXPECT_FALSE(RTree::Node::CompareHorizontal(&low, &shorter_tie));
+ RTreeRecord shorter_tie(Rect(1, 10, 2, 100), 2);
+ EXPECT_TRUE(NodeCompareHorizontal(&shorter_tie, &low));
+ EXPECT_FALSE(NodeCompareHorizontal(&low, &shorter_tie));
}
-TEST_F(RTreeTest, NodeCompareCenterDistanceFromParent) {
+TEST_F(RTreeNodeTest, CompareCenterDistanceFromParent) {
// Create a test node we can add children to, for distance comparisons.
- scoped_ptr<RTree::Node> parent(new RTree::Node(0));
+ scoped_ptr<RTreeNode> parent(new RTreeNode);
// Add three children, one each with centers at (0, 0), (10, 10), (-9, -9),
// around which a bounding box will be centered at (0, 0)
- RTree::Node* center_zero = new RTree::Node(Rect(-1, -1, 2, 2), 1);
- parent->AddChild(center_zero);
+ scoped_ptr<RTreeRecord> center_zero(new RTreeRecord(Rect(-1, -1, 2, 2), 1));
+ parent->AddChild(center_zero.PassAs<RTreeNodeBase>());
- RTree::Node* center_positive = new RTree::Node(Rect(9, 9, 2, 2), 2);
- parent->AddChild(center_positive);
+ scoped_ptr<RTreeRecord> center_positive(new RTreeRecord(Rect(9, 9, 2, 2), 2));
+ parent->AddChild(center_positive.PassAs<RTreeNodeBase>());
- RTree::Node* center_negative = new RTree::Node(Rect(-10, -10, 2, 2), 3);
- parent->AddChild(center_negative);
+ scoped_ptr<RTreeRecord> center_negative(
+ new RTreeRecord(Rect(-10, -10, 2, 2), 3));
+ parent->AddChild(center_negative.PassAs<RTreeNodeBase>());
ValidateNode(parent.get(), 1U, 5U);
- EXPECT_EQ(parent->rect_, Rect(-10, -10, 21, 21));
-
- EXPECT_TRUE(RTree::Node::CompareCenterDistanceFromParent(center_zero,
- center_positive));
- EXPECT_FALSE(RTree::Node::CompareCenterDistanceFromParent(center_positive,
- center_zero));
-
- EXPECT_TRUE(RTree::Node::CompareCenterDistanceFromParent(center_zero,
- center_negative));
- EXPECT_FALSE(RTree::Node::CompareCenterDistanceFromParent(center_negative,
- center_zero));
-
- EXPECT_TRUE(RTree::Node::CompareCenterDistanceFromParent(center_negative,
- center_positive));
- EXPECT_FALSE(RTree::Node::CompareCenterDistanceFromParent(center_positive,
- center_negative));
+ EXPECT_EQ(Rect(-10, -10, 21, 21), parent->rect());
+
+ EXPECT_TRUE(
+ NodeCompareCenterDistanceFromParent(parent->child(0), parent->child(1)));
+ EXPECT_FALSE(
+ NodeCompareCenterDistanceFromParent(parent->child(1), parent->child(0)));
+ EXPECT_TRUE(
+ NodeCompareCenterDistanceFromParent(parent->child(0), parent->child(2)));
+ EXPECT_FALSE(
+ NodeCompareCenterDistanceFromParent(parent->child(2), parent->child(0)));
+ EXPECT_TRUE(
+ NodeCompareCenterDistanceFromParent(parent->child(2), parent->child(1)));
+ EXPECT_FALSE(
+ NodeCompareCenterDistanceFromParent(parent->child(1), parent->child(2)));
}
-TEST_F(RTreeTest, NodeOverlapIncreaseToAdd) {
+TEST_F(RTreeNodeTest, OverlapIncreaseToAdd) {
// Create a test node with three children, for overlap comparisons.
- scoped_ptr<RTree::Node> parent(new RTree::Node(0));
+ scoped_ptr<RTreeNode> parent(new RTreeNode);
// Add three children, each 4 wide and tall, at (0, 0), (3, 3), (6, 6) with
// overlapping corners.
Rect top(0, 0, 4, 4);
- parent->AddChild(new RTree::Node(top, 1));
+ parent->AddChild(scoped_ptr<RTreeNodeBase>(new RTreeRecord(top, 1)));
Rect middle(3, 3, 4, 4);
- parent->AddChild(new RTree::Node(middle, 2));
+ parent->AddChild(scoped_ptr<RTreeNodeBase>(new RTreeRecord(middle, 2)));
Rect bottom(6, 6, 4, 4);
- parent->AddChild(new RTree::Node(bottom, 3));
+ parent->AddChild(scoped_ptr<RTreeNodeBase>(new RTreeRecord(bottom, 3)));
ValidateNode(parent.get(), 1U, 5U);
// Test a rect in corner.
Rect corner(0, 0, 1, 1);
Rect expanded = top;
expanded.Union(corner);
- // It should not add any overlap to add this to the first child at (0, 0);
- EXPECT_EQ(parent->OverlapIncreaseToAdd(corner, 0, expanded), 0);
+ // It should not add any overlap to add this to the first child at (0, 0).
+ EXPECT_EQ(0, NodeOverlapIncreaseToAdd(
+ parent.get(), corner, parent->child(0), expanded));
expanded = middle;
expanded.Union(corner);
// Overlap for middle rectangle should increase from 2 pixels at (3, 3) and
// (6, 6) to 17 pixels, as it will now cover 4x4 rectangle top,
- // so a change of +15
- EXPECT_EQ(parent->OverlapIncreaseToAdd(corner, 1, expanded), 15);
+ // so a change of +15.
+ EXPECT_EQ(15, NodeOverlapIncreaseToAdd(
+ parent.get(), corner, parent->child(1), expanded));
expanded = bottom;
expanded.Union(corner);
// Overlap for bottom rectangle should increase from 1 pixel at (6, 6) to
// 32 pixels, as it will now cover both 4x4 rectangles top and middle,
- // so a change of 31
- EXPECT_EQ(parent->OverlapIncreaseToAdd(corner, 2, expanded), 31);
+ // so a change of 31.
+ EXPECT_EQ(31, NodeOverlapIncreaseToAdd(
+ parent.get(), corner, parent->child(2), expanded));
// Test a rect that doesn't overlap with anything, in the far right corner.
Rect far_corner(9, 0, 1, 1);
@@ -464,58 +349,61 @@ TEST_F(RTreeTest, NodeOverlapIncreaseToAdd) {
expanded.Union(far_corner);
// Overlap of top should go from 1 to 4, as it will now cover the entire first
// row of pixels in middle.
- EXPECT_EQ(parent->OverlapIncreaseToAdd(far_corner, 0, expanded), 3);
+ EXPECT_EQ(3, NodeOverlapIncreaseToAdd(
+ parent.get(), far_corner, parent->child(0), expanded));
expanded = middle;
expanded.Union(far_corner);
// Overlap of middle should go from 2 to 8, as it will cover the rightmost 4
- // pixels of top and the top 4 pixles of bottom as it expands.
- EXPECT_EQ(parent->OverlapIncreaseToAdd(far_corner, 1, expanded), 6);
+ // pixels of top and the top 4 pixels of bottom as it expands.
+ EXPECT_EQ(6, NodeOverlapIncreaseToAdd(
+ parent.get(), far_corner, parent->child(1), expanded));
expanded = bottom;
expanded.Union(far_corner);
// Overlap of bottom should go from 1 to 4, as it will now cover the rightmost
// 4 pixels of middle.
- EXPECT_EQ(parent->OverlapIncreaseToAdd(far_corner, 2, expanded), 3);
+ EXPECT_EQ(3, NodeOverlapIncreaseToAdd(
+ parent.get(), far_corner, parent->child(2), expanded));
}
-TEST_F(RTreeTest, NodeBuildLowBounds) {
- ScopedVector<RTree::Node> nodes;
- nodes.reserve(10);
- for (int i = 1; i <= 10; ++i) {
- nodes.push_back(new RTree::Node(Rect(0, 0, i, i), i));
- }
- std::vector<Rect> vertical_bounds;
- std::vector<Rect> horizontal_bounds;
- RTree::Node::BuildLowBounds(
- nodes.get(), nodes.get(), &vertical_bounds, &horizontal_bounds);
+TEST_F(RTreeNodeTest, BuildLowBounds) {
+ RTreeNodes records;
+ records.reserve(10);
+ for (int i = 1; i <= 10; ++i)
+ records.push_back(new RTreeRecord(Rect(0, 0, i, i), i));
+
+ RTreeRects vertical_bounds;
+ RTreeRects horizontal_bounds;
+ NodeBuildLowBounds(
+ records.get(), records.get(), &vertical_bounds, &horizontal_bounds);
for (int i = 0; i < 10; ++i) {
- EXPECT_EQ(vertical_bounds[i], Rect(0, 0, i + 1, i + 1));
- EXPECT_EQ(horizontal_bounds[i], Rect(0, 0, i + 1, i + 1));
+ EXPECT_EQ(records[i]->rect(), vertical_bounds[i]);
+ EXPECT_EQ(records[i]->rect(), horizontal_bounds[i]);
}
}
-TEST_F(RTreeTest, NodeBuildHighBounds) {
- ScopedVector<RTree::Node> nodes;
- nodes.reserve(25);
- for (int i = 0; i < 25; ++i) {
- nodes.push_back(new RTree::Node(Rect(i, i, 25 - i, 25 - i), i));
- }
- std::vector<Rect> vertical_bounds;
- std::vector<Rect> horizontal_bounds;
- RTree::Node::BuildHighBounds(
- nodes.get(), nodes.get(), &vertical_bounds, &horizontal_bounds);
+TEST_F(RTreeNodeTest, BuildHighBounds) {
+ RTreeNodes records;
+ records.reserve(25);
+ for (int i = 0; i < 25; ++i)
+ records.push_back(new RTreeRecord(Rect(i, i, 25 - i, 25 - i), i));
+
+ RTreeRects vertical_bounds;
+ RTreeRects horizontal_bounds;
+ NodeBuildHighBounds(
+ records.get(), records.get(), &vertical_bounds, &horizontal_bounds);
for (int i = 0; i < 25; ++i) {
- EXPECT_EQ(vertical_bounds[i], Rect(i, i, 25 - i, 25 - i));
- EXPECT_EQ(horizontal_bounds[i], Rect(i, i, 25 - i, 25 - i));
+ EXPECT_EQ(records[i]->rect(), vertical_bounds[i]);
+ EXPECT_EQ(records[i]->rect(), horizontal_bounds[i]);
}
}
-TEST_F(RTreeTest, NodeChooseSplitAxisAndIndex) {
- std::vector<Rect> low_vertical_bounds;
- std::vector<Rect> high_vertical_bounds;
- std::vector<Rect> low_horizontal_bounds;
- std::vector<Rect> high_horizontal_bounds;
+TEST_F(RTreeNodeTest, ChooseSplitAxisAndIndexVertical) {
+ RTreeRects low_vertical_bounds;
+ RTreeRects high_vertical_bounds;
+ RTreeRects low_horizontal_bounds;
+ RTreeRects high_horizontal_bounds;
// In this test scenario we describe a mirrored, stacked configuration of
// horizontal, 1 pixel high rectangles labeled a-f like this:
//
@@ -538,9 +426,8 @@ TEST_F(RTreeTest, NodeChooseSplitAxisAndIndex) {
// Low bounds of horizontal sort start with bounds of box a and then jump to
// cover everything, as box f is second in horizontal sort.
low_horizontal_bounds.push_back(Rect(0, 0, 5, 1));
- for (int i = 0; i < 5; ++i) {
+ for (int i = 0; i < 5; ++i)
low_horizontal_bounds.push_back(Rect(0, 0, 5, 6));
- }
// High horizontal bounds are hand-calculated.
high_horizontal_bounds.push_back(Rect(0, 0, 5, 6));
@@ -550,18 +437,24 @@ TEST_F(RTreeTest, NodeChooseSplitAxisAndIndex) {
high_horizontal_bounds.push_back(Rect(2, 2, 1, 2));
high_horizontal_bounds.push_back(Rect(2, 3, 1, 1));
- // This should split vertically, right down the middle.
- EXPECT_TRUE(RTree::Node::ChooseSplitAxis(low_vertical_bounds,
- high_vertical_bounds,
- low_horizontal_bounds,
- high_horizontal_bounds,
- 2,
- 5));
- EXPECT_EQ(3U,
- RTree::Node::ChooseSplitIndex(
- 2, 5, low_vertical_bounds, high_vertical_bounds));
+ int smallest_vertical_margin =
+ NodeSmallestMarginSum(2, 3, low_vertical_bounds, high_vertical_bounds);
+ int smallest_horizontal_margin = NodeSmallestMarginSum(
+ 2, 3, low_horizontal_bounds, high_horizontal_bounds);
+ EXPECT_LT(smallest_vertical_margin, smallest_horizontal_margin);
+
+ EXPECT_EQ(
+ 3U,
+ NodeChooseSplitIndex(2, 5, low_vertical_bounds, high_vertical_bounds));
+}
- // We rotate the shape to test horizontal split axis detection:
+TEST_F(RTreeNodeTest, ChooseSplitAxisAndIndexHorizontal) {
+ RTreeRects low_vertical_bounds;
+ RTreeRects high_vertical_bounds;
+ RTreeRects low_horizontal_bounds;
+ RTreeRects high_horizontal_bounds;
+ // We rotate the shape from ChooseSplitAxisAndIndexVertical to test
+ // horizontal split axis detection:
//
// +--------+
// | a f |
@@ -574,18 +467,11 @@ TEST_F(RTreeTest, NodeChooseSplitAxisAndIndex) {
// h sort: | 012345 |
// +--------+
//
- // Clear out old bounds first.
- low_vertical_bounds.clear();
- high_vertical_bounds.clear();
- low_horizontal_bounds.clear();
- high_horizontal_bounds.clear();
-
// Low bounds of vertical sort start with bounds of box a and then jump to
// cover everything, as box f is second in vertical sort.
low_vertical_bounds.push_back(Rect(0, 0, 1, 5));
- for (int i = 0; i < 5; ++i) {
+ for (int i = 0; i < 5; ++i)
low_vertical_bounds.push_back(Rect(0, 0, 6, 5));
- }
// High vertical bounds are hand-calculated.
high_vertical_bounds.push_back(Rect(0, 0, 6, 5));
@@ -603,162 +489,178 @@ TEST_F(RTreeTest, NodeChooseSplitAxisAndIndex) {
high_horizontal_bounds.push_back(Rect(i, 0, 6 - i, 5));
}
- // This should split horizontally, right down the middle.
- EXPECT_FALSE(RTree::Node::ChooseSplitAxis(low_vertical_bounds,
- high_vertical_bounds,
- low_horizontal_bounds,
- high_horizontal_bounds,
- 2,
- 5));
+ int smallest_vertical_margin =
+ NodeSmallestMarginSum(2, 3, low_vertical_bounds, high_vertical_bounds);
+ int smallest_horizontal_margin = NodeSmallestMarginSum(
+ 2, 3, low_horizontal_bounds, high_horizontal_bounds);
+
+ EXPECT_GT(smallest_vertical_margin, smallest_horizontal_margin);
+
EXPECT_EQ(3U,
- RTree::Node::ChooseSplitIndex(
+ NodeChooseSplitIndex(
2, 5, low_horizontal_bounds, high_horizontal_bounds));
}
-TEST_F(RTreeTest, NodeDivideChildren) {
+TEST_F(RTreeNodeTest, DivideChildren) {
// Create a test node to split.
- scoped_ptr<RTree::Node> test_node(new RTree::Node(0));
- std::vector<RTree::Node*> sorted_children;
- std::vector<Rect> low_bounds;
- std::vector<Rect> high_bounds;
+ scoped_ptr<RTreeNode> test_node(new RTreeNode);
+ std::vector<RTreeNodeBase*> sorted_children;
+ RTreeRects low_bounds;
+ RTreeRects high_bounds;
// Insert 10 record nodes, also inserting them into our children array.
for (int i = 1; i <= 10; ++i) {
- RTree::Node* node = new RTree::Node(Rect(0, 0, i, i), i);
- test_node->AddChild(node);
- sorted_children.push_back(node);
+ scoped_ptr<RTreeRecord> record(new RTreeRecord(Rect(0, 0, i, i), i));
+ sorted_children.push_back(record.get());
+ test_node->AddChild(record.PassAs<RTreeNodeBase>());
low_bounds.push_back(Rect(0, 0, i, i));
high_bounds.push_back(Rect(0, 0, 10, 10));
}
// Split the children in half.
- scoped_ptr<RTree::Node> split_node(
- test_node->DivideChildren(low_bounds, high_bounds, sorted_children, 5));
+ scoped_ptr<RTreeNodeBase> split_node_base(NodeDivideChildren(
+ test_node.get(), low_bounds, high_bounds, sorted_children, 5));
+ RTreeNode* split_node = static_cast<RTreeNode*>(split_node_base.get());
// Both nodes should be valid.
ValidateNode(test_node.get(), 1U, 10U);
- ValidateNode(split_node.get(), 1U, 10U);
+ ValidateNode(split_node, 1U, 10U);
// Both nodes should have five children.
- EXPECT_EQ(test_node->children_.size(), 5U);
- EXPECT_EQ(split_node->children_.size(), 5U);
+ EXPECT_EQ(5U, test_node->count());
+ EXPECT_EQ(5U, split_node->count());
// Test node should have children 1-5, split node should have children 6-10.
for (int i = 0; i < 5; ++i) {
- EXPECT_EQ(test_node->children_[i]->key(), i + 1);
- EXPECT_EQ(split_node->children_[i]->key(), i + 6);
+ EXPECT_EQ(i + 1, record(test_node.get(), i)->key());
+ EXPECT_EQ(i + 6, record(split_node, i)->key());
}
}
-TEST_F(RTreeTest, NodeRemoveChildNoOrphans) {
- scoped_ptr<RTree::Node> test_parent(new RTree::Node(0));
- scoped_ptr<RTree::Node> child_one(new RTree::Node(Rect(0, 0, 1, 1), 1));
- scoped_ptr<RTree::Node> child_two(new RTree::Node(Rect(0, 0, 2, 2), 2));
- scoped_ptr<RTree::Node> child_three(new RTree::Node(Rect(0, 0, 3, 3), 3));
- test_parent->AddChild(child_one.get());
- test_parent->AddChild(child_two.get());
- test_parent->AddChild(child_three.get());
+TEST_F(RTreeNodeTest, RemoveChildNoOrphans) {
+ scoped_ptr<RTreeNode> test_parent(new RTreeNode);
+ test_parent->AddChild(
+ scoped_ptr<RTreeNodeBase>(new RTreeRecord(Rect(0, 0, 1, 1), 1)));
+ test_parent->AddChild(
+ scoped_ptr<RTreeNodeBase>(new RTreeRecord(Rect(0, 0, 2, 2), 2)));
+ test_parent->AddChild(
+ scoped_ptr<RTreeNodeBase>(new RTreeRecord(Rect(0, 0, 3, 3), 3)));
ValidateNode(test_parent.get(), 1U, 5U);
+
+ RTreeNodes orphans;
+
// Remove the middle node.
- ScopedVector<RTree::Node> orphans;
- EXPECT_EQ(test_parent->RemoveChild(child_two.get(), &orphans), 2U);
- EXPECT_EQ(orphans.size(), 0U);
- EXPECT_EQ(test_parent->count(), 2U);
- test_parent->RecomputeBoundsNoParents();
+ scoped_ptr<RTreeNodeBase> middle_child(
+ test_parent->RemoveChild(test_parent->child(1), &orphans));
+ EXPECT_EQ(0U, orphans.size());
+ EXPECT_EQ(2U, test_parent->count());
+ NodeRecomputeLocalBounds(test_parent.get());
ValidateNode(test_parent.get(), 1U, 5U);
+
// Remove the end node.
- EXPECT_EQ(test_parent->RemoveChild(child_three.get(), &orphans), 1U);
- EXPECT_EQ(orphans.size(), 0U);
- EXPECT_EQ(test_parent->count(), 1U);
- test_parent->RecomputeBoundsNoParents();
+ scoped_ptr<RTreeNodeBase> end_child(
+ test_parent->RemoveChild(test_parent->child(1), &orphans));
+ EXPECT_EQ(0U, orphans.size());
+ EXPECT_EQ(1U, test_parent->count());
+ NodeRecomputeLocalBounds(test_parent.get());
ValidateNode(test_parent.get(), 1U, 5U);
+
// Remove the first node.
- EXPECT_EQ(test_parent->RemoveChild(child_one.get(), &orphans), 0U);
- EXPECT_EQ(orphans.size(), 0U);
- EXPECT_EQ(test_parent->count(), 0U);
+ scoped_ptr<RTreeNodeBase> first_child(
+ test_parent->RemoveChild(test_parent->child(0), &orphans));
+ EXPECT_EQ(0U, orphans.size());
+ EXPECT_EQ(0U, test_parent->count());
}
-TEST_F(RTreeTest, NodeRemoveChildOrphans) {
- // Build flattened binary tree of Nodes 4 deep, from the record nodes up.
- ScopedVector<RTree::Node> nodes;
- nodes.resize(15);
- // Indicies 7 through 15 are record nodes.
- for (int i = 7; i < 15; ++i) {
- nodes[i] = new RTree::Node(Rect(0, 0, i, i), i);
- }
- // Nodes 3 through 6 are level 0 (leaves) and get 2 record nodes each.
- for (int i = 3; i < 7; ++i) {
- nodes[i] = new RTree::Node(0);
- nodes[i]->AddChild(nodes[(i * 2) + 1]);
- nodes[i]->AddChild(nodes[(i * 2) + 2]);
- }
- // Nodes 1 and 2 are level 1 and get 2 leaves each.
- for (int i = 1; i < 3; ++i) {
- nodes[i] = new RTree::Node(1);
- nodes[i]->AddChild(nodes[(i * 2) + 1]);
- nodes[i]->AddChild(nodes[(i * 2) + 2]);
- }
- // Node 0 is level 2 and gets 2 childen.
- nodes[0] = new RTree::Node(2);
- nodes[0]->AddChild(nodes[1]);
- nodes[0]->AddChild(nodes[2]);
- // This should now be a valid node structure.
- ValidateNode(nodes[0], 2U, 2U);
-
- // Now remove the level 0 nodes, so we get the record nodes as orphans.
- ScopedVector<RTree::Node> orphans;
- EXPECT_EQ(nodes[1]->RemoveChild(nodes[3], &orphans), 1U);
- EXPECT_EQ(nodes[1]->RemoveChild(nodes[4], &orphans), 0U);
- EXPECT_EQ(nodes[2]->RemoveChild(nodes[5], &orphans), 1U);
- EXPECT_EQ(nodes[2]->RemoveChild(nodes[6], &orphans), 0U);
-
- // Orphans should be nodes 7 through 15 in order.
- EXPECT_EQ(orphans.size(), 8U);
- for (int i = 0; i < 8; ++i) {
- EXPECT_EQ(orphans[i], nodes[i + 7]);
- }
-
- // Now we remove nodes 1 and 2 from the root, expecting no further orphans.
- // This prevents a crash due to double-delete on test exit, as no node should
- // own any other node right now.
- EXPECT_EQ(nodes[0]->RemoveChild(nodes[1], &orphans), 1U);
- EXPECT_EQ(orphans.size(), 8U);
- EXPECT_EQ(nodes[0]->RemoveChild(nodes[2], &orphans), 0U);
- EXPECT_EQ(orphans.size(), 8U);
-
- // Prevent double-delete of nodes by both nodes and orphans.
- orphans.weak_clear();
+TEST_F(RTreeNodeTest, RemoveChildOrphans) {
+ // Build binary tree of Nodes of height 4, keeping weak pointers to the
+ // Levels 0 and 1 Nodes and the Records so we can test removal of them below.
+ std::vector<RTreeNode*> level_1_children;
+ std::vector<RTreeNode*> level_0_children;
+ std::vector<RTreeRecord*> records;
+ int id = 1;
+ scoped_ptr<RTreeNode> root(NewNodeAtLevel(2));
+ for (int i = 0; i < 2; ++i) {
+ scoped_ptr<RTreeNode> level_1_child(NewNodeAtLevel(1));
+ for (int j = 0; j < 2; ++j) {
+ scoped_ptr<RTreeNode> level_0_child(new RTreeNode);
+ for (int k = 0; k < 2; ++k) {
+ scoped_ptr<RTreeRecord> record(
+ new RTreeRecord(Rect(0, 0, id, id), id));
+ ++id;
+ records.push_back(record.get());
+ level_0_child->AddChild(record.PassAs<RTreeNodeBase>());
+ }
+ level_0_children.push_back(level_0_child.get());
+ level_1_child->AddChild(level_0_child.PassAs<RTreeNodeBase>());
+ }
+ level_1_children.push_back(level_1_child.get());
+ root->AddChild(level_1_child.PassAs<RTreeNodeBase>());
+ }
+
+ // This should now be a valid tree structure.
+ ValidateNode(root.get(), 2U, 2U);
+ EXPECT_EQ(2U, level_1_children.size());
+ EXPECT_EQ(4U, level_0_children.size());
+ EXPECT_EQ(8U, records.size());
+
+ // Now remove all of the level 0 nodes so we get the record nodes as orphans.
+ RTreeNodes orphans;
+ for (size_t i = 0; i < level_0_children.size(); ++i)
+ level_1_children[i / 2]->RemoveChild(level_0_children[i], &orphans);
+
+ // Orphans should be all 8 records but no order guarantee.
+ EXPECT_EQ(8U, orphans.size());
+ for (std::vector<RTreeRecord*>::iterator it = records.begin();
+ it != records.end(); ++it) {
+ RTreeNodes::iterator orphan =
+ std::find(orphans.begin(), orphans.end(), *it);
+ EXPECT_NE(orphan, orphans.end());
+ orphans.erase(orphan);
+ }
+ EXPECT_EQ(0U, orphans.size());
}
-TEST_F(RTreeTest, NodeRemoveAndReturnLastChild) {
- scoped_ptr<RTree::Node> test_parent(new RTree::Node(0));
- scoped_ptr<RTree::Node> child_one(new RTree::Node(Rect(0, 0, 1, 1), 1));
- scoped_ptr<RTree::Node> child_two(new RTree::Node(Rect(0, 0, 2, 2), 2));
- scoped_ptr<RTree::Node> child_three(new RTree::Node(Rect(0, 0, 3, 3), 3));
- test_parent->AddChild(child_one.get());
- test_parent->AddChild(child_two.get());
- test_parent->AddChild(child_three.get());
+TEST_F(RTreeNodeTest, RemoveAndReturnLastChild) {
+ scoped_ptr<RTreeNode> test_parent(new RTreeNode);
+ test_parent->AddChild(
+ scoped_ptr<RTreeNodeBase>(new RTreeRecord(Rect(0, 0, 1, 1), 1)));
+ test_parent->AddChild(
+ scoped_ptr<RTreeNodeBase>(new RTreeRecord(Rect(0, 0, 2, 2), 2)));
+ test_parent->AddChild(
+ scoped_ptr<RTreeNodeBase>(new RTreeRecord(Rect(0, 0, 3, 3), 3)));
ValidateNode(test_parent.get(), 1U, 5U);
- EXPECT_EQ(test_parent->RemoveAndReturnLastChild().release(),
- child_three.get());
- EXPECT_EQ(test_parent->count(), 2U);
- test_parent->RecomputeBoundsNoParents();
+ RTreeNodeBase* child = test_parent->child(2);
+ scoped_ptr<RTreeNodeBase> last_child(test_parent->RemoveAndReturnLastChild());
+ EXPECT_EQ(child, last_child.get());
+ EXPECT_EQ(2U, test_parent->count());
+ NodeRecomputeLocalBounds(test_parent.get());
ValidateNode(test_parent.get(), 1U, 5U);
- EXPECT_EQ(test_parent->RemoveAndReturnLastChild().release(), child_two.get());
- EXPECT_EQ(test_parent->count(), 1U);
- test_parent->RecomputeBoundsNoParents();
+ child = test_parent->child(1);
+ scoped_ptr<RTreeNodeBase> middle_child(
+ test_parent->RemoveAndReturnLastChild());
+ EXPECT_EQ(child, middle_child.get());
+ EXPECT_EQ(1U, test_parent->count());
+ NodeRecomputeLocalBounds(test_parent.get());
ValidateNode(test_parent.get(), 1U, 5U);
- EXPECT_EQ(test_parent->RemoveAndReturnLastChild().release(), child_one.get());
- EXPECT_EQ(test_parent->count(), 0U);
+ child = test_parent->child(0);
+ scoped_ptr<RTreeNodeBase> first_child(
+ test_parent->RemoveAndReturnLastChild());
+ EXPECT_EQ(child, first_child.get());
+ EXPECT_EQ(0U, test_parent->count());
}
-TEST_F(RTreeTest, NodeLeastOverlapIncrease) {
- scoped_ptr<RTree::Node> test_parent(new RTree::Node(0));
- // Construct 4 nodes with 1x2 retangles spaced horizontally 1 pixel apart, or:
+TEST_F(RTreeNodeTest, LeastOverlapIncrease) {
+ scoped_ptr<RTreeNode> test_parent(NewNodeAtLevel(1));
+ // Construct 4 nodes with 1x2 rects spaced horizontally 1 pixel apart, or:
//
// a b c d
// a b c d
//
for (int i = 0; i < 4; ++i) {
- test_parent->AddChild(new RTree::Node(Rect(i * 2, 0, 1, 2), i + 1));
+ scoped_ptr<RTreeNode> node(new RTreeNode);
+ scoped_ptr<RTreeRecord> record(
+ new RTreeRecord(Rect(i * 2, 0, 1, 2), i + 1));
+ node->AddChild(record.PassAs<RTreeNodeBase>());
+ test_parent->AddChild(node.PassAs<RTreeNodeBase>());
}
ValidateNode(test_parent.get(), 1U, 5U);
@@ -770,11 +672,11 @@ TEST_F(RTreeTest, NodeLeastOverlapIncrease) {
// a b c d
//
Rect test_rect_far(7, 0, 1, 1);
- std::vector<Rect> expanded_rects;
+ RTreeRects expanded_rects;
BuildExpandedRects(test_parent.get(), test_rect_far, &expanded_rects);
- RTree::Node* result =
- test_parent->LeastOverlapIncrease(test_rect_far, expanded_rects);
- EXPECT_EQ(result->key(), 4);
+ RTreeNode* result = NodeLeastOverlapIncrease(
+ test_parent.get(), test_rect_far, expanded_rects);
+ EXPECT_EQ(4, record(result, 0)->key());
// Test rect covering the bottom half of all children should be a 4-way tie,
// so LeastOverlapIncrease should return NULL:
@@ -784,7 +686,8 @@ TEST_F(RTreeTest, NodeLeastOverlapIncrease) {
//
Rect test_rect_tie(0, 1, 7, 1);
BuildExpandedRects(test_parent.get(), test_rect_tie, &expanded_rects);
- result = test_parent->LeastOverlapIncrease(test_rect_tie, expanded_rects);
+ result = NodeLeastOverlapIncrease(
+ test_parent.get(), test_rect_tie, expanded_rects);
EXPECT_TRUE(result == NULL);
// Test rect completely inside c should return the third rectangle:
@@ -794,8 +697,9 @@ TEST_F(RTreeTest, NodeLeastOverlapIncrease) {
//
Rect test_rect_inside(4, 0, 1, 1);
BuildExpandedRects(test_parent.get(), test_rect_inside, &expanded_rects);
- result = test_parent->LeastOverlapIncrease(test_rect_inside, expanded_rects);
- EXPECT_EQ(result->key(), 3);
+ result = NodeLeastOverlapIncrease(
+ test_parent.get(), test_rect_inside, expanded_rects);
+ EXPECT_EQ(3, record(result, 0)->key());
// Add a rectangle that overlaps completely with rectangle c, to test
// when there is a tie between two completely contained rectangles:
@@ -803,24 +707,40 @@ TEST_F(RTreeTest, NodeLeastOverlapIncrease) {
// a b Ted
// a b eed
//
- test_parent->AddChild(new RTree::Node(Rect(4, 0, 2, 2), 9));
+ scoped_ptr<RTreeNode> record_parent(new RTreeNode);
+ record_parent->AddChild(
+ scoped_ptr<RTreeNodeBase>(new RTreeRecord(Rect(4, 0, 2, 2), 9)));
+ test_parent->AddChild(record_parent.PassAs<RTreeNodeBase>());
BuildExpandedRects(test_parent.get(), test_rect_inside, &expanded_rects);
- result = test_parent->LeastOverlapIncrease(test_rect_inside, expanded_rects);
+ result = NodeLeastOverlapIncrease(
+ test_parent.get(), test_rect_inside, expanded_rects);
EXPECT_TRUE(result == NULL);
}
-TEST_F(RTreeTest, NodeLeastAreaEnlargement) {
- scoped_ptr<RTree::Node> test_parent(new RTree::Node(0));
+TEST_F(RTreeNodeTest, LeastAreaEnlargement) {
+ scoped_ptr<RTreeNode> test_parent(NewNodeAtLevel(1));
// Construct 4 nodes in a cross-hairs style configuration:
//
// a
// b c
// d
//
- test_parent->AddChild(new RTree::Node(Rect(1, 0, 1, 1), 1));
- test_parent->AddChild(new RTree::Node(Rect(0, 1, 1, 1), 2));
- test_parent->AddChild(new RTree::Node(Rect(2, 1, 1, 1), 3));
- test_parent->AddChild(new RTree::Node(Rect(1, 2, 1, 1), 4));
+ scoped_ptr<RTreeNode> node(new RTreeNode);
+ node->AddChild(
+ scoped_ptr<RTreeNodeBase>(new RTreeRecord(Rect(1, 0, 1, 1), 1)));
+ test_parent->AddChild(node.PassAs<RTreeNodeBase>());
+ node.reset(new RTreeNode);
+ node->AddChild(
+ scoped_ptr<RTreeNodeBase>(new RTreeRecord(Rect(0, 1, 1, 1), 2)));
+ test_parent->AddChild(node.PassAs<RTreeNodeBase>());
+ node.reset(new RTreeNode);
+ node->AddChild(
+ scoped_ptr<RTreeNodeBase>(new RTreeRecord(Rect(2, 1, 1, 1), 3)));
+ test_parent->AddChild(node.PassAs<RTreeNodeBase>());
+ node.reset(new RTreeNode);
+ node->AddChild(
+ scoped_ptr<RTreeNodeBase>(new RTreeRecord(Rect(1, 2, 1, 1), 4)));
+ test_parent->AddChild(node.PassAs<RTreeNodeBase>());
ValidateNode(test_parent.get(), 1U, 5U);
@@ -832,11 +752,11 @@ TEST_F(RTreeTest, NodeLeastAreaEnlargement) {
// T
//
Rect test_rect_below(1, 3, 1, 1);
- std::vector<Rect> expanded_rects;
+ RTreeRects expanded_rects;
BuildExpandedRects(test_parent.get(), test_rect_below, &expanded_rects);
- RTree::Node* result =
- test_parent->LeastAreaEnlargement(test_rect_below, expanded_rects);
- EXPECT_EQ(result->key(), 4);
+ RTreeNode* result = NodeLeastAreaEnlargement(
+ test_parent.get(), test_rect_below, expanded_rects);
+ EXPECT_EQ(4, record(result, 0)->key());
// Test rect completely inside b should require minimum area to add to Node b:
//
@@ -846,8 +766,9 @@ TEST_F(RTreeTest, NodeLeastAreaEnlargement) {
//
Rect test_rect_inside(0, 1, 1, 1);
BuildExpandedRects(test_parent.get(), test_rect_inside, &expanded_rects);
- result = test_parent->LeastAreaEnlargement(test_rect_inside, expanded_rects);
- EXPECT_EQ(result->key(), 2);
+ result = NodeLeastAreaEnlargement(
+ test_parent.get(), test_rect_inside, expanded_rects);
+ EXPECT_EQ(2, record(result, 0)->key());
// Add e at (0, 1) to overlap b and c, to test tie-breaking:
//
@@ -855,7 +776,10 @@ TEST_F(RTreeTest, NodeLeastAreaEnlargement) {
// eee
// d
//
- test_parent->AddChild(new RTree::Node(Rect(0, 1, 3, 1), 7));
+ node.reset(new RTreeNode);
+ node->AddChild(
+ scoped_ptr<RTreeNodeBase>(new RTreeRecord(Rect(0, 1, 3, 1), 7)));
+ test_parent->AddChild(node.PassAs<RTreeNodeBase>());
ValidateNode(test_parent.get(), 1U, 5U);
@@ -869,9 +793,233 @@ TEST_F(RTreeTest, NodeLeastAreaEnlargement) {
//
Rect test_rect_tie_breaker(3, 1, 1, 1);
BuildExpandedRects(test_parent.get(), test_rect_tie_breaker, &expanded_rects);
- result =
- test_parent->LeastAreaEnlargement(test_rect_tie_breaker, expanded_rects);
- EXPECT_EQ(result->key(), 3);
+ result = NodeLeastAreaEnlargement(
+ test_parent.get(), test_rect_tie_breaker, expanded_rects);
+ EXPECT_EQ(3, record(result, 0)->key());
+}
+
+// RTreeTest ------------------------------------------------------------------
+
+// An empty RTree should never return AppendIntersectingRecords results, and
+// RTrees should be empty upon construction.
+TEST_F(RTreeTest, AppendIntersectingRecordsOnEmptyTree) {
+ RT rt(2, 10);
+ ValidateRTree(&rt);
+ RT::Matches results;
+ Rect test_rect(25, 25);
+ rt.AppendIntersectingRecords(test_rect, &results);
+ EXPECT_EQ(0U, results.size());
+ ValidateRTree(&rt);
+}
+
+// Clear should empty the tree, meaning that all queries should not return
+// results after.
+TEST_F(RTreeTest, ClearEmptiesTreeOfSingleNode) {
+ RT rt(2, 5);
+ rt.Insert(Rect(0, 0, 100, 100), 1);
+ rt.Clear();
+ RT::Matches results;
+ Rect test_rect(1, 1);
+ rt.AppendIntersectingRecords(test_rect, &results);
+ EXPECT_EQ(0U, results.size());
+ ValidateRTree(&rt);
+}
+
+// Even with a complex internal structure, clear should empty the tree, meaning
+// that all queries should not return results after.
+TEST_F(RTreeTest, ClearEmptiesTreeOfManyNodes) {
+ RT rt(2, 5);
+ AddStackedSquares(&rt, 100);
+ rt.Clear();
+ RT::Matches results;
+ Rect test_rect(1, 1);
+ rt.AppendIntersectingRecords(test_rect, &results);
+ EXPECT_EQ(0U, results.size());
+ ValidateRTree(&rt);
+}
+
+// Duplicate inserts should overwrite previous inserts.
+TEST_F(RTreeTest, DuplicateInsertsOverwrite) {
+ RT rt(2, 5);
+ // Add 100 stacked squares, but always with duplicate key of 0.
+ for (int i = 1; i <= 100; ++i) {
+ rt.Insert(Rect(0, 0, i, i), 0);
+ ValidateRTree(&rt);
+ }
+ RT::Matches results;
+ Rect test_rect(1, 1);
+ rt.AppendIntersectingRecords(test_rect, &results);
+ EXPECT_EQ(1U, results.size());
+ EXPECT_EQ(1U, results.count(0));
+}
+
+// Call Remove() once on something that's been inserted repeatedly.
+TEST_F(RTreeTest, DuplicateInsertRemove) {
+ RT rt(3, 9);
+ AddStackedSquares(&rt, 25);
+ for (int i = 1; i <= 100; ++i) {
+ rt.Insert(Rect(0, 0, i, i), 26);
+ ValidateRTree(&rt);
+ }
+ rt.Remove(26);
+ RT::Matches results;
+ Rect test_rect(1, 1);
+ rt.AppendIntersectingRecords(test_rect, &results);
+ EXPECT_EQ(25U, results.size());
+ VerifyAllKeys(results);
+}
+
+// Call Remove() repeatedly on something that's been inserted once.
+TEST_F(RTreeTest, InsertDuplicateRemove) {
+ RT rt(7, 15);
+ AddStackedSquares(&rt, 101);
+ for (int i = 0; i < 100; ++i) {
+ rt.Remove(101);
+ ValidateRTree(&rt);
+ }
+ RT::Matches results;
+ Rect test_rect(1, 1);
+ rt.AppendIntersectingRecords(test_rect, &results);
+ EXPECT_EQ(100U, results.size());
+ VerifyAllKeys(results);
+}
+
+// Stacked rects should meet all matching queries regardless of nesting.
+TEST_F(RTreeTest, AppendIntersectingRecordsStackedSquaresNestedHit) {
+ RT rt(2, 5);
+ AddStackedSquares(&rt, 100);
+ RT::Matches results;
+ Rect test_rect(1, 1);
+ rt.AppendIntersectingRecords(test_rect, &results);
+ EXPECT_EQ(100U, results.size());
+ VerifyAllKeys(results);
+}
+
+// Stacked rects should meet all matching queries when contained completely by
+// the query rectangle.
+TEST_F(RTreeTest, AppendIntersectingRecordsStackedSquaresContainedHit) {
+ RT rt(2, 10);
+ AddStackedSquares(&rt, 100);
+ RT::Matches results;
+ Rect test_rect(0, 0, 100, 100);
+ rt.AppendIntersectingRecords(test_rect, &results);
+ EXPECT_EQ(100U, results.size());
+ VerifyAllKeys(results);
+}
+
+// Stacked rects should miss a missing query when the query has no intersection
+// with the rects.
+TEST_F(RTreeTest, AppendIntersectingRecordsStackedSquaresCompleteMiss) {
+ RT rt(2, 7);
+ AddStackedSquares(&rt, 100);
+ RT::Matches results;
+ Rect test_rect(150, 150, 100, 100);
+ rt.AppendIntersectingRecords(test_rect, &results);
+ EXPECT_EQ(0U, results.size());
+}
+
+// Removing half the nodes after insertion should still result in a valid tree.
+TEST_F(RTreeTest, RemoveHalfStackedRects) {
+ RT rt(2, 11);
+ AddStackedSquares(&rt, 200);
+ for (int i = 101; i <= 200; ++i) {
+ rt.Remove(i);
+ ValidateRTree(&rt);
+ }
+ RT::Matches results;
+ Rect test_rect(1, 1);
+ rt.AppendIntersectingRecords(test_rect, &results);
+ EXPECT_EQ(100U, results.size());
+ VerifyAllKeys(results);
+
+ // Add the nodes back in.
+ for (int i = 101; i <= 200; ++i) {
+ rt.Insert(Rect(0, 0, i, i), i);
+ ValidateRTree(&rt);
+ }
+ results.clear();
+ rt.AppendIntersectingRecords(test_rect, &results);
+ EXPECT_EQ(200U, results.size());
+ VerifyAllKeys(results);
+}
+
+TEST_F(RTreeTest, InsertDupToRoot) {
+ RT rt(2, 5);
+ rt.Insert(Rect(0, 0, 1, 2), 1);
+ ValidateRTree(&rt);
+ rt.Insert(Rect(0, 0, 2, 1), 1);
+ ValidateRTree(&rt);
+}
+
+TEST_F(RTreeTest, InsertNegativeCoordsRect) {
+ RT rt(5, 11);
+ for (int i = 1; i <= 100; ++i) {
+ rt.Insert(Rect(-i, -i, i, i), (i * 2) - 1);
+ ValidateRTree(&rt);
+ rt.Insert(Rect(0, 0, i, i), i * 2);
+ ValidateRTree(&rt);
+ }
+ RT::Matches results;
+ Rect test_rect(-1, -1, 2, 2);
+ rt.AppendIntersectingRecords(test_rect, &results);
+ EXPECT_EQ(200U, results.size());
+ VerifyAllKeys(results);
+}
+
+TEST_F(RTreeTest, RemoveNegativeCoordsRect) {
+ RT rt(7, 21);
+
+ // Add 100 positive stacked squares.
+ AddStackedSquares(&rt, 100);
+
+ // Now add 100 negative stacked squares.
+ for (int i = 101; i <= 200; ++i) {
+ rt.Insert(Rect(100 - i, 100 - i, i - 100, i - 100), 301 - i);
+ ValidateRTree(&rt);
+ }
+
+ // Now remove half of the negative squares.
+ for (int i = 101; i <= 150; ++i) {
+ rt.Remove(301 - i);
+ ValidateRTree(&rt);
+ }
+
+ // Queries should return 100 positive and 50 negative stacked squares.
+ RT::Matches results;
+ Rect test_rect(-1, -1, 2, 2);
+ rt.AppendIntersectingRecords(test_rect, &results);
+ EXPECT_EQ(150U, results.size());
+ VerifyAllKeys(results);
+}
+
+TEST_F(RTreeTest, InsertEmptyRectReplacementRemovesKey) {
+ RT rt(10, 31);
+ AddStackedSquares(&rt, 50);
+ ValidateRTree(&rt);
+
+ // Replace last square with empty rect.
+ rt.Insert(Rect(), 50);
+ ValidateRTree(&rt);
+
+ // Now query large area to get all rects in tree.
+ RT::Matches results;
+ Rect test_rect(0, 0, 100, 100);
+ rt.AppendIntersectingRecords(test_rect, &results);
+
+ // Should only be 49 rects in tree.
+ EXPECT_EQ(49U, results.size());
+ VerifyAllKeys(results);
+}
+
+TEST_F(RTreeTest, InsertReplacementMaintainsTree) {
+ RT rt(2, 5);
+ AddStackedSquares(&rt, 100);
+ ValidateRTree(&rt);
+
+ for (int i = 1; i <= 100; ++i) {
+ rt.Insert(Rect(0, 0, 0, 0), i);
+ ValidateRTree(&rt);
+ }
}
} // namespace gfx
« no previous file with comments | « ui/gfx/geometry/r_tree_base.cc ('k') | ui/gfx/gfx.gyp » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698