src/ui/gfx/geometry/r_tree_unittest.cc

   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
   3 // found in the LICENSE file.
   4
   5 #include "testing/gtest/include/gtest/gtest.h"
   6 #include "ui/gfx/geometry/r_tree.h"
   7 #include "ui/gfx/geometry/rect.h"
   8
   9 namespace gfx {
  10
  11 class RTreeTest : public ::testing::Test {
  12  protected:
  13   // Given a pointer to an RTree, traverse it and verify its internal structure
  14   // is consistent with the RTree semantics.
  15   void ValidateRTree(RTree* rt) {
  16     // If RTree is empty it should have an empty rectangle.
  17     if (!rt->root_->count()) {
  18       EXPECT_TRUE(rt->root_->rect().IsEmpty());
  19       EXPECT_EQ(rt->root_->level(), 0);
  20       return;
  21     }
  22     // Root is allowed to have fewer than min_children_ but never more than
  23     // max_children_.
  24     EXPECT_LE(rt->root_->count(), rt->max_children_);
  25     // The root should never be a record node.
  26     EXPECT_GT(rt->root_->level(), -1);
  27     EXPECT_FALSE(rt->root_->key());
  28     // The root should never have a parent pointer.
  29     EXPECT_FALSE(rt->root_->parent());
  30     // Bounds must be consistent on the root.
  31     CheckBoundsConsistent(rt->root_.get());
  32     // We traverse root's children ourselves, so we can avoid asserts about
  33     // root's potential inconsistencies.
  34     for (size_t i = 0; i < rt->root_->children_.size(); ++i) {
  35       ValidateNode(
  36           rt->root_->children_[i], rt->min_children_, rt->max_children_);
  37     }
  38   }
  39
  40   // Recursive descent method used by ValidateRTree to check each node within
  41   // the RTree for consistency with RTree semantics.
  42   void ValidateNode(RTree::Node* node,
  43                     size_t min_children,
  44                     size_t max_children) {
  45     // Record nodes have different requirements, handle up front.
  46     if (node->level() == -1) {
  47       // Record nodes may have no children.
  48       EXPECT_EQ(node->count(), 0U);
  49       // They must have an associated non-NULL key.
  50       EXPECT_TRUE(node->key());
  51       // They must always have a parent.
  52       EXPECT_TRUE(node->parent());
  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     }
  63   }
  64
  65   // Check bounds are consistent with children bounds, and other checks
  66   // convenient to do while enumerating the children of node.
  67   void CheckBoundsConsistent(RTree::Node* node) {
  68     EXPECT_FALSE(node->rect_.IsEmpty());
  69     Rect check_bounds;
  70     for (size_t i = 0; i < node->children_.size(); ++i) {
  71       RTree::Node* child_node = node->children_[i];
  72       check_bounds.Union(child_node->rect());
  73       EXPECT_EQ(node->level() - 1, child_node->level());
  74       EXPECT_EQ(node, child_node->parent());
  75     }
  76     EXPECT_EQ(node->rect_, check_bounds);
  77   }
  78
  79   // Adds count squares stacked around the point (0,0) with key equal to width.
  80   void AddStackedSquares(RTree* rt, int count) {
  81     for (int i = 1; i <= count; ++i) {
  82       rt->Insert(Rect(0, 0, i, i), i);
  83       ValidateRTree(rt);
  84     }
  85   }
  86
  87   // Given an unordered list of matching keys, verify that it contains all
  88   // values [1..length] for the length of that list.
  89   void VerifyAllKeys(const base::hash_set<intptr_t>& keys) {
  90     // Verify that the keys are in values [1,count].
  91     for (size_t i = 1; i <= keys.size(); ++i) {
  92       EXPECT_EQ(keys.count(i), 1U);
  93     }
  94   }
  95
  96   // 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
  98   // the node and the argument rectangle.
  99   void BuildExpandedRects(RTree::Node* node,
 100                           const Rect& rect,
 101                           std::vector<Rect>* expanded_rects) {
 102     expanded_rects->clear();
 103     expanded_rects->reserve(node->children_.size());
 104     for (size_t i = 0; i < node->children_.size(); ++i) {
 105       Rect expanded_rect(rect);
 106       expanded_rect.Union(node->children_[i]->rect_);
 107       expanded_rects->push_back(expanded_rect);
 108     }
 109   }
 110 };
 111
 112 // An empty RTree should never return Query results, and RTrees should be empty
 113 // upon construction.
 114 TEST_F(RTreeTest, QueryEmptyTree) {
 115   RTree rt(2, 10);
 116   ValidateRTree(&rt);
 117   base::hash_set<intptr_t> results;
 118   Rect test_rect(25, 25);
 119   rt.Query(test_rect, &results);
 120   EXPECT_EQ(results.size(), 0U);
 121   ValidateRTree(&rt);
 122 }
 123
 124 // Clear should empty the tree, meaning that all queries should not return
 125 // results after.
 126 TEST_F(RTreeTest, ClearEmptiesTreeOfSingleNode) {
 127   RTree rt(2, 5);
 128   rt.Insert(Rect(0, 0, 100, 100), 1);
 129   rt.Clear();
 130   base::hash_set<intptr_t> results;
 131   Rect test_rect(1, 1);
 132   rt.Query(test_rect, &results);
 133   EXPECT_EQ(results.size(), 0U);
 134   ValidateRTree(&rt);
 135 }
 136
 137 // Even with a complex internal structure, clear should empty the tree, meaning
 138 // that all queries should not return results after.
 139 TEST_F(RTreeTest, ClearEmptiesTreeOfManyNodes) {
 140   RTree rt(2, 5);
 141   AddStackedSquares(&rt, 100);
 142   rt.Clear();
 143   base::hash_set<intptr_t> results;
 144   Rect test_rect(1, 1);
 145   rt.Query(test_rect, &results);
 146   EXPECT_EQ(results.size(), 0U);
 147   ValidateRTree(&rt);
 148 }
 149
 150 // Duplicate inserts should overwrite previous inserts.
 151 TEST_F(RTreeTest, DuplicateInsertsOverwrite) {
 152   RTree rt(2, 5);
 153   // Add 100 stacked squares, but always with duplicate key of 1.
 154   for (int i = 1; i <= 100; ++i) {
 155     rt.Insert(Rect(0, 0, i, i), 1);
 156     ValidateRTree(&rt);
 157   }
 158   base::hash_set<intptr_t> results;
 159   Rect test_rect(1, 1);
 160   rt.Query(test_rect, &results);
 161   EXPECT_EQ(results.size(), 1U);
 162   EXPECT_EQ(results.count(1), 1U);
 163 }
 164
 165 // Call Remove() once on something that's been inserted repeatedly.
 166 TEST_F(RTreeTest, DuplicateInsertRemove) {
 167   RTree rt(3, 9);
 168   AddStackedSquares(&rt, 25);
 169   for (int i = 1; i <= 100; ++i) {
 170     rt.Insert(Rect(0, 0, i, i), 26);
 171     ValidateRTree(&rt);
 172   }
 173   rt.Remove(26);
 174   base::hash_set<intptr_t> results;
 175   Rect test_rect(1, 1);
 176   rt.Query(test_rect, &results);
 177   EXPECT_EQ(results.size(), 25U);
 178   VerifyAllKeys(results);
 179 }
 180
 181 // Call Remove() repeatedly on something that's been inserted once.
 182 TEST_F(RTreeTest, InsertDuplicateRemove) {
 183   RTree rt(7, 15);
 184   AddStackedSquares(&rt, 101);
 185   for (int i = 0; i < 100; ++i) {
 186     rt.Remove(101);
 187     ValidateRTree(&rt);
 188   }
 189   base::hash_set<intptr_t> results;
 190   Rect test_rect(1, 1);
 191   rt.Query(test_rect, &results);
 192   EXPECT_EQ(results.size(), 100U);
 193   VerifyAllKeys(results);
 194 }
 195
 196 // Stacked rects should meet all matching queries regardless of nesting.
 197 TEST_F(RTreeTest, QueryStackedSquaresNestedHit) {
 198   RTree rt(2, 5);
 199   AddStackedSquares(&rt, 100);
 200   base::hash_set<intptr_t> results;
 201   Rect test_rect(1, 1);
 202   rt.Query(test_rect, &results);
 203   EXPECT_EQ(results.size(), 100U);
 204   VerifyAllKeys(results);
 205 }
 206
 207 // Stacked rects should meet all matching queries when contained completely by
 208 // the query rectangle.
 209 TEST_F(RTreeTest, QueryStackedSquaresContainedHit) {
 210   RTree rt(2, 10);
 211   AddStackedSquares(&rt, 100);
 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, InsertNegativeCoordsRect) {
 255   RTree rt(5, 11);
 256   for (int i = 1; i <= 100; ++i) {
 257     rt.Insert(Rect(-i, -i, i, i), (i * 2) - 1);
 258     ValidateRTree(&rt);
 259     rt.Insert(Rect(0, 0, i, i), i * 2);
 260     ValidateRTree(&rt);
 261   }
 262   base::hash_set<intptr_t> results;
 263   Rect test_rect(-1, -1, 2, 2);
 264   rt.Query(test_rect, &results);
 265   EXPECT_EQ(results.size(), 200U);
 266   VerifyAllKeys(results);
 267 }
 268
 269 TEST_F(RTreeTest, RemoveNegativeCoordsRect) {
 270   RTree rt(7, 21);
 271   // Add 100 positive stacked squares.
 272   AddStackedSquares(&rt, 100);
 273   // Now add 100 negative stacked squares.
 274   for (int i = 101; i <= 200; ++i) {
 275     rt.Insert(Rect(100 - i, 100 - i, i - 100, i - 100), 301 - i);
 276     ValidateRTree(&rt);
 277   }
 278   // Now remove half of the negative squares.
 279   for (int i = 101; i <= 150; ++i) {
 280     rt.Remove(301 - i);
 281     ValidateRTree(&rt);
 282   }
 283   // Queries should return 100 positive and 50 negative stacked squares.
 284   base::hash_set<intptr_t> results;
 285   Rect test_rect(-1, -1, 2, 2);
 286   rt.Query(test_rect, &results);
 287   EXPECT_EQ(results.size(), 150U);
 288   VerifyAllKeys(results);
 289 }
 290
 291 TEST_F(RTreeTest, InsertEmptyRectReplacementRemovesKey) {
 292   RTree rt(10, 31);
 293   AddStackedSquares(&rt, 50);
 294   ValidateRTree(&rt);
 295
 296   // Replace last square with empty rect.
 297   rt.Insert(Rect(), 50);
 298   ValidateRTree(&rt);
 299
 300   // Now query large area to get all rects in tree.
 301   base::hash_set<intptr_t> results;
 302   Rect test_rect(0, 0, 100, 100);
 303   rt.Query(test_rect, &results);
 304
 305   // Should only be 49 rects in tree.
 306   EXPECT_EQ(results.size(), 49U);
 307   VerifyAllKeys(results);
 308 }
 309
 310 TEST_F(RTreeTest, NodeRemoveNodesForReinsert) {
 311   // Make a leaf node for testing removal from.
 312   scoped_ptr<RTree::Node> test_node(new RTree::Node(0));
 313   // Build 20 record nodes with rectangle centers going from (1,1) to (20,20)
 314   for (int i = 1; i <= 20; ++i) {
 315     test_node->AddChild(new RTree::Node(Rect(i - 1, i - 1, 2, 2), i));
 316   }
 317   // Quick verification of the node before removing children.
 318   ValidateNode(test_node.get(), 1U, 20U);
 319   // Use a scoped vector to delete all children that get removed from the Node.
 320   ScopedVector<RTree::Node> removals;
 321   test_node->RemoveNodesForReinsert(1, &removals);
 322   // Should have gotten back 1 node pointers.
 323   EXPECT_EQ(removals.size(), 1U);
 324   // There should be 19 left in the test_node.
 325   EXPECT_EQ(test_node->count(), 19U);
 326   // If we fix up the bounds on the test_node, it should verify.
 327   test_node->RecomputeBoundsNoParents();
 328   ValidateNode(test_node.get(), 2U, 20U);
 329   // The node we removed should be node 10, as it was exactly in the center.
 330   EXPECT_EQ(removals[0]->key(), 10);
 331
 332   // Now remove the next 2.
 333   removals.clear();
 334   test_node->RemoveNodesForReinsert(2, &removals);
 335   EXPECT_EQ(removals.size(), 2U);
 336   EXPECT_EQ(test_node->count(), 17U);
 337   test_node->RecomputeBoundsNoParents();
 338   ValidateNode(test_node.get(), 2U, 20U);
 339   // Lastly the 2 nodes we should have gotten back are keys 9 and 11, as their
 340   // centers were the closest to the center of the node bounding box.
 341   base::hash_set<intptr_t> results_hash;
 342   results_hash.insert(removals[0]->key());
 343   results_hash.insert(removals[1]->key());
 344   EXPECT_EQ(results_hash.count(9), 1U);
 345   EXPECT_EQ(results_hash.count(11), 1U);
 346 }
 347
 348 TEST_F(RTreeTest, NodeCompareVertical) {
 349   // One rect with lower y than another should always sort lower than higher y.
 350   RTree::Node low(Rect(0, 1, 10, 10), 1);
 351   RTree::Node middle(Rect(0, 5, 10, 10), 5);
 352   EXPECT_TRUE(RTree::Node::CompareVertical(&low, &middle));
 353   EXPECT_FALSE(RTree::Node::CompareVertical(&middle, &low));
 354
 355   // Try a non-overlapping higher-y rectangle.
 356   RTree::Node high(Rect(-10, 20, 10, 1), 10);
 357   EXPECT_TRUE(RTree::Node::CompareVertical(&low, &high));
 358   EXPECT_FALSE(RTree::Node::CompareVertical(&high, &low));
 359
 360   // Ties are broken by lowest bottom y value.
 361   RTree::Node shorter_tie(Rect(10, 1, 100, 2), 2);
 362   EXPECT_TRUE(RTree::Node::CompareVertical(&shorter_tie, &low));
 363   EXPECT_FALSE(RTree::Node::CompareVertical(&low, &shorter_tie));
 364 }
 365
 366 TEST_F(RTreeTest, NodeCompareHorizontal) {
 367   // One rect with lower x than another should always sort lower than higher x.
 368   RTree::Node low(Rect(1, 0, 10, 10), 1);
 369   RTree::Node middle(Rect(5, 0, 10, 10), 5);
 370   EXPECT_TRUE(RTree::Node::CompareHorizontal(&low, &middle));
 371   EXPECT_FALSE(RTree::Node::CompareHorizontal(&middle, &low));
 372
 373   // Try a non-overlapping higher-x rectangle.
 374   RTree::Node high(Rect(20, -10, 1, 10), 10);
 375   EXPECT_TRUE(RTree::Node::CompareHorizontal(&low, &high));
 376   EXPECT_FALSE(RTree::Node::CompareHorizontal(&high, &low));
 377
 378   // Ties are broken by lowest bottom x value.
 379   RTree::Node shorter_tie(Rect(1, 10, 2, 100), 2);
 380   EXPECT_TRUE(RTree::Node::CompareHorizontal(&shorter_tie, &low));
 381   EXPECT_FALSE(RTree::Node::CompareHorizontal(&low, &shorter_tie));
 382 }
 383
 384 TEST_F(RTreeTest, NodeCompareCenterDistanceFromParent) {
 385   // Create a test node we can add children to, for distance comparisons.
 386   scoped_ptr<RTree::Node> parent(new RTree::Node(0));
 387
 388   // Add three children, one each with centers at (0, 0), (10, 10), (-9, -9),
 389   // around which a bounding box will be centered at (0, 0)
 390   RTree::Node* center_zero = new RTree::Node(Rect(-1, -1, 2, 2), 1);
 391   parent->AddChild(center_zero);
 392
 393   RTree::Node* center_positive = new RTree::Node(Rect(9, 9, 2, 2), 2);
 394   parent->AddChild(center_positive);
 395
 396   RTree::Node* center_negative = new RTree::Node(Rect(-10, -10, 2, 2), 3);
 397   parent->AddChild(center_negative);
 398
 399   ValidateNode(parent.get(), 1U, 5U);
 400   EXPECT_EQ(parent->rect_, Rect(-10, -10, 21, 21));
 401
 402   EXPECT_TRUE(RTree::Node::CompareCenterDistanceFromParent(center_zero,
 403                                                            center_positive));
 404   EXPECT_FALSE(RTree::Node::CompareCenterDistanceFromParent(center_positive,
 405                                                             center_zero));
 406
 407   EXPECT_TRUE(RTree::Node::CompareCenterDistanceFromParent(center_zero,
 408                                                            center_negative));
 409   EXPECT_FALSE(RTree::Node::CompareCenterDistanceFromParent(center_negative,
 410                                                             center_zero));
 411
 412   EXPECT_TRUE(RTree::Node::CompareCenterDistanceFromParent(center_negative,
 413                                                            center_positive));
 414   EXPECT_FALSE(RTree::Node::CompareCenterDistanceFromParent(center_positive,
 415                                                             center_negative));
 416 }
 417
 418 TEST_F(RTreeTest, NodeOverlapIncreaseToAdd) {
 419   // Create a test node with three children, for overlap comparisons.
 420   scoped_ptr<RTree::Node> parent(new RTree::Node(0));
 421
 422   // Add three children, each 4 wide and tall, at (0, 0), (3, 3), (6, 6) with
 423   // overlapping corners.
 424   Rect top(0, 0, 4, 4);
 425   parent->AddChild(new RTree::Node(top, 1));
 426   Rect middle(3, 3, 4, 4);
 427   parent->AddChild(new RTree::Node(middle, 2));
 428   Rect bottom(6, 6, 4, 4);
 429   parent->AddChild(new RTree::Node(bottom, 3));
 430   ValidateNode(parent.get(), 1U, 5U);
 431
 432   // Test a rect in corner.
 433   Rect corner(0, 0, 1, 1);
 434   Rect expanded = top;
 435   expanded.Union(corner);
 436   // It should not add any overlap to add this to the first child at (0, 0);
 437   EXPECT_EQ(parent->OverlapIncreaseToAdd(corner, 0, expanded), 0);
 438
 439   expanded = middle;
 440   expanded.Union(corner);
 441   // Overlap for middle rectangle should increase from 2 pixels at (3, 3) and
 442   // (6, 6) to 17 pixels, as it will now cover 4x4 rectangle top,
 443   // so a change of +15
 444   EXPECT_EQ(parent->OverlapIncreaseToAdd(corner, 1, expanded), 15);
 445
 446   expanded = bottom;
 447   expanded.Union(corner);
 448   // Overlap for bottom rectangle should increase from 1 pixel at (6, 6) to
 449   // 32 pixels, as it will now cover both 4x4 rectangles top and middle,
 450   // so a change of 31
 451   EXPECT_EQ(parent->OverlapIncreaseToAdd(corner, 2, expanded), 31);
 452
 453   // Test a rect that doesn't overlap with anything, in the far right corner.
 454   Rect far_corner(9, 0, 1, 1);
 455   expanded = top;
 456   expanded.Union(far_corner);
 457   // Overlap of top should go from 1 to 4, as it will now cover the entire first
 458   // row of pixels in middle.
 459   EXPECT_EQ(parent->OverlapIncreaseToAdd(far_corner, 0, expanded), 3);
 460
 461   expanded = middle;
 462   expanded.Union(far_corner);
 463   // Overlap of middle should go from 2 to 8, as it will cover the rightmost 4
 464   // pixels of top and the top 4 pixles of bottom as it expands.
 465   EXPECT_EQ(parent->OverlapIncreaseToAdd(far_corner, 1, expanded), 6);
 466
 467   expanded = bottom;
 468   expanded.Union(far_corner);
 469   // Overlap of bottom should go from 1 to 4, as it will now cover the rightmost
 470   // 4 pixels of middle.
 471   EXPECT_EQ(parent->OverlapIncreaseToAdd(far_corner, 2, expanded), 3);
 472 }
 473
 474 TEST_F(RTreeTest, NodeBuildLowBounds) {
 475   ScopedVector<RTree::Node> nodes;
 476   nodes.reserve(10);
 477   for (int i = 1; i <= 10; ++i) {
 478     nodes.push_back(new RTree::Node(Rect(0, 0, i, i), i));
 479   }
 480   std::vector<Rect> vertical_bounds;
 481   std::vector<Rect> horizontal_bounds;
 482   RTree::Node::BuildLowBounds(
 483       nodes.get(), nodes.get(), &vertical_bounds, &horizontal_bounds);
 484   for (int i = 0; i < 10; ++i) {
 485     EXPECT_EQ(vertical_bounds[i], Rect(0, 0, i + 1, i + 1));
 486     EXPECT_EQ(horizontal_bounds[i], Rect(0, 0, i + 1, i + 1));
 487   }
 488 }
 489
 490 TEST_F(RTreeTest, NodeBuildHighBounds) {
 491   ScopedVector<RTree::Node> nodes;
 492   nodes.reserve(25);
 493   for (int i = 0; i < 25; ++i) {
 494     nodes.push_back(new RTree::Node(Rect(i, i, 25 - i, 25 - i), i));
 495   }
 496   std::vector<Rect> vertical_bounds;
 497   std::vector<Rect> horizontal_bounds;
 498   RTree::Node::BuildHighBounds(
 499       nodes.get(), nodes.get(), &vertical_bounds, &horizontal_bounds);
 500   for (int i = 0; i < 25; ++i) {
 501     EXPECT_EQ(vertical_bounds[i], Rect(i, i, 25 - i, 25 - i));
 502     EXPECT_EQ(horizontal_bounds[i], Rect(i, i, 25 - i, 25 - i));
 503   }
 504 }
 505
 506 TEST_F(RTreeTest, NodeChooseSplitAxisAndIndex) {
 507   std::vector<Rect> low_vertical_bounds;
 508   std::vector<Rect> high_vertical_bounds;
 509   std::vector<Rect> low_horizontal_bounds;
 510   std::vector<Rect> high_horizontal_bounds;
 511   // In this test scenario we describe a mirrored, stacked configuration of
 512   // horizontal, 1 pixel high rectangles labeled a-f like this:
 513   //
 514   // shape: | v sort: | h sort: |
 515   // -------+---------+---------+
 516   // aaaaa  |    0    |    0    |
 517   //  bbb   |    1    |    2    |
 518   //   c    |    2    |    4    |
 519   //   d    |    3    |    5    |
 520   //  eee   |    4    |    3    |
 521   // fffff  |    5    |    1    |
 522   //
 523   // These are already sorted vertically from top to bottom. Bounding rectangles
 524   // of these vertically sorted will be 5 wide, i tall bounding boxes.
 525   for (int i = 0; i < 6; ++i) {
 526     low_vertical_bounds.push_back(Rect(0, 0, 5, i + 1));
 527     high_vertical_bounds.push_back(Rect(0, i, 5, 6 - i));
 528   }
 529
 530   // Low bounds of horizontal sort start with bounds of box a and then jump to
 531   // cover everything, as box f is second in horizontal sort.
 532   low_horizontal_bounds.push_back(Rect(0, 0, 5, 1));
 533   for (int i = 0; i < 5; ++i) {
 534     low_horizontal_bounds.push_back(Rect(0, 0, 5, 6));
 535   }
 536
 537   // High horizontal bounds are hand-calculated.
 538   high_horizontal_bounds.push_back(Rect(0, 0, 5, 6));
 539   high_horizontal_bounds.push_back(Rect(0, 1, 5, 5));
 540   high_horizontal_bounds.push_back(Rect(1, 1, 3, 4));
 541   high_horizontal_bounds.push_back(Rect(1, 2, 3, 3));
 542   high_horizontal_bounds.push_back(Rect(2, 2, 1, 2));
 543   high_horizontal_bounds.push_back(Rect(2, 3, 1, 1));
 544
 545   // This should split vertically, right down the middle.
 546   EXPECT_TRUE(RTree::Node::ChooseSplitAxis(low_vertical_bounds,
 547                                            high_vertical_bounds,
 548                                            low_horizontal_bounds,
 549                                            high_horizontal_bounds,
 550                                            2,
 551                                            5));
 552   EXPECT_EQ(3U,
 553             RTree::Node::ChooseSplitIndex(
 554                 2, 5, low_vertical_bounds, high_vertical_bounds));
 555
 556   // We rotate the shape to test horizontal split axis detection:
 557   //
 558   //         +--------+
 559   //         | a    f |
 560   //         | ab  ef |
 561   // sort:   | abcdef |
 562   //         | ab  ef |
 563   //         | a    f |
 564   //         |--------+
 565   // v sort: | 024531 |
 566   // h sort: | 012345 |
 567   //         +--------+
 568   //
 569   // Clear out old bounds first.
 570   low_vertical_bounds.clear();
 571   high_vertical_bounds.clear();
 572   low_horizontal_bounds.clear();
 573   high_horizontal_bounds.clear();
 574
 575   // Low bounds of vertical sort start with bounds of box a and then jump to
 576   // cover everything, as box f is second in vertical sort.
 577   low_vertical_bounds.push_back(Rect(0, 0, 1, 5));
 578   for (int i = 0; i < 5; ++i) {
 579     low_vertical_bounds.push_back(Rect(0, 0, 6, 5));
 580   }
 581
 582   // High vertical bounds are hand-calculated.
 583   high_vertical_bounds.push_back(Rect(0, 0, 6, 5));
 584   high_vertical_bounds.push_back(Rect(1, 0, 5, 5));
 585   high_vertical_bounds.push_back(Rect(1, 1, 4, 3));
 586   high_vertical_bounds.push_back(Rect(2, 1, 3, 3));
 587   high_vertical_bounds.push_back(Rect(2, 2, 2, 1));
 588   high_vertical_bounds.push_back(Rect(3, 2, 1, 1));
 589
 590   // These are already sorted horizontally from left to right. Bounding
 591   // rectangles of these horizontally sorted will be i wide, 5 tall bounding
 592   // boxes.
 593   for (int i = 0; i < 6; ++i) {
 594     low_horizontal_bounds.push_back(Rect(0, 0, i + 1, 5));
 595     high_horizontal_bounds.push_back(Rect(i, 0, 6 - i, 5));
 596   }
 597
 598   // This should split horizontally, right down the middle.
 599   EXPECT_FALSE(RTree::Node::ChooseSplitAxis(low_vertical_bounds,
 600                                             high_vertical_bounds,
 601                                             low_horizontal_bounds,
 602                                             high_horizontal_bounds,
 603                                             2,
 604                                             5));
 605   EXPECT_EQ(3U,
 606             RTree::Node::ChooseSplitIndex(
 607                 2, 5, low_horizontal_bounds, high_horizontal_bounds));
 608 }
 609
 610 TEST_F(RTreeTest, NodeDivideChildren) {
 611   // Create a test node to split.
 612   scoped_ptr<RTree::Node> test_node(new RTree::Node(0));
 613   std::vector<RTree::Node*> sorted_children;
 614   std::vector<Rect> low_bounds;
 615   std::vector<Rect> high_bounds;
 616   // Insert 10 record nodes, also inserting them into our children array.
 617   for (int i = 1; i <= 10; ++i) {
 618     RTree::Node* node = new RTree::Node(Rect(0, 0, i, i), i);
 619     test_node->AddChild(node);
 620     sorted_children.push_back(node);
 621     low_bounds.push_back(Rect(0, 0, i, i));
 622     high_bounds.push_back(Rect(0, 0, 10, 10));
 623   }
 624   // Split the children in half.
 625   scoped_ptr<RTree::Node> split_node(
 626       test_node->DivideChildren(low_bounds, high_bounds, sorted_children, 5));
 627   // Both nodes should be valid.
 628   ValidateNode(test_node.get(), 1U, 10U);
 629   ValidateNode(split_node.get(), 1U, 10U);
 630   // Both nodes should have five children.
 631   EXPECT_EQ(test_node->children_.size(), 5U);
 632   EXPECT_EQ(split_node->children_.size(), 5U);
 633   // Test node should have children 1-5, split node should have children 6-10.
 634   for (int i = 0; i < 5; ++i) {
 635     EXPECT_EQ(test_node->children_[i]->key(), i + 1);
 636     EXPECT_EQ(split_node->children_[i]->key(), i + 6);
 637   }
 638 }
 639
 640 TEST_F(RTreeTest, NodeRemoveChildNoOrphans) {
 641   scoped_ptr<RTree::Node> test_parent(new RTree::Node(0));
 642   scoped_ptr<RTree::Node> child_one(new RTree::Node(Rect(0, 0, 1, 1), 1));
 643   scoped_ptr<RTree::Node> child_two(new RTree::Node(Rect(0, 0, 2, 2), 2));
 644   scoped_ptr<RTree::Node> child_three(new RTree::Node(Rect(0, 0, 3, 3), 3));
 645   test_parent->AddChild(child_one.get());
 646   test_parent->AddChild(child_two.get());
 647   test_parent->AddChild(child_three.get());
 648   ValidateNode(test_parent.get(), 1U, 5U);
 649   // Remove the middle node.
 650   ScopedVector<RTree::Node> orphans;
 651   EXPECT_EQ(test_parent->RemoveChild(child_two.get(), &orphans), 2U);
 652   EXPECT_EQ(orphans.size(), 0U);
 653   EXPECT_EQ(test_parent->count(), 2U);
 654   test_parent->RecomputeBoundsNoParents();
 655   ValidateNode(test_parent.get(), 1U, 5U);
 656   // Remove the end node.
 657   EXPECT_EQ(test_parent->RemoveChild(child_three.get(), &orphans), 1U);
 658   EXPECT_EQ(orphans.size(), 0U);
 659   EXPECT_EQ(test_parent->count(), 1U);
 660   test_parent->RecomputeBoundsNoParents();
 661   ValidateNode(test_parent.get(), 1U, 5U);
 662   // Remove the first node.
 663   EXPECT_EQ(test_parent->RemoveChild(child_one.get(), &orphans), 0U);
 664   EXPECT_EQ(orphans.size(), 0U);
 665   EXPECT_EQ(test_parent->count(), 0U);
 666 }
 667
 668 TEST_F(RTreeTest, NodeRemoveChildOrphans) {
 669   // Build flattened binary tree of Nodes 4 deep, from the record nodes up.
 670   ScopedVector<RTree::Node> nodes;
 671   nodes.resize(15);
 672   // Indicies 7 through 15 are record nodes.
 673   for (int i = 7; i < 15; ++i) {
 674     nodes[i] = new RTree::Node(Rect(0, 0, i, i), i);
 675   }
 676   // Nodes 3 through 6 are level 0 (leaves) and get 2 record nodes each.
 677   for (int i = 3; i < 7; ++i) {
 678     nodes[i] = new RTree::Node(0);
 679     nodes[i]->AddChild(nodes[(i * 2) + 1]);
 680     nodes[i]->AddChild(nodes[(i * 2) + 2]);
 681   }
 682   // Nodes 1 and 2 are level 1 and get 2 leaves each.
 683   for (int i = 1; i < 3; ++i) {
 684     nodes[i] = new RTree::Node(1);
 685     nodes[i]->AddChild(nodes[(i * 2) + 1]);
 686     nodes[i]->AddChild(nodes[(i * 2) + 2]);
 687   }
 688   // Node 0 is level 2 and gets 2 childen.
 689   nodes[0] = new RTree::Node(2);
 690   nodes[0]->AddChild(nodes[1]);
 691   nodes[0]->AddChild(nodes[2]);
 692   // This should now be a valid node structure.
 693   ValidateNode(nodes[0], 2U, 2U);
 694
 695   // Now remove the level 0 nodes, so we get the record nodes as orphans.
 696   ScopedVector<RTree::Node> orphans;
 697   EXPECT_EQ(nodes[1]->RemoveChild(nodes[3], &orphans), 1U);
 698   EXPECT_EQ(nodes[1]->RemoveChild(nodes[4], &orphans), 0U);
 699   EXPECT_EQ(nodes[2]->RemoveChild(nodes[5], &orphans), 1U);
 700   EXPECT_EQ(nodes[2]->RemoveChild(nodes[6], &orphans), 0U);
 701
 702   // Orphans should be nodes 7 through 15 in order.
 703   EXPECT_EQ(orphans.size(), 8U);
 704   for (int i = 0; i < 8; ++i) {
 705     EXPECT_EQ(orphans[i], nodes[i + 7]);
 706   }
 707
 708   // Now we remove nodes 1 and 2 from the root, expecting no further orphans.
 709   // This prevents a crash due to double-delete on test exit, as no node should
 710   // own any other node right now.
 711   EXPECT_EQ(nodes[0]->RemoveChild(nodes[1], &orphans), 1U);
 712   EXPECT_EQ(orphans.size(), 8U);
 713   EXPECT_EQ(nodes[0]->RemoveChild(nodes[2], &orphans), 0U);
 714   EXPECT_EQ(orphans.size(), 8U);
 715
 716   // Prevent double-delete of nodes by both nodes and orphans.
 717   orphans.weak_clear();
 718 }
 719
 720 TEST_F(RTreeTest, NodeRemoveAndReturnLastChild) {
 721   scoped_ptr<RTree::Node> test_parent(new RTree::Node(0));
 722   scoped_ptr<RTree::Node> child_one(new RTree::Node(Rect(0, 0, 1, 1), 1));
 723   scoped_ptr<RTree::Node> child_two(new RTree::Node(Rect(0, 0, 2, 2), 2));
 724   scoped_ptr<RTree::Node> child_three(new RTree::Node(Rect(0, 0, 3, 3), 3));
 725   test_parent->AddChild(child_one.get());
 726   test_parent->AddChild(child_two.get());
 727   test_parent->AddChild(child_three.get());
 728   ValidateNode(test_parent.get(), 1U, 5U);
 729
 730   EXPECT_EQ(test_parent->RemoveAndReturnLastChild().release(),
 731             child_three.get());
 732   EXPECT_EQ(test_parent->count(), 2U);
 733   test_parent->RecomputeBoundsNoParents();
 734   ValidateNode(test_parent.get(), 1U, 5U);
 735
 736   EXPECT_EQ(test_parent->RemoveAndReturnLastChild().release(), child_two.get());
 737   EXPECT_EQ(test_parent->count(), 1U);
 738   test_parent->RecomputeBoundsNoParents();
 739   ValidateNode(test_parent.get(), 1U, 5U);
 740
 741   EXPECT_EQ(test_parent->RemoveAndReturnLastChild().release(), child_one.get());
 742   EXPECT_EQ(test_parent->count(), 0U);
 743 }
 744
 745 TEST_F(RTreeTest, NodeLeastOverlapIncrease) {
 746   scoped_ptr<RTree::Node> test_parent(new RTree::Node(0));
 747   // Construct 4 nodes with 1x2 retangles spaced horizontally 1 pixel apart, or:
 748   //
 749   // a b c d
 750   // a b c d
 751   //
 752   for (int i = 0; i < 4; ++i) {
 753     test_parent->AddChild(new RTree::Node(Rect(i * 2, 0, 1, 2), i + 1));
 754   }
 755
 756   ValidateNode(test_parent.get(), 1U, 5U);
 757
 758   // Test rect at (7, 0) should require minimum overlap on the part of the
 759   // fourth rectangle to add:
 760   //
 761   // a b c dT
 762   // a b c d
 763   //
 764   Rect test_rect_far(7, 0, 1, 1);
 765   std::vector<Rect> expanded_rects;
 766   BuildExpandedRects(test_parent.get(), test_rect_far, &expanded_rects);
 767   RTree::Node* result =
 768       test_parent->LeastOverlapIncrease(test_rect_far, expanded_rects);
 769   EXPECT_EQ(result->key(), 4);
 770
 771   // Test rect covering the bottom half of all children should be a 4-way tie,
 772   // so LeastOverlapIncrease should return NULL:
 773   //
 774   // a b c d
 775   // TTTTTTT
 776   //
 777   Rect test_rect_tie(0, 1, 7, 1);
 778   BuildExpandedRects(test_parent.get(), test_rect_tie, &expanded_rects);
 779   result = test_parent->LeastOverlapIncrease(test_rect_tie, expanded_rects);
 780   EXPECT_TRUE(result == NULL);
 781
 782   // Test rect completely inside c should return the third rectangle:
 783   //
 784   // a b T d
 785   // a b c d
 786   //
 787   Rect test_rect_inside(4, 0, 1, 1);
 788   BuildExpandedRects(test_parent.get(), test_rect_inside, &expanded_rects);
 789   result = test_parent->LeastOverlapIncrease(test_rect_inside, expanded_rects);
 790   EXPECT_EQ(result->key(), 3);
 791
 792   // Add a rectangle that overlaps completely with rectangle c, to test
 793   // when there is a tie between two completely contained rectangles:
 794   //
 795   // a b Ted
 796   // a b eed
 797   //
 798   test_parent->AddChild(new RTree::Node(Rect(4, 0, 2, 2), 9));
 799   BuildExpandedRects(test_parent.get(), test_rect_inside, &expanded_rects);
 800   result = test_parent->LeastOverlapIncrease(test_rect_inside, expanded_rects);
 801   EXPECT_TRUE(result == NULL);
 802 }
 803
 804 TEST_F(RTreeTest, NodeLeastAreaEnlargement) {
 805   scoped_ptr<RTree::Node> test_parent(new RTree::Node(0));
 806   // Construct 4 nodes in a cross-hairs style configuration:
 807   //
 808   //  a
 809   // b c
 810   //  d
 811   //
 812   test_parent->AddChild(new RTree::Node(Rect(1, 0, 1, 1), 1));
 813   test_parent->AddChild(new RTree::Node(Rect(0, 1, 1, 1), 2));
 814   test_parent->AddChild(new RTree::Node(Rect(2, 1, 1, 1), 3));
 815   test_parent->AddChild(new RTree::Node(Rect(1, 2, 1, 1), 4));
 816
 817   ValidateNode(test_parent.get(), 1U, 5U);
 818
 819   // Test rect at (1, 3) should require minimum area to add to Node d:
 820   //
 821   //  a
 822   // b c
 823   //  d
 824   //  T
 825   //
 826   Rect test_rect_below(1, 3, 1, 1);
 827   std::vector<Rect> expanded_rects;
 828   BuildExpandedRects(test_parent.get(), test_rect_below, &expanded_rects);
 829   RTree::Node* result =
 830       test_parent->LeastAreaEnlargement(test_rect_below, expanded_rects);
 831   EXPECT_EQ(result->key(), 4);
 832
 833   // Test rect completely inside b should require minimum area to add to Node b:
 834   //
 835   //  a
 836   // T c
 837   //  d
 838   //
 839   Rect test_rect_inside(0, 1, 1, 1);
 840   BuildExpandedRects(test_parent.get(), test_rect_inside, &expanded_rects);
 841   result = test_parent->LeastAreaEnlargement(test_rect_inside, expanded_rects);
 842   EXPECT_EQ(result->key(), 2);
 843
 844   // Add e at (0, 1) to overlap b and c, to test tie-breaking:
 845   //
 846   //  a
 847   // eee
 848   //  d
 849   //
 850   test_parent->AddChild(new RTree::Node(Rect(0, 1, 3, 1), 7));
 851
 852   ValidateNode(test_parent.get(), 1U, 5U);
 853
 854   // Test rect at (3, 1) should tie between c and e, but c has smaller area so
 855   // the algorithm should select c:
 856   //
 857   //
 858   //  a
 859   // eeeT
 860   //  d
 861   //
 862   Rect test_rect_tie_breaker(3, 1, 1, 1);
 863   BuildExpandedRects(test_parent.get(), test_rect_tie_breaker, &expanded_rects);
 864   result =
 865       test_parent->LeastAreaEnlargement(test_rect_tie_breaker, expanded_rects);
 866   EXPECT_EQ(result->key(), 3);
 867 }
 868
 869 }  // namespace gfx