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);
+      EXPECT_EQ(0, rt->root_->Level());
       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());
+    EXPECT_GT(rt->root_->Level(), -1);
     // 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.

[Peter Kasting, 2014/05/29 00:32:26]

I don't actually know what this comment means.

[luken, 2014/05/30 16:51:04]

I explained it better in the comments above, removed this comment.

     for (size_t i = 0; i < rt->root_->children_.size(); ++i) {

[Peter Kasting, 2014/05/29 00:32:26]

Nit: Use count() (many places)

[luken, 2014/05/30 16:51:04]

Done.

       ValidateNode(
           rt->root_->children_[i], rt->min_children_, rt->max_children_);

[Peter Kasting, 2014/05/29 00:32:26]

Nit: Use child() (many places)

[luken, 2014/05/30 16:51:04]

Done.

     }
   }
 
   // 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) {

[Peter Kasting, 2014/05/29 00:32:26]

Nit: Unlike r_tree_base.cc, this file consistently uses {} on one-line loop
bodies, so it's not necessary to remove them; but I might consider removing them
to be consistent with that file (and the majority of Chrome code).

[luken, 2014/05/30 16:51:04]

Done.

+        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->Level() - 1, child_node->Level());
       EXPECT_EQ(node, child_node->parent());
     }
-    EXPECT_EQ(node->rect_, check_bounds);
+    EXPECT_EQ(check_bounds, node->rect());
   }
 
   // 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

[Peter Kasting, 2014/05/29 00:32:26]

Nit: verifies

[luken, 2014/05/30 16:51:04]

Done.

   // 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) {

[Peter Kasting, 2014/05/29 00:32:26]

Nit: Use the RT::Matches typedef in place of hash_set<> everywhere (many places)

[luken, 2014/05/30 16:51:04]

Done.

+    // Verify that the keys are in values [0,count).
     for (size_t i = 1; i <= keys.size(); ++i) {
-      EXPECT_EQ(keys.count(i), 1U);
+      EXPECT_EQ(1U, keys.count(i));
     }
   }
 
   // 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

[Peter Kasting, 2014/05/29 00:32:26]

Nit: element of the rectangle -> element of the list

[luken, 2014/05/30 16:51:04]

Done.

   // 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, InsertDupToRoot) {
-  RTree rt(2, 5);
-  rt.Insert(Rect(0, 0, 1, 2), 1);
-  ValidateRTree(&rt);
-  rt.Insert(Rect(0, 0, 2, 1), 1);
-  ValidateRTree(&rt);
-}
-
-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); }

[Peter Kasting, 2014/05/29 00:32:26]

Nit: Since the caller must take ownership, return a scoped_ptr.

[luken, 2014/05/30 16:51:04]

Done.

+
+  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,
+                               const RTreeNodeBase* candidate_node,
+                               const Rect& expanded_rect) {
+    return node->OverlapIncreaseToAdd(rect, candidate_node, 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);
+  }
+
+  scoped_ptr<RTreeNodeBase> 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.

[Peter Kasting, 2014/05/29 00:32:26]

Nit: pointer

[luken, 2014/05/30 16:51:04]

Done.

-  EXPECT_EQ(removals.size(), 1U);
+  EXPECT_EQ(1U, removals.size());
   // There should be 19 left in the test_node.
-  EXPECT_EQ(test_node->count(), 19U);
+  EXPECT_EQ(19U, test_node->count());
   // 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(10, static_cast<RTreeRecord*>(removals[0])->key());
 
   // 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();
+  EXPECT_EQ(2U, removals.size());
+  EXPECT_EQ(17U, test_node->count());
+  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());
-  EXPECT_EQ(results_hash.count(9), 1U);
-  EXPECT_EQ(results_hash.count(11), 1U);
-}
-
-TEST_F(RTreeTest, NodeCompareVertical) {
+  results_hash.insert(static_cast<RTreeRecord*>(removals[0])->key());
+  results_hash.insert(static_cast<RTreeRecord*>(removals[1])->key());
+  EXPECT_EQ(1U, results_hash.count(9));
+  EXPECT_EQ(1U, results_hash.count(11));
+}
+
+TEST_F(RTreeNodeTest, CompareVertical) {
   // One rect with lower y than another should always sort lower than higher y.

[Peter Kasting, 2014/05/29 00:32:26]

Nit: Remove "than higher y"

[luken, 2014/05/30 16:51:04]

Done.

-  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(Rect(-10, -10, 21, 21), parent->rect());
+
+  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);

[Peter Kasting, 2014/05/29 00:32:26]

Nit: Trailing period, not semicolon.  Similarly, the subsequent comments should
all end with periods.

[luken, 2014/05/30 16:51:04]

Done.

-  EXPECT_EQ(parent->OverlapIncreaseToAdd(corner, 0, expanded), 0);
+  EXPECT_EQ(0, NodeOverlapIncreaseToAdd(
+      parent.get(), corner, parent->child(0), expanded));
 
   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(15, NodeOverlapIncreaseToAdd(
+      parent.get(), corner, parent->child(1), expanded));
 
   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(31, NodeOverlapIncreaseToAdd(
+      parent.get(), corner, parent->child(2), expanded));
 
   // 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(3, NodeOverlapIncreaseToAdd(
+      parent.get(), far_corner, parent->child(0), expanded));
 
   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(6, NodeOverlapIncreaseToAdd(
+      parent.get(), far_corner, parent->child(1), expanded));
 
   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(3, NodeOverlapIncreaseToAdd(
+      parent.get(), far_corner, parent->child(2), expanded));
 }
 
-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));
+    EXPECT_EQ(Rect(0, 0, i + 1, i + 1), vertical_bounds[i]);

[Peter Kasting, 2014/05/29 00:32:26]

Seems like this first arg is equivalent to "records[i]->rect()" -- would it make
any more sense to compare against this?

[luken, 2014/05/30 16:51:04]

Done.

+    EXPECT_EQ(Rect(0, 0, i + 1, i + 1), horizontal_bounds[i]);
   }
 }
 
-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));
+    EXPECT_EQ(Rect(i, i, 25 - i, 25 - i), vertical_bounds[i]);

[Peter Kasting, 2014/05/29 00:32:26]

Similar comment.

[luken, 2014/05/30 16:51:04]

Done.

+    EXPECT_EQ(Rect(i, i, 25 - i, 25 - i), horizontal_bounds[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 |
   //         |--------+
   // v sort: | 024531 |
   // h sort: | 012345 |
   //         +--------+
   //
   // Clear out old bounds first.

[Peter Kasting, 2014/05/29 00:32:26]

Nit: Perhaps the remainder of this function should be in a second test since it
doesn't really want to preserve any state from the code above.

[luken, 2014/05/30 16:51:04]

Done.

   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));
+  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<RTreeNodeBase> split_node_base(NodeDivideChildren(
+      test_node.get(), low_bounds, high_bounds, sorted_children, 5));
+  RTreeNode* split_node = static_cast<RTreeNode*>(split_node_base.get());
   // Both nodes should be valid.
   ValidateNode(test_node.get(), 1U, 10U);
-  ValidateNode(split_node.get(), 1U, 10U);
+  ValidateNode(split_node, 1U, 10U);
   // Both nodes should have five children.
-  EXPECT_EQ(test_node->children_.size(), 5U);
-  EXPECT_EQ(split_node->children_.size(), 5U);
+  EXPECT_EQ(5U, test_node->count());
+  EXPECT_EQ(5U, split_node->count());
   // 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(i + 1, record(test_node.get(), i)->key());
+    EXPECT_EQ(i + 6, record(split_node, i)->key());
   }
 }
 
-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));

[Peter Kasting, 2014/05/29 00:32:26]

Use scoped_ptrs instead of raw pointers in all cases where you call "new". (Many
places in this file)

Note that in this case, that means your RemoveChild() calls will have to
reference child(i) instead of a raw pointer you have sitting around.

[luken, 2014/05/30 16:51:04]

Done.

+  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);
-  EXPECT_EQ(orphans.size(), 0U);
-  EXPECT_EQ(test_parent->count(), 2U);
-  test_parent->RecomputeBoundsNoParents();
+  ScopedVector<RTreeNodeBase> orphans;
+  EXPECT_EQ(2U, test_parent->RemoveChild(child_two, &orphans));
+  EXPECT_EQ(0U, orphans.size());
+  EXPECT_EQ(2U, test_parent->count());
+  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(orphans.size(), 0U);
-  EXPECT_EQ(test_parent->count(), 1U);
-  test_parent->RecomputeBoundsNoParents();
+  EXPECT_EQ(1U, test_parent->RemoveChild(child_three, &orphans));
+  EXPECT_EQ(0U, orphans.size());
+  EXPECT_EQ(1U, test_parent->count());
+  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(orphans.size(), 0U);
-  EXPECT_EQ(test_parent->count(), 0U);
+  EXPECT_EQ(0U, test_parent->RemoveChild(child_one, &orphans));
+  EXPECT_EQ(0U, orphans.size());
+  EXPECT_EQ(0U, test_parent->count());
+  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;
-  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);
+  ScopedVector<RTreeNodeBase> orphans;
+  EXPECT_EQ(1U, nodes[1]->RemoveChild(nodes[3], &orphans));
+  EXPECT_EQ(0U, nodes[1]->RemoveChild(nodes[4], &orphans));
+  EXPECT_EQ(1U, nodes[2]->RemoveChild(nodes[5], &orphans));
+  EXPECT_EQ(0U, nodes[2]->RemoveChild(nodes[6], &orphans));
 
-  // 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]);
+  // Orphans should be all 8 records but no order guarantee.
+  EXPECT_EQ(8U, orphans.size());
+  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(0U, orphans.size());
 
   // 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

[Peter Kasting, 2014/05/29 00:32:26]

What would double-free otherwise?  Seems like we should never be in a state
where there's double ownership.

[luken, 2014/05/30 16:51:04]

By not using raw pointers to wrap these objects. |nodes| owns all the Node
objects, but nodes[0] also owns nodes[1] and nodes[2] as they are currently
children of nodes[0].

[Peter Kasting, 2014/05/30 18:51:18]

That indicates that this test is buggy.  Because AddChild() causes the parent to
take ownership of the child, we should never be doing an AddChild() followed by
placing the same node pointer into a ScopedVector.

It looks to me as if the code should look more like this (but with comments):

  scoped_ptr<RTreeNode> root_node(NewNodeAtLevel(2));

  std::vector<RTreeNode*> level_one_nodes;
  std::vector<RTreeRecord*> records;
  int record_counter = 0;
  for (size_t i = 0; i < 2; ++i) {
    scoped_ptr<RTreeNode> level_one_node(NewNodeAtLevel(1));
    level_one_nodes.push_back(level_one_node.get());
    for (size_t j = 0; j < 2; ++j) {
      scoped_ptr<RTreeNode> level_zero_node(new RTreeNode);
      for (size_t k = 0; k < 2; ++k) {
        scoped_ptr<RTreeRecord> record(new RTreeRecord(
            Rect(0, 0, record_counter, record_counter), record_counter + 1));
        records.push_back(record.get());
        level_zero_node->AddChild(record.PassAs<RTreeNodeBase>());
        ++record_counter;
      }
      level_one_node->AddChild(level_zero_node.Pass());
    }
    root_node->AddChild(level_one_node.Pass());
  }

  ValidateNode(root_node.get(), 2U, 2U);

  ScopedVector<RTreeNodeBase> orphans;
  for (std::vector<RTreeNode*>::iterator i(level_one_nodes.begin());
       i != level_one_nodes.end(); ++i) {
    EXPECT_EQ(1U, (*i)->RemoveChild((*i)->child(0), &orphans));
    EXPECT_EQ(0U, (*i)->RemoveChild((*i)->child(0), &orphans));
  }

  ...rest of test continues here

This ensures that heap-allocated objects are always owned by exactly one other
object at all times.

[luken, 2014/05/30 19:23:39]

So storage of raw pointer values is OK within vectors but not individually? What
is the rule here?

[luken, 2014/05/30 19:39:33]

Additionally, how should I delete the nodes in level_one_nodes? With a for loop?
Or put them back in scoped_ptr somewhere after the call to RemoveChild()?

[Peter Kasting, 2014/05/30 19:49:31]

The key is in my previous comment: heap-allocated objects should always be owned
by exactly one other object at all times.

As long as such an object is owned, you can have an arbitrarily large number of
additional raw pointers pointing to it (but must make sure no one uses those
pointers after the object is destroyed).  What you don't want is _only_ raw
pointers to an object, or more than one object thinking it owns the pointer.

BAD:

  Foo* f = new Foo();
  Foo* g = f;
  std::vector<Foo*> foo_vec;
  foo_vec.push_back(f);
  // Three pointers to the object, but none owns it.
  // It will leak unless we manually delete one of the pointers.

ALSO BAD:

  scoped_ptr<Foo> f(new Foo());
  ScopedVector<Foo> foo_vec;
  foo_vec.push_back(f.get());
  // Two objects that both think they own the same Foo.
  // It will be double-freed unless we eliminate one of the
  // owning relationships.

GOOD:

  scoped_ptr<Foo> f(new Foo());
  Foo* raw_f = f.get();
  std::vector<Foo*> foo_vec;
  foo_vec.push_back(raw_f);
  // Three different references to the Foo, but only one owns it.
  // The others are weak (raw), we merely need to ensure they're
  // not used after the Foo is deleted.

ALSO GOOD:

  scoped_ptr<Foo> f(new Foo());
  ScopedVector<Foo> foo_vec;
  foo_vec.push_back(f.release());
  // Again, only one object owns the Foo.

In other words, whether raw pointers are OK has nothing to do with whether
they're alone or in a container; it's all about ensuring that an object is owned
by exactly one thing.  Your existing code double-owns the objects.
Ah, I missed the fact that RemoveChild() removes the child in question from the
ownership hierarchy, but neither frees it nor explicitly returns ownership of it
to the caller.  That means the code I wrote leaks the removed children.  This is
really a symptom of the problem that the RemoveChild() API is easy to misuse.

If RemoveChild() makes the child in question no longer owned, but doesn't free
it outright, it should pass ownership back to the caller, like so:

scoped_ptr<NodeBase> RemoveChild(NodeBase* child, Nodes* orphans);

This way, callers who wish to preserve the child can do so, and callers who
ignore the return value will cause the child to be deleted, avoiding a memory
leak.

This does force callers who want to know the number of remaining children to
explicitly call count(); I don't think that's too bad, but if you viewed it as a
huge problem, you could pass a size_t outparam.

Once this API change is made, this unittest code should be pretty
straightforward.

[luken, 2014/06/03 21:04:59]

The refactor is done. I had a question about a technique, which I've left as a
comment in the review on the latest patch set.

   // own any other node right now.
-  EXPECT_EQ(nodes[0]->RemoveChild(nodes[1], &orphans), 1U);
-  EXPECT_EQ(orphans.size(), 8U);
-  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(1U, nodes[0]->RemoveChild(nodes[1], &orphans));
+  EXPECT_EQ(0U, orphans.size());
+  EXPECT_EQ(0U, nodes[0]->RemoveChild(nodes[2], &orphans));
+  EXPECT_EQ(0U, orphans.size());
 }
 
-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->count(), 2U);
-  test_parent->RecomputeBoundsNoParents();
+  EXPECT_EQ(child_three, test_parent->RemoveAndReturnLastChild().release());
+  EXPECT_EQ(2U, test_parent->count());
+  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->count(), 1U);
-  test_parent->RecomputeBoundsNoParents();
+  EXPECT_EQ(child_two, test_parent->RemoveAndReturnLastChild().release());
+  EXPECT_EQ(1U, test_parent->count());
+  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->count(), 0U);
+  EXPECT_EQ(child_one, test_parent->RemoveAndReturnLastChild().release());
+  EXPECT_EQ(0U, test_parent->count());
+  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(4, record(result, 0)->key());
 
   // 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(3, record(result, 0)->key());
 
   // 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(4, record(result, 0)->key());
 
   // 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(2, record(result, 0)->key());
 
   // 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(3, record(result, 0)->key());
+}
+
+// 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(0U, results.size());
+  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(0U, results.size());
+  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(0U, results.size());
+  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(1U, results.size());
+  EXPECT_EQ(1U, results.count(0));
+}
+
+// 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(25U, results.size());
+  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(100U, results.size());
+  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(100U, results.size());
+  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(100U, results.size());
+  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(0U, results.size());
+}
+
+// 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(100U, results.size());
+  VerifyAllKeys(results);
+  // Add the nodes back in.

[Peter Kasting, 2014/05/29 00:32:26]

Nit: Maybe blank line above this?

[luken, 2014/05/30 16:51:04]

Done.

+  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(200U, results.size());
+  VerifyAllKeys(results);
+}
+
+TEST_F(RTreeTest, InsertDupToRoot) {
+  RT rt(2, 5);
+  rt.Insert(Rect(0, 0, 1, 2), 1);
+  ValidateRTree(&rt);
+  rt.Insert(Rect(0, 0, 2, 1), 1);
+  ValidateRTree(&rt);
+}
+
+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(200U, results.size());
+  VerifyAllKeys(results);
+}
+
+TEST_F(RTreeTest, RemoveNegativeCoordsRect) {
+  RT rt(7, 21);
+  // Add 100 positive stacked squares.

[Peter Kasting, 2014/05/29 00:32:26]

Similarly, maybe blank lines above the commented code blocks in this function.

[luken, 2014/05/30 16:51:04]

Done.

+  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(150U, results.size());
+  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(49U, results.size());
+  VerifyAllKeys(results);
 }
 
 }  // namespace gfx