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/r_tree_base.h"
   8 #include "ui/gfx/geometry/rect.h"
   9
  10 namespace gfx {
  11
  12 class RTreeTest : public ::testing::Test {
  13  protected:
  14   typedef RTree<int> RT;
  15
  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) {
  19     // If RTree is empty it should have an empty rectangle.
  20     if (!rt->root()->count()) {
  21       EXPECT_TRUE(rt->root()->rect().IsEmpty());
  22       EXPECT_EQ(0, rt->root()->Level());
  23       return;
  24     }
  25     // Root is allowed to have fewer than min_children_ but never more than
  26     // max_children_.
  27     EXPECT_LE(rt->root()->count(), rt->max_children_);
  28     // The root should never be a record node.
  29     EXPECT_GT(rt->root()->Level(), -1);
  30     // The root should never have a parent pointer.
  31     EXPECT_TRUE(rt->root()->parent() == NULL);
  32     // Bounds must be consistent on the root.
  33     CheckBoundsConsistent(rt->root());
  34     for (size_t i = 0; i < rt->root()->count(); ++i) {
  35       ValidateNode(
  36           rt->root()->child(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(const RTreeBase::NodeBase* node_base,
  43                     size_t min_children,
  44                     size_t max_children) {
  45     if (node_base->Level() >= 0) {
  46       const RTreeBase::Node* node =
  47           static_cast<const RTreeBase::Node*>(node_base);
  48       EXPECT_GE(node->count(), min_children);
  49       EXPECT_LE(node->count(), max_children);
  50       CheckBoundsConsistent(node);
  51       for (size_t i = 0; i < node->count(); ++i)
  52         ValidateNode(node->child(i), min_children, max_children);
  53     }
  54   }
  55
  56   // Check bounds are consistent with children bounds, and other checks
  57   // convenient to do while enumerating the children of node.
  58   void CheckBoundsConsistent(const RTreeBase::Node* node) {
  59     EXPECT_FALSE(node->rect().IsEmpty());
  60     Rect check_bounds;
  61     for (size_t i = 0; i < node->count(); ++i) {
  62       const RTreeBase::NodeBase* child_node = node->child(i);
  63       check_bounds.Union(child_node->rect());
  64       EXPECT_EQ(node->Level() - 1, child_node->Level());
  65       EXPECT_EQ(node, child_node->parent());
  66     }
  67     EXPECT_EQ(check_bounds, node->rect());
  68   }
  69
  70   // Adds count squares stacked around the point (0,0) with key equal to width.
  71   void AddStackedSquares(RT* rt, int count) {
  72     for (int i = 1; i <= count; ++i) {
  73       rt->Insert(Rect(0, 0, i, i), i);
  74       ValidateRTree(static_cast<RTreeBase*>(rt));
  75     }
  76   }
  77
  78   // Given an unordered list of matching keys, verifies that it contains all
  79   // values [1..length] for the length of that list.
  80   void VerifyAllKeys(const RT::Matches& keys) {
  81     for (size_t i = 1; i <= keys.size(); ++i)
  82       EXPECT_EQ(1U, keys.count(i));
  83   }
  84
  85   // Given a node and a rectangle, builds an expanded rectangle list where the
  86   // ith element of the vector is the union of the rectangle of the ith child of
  87   // the node and the argument rectangle.
  88   void BuildExpandedRects(RTreeBase::Node* node,
  89                           const Rect& rect,
  90                           std::vector<Rect>* expanded_rects) {
  91     expanded_rects->clear();
  92     expanded_rects->reserve(node->count());
  93     for (size_t i = 0; i < node->count(); ++i) {
  94       Rect expanded_rect(rect);
  95       expanded_rect.Union(node->child(i)->rect());
  96       expanded_rects->push_back(expanded_rect);
  97     }
  98   }
  99 };
 100
 101 class RTreeNodeTest : public RTreeTest {
 102  protected:
 103   typedef RTreeBase::NodeBase RTreeNodeBase;
 104   typedef RT::Record RTreeRecord;
 105   typedef RTreeBase::Node RTreeNode;
 106   typedef RTreeBase::Node::Rects RTreeRects;
 107   typedef RTreeBase::Nodes RTreeNodes;
 108
 109   // Accessors to private members of RTree::Node.
 110   const RTreeRecord* record(RTreeNode* node, size_t i) {
 111     return static_cast<const RTreeRecord*>(node->child(i));
 112   }
 113
 114   // Provides access for tests to private methods of RTree::Node.
 115   scoped_ptr<RTreeNode> NewNodeAtLevel(size_t level) {
 116     return make_scoped_ptr(new RTreeBase::Node(level));
 117   }
 118
 119   void NodeRecomputeLocalBounds(RTreeNodeBase* node) {
 120     node->RecomputeLocalBounds();
 121   }
 122
 123   bool NodeCompareVertical(RTreeNodeBase* a, RTreeNodeBase* b) {
 124     return RTreeBase::Node::CompareVertical(a, b);
 125   }
 126
 127   bool NodeCompareHorizontal(RTreeNodeBase* a, RTreeNodeBase* b) {
 128     return RTreeBase::Node::CompareHorizontal(a, b);
 129   }
 130
 131   bool NodeCompareCenterDistanceFromParent(
 132       const RTreeNodeBase* a, const RTreeNodeBase* b) {
 133     return RTreeBase::Node::CompareCenterDistanceFromParent(a, b);
 134   }
 135
 136   int NodeOverlapIncreaseToAdd(RTreeNode* node,
 137                                const Rect& rect,
 138                                const RTreeNodeBase* candidate_node,
 139                                const Rect& expanded_rect) {
 140     return node->OverlapIncreaseToAdd(rect, candidate_node, expanded_rect);
 141   }
 142
 143   void NodeBuildLowBounds(const std::vector<RTreeNodeBase*>& vertical_sort,
 144                           const std::vector<RTreeNodeBase*>& horizontal_sort,
 145                           RTreeRects* vertical_bounds,
 146                           RTreeRects* horizontal_bounds) {
 147     RTreeBase::Node::BuildLowBounds(
 148         vertical_sort, horizontal_sort, vertical_bounds, horizontal_bounds);
 149   }
 150
 151   void NodeBuildHighBounds(const std::vector<RTreeNodeBase*>& vertical_sort,
 152                            const std::vector<RTreeNodeBase*>& horizontal_sort,
 153                            RTreeRects* vertical_bounds,
 154                            RTreeRects* horizontal_bounds) {
 155     RTreeBase::Node::BuildHighBounds(
 156         vertical_sort, horizontal_sort, vertical_bounds, horizontal_bounds);
 157   }
 158
 159   int NodeSmallestMarginSum(size_t start_index,
 160                             size_t end_index,
 161                             const RTreeRects& low_bounds,
 162                             const RTreeRects& high_bounds) {
 163     return RTreeBase::Node::SmallestMarginSum(
 164         start_index, end_index, low_bounds, high_bounds);
 165   }
 166
 167   size_t NodeChooseSplitIndex(size_t min_children,
 168                               size_t max_children,
 169                               const RTreeRects& low_bounds,
 170                               const RTreeRects& high_bounds) {
 171     return RTreeBase::Node::ChooseSplitIndex(
 172         min_children, max_children, low_bounds, high_bounds);
 173   }
 174
 175   scoped_ptr<RTreeNodeBase> NodeDivideChildren(
 176       RTreeNode* node,
 177       const RTreeRects& low_bounds,
 178       const RTreeRects& high_bounds,
 179       const std::vector<RTreeNodeBase*>& sorted_children,
 180       size_t split_index) {
 181     return node->DivideChildren(
 182         low_bounds, high_bounds, sorted_children, split_index);
 183   }
 184
 185   RTreeNode* NodeLeastOverlapIncrease(RTreeNode* node,
 186                                       const Rect& node_rect,
 187                                       const RTreeRects& expanded_rects) {
 188     return node->LeastOverlapIncrease(node_rect, expanded_rects);
 189   }
 190
 191   RTreeNode* NodeLeastAreaEnlargement(RTreeNode* node,
 192                                       const Rect& node_rect,
 193                                       const RTreeRects& expanded_rects) {
 194     return node->LeastAreaEnlargement(node_rect, expanded_rects);
 195   }
 196 };
 197
 198 // RTreeNodeTest --------------------------------------------------------------
 199
 200 TEST_F(RTreeNodeTest, RemoveNodesForReinsert) {
 201   // Make a leaf node for testing removal from.
 202   scoped_ptr<RTreeNode> test_node(new RTreeNode);
 203   // Build 20 record nodes with rectangle centers going from (1,1) to (20,20)
 204   for (int i = 1; i <= 20; ++i)
 205     test_node->AddChild(scoped_ptr<RTreeNodeBase>(
 206         new RTreeRecord(Rect(i - 1, i - 1, 2, 2), i)));
 207
 208   // Quick verification of the node before removing children.
 209   ValidateNode(test_node.get(), 1U, 20U);
 210   // Use a scoped vector to delete all children that get removed from the Node.
 211   RTreeNodes removals;
 212   test_node->RemoveNodesForReinsert(1, &removals);
 213   // Should have gotten back 1 node pointer.
 214   EXPECT_EQ(1U, removals.size());
 215   // There should be 19 left in the test_node.
 216   EXPECT_EQ(19U, test_node->count());
 217   // If we fix up the bounds on the test_node, it should verify.
 218   NodeRecomputeLocalBounds(test_node.get());
 219   ValidateNode(test_node.get(), 2U, 20U);
 220   // The node we removed should be node 10, as it was exactly in the center.
 221   EXPECT_EQ(10, static_cast<RTreeRecord*>(removals[0])->key());
 222
 223   // Now remove the next 2.
 224   removals.clear();
 225   test_node->RemoveNodesForReinsert(2, &removals);
 226   EXPECT_EQ(2U, removals.size());
 227   EXPECT_EQ(17U, test_node->count());
 228   NodeRecomputeLocalBounds(test_node.get());
 229   ValidateNode(test_node.get(), 2U, 20U);
 230   // Lastly the 2 nodes we should have gotten back are keys 9 and 11, as their
 231   // centers were the closest to the center of the node bounding box.
 232   base::hash_set<intptr_t> results_hash;
 233   results_hash.insert(static_cast<RTreeRecord*>(removals[0])->key());
 234   results_hash.insert(static_cast<RTreeRecord*>(removals[1])->key());
 235   EXPECT_EQ(1U, results_hash.count(9));
 236   EXPECT_EQ(1U, results_hash.count(11));
 237 }
 238
 239 TEST_F(RTreeNodeTest, CompareVertical) {
 240   // One rect with lower y than another should always sort lower.
 241   RTreeRecord low(Rect(0, 1, 10, 10), 1);
 242   RTreeRecord middle(Rect(0, 5, 10, 10), 5);
 243   EXPECT_TRUE(NodeCompareVertical(&low, &middle));
 244   EXPECT_FALSE(NodeCompareVertical(&middle, &low));
 245
 246   // Try a non-overlapping higher-y rectangle.
 247   RTreeRecord high(Rect(-10, 20, 10, 1), 10);
 248   EXPECT_TRUE(NodeCompareVertical(&low, &high));
 249   EXPECT_FALSE(NodeCompareVertical(&high, &low));
 250
 251   // Ties are broken by lowest bottom y value.
 252   RTreeRecord shorter_tie(Rect(10, 1, 100, 2), 2);
 253   EXPECT_TRUE(NodeCompareVertical(&shorter_tie, &low));
 254   EXPECT_FALSE(NodeCompareVertical(&low, &shorter_tie));
 255 }
 256
 257 TEST_F(RTreeNodeTest, CompareHorizontal) {
 258   // One rect with lower x than another should always sort lower than higher x.
 259   RTreeRecord low(Rect(1, 0, 10, 10), 1);
 260   RTreeRecord middle(Rect(5, 0, 10, 10), 5);
 261   EXPECT_TRUE(NodeCompareHorizontal(&low, &middle));
 262   EXPECT_FALSE(NodeCompareHorizontal(&middle, &low));
 263
 264   // Try a non-overlapping higher-x rectangle.
 265   RTreeRecord high(Rect(20, -10, 1, 10), 10);
 266   EXPECT_TRUE(NodeCompareHorizontal(&low, &high));
 267   EXPECT_FALSE(NodeCompareHorizontal(&high, &low));
 268
 269   // Ties are broken by lowest bottom x value.
 270   RTreeRecord shorter_tie(Rect(1, 10, 2, 100), 2);
 271   EXPECT_TRUE(NodeCompareHorizontal(&shorter_tie, &low));
 272   EXPECT_FALSE(NodeCompareHorizontal(&low, &shorter_tie));
 273 }
 274
 275 TEST_F(RTreeNodeTest, CompareCenterDistanceFromParent) {
 276   // Create a test node we can add children to, for distance comparisons.
 277   scoped_ptr<RTreeNode> parent(new RTreeNode);
 278
 279   // Add three children, one each with centers at (0, 0), (10, 10), (-9, -9),
 280   // around which a bounding box will be centered at (0, 0)
 281   scoped_ptr<RTreeRecord> center_zero(new RTreeRecord(Rect(-1, -1, 2, 2), 1));
 282   parent->AddChild(center_zero.Pass());
 283
 284   scoped_ptr<RTreeRecord> center_positive(new RTreeRecord(Rect(9, 9, 2, 2), 2));
 285   parent->AddChild(center_positive.Pass());
 286
 287   scoped_ptr<RTreeRecord> center_negative(
 288       new RTreeRecord(Rect(-10, -10, 2, 2), 3));
 289   parent->AddChild(center_negative.Pass());
 290
 291   ValidateNode(parent.get(), 1U, 5U);
 292   EXPECT_EQ(Rect(-10, -10, 21, 21), parent->rect());
 293
 294   EXPECT_TRUE(
 295       NodeCompareCenterDistanceFromParent(parent->child(0), parent->child(1)));
 296   EXPECT_FALSE(
 297       NodeCompareCenterDistanceFromParent(parent->child(1), parent->child(0)));
 298   EXPECT_TRUE(
 299       NodeCompareCenterDistanceFromParent(parent->child(0), parent->child(2)));
 300   EXPECT_FALSE(
 301       NodeCompareCenterDistanceFromParent(parent->child(2), parent->child(0)));
 302   EXPECT_TRUE(
 303       NodeCompareCenterDistanceFromParent(parent->child(2), parent->child(1)));
 304   EXPECT_FALSE(
 305       NodeCompareCenterDistanceFromParent(parent->child(1), parent->child(2)));
 306 }
 307
 308 TEST_F(RTreeNodeTest, OverlapIncreaseToAdd) {
 309   // Create a test node with three children, for overlap comparisons.
 310   scoped_ptr<RTreeNode> parent(new RTreeNode);
 311
 312   // Add three children, each 4 wide and tall, at (0, 0), (3, 3), (6, 6) with
 313   // overlapping corners.
 314   Rect top(0, 0, 4, 4);
 315   parent->AddChild(scoped_ptr<RTreeNodeBase>(new RTreeRecord(top, 1)));
 316   Rect middle(3, 3, 4, 4);
 317   parent->AddChild(scoped_ptr<RTreeNodeBase>(new RTreeRecord(middle, 2)));
 318   Rect bottom(6, 6, 4, 4);
 319   parent->AddChild(scoped_ptr<RTreeNodeBase>(new RTreeRecord(bottom, 3)));
 320   ValidateNode(parent.get(), 1U, 5U);
 321
 322   // Test a rect in corner.
 323   Rect corner(0, 0, 1, 1);
 324   Rect expanded = top;
 325   expanded.Union(corner);
 326   // It should not add any overlap to add this to the first child at (0, 0).
 327   EXPECT_EQ(0, NodeOverlapIncreaseToAdd(
 328       parent.get(), corner, parent->child(0), expanded));
 329
 330   expanded = middle;
 331   expanded.Union(corner);
 332   // Overlap for middle rectangle should increase from 2 pixels at (3, 3) and
 333   // (6, 6) to 17 pixels, as it will now cover 4x4 rectangle top,
 334   // so a change of +15.
 335   EXPECT_EQ(15, NodeOverlapIncreaseToAdd(
 336       parent.get(), corner, parent->child(1), expanded));
 337
 338   expanded = bottom;
 339   expanded.Union(corner);
 340   // Overlap for bottom rectangle should increase from 1 pixel at (6, 6) to
 341   // 32 pixels, as it will now cover both 4x4 rectangles top and middle,
 342   // so a change of 31.
 343   EXPECT_EQ(31, NodeOverlapIncreaseToAdd(
 344       parent.get(), corner, parent->child(2), expanded));
 345
 346   // Test a rect that doesn't overlap with anything, in the far right corner.
 347   Rect far_corner(9, 0, 1, 1);
 348   expanded = top;
 349   expanded.Union(far_corner);
 350   // Overlap of top should go from 1 to 4, as it will now cover the entire first
 351   // row of pixels in middle.
 352   EXPECT_EQ(3, NodeOverlapIncreaseToAdd(
 353       parent.get(), far_corner, parent->child(0), expanded));
 354
 355   expanded = middle;
 356   expanded.Union(far_corner);
 357   // Overlap of middle should go from 2 to 8, as it will cover the rightmost 4
 358   // pixels of top and the top 4 pixels of bottom as it expands.
 359   EXPECT_EQ(6, NodeOverlapIncreaseToAdd(
 360       parent.get(), far_corner, parent->child(1), expanded));
 361
 362   expanded = bottom;
 363   expanded.Union(far_corner);
 364   // Overlap of bottom should go from 1 to 4, as it will now cover the rightmost
 365   // 4 pixels of middle.
 366   EXPECT_EQ(3, NodeOverlapIncreaseToAdd(
 367       parent.get(), far_corner, parent->child(2), expanded));
 368 }
 369
 370 TEST_F(RTreeNodeTest, BuildLowBounds) {
 371   RTreeNodes records;
 372   records.reserve(10);
 373   for (int i = 1; i <= 10; ++i)
 374     records.push_back(new RTreeRecord(Rect(0, 0, i, i), i));
 375
 376   RTreeRects vertical_bounds;
 377   RTreeRects horizontal_bounds;
 378   NodeBuildLowBounds(
 379       records.get(), records.get(), &vertical_bounds, &horizontal_bounds);
 380   for (int i = 0; i < 10; ++i) {
 381     EXPECT_EQ(records[i]->rect(), vertical_bounds[i]);
 382     EXPECT_EQ(records[i]->rect(), horizontal_bounds[i]);
 383   }
 384 }
 385
 386 TEST_F(RTreeNodeTest, BuildHighBounds) {
 387   RTreeNodes records;
 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);
 396   for (int i = 0; i < 25; ++i) {
 397     EXPECT_EQ(records[i]->rect(), vertical_bounds[i]);
 398     EXPECT_EQ(records[i]->rect(), horizontal_bounds[i]);
 399   }
 400 }
 401
 402 TEST_F(RTreeNodeTest, ChooseSplitAxisAndIndexVertical) {
 403   RTreeRects low_vertical_bounds;
 404   RTreeRects high_vertical_bounds;
 405   RTreeRects low_horizontal_bounds;
 406   RTreeRects high_horizontal_bounds;
 407   // In this test scenario we describe a mirrored, stacked configuration of
 408   // horizontal, 1 pixel high rectangles labeled a-f like this:
 409   //
 410   // shape: | v sort: | h sort: |
 411   // -------+---------+---------+
 412   // aaaaa  |    0    |    0    |
 413   //  bbb   |    1    |    2    |
 414   //   c    |    2    |    4    |
 415   //   d    |    3    |    5    |
 416   //  eee   |    4    |    3    |
 417   // fffff  |    5    |    1    |
 418   //
 419   // These are already sorted vertically from top to bottom. Bounding rectangles
 420   // of these vertically sorted will be 5 wide, i tall bounding boxes.
 421   for (int i = 0; i < 6; ++i) {
 422     low_vertical_bounds.push_back(Rect(0, 0, 5, i + 1));
 423     high_vertical_bounds.push_back(Rect(0, i, 5, 6 - i));
 424   }
 425
 426   // Low bounds of horizontal sort start with bounds of box a and then jump to
 427   // cover everything, as box f is second in horizontal sort.
 428   low_horizontal_bounds.push_back(Rect(0, 0, 5, 1));
 429   for (int i = 0; i < 5; ++i)
 430     low_horizontal_bounds.push_back(Rect(0, 0, 5, 6));
 431
 432   // High horizontal bounds are hand-calculated.
 433   high_horizontal_bounds.push_back(Rect(0, 0, 5, 6));
 434   high_horizontal_bounds.push_back(Rect(0, 1, 5, 5));
 435   high_horizontal_bounds.push_back(Rect(1, 1, 3, 4));
 436   high_horizontal_bounds.push_back(Rect(1, 2, 3, 3));
 437   high_horizontal_bounds.push_back(Rect(2, 2, 1, 2));
 438   high_horizontal_bounds.push_back(Rect(2, 3, 1, 1));
 439
 440   int smallest_vertical_margin =
 441       NodeSmallestMarginSum(2, 3, low_vertical_bounds, high_vertical_bounds);
 442   int smallest_horizontal_margin = NodeSmallestMarginSum(
 443       2, 3, low_horizontal_bounds, high_horizontal_bounds);
 444   EXPECT_LT(smallest_vertical_margin, smallest_horizontal_margin);
 445
 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:
 458   //
 459   //         +--------+
 460   //         | a    f |
 461   //         | ab  ef |
 462   // sort:   | abcdef |
 463   //         | ab  ef |
 464   //         | a    f |
 465   //         |--------+
 466   // v sort: | 024531 |
 467   // h sort: | 012345 |
 468   //         +--------+
 469   //
 470   // Low bounds of vertical sort start with bounds of box a and then jump to
 471   // cover everything, as box f is second in vertical sort.
 472   low_vertical_bounds.push_back(Rect(0, 0, 1, 5));
 473   for (int i = 0; i < 5; ++i)
 474     low_vertical_bounds.push_back(Rect(0, 0, 6, 5));
 475
 476   // High vertical bounds are hand-calculated.
 477   high_vertical_bounds.push_back(Rect(0, 0, 6, 5));
 478   high_vertical_bounds.push_back(Rect(1, 0, 5, 5));
 479   high_vertical_bounds.push_back(Rect(1, 1, 4, 3));
 480   high_vertical_bounds.push_back(Rect(2, 1, 3, 3));
 481   high_vertical_bounds.push_back(Rect(2, 2, 2, 1));
 482   high_vertical_bounds.push_back(Rect(3, 2, 1, 1));
 483
 484   // These are already sorted horizontally from left to right. Bounding
 485   // rectangles of these horizontally sorted will be i wide, 5 tall bounding
 486   // boxes.
 487   for (int i = 0; i < 6; ++i) {
 488     low_horizontal_bounds.push_back(Rect(0, 0, i + 1, 5));
 489     high_horizontal_bounds.push_back(Rect(i, 0, 6 - i, 5));
 490   }
 491
 492   int smallest_vertical_margin =
 493       NodeSmallestMarginSum(2, 3, low_vertical_bounds, high_vertical_bounds);
 494   int smallest_horizontal_margin = NodeSmallestMarginSum(
 495       2, 3, low_horizontal_bounds, high_horizontal_bounds);
 496
 497   EXPECT_GT(smallest_vertical_margin, smallest_horizontal_margin);
 498
 499   EXPECT_EQ(3U,
 500             NodeChooseSplitIndex(
 501                 2, 5, low_horizontal_bounds, high_horizontal_bounds));
 502 }
 503
 504 TEST_F(RTreeNodeTest, DivideChildren) {
 505   // Create a test node to split.
 506   scoped_ptr<RTreeNode> test_node(new RTreeNode);
 507   std::vector<RTreeNodeBase*> sorted_children;
 508   RTreeRects low_bounds;
 509   RTreeRects high_bounds;
 510   // Insert 10 record nodes, also inserting them into our children array.
 511   for (int i = 1; i <= 10; ++i) {
 512     scoped_ptr<RTreeRecord> record(new RTreeRecord(Rect(0, 0, i, i), i));
 513     sorted_children.push_back(record.get());
 514     test_node->AddChild(record.Pass());
 515     low_bounds.push_back(Rect(0, 0, i, i));
 516     high_bounds.push_back(Rect(0, 0, 10, 10));
 517   }
 518   // Split the children in half.
 519   scoped_ptr<RTreeNodeBase> split_node_base(NodeDivideChildren(
 520       test_node.get(), low_bounds, high_bounds, sorted_children, 5));
 521   RTreeNode* split_node = static_cast<RTreeNode*>(split_node_base.get());
 522   // Both nodes should be valid.
 523   ValidateNode(test_node.get(), 1U, 10U);
 524   ValidateNode(split_node, 1U, 10U);
 525   // Both nodes should have five children.
 526   EXPECT_EQ(5U, test_node->count());
 527   EXPECT_EQ(5U, split_node->count());
 528   // Test node should have children 1-5, split node should have children 6-10.
 529   for (int i = 0; i < 5; ++i) {
 530     EXPECT_EQ(i + 1, record(test_node.get(), i)->key());
 531     EXPECT_EQ(i + 6, record(split_node, i)->key());
 532   }
 533 }
 534
 535 TEST_F(RTreeNodeTest, RemoveChildNoOrphans) {
 536   scoped_ptr<RTreeNode> test_parent(new RTreeNode);
 537   test_parent->AddChild(
 538       scoped_ptr<RTreeNodeBase>(new RTreeRecord(Rect(0, 0, 1, 1), 1)));
 539   test_parent->AddChild(
 540       scoped_ptr<RTreeNodeBase>(new RTreeRecord(Rect(0, 0, 2, 2), 2)));
 541   test_parent->AddChild(
 542     scoped_ptr<RTreeNodeBase>(new RTreeRecord(Rect(0, 0, 3, 3), 3)));
 543   ValidateNode(test_parent.get(), 1U, 5U);
 544
 545   RTreeNodes orphans;
 546
 547   // Remove the middle node.
 548   scoped_ptr<RTreeNodeBase> middle_child(
 549       test_parent->RemoveChild(test_parent->child(1), &orphans));
 550   EXPECT_EQ(0U, orphans.size());
 551   EXPECT_EQ(2U, test_parent->count());
 552   NodeRecomputeLocalBounds(test_parent.get());
 553   ValidateNode(test_parent.get(), 1U, 5U);
 554
 555   // Remove the end node.
 556   scoped_ptr<RTreeNodeBase> end_child(
 557       test_parent->RemoveChild(test_parent->child(1), &orphans));
 558   EXPECT_EQ(0U, orphans.size());
 559   EXPECT_EQ(1U, test_parent->count());
 560   NodeRecomputeLocalBounds(test_parent.get());
 561   ValidateNode(test_parent.get(), 1U, 5U);
 562
 563   // Remove the first node.
 564   scoped_ptr<RTreeNodeBase> first_child(
 565       test_parent->RemoveChild(test_parent->child(0), &orphans));
 566   EXPECT_EQ(0U, orphans.size());
 567   EXPECT_EQ(0U, test_parent->count());
 568 }
 569
 570 TEST_F(RTreeNodeTest, RemoveChildOrphans) {
 571   // Build binary tree of Nodes of height 4, keeping weak pointers to the
 572   // Levels 0 and 1 Nodes and the Records so we can test removal of them below.
 573   std::vector<RTreeNode*> level_1_children;
 574   std::vector<RTreeNode*> level_0_children;
 575   std::vector<RTreeRecord*> records;
 576   int id = 1;
 577   scoped_ptr<RTreeNode> root(NewNodeAtLevel(2));
 578   for (int i = 0; i < 2; ++i) {
 579     scoped_ptr<RTreeNode> level_1_child(NewNodeAtLevel(1));
 580     for (int j = 0; j < 2; ++j) {
 581       scoped_ptr<RTreeNode> level_0_child(new RTreeNode);
 582       for (int k = 0; k < 2; ++k) {
 583         scoped_ptr<RTreeRecord> record(
 584             new RTreeRecord(Rect(0, 0, id, id), id));
 585         ++id;
 586         records.push_back(record.get());
 587         level_0_child->AddChild(record.Pass());
 588       }
 589       level_0_children.push_back(level_0_child.get());
 590       level_1_child->AddChild(level_0_child.Pass());
 591     }
 592     level_1_children.push_back(level_1_child.get());
 593     root->AddChild(level_1_child.Pass());
 594   }
 595
 596   // This should now be a valid tree structure.
 597   ValidateNode(root.get(), 2U, 2U);
 598   EXPECT_EQ(2U, level_1_children.size());
 599   EXPECT_EQ(4U, level_0_children.size());
 600   EXPECT_EQ(8U, records.size());
 601
 602   // Now remove all of the level 0 nodes so we get the record nodes as orphans.
 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());
 617 }
 618
 619 TEST_F(RTreeNodeTest, RemoveAndReturnLastChild) {
 620   scoped_ptr<RTreeNode> test_parent(new RTreeNode);
 621   test_parent->AddChild(
 622       scoped_ptr<RTreeNodeBase>(new RTreeRecord(Rect(0, 0, 1, 1), 1)));
 623   test_parent->AddChild(
 624       scoped_ptr<RTreeNodeBase>(new RTreeRecord(Rect(0, 0, 2, 2), 2)));
 625   test_parent->AddChild(
 626       scoped_ptr<RTreeNodeBase>(new RTreeRecord(Rect(0, 0, 3, 3), 3)));
 627   ValidateNode(test_parent.get(), 1U, 5U);
 628
 629   RTreeNodeBase* child = test_parent->child(2);
 630   scoped_ptr<RTreeNodeBase> last_child(test_parent->RemoveAndReturnLastChild());
 631   EXPECT_EQ(child, last_child.get());
 632   EXPECT_EQ(2U, test_parent->count());
 633   NodeRecomputeLocalBounds(test_parent.get());
 634   ValidateNode(test_parent.get(), 1U, 5U);
 635
 636   child = test_parent->child(1);
 637   scoped_ptr<RTreeNodeBase> middle_child(
 638       test_parent->RemoveAndReturnLastChild());
 639   EXPECT_EQ(child, middle_child.get());
 640   EXPECT_EQ(1U, test_parent->count());
 641   NodeRecomputeLocalBounds(test_parent.get());
 642   ValidateNode(test_parent.get(), 1U, 5U);
 643
 644   child = test_parent->child(0);
 645   scoped_ptr<RTreeNodeBase> first_child(
 646       test_parent->RemoveAndReturnLastChild());
 647   EXPECT_EQ(child, first_child.get());
 648   EXPECT_EQ(0U, test_parent->count());
 649 }
 650
 651 TEST_F(RTreeNodeTest, LeastOverlapIncrease) {
 652   scoped_ptr<RTreeNode> test_parent(NewNodeAtLevel(1));
 653   // Construct 4 nodes with 1x2 rects spaced horizontally 1 pixel apart, or:
 654   //
 655   // a b c d
 656   // a b c d
 657   //
 658   for (int i = 0; i < 4; ++i) {
 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.Pass());
 663     test_parent->AddChild(node.Pass());
 664   }
 665
 666   ValidateNode(test_parent.get(), 1U, 5U);
 667
 668   // Test rect at (7, 0) should require minimum overlap on the part of the
 669   // fourth rectangle to add:
 670   //
 671   // a b c dT
 672   // a b c d
 673   //
 674   Rect test_rect_far(7, 0, 1, 1);
 675   RTreeRects expanded_rects;
 676   BuildExpandedRects(test_parent.get(), test_rect_far, &expanded_rects);
 677   RTreeNode* result = NodeLeastOverlapIncrease(
 678       test_parent.get(), test_rect_far, expanded_rects);
 679   EXPECT_EQ(4, record(result, 0)->key());
 680
 681   // Test rect covering the bottom half of all children should be a 4-way tie,
 682   // so LeastOverlapIncrease should return NULL:
 683   //
 684   // a b c d
 685   // TTTTTTT
 686   //
 687   Rect test_rect_tie(0, 1, 7, 1);
 688   BuildExpandedRects(test_parent.get(), test_rect_tie, &expanded_rects);
 689   result = NodeLeastOverlapIncrease(
 690       test_parent.get(), test_rect_tie, expanded_rects);
 691   EXPECT_TRUE(result == NULL);
 692
 693   // Test rect completely inside c should return the third rectangle:
 694   //
 695   // a b T d
 696   // a b c d
 697   //
 698   Rect test_rect_inside(4, 0, 1, 1);
 699   BuildExpandedRects(test_parent.get(), test_rect_inside, &expanded_rects);
 700   result = NodeLeastOverlapIncrease(
 701       test_parent.get(), test_rect_inside, expanded_rects);
 702   EXPECT_EQ(3, record(result, 0)->key());
 703
 704   // Add a rectangle that overlaps completely with rectangle c, to test
 705   // when there is a tie between two completely contained rectangles:
 706   //
 707   // a b Ted
 708   // a b eed
 709   //
 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.Pass());
 714   BuildExpandedRects(test_parent.get(), test_rect_inside, &expanded_rects);
 715   result = NodeLeastOverlapIncrease(
 716       test_parent.get(), test_rect_inside, expanded_rects);
 717   EXPECT_TRUE(result == NULL);
 718 }
 719
 720 TEST_F(RTreeNodeTest, LeastAreaEnlargement) {
 721   scoped_ptr<RTreeNode> test_parent(NewNodeAtLevel(1));
 722   // Construct 4 nodes in a cross-hairs style configuration:
 723   //
 724   //  a
 725   // b c
 726   //  d
 727   //
 728   scoped_ptr<RTreeNode> node(new RTreeNode);
 729   node->AddChild(
 730       scoped_ptr<RTreeNodeBase>(new RTreeRecord(Rect(1, 0, 1, 1), 1)));
 731   test_parent->AddChild(node.Pass());
 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.Pass());
 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.Pass());
 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.Pass());
 744
 745   ValidateNode(test_parent.get(), 1U, 5U);
 746
 747   // Test rect at (1, 3) should require minimum area to add to Node d:
 748   //
 749   //  a
 750   // b c
 751   //  d
 752   //  T
 753   //
 754   Rect test_rect_below(1, 3, 1, 1);
 755   RTreeRects expanded_rects;
 756   BuildExpandedRects(test_parent.get(), test_rect_below, &expanded_rects);
 757   RTreeNode* result = NodeLeastAreaEnlargement(
 758       test_parent.get(), test_rect_below, expanded_rects);
 759   EXPECT_EQ(4, record(result, 0)->key());
 760
 761   // Test rect completely inside b should require minimum area to add to Node b:
 762   //
 763   //  a
 764   // T c
 765   //  d
 766   //
 767   Rect test_rect_inside(0, 1, 1, 1);
 768   BuildExpandedRects(test_parent.get(), test_rect_inside, &expanded_rects);
 769   result = NodeLeastAreaEnlargement(
 770       test_parent.get(), test_rect_inside, expanded_rects);
 771   EXPECT_EQ(2, record(result, 0)->key());
 772
 773   // Add e at (0, 1) to overlap b and c, to test tie-breaking:
 774   //
 775   //  a
 776   // eee
 777   //  d
 778   //
 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.Pass());
 783
 784   ValidateNode(test_parent.get(), 1U, 5U);
 785
 786   // Test rect at (3, 1) should tie between c and e, but c has smaller area so
 787   // the algorithm should select c:
 788   //
 789   //
 790   //  a
 791   // eeeT
 792   //  d
 793   //
 794   Rect test_rect_tie_breaker(3, 1, 1, 1);
 795   BuildExpandedRects(test_parent.get(), test_rect_tie_breaker, &expanded_rects);
 796   result = NodeLeastAreaEnlargement(
 797       test_parent.get(), test_rect_tie_breaker, expanded_rects);
 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);
1012 }
1013
1014 TEST_F(RTreeTest, InsertReplacementMaintainsTree) {
1015   RT rt(2, 5);
1016   AddStackedSquares(&rt, 100);
1017   ValidateRTree(&rt);
1018
1019   for (int i = 1; i <= 100; ++i) {
1020     rt.Insert(Rect(0, 0, 0, 0), i);
1021     ValidateRTree(&rt);
1022   }
1023 }
1024
1025 }  // namespace gfx