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

Side by Side Diff: ui/gfx/geometry/r_tree_unittest.cc

Issue 269513002: readability review for luken (Closed) Base URL: https://chromium.googlesource.com/chromium/src.git@master
Patch Set: clang repairs 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 unified diff | 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 »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
1 // Copyright 2014 The Chromium Authors. All rights reserved. 1 // Copyright 2014 The Chromium Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be 2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file. 3 // found in the LICENSE file.
4 4
5 #include "testing/gtest/include/gtest/gtest.h" 5 #include "testing/gtest/include/gtest/gtest.h"
6 #include "ui/gfx/geometry/r_tree.h" 6 #include "ui/gfx/geometry/r_tree.h"
7 #include "ui/gfx/geometry/r_tree_base.h"
7 #include "ui/gfx/geometry/rect.h" 8 #include "ui/gfx/geometry/rect.h"
8 9
9 namespace gfx { 10 namespace gfx {
10 11
11 class RTreeTest : public ::testing::Test { 12 class RTreeTest : public ::testing::Test {
12 protected: 13 protected:
13 // Given a pointer to an RTree, traverse it and verify its internal structure 14 typedef RTree<int> RT;
14 // is consistent with the RTree semantics. 15
15 void ValidateRTree(RTree* rt) { 16 // Given a pointer to an RTree, traverse it and verify that its internal
17 // structure is consistent with RTree semantics.
18 void ValidateRTree(RTreeBase* rt) {
16 // If RTree is empty it should have an empty rectangle. 19 // If RTree is empty it should have an empty rectangle.
17 if (!rt->root_->count()) { 20 if (!rt->root()->count()) {
18 EXPECT_TRUE(rt->root_->rect().IsEmpty()); 21 EXPECT_TRUE(rt->root()->rect().IsEmpty());
19 EXPECT_EQ(rt->root_->level(), 0); 22 EXPECT_EQ(0, rt->root()->Level());
20 return; 23 return;
21 } 24 }
22 // Root is allowed to have fewer than min_children_ but never more than 25 // Root is allowed to have fewer than min_children_ but never more than
23 // max_children_. 26 // max_children_.
24 EXPECT_LE(rt->root_->count(), rt->max_children_); 27 EXPECT_LE(rt->root()->count(), rt->max_children_);
25 // The root should never be a record node. 28 // The root should never be a record node.
26 EXPECT_GT(rt->root_->level(), -1); 29 EXPECT_GT(rt->root()->Level(), -1);
27 EXPECT_FALSE(rt->root_->key());
28 // The root should never have a parent pointer. 30 // The root should never have a parent pointer.
29 EXPECT_FALSE(rt->root_->parent()); 31 EXPECT_TRUE(rt->root()->parent() == NULL);
30 // Bounds must be consistent on the root. 32 // Bounds must be consistent on the root.
31 CheckBoundsConsistent(rt->root_.get()); 33 CheckBoundsConsistent(rt->root());
32 // We traverse root's children ourselves, so we can avoid asserts about 34 for (size_t i = 0; i < rt->root()->count(); ++i) {
33 // root's potential inconsistencies.
34 for (size_t i = 0; i < rt->root_->children_.size(); ++i) {
35 ValidateNode( 35 ValidateNode(
36 rt->root_->children_[i], rt->min_children_, rt->max_children_); 36 rt->root()->child(i), rt->min_children_, rt->max_children_);
37 } 37 }
38 } 38 }
39 39
40 // Recursive descent method used by ValidateRTree to check each node within 40 // Recursive descent method used by ValidateRTree to check each node within
41 // the RTree for consistency with RTree semantics. 41 // the RTree for consistency with RTree semantics.
42 void ValidateNode(RTree::Node* node, 42 void ValidateNode(const RTreeBase::NodeBase* node_base,
43 size_t min_children, 43 size_t min_children,
44 size_t max_children) { 44 size_t max_children) {
45 // Record nodes have different requirements, handle up front. 45 if (node_base->Level() >= 0) {
46 if (node->level() == -1) { 46 const RTreeBase::Node* node =
47 // Record nodes may have no children. 47 static_cast<const RTreeBase::Node*>(node_base);
48 EXPECT_EQ(node->count(), 0U); 48 EXPECT_GE(node->count(), min_children);
49 // They must have an associated non-NULL key. 49 EXPECT_LE(node->count(), max_children);
50 EXPECT_TRUE(node->key()); 50 CheckBoundsConsistent(node);
51 // They must always have a parent. 51 for (size_t i = 0; i < node->count(); ++i)
52 EXPECT_TRUE(node->parent()); 52 ValidateNode(node->child(i), min_children, max_children);
53 return;
54 }
55 // Non-record node, normal expectations apply.
56 EXPECT_GE(node->count(), min_children);
57 EXPECT_LE(node->count(), max_children);
58 EXPECT_EQ(node->key(), 0);
59 CheckBoundsConsistent(node);
60 for (size_t i = 0; i < node->children_.size(); ++i) {
61 ValidateNode(node->children_[i], min_children, max_children);
62 } 53 }
63 } 54 }
64 55
65 // Check bounds are consistent with children bounds, and other checks 56 // Check bounds are consistent with children bounds, and other checks
66 // convenient to do while enumerating the children of node. 57 // convenient to do while enumerating the children of node.
67 void CheckBoundsConsistent(RTree::Node* node) { 58 void CheckBoundsConsistent(const RTreeBase::Node* node) {
68 EXPECT_FALSE(node->rect_.IsEmpty()); 59 EXPECT_FALSE(node->rect().IsEmpty());
69 Rect check_bounds; 60 Rect check_bounds;
70 for (size_t i = 0; i < node->children_.size(); ++i) { 61 for (size_t i = 0; i < node->count(); ++i) {
71 RTree::Node* child_node = node->children_[i]; 62 const RTreeBase::NodeBase* child_node = node->child(i);
72 check_bounds.Union(child_node->rect()); 63 check_bounds.Union(child_node->rect());
73 EXPECT_EQ(node->level() - 1, child_node->level()); 64 EXPECT_EQ(node->Level() - 1, child_node->Level());
74 EXPECT_EQ(node, child_node->parent()); 65 EXPECT_EQ(node, child_node->parent());
75 } 66 }
76 EXPECT_EQ(node->rect_, check_bounds); 67 EXPECT_EQ(check_bounds, node->rect());
77 } 68 }
78 69
79 // Adds count squares stacked around the point (0,0) with key equal to width. 70 // Adds count squares stacked around the point (0,0) with key equal to width.
80 void AddStackedSquares(RTree* rt, int count) { 71 void AddStackedSquares(RT* rt, int count) {
81 for (int i = 1; i <= count; ++i) { 72 for (int i = 1; i <= count; ++i) {
82 rt->Insert(Rect(0, 0, i, i), i); 73 rt->Insert(Rect(0, 0, i, i), i);
83 ValidateRTree(rt); 74 ValidateRTree(static_cast<RTreeBase*>(rt));
84 } 75 }
85 } 76 }
86 77
87 // Given an unordered list of matching keys, verify that it contains all 78 // Given an unordered list of matching keys, verifies that it contains all
88 // values [1..length] for the length of that list. 79 // values [1..length] for the length of that list.
89 void VerifyAllKeys(const base::hash_set<intptr_t>& keys) { 80 void VerifyAllKeys(const RT::Matches& keys) {
90 // Verify that the keys are in values [1,count]. 81 for (size_t i = 1; i <= keys.size(); ++i)
91 for (size_t i = 1; i <= keys.size(); ++i) { 82 EXPECT_EQ(1U, keys.count(i));
92 EXPECT_EQ(keys.count(i), 1U);
93 }
94 } 83 }
95 84
96 // Given a node and a rectangle, builds an expanded rectangle list where the 85 // Given a node and a rectangle, builds an expanded rectangle list where the
97 // ith element of the rectangle is union of the recangle of the ith child of 86 // ith element of the vector is the union of the rectangle of the ith child of
98 // the node and the argument rectangle. 87 // the node and the argument rectangle.
99 void BuildExpandedRects(RTree::Node* node, 88 void BuildExpandedRects(RTreeBase::Node* node,
100 const Rect& rect, 89 const Rect& rect,
101 std::vector<Rect>* expanded_rects) { 90 std::vector<Rect>* expanded_rects) {
102 expanded_rects->clear(); 91 expanded_rects->clear();
103 expanded_rects->reserve(node->children_.size()); 92 expanded_rects->reserve(node->count());
104 for (size_t i = 0; i < node->children_.size(); ++i) { 93 for (size_t i = 0; i < node->count(); ++i) {
105 Rect expanded_rect(rect); 94 Rect expanded_rect(rect);
106 expanded_rect.Union(node->children_[i]->rect_); 95 expanded_rect.Union(node->child(i)->rect());
107 expanded_rects->push_back(expanded_rect); 96 expanded_rects->push_back(expanded_rect);
108 } 97 }
109 } 98 }
110 }; 99 };
111 100
112 // An empty RTree should never return Query results, and RTrees should be empty 101 class RTreeNodeTest : public RTreeTest {
113 // upon construction. 102 protected:
114 TEST_F(RTreeTest, QueryEmptyTree) { 103 typedef RTreeBase::NodeBase RTreeNodeBase;
115 RTree rt(2, 10); 104 typedef RT::Record RTreeRecord;
116 ValidateRTree(&rt); 105 typedef RTreeBase::Node RTreeNode;
117 base::hash_set<intptr_t> results; 106 typedef RTreeBase::Node::Rects RTreeRects;
118 Rect test_rect(25, 25); 107 typedef RTreeBase::Nodes RTreeNodes;
119 rt.Query(test_rect, &results); 108
120 EXPECT_EQ(results.size(), 0U); 109 // Accessors to private members of RTree::Node.
121 ValidateRTree(&rt); 110 const RTreeRecord* record(RTreeNode* node, size_t i) {
122 } 111 return static_cast<const RTreeRecord*>(node->child(i));
123 112 }
124 // Clear should empty the tree, meaning that all queries should not return 113
125 // results after. 114 // Provides access for tests to private methods of RTree::Node.
126 TEST_F(RTreeTest, ClearEmptiesTreeOfSingleNode) { 115 scoped_ptr<RTreeNode> NewNodeAtLevel(size_t level) {
127 RTree rt(2, 5); 116 return make_scoped_ptr(new RTreeBase::Node(level));
128 rt.Insert(Rect(0, 0, 100, 100), 1); 117 }
129 rt.Clear(); 118
130 base::hash_set<intptr_t> results; 119 void NodeRecomputeLocalBounds(RTreeNodeBase* node) {
131 Rect test_rect(1, 1); 120 node->RecomputeLocalBounds();
132 rt.Query(test_rect, &results); 121 }
133 EXPECT_EQ(results.size(), 0U); 122
134 ValidateRTree(&rt); 123 bool NodeCompareVertical(RTreeNodeBase* a, RTreeNodeBase* b) {
135 } 124 return RTreeBase::Node::CompareVertical(a, b);
136 125 }
137 // Even with a complex internal structure, clear should empty the tree, meaning 126
138 // that all queries should not return results after. 127 bool NodeCompareHorizontal(RTreeNodeBase* a, RTreeNodeBase* b) {
139 TEST_F(RTreeTest, ClearEmptiesTreeOfManyNodes) { 128 return RTreeBase::Node::CompareHorizontal(a, b);
140 RTree rt(2, 5); 129 }
141 AddStackedSquares(&rt, 100); 130
142 rt.Clear(); 131 bool NodeCompareCenterDistanceFromParent(
143 base::hash_set<intptr_t> results; 132 const RTreeNodeBase* a, const RTreeNodeBase* b) {
144 Rect test_rect(1, 1); 133 return RTreeBase::Node::CompareCenterDistanceFromParent(a, b);
145 rt.Query(test_rect, &results); 134 }
146 EXPECT_EQ(results.size(), 0U); 135
147 ValidateRTree(&rt); 136 int NodeOverlapIncreaseToAdd(RTreeNode* node,
148 } 137 const Rect& rect,
149 138 const RTreeNodeBase* candidate_node,
150 // Duplicate inserts should overwrite previous inserts. 139 const Rect& expanded_rect) {
151 TEST_F(RTreeTest, DuplicateInsertsOverwrite) { 140 return node->OverlapIncreaseToAdd(rect, candidate_node, expanded_rect);
152 RTree rt(2, 5); 141 }
153 // Add 100 stacked squares, but always with duplicate key of 1. 142
154 for (int i = 1; i <= 100; ++i) { 143 void NodeBuildLowBounds(const std::vector<RTreeNodeBase*>& vertical_sort,
155 rt.Insert(Rect(0, 0, i, i), 1); 144 const std::vector<RTreeNodeBase*>& horizontal_sort,
156 ValidateRTree(&rt); 145 RTreeRects* vertical_bounds,
157 } 146 RTreeRects* horizontal_bounds) {
158 base::hash_set<intptr_t> results; 147 RTreeBase::Node::BuildLowBounds(
159 Rect test_rect(1, 1); 148 vertical_sort, horizontal_sort, vertical_bounds, horizontal_bounds);
160 rt.Query(test_rect, &results); 149 }
161 EXPECT_EQ(results.size(), 1U); 150
162 EXPECT_EQ(results.count(1), 1U); 151 void NodeBuildHighBounds(const std::vector<RTreeNodeBase*>& vertical_sort,
163 } 152 const std::vector<RTreeNodeBase*>& horizontal_sort,
164 153 RTreeRects* vertical_bounds,
165 // Call Remove() once on something that's been inserted repeatedly. 154 RTreeRects* horizontal_bounds) {
166 TEST_F(RTreeTest, DuplicateInsertRemove) { 155 RTreeBase::Node::BuildHighBounds(
167 RTree rt(3, 9); 156 vertical_sort, horizontal_sort, vertical_bounds, horizontal_bounds);
168 AddStackedSquares(&rt, 25); 157 }
169 for (int i = 1; i <= 100; ++i) { 158
170 rt.Insert(Rect(0, 0, i, i), 26); 159 int NodeSmallestMarginSum(size_t start_index,
171 ValidateRTree(&rt); 160 size_t end_index,
172 } 161 const RTreeRects& low_bounds,
173 rt.Remove(26); 162 const RTreeRects& high_bounds) {
174 base::hash_set<intptr_t> results; 163 return RTreeBase::Node::SmallestMarginSum(
175 Rect test_rect(1, 1); 164 start_index, end_index, low_bounds, high_bounds);
176 rt.Query(test_rect, &results); 165 }
177 EXPECT_EQ(results.size(), 25U); 166
178 VerifyAllKeys(results); 167 size_t NodeChooseSplitIndex(size_t min_children,
179 } 168 size_t max_children,
180 169 const RTreeRects& low_bounds,
181 // Call Remove() repeatedly on something that's been inserted once. 170 const RTreeRects& high_bounds) {
182 TEST_F(RTreeTest, InsertDuplicateRemove) { 171 return RTreeBase::Node::ChooseSplitIndex(
183 RTree rt(7, 15); 172 min_children, max_children, low_bounds, high_bounds);
184 AddStackedSquares(&rt, 101); 173 }
185 for (int i = 0; i < 100; ++i) { 174
186 rt.Remove(101); 175 scoped_ptr<RTreeNodeBase> NodeDivideChildren(
187 ValidateRTree(&rt); 176 RTreeNode* node,
188 } 177 const RTreeRects& low_bounds,
189 base::hash_set<intptr_t> results; 178 const RTreeRects& high_bounds,
190 Rect test_rect(1, 1); 179 const std::vector<RTreeNodeBase*>& sorted_children,
191 rt.Query(test_rect, &results); 180 size_t split_index) {
192 EXPECT_EQ(results.size(), 100U); 181 return node->DivideChildren(
193 VerifyAllKeys(results); 182 low_bounds, high_bounds, sorted_children, split_index);
194 } 183 }
195 184
196 // Stacked rects should meet all matching queries regardless of nesting. 185 RTreeNode* NodeLeastOverlapIncrease(RTreeNode* node,
197 TEST_F(RTreeTest, QueryStackedSquaresNestedHit) { 186 const Rect& node_rect,
198 RTree rt(2, 5); 187 const RTreeRects& expanded_rects) {
199 AddStackedSquares(&rt, 100); 188 return node->LeastOverlapIncrease(node_rect, expanded_rects);
200 base::hash_set<intptr_t> results; 189 }
201 Rect test_rect(1, 1); 190
202 rt.Query(test_rect, &results); 191 RTreeNode* NodeLeastAreaEnlargement(RTreeNode* node,
203 EXPECT_EQ(results.size(), 100U); 192 const Rect& node_rect,
204 VerifyAllKeys(results); 193 const RTreeRects& expanded_rects) {
205 } 194 return node->LeastAreaEnlargement(node_rect, expanded_rects);
206 195 }
207 // Stacked rects should meet all matching queries when contained completely by 196 };
208 // the query rectangle. 197
209 TEST_F(RTreeTest, QueryStackedSquaresContainedHit) { 198 // RTreeNodeTest --------------------------------------------------------------
210 RTree rt(2, 10); 199
211 AddStackedSquares(&rt, 100); 200 TEST_F(RTreeNodeTest, RemoveNodesForReinsert) {
212 base::hash_set<intptr_t> results;
213 Rect test_rect(0, 0, 100, 100);
214 rt.Query(test_rect, &results);
215 EXPECT_EQ(results.size(), 100U);
216 VerifyAllKeys(results);
217 }
218
219 // Stacked rects should miss a missing query when the query has no intersection
220 // with the rects.
221 TEST_F(RTreeTest, QueryStackedSquaresCompleteMiss) {
222 RTree rt(2, 7);
223 AddStackedSquares(&rt, 100);
224 base::hash_set<intptr_t> results;
225 Rect test_rect(150, 150, 100, 100);
226 rt.Query(test_rect, &results);
227 EXPECT_EQ(results.size(), 0U);
228 }
229
230 // Removing half the nodes after insertion should still result in a valid tree.
231 TEST_F(RTreeTest, RemoveHalfStackedRects) {
232 RTree rt(2, 11);
233 AddStackedSquares(&rt, 200);
234 for (int i = 101; i <= 200; ++i) {
235 rt.Remove(i);
236 ValidateRTree(&rt);
237 }
238 base::hash_set<intptr_t> results;
239 Rect test_rect(1, 1);
240 rt.Query(test_rect, &results);
241 EXPECT_EQ(results.size(), 100U);
242 VerifyAllKeys(results);
243 // Add the nodes back in.
244 for (int i = 101; i <= 200; ++i) {
245 rt.Insert(Rect(0, 0, i, i), i);
246 ValidateRTree(&rt);
247 }
248 results.clear();
249 rt.Query(test_rect, &results);
250 EXPECT_EQ(results.size(), 200U);
251 VerifyAllKeys(results);
252 }
253
254 TEST_F(RTreeTest, InsertDupToRoot) {
255 RTree rt(2, 5);
256 rt.Insert(Rect(0, 0, 1, 2), 1);
257 ValidateRTree(&rt);
258 rt.Insert(Rect(0, 0, 2, 1), 1);
259 ValidateRTree(&rt);
260 }
261
262 TEST_F(RTreeTest, InsertNegativeCoordsRect) {
263 RTree rt(5, 11);
264 for (int i = 1; i <= 100; ++i) {
265 rt.Insert(Rect(-i, -i, i, i), (i * 2) - 1);
266 ValidateRTree(&rt);
267 rt.Insert(Rect(0, 0, i, i), i * 2);
268 ValidateRTree(&rt);
269 }
270 base::hash_set<intptr_t> results;
271 Rect test_rect(-1, -1, 2, 2);
272 rt.Query(test_rect, &results);
273 EXPECT_EQ(results.size(), 200U);
274 VerifyAllKeys(results);
275 }
276
277 TEST_F(RTreeTest, RemoveNegativeCoordsRect) {
278 RTree rt(7, 21);
279 // Add 100 positive stacked squares.
280 AddStackedSquares(&rt, 100);
281 // Now add 100 negative stacked squares.
282 for (int i = 101; i <= 200; ++i) {
283 rt.Insert(Rect(100 - i, 100 - i, i - 100, i - 100), 301 - i);
284 ValidateRTree(&rt);
285 }
286 // Now remove half of the negative squares.
287 for (int i = 101; i <= 150; ++i) {
288 rt.Remove(301 - i);
289 ValidateRTree(&rt);
290 }
291 // Queries should return 100 positive and 50 negative stacked squares.
292 base::hash_set<intptr_t> results;
293 Rect test_rect(-1, -1, 2, 2);
294 rt.Query(test_rect, &results);
295 EXPECT_EQ(results.size(), 150U);
296 VerifyAllKeys(results);
297 }
298
299 TEST_F(RTreeTest, InsertEmptyRectReplacementRemovesKey) {
300 RTree rt(10, 31);
301 AddStackedSquares(&rt, 50);
302 ValidateRTree(&rt);
303
304 // Replace last square with empty rect.
305 rt.Insert(Rect(), 50);
306 ValidateRTree(&rt);
307
308 // Now query large area to get all rects in tree.
309 base::hash_set<intptr_t> results;
310 Rect test_rect(0, 0, 100, 100);
311 rt.Query(test_rect, &results);
312
313 // Should only be 49 rects in tree.
314 EXPECT_EQ(results.size(), 49U);
315 VerifyAllKeys(results);
316 }
317
318 TEST_F(RTreeTest, NodeRemoveNodesForReinsert) {
319 // Make a leaf node for testing removal from. 201 // Make a leaf node for testing removal from.
320 scoped_ptr<RTree::Node> test_node(new RTree::Node(0)); 202 scoped_ptr<RTreeNode> test_node(new RTreeNode);
321 // Build 20 record nodes with rectangle centers going from (1,1) to (20,20) 203 // Build 20 record nodes with rectangle centers going from (1,1) to (20,20)
322 for (int i = 1; i <= 20; ++i) { 204 for (int i = 1; i <= 20; ++i)
323 test_node->AddChild(new RTree::Node(Rect(i - 1, i - 1, 2, 2), i)); 205 test_node->AddChild(scoped_ptr<RTreeNodeBase>(
324 } 206 new RTreeRecord(Rect(i - 1, i - 1, 2, 2), i)));
207
325 // Quick verification of the node before removing children. 208 // Quick verification of the node before removing children.
326 ValidateNode(test_node.get(), 1U, 20U); 209 ValidateNode(test_node.get(), 1U, 20U);
327 // Use a scoped vector to delete all children that get removed from the Node. 210 // Use a scoped vector to delete all children that get removed from the Node.
328 ScopedVector<RTree::Node> removals; 211 RTreeNodes removals;
329 test_node->RemoveNodesForReinsert(1, &removals); 212 test_node->RemoveNodesForReinsert(1, &removals);
330 // Should have gotten back 1 node pointers. 213 // Should have gotten back 1 node pointer.
331 EXPECT_EQ(removals.size(), 1U); 214 EXPECT_EQ(1U, removals.size());
332 // There should be 19 left in the test_node. 215 // There should be 19 left in the test_node.
333 EXPECT_EQ(test_node->count(), 19U); 216 EXPECT_EQ(19U, test_node->count());
334 // If we fix up the bounds on the test_node, it should verify. 217 // If we fix up the bounds on the test_node, it should verify.
335 test_node->RecomputeBoundsNoParents(); 218 NodeRecomputeLocalBounds(test_node.get());
336 ValidateNode(test_node.get(), 2U, 20U); 219 ValidateNode(test_node.get(), 2U, 20U);
337 // The node we removed should be node 10, as it was exactly in the center. 220 // The node we removed should be node 10, as it was exactly in the center.
338 EXPECT_EQ(removals[0]->key(), 10); 221 EXPECT_EQ(10, static_cast<RTreeRecord*>(removals[0])->key());
339 222
340 // Now remove the next 2. 223 // Now remove the next 2.
341 removals.clear(); 224 removals.clear();
342 test_node->RemoveNodesForReinsert(2, &removals); 225 test_node->RemoveNodesForReinsert(2, &removals);
343 EXPECT_EQ(removals.size(), 2U); 226 EXPECT_EQ(2U, removals.size());
344 EXPECT_EQ(test_node->count(), 17U); 227 EXPECT_EQ(17U, test_node->count());
345 test_node->RecomputeBoundsNoParents(); 228 NodeRecomputeLocalBounds(test_node.get());
346 ValidateNode(test_node.get(), 2U, 20U); 229 ValidateNode(test_node.get(), 2U, 20U);
347 // Lastly the 2 nodes we should have gotten back are keys 9 and 11, as their 230 // Lastly the 2 nodes we should have gotten back are keys 9 and 11, as their
348 // centers were the closest to the center of the node bounding box. 231 // centers were the closest to the center of the node bounding box.
349 base::hash_set<intptr_t> results_hash; 232 base::hash_set<intptr_t> results_hash;
350 results_hash.insert(removals[0]->key()); 233 results_hash.insert(static_cast<RTreeRecord*>(removals[0])->key());
351 results_hash.insert(removals[1]->key()); 234 results_hash.insert(static_cast<RTreeRecord*>(removals[1])->key());
352 EXPECT_EQ(results_hash.count(9), 1U); 235 EXPECT_EQ(1U, results_hash.count(9));
353 EXPECT_EQ(results_hash.count(11), 1U); 236 EXPECT_EQ(1U, results_hash.count(11));
354 } 237 }
355 238
356 TEST_F(RTreeTest, NodeCompareVertical) { 239 TEST_F(RTreeNodeTest, CompareVertical) {
357 // One rect with lower y than another should always sort lower than higher y. 240 // One rect with lower y than another should always sort lower.
358 RTree::Node low(Rect(0, 1, 10, 10), 1); 241 RTreeRecord low(Rect(0, 1, 10, 10), 1);
359 RTree::Node middle(Rect(0, 5, 10, 10), 5); 242 RTreeRecord middle(Rect(0, 5, 10, 10), 5);
360 EXPECT_TRUE(RTree::Node::CompareVertical(&low, &middle)); 243 EXPECT_TRUE(NodeCompareVertical(&low, &middle));
361 EXPECT_FALSE(RTree::Node::CompareVertical(&middle, &low)); 244 EXPECT_FALSE(NodeCompareVertical(&middle, &low));
362 245
363 // Try a non-overlapping higher-y rectangle. 246 // Try a non-overlapping higher-y rectangle.
364 RTree::Node high(Rect(-10, 20, 10, 1), 10); 247 RTreeRecord high(Rect(-10, 20, 10, 1), 10);
365 EXPECT_TRUE(RTree::Node::CompareVertical(&low, &high)); 248 EXPECT_TRUE(NodeCompareVertical(&low, &high));
366 EXPECT_FALSE(RTree::Node::CompareVertical(&high, &low)); 249 EXPECT_FALSE(NodeCompareVertical(&high, &low));
367 250
368 // Ties are broken by lowest bottom y value. 251 // Ties are broken by lowest bottom y value.
369 RTree::Node shorter_tie(Rect(10, 1, 100, 2), 2); 252 RTreeRecord shorter_tie(Rect(10, 1, 100, 2), 2);
370 EXPECT_TRUE(RTree::Node::CompareVertical(&shorter_tie, &low)); 253 EXPECT_TRUE(NodeCompareVertical(&shorter_tie, &low));
371 EXPECT_FALSE(RTree::Node::CompareVertical(&low, &shorter_tie)); 254 EXPECT_FALSE(NodeCompareVertical(&low, &shorter_tie));
372 } 255 }
373 256
374 TEST_F(RTreeTest, NodeCompareHorizontal) { 257 TEST_F(RTreeNodeTest, CompareHorizontal) {
375 // One rect with lower x than another should always sort lower than higher x. 258 // One rect with lower x than another should always sort lower than higher x.
376 RTree::Node low(Rect(1, 0, 10, 10), 1); 259 RTreeRecord low(Rect(1, 0, 10, 10), 1);
377 RTree::Node middle(Rect(5, 0, 10, 10), 5); 260 RTreeRecord middle(Rect(5, 0, 10, 10), 5);
378 EXPECT_TRUE(RTree::Node::CompareHorizontal(&low, &middle)); 261 EXPECT_TRUE(NodeCompareHorizontal(&low, &middle));
379 EXPECT_FALSE(RTree::Node::CompareHorizontal(&middle, &low)); 262 EXPECT_FALSE(NodeCompareHorizontal(&middle, &low));
380 263
381 // Try a non-overlapping higher-x rectangle. 264 // Try a non-overlapping higher-x rectangle.
382 RTree::Node high(Rect(20, -10, 1, 10), 10); 265 RTreeRecord high(Rect(20, -10, 1, 10), 10);
383 EXPECT_TRUE(RTree::Node::CompareHorizontal(&low, &high)); 266 EXPECT_TRUE(NodeCompareHorizontal(&low, &high));
384 EXPECT_FALSE(RTree::Node::CompareHorizontal(&high, &low)); 267 EXPECT_FALSE(NodeCompareHorizontal(&high, &low));
385 268
386 // Ties are broken by lowest bottom x value. 269 // Ties are broken by lowest bottom x value.
387 RTree::Node shorter_tie(Rect(1, 10, 2, 100), 2); 270 RTreeRecord shorter_tie(Rect(1, 10, 2, 100), 2);
388 EXPECT_TRUE(RTree::Node::CompareHorizontal(&shorter_tie, &low)); 271 EXPECT_TRUE(NodeCompareHorizontal(&shorter_tie, &low));
389 EXPECT_FALSE(RTree::Node::CompareHorizontal(&low, &shorter_tie)); 272 EXPECT_FALSE(NodeCompareHorizontal(&low, &shorter_tie));
390 } 273 }
391 274
392 TEST_F(RTreeTest, NodeCompareCenterDistanceFromParent) { 275 TEST_F(RTreeNodeTest, CompareCenterDistanceFromParent) {
393 // Create a test node we can add children to, for distance comparisons. 276 // Create a test node we can add children to, for distance comparisons.
394 scoped_ptr<RTree::Node> parent(new RTree::Node(0)); 277 scoped_ptr<RTreeNode> parent(new RTreeNode);
395 278
396 // Add three children, one each with centers at (0, 0), (10, 10), (-9, -9), 279 // Add three children, one each with centers at (0, 0), (10, 10), (-9, -9),
397 // around which a bounding box will be centered at (0, 0) 280 // around which a bounding box will be centered at (0, 0)
398 RTree::Node* center_zero = new RTree::Node(Rect(-1, -1, 2, 2), 1); 281 scoped_ptr<RTreeRecord> center_zero(new RTreeRecord(Rect(-1, -1, 2, 2), 1));
399 parent->AddChild(center_zero); 282 parent->AddChild(center_zero.PassAs<RTreeNodeBase>());
400 283
401 RTree::Node* center_positive = new RTree::Node(Rect(9, 9, 2, 2), 2); 284 scoped_ptr<RTreeRecord> center_positive(new RTreeRecord(Rect(9, 9, 2, 2), 2));
402 parent->AddChild(center_positive); 285 parent->AddChild(center_positive.PassAs<RTreeNodeBase>());
403 286
404 RTree::Node* center_negative = new RTree::Node(Rect(-10, -10, 2, 2), 3); 287 scoped_ptr<RTreeRecord> center_negative(
405 parent->AddChild(center_negative); 288 new RTreeRecord(Rect(-10, -10, 2, 2), 3));
289 parent->AddChild(center_negative.PassAs<RTreeNodeBase>());
406 290
407 ValidateNode(parent.get(), 1U, 5U); 291 ValidateNode(parent.get(), 1U, 5U);
408 EXPECT_EQ(parent->rect_, Rect(-10, -10, 21, 21)); 292 EXPECT_EQ(Rect(-10, -10, 21, 21), parent->rect());
409 293
410 EXPECT_TRUE(RTree::Node::CompareCenterDistanceFromParent(center_zero, 294 EXPECT_TRUE(
411 center_positive)); 295 NodeCompareCenterDistanceFromParent(parent->child(0), parent->child(1)));
412 EXPECT_FALSE(RTree::Node::CompareCenterDistanceFromParent(center_positive, 296 EXPECT_FALSE(
413 center_zero)); 297 NodeCompareCenterDistanceFromParent(parent->child(1), parent->child(0)));
414 298 EXPECT_TRUE(
415 EXPECT_TRUE(RTree::Node::CompareCenterDistanceFromParent(center_zero, 299 NodeCompareCenterDistanceFromParent(parent->child(0), parent->child(2)));
416 center_negative)); 300 EXPECT_FALSE(
417 EXPECT_FALSE(RTree::Node::CompareCenterDistanceFromParent(center_negative, 301 NodeCompareCenterDistanceFromParent(parent->child(2), parent->child(0)));
418 center_zero)); 302 EXPECT_TRUE(
419 303 NodeCompareCenterDistanceFromParent(parent->child(2), parent->child(1)));
420 EXPECT_TRUE(RTree::Node::CompareCenterDistanceFromParent(center_negative, 304 EXPECT_FALSE(
421 center_positive)); 305 NodeCompareCenterDistanceFromParent(parent->child(1), parent->child(2)));
422 EXPECT_FALSE(RTree::Node::CompareCenterDistanceFromParent(center_positive,
423 center_negative));
424 } 306 }
425 307
426 TEST_F(RTreeTest, NodeOverlapIncreaseToAdd) { 308 TEST_F(RTreeNodeTest, OverlapIncreaseToAdd) {
427 // Create a test node with three children, for overlap comparisons. 309 // Create a test node with three children, for overlap comparisons.
428 scoped_ptr<RTree::Node> parent(new RTree::Node(0)); 310 scoped_ptr<RTreeNode> parent(new RTreeNode);
429 311
430 // Add three children, each 4 wide and tall, at (0, 0), (3, 3), (6, 6) with 312 // Add three children, each 4 wide and tall, at (0, 0), (3, 3), (6, 6) with
431 // overlapping corners. 313 // overlapping corners.
432 Rect top(0, 0, 4, 4); 314 Rect top(0, 0, 4, 4);
433 parent->AddChild(new RTree::Node(top, 1)); 315 parent->AddChild(scoped_ptr<RTreeNodeBase>(new RTreeRecord(top, 1)));
434 Rect middle(3, 3, 4, 4); 316 Rect middle(3, 3, 4, 4);
435 parent->AddChild(new RTree::Node(middle, 2)); 317 parent->AddChild(scoped_ptr<RTreeNodeBase>(new RTreeRecord(middle, 2)));
436 Rect bottom(6, 6, 4, 4); 318 Rect bottom(6, 6, 4, 4);
437 parent->AddChild(new RTree::Node(bottom, 3)); 319 parent->AddChild(scoped_ptr<RTreeNodeBase>(new RTreeRecord(bottom, 3)));
438 ValidateNode(parent.get(), 1U, 5U); 320 ValidateNode(parent.get(), 1U, 5U);
439 321
440 // Test a rect in corner. 322 // Test a rect in corner.
441 Rect corner(0, 0, 1, 1); 323 Rect corner(0, 0, 1, 1);
442 Rect expanded = top; 324 Rect expanded = top;
443 expanded.Union(corner); 325 expanded.Union(corner);
444 // It should not add any overlap to add this to the first child at (0, 0); 326 // It should not add any overlap to add this to the first child at (0, 0).
445 EXPECT_EQ(parent->OverlapIncreaseToAdd(corner, 0, expanded), 0); 327 EXPECT_EQ(0, NodeOverlapIncreaseToAdd(
328 parent.get(), corner, parent->child(0), expanded));
446 329
447 expanded = middle; 330 expanded = middle;
448 expanded.Union(corner); 331 expanded.Union(corner);
449 // Overlap for middle rectangle should increase from 2 pixels at (3, 3) and 332 // Overlap for middle rectangle should increase from 2 pixels at (3, 3) and
450 // (6, 6) to 17 pixels, as it will now cover 4x4 rectangle top, 333 // (6, 6) to 17 pixels, as it will now cover 4x4 rectangle top,
451 // so a change of +15 334 // so a change of +15.
452 EXPECT_EQ(parent->OverlapIncreaseToAdd(corner, 1, expanded), 15); 335 EXPECT_EQ(15, NodeOverlapIncreaseToAdd(
336 parent.get(), corner, parent->child(1), expanded));
453 337
454 expanded = bottom; 338 expanded = bottom;
455 expanded.Union(corner); 339 expanded.Union(corner);
456 // Overlap for bottom rectangle should increase from 1 pixel at (6, 6) to 340 // Overlap for bottom rectangle should increase from 1 pixel at (6, 6) to
457 // 32 pixels, as it will now cover both 4x4 rectangles top and middle, 341 // 32 pixels, as it will now cover both 4x4 rectangles top and middle,
458 // so a change of 31 342 // so a change of 31.
459 EXPECT_EQ(parent->OverlapIncreaseToAdd(corner, 2, expanded), 31); 343 EXPECT_EQ(31, NodeOverlapIncreaseToAdd(
344 parent.get(), corner, parent->child(2), expanded));
460 345
461 // Test a rect that doesn't overlap with anything, in the far right corner. 346 // Test a rect that doesn't overlap with anything, in the far right corner.
462 Rect far_corner(9, 0, 1, 1); 347 Rect far_corner(9, 0, 1, 1);
463 expanded = top; 348 expanded = top;
464 expanded.Union(far_corner); 349 expanded.Union(far_corner);
465 // Overlap of top should go from 1 to 4, as it will now cover the entire first 350 // Overlap of top should go from 1 to 4, as it will now cover the entire first
466 // row of pixels in middle. 351 // row of pixels in middle.
467 EXPECT_EQ(parent->OverlapIncreaseToAdd(far_corner, 0, expanded), 3); 352 EXPECT_EQ(3, NodeOverlapIncreaseToAdd(
353 parent.get(), far_corner, parent->child(0), expanded));
468 354
469 expanded = middle; 355 expanded = middle;
470 expanded.Union(far_corner); 356 expanded.Union(far_corner);
471 // Overlap of middle should go from 2 to 8, as it will cover the rightmost 4 357 // Overlap of middle should go from 2 to 8, as it will cover the rightmost 4
472 // pixels of top and the top 4 pixles of bottom as it expands. 358 // pixels of top and the top 4 pixels of bottom as it expands.
473 EXPECT_EQ(parent->OverlapIncreaseToAdd(far_corner, 1, expanded), 6); 359 EXPECT_EQ(6, NodeOverlapIncreaseToAdd(
360 parent.get(), far_corner, parent->child(1), expanded));
474 361
475 expanded = bottom; 362 expanded = bottom;
476 expanded.Union(far_corner); 363 expanded.Union(far_corner);
477 // Overlap of bottom should go from 1 to 4, as it will now cover the rightmost 364 // Overlap of bottom should go from 1 to 4, as it will now cover the rightmost
478 // 4 pixels of middle. 365 // 4 pixels of middle.
479 EXPECT_EQ(parent->OverlapIncreaseToAdd(far_corner, 2, expanded), 3); 366 EXPECT_EQ(3, NodeOverlapIncreaseToAdd(
367 parent.get(), far_corner, parent->child(2), expanded));
480 } 368 }
481 369
482 TEST_F(RTreeTest, NodeBuildLowBounds) { 370 TEST_F(RTreeNodeTest, BuildLowBounds) {
483 ScopedVector<RTree::Node> nodes; 371 RTreeNodes records;
484 nodes.reserve(10); 372 records.reserve(10);
485 for (int i = 1; i <= 10; ++i) { 373 for (int i = 1; i <= 10; ++i)
486 nodes.push_back(new RTree::Node(Rect(0, 0, i, i), i)); 374 records.push_back(new RTreeRecord(Rect(0, 0, i, i), i));
487 } 375
488 std::vector<Rect> vertical_bounds; 376 RTreeRects vertical_bounds;
489 std::vector<Rect> horizontal_bounds; 377 RTreeRects horizontal_bounds;
490 RTree::Node::BuildLowBounds( 378 NodeBuildLowBounds(
491 nodes.get(), nodes.get(), &vertical_bounds, &horizontal_bounds); 379 records.get(), records.get(), &vertical_bounds, &horizontal_bounds);
492 for (int i = 0; i < 10; ++i) { 380 for (int i = 0; i < 10; ++i) {
493 EXPECT_EQ(vertical_bounds[i], Rect(0, 0, i + 1, i + 1)); 381 EXPECT_EQ(records[i]->rect(), vertical_bounds[i]);
494 EXPECT_EQ(horizontal_bounds[i], Rect(0, 0, i + 1, i + 1)); 382 EXPECT_EQ(records[i]->rect(), horizontal_bounds[i]);
495 } 383 }
496 } 384 }
497 385
498 TEST_F(RTreeTest, NodeBuildHighBounds) { 386 TEST_F(RTreeNodeTest, BuildHighBounds) {
499 ScopedVector<RTree::Node> nodes; 387 RTreeNodes records;
500 nodes.reserve(25); 388 records.reserve(25);
389 for (int i = 0; i < 25; ++i)
390 records.push_back(new RTreeRecord(Rect(i, i, 25 - i, 25 - i), i));
391
392 RTreeRects vertical_bounds;
393 RTreeRects horizontal_bounds;
394 NodeBuildHighBounds(
395 records.get(), records.get(), &vertical_bounds, &horizontal_bounds);
501 for (int i = 0; i < 25; ++i) { 396 for (int i = 0; i < 25; ++i) {
502 nodes.push_back(new RTree::Node(Rect(i, i, 25 - i, 25 - i), i)); 397 EXPECT_EQ(records[i]->rect(), vertical_bounds[i]);
503 } 398 EXPECT_EQ(records[i]->rect(), horizontal_bounds[i]);
504 std::vector<Rect> vertical_bounds;
505 std::vector<Rect> horizontal_bounds;
506 RTree::Node::BuildHighBounds(
507 nodes.get(), nodes.get(), &vertical_bounds, &horizontal_bounds);
508 for (int i = 0; i < 25; ++i) {
509 EXPECT_EQ(vertical_bounds[i], Rect(i, i, 25 - i, 25 - i));
510 EXPECT_EQ(horizontal_bounds[i], Rect(i, i, 25 - i, 25 - i));
511 } 399 }
512 } 400 }
513 401
514 TEST_F(RTreeTest, NodeChooseSplitAxisAndIndex) { 402 TEST_F(RTreeNodeTest, ChooseSplitAxisAndIndexVertical) {
515 std::vector<Rect> low_vertical_bounds; 403 RTreeRects low_vertical_bounds;
516 std::vector<Rect> high_vertical_bounds; 404 RTreeRects high_vertical_bounds;
517 std::vector<Rect> low_horizontal_bounds; 405 RTreeRects low_horizontal_bounds;
518 std::vector<Rect> high_horizontal_bounds; 406 RTreeRects high_horizontal_bounds;
519 // In this test scenario we describe a mirrored, stacked configuration of 407 // In this test scenario we describe a mirrored, stacked configuration of
520 // horizontal, 1 pixel high rectangles labeled a-f like this: 408 // horizontal, 1 pixel high rectangles labeled a-f like this:
521 // 409 //
522 // shape: | v sort: | h sort: | 410 // shape: | v sort: | h sort: |
523 // -------+---------+---------+ 411 // -------+---------+---------+
524 // aaaaa | 0 | 0 | 412 // aaaaa | 0 | 0 |
525 // bbb | 1 | 2 | 413 // bbb | 1 | 2 |
526 // c | 2 | 4 | 414 // c | 2 | 4 |
527 // d | 3 | 5 | 415 // d | 3 | 5 |
528 // eee | 4 | 3 | 416 // eee | 4 | 3 |
529 // fffff | 5 | 1 | 417 // fffff | 5 | 1 |
530 // 418 //
531 // These are already sorted vertically from top to bottom. Bounding rectangles 419 // These are already sorted vertically from top to bottom. Bounding rectangles
532 // of these vertically sorted will be 5 wide, i tall bounding boxes. 420 // of these vertically sorted will be 5 wide, i tall bounding boxes.
533 for (int i = 0; i < 6; ++i) { 421 for (int i = 0; i < 6; ++i) {
534 low_vertical_bounds.push_back(Rect(0, 0, 5, i + 1)); 422 low_vertical_bounds.push_back(Rect(0, 0, 5, i + 1));
535 high_vertical_bounds.push_back(Rect(0, i, 5, 6 - i)); 423 high_vertical_bounds.push_back(Rect(0, i, 5, 6 - i));
536 } 424 }
537 425
538 // Low bounds of horizontal sort start with bounds of box a and then jump to 426 // Low bounds of horizontal sort start with bounds of box a and then jump to
539 // cover everything, as box f is second in horizontal sort. 427 // cover everything, as box f is second in horizontal sort.
540 low_horizontal_bounds.push_back(Rect(0, 0, 5, 1)); 428 low_horizontal_bounds.push_back(Rect(0, 0, 5, 1));
541 for (int i = 0; i < 5; ++i) { 429 for (int i = 0; i < 5; ++i)
542 low_horizontal_bounds.push_back(Rect(0, 0, 5, 6)); 430 low_horizontal_bounds.push_back(Rect(0, 0, 5, 6));
543 }
544 431
545 // High horizontal bounds are hand-calculated. 432 // High horizontal bounds are hand-calculated.
546 high_horizontal_bounds.push_back(Rect(0, 0, 5, 6)); 433 high_horizontal_bounds.push_back(Rect(0, 0, 5, 6));
547 high_horizontal_bounds.push_back(Rect(0, 1, 5, 5)); 434 high_horizontal_bounds.push_back(Rect(0, 1, 5, 5));
548 high_horizontal_bounds.push_back(Rect(1, 1, 3, 4)); 435 high_horizontal_bounds.push_back(Rect(1, 1, 3, 4));
549 high_horizontal_bounds.push_back(Rect(1, 2, 3, 3)); 436 high_horizontal_bounds.push_back(Rect(1, 2, 3, 3));
550 high_horizontal_bounds.push_back(Rect(2, 2, 1, 2)); 437 high_horizontal_bounds.push_back(Rect(2, 2, 1, 2));
551 high_horizontal_bounds.push_back(Rect(2, 3, 1, 1)); 438 high_horizontal_bounds.push_back(Rect(2, 3, 1, 1));
552 439
553 // This should split vertically, right down the middle. 440 int smallest_vertical_margin =
554 EXPECT_TRUE(RTree::Node::ChooseSplitAxis(low_vertical_bounds, 441 NodeSmallestMarginSum(2, 3, low_vertical_bounds, high_vertical_bounds);
555 high_vertical_bounds, 442 int smallest_horizontal_margin = NodeSmallestMarginSum(
556 low_horizontal_bounds, 443 2, 3, low_horizontal_bounds, high_horizontal_bounds);
557 high_horizontal_bounds, 444 EXPECT_LT(smallest_vertical_margin, smallest_horizontal_margin);
558 2,
559 5));
560 EXPECT_EQ(3U,
561 RTree::Node::ChooseSplitIndex(
562 2, 5, low_vertical_bounds, high_vertical_bounds));
563 445
564 // We rotate the shape to test horizontal split axis detection: 446 EXPECT_EQ(
447 3U,
448 NodeChooseSplitIndex(2, 5, low_vertical_bounds, high_vertical_bounds));
449 }
450
451 TEST_F(RTreeNodeTest, ChooseSplitAxisAndIndexHorizontal) {
452 RTreeRects low_vertical_bounds;
453 RTreeRects high_vertical_bounds;
454 RTreeRects low_horizontal_bounds;
455 RTreeRects high_horizontal_bounds;
456 // We rotate the shape from ChooseSplitAxisAndIndexVertical to test
457 // horizontal split axis detection:
565 // 458 //
566 // +--------+ 459 // +--------+
567 // | a f | 460 // | a f |
568 // | ab ef | 461 // | ab ef |
569 // sort: | abcdef | 462 // sort: | abcdef |
570 // | ab ef | 463 // | ab ef |
571 // | a f | 464 // | a f |
572 // |--------+ 465 // |--------+
573 // v sort: | 024531 | 466 // v sort: | 024531 |
574 // h sort: | 012345 | 467 // h sort: | 012345 |
575 // +--------+ 468 // +--------+
576 // 469 //
577 // Clear out old bounds first.
578 low_vertical_bounds.clear();
579 high_vertical_bounds.clear();
580 low_horizontal_bounds.clear();
581 high_horizontal_bounds.clear();
582
583 // Low bounds of vertical sort start with bounds of box a and then jump to 470 // Low bounds of vertical sort start with bounds of box a and then jump to
584 // cover everything, as box f is second in vertical sort. 471 // cover everything, as box f is second in vertical sort.
585 low_vertical_bounds.push_back(Rect(0, 0, 1, 5)); 472 low_vertical_bounds.push_back(Rect(0, 0, 1, 5));
586 for (int i = 0; i < 5; ++i) { 473 for (int i = 0; i < 5; ++i)
587 low_vertical_bounds.push_back(Rect(0, 0, 6, 5)); 474 low_vertical_bounds.push_back(Rect(0, 0, 6, 5));
588 }
589 475
590 // High vertical bounds are hand-calculated. 476 // High vertical bounds are hand-calculated.
591 high_vertical_bounds.push_back(Rect(0, 0, 6, 5)); 477 high_vertical_bounds.push_back(Rect(0, 0, 6, 5));
592 high_vertical_bounds.push_back(Rect(1, 0, 5, 5)); 478 high_vertical_bounds.push_back(Rect(1, 0, 5, 5));
593 high_vertical_bounds.push_back(Rect(1, 1, 4, 3)); 479 high_vertical_bounds.push_back(Rect(1, 1, 4, 3));
594 high_vertical_bounds.push_back(Rect(2, 1, 3, 3)); 480 high_vertical_bounds.push_back(Rect(2, 1, 3, 3));
595 high_vertical_bounds.push_back(Rect(2, 2, 2, 1)); 481 high_vertical_bounds.push_back(Rect(2, 2, 2, 1));
596 high_vertical_bounds.push_back(Rect(3, 2, 1, 1)); 482 high_vertical_bounds.push_back(Rect(3, 2, 1, 1));
597 483
598 // These are already sorted horizontally from left to right. Bounding 484 // These are already sorted horizontally from left to right. Bounding
599 // rectangles of these horizontally sorted will be i wide, 5 tall bounding 485 // rectangles of these horizontally sorted will be i wide, 5 tall bounding
600 // boxes. 486 // boxes.
601 for (int i = 0; i < 6; ++i) { 487 for (int i = 0; i < 6; ++i) {
602 low_horizontal_bounds.push_back(Rect(0, 0, i + 1, 5)); 488 low_horizontal_bounds.push_back(Rect(0, 0, i + 1, 5));
603 high_horizontal_bounds.push_back(Rect(i, 0, 6 - i, 5)); 489 high_horizontal_bounds.push_back(Rect(i, 0, 6 - i, 5));
604 } 490 }
605 491
606 // This should split horizontally, right down the middle. 492 int smallest_vertical_margin =
607 EXPECT_FALSE(RTree::Node::ChooseSplitAxis(low_vertical_bounds, 493 NodeSmallestMarginSum(2, 3, low_vertical_bounds, high_vertical_bounds);
608 high_vertical_bounds, 494 int smallest_horizontal_margin = NodeSmallestMarginSum(
609 low_horizontal_bounds, 495 2, 3, low_horizontal_bounds, high_horizontal_bounds);
610 high_horizontal_bounds, 496
611 2, 497 EXPECT_GT(smallest_vertical_margin, smallest_horizontal_margin);
612 5)); 498
613 EXPECT_EQ(3U, 499 EXPECT_EQ(3U,
614 RTree::Node::ChooseSplitIndex( 500 NodeChooseSplitIndex(
615 2, 5, low_horizontal_bounds, high_horizontal_bounds)); 501 2, 5, low_horizontal_bounds, high_horizontal_bounds));
616 } 502 }
617 503
618 TEST_F(RTreeTest, NodeDivideChildren) { 504 TEST_F(RTreeNodeTest, DivideChildren) {
619 // Create a test node to split. 505 // Create a test node to split.
620 scoped_ptr<RTree::Node> test_node(new RTree::Node(0)); 506 scoped_ptr<RTreeNode> test_node(new RTreeNode);
621 std::vector<RTree::Node*> sorted_children; 507 std::vector<RTreeNodeBase*> sorted_children;
622 std::vector<Rect> low_bounds; 508 RTreeRects low_bounds;
623 std::vector<Rect> high_bounds; 509 RTreeRects high_bounds;
624 // Insert 10 record nodes, also inserting them into our children array. 510 // Insert 10 record nodes, also inserting them into our children array.
625 for (int i = 1; i <= 10; ++i) { 511 for (int i = 1; i <= 10; ++i) {
626 RTree::Node* node = new RTree::Node(Rect(0, 0, i, i), i); 512 scoped_ptr<RTreeRecord> record(new RTreeRecord(Rect(0, 0, i, i), i));
627 test_node->AddChild(node); 513 sorted_children.push_back(record.get());
628 sorted_children.push_back(node); 514 test_node->AddChild(record.PassAs<RTreeNodeBase>());
629 low_bounds.push_back(Rect(0, 0, i, i)); 515 low_bounds.push_back(Rect(0, 0, i, i));
630 high_bounds.push_back(Rect(0, 0, 10, 10)); 516 high_bounds.push_back(Rect(0, 0, 10, 10));
631 } 517 }
632 // Split the children in half. 518 // Split the children in half.
633 scoped_ptr<RTree::Node> split_node( 519 scoped_ptr<RTreeNodeBase> split_node_base(NodeDivideChildren(
634 test_node->DivideChildren(low_bounds, high_bounds, sorted_children, 5)); 520 test_node.get(), low_bounds, high_bounds, sorted_children, 5));
521 RTreeNode* split_node = static_cast<RTreeNode*>(split_node_base.get());
635 // Both nodes should be valid. 522 // Both nodes should be valid.
636 ValidateNode(test_node.get(), 1U, 10U); 523 ValidateNode(test_node.get(), 1U, 10U);
637 ValidateNode(split_node.get(), 1U, 10U); 524 ValidateNode(split_node, 1U, 10U);
638 // Both nodes should have five children. 525 // Both nodes should have five children.
639 EXPECT_EQ(test_node->children_.size(), 5U); 526 EXPECT_EQ(5U, test_node->count());
640 EXPECT_EQ(split_node->children_.size(), 5U); 527 EXPECT_EQ(5U, split_node->count());
641 // Test node should have children 1-5, split node should have children 6-10. 528 // Test node should have children 1-5, split node should have children 6-10.
642 for (int i = 0; i < 5; ++i) { 529 for (int i = 0; i < 5; ++i) {
643 EXPECT_EQ(test_node->children_[i]->key(), i + 1); 530 EXPECT_EQ(i + 1, record(test_node.get(), i)->key());
644 EXPECT_EQ(split_node->children_[i]->key(), i + 6); 531 EXPECT_EQ(i + 6, record(split_node, i)->key());
645 } 532 }
646 } 533 }
647 534
648 TEST_F(RTreeTest, NodeRemoveChildNoOrphans) { 535 TEST_F(RTreeNodeTest, RemoveChildNoOrphans) {
649 scoped_ptr<RTree::Node> test_parent(new RTree::Node(0)); 536 scoped_ptr<RTreeNode> test_parent(new RTreeNode);
650 scoped_ptr<RTree::Node> child_one(new RTree::Node(Rect(0, 0, 1, 1), 1)); 537 test_parent->AddChild(
651 scoped_ptr<RTree::Node> child_two(new RTree::Node(Rect(0, 0, 2, 2), 2)); 538 scoped_ptr<RTreeNodeBase>(new RTreeRecord(Rect(0, 0, 1, 1), 1)));
652 scoped_ptr<RTree::Node> child_three(new RTree::Node(Rect(0, 0, 3, 3), 3)); 539 test_parent->AddChild(
653 test_parent->AddChild(child_one.get()); 540 scoped_ptr<RTreeNodeBase>(new RTreeRecord(Rect(0, 0, 2, 2), 2)));
654 test_parent->AddChild(child_two.get()); 541 test_parent->AddChild(
655 test_parent->AddChild(child_three.get()); 542 scoped_ptr<RTreeNodeBase>(new RTreeRecord(Rect(0, 0, 3, 3), 3)));
656 ValidateNode(test_parent.get(), 1U, 5U); 543 ValidateNode(test_parent.get(), 1U, 5U);
544
545 RTreeNodes orphans;
546
657 // Remove the middle node. 547 // Remove the middle node.
658 ScopedVector<RTree::Node> orphans; 548 scoped_ptr<RTreeNodeBase> middle_child(
659 EXPECT_EQ(test_parent->RemoveChild(child_two.get(), &orphans), 2U); 549 test_parent->RemoveChild(test_parent->child(1), &orphans));
660 EXPECT_EQ(orphans.size(), 0U); 550 EXPECT_EQ(0U, orphans.size());
661 EXPECT_EQ(test_parent->count(), 2U); 551 EXPECT_EQ(2U, test_parent->count());
662 test_parent->RecomputeBoundsNoParents(); 552 NodeRecomputeLocalBounds(test_parent.get());
663 ValidateNode(test_parent.get(), 1U, 5U); 553 ValidateNode(test_parent.get(), 1U, 5U);
554
664 // Remove the end node. 555 // Remove the end node.
665 EXPECT_EQ(test_parent->RemoveChild(child_three.get(), &orphans), 1U); 556 scoped_ptr<RTreeNodeBase> end_child(
666 EXPECT_EQ(orphans.size(), 0U); 557 test_parent->RemoveChild(test_parent->child(1), &orphans));
667 EXPECT_EQ(test_parent->count(), 1U); 558 EXPECT_EQ(0U, orphans.size());
668 test_parent->RecomputeBoundsNoParents(); 559 EXPECT_EQ(1U, test_parent->count());
560 NodeRecomputeLocalBounds(test_parent.get());
669 ValidateNode(test_parent.get(), 1U, 5U); 561 ValidateNode(test_parent.get(), 1U, 5U);
562
670 // Remove the first node. 563 // Remove the first node.
671 EXPECT_EQ(test_parent->RemoveChild(child_one.get(), &orphans), 0U); 564 scoped_ptr<RTreeNodeBase> first_child(
672 EXPECT_EQ(orphans.size(), 0U); 565 test_parent->RemoveChild(test_parent->child(0), &orphans));
673 EXPECT_EQ(test_parent->count(), 0U); 566 EXPECT_EQ(0U, orphans.size());
567 EXPECT_EQ(0U, test_parent->count());
674 } 568 }
675 569
676 TEST_F(RTreeTest, NodeRemoveChildOrphans) { 570 TEST_F(RTreeNodeTest, RemoveChildOrphans) {
677 // Build flattened binary tree of Nodes 4 deep, from the record nodes up. 571 // Build binary tree of Nodes of height 4, keeping weak pointers to the
678 ScopedVector<RTree::Node> nodes; 572 // Levels 0 and 1 Nodes and the Records so we can test removal of them below.
679 nodes.resize(15); 573 std::vector<RTreeNode*> level_1_children;
680 // Indicies 7 through 15 are record nodes. 574 std::vector<RTreeNode*> level_0_children;
681 for (int i = 7; i < 15; ++i) { 575 std::vector<RTreeRecord*> records;
682 nodes[i] = new RTree::Node(Rect(0, 0, i, i), i); 576 int id = 1;
683 } 577 scoped_ptr<RTreeNode> root(NewNodeAtLevel(2));
684 // Nodes 3 through 6 are level 0 (leaves) and get 2 record nodes each. 578 for (int i = 0; i < 2; ++i) {
685 for (int i = 3; i < 7; ++i) { 579 scoped_ptr<RTreeNode> level_1_child(NewNodeAtLevel(1));
686 nodes[i] = new RTree::Node(0); 580 for (int j = 0; j < 2; ++j) {
687 nodes[i]->AddChild(nodes[(i * 2) + 1]); 581 scoped_ptr<RTreeNode> level_0_child(new RTreeNode);
688 nodes[i]->AddChild(nodes[(i * 2) + 2]); 582 for (int k = 0; k < 2; ++k) {
689 } 583 scoped_ptr<RTreeRecord> record(
690 // Nodes 1 and 2 are level 1 and get 2 leaves each. 584 new RTreeRecord(Rect(0, 0, id, id), id));
691 for (int i = 1; i < 3; ++i) { 585 ++id;
692 nodes[i] = new RTree::Node(1); 586 records.push_back(record.get());
693 nodes[i]->AddChild(nodes[(i * 2) + 1]); 587 level_0_child->AddChild(record.PassAs<RTreeNodeBase>());
694 nodes[i]->AddChild(nodes[(i * 2) + 2]); 588 }
695 } 589 level_0_children.push_back(level_0_child.get());
696 // Node 0 is level 2 and gets 2 childen. 590 level_1_child->AddChild(level_0_child.PassAs<RTreeNodeBase>());
697 nodes[0] = new RTree::Node(2); 591 }
698 nodes[0]->AddChild(nodes[1]); 592 level_1_children.push_back(level_1_child.get());
699 nodes[0]->AddChild(nodes[2]); 593 root->AddChild(level_1_child.PassAs<RTreeNodeBase>());
700 // This should now be a valid node structure.
701 ValidateNode(nodes[0], 2U, 2U);
702
703 // Now remove the level 0 nodes, so we get the record nodes as orphans.
704 ScopedVector<RTree::Node> orphans;
705 EXPECT_EQ(nodes[1]->RemoveChild(nodes[3], &orphans), 1U);
706 EXPECT_EQ(nodes[1]->RemoveChild(nodes[4], &orphans), 0U);
707 EXPECT_EQ(nodes[2]->RemoveChild(nodes[5], &orphans), 1U);
708 EXPECT_EQ(nodes[2]->RemoveChild(nodes[6], &orphans), 0U);
709
710 // Orphans should be nodes 7 through 15 in order.
711 EXPECT_EQ(orphans.size(), 8U);
712 for (int i = 0; i < 8; ++i) {
713 EXPECT_EQ(orphans[i], nodes[i + 7]);
714 } 594 }
715 595
716 // Now we remove nodes 1 and 2 from the root, expecting no further orphans. 596 // This should now be a valid tree structure.
717 // This prevents a crash due to double-delete on test exit, as no node should 597 ValidateNode(root.get(), 2U, 2U);
718 // own any other node right now. 598 EXPECT_EQ(2U, level_1_children.size());
719 EXPECT_EQ(nodes[0]->RemoveChild(nodes[1], &orphans), 1U); 599 EXPECT_EQ(4U, level_0_children.size());
720 EXPECT_EQ(orphans.size(), 8U); 600 EXPECT_EQ(8U, records.size());
721 EXPECT_EQ(nodes[0]->RemoveChild(nodes[2], &orphans), 0U);
722 EXPECT_EQ(orphans.size(), 8U);
723 601
724 // Prevent double-delete of nodes by both nodes and orphans. 602 // Now remove all of the level 0 nodes so we get the record nodes as orphans.
725 orphans.weak_clear(); 603 RTreeNodes orphans;
604 for (size_t i = 0; i < level_0_children.size(); ++i)
605 level_1_children[i / 2]->RemoveChild(level_0_children[i], &orphans);
606
607 // Orphans should be all 8 records but no order guarantee.
608 EXPECT_EQ(8U, orphans.size());
609 for (std::vector<RTreeRecord*>::iterator it = records.begin();
610 it != records.end(); ++it) {
611 RTreeNodes::iterator orphan =
612 std::find(orphans.begin(), orphans.end(), *it);
613 EXPECT_NE(orphan, orphans.end());
614 orphans.erase(orphan);
615 }
616 EXPECT_EQ(0U, orphans.size());
726 } 617 }
727 618
728 TEST_F(RTreeTest, NodeRemoveAndReturnLastChild) { 619 TEST_F(RTreeNodeTest, RemoveAndReturnLastChild) {
729 scoped_ptr<RTree::Node> test_parent(new RTree::Node(0)); 620 scoped_ptr<RTreeNode> test_parent(new RTreeNode);
730 scoped_ptr<RTree::Node> child_one(new RTree::Node(Rect(0, 0, 1, 1), 1)); 621 test_parent->AddChild(
731 scoped_ptr<RTree::Node> child_two(new RTree::Node(Rect(0, 0, 2, 2), 2)); 622 scoped_ptr<RTreeNodeBase>(new RTreeRecord(Rect(0, 0, 1, 1), 1)));
732 scoped_ptr<RTree::Node> child_three(new RTree::Node(Rect(0, 0, 3, 3), 3)); 623 test_parent->AddChild(
733 test_parent->AddChild(child_one.get()); 624 scoped_ptr<RTreeNodeBase>(new RTreeRecord(Rect(0, 0, 2, 2), 2)));
734 test_parent->AddChild(child_two.get()); 625 test_parent->AddChild(
735 test_parent->AddChild(child_three.get()); 626 scoped_ptr<RTreeNodeBase>(new RTreeRecord(Rect(0, 0, 3, 3), 3)));
736 ValidateNode(test_parent.get(), 1U, 5U); 627 ValidateNode(test_parent.get(), 1U, 5U);
737 628
738 EXPECT_EQ(test_parent->RemoveAndReturnLastChild().release(), 629 RTreeNodeBase* child = test_parent->child(2);
739 child_three.get()); 630 scoped_ptr<RTreeNodeBase> last_child(test_parent->RemoveAndReturnLastChild());
740 EXPECT_EQ(test_parent->count(), 2U); 631 EXPECT_EQ(child, last_child.get());
741 test_parent->RecomputeBoundsNoParents(); 632 EXPECT_EQ(2U, test_parent->count());
633 NodeRecomputeLocalBounds(test_parent.get());
742 ValidateNode(test_parent.get(), 1U, 5U); 634 ValidateNode(test_parent.get(), 1U, 5U);
743 635
744 EXPECT_EQ(test_parent->RemoveAndReturnLastChild().release(), child_two.get()); 636 child = test_parent->child(1);
745 EXPECT_EQ(test_parent->count(), 1U); 637 scoped_ptr<RTreeNodeBase> middle_child(
746 test_parent->RecomputeBoundsNoParents(); 638 test_parent->RemoveAndReturnLastChild());
639 EXPECT_EQ(child, middle_child.get());
640 EXPECT_EQ(1U, test_parent->count());
641 NodeRecomputeLocalBounds(test_parent.get());
747 ValidateNode(test_parent.get(), 1U, 5U); 642 ValidateNode(test_parent.get(), 1U, 5U);
748 643
749 EXPECT_EQ(test_parent->RemoveAndReturnLastChild().release(), child_one.get()); 644 child = test_parent->child(0);
750 EXPECT_EQ(test_parent->count(), 0U); 645 scoped_ptr<RTreeNodeBase> first_child(
646 test_parent->RemoveAndReturnLastChild());
647 EXPECT_EQ(child, first_child.get());
648 EXPECT_EQ(0U, test_parent->count());
751 } 649 }
752 650
753 TEST_F(RTreeTest, NodeLeastOverlapIncrease) { 651 TEST_F(RTreeNodeTest, LeastOverlapIncrease) {
754 scoped_ptr<RTree::Node> test_parent(new RTree::Node(0)); 652 scoped_ptr<RTreeNode> test_parent(NewNodeAtLevel(1));
755 // Construct 4 nodes with 1x2 retangles spaced horizontally 1 pixel apart, or: 653 // Construct 4 nodes with 1x2 rects spaced horizontally 1 pixel apart, or:
756 // 654 //
757 // a b c d 655 // a b c d
758 // a b c d 656 // a b c d
759 // 657 //
760 for (int i = 0; i < 4; ++i) { 658 for (int i = 0; i < 4; ++i) {
761 test_parent->AddChild(new RTree::Node(Rect(i * 2, 0, 1, 2), i + 1)); 659 scoped_ptr<RTreeNode> node(new RTreeNode);
660 scoped_ptr<RTreeRecord> record(
661 new RTreeRecord(Rect(i * 2, 0, 1, 2), i + 1));
662 node->AddChild(record.PassAs<RTreeNodeBase>());
663 test_parent->AddChild(node.PassAs<RTreeNodeBase>());
762 } 664 }
763 665
764 ValidateNode(test_parent.get(), 1U, 5U); 666 ValidateNode(test_parent.get(), 1U, 5U);
765 667
766 // Test rect at (7, 0) should require minimum overlap on the part of the 668 // Test rect at (7, 0) should require minimum overlap on the part of the
767 // fourth rectangle to add: 669 // fourth rectangle to add:
768 // 670 //
769 // a b c dT 671 // a b c dT
770 // a b c d 672 // a b c d
771 // 673 //
772 Rect test_rect_far(7, 0, 1, 1); 674 Rect test_rect_far(7, 0, 1, 1);
773 std::vector<Rect> expanded_rects; 675 RTreeRects expanded_rects;
774 BuildExpandedRects(test_parent.get(), test_rect_far, &expanded_rects); 676 BuildExpandedRects(test_parent.get(), test_rect_far, &expanded_rects);
775 RTree::Node* result = 677 RTreeNode* result = NodeLeastOverlapIncrease(
776 test_parent->LeastOverlapIncrease(test_rect_far, expanded_rects); 678 test_parent.get(), test_rect_far, expanded_rects);
777 EXPECT_EQ(result->key(), 4); 679 EXPECT_EQ(4, record(result, 0)->key());
778 680
779 // Test rect covering the bottom half of all children should be a 4-way tie, 681 // Test rect covering the bottom half of all children should be a 4-way tie,
780 // so LeastOverlapIncrease should return NULL: 682 // so LeastOverlapIncrease should return NULL:
781 // 683 //
782 // a b c d 684 // a b c d
783 // TTTTTTT 685 // TTTTTTT
784 // 686 //
785 Rect test_rect_tie(0, 1, 7, 1); 687 Rect test_rect_tie(0, 1, 7, 1);
786 BuildExpandedRects(test_parent.get(), test_rect_tie, &expanded_rects); 688 BuildExpandedRects(test_parent.get(), test_rect_tie, &expanded_rects);
787 result = test_parent->LeastOverlapIncrease(test_rect_tie, expanded_rects); 689 result = NodeLeastOverlapIncrease(
690 test_parent.get(), test_rect_tie, expanded_rects);
788 EXPECT_TRUE(result == NULL); 691 EXPECT_TRUE(result == NULL);
789 692
790 // Test rect completely inside c should return the third rectangle: 693 // Test rect completely inside c should return the third rectangle:
791 // 694 //
792 // a b T d 695 // a b T d
793 // a b c d 696 // a b c d
794 // 697 //
795 Rect test_rect_inside(4, 0, 1, 1); 698 Rect test_rect_inside(4, 0, 1, 1);
796 BuildExpandedRects(test_parent.get(), test_rect_inside, &expanded_rects); 699 BuildExpandedRects(test_parent.get(), test_rect_inside, &expanded_rects);
797 result = test_parent->LeastOverlapIncrease(test_rect_inside, expanded_rects); 700 result = NodeLeastOverlapIncrease(
798 EXPECT_EQ(result->key(), 3); 701 test_parent.get(), test_rect_inside, expanded_rects);
702 EXPECT_EQ(3, record(result, 0)->key());
799 703
800 // Add a rectangle that overlaps completely with rectangle c, to test 704 // Add a rectangle that overlaps completely with rectangle c, to test
801 // when there is a tie between two completely contained rectangles: 705 // when there is a tie between two completely contained rectangles:
802 // 706 //
803 // a b Ted 707 // a b Ted
804 // a b eed 708 // a b eed
805 // 709 //
806 test_parent->AddChild(new RTree::Node(Rect(4, 0, 2, 2), 9)); 710 scoped_ptr<RTreeNode> record_parent(new RTreeNode);
711 record_parent->AddChild(
712 scoped_ptr<RTreeNodeBase>(new RTreeRecord(Rect(4, 0, 2, 2), 9)));
713 test_parent->AddChild(record_parent.PassAs<RTreeNodeBase>());
807 BuildExpandedRects(test_parent.get(), test_rect_inside, &expanded_rects); 714 BuildExpandedRects(test_parent.get(), test_rect_inside, &expanded_rects);
808 result = test_parent->LeastOverlapIncrease(test_rect_inside, expanded_rects); 715 result = NodeLeastOverlapIncrease(
716 test_parent.get(), test_rect_inside, expanded_rects);
809 EXPECT_TRUE(result == NULL); 717 EXPECT_TRUE(result == NULL);
810 } 718 }
811 719
812 TEST_F(RTreeTest, NodeLeastAreaEnlargement) { 720 TEST_F(RTreeNodeTest, LeastAreaEnlargement) {
813 scoped_ptr<RTree::Node> test_parent(new RTree::Node(0)); 721 scoped_ptr<RTreeNode> test_parent(NewNodeAtLevel(1));
814 // Construct 4 nodes in a cross-hairs style configuration: 722 // Construct 4 nodes in a cross-hairs style configuration:
815 // 723 //
816 // a 724 // a
817 // b c 725 // b c
818 // d 726 // d
819 // 727 //
820 test_parent->AddChild(new RTree::Node(Rect(1, 0, 1, 1), 1)); 728 scoped_ptr<RTreeNode> node(new RTreeNode);
821 test_parent->AddChild(new RTree::Node(Rect(0, 1, 1, 1), 2)); 729 node->AddChild(
822 test_parent->AddChild(new RTree::Node(Rect(2, 1, 1, 1), 3)); 730 scoped_ptr<RTreeNodeBase>(new RTreeRecord(Rect(1, 0, 1, 1), 1)));
823 test_parent->AddChild(new RTree::Node(Rect(1, 2, 1, 1), 4)); 731 test_parent->AddChild(node.PassAs<RTreeNodeBase>());
732 node.reset(new RTreeNode);
733 node->AddChild(
734 scoped_ptr<RTreeNodeBase>(new RTreeRecord(Rect(0, 1, 1, 1), 2)));
735 test_parent->AddChild(node.PassAs<RTreeNodeBase>());
736 node.reset(new RTreeNode);
737 node->AddChild(
738 scoped_ptr<RTreeNodeBase>(new RTreeRecord(Rect(2, 1, 1, 1), 3)));
739 test_parent->AddChild(node.PassAs<RTreeNodeBase>());
740 node.reset(new RTreeNode);
741 node->AddChild(
742 scoped_ptr<RTreeNodeBase>(new RTreeRecord(Rect(1, 2, 1, 1), 4)));
743 test_parent->AddChild(node.PassAs<RTreeNodeBase>());
824 744
825 ValidateNode(test_parent.get(), 1U, 5U); 745 ValidateNode(test_parent.get(), 1U, 5U);
826 746
827 // Test rect at (1, 3) should require minimum area to add to Node d: 747 // Test rect at (1, 3) should require minimum area to add to Node d:
828 // 748 //
829 // a 749 // a
830 // b c 750 // b c
831 // d 751 // d
832 // T 752 // T
833 // 753 //
834 Rect test_rect_below(1, 3, 1, 1); 754 Rect test_rect_below(1, 3, 1, 1);
835 std::vector<Rect> expanded_rects; 755 RTreeRects expanded_rects;
836 BuildExpandedRects(test_parent.get(), test_rect_below, &expanded_rects); 756 BuildExpandedRects(test_parent.get(), test_rect_below, &expanded_rects);
837 RTree::Node* result = 757 RTreeNode* result = NodeLeastAreaEnlargement(
838 test_parent->LeastAreaEnlargement(test_rect_below, expanded_rects); 758 test_parent.get(), test_rect_below, expanded_rects);
839 EXPECT_EQ(result->key(), 4); 759 EXPECT_EQ(4, record(result, 0)->key());
840 760
841 // Test rect completely inside b should require minimum area to add to Node b: 761 // Test rect completely inside b should require minimum area to add to Node b:
842 // 762 //
843 // a 763 // a
844 // T c 764 // T c
845 // d 765 // d
846 // 766 //
847 Rect test_rect_inside(0, 1, 1, 1); 767 Rect test_rect_inside(0, 1, 1, 1);
848 BuildExpandedRects(test_parent.get(), test_rect_inside, &expanded_rects); 768 BuildExpandedRects(test_parent.get(), test_rect_inside, &expanded_rects);
849 result = test_parent->LeastAreaEnlargement(test_rect_inside, expanded_rects); 769 result = NodeLeastAreaEnlargement(
850 EXPECT_EQ(result->key(), 2); 770 test_parent.get(), test_rect_inside, expanded_rects);
771 EXPECT_EQ(2, record(result, 0)->key());
851 772
852 // Add e at (0, 1) to overlap b and c, to test tie-breaking: 773 // Add e at (0, 1) to overlap b and c, to test tie-breaking:
853 // 774 //
854 // a 775 // a
855 // eee 776 // eee
856 // d 777 // d
857 // 778 //
858 test_parent->AddChild(new RTree::Node(Rect(0, 1, 3, 1), 7)); 779 node.reset(new RTreeNode);
780 node->AddChild(
781 scoped_ptr<RTreeNodeBase>(new RTreeRecord(Rect(0, 1, 3, 1), 7)));
782 test_parent->AddChild(node.PassAs<RTreeNodeBase>());
859 783
860 ValidateNode(test_parent.get(), 1U, 5U); 784 ValidateNode(test_parent.get(), 1U, 5U);
861 785
862 // Test rect at (3, 1) should tie between c and e, but c has smaller area so 786 // Test rect at (3, 1) should tie between c and e, but c has smaller area so
863 // the algorithm should select c: 787 // the algorithm should select c:
864 // 788 //
865 // 789 //
866 // a 790 // a
867 // eeeT 791 // eeeT
868 // d 792 // d
869 // 793 //
870 Rect test_rect_tie_breaker(3, 1, 1, 1); 794 Rect test_rect_tie_breaker(3, 1, 1, 1);
871 BuildExpandedRects(test_parent.get(), test_rect_tie_breaker, &expanded_rects); 795 BuildExpandedRects(test_parent.get(), test_rect_tie_breaker, &expanded_rects);
872 result = 796 result = NodeLeastAreaEnlargement(
873 test_parent->LeastAreaEnlargement(test_rect_tie_breaker, expanded_rects); 797 test_parent.get(), test_rect_tie_breaker, expanded_rects);
874 EXPECT_EQ(result->key(), 3); 798 EXPECT_EQ(3, record(result, 0)->key());
799 }
800
801 // RTreeTest ------------------------------------------------------------------
802
803 // An empty RTree should never return AppendIntersectingRecords results, and
804 // RTrees should be empty upon construction.
805 TEST_F(RTreeTest, AppendIntersectingRecordsOnEmptyTree) {
806 RT rt(2, 10);
807 ValidateRTree(&rt);
808 RT::Matches results;
809 Rect test_rect(25, 25);
810 rt.AppendIntersectingRecords(test_rect, &results);
811 EXPECT_EQ(0U, results.size());
812 ValidateRTree(&rt);
813 }
814
815 // Clear should empty the tree, meaning that all queries should not return
816 // results after.
817 TEST_F(RTreeTest, ClearEmptiesTreeOfSingleNode) {
818 RT rt(2, 5);
819 rt.Insert(Rect(0, 0, 100, 100), 1);
820 rt.Clear();
821 RT::Matches results;
822 Rect test_rect(1, 1);
823 rt.AppendIntersectingRecords(test_rect, &results);
824 EXPECT_EQ(0U, results.size());
825 ValidateRTree(&rt);
826 }
827
828 // Even with a complex internal structure, clear should empty the tree, meaning
829 // that all queries should not return results after.
830 TEST_F(RTreeTest, ClearEmptiesTreeOfManyNodes) {
831 RT rt(2, 5);
832 AddStackedSquares(&rt, 100);
833 rt.Clear();
834 RT::Matches results;
835 Rect test_rect(1, 1);
836 rt.AppendIntersectingRecords(test_rect, &results);
837 EXPECT_EQ(0U, results.size());
838 ValidateRTree(&rt);
839 }
840
841 // Duplicate inserts should overwrite previous inserts.
842 TEST_F(RTreeTest, DuplicateInsertsOverwrite) {
843 RT rt(2, 5);
844 // Add 100 stacked squares, but always with duplicate key of 0.
845 for (int i = 1; i <= 100; ++i) {
846 rt.Insert(Rect(0, 0, i, i), 0);
847 ValidateRTree(&rt);
848 }
849 RT::Matches results;
850 Rect test_rect(1, 1);
851 rt.AppendIntersectingRecords(test_rect, &results);
852 EXPECT_EQ(1U, results.size());
853 EXPECT_EQ(1U, results.count(0));
854 }
855
856 // Call Remove() once on something that's been inserted repeatedly.
857 TEST_F(RTreeTest, DuplicateInsertRemove) {
858 RT rt(3, 9);
859 AddStackedSquares(&rt, 25);
860 for (int i = 1; i <= 100; ++i) {
861 rt.Insert(Rect(0, 0, i, i), 26);
862 ValidateRTree(&rt);
863 }
864 rt.Remove(26);
865 RT::Matches results;
866 Rect test_rect(1, 1);
867 rt.AppendIntersectingRecords(test_rect, &results);
868 EXPECT_EQ(25U, results.size());
869 VerifyAllKeys(results);
870 }
871
872 // Call Remove() repeatedly on something that's been inserted once.
873 TEST_F(RTreeTest, InsertDuplicateRemove) {
874 RT rt(7, 15);
875 AddStackedSquares(&rt, 101);
876 for (int i = 0; i < 100; ++i) {
877 rt.Remove(101);
878 ValidateRTree(&rt);
879 }
880 RT::Matches results;
881 Rect test_rect(1, 1);
882 rt.AppendIntersectingRecords(test_rect, &results);
883 EXPECT_EQ(100U, results.size());
884 VerifyAllKeys(results);
885 }
886
887 // Stacked rects should meet all matching queries regardless of nesting.
888 TEST_F(RTreeTest, AppendIntersectingRecordsStackedSquaresNestedHit) {
889 RT rt(2, 5);
890 AddStackedSquares(&rt, 100);
891 RT::Matches results;
892 Rect test_rect(1, 1);
893 rt.AppendIntersectingRecords(test_rect, &results);
894 EXPECT_EQ(100U, results.size());
895 VerifyAllKeys(results);
896 }
897
898 // Stacked rects should meet all matching queries when contained completely by
899 // the query rectangle.
900 TEST_F(RTreeTest, AppendIntersectingRecordsStackedSquaresContainedHit) {
901 RT rt(2, 10);
902 AddStackedSquares(&rt, 100);
903 RT::Matches results;
904 Rect test_rect(0, 0, 100, 100);
905 rt.AppendIntersectingRecords(test_rect, &results);
906 EXPECT_EQ(100U, results.size());
907 VerifyAllKeys(results);
908 }
909
910 // Stacked rects should miss a missing query when the query has no intersection
911 // with the rects.
912 TEST_F(RTreeTest, AppendIntersectingRecordsStackedSquaresCompleteMiss) {
913 RT rt(2, 7);
914 AddStackedSquares(&rt, 100);
915 RT::Matches results;
916 Rect test_rect(150, 150, 100, 100);
917 rt.AppendIntersectingRecords(test_rect, &results);
918 EXPECT_EQ(0U, results.size());
919 }
920
921 // Removing half the nodes after insertion should still result in a valid tree.
922 TEST_F(RTreeTest, RemoveHalfStackedRects) {
923 RT rt(2, 11);
924 AddStackedSquares(&rt, 200);
925 for (int i = 101; i <= 200; ++i) {
926 rt.Remove(i);
927 ValidateRTree(&rt);
928 }
929 RT::Matches results;
930 Rect test_rect(1, 1);
931 rt.AppendIntersectingRecords(test_rect, &results);
932 EXPECT_EQ(100U, results.size());
933 VerifyAllKeys(results);
934
935 // Add the nodes back in.
936 for (int i = 101; i <= 200; ++i) {
937 rt.Insert(Rect(0, 0, i, i), i);
938 ValidateRTree(&rt);
939 }
940 results.clear();
941 rt.AppendIntersectingRecords(test_rect, &results);
942 EXPECT_EQ(200U, results.size());
943 VerifyAllKeys(results);
944 }
945
946 TEST_F(RTreeTest, InsertDupToRoot) {
947 RT rt(2, 5);
948 rt.Insert(Rect(0, 0, 1, 2), 1);
949 ValidateRTree(&rt);
950 rt.Insert(Rect(0, 0, 2, 1), 1);
951 ValidateRTree(&rt);
952 }
953
954 TEST_F(RTreeTest, InsertNegativeCoordsRect) {
955 RT rt(5, 11);
956 for (int i = 1; i <= 100; ++i) {
957 rt.Insert(Rect(-i, -i, i, i), (i * 2) - 1);
958 ValidateRTree(&rt);
959 rt.Insert(Rect(0, 0, i, i), i * 2);
960 ValidateRTree(&rt);
961 }
962 RT::Matches results;
963 Rect test_rect(-1, -1, 2, 2);
964 rt.AppendIntersectingRecords(test_rect, &results);
965 EXPECT_EQ(200U, results.size());
966 VerifyAllKeys(results);
967 }
968
969 TEST_F(RTreeTest, RemoveNegativeCoordsRect) {
970 RT rt(7, 21);
971
972 // Add 100 positive stacked squares.
973 AddStackedSquares(&rt, 100);
974
975 // Now add 100 negative stacked squares.
976 for (int i = 101; i <= 200; ++i) {
977 rt.Insert(Rect(100 - i, 100 - i, i - 100, i - 100), 301 - i);
978 ValidateRTree(&rt);
979 }
980
981 // Now remove half of the negative squares.
982 for (int i = 101; i <= 150; ++i) {
983 rt.Remove(301 - i);
984 ValidateRTree(&rt);
985 }
986
987 // Queries should return 100 positive and 50 negative stacked squares.
988 RT::Matches results;
989 Rect test_rect(-1, -1, 2, 2);
990 rt.AppendIntersectingRecords(test_rect, &results);
991 EXPECT_EQ(150U, results.size());
992 VerifyAllKeys(results);
993 }
994
995 TEST_F(RTreeTest, InsertEmptyRectReplacementRemovesKey) {
996 RT rt(10, 31);
997 AddStackedSquares(&rt, 50);
998 ValidateRTree(&rt);
999
1000 // Replace last square with empty rect.
1001 rt.Insert(Rect(), 50);
1002 ValidateRTree(&rt);
1003
1004 // Now query large area to get all rects in tree.
1005 RT::Matches results;
1006 Rect test_rect(0, 0, 100, 100);
1007 rt.AppendIntersectingRecords(test_rect, &results);
1008
1009 // Should only be 49 rects in tree.
1010 EXPECT_EQ(49U, results.size());
1011 VerifyAllKeys(results);
875 } 1012 }
876 1013
877 } // namespace gfx 1014 } // namespace gfx
OLDNEW
« 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