readability review for luken

ui/gfx/geometry/r_tree_unittest.cc

 // Copyright 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 "testing/gtest/include/gtest/gtest.h"
 #include "ui/gfx/geometry/r_tree.h"
+#include "ui/gfx/geometry/r_tree_base.h"
 #include "ui/gfx/geometry/rect.h"
 
 namespace gfx {
 
 class RTreeTest : public ::testing::Test {
  protected:
-  // Given a pointer to an RTree, traverse it and verify its internal structure
-  // is consistent with the RTree semantics.
-  void ValidateRTree(RTree* rt) {
+  typedef RTree<int> RT;
+
+  // Given a pointer to an RTree, traverse it and verify that its internal
+  // structure is consistent with RTree semantics.
+  void ValidateRTree(RTreeBase* rt) {
     // If RTree is empty it should have an empty rectangle.
     if (!rt->root_->count()) {
       EXPECT_TRUE(rt->root_->rect().IsEmpty());
       EXPECT_EQ(rt->root_->level(), 0);
       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,
+  void ValidateNode(RTreeBase::NodeBase* node_base,
                     size_t min_children,
                     size_t max_children) {
-    // Record nodes have different requirements, handle up front.
-    if (node->level() == -1) {
-      // Record nodes may have no children.
-      EXPECT_EQ(node->count(), 0U);
-      // They must have an associated non-NULL key.
-      EXPECT_TRUE(node->key());
-      // They must always have a parent.
-      EXPECT_TRUE(node->parent());
-      return;
-    }
-    // Non-record node, normal expectations apply.
-    EXPECT_GE(node->count(), min_children);
-    EXPECT_LE(node->count(), max_children);
-    EXPECT_EQ(node->key(), 0);
-    CheckBoundsConsistent(node);
-    for (size_t i = 0; i < node->children_.size(); ++i) {
-      ValidateNode(node->children_[i], min_children, max_children);
+    if (node_base->level() >= 0) {
+      RTreeBase::Node* node = static_cast<RTreeBase::Node*>(node_base);
+      EXPECT_GE(node->count(), min_children);
+      EXPECT_LE(node->count(), max_children);
+      CheckBoundsConsistent(node);
+      for (size_t i = 0; i < node->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) {
+  void CheckBoundsConsistent(RTreeBase::Node* node) {
     EXPECT_FALSE(node->rect_.IsEmpty());
     Rect check_bounds;
     for (size_t i = 0; i < node->children_.size(); ++i) {
-      RTree::Node* child_node = node->children_[i];
+      RTreeBase::NodeBase* 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);
+    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) {
+  void AddStackedSquares(RT* rt, int count) {
     for (int i = 1; i <= count; ++i) {
       rt->Insert(Rect(0, 0, i, i), i);
-      ValidateRTree(rt);
+      ValidateRTree(static_cast<RTreeBase*>(rt));
     }
   }
 
   // Given an unordered list of matching keys, verify that it contains all
   // values [1..length] for the length of that list.
-  void VerifyAllKeys(const base::hash_set<intptr_t>& keys) {
-    // Verify that the keys are in values [1,count].
+  void VerifyAllKeys(const base::hash_set<int>& keys) {
+    // Verify that the keys are in values [0,count).
     for (size_t i = 1; i <= keys.size(); ++i) {
       EXPECT_EQ(keys.count(i), 1U);
     }
   }
 
   // Given a node and a rectangle, builds an expanded rectangle list where the
   // ith element of the rectangle is union of the recangle of the ith child of
   // the node and the argument rectangle.
-  void BuildExpandedRects(RTree::Node* node,
+  void BuildExpandedRects(RTreeBase::Node* node,
                           const Rect& rect,
                           std::vector<Rect>* expanded_rects) {
     expanded_rects->clear();
     expanded_rects->reserve(node->children_.size());
     for (size_t i = 0; i < node->children_.size(); ++i) {
       Rect expanded_rect(rect);
-      expanded_rect.Union(node->children_[i]->rect_);
+      expanded_rect.Union(node->children_[i]->rect());
       expanded_rects->push_back(expanded_rect);
     }
   }
 };
 
-// An empty RTree should never return Query results, and RTrees should be empty
-// upon construction.
-TEST_F(RTreeTest, QueryEmptyTree) {
-  RTree rt(2, 10);
-  ValidateRTree(&rt);
-  base::hash_set<intptr_t> results;
-  Rect test_rect(25, 25);
-  rt.Query(test_rect, &results);
-  EXPECT_EQ(results.size(), 0U);
-  ValidateRTree(&rt);
-}
-
-// Clear should empty the tree, meaning that all queries should not return
-// results after.
-TEST_F(RTreeTest, ClearEmptiesTreeOfSingleNode) {
-  RTree rt(2, 5);
-  rt.Insert(Rect(0, 0, 100, 100), 1);
-  rt.Clear();
-  base::hash_set<intptr_t> results;
-  Rect test_rect(1, 1);
-  rt.Query(test_rect, &results);
-  EXPECT_EQ(results.size(), 0U);
-  ValidateRTree(&rt);
-}
-
-// Even with a complex internal structure, clear should empty the tree, meaning
-// that all queries should not return results after.
-TEST_F(RTreeTest, ClearEmptiesTreeOfManyNodes) {
-  RTree rt(2, 5);
-  AddStackedSquares(&rt, 100);
-  rt.Clear();
-  base::hash_set<intptr_t> results;
-  Rect test_rect(1, 1);
-  rt.Query(test_rect, &results);
-  EXPECT_EQ(results.size(), 0U);
-  ValidateRTree(&rt);
-}
-
-// Duplicate inserts should overwrite previous inserts.
-TEST_F(RTreeTest, DuplicateInsertsOverwrite) {
-  RTree rt(2, 5);
-  // Add 100 stacked squares, but always with duplicate key of 1.
-  for (int i = 1; i <= 100; ++i) {
-    rt.Insert(Rect(0, 0, i, i), 1);
-    ValidateRTree(&rt);
-  }
-  base::hash_set<intptr_t> results;
-  Rect test_rect(1, 1);
-  rt.Query(test_rect, &results);
-  EXPECT_EQ(results.size(), 1U);
-  EXPECT_EQ(results.count(1), 1U);
-}
-
-// Call Remove() once on something that's been inserted repeatedly.
-TEST_F(RTreeTest, DuplicateInsertRemove) {
-  RTree rt(3, 9);
-  AddStackedSquares(&rt, 25);
-  for (int i = 1; i <= 100; ++i) {
-    rt.Insert(Rect(0, 0, i, i), 26);
-    ValidateRTree(&rt);
-  }
-  rt.Remove(26);
-  base::hash_set<intptr_t> results;
-  Rect test_rect(1, 1);
-  rt.Query(test_rect, &results);
-  EXPECT_EQ(results.size(), 25U);
-  VerifyAllKeys(results);
-}
-
-// Call Remove() repeatedly on something that's been inserted once.
-TEST_F(RTreeTest, InsertDuplicateRemove) {
-  RTree rt(7, 15);
-  AddStackedSquares(&rt, 101);
-  for (int i = 0; i < 100; ++i) {
-    rt.Remove(101);
-    ValidateRTree(&rt);
-  }
-  base::hash_set<intptr_t> results;
-  Rect test_rect(1, 1);
-  rt.Query(test_rect, &results);
-  EXPECT_EQ(results.size(), 100U);
-  VerifyAllKeys(results);
-}
-
-// Stacked rects should meet all matching queries regardless of nesting.
-TEST_F(RTreeTest, QueryStackedSquaresNestedHit) {
-  RTree rt(2, 5);
-  AddStackedSquares(&rt, 100);
-  base::hash_set<intptr_t> results;
-  Rect test_rect(1, 1);
-  rt.Query(test_rect, &results);
-  EXPECT_EQ(results.size(), 100U);
-  VerifyAllKeys(results);
-}
-
-// Stacked rects should meet all matching queries when contained completely by
-// the query rectangle.
-TEST_F(RTreeTest, QueryStackedSquaresContainedHit) {
-  RTree rt(2, 10);
-  AddStackedSquares(&rt, 100);
-  base::hash_set<intptr_t> results;
-  Rect test_rect(0, 0, 100, 100);
-  rt.Query(test_rect, &results);
-  EXPECT_EQ(results.size(), 100U);
-  VerifyAllKeys(results);
-}
-
-// Stacked rects should miss a missing query when the query has no intersection
-// with the rects.
-TEST_F(RTreeTest, QueryStackedSquaresCompleteMiss) {
-  RTree rt(2, 7);
-  AddStackedSquares(&rt, 100);
-  base::hash_set<intptr_t> results;
-  Rect test_rect(150, 150, 100, 100);
-  rt.Query(test_rect, &results);
-  EXPECT_EQ(results.size(), 0U);
-}
-
-// Removing half the nodes after insertion should still result in a valid tree.
-TEST_F(RTreeTest, RemoveHalfStackedRects) {
-  RTree rt(2, 11);
-  AddStackedSquares(&rt, 200);
-  for (int i = 101; i <= 200; ++i) {
-    rt.Remove(i);
-    ValidateRTree(&rt);
-  }
-  base::hash_set<intptr_t> results;
-  Rect test_rect(1, 1);
-  rt.Query(test_rect, &results);
-  EXPECT_EQ(results.size(), 100U);
-  VerifyAllKeys(results);
-  // Add the nodes back in.
-  for (int i = 101; i <= 200; ++i) {
-    rt.Insert(Rect(0, 0, i, i), i);
-    ValidateRTree(&rt);
-  }
-  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), (i * 2) - 1);
-    ValidateRTree(&rt);
-    rt.Insert(Rect(0, 0, i, i), i * 2);
-    ValidateRTree(&rt);
-  }
-  base::hash_set<intptr_t> results;
-  Rect test_rect(-1, -1, 2, 2);
-  rt.Query(test_rect, &results);
-  EXPECT_EQ(results.size(), 200U);
-  VerifyAllKeys(results);
-}
-
-TEST_F(RTreeTest, RemoveNegativeCoordsRect) {
-  RTree rt(7, 21);
-  // Add 100 positive stacked squares.
-  AddStackedSquares(&rt, 100);
-  // Now add 100 negative stacked squares.
-  for (int i = 101; i <= 200; ++i) {
-    rt.Insert(Rect(100 - i, 100 - i, i - 100, i - 100), 301 - i);
-    ValidateRTree(&rt);
-  }
-  // Now remove half of the negative squares.
-  for (int i = 101; i <= 150; ++i) {
-    rt.Remove(301 - i);
-    ValidateRTree(&rt);
-  }
-  // Queries should return 100 positive and 50 negative stacked squares.
-  base::hash_set<intptr_t> results;
-  Rect test_rect(-1, -1, 2, 2);
-  rt.Query(test_rect, &results);
-  EXPECT_EQ(results.size(), 150U);
-  VerifyAllKeys(results);
-}
-
-TEST_F(RTreeTest, InsertEmptyRectReplacementRemovesKey) {
-  RTree rt(10, 31);
-  AddStackedSquares(&rt, 50);
-  ValidateRTree(&rt);
-
-  // Replace last square with empty rect.
-  rt.Insert(Rect(), 50);
-  ValidateRTree(&rt);
-
-  // Now query large area to get all rects in tree.
-  base::hash_set<intptr_t> results;
-  Rect test_rect(0, 0, 100, 100);
-  rt.Query(test_rect, &results);
-
-  // Should only be 49 rects in tree.
-  EXPECT_EQ(results.size(), 49U);
-  VerifyAllKeys(results);
-}
-
-TEST_F(RTreeTest, NodeRemoveNodesForReinsert) {
+class RTreeNodeTest : public RTreeTest {
+ protected:
+  typedef RTreeBase::NodeBase RTreeNodeBase;
+  typedef RT::Record RTreeRecord;
+  typedef RTreeBase::Node RTreeNode;
+  typedef RTreeBase::Node::Rects RTreeRects;
+
+  // Accessors to private members of RTree::Node.
+  RTreeRecord* record(RTreeNode* node, size_t i) {
+    return static_cast<RTreeRecord*>(node->children_[i]);
+  }
+
+  // Provides access for tests to private methods of RTree::Node.
+  RTreeNode* NewNodeAtLevel(size_t level) { return new RTreeBase::Node(level); }
+
+  void NodeRecomputeLocalBounds(RTreeNodeBase* node) {
+    node->RecomputeLocalBounds();
+  }
+
+  bool NodeCompareVertical(RTreeNodeBase* a, RTreeNodeBase* b) {
+    return RTreeBase::Node::CompareVertical(a, b);
+  }
+
+  bool NodeCompareHorizontal(RTreeNodeBase* a, RTreeNodeBase* b) {
+    return RTreeBase::Node::CompareHorizontal(a, b);
+  }
+
+  bool NodeCompareCenterDistanceFromParent(RTreeNodeBase* a, RTreeNodeBase* b) {
+    return RTreeBase::Node::CompareCenterDistanceFromParent(a, b);
+  }
+
+  int NodeOverlapIncreaseToAdd(RTreeNode* node,
+                               const Rect& rect,
+                               size_t candidate,
+                               const Rect& expanded_rect) {
+    return node->OverlapIncreaseToAdd(rect, candidate, expanded_rect);
+  }
+
+  void NodeBuildLowBounds(const std::vector<RTreeNodeBase*>& vertical_sort,
+                          const std::vector<RTreeNodeBase*>& horizontal_sort,
+                          RTreeRects* vertical_bounds,
+                          RTreeRects* horizontal_bounds) {
+    RTreeBase::Node::BuildLowBounds(
+        vertical_sort, horizontal_sort, vertical_bounds, horizontal_bounds);
+  }
+
+  void NodeBuildHighBounds(const std::vector<RTreeNodeBase*>& vertical_sort,
+                           const std::vector<RTreeNodeBase*>& horizontal_sort,
+                           RTreeRects* vertical_bounds,
+                           RTreeRects* horizontal_bounds) {
+    RTreeBase::Node::BuildHighBounds(
+        vertical_sort, horizontal_sort, vertical_bounds, horizontal_bounds);
+  }
+
+  int NodeSmallestMarginSum(size_t start_index,
+                            size_t end_index,
+                            const RTreeRects& low_bounds,
+                            const RTreeRects& high_bounds) {
+    return RTreeBase::Node::SmallestMarginSum(
+        start_index, end_index, low_bounds, high_bounds);
+  }
+
+  size_t NodeChooseSplitIndex(size_t min_children,
+                              size_t max_children,
+                              const RTreeRects& low_bounds,
+                              const RTreeRects& high_bounds) {
+    return RTreeBase::Node::ChooseSplitIndex(
+        min_children, max_children, low_bounds, high_bounds);
+  }
+
+  RTreeNode* NodeDivideChildren(
+      RTreeNode* node,
+      const RTreeRects& low_bounds,
+      const RTreeRects& high_bounds,
+      const std::vector<RTreeNodeBase*>& sorted_children,
+      size_t split_index) {
+    return node->DivideChildren(
+        low_bounds, high_bounds, sorted_children, split_index);
+  }
+
+  RTreeNode* NodeLeastOverlapIncrease(RTreeNode* node,
+                                      const Rect& node_rect,
+                                      const RTreeRects& expanded_rects) {
+    return node->LeastOverlapIncrease(node_rect, expanded_rects);
+  }
+
+  RTreeNode* NodeLeastAreaEnlargement(RTreeNode* node,
+                                      const Rect& node_rect,
+                                      const RTreeRects& expanded_rects) {
+    return node->LeastAreaEnlargement(node_rect, expanded_rects);
+  }
+};
+
+// RTreeNodeTest --------------------------------------------------------------
+
+TEST_F(RTreeNodeTest, RemoveNodesForReinsert) {
   // Make a leaf node for testing removal from.
-  scoped_ptr<RTree::Node> test_node(new RTree::Node(0));
+  scoped_ptr<RTreeNode> test_node(new RTreeNode);
   // Build 20 record nodes with rectangle centers going from (1,1) to (20,20)
   for (int i = 1; i <= 20; ++i) {
-    test_node->AddChild(new RTree::Node(Rect(i - 1, i - 1, 2, 2), i));
+    test_node->AddChild(scoped_ptr<RTreeNodeBase>(
+        new RTreeRecord(Rect(i - 1, i - 1, 2, 2), i)));
   }
   // Quick verification of the node before removing children.
   ValidateNode(test_node.get(), 1U, 20U);
   // Use a scoped vector to delete all children that get removed from the Node.
-  ScopedVector<RTree::Node> removals;
+  ScopedVector<RTreeNodeBase> removals;
   test_node->RemoveNodesForReinsert(1, &removals);
   // 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();
+  NodeRecomputeLocalBounds(test_node.get());
   ValidateNode(test_node.get(), 2U, 20U);
   // The node we removed should be node 10, as it was exactly in the center.
-  EXPECT_EQ(removals[0]->key(), 10);
+  EXPECT_EQ(static_cast<RTreeRecord*>(removals[0])->key(), 10);
 
   // Now remove the next 2.
   removals.clear();
   test_node->RemoveNodesForReinsert(2, &removals);
   EXPECT_EQ(removals.size(), 2U);
   EXPECT_EQ(test_node->count(), 17U);
-  test_node->RecomputeBoundsNoParents();
+  NodeRecomputeLocalBounds(test_node.get());
   ValidateNode(test_node.get(), 2U, 20U);
   // Lastly the 2 nodes we should have gotten back are keys 9 and 11, as their
   // centers were the closest to the center of the node bounding box.
   base::hash_set<intptr_t> results_hash;
-  results_hash.insert(removals[0]->key());
-  results_hash.insert(removals[1]->key());
+  results_hash.insert(static_cast<RTreeRecord*>(removals[0])->key());
+  results_hash.insert(static_cast<RTreeRecord*>(removals[1])->key());
   EXPECT_EQ(results_hash.count(9), 1U);
   EXPECT_EQ(results_hash.count(11), 1U);
 }
 
-TEST_F(RTreeTest, NodeCompareVertical) {
+TEST_F(RTreeNodeTest, CompareVertical) {
   // One rect with lower y than another should always sort lower than higher y.
-  RTree::Node low(Rect(0, 1, 10, 10), 1);
-  RTree::Node middle(Rect(0, 5, 10, 10), 5);
-  EXPECT_TRUE(RTree::Node::CompareVertical(&low, &middle));
-  EXPECT_FALSE(RTree::Node::CompareVertical(&middle, &low));
+  RTreeRecord low(Rect(0, 1, 10, 10), 1);
+  RTreeRecord middle(Rect(0, 5, 10, 10), 5);
+  EXPECT_TRUE(NodeCompareVertical(&low, &middle));
+  EXPECT_FALSE(NodeCompareVertical(&middle, &low));
 
   // Try a non-overlapping higher-y rectangle.
-  RTree::Node high(Rect(-10, 20, 10, 1), 10);
-  EXPECT_TRUE(RTree::Node::CompareVertical(&low, &high));
-  EXPECT_FALSE(RTree::Node::CompareVertical(&high, &low));
+  RTreeRecord high(Rect(-10, 20, 10, 1), 10);
+  EXPECT_TRUE(NodeCompareVertical(&low, &high));
+  EXPECT_FALSE(NodeCompareVertical(&high, &low));
 
   // Ties are broken by lowest bottom y value.
-  RTree::Node shorter_tie(Rect(10, 1, 100, 2), 2);
-  EXPECT_TRUE(RTree::Node::CompareVertical(&shorter_tie, &low));
-  EXPECT_FALSE(RTree::Node::CompareVertical(&low, &shorter_tie));
-}
-
-TEST_F(RTreeTest, NodeCompareHorizontal) {
+  RTreeRecord shorter_tie(Rect(10, 1, 100, 2), 2);
+  EXPECT_TRUE(NodeCompareVertical(&shorter_tie, &low));
+  EXPECT_FALSE(NodeCompareVertical(&low, &shorter_tie));
+}
+
+TEST_F(RTreeNodeTest, CompareHorizontal) {
   // One rect with lower x than another should always sort lower than higher x.
-  RTree::Node low(Rect(1, 0, 10, 10), 1);
-  RTree::Node middle(Rect(5, 0, 10, 10), 5);
-  EXPECT_TRUE(RTree::Node::CompareHorizontal(&low, &middle));
-  EXPECT_FALSE(RTree::Node::CompareHorizontal(&middle, &low));
+  RTreeRecord low(Rect(1, 0, 10, 10), 1);
+  RTreeRecord middle(Rect(5, 0, 10, 10), 5);
+  EXPECT_TRUE(NodeCompareHorizontal(&low, &middle));
+  EXPECT_FALSE(NodeCompareHorizontal(&middle, &low));
 
   // Try a non-overlapping higher-x rectangle.
-  RTree::Node high(Rect(20, -10, 1, 10), 10);
-  EXPECT_TRUE(RTree::Node::CompareHorizontal(&low, &high));
-  EXPECT_FALSE(RTree::Node::CompareHorizontal(&high, &low));
+  RTreeRecord high(Rect(20, -10, 1, 10), 10);
+  EXPECT_TRUE(NodeCompareHorizontal(&low, &high));
+  EXPECT_FALSE(NodeCompareHorizontal(&high, &low));
 
   // Ties are broken by lowest bottom x value.
-  RTree::Node shorter_tie(Rect(1, 10, 2, 100), 2);
-  EXPECT_TRUE(RTree::Node::CompareHorizontal(&shorter_tie, &low));
-  EXPECT_FALSE(RTree::Node::CompareHorizontal(&low, &shorter_tie));
-}
-
-TEST_F(RTreeTest, NodeCompareCenterDistanceFromParent) {
+  RTreeRecord shorter_tie(Rect(1, 10, 2, 100), 2);
+  EXPECT_TRUE(NodeCompareHorizontal(&shorter_tie, &low));
+  EXPECT_FALSE(NodeCompareHorizontal(&low, &shorter_tie));
+}
+
+TEST_F(RTreeNodeTest, CompareCenterDistanceFromParent) {
   // Create a test node we can add children to, for distance comparisons.
-  scoped_ptr<RTree::Node> parent(new RTree::Node(0));
+  scoped_ptr<RTreeNode> parent(new RTreeNode);
 
   // Add three children, one each with centers at (0, 0), (10, 10), (-9, -9),
   // around which a bounding box will be centered at (0, 0)
-  RTree::Node* center_zero = new RTree::Node(Rect(-1, -1, 2, 2), 1);
-  parent->AddChild(center_zero);
-
-  RTree::Node* center_positive = new RTree::Node(Rect(9, 9, 2, 2), 2);
-  parent->AddChild(center_positive);
-
-  RTree::Node* center_negative = new RTree::Node(Rect(-10, -10, 2, 2), 3);
-  parent->AddChild(center_negative);
+  RTreeRecord* center_zero = new RTreeRecord(Rect(-1, -1, 2, 2), 1);
+  parent->AddChild(scoped_ptr<RTreeNodeBase>(center_zero));
+
+  RTreeRecord* center_positive = new RTreeRecord(Rect(9, 9, 2, 2), 2);
+  parent->AddChild(scoped_ptr<RTreeNodeBase>(center_positive));
+
+  RTreeRecord* center_negative = new RTreeRecord(Rect(-10, -10, 2, 2), 3);
+  parent->AddChild(scoped_ptr<RTreeNodeBase>(center_negative));
 
   ValidateNode(parent.get(), 1U, 5U);
-  EXPECT_EQ(parent->rect_, Rect(-10, -10, 21, 21));
-
-  EXPECT_TRUE(RTree::Node::CompareCenterDistanceFromParent(center_zero,
-                                                           center_positive));
-  EXPECT_FALSE(RTree::Node::CompareCenterDistanceFromParent(center_positive,
-                                                            center_zero));
-
-  EXPECT_TRUE(RTree::Node::CompareCenterDistanceFromParent(center_zero,
-                                                           center_negative));
-  EXPECT_FALSE(RTree::Node::CompareCenterDistanceFromParent(center_negative,
-                                                            center_zero));
-
-  EXPECT_TRUE(RTree::Node::CompareCenterDistanceFromParent(center_negative,
-                                                           center_positive));
-  EXPECT_FALSE(RTree::Node::CompareCenterDistanceFromParent(center_positive,
-                                                            center_negative));
-}
-
-TEST_F(RTreeTest, NodeOverlapIncreaseToAdd) {
+  EXPECT_EQ(parent->rect(), Rect(-10, -10, 21, 21));
+
+  EXPECT_TRUE(
+      NodeCompareCenterDistanceFromParent(center_zero, center_positive));
+  EXPECT_FALSE(
+      NodeCompareCenterDistanceFromParent(center_positive, center_zero));
+  EXPECT_TRUE(
+      NodeCompareCenterDistanceFromParent(center_zero, center_negative));
+  EXPECT_FALSE(
+      NodeCompareCenterDistanceFromParent(center_negative, center_zero));
+  EXPECT_TRUE(
+      NodeCompareCenterDistanceFromParent(center_negative, center_positive));
+  EXPECT_FALSE(
+      NodeCompareCenterDistanceFromParent(center_positive, center_negative));
+}
+
+TEST_F(RTreeNodeTest, OverlapIncreaseToAdd) {
   // Create a test node with three children, for overlap comparisons.
-  scoped_ptr<RTree::Node> parent(new RTree::Node(0));
+  scoped_ptr<RTreeNode> parent(new RTreeNode);
 
   // Add three children, each 4 wide and tall, at (0, 0), (3, 3), (6, 6) with
   // overlapping corners.
   Rect top(0, 0, 4, 4);
-  parent->AddChild(new RTree::Node(top, 1));
+  parent->AddChild(scoped_ptr<RTreeNodeBase>(new RTreeRecord(top, 1)));
   Rect middle(3, 3, 4, 4);
-  parent->AddChild(new RTree::Node(middle, 2));
+  parent->AddChild(scoped_ptr<RTreeNodeBase>(new RTreeRecord(middle, 2)));
   Rect bottom(6, 6, 4, 4);
-  parent->AddChild(new RTree::Node(bottom, 3));
+  parent->AddChild(scoped_ptr<RTreeNodeBase>(new RTreeRecord(bottom, 3)));
   ValidateNode(parent.get(), 1U, 5U);
 
   // Test a rect in corner.
   Rect corner(0, 0, 1, 1);
   Rect expanded = top;
   expanded.Union(corner);
   // It should not add any overlap to add this to the first child at (0, 0);
-  EXPECT_EQ(parent->OverlapIncreaseToAdd(corner, 0, expanded), 0);
+  EXPECT_EQ(NodeOverlapIncreaseToAdd(parent.get(), 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);
+  EXPECT_EQ(NodeOverlapIncreaseToAdd(parent.get(), 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);
+  EXPECT_EQ(NodeOverlapIncreaseToAdd(parent.get(), 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);
+  EXPECT_EQ(NodeOverlapIncreaseToAdd(parent.get(), 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);
+  EXPECT_EQ(NodeOverlapIncreaseToAdd(parent.get(), 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);
+  EXPECT_EQ(NodeOverlapIncreaseToAdd(parent.get(), far_corner, 2, expanded), 3);
 }
 
-TEST_F(RTreeTest, NodeBuildLowBounds) {
-  ScopedVector<RTree::Node> nodes;
-  nodes.reserve(10);
+TEST_F(RTreeNodeTest, BuildLowBounds) {
+  ScopedVector<RTreeNodeBase> records;
+  records.reserve(10);
   for (int i = 1; i <= 10; ++i) {
-    nodes.push_back(new RTree::Node(Rect(0, 0, i, i), i));
+    records.push_back(new RTreeRecord(Rect(0, 0, i, i), i));
   }
-  std::vector<Rect> vertical_bounds;
-  std::vector<Rect> horizontal_bounds;
-  RTree::Node::BuildLowBounds(
-      nodes.get(), nodes.get(), &vertical_bounds, &horizontal_bounds);
+  RTreeRects vertical_bounds;
+  RTreeRects horizontal_bounds;
+  NodeBuildLowBounds(
+      records.get(), records.get(), &vertical_bounds, &horizontal_bounds);
   for (int i = 0; i < 10; ++i) {
     EXPECT_EQ(vertical_bounds[i], Rect(0, 0, i + 1, i + 1));
     EXPECT_EQ(horizontal_bounds[i], Rect(0, 0, i + 1, i + 1));
   }
 }
 
-TEST_F(RTreeTest, NodeBuildHighBounds) {
-  ScopedVector<RTree::Node> nodes;
-  nodes.reserve(25);
+TEST_F(RTreeNodeTest, BuildHighBounds) {
+  ScopedVector<RTreeNodeBase> records;
+  records.reserve(25);
   for (int i = 0; i < 25; ++i) {
-    nodes.push_back(new RTree::Node(Rect(i, i, 25 - i, 25 - i), i));
+    records.push_back(new RTreeRecord(Rect(i, i, 25 - i, 25 - i), i));
   }
-  std::vector<Rect> vertical_bounds;
-  std::vector<Rect> horizontal_bounds;
-  RTree::Node::BuildHighBounds(
-      nodes.get(), nodes.get(), &vertical_bounds, &horizontal_bounds);
+  RTreeRects vertical_bounds;
+  RTreeRects horizontal_bounds;
+  NodeBuildHighBounds(
+      records.get(), records.get(), &vertical_bounds, &horizontal_bounds);
   for (int i = 0; i < 25; ++i) {
     EXPECT_EQ(vertical_bounds[i], Rect(i, i, 25 - i, 25 - i));
     EXPECT_EQ(horizontal_bounds[i], Rect(i, i, 25 - i, 25 - i));
   }
 }
 
-TEST_F(RTreeTest, NodeChooseSplitAxisAndIndex) {
-  std::vector<Rect> low_vertical_bounds;
-  std::vector<Rect> high_vertical_bounds;
-  std::vector<Rect> low_horizontal_bounds;
-  std::vector<Rect> high_horizontal_bounds;
+TEST_F(RTreeNodeTest, ChooseSplitAxisAndIndex) {
+  RTreeRects low_vertical_bounds;
+  RTreeRects high_vertical_bounds;
+  RTreeRects low_horizontal_bounds;
+  RTreeRects high_horizontal_bounds;
   // In this test scenario we describe a mirrored, stacked configuration of
   // horizontal, 1 pixel high rectangles labeled a-f like this:
   //
   // shape: | v sort: | h sort: |
   // -------+---------+---------+
   // aaaaa  |    0    |    0    |
   //  bbb   |    1    |    2    |
   //   c    |    2    |    4    |
   //   d    |    3    |    5    |
   //  eee   |    4    |    3    |
@@ skipping 14 matching lines @@
   }
 
   // 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));
+  int smallest_vertical_margin =
+      NodeSmallestMarginSum(2, 3, low_vertical_bounds, high_vertical_bounds);
+  int smallest_horizontal_margin = NodeSmallestMarginSum(
+      2, 3, low_horizontal_bounds, high_horizontal_bounds);
+  EXPECT_LT(smallest_vertical_margin, smallest_horizontal_margin);
+
+  EXPECT_EQ(
+      3U,
+      NodeChooseSplitIndex(2, 5, low_vertical_bounds, high_vertical_bounds));
 
   // We rotate the shape to test horizontal split axis detection:
   //
   //         +--------+
   //         | a    f |
   //         | ab  ef |
   // sort:   | abcdef |
   //         | ab  ef |
   //         | a    f |
   //         |--------+
@@ skipping 23 matching lines @@
   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));
+  smallest_vertical_margin =
+      NodeSmallestMarginSum(2, 3, low_vertical_bounds, high_vertical_bounds);
+  smallest_horizontal_margin = NodeSmallestMarginSum(
+      2, 3, low_horizontal_bounds, high_horizontal_bounds);
+
+  EXPECT_GT(smallest_vertical_margin, smallest_horizontal_margin);
+
   EXPECT_EQ(3U,
-            RTree::Node::ChooseSplitIndex(
+            NodeChooseSplitIndex(
                 2, 5, low_horizontal_bounds, high_horizontal_bounds));
 }
 
-TEST_F(RTreeTest, NodeDivideChildren) {
+TEST_F(RTreeNodeTest, DivideChildren) {
   // Create a test node to split.
-  scoped_ptr<RTree::Node> test_node(new RTree::Node(0));
-  std::vector<RTree::Node*> sorted_children;
-  std::vector<Rect> low_bounds;
-  std::vector<Rect> high_bounds;
+  scoped_ptr<RTreeNode> test_node(new RTreeNode);
+  std::vector<RTreeNodeBase*> sorted_children;
+  RTreeRects low_bounds;
+  RTreeRects high_bounds;
   // Insert 10 record nodes, also inserting them into our children array.
   for (int i = 1; i <= 10; ++i) {
-    RTree::Node* node = new RTree::Node(Rect(0, 0, i, i), i);
-    test_node->AddChild(node);
-    sorted_children.push_back(node);
+    RTreeRecord* record = new RTreeRecord(Rect(0, 0, i, i), i);
+    test_node->AddChild(scoped_ptr<RTreeNodeBase>(record));
+    sorted_children.push_back(record);
     low_bounds.push_back(Rect(0, 0, i, i));
     high_bounds.push_back(Rect(0, 0, 10, 10));
   }
   // Split the children in half.
-  scoped_ptr<RTree::Node> split_node(
-      test_node->DivideChildren(low_bounds, high_bounds, sorted_children, 5));
+  scoped_ptr<RTreeNode> split_node(NodeDivideChildren(
+      test_node.get(), 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);
+  EXPECT_EQ(test_node->count(), 5U);
+  EXPECT_EQ(split_node->count(), 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(), i + 1);
-    EXPECT_EQ(split_node->children_[i]->key(), i + 6);
+    EXPECT_EQ(record(test_node.get(), i)->key(), i + 1);
+    EXPECT_EQ(record(split_node.get(), i)->key(), 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), 1));
-  scoped_ptr<RTree::Node> child_two(new RTree::Node(Rect(0, 0, 2, 2), 2));
-  scoped_ptr<RTree::Node> child_three(new RTree::Node(Rect(0, 0, 3, 3), 3));
-  test_parent->AddChild(child_one.get());
-  test_parent->AddChild(child_two.get());
-  test_parent->AddChild(child_three.get());
+TEST_F(RTreeNodeTest, RemoveChildNoOrphans) {
+  scoped_ptr<RTreeNode> test_parent(new RTreeNode);
+  RTreeRecord* child_one(new RTreeRecord(Rect(0, 0, 1, 1), 1));
+  RTreeRecord* child_two(new RTreeRecord(Rect(0, 0, 2, 2), 2));
+  RTreeRecord* child_three(new RTreeRecord(Rect(0, 0, 3, 3), 3));
+  test_parent->AddChild(scoped_ptr<RTreeNodeBase>(child_one));
+  test_parent->AddChild(scoped_ptr<RTreeNodeBase>(child_two));
+  test_parent->AddChild(scoped_ptr<RTreeNodeBase>(child_three));
   ValidateNode(test_parent.get(), 1U, 5U);
   // Remove the middle node.
-  ScopedVector<RTree::Node> orphans;
-  EXPECT_EQ(test_parent->RemoveChild(child_two.get(), &orphans), 2U);
+  ScopedVector<RTreeNodeBase> orphans;
+  EXPECT_EQ(test_parent->RemoveChild(child_two, &orphans), 2U);
   EXPECT_EQ(orphans.size(), 0U);
   EXPECT_EQ(test_parent->count(), 2U);
-  test_parent->RecomputeBoundsNoParents();
+  NodeRecomputeLocalBounds(test_parent.get());
   ValidateNode(test_parent.get(), 1U, 5U);
+  delete child_two;
   // Remove the end node.
-  EXPECT_EQ(test_parent->RemoveChild(child_three.get(), &orphans), 1U);
+  EXPECT_EQ(test_parent->RemoveChild(child_three, &orphans), 1U);
   EXPECT_EQ(orphans.size(), 0U);
   EXPECT_EQ(test_parent->count(), 1U);
-  test_parent->RecomputeBoundsNoParents();
+  NodeRecomputeLocalBounds(test_parent.get());
   ValidateNode(test_parent.get(), 1U, 5U);
+  delete child_three;
   // Remove the first node.
-  EXPECT_EQ(test_parent->RemoveChild(child_one.get(), &orphans), 0U);
+  EXPECT_EQ(test_parent->RemoveChild(child_one, &orphans), 0U);
   EXPECT_EQ(orphans.size(), 0U);
   EXPECT_EQ(test_parent->count(), 0U);
+  delete child_one;
 }
 
-TEST_F(RTreeTest, NodeRemoveChildOrphans) {
+TEST_F(RTreeNodeTest, RemoveChildOrphans) {
   // Build flattened binary tree of Nodes 4 deep, from the record nodes up.
-  ScopedVector<RTree::Node> nodes;
-  nodes.resize(15);
-  // Indicies 7 through 15 are record nodes.
-  for (int i = 7; i < 15; ++i) {
-    nodes[i] = new RTree::Node(Rect(0, 0, i, i), i);
+  ScopedVector<RTreeNode> nodes;
+  ScopedVector<RTreeRecord> records;
+  nodes.resize(7);
+  records.reserve(8);
+  for (int i = 0; i < 8; ++i) {
+    records.push_back(new RTreeRecord(Rect(0, 0, i, i), i + 1));
   }
+
   // Nodes 3 through 6 are level 0 (leaves) and get 2 record nodes each.
+  int record_counter = 0;
   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]);
+    RTreeNode* node = new RTreeNode;
+    node->AddChild(scoped_ptr<RTreeNodeBase>(records[record_counter++]));
+    node->AddChild(scoped_ptr<RTreeNodeBase>(records[record_counter++]));
+    nodes[i] = node;
   }
+
   // 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]);
+    RTreeNode* node = NewNodeAtLevel(1);
+    node->AddChild(scoped_ptr<RTreeNodeBase>(nodes[(i * 2) + 1]));
+    node->AddChild(scoped_ptr<RTreeNodeBase>(nodes[(i * 2) + 2]));
+    nodes[i] = node;
   }
-  // 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]);
+
+  // Node 0 is level 2 and gets 2 children.
+  RTreeNode* node_zero = NewNodeAtLevel(2);
+  node_zero->AddChild(scoped_ptr<RTreeNodeBase>(nodes[1]));
+  node_zero->AddChild(scoped_ptr<RTreeNodeBase>(nodes[2]));
+  nodes[0] = node_zero;
+
   // This should now be a valid node structure.
   ValidateNode(nodes[0], 2U, 2U);
 
   // Now remove the level 0 nodes, so we get the record nodes as orphans.
-  ScopedVector<RTree::Node> orphans;
+  ScopedVector<RTreeNodeBase> 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.
+  // Orphans should be all 8 records but no order guarantee.
   EXPECT_EQ(orphans.size(), 8U);
-  for (int i = 0; i < 8; ++i) {
-    EXPECT_EQ(orphans[i], nodes[i + 7]);
+  for (int i = 0; i < 8; i++) {
+    RTreeNodeBase* base = records[i];
+    for (ScopedVector<RTreeNodeBase>::iterator it = orphans.begin();
+         it != orphans.end();
+         ++it) {
+      if (*it == base) {
+        orphans.weak_erase(it);
+        break;
+      }
+    }
   }
+  EXPECT_EQ(orphans.size(), 0U);
 
   // Now we remove nodes 1 and 2 from the root, expecting no further orphans.
   // This prevents a crash due to double-delete on test exit, as no node should
   // own any other node right now.
   EXPECT_EQ(nodes[0]->RemoveChild(nodes[1], &orphans), 1U);
-  EXPECT_EQ(orphans.size(), 8U);
+  EXPECT_EQ(orphans.size(), 0U);
   EXPECT_EQ(nodes[0]->RemoveChild(nodes[2], &orphans), 0U);
-  EXPECT_EQ(orphans.size(), 8U);
-
-  // Prevent double-delete of nodes by both nodes and orphans.
-  orphans.weak_clear();
+  EXPECT_EQ(orphans.size(), 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), 1));
-  scoped_ptr<RTree::Node> child_two(new RTree::Node(Rect(0, 0, 2, 2), 2));
-  scoped_ptr<RTree::Node> child_three(new RTree::Node(Rect(0, 0, 3, 3), 3));
-  test_parent->AddChild(child_one.get());
-  test_parent->AddChild(child_two.get());
-  test_parent->AddChild(child_three.get());
+TEST_F(RTreeNodeTest, RemoveAndReturnLastChild) {
+  scoped_ptr<RTreeNode> test_parent(new RTreeNode);
+  RTreeRecord* child_one(new RTreeRecord(Rect(0, 0, 1, 1), 1));
+  RTreeRecord* child_two(new RTreeRecord(Rect(0, 0, 2, 2), 2));
+  RTreeRecord* child_three(new RTreeRecord(Rect(0, 0, 3, 3), 3));
+  test_parent->AddChild(scoped_ptr<RTreeNodeBase>(child_one));
+  test_parent->AddChild(scoped_ptr<RTreeNodeBase>(child_two));
+  test_parent->AddChild(scoped_ptr<RTreeNodeBase>(child_three));
   ValidateNode(test_parent.get(), 1U, 5U);
 
-  EXPECT_EQ(test_parent->RemoveAndReturnLastChild().release(),
-            child_three.get());
+  EXPECT_EQ(test_parent->RemoveAndReturnLastChild().release(), child_three);
   EXPECT_EQ(test_parent->count(), 2U);
-  test_parent->RecomputeBoundsNoParents();
+  NodeRecomputeLocalBounds(test_parent.get());
   ValidateNode(test_parent.get(), 1U, 5U);
+  delete child_three;
 
-  EXPECT_EQ(test_parent->RemoveAndReturnLastChild().release(), child_two.get());
+  EXPECT_EQ(test_parent->RemoveAndReturnLastChild().release(), child_two);
   EXPECT_EQ(test_parent->count(), 1U);
-  test_parent->RecomputeBoundsNoParents();
+  NodeRecomputeLocalBounds(test_parent.get());
   ValidateNode(test_parent.get(), 1U, 5U);
+  delete child_two;
 
-  EXPECT_EQ(test_parent->RemoveAndReturnLastChild().release(), child_one.get());
+  EXPECT_EQ(test_parent->RemoveAndReturnLastChild().release(), child_one);
   EXPECT_EQ(test_parent->count(), 0U);
+  delete child_one;
 }
 
-TEST_F(RTreeTest, NodeLeastOverlapIncrease) {
-  scoped_ptr<RTree::Node> test_parent(new RTree::Node(0));
-  // Construct 4 nodes with 1x2 retangles spaced horizontally 1 pixel apart, or:
+TEST_F(RTreeNodeTest, LeastOverlapIncrease) {
+  scoped_ptr<RTreeNode> test_parent(NewNodeAtLevel(1));
+  // Construct 4 nodes with 1x2 rects spaced horizontally 1 pixel apart, or:
   //
   // a b c d
   // a b c d
   //
   for (int i = 0; i < 4; ++i) {
-    test_parent->AddChild(new RTree::Node(Rect(i * 2, 0, 1, 2), i + 1));
+    RTreeNode* node = new RTreeNode;
+    RTreeRecord* record = new RTreeRecord(Rect(i * 2, 0, 1, 2), i + 1);
+    node->AddChild(scoped_ptr<RTreeNodeBase>(record));
+    test_parent->AddChild(scoped_ptr<RTreeNodeBase>(node));
   }
 
   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
   //
   Rect test_rect_far(7, 0, 1, 1);
-  std::vector<Rect> expanded_rects;
+  RTreeRects expanded_rects;
   BuildExpandedRects(test_parent.get(), test_rect_far, &expanded_rects);
-  RTree::Node* result =
-      test_parent->LeastOverlapIncrease(test_rect_far, expanded_rects);
-  EXPECT_EQ(result->key(), 4);
+  RTreeNode* result = NodeLeastOverlapIncrease(
+      test_parent.get(), test_rect_far, expanded_rects);
+  EXPECT_EQ(record(result, 0)->key(), 4);
 
   // 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
   //
   Rect test_rect_tie(0, 1, 7, 1);
   BuildExpandedRects(test_parent.get(), test_rect_tie, &expanded_rects);
-  result = test_parent->LeastOverlapIncrease(test_rect_tie, expanded_rects);
+  result = NodeLeastOverlapIncrease(
+      test_parent.get(), test_rect_tie, expanded_rects);
   EXPECT_TRUE(result == NULL);
 
   // Test rect completely inside c should return the third rectangle:
   //
   // a b T d
   // a b c d
   //
   Rect test_rect_inside(4, 0, 1, 1);
   BuildExpandedRects(test_parent.get(), test_rect_inside, &expanded_rects);
-  result = test_parent->LeastOverlapIncrease(test_rect_inside, expanded_rects);
-  EXPECT_EQ(result->key(), 3);
+  result = NodeLeastOverlapIncrease(
+      test_parent.get(), test_rect_inside, expanded_rects);
+  EXPECT_EQ(record(result, 0)->key(), 3);
 
   // 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), 9));
+  RTreeNode* record_parent = new RTreeNode;
+  record_parent->AddChild(
+      scoped_ptr<RTreeNodeBase>(new RTreeRecord(Rect(4, 0, 2, 2), 9)));
+  test_parent->AddChild(scoped_ptr<RTreeNodeBase>(record_parent));
   BuildExpandedRects(test_parent.get(), test_rect_inside, &expanded_rects);
-  result = test_parent->LeastOverlapIncrease(test_rect_inside, expanded_rects);
+  result = NodeLeastOverlapIncrease(
+      test_parent.get(), test_rect_inside, expanded_rects);
   EXPECT_TRUE(result == NULL);
 }
 
-TEST_F(RTreeTest, NodeLeastAreaEnlargement) {
-  scoped_ptr<RTree::Node> test_parent(new RTree::Node(0));
+TEST_F(RTreeNodeTest, LeastAreaEnlargement) {
+  scoped_ptr<RTreeNode> test_parent(NewNodeAtLevel(1));
   // Construct 4 nodes in a cross-hairs style configuration:
   //
   //  a
   // b c
   //  d
   //
-  test_parent->AddChild(new RTree::Node(Rect(1, 0, 1, 1), 1));
-  test_parent->AddChild(new RTree::Node(Rect(0, 1, 1, 1), 2));
-  test_parent->AddChild(new RTree::Node(Rect(2, 1, 1, 1), 3));
-  test_parent->AddChild(new RTree::Node(Rect(1, 2, 1, 1), 4));
+  RTreeNode* node = new RTreeNode;
+  node->AddChild(
+      scoped_ptr<RTreeNodeBase>(new RTreeRecord(Rect(1, 0, 1, 1), 1)));
+  test_parent->AddChild(scoped_ptr<RTreeNodeBase>(node));
+  node = new RTreeNode;
+  node->AddChild(
+      scoped_ptr<RTreeNodeBase>(new RTreeRecord(Rect(0, 1, 1, 1), 2)));
+  test_parent->AddChild(scoped_ptr<RTreeNodeBase>(node));
+  node = new RTreeNode;
+  node->AddChild(
+      scoped_ptr<RTreeNodeBase>(new RTreeRecord(Rect(2, 1, 1, 1), 3)));
+  test_parent->AddChild(scoped_ptr<RTreeNodeBase>(node));
+  node = new RTreeNode;
+  node->AddChild(
+      scoped_ptr<RTreeNodeBase>(new RTreeRecord(Rect(1, 2, 1, 1), 4)));
+  test_parent->AddChild(scoped_ptr<RTreeNodeBase>(node));
 
   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
   //
   Rect test_rect_below(1, 3, 1, 1);
-  std::vector<Rect> expanded_rects;
+  RTreeRects expanded_rects;
   BuildExpandedRects(test_parent.get(), test_rect_below, &expanded_rects);
-  RTree::Node* result =
-      test_parent->LeastAreaEnlargement(test_rect_below, expanded_rects);
-  EXPECT_EQ(result->key(), 4);
+  RTreeNode* result = NodeLeastAreaEnlargement(
+      test_parent.get(), test_rect_below, expanded_rects);
+  EXPECT_EQ(record(result, 0)->key(), 4);
 
   // Test rect completely inside b should require minimum area to add to Node b:
   //
   //  a
   // T c
   //  d
   //
   Rect test_rect_inside(0, 1, 1, 1);
   BuildExpandedRects(test_parent.get(), test_rect_inside, &expanded_rects);
-  result = test_parent->LeastAreaEnlargement(test_rect_inside, expanded_rects);
-  EXPECT_EQ(result->key(), 2);
+  result = NodeLeastAreaEnlargement(
+      test_parent.get(), test_rect_inside, expanded_rects);
+  EXPECT_EQ(record(result, 0)->key(), 2);
 
   // 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), 7));
+  node = new RTreeNode;
+  node->AddChild(
+      scoped_ptr<RTreeNodeBase>(new RTreeRecord(Rect(0, 1, 3, 1), 7)));
+  test_parent->AddChild(scoped_ptr<RTreeNodeBase>(node));
 
   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
   //
   Rect test_rect_tie_breaker(3, 1, 1, 1);
   BuildExpandedRects(test_parent.get(), test_rect_tie_breaker, &expanded_rects);
-  result =
-      test_parent->LeastAreaEnlargement(test_rect_tie_breaker, expanded_rects);
-  EXPECT_EQ(result->key(), 3);
+  result = NodeLeastAreaEnlargement(
+      test_parent.get(), test_rect_tie_breaker, expanded_rects);
+  EXPECT_EQ(record(result, 0)->key(), 3);
+}
+
+// RTreeTest ------------------------------------------------------------------
+
+// An empty RTree should never return Query results, and RTrees should be empty
+// upon construction.
+TEST_F(RTreeTest, QueryEmptyTree) {
+  RT rt(2, 10);
+  ValidateRTree(&rt);
+  base::hash_set<int> 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) {
+  RT rt(2, 5);
+  rt.Insert(Rect(0, 0, 100, 100), 1);
+  rt.Clear();
+  base::hash_set<int> 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) {
+  RT rt(2, 5);
+  AddStackedSquares(&rt, 100);
+  rt.Clear();
+  base::hash_set<int> 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) {
+  RT rt(2, 5);
+  // Add 100 stacked squares, but always with duplicate key of 0.
+  for (int i = 1; i <= 100; ++i) {
+    rt.Insert(Rect(0, 0, i, i), 0);
+    ValidateRTree(&rt);
+  }
+  base::hash_set<int> results;
+  Rect test_rect(1, 1);
+  rt.Query(test_rect, &results);
+  EXPECT_EQ(results.size(), 1U);
+  EXPECT_EQ(results.count(0), 1U);
+}
+
+// Call Remove() once on something that's been inserted repeatedly.
+TEST_F(RTreeTest, DuplicateInsertRemove) {
+  RT rt(3, 9);
+  AddStackedSquares(&rt, 25);
+  for (int i = 1; i <= 100; ++i) {
+    rt.Insert(Rect(0, 0, i, i), 26);
+    ValidateRTree(&rt);
+  }
+  rt.Remove(26);
+  base::hash_set<int> 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) {
+  RT rt(7, 15);
+  AddStackedSquares(&rt, 101);
+  for (int i = 0; i < 100; ++i) {
+    rt.Remove(101);
+    ValidateRTree(&rt);
+  }
+  base::hash_set<int> 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) {
+  RT rt(2, 5);
+  AddStackedSquares(&rt, 100);
+  base::hash_set<int> 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) {
+  RT rt(2, 10);
+  AddStackedSquares(&rt, 100);
+  base::hash_set<int> 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) {
+  RT rt(2, 7);
+  AddStackedSquares(&rt, 100);
+  base::hash_set<int> 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) {
+  RT rt(2, 11);
+  AddStackedSquares(&rt, 200);
+  for (int i = 101; i <= 200; ++i) {
+    rt.Remove(i);
+    ValidateRTree(&rt);
+  }
+  base::hash_set<int> results;
+  Rect test_rect(1, 1);
+  rt.Query(test_rect, &results);
+  EXPECT_EQ(results.size(), 100U);
+  VerifyAllKeys(results);
+  // Add the nodes back in.
+  for (int i = 101; i <= 200; ++i) {
+    rt.Insert(Rect(0, 0, i, i), i);
+    ValidateRTree(&rt);
+  }
+  results.clear();
+  rt.Query(test_rect, &results);
+  EXPECT_EQ(results.size(), 200U);
+  VerifyAllKeys(results);
+}
+
+TEST_F(RTreeTest, InsertNegativeCoordsRect) {
+  RT rt(5, 11);
+  for (int i = 1; i <= 100; ++i) {
+    rt.Insert(Rect(-i, -i, i, i), (i * 2) - 1);
+    ValidateRTree(&rt);
+    rt.Insert(Rect(0, 0, i, i), i * 2);
+    ValidateRTree(&rt);
+  }
+  base::hash_set<int> results;
+  Rect test_rect(-1, -1, 2, 2);
+  rt.Query(test_rect, &results);
+  EXPECT_EQ(results.size(), 200U);
+  VerifyAllKeys(results);
+}
+
+TEST_F(RTreeTest, RemoveNegativeCoordsRect) {
+  RT rt(7, 21);
+  // Add 100 positive stacked squares.
+  AddStackedSquares(&rt, 100);
+  // Now add 100 negative stacked squares.
+  for (int i = 101; i <= 200; ++i) {
+    rt.Insert(Rect(100 - i, 100 - i, i - 100, i - 100), 301 - i);
+    ValidateRTree(&rt);
+  }
+  // Now remove half of the negative squares.
+  for (int i = 101; i <= 150; ++i) {
+    rt.Remove(301 - i);
+    ValidateRTree(&rt);
+  }
+  // Queries should return 100 positive and 50 negative stacked squares.
+  base::hash_set<int> results;
+  Rect test_rect(-1, -1, 2, 2);
+  rt.Query(test_rect, &results);
+  EXPECT_EQ(results.size(), 150U);
+  VerifyAllKeys(results);
+}
+
+TEST_F(RTreeTest, InsertEmptyRectReplacementRemovesKey) {
+  RT rt(10, 31);
+  AddStackedSquares(&rt, 50);
+  ValidateRTree(&rt);
+
+  // Replace last square with empty rect.
+  rt.Insert(Rect(), 50);
+  ValidateRTree(&rt);
+
+  // Now query large area to get all rects in tree.
+  base::hash_set<int> 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);
 }
 
 }  // namespace gfx