Adds an RTree data structure to gfx/geometry

ui/gfx/geometry/r_tree_unittest.cc

+// Copyright (c) 2014 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include <set>
+
+#include "testing/gtest/include/gtest/gtest.h"
+#include "ui/gfx/geometry/r_tree.h"
+#include "ui/gfx/geometry/rect.h"
+
+namespace gfx {
+
+class RTreeTest : public ::testing::Test {
+ protected:
+  // Given a pointer to an RTree, traverse it and verify its internal structure
+  // is consistent with the RTree semantics.
+  void ValidateRTree(RTree* rt) {
+    // If RTree is empty it should have an empty rectangle.
+    if (!rt->root_->count()) {
+      EXPECT_TRUE(rt->root_->rect().IsEmpty());
+      EXPECT_EQ(rt->root_->level(), 0);
+      return;
+    }
+    // Root is allowed to have fewer than min_children_ but never more than
+    // max_children_.
+    EXPECT_LE(rt->root_->count(), rt->max_children_);
+    // The root should never be a record node.
+    EXPECT_GT(rt->root_->level(), -1);
+    EXPECT_FALSE(rt->root_->key());
+    // The root should never have a parent pointer.
+    EXPECT_FALSE(rt->root_->parent());
+    // Bounds must be consistent on the root.
+    CheckBoundsConsistent(rt->root_.get());
+    // We traverse root's children ourselves, so we can avoid asserts about
+    // root's potential inconsistencies.
+    for (size_t i = 0; i < rt->root_->children_.size(); ++i) {
+      ValidateNode(
+          rt->root_->children_[i], rt->min_children_, rt->max_children_);
+    }
+  }
+
+  // Recursive descent method used by ValidateRTree to check each node within
+  // the RTree for consistency with RTree semantics.
+  void ValidateNode(RTree::Node* node,
+                    size_t min_children,
+                    size_t max_children) {
+    // Record nodes have different requirements, handle up front.
+    if (node->level() == -1) {
+      // Record nodes may have no children.
+      EXPECT_EQ(node->count(), 0U);
+      // They must have an associated non-NULL key.
+      EXPECT_TRUE(node->key());
+      // They must always have a parent.
+      EXPECT_TRUE(node->parent());
+      return;
+    }
+    // Non-record node, normal expectations apply.
+    EXPECT_GE(node->count(), min_children);
+    EXPECT_LE(node->count(), max_children);
+    EXPECT_TRUE(node->key() == NULL);
+    CheckBoundsConsistent(node);
+    for (size_t i = 0; i < node->children_.size(); ++i) {
+      ValidateNode(node->children_[i], min_children, max_children);
+    }
+  }
+
+  // Check bounds are consistent with children bounds, and other checks
+  // convenient to do while enumerating the children of node.
+  void CheckBoundsConsistent(RTree::Node* node) {
+    EXPECT_FALSE(node->rect_.IsEmpty());
+    Rect check_bounds(0, 0, 0, 0);
+    for (size_t i = 0; i < node->children_.size(); ++i) {
+      RTree::Node* child_node = node->children_[i];
+      check_bounds.Union(child_node->rect());
+      EXPECT_EQ(node->level() - 1, child_node->level());
+      EXPECT_EQ(node, child_node->parent());
+    }
+    EXPECT_EQ(node->rect_, check_bounds);
+  }
+
+  // Adds count squares stacked around the point (0,0) with key equal to width.
+  void AddStackedSquares(RTree* rt, int count) {
+    for (int i = 1; i <= count; ++i) {
+      rt->Insert(Rect(0, 0, i, i), reinterpret_cast<const void*>(i));
+      ValidateRTree(rt);
+    }
+  }
+
+  // Given an unordered list of matching keys, verify that it contains all
+  // values [1..length] for the length of that list.
+  void VerifyAllKeys(const std::set<const void*>& keys) {
+    // Verify that the keys are in values [1,count].
+    for (size_t i = 1; i <= keys.size(); ++i) {
+      EXPECT_TRUE(keys.count(reinterpret_cast<const void*>(i)) == 1U);
+    }
+  }
+};
+
+// An empty RTree should never return Query results, and RTrees should be empty
+// upon construction.
+TEST_F(RTreeTest, QueryEmptyTree) {
+  RTree rt(2, 10);
+  ValidateRTree(&rt);
+  std::set<const void*> results;
+  Rect test_rect(25, 25);
+  rt.Query(test_rect, &results);
+  EXPECT_EQ(results.size(), 0U);
+  ValidateRTree(&rt);
+}
+
+// Clear should empty the tree, meaning that all queries should not return
+// results after.
+TEST_F(RTreeTest, ClearEmptiesTreeOfSingleNode) {
+  RTree rt(2, 5);
+  rt.Insert(Rect(0, 0, 100, 100), reinterpret_cast<const void*>(1));
+  rt.Clear();
+  std::set<const void*> results;
+  Rect test_rect(1, 1);
+  rt.Query(test_rect, &results);
+  EXPECT_EQ(results.size(), 0U);
+  ValidateRTree(&rt);
+}
+
+// Even with a complex internal structure, clear should empty the tree, meaning
+// that all queries should not return results after.
+TEST_F(RTreeTest, ClearEmptiesTreeOfManyNodes) {
+  RTree rt(2, 5);
+  AddStackedSquares(&rt, 100);
+  rt.Clear();
+  std::set<const void*> results;
+  Rect test_rect(1, 1);
+  rt.Query(test_rect, &results);
+  EXPECT_EQ(results.size(), 0U);
+  ValidateRTree(&rt);
+}
+
+// Duplicate inserts should overwrite previous inserts.
+TEST_F(RTreeTest, DuplicateInsertsOverwrite) {
+  RTree rt(2, 5);
+  // Add 100 stacked squares, but always with duplicate key of 1.
+  for (int i = 1; i <= 100; ++i) {
+    rt.Insert(Rect(0, 0, i, i), reinterpret_cast<const void*>(1));
+    ValidateRTree(&rt);
+  }
+  std::set<const void*> results;
+  Rect test_rect(1, 1);
+  rt.Query(test_rect, &results);
+  EXPECT_EQ(results.size(), 1U);
+  EXPECT_TRUE(*results.begin() == reinterpret_cast<const void*>(1));
+}
+
+// Call Remove() once on something that's been inserted repeatedly.
+TEST_F(RTreeTest, DuplicateInsertRemove) {
+  RTree rt(3, 9);
+  AddStackedSquares(&rt, 25);
+  for (int i = 1; i <= 100; ++i) {
+    rt.Insert(Rect(0, 0, i, i), reinterpret_cast<const void*>(26));
+    ValidateRTree(&rt);
+  }
+  rt.Remove(reinterpret_cast<const void*>(26));
+  std::set<const void*> results;
+  Rect test_rect(1, 1);
+  rt.Query(test_rect, &results);
+  EXPECT_EQ(results.size(), 25U);
+  VerifyAllKeys(results);
+}
+
+// Call Remove() repeatedly on something that's been inserted once.
+TEST_F(RTreeTest, InsertDuplicateRemove) {
+  RTree rt(7, 15);
+  AddStackedSquares(&rt, 101);
+  for (int i = 0; i < 100; ++i) {
+    rt.Remove(reinterpret_cast<const void*>(101));
+    ValidateRTree(&rt);
+  }
+  std::set<const void*> results;
+  Rect test_rect(1, 1);
+  rt.Query(test_rect, &results);
+  EXPECT_EQ(results.size(), 100U);
+  VerifyAllKeys(results);
+}
+
+// Stacked rects should meet all matching queries regardless of nesting.
+TEST_F(RTreeTest, QueryStackedSquaresNestedHit) {
+  RTree rt(2, 5);
+  AddStackedSquares(&rt, 100);
+  std::set<const void*> results;
+  Rect test_rect(1, 1);
+  rt.Query(test_rect, &results);
+  EXPECT_EQ(results.size(), 100U);
+  VerifyAllKeys(results);
+}
+
+// Stacked rects should meet all matching queries when contained completely by
+// the query rectangle.
+TEST_F(RTreeTest, QueryStackedSquaresContainedHit) {
+  RTree rt(2, 10);
+  AddStackedSquares(&rt, 100);
+  std::set<const void*> results;
+  Rect test_rect(0, 0, 100, 100);
+  rt.Query(test_rect, &results);
+  EXPECT_EQ(results.size(), 100U);
+  VerifyAllKeys(results);
+}
+
+// Stacked rects should miss a missing query when the query has no intersection
+// with the rects.
+TEST_F(RTreeTest, QueryStackedSquaresCompleteMiss) {
+  RTree rt(2, 7);
+  AddStackedSquares(&rt, 100);
+  std::set<const void*> results;
+  Rect test_rect(150, 150, 100, 100);
+  rt.Query(test_rect, &results);
+  EXPECT_EQ(results.size(), 0U);
+}
+
+// Removing half the nodes after insertion should still result in a valid tree.
+TEST_F(RTreeTest, RemoveHalfStackedRects) {
+  RTree rt(2, 11);
+  AddStackedSquares(&rt, 200);
+  for (int i = 101; i <= 200; ++i) {
+    rt.Remove(reinterpret_cast<const void*>(i));
+    ValidateRTree(&rt);
+  }
+  std::set<const void*> results;
+  Rect test_rect(1, 1);
+  rt.Query(test_rect, &results);
+  EXPECT_EQ(results.size(), 100U);
+  VerifyAllKeys(results);
+  // Add the nodes back in.
+  for (int i = 101; i <= 200; ++i) {
+    rt.Insert(Rect(0, 0, i, i), reinterpret_cast<const void*>(i));
+    ValidateRTree(&rt);
+  }
+  results.clear();
+  rt.Query(test_rect, &results);
+  EXPECT_EQ(results.size(), 200U);
+  VerifyAllKeys(results);
+}
+
+TEST_F(RTreeTest, InsertNegativeCoordsRect) {
+  RTree rt(5, 11);
+  for (int i = 1; i <= 100; ++i) {
+    rt.Insert(Rect(-i, -i, i, i), reinterpret_cast<const void*>((i * 2) - 1));
+    ValidateRTree(&rt);
+    rt.Insert(Rect(0, 0, i, i), reinterpret_cast<const void*>(i * 2));
+    ValidateRTree(&rt);
+  }
+  std::set<const void*> results;
+  Rect test_rect(-1, -1, 2, 2);
+  rt.Query(test_rect, &results);
+  EXPECT_EQ(results.size(), 200U);
+  VerifyAllKeys(results);
+}
+
+TEST_F(RTreeTest, RemoveNegativeCoordsRect) {
+  RTree rt(7, 21);
+  // Add 100 positive stacked squares.
+  AddStackedSquares(&rt, 100);
+  // Now add 100 negative stacked squares.
+  for (int i = 101; i <= 200; ++i) {
+    rt.Insert(Rect(100 - i, 100 - i, i - 100, i - 100),
+              reinterpret_cast<const void*>(301 - i));
+    ValidateRTree(&rt);
+  }
+  // Now remove half of the negative squares.
+  for (int i = 101; i <= 150; ++i) {
+    rt.Remove(reinterpret_cast<const void*>(301 - i));
+    ValidateRTree(&rt);
+  }
+  // Queries should return 100 positive and 50 negative stacked squares.
+  std::set<const void*> results;
+  Rect test_rect(-1, -1, 2, 2);
+  rt.Query(test_rect, &results);
+  EXPECT_EQ(results.size(), 150U);
+  VerifyAllKeys(results);
+}
+
+TEST_F(RTreeTest, InsertEmptyRectReplacementRemovesKey) {
+  RTree rt(10, 31);
+  AddStackedSquares(&rt, 50);
+  ValidateRTree(&rt);
+
+  // Replace last square with empty rect.
+  rt.Insert(Rect(0, 0, 0, 0), reinterpret_cast<const void*>(50));
+  ValidateRTree(&rt);
+
+  // Now query large area to get all rects in tree.
+  std::set<const void*> results;
+  Rect test_rect(0, 0, 100, 100);
+  rt.Query(test_rect, &results);
+
+  // Should only be 49 rects in tree.
+  EXPECT_EQ(results.size(), 49U);
+  VerifyAllKeys(results);
+}
+
+TEST_F(RTreeTest, NodeRemoveNodesForReinsert) {
+  // Make a leaf node for testing removal from.
+  scoped_ptr<RTree::Node> test_node(new RTree::Node(0));
+  // Build 20 record nodes with rectangle centers going from (1,1) to (20,20)
+  for (int i = 1; i <= 20; ++i) {
+    test_node->AddChild(new RTree::Node(Rect(i - 1, i - 1, 2, 2),
+                                        reinterpret_cast<const void*>(i)));
+  }
+  // Quick verification of the node before removing children.
+  ValidateNode(test_node.get(), 1U, 20U);
+  // Use a scoped vector to delete all children that get removed from the Node.
+  ScopedVector<RTree::Node> removals;
+  test_node->RemoveNodesForReinsert(1, &removals.get());
+  // Should have gotten back 1 node pointers.
+  EXPECT_EQ(removals.size(), 1U);
+  // There should be 19 left in the test_node.
+  EXPECT_EQ(test_node->count(), 19U);
+  // If we fix up the bounds on the test_node, it should verify.
+  test_node->RecomputeBoundsNoParents();
+  ValidateNode(test_node.get(), 2U, 20U);
+  // The node we removed should be node 10, as it was exactly in the center.
+  EXPECT_TRUE(removals[0]->key() == reinterpret_cast<const void*>(10));
+
+  // Now remove the next 2.
+  removals.clear();
+  test_node->RemoveNodesForReinsert(2, &removals.get());
+  EXPECT_EQ(removals.size(), 2U);
+  EXPECT_EQ(test_node->count(), 17U);
+  test_node->RecomputeBoundsNoParents();
+  ValidateNode(test_node.get(), 2U, 20U);
+  // Lastly the 2 nodes we should have gotten back are keys 9 and 11, as their
+  // centers were the closest to the center of the node bounding box.
+  EXPECT_TRUE(removals[0]->key() == reinterpret_cast<const void*>(9) ||
+              removals[0]->key() == reinterpret_cast<const void*>(11));
+  EXPECT_TRUE(removals[1]->key() == reinterpret_cast<const void*>(9) ||
+              removals[1]->key() == reinterpret_cast<const void*>(11));
+  EXPECT_TRUE(removals[0]->key() != removals[1]->key());
+}
+
+TEST_F(RTreeTest, NodeCompareVertical) {
+  // One rect with lower y than another should always sort lower than higher y.
+  RTree::Node low(Rect(0, 1, 10, 10), reinterpret_cast<const void*>(1));
+  RTree::Node middle(Rect(0, 5, 10, 10), reinterpret_cast<const void*>(5));
+  EXPECT_TRUE(RTree::Node::CompareVertical(&low, &middle));
+  EXPECT_FALSE(RTree::Node::CompareVertical(&middle, &low));
+
+  // Try a non-overlapping higher-y rectangle.
+  RTree::Node high(Rect(-10, 20, 10, 1), reinterpret_cast<const void*>(10));
+  EXPECT_TRUE(RTree::Node::CompareVertical(&low, &high));
+  EXPECT_FALSE(RTree::Node::CompareVertical(&high, &low));
+
+  // Ties are broken by lowest bottom y value.
+  RTree::Node shorter_tie(Rect(10, 1, 100, 2),
+                          reinterpret_cast<const void*>(2));
+  EXPECT_TRUE(RTree::Node::CompareVertical(&shorter_tie, &low));
+  EXPECT_FALSE(RTree::Node::CompareVertical(&low, &shorter_tie));
+}
+
+TEST_F(RTreeTest, NodeCompareHorizontal) {
+  // One rect with lower x than another should always sort lower than higher x.
+  RTree::Node low(Rect(1, 0, 10, 10), reinterpret_cast<const void*>(1));
+  RTree::Node middle(Rect(5, 0, 10, 10), reinterpret_cast<const void*>(5));
+  EXPECT_TRUE(RTree::Node::CompareHorizontal(&low, &middle));
+  EXPECT_FALSE(RTree::Node::CompareHorizontal(&middle, &low));
+
+  // Try a non-overlapping higher-x rectangle.
+  RTree::Node high(Rect(20, -10, 1, 10), reinterpret_cast<const void*>(10));
+  EXPECT_TRUE(RTree::Node::CompareHorizontal(&low, &high));
+  EXPECT_FALSE(RTree::Node::CompareHorizontal(&high, &low));
+
+  // Ties are broken by lowest bottom x value.
+  RTree::Node shorter_tie(Rect(1, 10, 2, 100),
+                          reinterpret_cast<const void*>(2));
+  EXPECT_TRUE(RTree::Node::CompareHorizontal(&shorter_tie, &low));
+  EXPECT_FALSE(RTree::Node::CompareHorizontal(&low, &shorter_tie));
+}
+
+TEST_F(RTreeTest, NodeCompareCenterDistanceFromParent) {
+  // Create a test node we can add children to, for distance comparisons.
+  scoped_ptr<RTree::Node> parent(new RTree::Node(0));
+
+  // Add three children, one each with centers at (0, 0), (10, 10), (-9, -9),
+  // around which a bounding box will be centered at (0, 0)
+  RTree::Node* center_zero =
+      new RTree::Node(Rect(-1, -1, 2, 2), reinterpret_cast<const void*>(1));
+  parent->AddChild(center_zero);
+
+  RTree::Node* center_positive =
+      new RTree::Node(Rect(9, 9, 2, 2), reinterpret_cast<const void*>(2));
+  parent->AddChild(center_positive);
+
+  RTree::Node* center_negative =
+      new RTree::Node(Rect(-10, -10, 2, 2), reinterpret_cast<const void*>(3));
+  parent->AddChild(center_negative);
+
+  ValidateNode(parent.get(), 1U, 5U);
+  EXPECT_TRUE(parent->rect_ == Rect(-10, -10, 21, 21));
+
+  EXPECT_TRUE(RTree::Node::CompareCenterDistanceFromParent(center_zero,
+                                                           center_positive));
+  EXPECT_FALSE(RTree::Node::CompareCenterDistanceFromParent(center_positive,
+                                                            center_zero));
+
+  EXPECT_TRUE(RTree::Node::CompareCenterDistanceFromParent(center_zero,
+                                                           center_negative));
+  EXPECT_FALSE(RTree::Node::CompareCenterDistanceFromParent(center_negative,
+                                                            center_zero));
+
+  EXPECT_TRUE(RTree::Node::CompareCenterDistanceFromParent(center_negative,
+                                                           center_positive));
+  EXPECT_FALSE(RTree::Node::CompareCenterDistanceFromParent(center_positive,
+                                                            center_negative));
+}
+
+TEST_F(RTreeTest, NodeOverlapIncreaseToAdd) {
+  // Create a test node with three children, for overlap comparisons.
+  scoped_ptr<RTree::Node> parent(new RTree::Node(0));
+
+  // Add three children, each 4 wide and tall, at (0, 0), (3, 3), (6, 6) with
+  // overlapping corners.
+  Rect top(0, 0, 4, 4);
+  parent->AddChild(new RTree::Node(top, reinterpret_cast<const void*>(1)));
+  Rect middle(3, 3, 4, 4);
+  parent->AddChild(new RTree::Node(middle, reinterpret_cast<const void*>(2)));
+  Rect bottom(6, 6, 4, 4);
+  parent->AddChild(new RTree::Node(bottom, reinterpret_cast<const void*>(3)));
+  ValidateNode(parent.get(), 1U, 5U);
+
+  // Test a rect in corner.
+  Rect corner(0, 0, 1, 1);
+  Rect expanded = top;
+  expanded.Union(corner);
+  // It should not add any overlap to add this to the first child at (0, 0);
+  EXPECT_EQ(parent->OverlapIncreaseToAdd(corner, 0, expanded), 0);
+
+  expanded = middle;
+  expanded.Union(corner);
+  // Overlap for middle rectangle should increase from 2 pixels at (3, 3) and
+  // (6, 6) to 17 pixels, as it will now cover 4x4 rectangle top,
+  // so a change of +15
+  EXPECT_EQ(parent->OverlapIncreaseToAdd(corner, 1, expanded), 15);
+
+  expanded = bottom;
+  expanded.Union(corner);
+  // Overlap for bottom rectangle should increase from 1 pixel at (6, 6) to
+  // 32 pixels, as it will now cover both 4x4 rectangles top and middle,
+  // so a change of 31
+  EXPECT_EQ(parent->OverlapIncreaseToAdd(corner, 2, expanded), 31);
+
+  // Test a rect that doesn't overlap with anything, in the far right corner.
+  Rect far_corner(9, 0, 1, 1);
+  expanded = top;
+  expanded.Union(far_corner);
+  // Overlap of top should go from 1 to 4, as it will now cover the entire first
+  // row of pixels in middle.
+  EXPECT_EQ(parent->OverlapIncreaseToAdd(far_corner, 0, expanded), 3);
+
+  expanded = middle;
+  expanded.Union(far_corner);
+  // Overlap of middle should go from 2 to 8, as it will cover the rightmost 4
+  // pixels of top and the top 4 pixles of bottom as it expands.
+  EXPECT_EQ(parent->OverlapIncreaseToAdd(far_corner, 1, expanded), 6);
+
+  expanded = bottom;
+  expanded.Union(far_corner);
+  // Overlap of bottom should go from 1 to 4, as it will now cover the rightmost
+  // 4 pixels of middle.
+  EXPECT_EQ(parent->OverlapIncreaseToAdd(far_corner, 2, expanded), 3);
+}
+
+TEST_F(RTreeTest, NodeBuildLowBounds) {
+  ScopedVector<RTree::Node> nodes;
+  nodes.reserve(10);
+  for (int i = 1; i <= 10; ++i) {
+    nodes.push_back(
+        new RTree::Node(Rect(0, 0, i, i), reinterpret_cast<const void*>(i)));
+  }
+  std::vector<Rect> vertical_bounds;
+  std::vector<Rect> horizontal_bounds;
+  RTree::Node::BuildLowBounds(
+      nodes.get(), nodes.get(), &vertical_bounds, &horizontal_bounds);
+  for (int i = 0; i < 10; ++i) {
+    EXPECT_EQ(vertical_bounds[i], Rect(0, 0, i + 1, i + 1));
+    EXPECT_EQ(horizontal_bounds[i], Rect(0, 0, i + 1, i + 1));
+  }
+}
+
+TEST_F(RTreeTest, NodeBuildHighBounds) {
+  ScopedVector<RTree::Node> nodes;
+  nodes.reserve(25);
+  for (int i = 0; i < 25; ++i) {
+    nodes.push_back(new RTree::Node(Rect(i, i, 25 - i, 25 - i),
+                                    reinterpret_cast<const void*>(i)));
+  }
+  std::vector<Rect> vertical_bounds;
+  std::vector<Rect> horizontal_bounds;
+  RTree::Node::BuildHighBounds(
+      nodes.get(), nodes.get(), &vertical_bounds, &horizontal_bounds);
+  for (int i = 0; i < 25; ++i) {
+    EXPECT_EQ(vertical_bounds[i], Rect(i, i, 25 - i, 25 - i));
+    EXPECT_EQ(horizontal_bounds[i], Rect(i, i, 25 - i, 25 - i));
+  }
+}
+
+TEST_F(RTreeTest, NodeChooseSplitAxisAndIndex) {
+  std::vector<Rect> low_vertical_bounds;
+  std::vector<Rect> high_vertical_bounds;
+  std::vector<Rect> low_horizontal_bounds;
+  std::vector<Rect> high_horizontal_bounds;
+  // In this test scenario we describe a mirrored, stacked configuration of
+  // horizontal, 1 pixel high rectangles labeled a-f like this:
+  //
+  // shape: | v sort: | h sort: |
+  // -------+---------+---------+
+  // aaaaa  |    0    |    0    |
+  //  bbb   |    1    |    2    |
+  //   c    |    2    |    4    |
+  //   d    |    3    |    5    |
+  //  eee   |    4    |    3    |
+  // fffff  |    5    |    1    |
+  //
+  // These are already sorted vertically from top to bottom. Bounding rectangles
+  // of these vertically sorted will be 5 wide, i tall bounding boxes.
+  for (int i = 0; i < 6; ++i) {
+    low_vertical_bounds.push_back(Rect(0, 0, 5, i + 1));
+    high_vertical_bounds.push_back(Rect(0, i, 5, 6 - i));
+  }
+
+  // Low bounds of horizontal sort start with bounds of box a and then jump to
+  // cover everything, as box f is second in horizontal sort.
+  low_horizontal_bounds.push_back(Rect(0, 0, 5, 1));
+  for (int i = 0; i < 5; ++i) {
+    low_horizontal_bounds.push_back(Rect(0, 0, 5, 6));
+  }
+
+  // High horizontal bounds are hand-calculated.
+  high_horizontal_bounds.push_back(Rect(0, 0, 5, 6));
+  high_horizontal_bounds.push_back(Rect(0, 1, 5, 5));
+  high_horizontal_bounds.push_back(Rect(1, 1, 3, 4));
+  high_horizontal_bounds.push_back(Rect(1, 2, 3, 3));
+  high_horizontal_bounds.push_back(Rect(2, 2, 1, 2));
+  high_horizontal_bounds.push_back(Rect(2, 3, 1, 1));
+
+  // This should split vertically, right down the middle.
+  EXPECT_TRUE(RTree::Node::ChooseSplitAxis(low_vertical_bounds,
+                                           high_vertical_bounds,
+                                           low_horizontal_bounds,
+                                           high_horizontal_bounds,
+                                           2,
+                                           5));
+  EXPECT_EQ(3U,
+            RTree::Node::ChooseSplitIndex(
+                2, 5, low_vertical_bounds, high_vertical_bounds));
+
+  // We rotate the shape to test horizontal split axis detection:
+  //
+  //         +--------+
+  //         | a    f |
+  //         | ab  ef |
+  // sort:   | abcdef |
+  //         | ab  ef |
+  //         | a    f |
+  //         |--------+
+  // v sort: | 024531 |
+  // h sort: | 012345 |
+  //         +--------+
+  //
+  // Clear out old bounds first.
+  low_vertical_bounds.clear();
+  high_vertical_bounds.clear();
+  low_horizontal_bounds.clear();
+  high_horizontal_bounds.clear();
+
+  // Low bounds of vertical sort start with bounds of box a and then jump to
+  // cover everything, as box f is second in vertical sort.
+  low_vertical_bounds.push_back(Rect(0, 0, 1, 5));
+  for (int i = 0; i < 5; ++i) {
+    low_vertical_bounds.push_back(Rect(0, 0, 6, 5));
+  }
+
+  // High vertical bounds are hand-calculated.
+  high_vertical_bounds.push_back(Rect(0, 0, 6, 5));
+  high_vertical_bounds.push_back(Rect(1, 0, 5, 5));
+  high_vertical_bounds.push_back(Rect(1, 1, 4, 3));
+  high_vertical_bounds.push_back(Rect(2, 1, 3, 3));
+  high_vertical_bounds.push_back(Rect(2, 2, 2, 1));
+  high_vertical_bounds.push_back(Rect(3, 2, 1, 1));
+
+  // These are already sorted horizontally from left to right. Bounding
+  // rectangles of these horizontally sorted will be i wide, 5 tall bounding
+  // boxes.
+  for (int i = 0; i < 6; ++i) {
+    low_horizontal_bounds.push_back(Rect(0, 0, i + 1, 5));
+    high_horizontal_bounds.push_back(Rect(i, 0, 6 - i, 5));
+  }
+
+  // This should split horizontally, right down the middle.
+  EXPECT_FALSE(RTree::Node::ChooseSplitAxis(low_vertical_bounds,
+                                            high_vertical_bounds,
+                                            low_horizontal_bounds,
+                                            high_horizontal_bounds,
+                                            2,
+                                            5));
+  EXPECT_EQ(3U,
+            RTree::Node::ChooseSplitIndex(
+                2, 5, low_horizontal_bounds, high_horizontal_bounds));
+}
+
+TEST_F(RTreeTest, NodeDivideChildren) {
+  // Create a test node to split.
+  scoped_ptr<RTree::Node> test_node(new RTree::Node(0));
+  std::vector<RTree::Node*> sorted_children;
+  std::vector<Rect> low_bounds;
+  std::vector<Rect> high_bounds;
+  // Insert 10 record nodes, also inserting them into our children array.
+  for (int i = 1; i <= 10; ++i) {
+    RTree::Node* node =
+        new RTree::Node(Rect(0, 0, i, i), reinterpret_cast<const void*>(i));
+    test_node->AddChild(node);
+    sorted_children.push_back(node);
+    low_bounds.push_back(Rect(0, 0, i, i));
+    high_bounds.push_back(Rect(0, 0, 10, 10));
+  }
+  // Split the children in half.
+  scoped_ptr<RTree::Node> split_node(
+      test_node->DivideChildren(low_bounds, high_bounds, sorted_children, 5));
+  // Both nodes should be valid.
+  ValidateNode(test_node.get(), 1U, 10U);
+  ValidateNode(split_node.get(), 1U, 10U);
+  // Both nodes should have five children.
+  EXPECT_EQ(test_node->children_.size(), 5U);
+  EXPECT_EQ(split_node->children_.size(), 5U);
+  // Test node should have children 1-5, split node should have children 6-10.
+  for (int i = 0; i < 5; ++i) {
+    EXPECT_EQ(test_node->children_[i]->key(),
+              reinterpret_cast<const void*>(i + 1));
+    EXPECT_EQ(split_node->children_[i]->key(),
+              reinterpret_cast<const void*>(i + 6));
+  }
+}
+
+TEST_F(RTreeTest, NodeRemoveChildNoOrphans) {
+  scoped_ptr<RTree::Node> test_parent(new RTree::Node(0));
+  scoped_ptr<RTree::Node> child_one(
+      new RTree::Node(Rect(0, 0, 1, 1), reinterpret_cast<const void*>(1)));
+  scoped_ptr<RTree::Node> child_two(
+      new RTree::Node(Rect(0, 0, 2, 2), reinterpret_cast<const void*>(2)));
+  scoped_ptr<RTree::Node> child_three(
+      new RTree::Node(Rect(0, 0, 3, 3), reinterpret_cast<const void*>(3)));
+  test_parent->AddChild(child_one.get());
+  test_parent->AddChild(child_two.get());
+  test_parent->AddChild(child_three.get());
+  ValidateNode(test_parent.get(), 1U, 5U);
+  // Remove the middle node.
+  std::vector<RTree::Node*> orphans;
+  EXPECT_EQ(test_parent->RemoveChild(child_two.get(), &orphans), 2U);
+  EXPECT_EQ(orphans.size(), 0U);
+  EXPECT_EQ(test_parent->count(), 2U);
+  test_parent->RecomputeBoundsNoParents();
+  ValidateNode(test_parent.get(), 1U, 5U);
+  // Remove the end node.
+  EXPECT_EQ(test_parent->RemoveChild(child_three.get(), &orphans), 1U);
+  EXPECT_EQ(orphans.size(), 0U);
+  EXPECT_EQ(test_parent->count(), 1U);
+  test_parent->RecomputeBoundsNoParents();
+  ValidateNode(test_parent.get(), 1U, 5U);
+  // Remove the first node.
+  EXPECT_EQ(test_parent->RemoveChild(child_one.get(), &orphans), 0U);
+  EXPECT_EQ(orphans.size(), 0U);
+  EXPECT_EQ(test_parent->count(), 0U);
+}
+
+TEST_F(RTreeTest, NodeRemoveChildOrphans) {
+  // Build flattened binary tree of Nodes 4 deep, from the record nodes up.
+  ScopedVector<RTree::Node> nodes;
+  nodes.resize(15);
+  // Indicies 7 through 15 are record nodes.
+  for (int i = 7; i < 15; ++i) {
+    nodes[i] =
+        new RTree::Node(Rect(0, 0, i, i), reinterpret_cast<const void*>(i));
+  }
+  // Nodes 3 through 6 are level 0 (leaves) and get 2 record nodes each.
+  for (int i = 3; i < 7; ++i) {
+    nodes[i] = new RTree::Node(0);
+    nodes[i]->AddChild(nodes[(i * 2) + 1]);
+    nodes[i]->AddChild(nodes[(i * 2) + 2]);
+  }
+  // Nodes 1 and 2 are level 1 and get 2 leaves each.
+  for (int i = 1; i < 3; ++i) {
+    nodes[i] = new RTree::Node(1);
+    nodes[i]->AddChild(nodes[(i * 2) + 1]);
+    nodes[i]->AddChild(nodes[(i * 2) + 2]);
+  }
+  // Node 0 is level 2 and gets 2 childen.
+  nodes[0] = new RTree::Node(2);
+  nodes[0]->AddChild(nodes[1]);
+  nodes[0]->AddChild(nodes[2]);
+  // This should now be a valid node structure.
+  ValidateNode(nodes[0], 2U, 2U);
+
+  // Now remove the level 0 nodes, so we get the record nodes as orphans.
+  std::vector<RTree::Node*> orphans;
+  EXPECT_EQ(nodes[1]->RemoveChild(nodes[3], &orphans), 1U);
+  EXPECT_EQ(nodes[1]->RemoveChild(nodes[4], &orphans), 0U);
+  EXPECT_EQ(nodes[2]->RemoveChild(nodes[5], &orphans), 1U);
+  EXPECT_EQ(nodes[2]->RemoveChild(nodes[6], &orphans), 0U);
+
+  // Orphans should be nodes 7 through 15 in order.
+  EXPECT_EQ(orphans.size(), 8U);
+  for (int i = 0; i < 8; ++i) {
+    EXPECT_EQ(orphans[i], nodes[i + 7]);
+  }
+
+  // Now we remove nodes 1 and 2 from the root, expecting no further orphans.
+  // This prevents a crash due to double-delete on test exit, as no node should
+  // own any other node right now.
+  EXPECT_EQ(nodes[0]->RemoveChild(nodes[1], &orphans), 1U);
+  EXPECT_EQ(nodes[0]->RemoveChild(nodes[2], &orphans), 0U);
+}
+
+TEST_F(RTreeTest, NodeRemoveAndReturnLastChild) {
+  scoped_ptr<RTree::Node> test_parent(new RTree::Node(0));
+  scoped_ptr<RTree::Node> child_one(
+      new RTree::Node(Rect(0, 0, 1, 1), reinterpret_cast<const void*>(1)));
+  scoped_ptr<RTree::Node> child_two(
+      new RTree::Node(Rect(0, 0, 2, 2), reinterpret_cast<const void*>(2)));
+  scoped_ptr<RTree::Node> child_three(
+      new RTree::Node(Rect(0, 0, 3, 3), reinterpret_cast<const void*>(3)));
+  test_parent->AddChild(child_one.get());
+  test_parent->AddChild(child_two.get());
+  test_parent->AddChild(child_three.get());
+  ValidateNode(test_parent.get(), 1U, 5U);
+
+  EXPECT_EQ(test_parent->RemoveAndReturnLastChild(), child_three.get());
+  EXPECT_EQ(test_parent->count(), 2U);
+  test_parent->RecomputeBoundsNoParents();
+  ValidateNode(test_parent.get(), 1U, 5U);
+
+  EXPECT_EQ(test_parent->RemoveAndReturnLastChild(), child_two.get());
+  EXPECT_EQ(test_parent->count(), 1U);
+  test_parent->RecomputeBoundsNoParents();
+  ValidateNode(test_parent.get(), 1U, 5U);
+
+  EXPECT_EQ(test_parent->RemoveAndReturnLastChild(), child_one.get());
+  EXPECT_EQ(test_parent->count(), 0U);
+}
+
+// TODO: investigate and remove needless children ordering assumptions.
+TEST_F(RTreeTest, NodeLeastOverlapIncrease) {
+  scoped_ptr<RTree::Node> test_parent(new RTree::Node(0));
+  // Construct 4 nodes with 1x2 retangles spaced horizontally 1 pixel apart, or:
+  //
+  // a b c d
+  // a b c d
+  //
+  for (int i = 0; i < 4; ++i) {
+    test_parent->AddChild(new RTree::Node(
+        Rect(i * 2, 0, 1, 2), reinterpret_cast<const void*>(i + 1)));
+  }
+
+  ValidateNode(test_parent.get(), 1U, 5U);
+
+  // Test rect at (7, 0) should require minimum overlap on the part of the
+  // fourth rectangle to add:
+  //
+  // a b c dT
+  // a b c d
+  //
+  scoped_ptr<RTree::Node> test_node_far(
+      new RTree::Node(Rect(7, 0, 1, 1), reinterpret_cast<const void*>(7)));
+  EXPECT_EQ(test_parent->LeastOverlapIncrease(test_node_far.get()),
+            test_parent->children_[3]);
+
+  // Test rect covering the bottom half of all children should be a 4-way tie,
+  // so LeastOverlapIncrease should return NULL:
+  //
+  // a b c d
+  // TTTTTTT
+  //
+  scoped_ptr<RTree::Node> test_node_tie(
+      new RTree::Node(Rect(0, 1, 7, 1), reinterpret_cast<const void*>(8)));
+  EXPECT_TRUE(test_parent->LeastOverlapIncrease(test_node_tie.get()) == NULL);
+
+  // Test rect completely inside c should return the third rectangle:
+  //
+  // a b T d
+  // a b c d
+  //
+  scoped_ptr<RTree::Node> test_node_inside(
+      new RTree::Node(Rect(4, 0, 1, 1), reinterpret_cast<const void*>(8)));
+  EXPECT_EQ(test_parent->LeastOverlapIncrease(test_node_inside.get()),
+            test_parent->children_[2]);
+
+  // Add a rectangle that overlaps completely with rectangle c, to test
+  // when there is a tie between two completely contained rectangles:
+  //
+  // a b Ted
+  // a b eed
+  //
+  test_parent->AddChild(
+      new RTree::Node(Rect(4, 0, 2, 2), reinterpret_cast<const void*>(9)));
+  EXPECT_TRUE(test_parent->LeastOverlapIncrease(test_node_inside.get()) ==
+              NULL);
+}
+
+TEST_F(RTreeTest, NodeLeastAreaEnlargement) {
+  scoped_ptr<RTree::Node> test_parent(new RTree::Node(0));
+  // Construct 4 nodes in a cross-hairs style configuration:
+  //
+  //  a
+  // b c
+  //  d
+  //
+  test_parent->AddChild(
+      new RTree::Node(Rect(1, 0, 1, 1), reinterpret_cast<const void*>(1)));
+  test_parent->AddChild(
+      new RTree::Node(Rect(0, 1, 1, 1), reinterpret_cast<const void*>(2)));
+  test_parent->AddChild(
+      new RTree::Node(Rect(2, 1, 1, 1), reinterpret_cast<const void*>(3)));
+  test_parent->AddChild(
+      new RTree::Node(Rect(1, 2, 1, 1), reinterpret_cast<const void*>(4)));
+
+  ValidateNode(test_parent.get(), 1U, 5U);
+
+  // Test rect at (1, 3) should require minimum area to add to Node d:
+  //
+  //  a
+  // b c
+  //  d
+  //  T
+  //
+  scoped_ptr<RTree::Node> test_node_below(
+      new RTree::Node(Rect(1, 3, 1, 1), reinterpret_cast<const void*>(5)));
+  EXPECT_EQ(test_parent->LeastAreaEnlargement(test_node_below.get()),
+            test_parent->children_[3]);
+
+  // Test rect completely inside b should require minimum area to add to Node b:
+  //
+  //  a
+  // T c
+  //  d
+  //
+  scoped_ptr<RTree::Node> test_node_inside(
+      new RTree::Node(Rect(0, 1, 1, 1), reinterpret_cast<const void*>(6)));
+  EXPECT_EQ(test_parent->LeastAreaEnlargement(test_node_inside.get()),
+            test_parent->children_[1]);
+
+  // Add e at (0, 1) to overlap b and c, to test tie-breaking:
+  //
+  //  a
+  // eee
+  //  d
+  //
+  test_parent->AddChild(
+      new RTree::Node(Rect(0, 1, 3, 1), reinterpret_cast<const void*>(7)));
+
+  ValidateNode(test_parent.get(), 1U, 5U);
+
+  // Test rect at (3, 1) should tie between c and e, but c has smaller area so
+  // the algorithm should select c:
+  //
+  //
+  //  a
+  // eeeT
+  //  d
+  //
+  scoped_ptr<RTree::Node> test_node_tie_breaker(
+      new RTree::Node(Rect(3, 1, 1, 1), reinterpret_cast<const void*>(8)));
+  EXPECT_EQ(test_parent->LeastAreaEnlargement(test_node_tie_breaker.get()),
+            test_parent->children_[2]);
+}
+
+}  // namespace gfx